基于多种群多策略的混合遗传-蚁群算法及应用研究*

周 頔

（四川文理学院 达州 635000）

1 引言

当前在工农业、国防、信息、经管等领域中的诸多问题都可转化为组合优化问题，而在使用智能优化算法解决这些问题时，都表现出自身的优势与不足［1］。所以不少的研究是针对特定问题，基于各自优化互补思想，以融合、结合等方式，建立多种智能优化算法相结合的混合型智能算法，增强其求解复杂问题的能力。在这些混合型智能算法中，充分结合了各种算法的优点，得到了广泛的关注与重视。遗传算法是一种通过模拟自然进化过程搜索最优解的方法［2］。它在求解过程不需要求导，非常适用于大规模并行计算。蚁群算法是通过模拟自然界蚁群寻食过程中通过信息素的相互交流从而找到由蚁巢至食物的最短路径的现象，而提出的一种基于信息正反馈原理的蚁群优化算法［2～3］。这两种智能算法都具有并行性、鲁棒性和自组织性等特点，基于群体的能力来求解问题，获得最优解。因此获得了广泛的研究及应用。如邵晓巍等［4］提出一种基于蚁群算法信息量留存的遗传算法；彭沛夫等［5］提出基于遗传因子的自适应蚁群算法；张应辉等［6］提出基于蚁群信息素和选择基因的概率的选择基因的方法；陶利民等［7］提出一种带有近邻节点选择策略和遗传算子的蚁群算法；董蓉等［8］提出一种混合遗传—蚁群算法，用于求解柔性作业车间调度问题；刘传领［9］提出一种改进蚁群优化算法，用于结合遗传算法，进而提出一种混合智能算法；陈亚云等［10］提出一种新的融合遗传算法和蚁群算法的启发式算法；蔡延光等［11］提出一种基于遗传算子的自适应蚁群算法；黄永青等［12］提出一种使用精英保留策略的交互式蚁群遗传算法；田增瑞等［13］提出一种基于遗传算法与蚁群算法相结合的混合算法，用于设计最佳旅游路线。很多专家和学者针对特定求解问题，还提出了许多基于遗传算法和蚁群算法的混合智能优化算法［14～18］。

这些遗传算法和蚁群算法的混合算法，较好地解决了某些特定问题，但还存在求解效率和精度较低。因此，本文在分析遗传算法和蚁群算法的动态特性、机理、寻优策略及收敛性基础上，引入多种群、遗传算法的选择、交叉、变异和蚁群算法的寻优多策略有机结合，实现参数的自适应调整，提出一种基于多种群多策略的混合遗传-蚁群（HPSGAO）算法，以充分体现HPSGAO的整体寻优能力，动态地平衡算法收敛速度和搜索范围之间的矛盾，克服遗传算法搜索到一定阶段效率低和蚁群算法初始信息素分布盲目等问题。

2 遗传算法和蚁群优化算法

2.1 遗传算法

遗传算法（Genetic algorithm，GA）是一种自适应随机迭代搜索方法，它通过个体的选择、交叉和变异等操作来产生新的个体，进而构成新的种群。该算法通过不断重复进化，使求解问题的解逐渐优化，获得最优解。遗传算法一般由编码机制、适应值函数、遗传算子、控制参数等组成，其计算流程如图1所示。

2.2 蚁群算法

蚁群算法（Ant colony optimization，ACO）是一种基于蚂蚁寻径行为的群智能优化算法算法［3］。它源于自然界中的真实蚂蚁在寻找食物时相互协作行为的启发，通过信息素的调整较好地控制了种群的多样性，具有较强的全局优化能力。蚁群算法求解TSP的流程图，如图2所示。

图1 遗传算法流程图

图2 蚁群算法求解TSP流程图

3 多种群与多策略

3.1 多种群

在HPSGAO算法中，充分利用了多个子种群的平行进化。在每个子种群的内部，除了GA的选择操作、交叉操作和变异操作外，还引入了一种替代操作。该操作是利用ACO算法搜索到的解去替代种群中的较差个体。而蚁群搜索是基于各子种群的最优个体，所以引入的替代操作能够共享优良个体、改善种群，并能有效加速算法的进化。

3.2 多策略

1）遗传策略

遗传策略是具有较强的全局快速收敛能力，它主要包括选择策略、交叉策略和变异策略。

（1）选择策略

针对引发超级个体和相似个体问题的盘赌方法，提出采用联赛选择方法来选择算法的个体，目的是为了避免算法的早熟现象，保证选出具有较高适应值的个体。

（2）交叉策略和变异策略

本文的交叉策略采用一种非常规码的常规交配法，实现个体之间的交叉。变异策略采用一种交换的变异算子，通过随机选择的两个变异点，实现两个基因的变异。

2）蚁群算法寻优策略

当蚁群算法被用于求解不同的组合优化问题时，蚁群算法的寻优策略具有不同的表达形式。本文主要分析蚂蚁的寻优策略。根据蚁群算法自适应伪随机比率选择规则，选择下一节点：

其中：λ(t)∈[2，N]表示算法在第 t次迭代时的ANB，N表示节点数，q(λ(t))∈[2/N，1]，q(t)为［0，1］区间上一致分布的随机数。S根据下列公式进行选择：

其中αc是α的初始值，βc是 β的初始值，rand()是随机函数。

3）参数自适应调整策略

（1）GA参数自适应调整策略

Srinivas提出了一种自适应遗传算法用于平衡GA的搜索范围与能力。该算法利用种群平均适应值与最优个体适应值的差来确定种群的多样性，但存在过早收敛现象。因此可以将适应度值大于fˉ(t)的个体适应值再做一次平均得到，定义表示种群的过早收敛程度，这样就能提高遗传算法参数的自适应性。

