摘 要：为了提高全局和局部搜索的质量，提出了一种基于邻域智能的交叉变异算法。受中国成功学习典故“孟母三迁”的启发，根据对粒子群内各个邻域性能的评价来动态调整算法参数，使得迭代初期粒子群保持较好的局部搜索能力，在后期提高全局搜索能力，避免陷入局部最优，提高了共享信息的可信度。同时，算法引入交叉变异因子，通过收集粒子周边邻域反馈，自适应动态调整周边邻域。�
关键词：受信任邻域；粒子群算法；交叉变异�
中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2012）003-0059-03��
�
作者简介：董文娟（1987-），女，宁夏银川人，四川大学硕士研究生，研究方向为计算机技术。
0 引言 �
粒子群优化(PSO)算法是Eberhart和Kennidy于1995年提出的，它源于对鸟群捕食行为的简化社会模型的研究，通过对鸟群觅食过程中迁徙和群体行为的模拟，实现了个体的协同优化。该算法很好地利用了信息共享机制 ，使粒子之间相互学习竞争，促进整个群体的发展，具有典型的群体智能特性。该算法简洁，易于实现，收敛速度快。目前PSO算法的研究已在参数设置调整、与Ant等算法的融合改进以及工程应用中得到了广泛的应用。但基本粒子群已陷入局部最优，并且具有后期收敛速度慢等缺点，本文改进的算法，通过将基本粒子群算法粒子行为基于个体极值点转化为个体自身极值与其邻居的极值的加权平均值，从而让个体很好地受到邻居的熏陶，而全局极值点转化为群体中优秀个体极值的加权平均值，使粒子能够获得更多的信息来调整自身的状态 。�
1 标准粒子群算法PSO�
粒子群优化算法将个体看�作是D维搜索空间中的一个粒子，根据对环境的适应度将群体中的粒子移动到好的区域 。该算法对标准粒子群优化算法中”社会”部分对粒子运动的影响方式进行了改进，增加了粒子视野范围内个邻居中具有最优适应度值的粒子作为参考，以克服原算法采用全体粒子中最优个体作为全局极值而产生的易陷入局部最优的缺点，从而更真实地模拟群体行为。�
假设包含m个粒子的粒子群在D维�空间（即搜索空的终止条件为搜索到满足误差条件的解，或者达�到预设的最大迭代次数。
2 改进的经典PSO算法�
基本PSO算法存在诸多问题，主要表现在收敛速度慢和过早收敛：随着迭代数的增加，粒子间相似度增大，基本PSO算法不能对解进行持续优化，而是在局部最优解附近徘徊。粒子群算法的本质是利用个体极值与全局最优值对基本PSO算法改进，方法主要有两种：一种是对权重的变化进行改进，权重变化对算法的全局探索和局部探测有很大影响，为此把权重线性变化变成非线性变化或模糊化 ；另一种是通过控制种群的多样性来提高算法性能，通过解决微粒间冲突 ，引人速度变异和位置变异，小概率重新初始化等方法，增加粒子的多样性，提高全局搜索能力，避免陷人局部最优。�
3 改进的粒子群优化算法�
标准PSO算法在进化过程中除跟踪自身最优外，只与种群最优粒子发生信息交流，在进化过程中种群最优对其影响很大，一旦粒子赶上种群最优，粒子会聚集到相同位置并停止，从而导致算法过早收敛而出现早熟。而收敛现象过早发生时，往往是适应度暂时最优的那些个体相互趋同，其余适应度较小的个体在种群空间中依然是离散分布。为了降低种群最优粒子的影响，本文在粒子位置更新时除考虑自身最优和种群最优外，还与粒子邻域内粒子最优发生信息交流。�
在粒子群算法中，每个粒子周围都存在一定数量的邻居，它们之间相互共享信息。这就恰恰和人类社会相同。他人和群体制约的个体的行为、判断和思想，如人际知觉、人际吸引、社会促进和社会抑制、顺从等。同时群体本身特有的心理特征，如群体凝聚力、社会心理气氛、群体决策等等也会受到个体的影响。�
文献\[1\]中提出了带邻近粒子信息的模型，因此将上式改为
表示第i个粒子其各邻居在D维空间中的历史最优位置。第一部分为粒子先前的速度；第二部分为“认知部分”，是粒子对自身的思考；第三部分为“社会部分”，表示粒子与邻居间的信息共享和相互合作。从式(3)中可以看出，该算法充分利用了社会部分包括了与种群最优粒子和目前位置最近粒子最优之间的信息交流。较基�本PSO更好地在初期应保持较高的多样性，应减小种群最优的影响，而增加最近粒子的影响，防止粒子向种群最优位置聚集。这样使得算法在粒子位置更新时除考虑自身最优和种群最优外，还与粒子目前位置最近粒子最优发生信息交流。�
实验表明这种改进通过自适应调整惯性因子，能兼顾搜索效率和搜索精度，优化性能有所改善。但是未考虑算法随迭代次数增多之后邻域内的粒子性能下降，所以本文在此基础上自适应的调整邻域受“孟母三迁”的启发，个体具有强烈的易驱性，会随迭代的增加而进入局部最优当发现粒子小于阀值时，根据算法为其更换邻居，防止其陷入局部最优交叉邻域。本文考虑了两种情况为粒子搬家，第一种情况：当个体周围的邻居其信誉低于某个值时，为其更换邻居；第二种情况：当个体陷入局部优化时，个体在某一个极值点附近振动，为其更换邻居。
�
3.2 基于自适应的交叉变异�
自适应有个阈值。�
邻域交换策略。�
3.3 算法流程�
①初始化粒子群，设定最大迭代次数T一，当前值置1，设定学习因子C。、C 。在空间Ro中产生m个粒子，随机初始化粒子位置和初始速度；②计算每个粒子的适应值；③比较粒子当前适应值F(x。)和自身历史最优值P ，若F(X。)比P 更优，则置P 为F(X )，P。为当前X；④比较粒子当前适应值F(x )和群体最优值g ，若F(x。)比 更优，则置g 为v(X。)，P 为当前x；⑤粒子飞翔，进行迭代，按式(7)、(8)、(9)更新粒子速度，粒子群更新为x；⑥查看局部优化标志位。若达到其临界值，粒子陷入局部优化，重新初始化该粒子；⑦检查结束条件，如果满足，则算法结束。如果不满足，转②。结束条件为寻找到满足精度的解或者算法达到最大迭代次数。 �
4 新算法的仿真测试�
为了证明算法改进的有效性，选择�Sphere、Rosenbrock、Rastrigrin、Griewank这4个无约束优化基准测试函数对改进算法进行测试。通过与标准PSO 算法比较收敛精度和收敛速度，检验FPSO�的性能。4个函数分别如下所示：�
4．1 测试收敛精度�
在收敛精度测试中，取最大迭代次数为1 000，两种算法重复运行30次，比较两种算法的平均适应值和最优值。解空间维数分别取20、30。测试结果如表1所示。�
4．2 测试收敛速度�
在收敛速度测试中，取最大迭代次数为2 000，解空间维度为10，并为每个函数设置精度较高的算法结束条件，每个算法测试结果：
运行30次，统计算法寻优成功率和寻优成功情况下的平均迭代次数，测试结果如表2所示。
5 结束语�
针对经典的PSO算法容易陷入局部最小值，提出了一种新的带变异自适应参数调整PSO算法。通过引入粒子群评价，根据粒子群的整体性能评价对PSO算法的所有参数进行动态调整，同时对粒子本身找到的最优解以动态调整概率进行变异。这样可以帮助算法摆脱后期已陷入局部最优点的束缚，同时能够保持前期搜索的快速性。对4个经典的测试函数进行了对比实验，结果表明，本文提出的算法性能优于经典PSO等算法。在前100次迭代中要优于基本粒子群和动态邻域算法，但是新算法也存在着迭代稳定性的问题，如将每个粒子视为一个进程，其邻域即空间中的可用资源，在迭代中会出现进程间抢占资源问题，这是今后研究中要解决的问题
参考文献：�
\[1\] KENNEDY J，EBELHART R．Particle swarm optimization\[C\].IEEE Int Cod Neural Networks，1995．�
\[2\] SHI Y，EBERHART R．A modified particle 8mtarnl optimizer\[C\].IEEE World Congress on Computational Intelligence，1998．�
\[3\] SHI Y，EBERHART R C．Fuzzy adaptive particle swarm optimization\[C\].Proceedings of the IEEE Conference on Evolutionary Computation Piscataway，NJ：IEEE Press，2001．�
\[4\] SRINIVAS M.adaptive probability of crossover and mutation in genetic algorithms\[J\].IEEE,2010(11).�
（责任编辑：杜能钢）
Particle Swarm Algorithm Based on Crossover and �Mutation Evaluation of Trusted Neighborhood
��
Abstract:In order to improve the quality of global and local search, a neighborhood-based crossover and mutation intelligence algorithm （NPSO) was proposed .Inspired by the Chinese success story: "Mother Meng moved house third for her child " ,we dynamically adjust the algorithm parameters according to the performance of particle swarm in the evaluation of each neighbourhood .The improvement makes the initial iteration particle swarm maintain a strong ability of local search .The new algorithm can improve global search ability to avoid local optimum trap and enhance the credibility of sharing information between particle at the later stage.Meanwhile, the algorithm introduces the crossover and mutation factor, collect feedback of particles in the surrounding neighborhood , adaptively adjust the neighbourhood. Under all test cases, simulation shows that the NPSO always finds better solutions than PSO.
�
Key Words: Trusted Neighborhood; Particle Swarm Optimization; Optimization Algorithm