文化基因算法(Memetic Algorithm)研究进展（文化基因（模因）算法新手入门）

各类优化算法入门优秀论文总结目录

1.摘要

文化基因算法（memetic algorithm）是 Pablo Moscato 提出的建立在模拟文化进化基础上的优化算法,它实质上是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。文化基因算法的概念被提出后,已被越来越多的研究人员接受和采纳。
本文主要介绍了文化基因算法的起源、实现过程,以及在各类优化问题中的应用情况。

2.介绍

Pablo Moscato 于 1989 年首次提出 memetic algorithm 的概念。Memetic一词由meme而来,其谐音译法很多,根据道金斯提出的本意,应理解为“文化基因”,因此我们将Memetic algorithm称为文化基因算法。
Pablo Moscato 认为,在遗传算法（GA）中,变异操作可以看作是含有一定噪声的爬山搜索,实际上模拟遗传编码和自然选择的过程不应包含变异操作,因为在文化进化的过程中,在众多的随机变化步骤中得到一个正确的可提高整体性能的一步进展是非常困难的,只有此领域的拥有足够的专业知识的精通者们,才有可
能创造新的进展,但是这样的事情发生的频率是很低的。因此,文化基因的传播过程应是严格复制的,若要发生变异,那么每一步的变异都需要有大量的专业知识支撑,而所有的变异都应带来进展而不是混乱,这就是为什么我们观察到的文化进化速度要比生物进化速度快得多的原因。对应于模拟生物进化过程的遗传算法,Moscato提出了模拟文化进化过程的文化基因算法,文化基因算法用局部启发式搜索来模拟由大量专业知识支撑的变异过程,因此说,文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。
文化基因算法的这种全局搜索和局部搜索的结合机制使其搜索效率在某些问题领域比传统遗传算法快几个数量级,可应用于广泛的问题领域并得到满意的结果。很多人将文化基因算法看作混合遗传算法、遗传局部搜索或是拉马克式进化算法,实际上,文化基因算法提出的是一种框架、是一个概念,在这个框架下,采用不同的搜索策略可以构成不同的文化基因算法,如全局搜索策略可以采用遗传算法、进化策略、进化规划等,局部搜索策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式局部搜索等。
在遗传算法中,我们通常对个体（Individual）进行选择、交叉、变异操作,通过对一代一代个体的适应性进化得到问题的最优解。在文化基因算法中,用了智能体（agent,实际上agent在此译为“代表”更加恰当）的概念,遗传操作的对象并不是种群空间中的普通个体,而是各局部区域推选出的优秀代表,遗传操作的结果是选出那些适应性强的优秀代表,同时也产生一些交叉作用后新的个体,这些新个体可能属于一些新的区域,在下一代的局部搜索中它们会被附近的优秀个体取代,然后再进行进一步的全局进化。这种局部与全局的混合搜索机制显然要比单纯在普通个体间搜索的进化效率高得多。

3.文化基因算法总体框架

文化基因算法作为一种混合算法框架,其各个环节均存在多种实施策略和较宽的探讨空间,下面分别进行讨论:

1. 初始种群的产生
   初始种群一般是随机产生的,也可以利用优化问题的先验知识人为加入一些优秀个体,例如,若已知最优个体在某区域的概率较大,可以在该区域内选取较多的个体加入初始种群。初始种群的选择应确保种群的多样性。一般地,文化基因算法将对初始种群的每一个个体进行局部搜索,将每个个体邻域内的最优个体替
   换该个体,形成新的初始种群。
2. 进化操作
   进化操作可以采用遗传算法中的交叉、变异算子,也可以只进行交叉,或只进行变异。有些研究人员还针对具体的优化问题,或结合所使用的局部搜索策略,研究了新的进化算子。不管采用何种进化算子,应确保子代能够遗传父代的主要特征,同时又能探索到未知的区域。
3. 局部搜索
   局部搜索的过程也就是推举局部区域优秀个体的过程。局部搜索的关键问题在于:
   a）邻域的确定:对于连续系统,可以以当前个体为中心,选取距离为ε的欧式空间,对于离散系统,可以选取球形、立方体等空间结构作为个体的邻域空间。邻域空间取得越大,整体算法的优化效率就越高,但同时也使算法的计算时间延长。
   b）局部搜索策略:可选择的方法很多,可以针对函数优化问题或组合优化问题选用不同的适用策略,同时也应考虑算法效率问题。文献[7]针对一组标准测试函数研究了模拟退火、禁忌搜索和导引式搜索（Guided local search,GLS）三种局部搜索策略对算法性能的影响,认为采用导引式局部搜索可以使算法更易收敛。
   c）局部搜索在算法流程中的位置:在何时执行局部搜索操作也是算法设计过程中需要确定的一项内容。有些算法让每个个体在进行交叉、变异后再逐个进行局部搜索（如图1所示的例子）,有些算法则将局部搜索分别安排在交叉和变异操作之后,即每一代的进化过程进行两次局部优化[8]。
4. 新种群的产生
   一般经过进化操作和局部搜索后,种群数目会大于初始种群的数目,为了保证种群的多样性,可以采用轮盘赌选择、截断选择、锦标赛选择等方法选出相对较优的个体形成新的种群。
5. 终止策略
   同其他启发式优化算法一样,进化终止条件可以定为:达到一定的迭代步数,或最优结果达到要求的精度。

各类优化算法入门优秀论文总结目录