（2）ACO参数自适应调整策略

针对ACO算法信息素挥发系数ρ(t)过大带来了降低算法全局搜索能力和过小带了降低算法的收敛速度的问题，采用ACO算法信息素挥发系数自适应方法。该方法具体为初始值取ρ=0.999；在T次循环内最优值没有明显变化时，ρ值减为

其中rand()是随机函数，最小取值ρmin是防止过小的ρ而降低收敛性。该方法能有效保证搜索的有效性，提高全局搜索能力。

4 基于多种群多策略的混合遗传-蚁群算法

4.1 混合遗传-蚁群算法思想

GA具有快速和全局的搜索能力，但求解效率较低；ACO算法具有较强的鲁棒性和并行求解质量好，但存在收敛速度慢、易陷入局部最优等问题。为了充分利用GA和ACO算法各自的优点，克服它们的不足，形成优势互补，引入多种群和多策略思想，将GA和ACO算法相结合，提出一种时间效率高于ACO算法、求解效率高于GA的混合遗传-蚂蚁（HPSGAO）算法。HPSGAO算法的基本思想：在HPSGAO算法的每次循环中，GA和ACO算法基于更新全局最优解来相互指导，ACO算法获得的较优解作为精英个体，加入到GA中，以提高GA的求解问题的精度和效率；GA获得的较优解作为ACO算法当前的最优路径，用于更新ACO算法的信息素浓度，以提高ACO算法的全局择优性能。通过多次循环，HPSGAO算法从GA获得全局择优能力和ACO算法获得较快的收敛速度和较高的求解精度。因此，在理论上HPSGAO算法具有较好的时间效率和求解精度。

4.2 HPSGAO算法模型及步骤

基于多种群多策略的混合遗传-蚂蚁算法描述如下：

Step1：初始化遗传算法的参数

根据待求解优化问题，初始化算法种群个体、搜索点以及速率等约束，确定种群的规模，设定遗传算法相关参数：选择方式、交叉概率、变异概率、迭代次数等。

Step 2：计算适应度值

根据待求解优化问题，确定适应度函数，并计算所有个体的适应度值，并按序排列。

Step 3：选择、交叉和变异操作

采用联赛选择方法从4N个体种群中选择适应度值最优的2N个，组成算法子种群。再采用一种非常规码的常规交配法进行交叉操作。按照交叉概率（Pc）随机进行两两配对，实现个体之间的交叉。假设在2个个体xi和xi+1之间进行交叉，则交叉后产生的亲个体为

在式（6）和（7）中，pi为算术交叉系数，取值为均匀分布的［0，1］之间的随机数，xi表示第i个粒子的位置。

以变异概率（Pm）对个体进行变异操作，公式表述为

Step4：获得问题的优化解

比较HPSGAO算法得到的适应度值，获得全局最优值gBest。如果全局最优值满足精度，则执行Step5；否则循环Step2到Step4，直到获得最优解或达到最大迭代。

Step5：初始化ACO算法信息素

利用Step4获得最优解来初始化ACO算法的信息素。根据以下公式计算两个城市间路径的信息素浓度（T(i)）：

其中，k、α是常量，k＞0，0＜α＜1；Xi是第i只蚂蚁的位置，f(Xi)是目标函数值。

Step 6：计算转移概率

按照转移概率式（2），计算第i个子群中第k只蚂蚁的转移概率。

Step7：计算每只蚂蚁完成一次旅行所经过的路径长度。

Step 8：按照信息素更新式（10）更新第i个子群中第k只蚂蚁的信息素浓度。

Step9：输出最优值

比较获得的优化解，如果是最优解，则更新全局最优解；否则循环Step5～Step8，直到获得最优解或达到最大迭代。

5 混合遗传-蚁群算法求解TSP问题

为了测试混合遗传-蚁群算法的有效性，选择了GA、ACO和HPSGAO算法进行实验分析比较。10个来自于TSPLIB库的TSP标准实例被用于测试算法优化性能。为了获得这些算法合理的初始参数值，测试可供选择的参数取值，选定的参数值具有算法的最优解和最合理的运行时间。因此，为这3个算法选择的最合理参数取值，如表1所示。每个TSP实例连续运行10次，实验结果如表2所示。

表1 GA、ACO和HPSGAO算法的参数设置

表2 实验结果

从表2可以看出，对于 berlin52、pr76、rad100、eil101、lin105、ch130、kroA150、kroA200、lin318 和d1655共计10个TSP实例来说，提出的HPSGAO算法求解所获得最优解明显要优于GA和ACO算法，而且eil51实例求得了最优值426，eil101实例所求解得到的最优解643几乎接近于最优值629。HPSGAO算法在求解TSP时，如果城市规模较小时，该算法的优化效果较明显。当城市规模逐渐增加时，HPSGAO算法优化效果逐渐降低，较难获得最优解。因此，提出的HPSGAO算法表现出较强的全局优化能力。

HPSGAO算法求解eil51实例所获得的最优路径，如图3所示。

图3 eil51的最好值路径（426）

6 结语

本文充分利用了遗传算法的和蚁群算法各自的优点，基于多种群和多策略，提出一种带有参数自适应调整的混合遗传-蚁群算法。该算法利用遗传算法产生的较优解来初始化蚁群算法的信息素分布，进而有效融合了蚁群策略和遗传策略，动态平衡HPSGAO算法的收索范围与收敛速度间的矛盾，进而提高HPSGAO算法的全局择优能力。10个TSP实例被用来验证HPSGAO算法的优化性能。仿真实验结果表明，提出的HPSGAO算法能较好地求解到TSP问题，很多TSP实例能够获得近似的最优解，充分展现出HPSGAO算法较快的收敛速度和较高的求解精度，具有较强的全局优化能力。