下载掌阅APP，畅读海量书库
立即打开
可以认为Memetic算法是由遗传算法改进得到的，相比于遗传算法，Memetic算法的重点就是多了局部搜索机制，所以该算法的算法流程图与遗传算法的算法流程有很多相似之处。一般地，Memetic算法流程图可以由图3.1表示。如图3.1可知，Memetic算法执行的具体步骤如下所述。
步骤1：确定解的编码方法和算法执行中的所有参数；
步骤2：初始化种群，得到父代群体；
步骤3：执行交叉算子；
步骤4：利用局部搜索算法对个体进行邻域搜索，更新种群所有个体；
步骤5：执行变异算子；
步骤6：再次利用局部搜索算法更新种群个体；
步骤7：根据适应度函数计算种群内个体的适应度值；
步骤8：执行选择算子，保留当前种群内的优秀个体（适应度值高的个体），产生新种群；
步骤9：判断是否满足终止条件，若满足终止条件则算法结束，输出优化结果；若不满足终止条件，则跳转到步骤3继续执行。
随着新问题的提出，问题规模的增大，人们对求解精度要求的提高等，在应用Memetic算法时，必须对算法本身进行改进，以适应新的问题和新的要求。Memetic算法可改进的思路很多，可以从编码方式、种群初始化方法、交叉算子、变异算子、选择算子、局部搜索算子等多方面入手。
图3.1 Memetic算法流程图
根据采用的符号，可以将编码方式分为二进制编码、实数编码和整数编码等；根据编码的长度可以将编码方式分为变长度编码和不可变长度编码。选择什么样的编码方式，需要根据特定问题进行选择，合适的编码方式有利于算法的执行，降低算法难度，提高算法效率等。
种群初始化方式分为两种：在无先验知识时，采用完全随机的初始化方法；当有一定先验知识时，可以通过设定相关的机制，融入先验知识来生成初始种群。
常用的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉等。对于特殊的问题也有特殊的交叉方式，如Memetic算法用于社区检测时，还可以使用双向交叉 [17] 。
变异算子可以在一定程度上提高局部搜索能力，增加种群多向性，但当问题较复杂时，就无法达到想要的效果。常用的变异方法包括单点变异、互换变异、插入变异等。
同遗传算法一样，Memetic算法常用的选择操作有轮盘赌选择、竞标赛选择、排序选择等，主要作用就是保留种群中的优秀个体到下一代，以实现优胜劣汰。
从某些方面来看，可以把Memetic算法看成是遗传算法的改进方法，而局部搜索算子就是使Memetic算法不同于遗传算法的重要突破点，它在遗传算法中加入局部搜索机制，使传统的遗传算法具有全局和局部的搜索能力。常用的局部搜索机制有爬山算法、模拟退火算法、禁忌搜索算法等。针对不同问题，应选择不同的局部搜索方法，局部搜索效率越高，整个Memetic算法的效率也越高。
（1）爬山算法。从当前解开始，搜索邻域计算适应度值，选出适应度值最高的个体作为山峰（最高点），继续对新个体的邻域进行搜索，若当前最大适应度值大于山峰适应度值，则将替换山峰值和点。循环上述步骤，直到找到邻域范围内的最大适应度值个体 [18] 。基于爬山算法基础，罗彪等提出了一种定向爬山算法 [19] 。牟宏鑫等针对图像调焦问题，提出了一种改进的自动调焦爬山算法，有效地避免了局部极值的干扰 [20] 。
（2）模拟退火算法。模拟退火算法源于固体退火原理，每个解个体是一个分子，解的适应度值则相当于分子的内能。首先固体加热到非常高的温度，此时固体内部粒子内能增大，然后逐渐降低温度，粒子内能逐渐减小，当温度达到基态时内能最小，即是算法求到的最小解 [21] 。所以该算法的重要参数有初始温度、可降到的最低温度、控制温度降低的衰减因子和同一温度时的迭代次数等。
（3）禁忌搜索算法。前面两种局部搜索算法，只比较了子代个体与父代个体间的最优解，这使算法容易陷入局部最优，而禁忌搜索算法为了避免局部最优，构建了禁忌搜索表，该表记录了出现过的最优的 n 个解，在新的搜索中，若新解优于表中的 n 个解，则替换。
近些年，Memetic算法受到越来越多研究人员的关注，并被广泛应用于许多不同的领域，如最优化搜索、自动规划、机器人学习、经济模型、免疫系统、社会系统以及进化和学习的交互等。
从优化的观点来讲，针对某些问题，Memetic算法比传统的遗传算法更有效率，它可以更快地找到最优解，同时求解的精度更高。因此Memetic算法获得了广泛的认同，特别是在组合优化问题上，采用Memetic算法的求解结果往往比其他的启发式搜索方法要好很多 [34] 。
Memetic算法根据发展历程可以分为规范Memetic算法、适应性Memetic算法（超启发式Memetic算法、多Memetic算法、协同Memetic算法、后拉马克Memetic算法）等类型。
（1）规范Memetic算法：遗传算法作为一种计算模型，充分模拟了生物的进化机制；
而Memetic算法则是一种模拟文化进化的机制 [35] ，可以看作人们交流思想时被复制的信息单元。Memetic算法中的种群是由许多的局部最优值组成的。
（2）适应性Memetic算法：作为一个新的研究领域，Ong等对其进行了很好的归纳，并称其为适应性Memetic算法 [36] 。适应性Memetic算法包括Krasnogor提出的多Memetic算法 [37-40] ，Smith提出的与多Memetic算法相似的协同Memetic算法 [41-42] ，Ong和Keane等提出的后拉马克Memetic算法以及超启发式Memetic算法等。这些算法具有一个共同的特点，那就是在进行搜索的过程中会采用很多密母，而具体采用哪个密母（如meme、文化基因）则是动态选择的。首先算法会随机或按照某种特定的方式生成种群，接下来针对种群中的每一个个体，在密母池中选择合适的密母进行局部搜索。针对组合优化问题的求解，Cowing等提出了超启发式 [43] ，它描述了融合不同的密母以在不同的确定点应用不同密母的思想。Krasnogor等也提出了与超启发式类似的思想。针对超启发式搜索的局部搜索的方式也很多，拉马克和班德文学习正是密母算法中经常采用的学习机制。通过个体适应度值的局部改进，原来种群将被改进种群取代。Ong和Keane在对连续非线性函数优化的过程中，采用了后拉马克学习机制对标准问题的特性进行了研究 [43] 。由于在对Memetic算法搜索的研究中主要采用了拉马克学习机制，因此这种Memetic算法被称为后拉马克学习。这种机制的机理主要是在多密母信息中引入竞争和合作，以更有效地解决问题。