本文共 1372 字,大约阅读时间需要 4 分钟。
参考Application of natural computation inspired method in community detection
自然计算方法受自然启发,具有自适应性、自组织性和自学习能力.
自然计算方法: (1)进化算法(EA)主要包括遗传算法(GA),免疫算法(IA),模拟退火法(SA) (2)群智能(包括蚁群优化(ACO)算法、粒子群优化(PSO)算法) (3)神经网络 多目标优化算法(MOP) 在用进化算法求解优化问题的迭代过程中,往往需要选择合适的目标函数[55]。单目标函数的优化可以始终获得与该目标函数相对应的最优解。然而,当解决现实中的实际问题时,通常不仅需要优化一个目标。这这类问题称为多目标优化问题。多目标优化问题的求解不是单最优解,而是最优解集 进化算法 遗传算法:遗传算法的关键技术有:编码、种群初始化、个体评价、遗传算子的设计等,遗传算子主要包括选择算子,交接算子,突变算子。 适用于非线性,多变量问题,对于一些复杂的问题,没有明确的函数关系。 遗传算法的特征 (1)根据目标函数进行智能搜索 (2)渐变式优化,不断逼近最优结果 (3)可以逼近全局最优解,不会陷入局部最优解 (4)只考虑输入和输出之间的黑箱式操作 (5)并行式的计算 遗传算法的过程:第一代随机产生一些初始点,到五代时向局部最优解靠拢,到11代时,向全局最优解靠拢,如果关系很复杂时,收敛的很慢。 遗传算法今后的发展: (1)编码技术和程序表达技术的改进 (2)复制(根据适应度的大小复制,用轮盘方式来选择复制),交换,突变等遗传操作的改进 (3)适应度的表达和计算的改进 (4)寻找其他有效的遗传算子,防止近缘杂交,过早收敛(开始收敛的很快,后来不变了,无法达到最优解) 遗传算法的过程 (1)编码,随机产生初始群体,一般该种群的数量为100~500,编码直接决定速度,效果 (2)个体评价(是否达到全局最优解),将目标函数值作为个体的适应度,用适应度来衡量,淘汰差的个体,选择优秀个体 (3)选择(复制)操作。根据种群中个体的适应度大小,通过轮盘赌等方式将适应度高的个体从当前种群中选择出来。其中轮盘赌即是与适应度成正比的概率来确定各个个体遗传到下一代群体中的数量。具体步骤如下: (1)首先计算出所有个体的适应度总和Σfi。 (2)其次计算出每个个体的相对适应度大小fi/Σfi,类似于softmax。 (3)再产生一个0到1之间的随机数,依据随机数出现在上述哪个概率区域内来确定各个个体被选中的次数。
(4)随机交叉运算(留下来的优秀个体)该步骤是遗传算法中产生新的个体的主要操作过程,它用一定的交配概率阈值(pc,一般是0.4到0.99)来控制是否采取单点交叉,多点交叉等方式生成新的交叉个体。
具体步骤如下: (1)先对群体随机配对。 (2)再随机设定交叉点的位置。 (3)再互换配对染色体间的部分基因。
(5)随机变异运算,该步骤是产生新的个体的另一种操作。一般先随机产生变异点,再根据变异概率阈值(pm,一般是0.0001到0.1)将变异点的原有基因取反。
(6) 个体评价,优胜劣汰 程序参考https://blog.csdn.net/quinn1994/article/details/80501542