3.1　Memetic算法发展历程

Memetic算法由Pablo Moscato在1989年提出。遗传算法主要是模拟物种的进化过程，而Memetic算法主要是为了模仿文化进化过程 ^[3-5] 。其中，个体的局部搜索优化过程就是模拟人在成长过程中的学习过程；个体通过在其邻域搜索找到局部最优解来达到提高适应度函数的目的，正如人通过学习提高自身能力一样。

因Memetic算法优化性能远高于单纯的遗传算法，所以被广泛关注并应用到许多研究领域中。

改进的Memetic算法已在社区检测（community detection）问题中使用并取得了成功。如在文献[6]中，作者主要研究社区检测中分辨率受限的问题，并提出称为Meme-Net的Memetic算法来解决该问题。在文献[7]中，作者提出了一种可以有效解决社区检测问题的快速Memetic算法，该算法采用多级学习作为局部搜索算子，实验表明了算法的有效性。在文献[8]中，作者提出了一种快速的Memetic算法来解决社交网络的结构平衡问题。

Lacomme等在2001年将Memetic算法应用到CARR问题的求解中，但它的不足在于全局搜索能力不强 ^[9] 。2004年Lacomme等又提出了一种更高效的模因演算算法LMA ^[10] ，通过对某些解执行重新进化和提高局部搜索概率，从而提高了解的收敛速度，但是其只增加了局部搜索能力，全局寻优能力依然不强。之后，唐柯等又在LMA的框架下引入了扩展步长的领域搜索（MAENS）方法，使算法可以跳出局部最优，并在测试集上获得良好的下界 ^[11] 。随着关于LSCARP的研讨越来越深入，2013年，梅一等又将该算法与路由距离分组（RDG）方案 ^[12] 相结合提出了RDG-MAENS算法。在该算法中，首先采用RDG策略将路由问题中的任务集合分为多个小的任务集，再使用MAENS独立处理每个子任务集合。并且，Memetic算法在多目标CARP的应用也越来越多，如2011年梅一等提出的D-MAENS算法 ^[13] 。

另外，Memetic算法还经常被用来训练神经网络，Toby O. Hara等 ^[14] 和H. A. Abbass等 ^[15] 分别用Memetic算法来训练神经网络，实验结果表明Memetic算法的寻优能力及搜索速度较其他传统方法更快。Tatiane R. Bonfim等 ^[16] 不仅利用Memetic算法训练神经网络系统，还将其应用于并行机调度问题，两者都取得了很好的效果。

Memetic算法因其较强的优化能力，使其还可用于解决TSP、模糊系统控制、图像处理等优化问题中，在这里不再一一赘述，本书将在3.3节和3.4节详细描述Memetic算法在社区检测和限量弧路由问题上的应用。 w3pvnMYL2P89cpFDWdzV26yJgjQXphyt1Z5AZboueCU+Ao8xelFSiJ1PbMaSCeN8