模拟进化算法新发展

第六章模拟进化算法的新近发展模拟进化算法实际上是一种非常宏观意义下的仿生计算技术，它模拟的是一切生命与智能生成与进化过程。这种技术不仅仅包含到目前为止我们所讨论的遗传算法等。本章目的在于向大家简单介绍国内外新近发展起来，并正在受到广泛关注的几类新模拟进化算法。§1蚁群算法蚁群算法是由Colorni和Dorigo等人提出的一类模拟自然界蚁群行为的模拟进化算法。这类算法主要基于以下的观察：像蚂蚁这类群居昆虫，虽然没有视觉且单个行为极其简单，但由这些简单个体所组成的群体却常常表现出令人称奇的行为——能够在复杂的环境下最终找到从蚁穴到食物源的最短路径。蚂蚁在运动过程中能够在它所经过的路径上留下信息素，而且在运动过程中感知这种信息素的存在及其强度，并以此指导自己的运动方向。蚂蚁倾向于朝着信息素强度高的方向前进，因此，由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象：某一路径上走过的蚂蚁越多，则后者选择该路径的概率就越大。蚁群就是通过个体之间这种信息交换机制来彼此协作达到搜索食物的目的。蚁群彼此协作所表现出的“智能”行为还显现在它们对环境的自适应性上：当在运动过程中突遇障碍时，它们能够躲过障碍而很快找到满足约束条件的最优路径。蚁群通过信息交换与相互协作找到从蚁穴到食物源最短路径的机制，可以数学化来求解图上各种与最优路径相关的组合优化问题。我们可以将“跨越障碍”对应为所求问题的某种启发式信息（指明满足约束的可能选择），而将信息素对应为所选择路段对整体最优解的贡献程度。例：考虑n个城市的TSP问题（分别表示城市编号）。下面说明用蚁群行为来搜索通过这n个城市各一次且最后回到出发地的最短路径。假定：m是蚁群的数量，表示城市与间的距离（假定，考虑对称TSP问题），表示t时刻位于城市的蚂蚁数量。表示问题在t时刻所能提供的某种启发式信息，而表示t时刻蚁群在连线上所放置的信息素。初始时刻，蚁群中的蚂蚁可随机放置，此时设各路径上的信息素恒等（如为某一预设常数）。

蚂蚁在运动过程中将根据各条路径上的信息量（信息素含量）与启发式信息（即环境因素）来决定其转移概率。例如，设表示t时刻蚂蚁由位置移到位置的概率，则可令这里，为参数，表示蚂蚁下一步允许选择的城市，而是蚂蚁到目前为止已走过的城市（与实际不同，人工蚂蚁要求具有一定的记忆功能）。每一只蚂蚁都按照上式的概率来决定它的位置转移。当蚂蚁完成一次循环（即完成一个闭合路径，或产生一个完整可能路径），各路径上的信息量将依据一定的规则调整，以体现整个蚁群在该路径上所留下的信息素。如以表示其消失程度，则整个蚁群完成一次循环后，各路径上的信息量可依下式调整：其中表示第只蚂蚁在本次循环中留在路径上的信息量。如可取其中表示第只蚂蚁所走路径长度。启发式信息常在这种应用情形反映人们对从城市转移到城市的期望程度，可根据某种启发式算法具体确定。为理论上的方便我们可取

在对各参数合适选择之后，上述模拟蚁群寻食过程便自然形成一个求解TSP问题的仿生算法。求解一般图上组合优化问题的蚁群算法可描述如下：

蚁群算法步骤1

（初始化）指定蚁群规模，父代种群规模；输入初始信息素及启发式信息；随机生成初始蚁群

其中；置。

步骤2（模拟演化）执行以下操作：

（1）选择从中依其目标函数值选择出n只蚂蚁（例如可择优选择）组成第代父代蚁群。（2）重组

1）设信息量，其中这里是反映作为问题解质量的评价，如，是蚂蚁所产生解的路径长度。

2）令

3）以适当方式获得启发式信息。

4）独立、重复地以概率随机产生蚂蚁，由此组成第代蚁群步骤3（终止检验）如解已达到精度要求，或已达到预设进化时限，则停机，输出中最好的个体为问题近似解；否则，对于转步骤2。

近年来，蚁群算法无论是理论分析还是算法推广及应用研究等方面都受到了国内外广泛关注。§2粒子群优化粒子群优化（particleswarmoptimization,简称PSO）是由Kennedy和Eberhart(1995)等人提出的一类模拟群体智能行为的优化算法。

算法的仿生基点是：群集动物（如蚂蚁、鸟、鱼等）通过群聚而有效的觅食和逃避追捕。在这类群集动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或者化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间的推移，这些初始处于随机状态的鸟通过相互学习（相互跟踪）自组织地聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集到同一位置——食源。这些群集动物所表现出的智能常称为“群集智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯（通过改变局部环境）的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作能表现出智能的行为特征。

PSO以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景。在PSO中，每只鸟被称之为一个粒子（particle），每个粒子以其几何位置与速度向量表示。在求解中，每个粒子参考自己的既定方向、所经历的最优方向和整个鸟群所公认的最优方向来决定自己的飞行。

每个粒子X可标识为

PSO以下述形式来求解问题。

PSO算法步骤1（初始步）随机产生N个粒子构成初始粒子群

置。步骤2（种群演化）

（1）选择

1）假定以概率1选择中的每一个体；

2）求出每个粒子到目前为止所找到的最优（如记为）；

3）求出当前种群到目前为止所找到的最优（如记为）。

（2）繁殖对每个粒子，令由此形成第代粒子群

步骤3（终止检验）如已产生满足精度的近似解，或已达到进化时限的要求，则停机并输出的最佳个体为近似解；否则对于转步骤2。

在上述的PSO算法中，常称为步长因子，可参考无条件约束优化方法中的搜索步长选取方式选取；表示中的随机数；分别是惯性系数、社会学习系数和认知系数，它们分别表示相信自己的程度，相信经验的程度和相信周围个体的程度。

PSO算法的突出特点是：简单、有效，但仍缺乏严格的收敛性理论分析。虽然PSO最早是对连续优化问题所提出，但目前已被推广到各种离散优化问题。§3人口迁移算法人口迁移算法（populationmigrational-ogrithm，简称PMA）是我国学者周允华、毛宗源等人近期所提出的一类模拟人口迁移机理的全局优化算法。算法的模拟基点在于：对人口移动规律的整体认识。人口作为有生命的群体，为了生存和发展，它必然会产生不断地移动。人口移动通常泛指人口在空间或地域上的一切移动，包括人口流