基于粒子群信息传递模式的混合算法
摘 要:
粒子群优化算法(Particle Swarm Optimization，简称PSO)是一种基于群智能(Swarm Intelligence)的随机优化计算技术. 两种算法相比较，PSO收敛快速准确，但编码形式单一，局限于解决实优化问题，而遗传算法(Genetic Algorithm，简记GA)编码形式灵活，解决问题广泛，但在执行效率低于PSO[4]. 本文将粒子群算法的信息传递模式与GA的编码和遗传操作相结合，提出一种混合算法。通过组合优化和函数优化的基准测试集对算法进行了测试，试验结果表明，该算法的在收敛精度和速度较传统GA相比，该算法收敛效果明显优于标准GA. 同时，也观察到该算法通过引入PSO的信息传递模式取得了与粒子群算法一致的收敛现象，也一定程度解释PSO获得快速收敛的原理.
关键词: 粒子群算法；遗传算法；演化计算；最小生成树
中图法分类号: TP392 文献标识码: A
1. 引言
粒子群优化算法[2]是由Kennedy和Eberhart在1995年提出的一种基于群智能的演化计算技术[3]，是在鸟群、鱼群和人类社会的行为规律启发下提出的. 粒子群算法已被证明在函数优化问题中收敛速度和结果优于传统的遗传算法[4,6]. 粒子群算法善于解决浮点编码的函数优化问题，但当对于离散编码的优化问题，粒子群算法未能有如同GA和蚁群算法的优势.
遗传算法是在生物界自然选择和进化机制启发下提出的高度并行、随机、自适应搜索算法 [1] ，是当前在智能优化领域中应用最广泛、技术最成熟的一种优化技术. 遗传算法通过对个体染色体进行编码，使其代表问题的可行解，然后，对个体组成的种群施加选择、交叉和变异等一系列遗传操作，从而产生新一代种群，并逐步使种群进化到包含近似最优解的状态. 遗传算法通过对各种问题进行灵活多样的编码，使其应用范围得到了不断的扩展.
通过分析粒子群算法的主要思想可知，个体充分利用自身经验和群体经验调整自身的状态是粒子群算法具有优异特性的关键. 基于这一想法，本文将PSO中的粒子间信息传递模式融合遗传算法编码方式和遗传操作，提出了一种混合算法（Hybrid PSO-based Algorithm, 简称HPSO）. 混合算法中每一个体通过保留自身经验增加进化过程中个体间的交互信息量，来提高算法的搜索效率. 为此，本文为混合算法设计了一种新的交叉算子，以便将这一信息引入进化过程. 新算法同时继承了遗传算法对问题编码灵活和粒子群算法收敛快速准确的特性. 测试结果表明，本算法不仅可以解决各种类型的优化问题，而且在收敛速度和精度优于标准遗传算法，并且继承了粒子群算法的收敛特点，即算法能够在较少的迭代次数内收敛到较优的结果.
2. 基于 PSO 混合算法
基本粒子群算法（Particle Swarm Optimization）在D维目标搜索空间中，n个粒子组成一个群落，每个粒子i包含一个D维的位置向量xi=(xi1, xi2,…, xiD,)和速度向量vi=(vi1, vi2,…, viD,). 粒子i在搜索解空间时，记住其搜索到的最优位置pi，在每次迭代中，粒子i根据自身惯性、自身经验pi=(pi1, pi2,…, piD,)和群体最优经验pg=(pg1, pg2,…, pgD,)调整自己的速度向量，进而调整自身位置.
Kennedy 和 Eberhart 最早提出的PSO算法采用如下公式更新粒子状态[8]：
其中，学习因子c1和c2是非负常数；r1和r2是取值介于(0,1)之间的随机数. vid∈[-vmax, vmax]; vmax是常数，根据问题而设定. 迭代终止条件根据具体问题一般选为最大迭代次数或(和)粒子群迄今为止搜索到的最优位置满足预定最小适应阈值.
粒子群算法思想及优缺点
粒子群算法是一种群搜索算法，它之所以有高效的搜索性能，是由于群体的合作. 正如文献[12]所说：“社会行为有两个主要的目的：一是每个个体能够在搜索食物的过程中协助其它群内的成员，二是群体合作能够提高搜索效率. ”换而言之，每个粒子能够向群体提供信息，并且每个粒子又能够协助其它粒子进行搜索.文献[13]中阐述了粒子群算法的基本思想：
粒子利用个体经验信息和种群经验信息来调整自身状态.
从演化计算角度讲，PSO 算法属于演化计算技术的一种. 因为粒子状态更新公式(1)、(2)相当于GA 中个体之间的交叉操作；但PSO 没有类似于遗传算法的变异算子，但文献[7]经过研究发现，将变异算子引入粒子群算法中可以增强避免陷入局部最优的能力. 所以，粒子群算法也可以理解为利用自身经验进行交叉的演化计算技术.
PSO 算法的优势在于求解一些连续函数的优化问题，文献[4]研究表明粒子群算法在函数优化中的收敛速度和精度要优于传统的遗传算法. 但实际中许多问题是组合优化向题，因此，文献[5][6]提出二进制离散粒子群（Discrete PSO，DPSO）算法来解决这一类问题. 但实验结果表明目前DPSO 在组合优化这类问题上未能有如同GA 和蚁群算法那样有优势.
文献[13]认为粒子群算法快速准确收敛的关键在于粒子对各种信息的利用. 在传统的遗传算法中，个体不保留自身经验，群体只保留群体最优经验，所以遗传算法利用的信息量少于粒子群算法所利用的信息量. 本文基于这种想法，提出在GA 中个体保留自身经验增加进化过程中的信息，并设计一种模仿粒子群信息交互模式的交叉算子来利用个体经验信息，进而达到提高算法的搜索效率的目的.
混合算法的个体数据结构
混合算法的个体信息结构与PSO相同，其包括两部分：一是个体当前世代的编码，二是个体自身所搜索到的适应值最高的编码. 定义个体i，设其当前的编码为Xi，其祖先经验编码为Pi，如图1 所示，一个5 个城市的TSP问题中的不同算法个体对比，这是本算法与标准GA主要区别之一.
算法中编码形式是任意的，染色体编码根据问题的不同可采用不同形式的编码；个体经验也在迭代过程中进行更新（当前编码适应度优于经验编码适应度时，则更新经验）. 当然，个体保留经验不是目的，而是要提高算法的搜索效率和精度. 所以，本文设计了如下交叉算子，使得个体能够在交叉过程中利用自身经验信息.
混合算法的交叉算子
由PSO中粒子状态更新公式（1）和（2）可知，粒子在状态更新操作中利用了三个方面的信息：粒子当前位置，经验位置和邻居经验位置信息，然后，粒子利用这些信息调整自身位置和速度. 本文提出的交叉操作其思想也继承了粒子群算法的这种信息交互模式. 假设个体i与j需进行交叉操作，定义λ1和λ2为随机交叉系数，定义1λ?为（在编码形式为二进制编码和序列编码中，则λ1和λ2代表随机交叉位置，介于1到编码长度之间的随机自然数；如为浮点编码，则为(0，1)之间的随机浮点数.），本文定义交叉过程如(3)(4)所示.
其中，Xi’和Xj’分别为交叉操作后个体i和个体j的后代的遗传编码. 当群体完成交叉操作后，以Xi’和Xj’分别替代Xi和Xj，并计算每个个体的适应度，如果个体i当前适应度优于各自的经验编码的适应度，则更新经验编码Pi.
在公式(3)和(4)中，若要生成i的后代Xi， Xj首先与个体i的经验编码Pi在系数λ2进行交叉操作生成两个个体. 然后，随机选取其一与Xi在系数λ1下进行交叉生成两个子代，再随机选取其一作为Xi’. 这种交叉模式，保证种群中的个体能够利用3种信息修改自身的染色体编码.
本文认为这种模式是粒子群算法一种个广义的描述. 因为可以由这种模式推导出实数优化的粒子群算法的状态更新方程. 首先定义交叉模式为如公式(5)所示的基于方向的算术交叉[11].
可以发现公式(8)与粒子速度更新公式(1)除无速度vid基本相同.
混合算法流程
基于PSO的混合算法的流程融合了粒子群算法和遗传算法的流程，具体过程如下：
Step1：随机初始化种群，设种群大小为n，最大迭代次数max；个体编号i=0;Step2：每个个体计算适应度，并将目前的编码作为经验位置保存；Step3：根据每个个体的适应度，计算选择概率；Step4：确定个体i=i+1为待交叉个体，通过轮转法选择出待另一个待交叉个体j，j≠i；Step5：根据交叉率，确定个体i和个体j是否交叉交叉，如满足条件，个体i和个体j进行2.4节所述的单点交叉操作，即根据自身经验和对方经验修改当前的编码信息，交叉后的位置分别替代各自父代当前位置；未交叉的个体保存并进入下一代；Step6：如果i≤n，则转Step4，否则转Step7；Step7：根据变异率，对种群进行相应得的变异操作；Step8：计算每个个体的当前的适应度，如果优于自身经验适应度，则将当前编码替换自身的经验编码；并计算出本代最优个体，如果其适应度优于全局最优适应度，则更新全局最优信息；Step9：如果max>0,则max=max-1，转Step3；否则，输出全局最优个体的编码和适应度。
算法中针对每个个体i，并未选取种群最优编码与其完成交叉操作，通过试验发现，由于混合算法没有“速度”变量控制交叉速度，如果选取全局最优作为i的交叉对象，算法会过早的陷入举步最优，所以采用轮转选择的方式防止过快收敛.
3. 实验设定及结果分析
3.1 实验参数设置
本文分别采用组合优化和函数优化问题对算法进行测试. 组合优化问题采用最小生成树(Minimum Spanning Tree，MST)[9]问题作为测试用例. 本文中的最小生成树采用的是Kruskal算例[11]，节点的限定度为3，度分布如表1所示.
函数优化问题中个体染色体编码采用二进制01串编码，变异方式采用翻转变异；最小生成树问题中编码采用Prüfer数离散编码[10]，变异方式采用插入变异；为公平起见，在两种算法中，种群大小都为50，交叉率0.25，变异率0.02，交叉方式均采用单点.
3.2 实验结果
为保证数据准确，每个优化问题最大迭代次数均为1000次，每个测试重复100次，然后求得最小平均适应值及其标准差.对比情况如表3所示.
3.3 实验结果分析
由表3可知，基于PSO的混合算法在同样迭代次数内收敛精度和结果稳定性优于标准GA；由图3-8可知两种算法在处理不同优化问题时，HPSO在收敛速度优于标准GA，即在100到200次迭代内，HPSO就可以获得比较稳定的结果，这种特性与粒子群解决函数优化时的收敛现象一致. 这表明个体经验信息对收敛速度和精度存在一定程度的影响作用.
4. 结束语
本文通过分析研究粒子群算法的信息传递模式，并结合遗传算法对问题灵活编码的特点，提出一种混合算法. 该算法在处理组合优化与函数优化的实例中不仅可以获得较稳定和精确的收敛结果，而且保持较快的收敛速度. 实验结果表明，基于PSO的混合算法在收敛速度、稳定性和精度优于标准遗传算法. 同时也推导了由这种交叉模式和粒子群算法状态更新的关系，一定程度解释了粒子群算法快速收敛的机理.
