遗传算法（Genetic Algorithms，GAs）是一种基于生物进化理论的优胜劣汰规则与染色体信息交换机制的全局搜索算法，具有使用简单、通用性和鲁棒性强、对问题模型依赖性小等特性，对解决处理传统搜索方法难以解决的大规模、非线性、多变量、全局优化等复杂问题具有独特优势。但是，在实际应用中，过早的收敛到局部最优和在进化后期搜索效率较低是基本遗传算法的两个主要缺点。针对基本遗传算法的不足，结合产品服务设施动态选址的具体问题，本书对采用了基于多种群协同进化的自适应多目标遗传算法（Co-evolution based Adaptive Multi-objective Genetic Algorithms，CA-MOGA）采取了如下改进措施：

（1）针对拟解决的问题，采用多层染色体编码设计，并设计了基于约束检查的交叉和变异算子。

（2）针对实际问题的约束条件，引入了自适应罚函数。

（3）针对多个目标的可比较性差的问题，采用了基于目标排序的动态适应度函数。

（4）为了防止早熟和提高后期搜索效率，采用了自适应交叉和变异概率。

（5）通过基于缓冲池的跨世代精英迁移策略实现多种群协同进化过程中的个体迁移，保证种群的多样性。

具体算法流程如图3-5所示。

图3-5 基于多种群协同进化的自适应多目标遗传算法流程

步骤1 初始化参数。随机生成π个子种群，每个子种群大小为n，最大进化代数为G，各子种群的交叉概率为P_c，变异概率为Pm。

步骤2 随机产生满足约束的n个初始个体，设定初始进化参数g=0。

步骤3 定义适应度函数F（X），计算子种群中每个个体的适应函数值F（Xj），并对个体进行排序。

步骤4 根据适应度值排序，从当前各个子群中选择一定（相等的）数量的优秀个体，组成第n+1个种群，形成精英种群。(www.daowen.com)

步骤5 把第n+1个种群（精英种群）中的个体复制到精英种群缓冲池。

步骤6 令g=1，对每一个子种群实施如下操作，并产生新的种群：

（1）计算子种群中每个个体的适应函数值F（X_j）。

（2）采用锦标赛选择法进行选择操作。

（3）交叉变异操作。从各个子种群中选取个体按交叉概率P_c进行交叉操作，并对个体按变异概率Pm进行变异操作。

步骤7 执行步骤4，更新精英种群（也就是第n+1个种群）。

步骤8 若g=G或者第n+1个种群（即精英缓冲池）中的最优个体满足终止条件，运行结束，得到全局最优解。若g≤G或者第n+1个种群中的最优个体未满足收敛条件：

●如果g≠k×w，k是正整数，w是种群迁移代数间隔，g→g+1，各个子种群再次执行步骤6的操作。

●如果g=k×w，即各种群独立进化w次以后，把精英种群缓冲池中的个体分别与各个子种群中的个体混合，并按照新的适应度值排序，剔除劣解，从中选择与原种群规模相当的适应度较好的个体组成新的种群，从而实现基于精英种群的跨世代迁移操作。

步骤9 执行步骤5，更新精英种群缓冲池。

步骤10g→g+1，对n个子种群再次执行步骤6的操作。