动态环境下一种改进的小生境粒子群算法

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用２００８，４４（９）５１

动态环境下一种改进的小生境粒子群算法

李孝源，李枚毅，宋凌

ＬＩＸｉａｏ－ｙｕａｎ，ＬＩＭｅｉ－ｙｉ，ＳＯＮＧＬｉｎｇ

湘潭大学信息工程学院，湖南湘潭４１１１０５ＩｎｓｔｉｔｕｔｅｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＸｉａｎｇｔａｎＵｎｉｖｅｒｓｉｔｙ，Ｘｉａｎｇｔａｎ４１１１０５，ＣｈｉｎａＥ－ｍａｉｌ：ｌｉｘｉａｏｙｕａｎ＿３０５＠１６３．ｃｏｍ

ＬＩＸｉａｏ－ｙｕａｎ，ＬＩＭｅｉ－ｙｉ，ＳＯＮＧＬｉｎｇ．ＩｍｐｒｏｖｅｄｎｉｃｈｅＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚｅｒｉｎｄｙｎａｍｉｃｅｎｖｉｒｏｎｍｅｎｔ．Ｃｏｍｐｕｔｅｒ

（９）：ＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００８，４４５１－５４．（ＰＳＯ）ａｌｇｏｒｉｔｈｍａｐｐｌｉｅｄｔｏｔｈｅｃｏｍ－Ａｂｓｔｒａｃｔ：ＴｈｅｐｕｒｐｏｓｅｏｆｔｈｉｓｐａｐｅｒｉｓｔｏｐｒｅｓｅｎｔａｍｏｄｉｆｉｅｄＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ

（ＩＮ－ＰＳＯ）ｐｌｅｘｄｙｎａｍｉｃｅｎｖｉｒｏｎｍｅｎｔ．ＴｈｅｍｅｔｈｏｄｐｒｅｓｅｎｔｅｄｉｓｄｅｆｉｎｅｄａｓＩｍｐｒｏｖｅＮｉｃｈｅＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚｅｒ．Ｉｔｃａｎｉｍｐｒｏｖｅｔｈｅｒｅｌｉａｂｉｌｉｔｙａｎｄａｃｃｕｒａｃｙｗｈｉｌｅｔｒａｃｋｉｎｇｄｙｎａｍｉｃｐｏｌｅｉｎｄｙｎａｍｉｃｅｎｖｉｒｏｎｍｅｎｔａｎｄａｖｏｉｄｃｏｎｖｅｒｇｅｔｏａｏｐｔｉｍａｌｉｔｙ．Ｔｈｅｅｎｖｉｒｏｎ－

（ＤＦ１）ｍｅｎｔｕｓｅｄｉｎｔｈｅｓｅｅｘｐｅｒｉｍｅｎｔｓｉｓｇｅｎｅｒａｔｅｄｂｙＤｙｎａｍｉｃＦｕｎｃｔｉｏｎ＃１．ＴｈｅｒｅｓｕｌｔｓｏｆｔｈｅｅｘｐｅｒｉｍｅｎｔｓｅｌｕｃｉｄａｔｅｔｈａｔＩＮ－

（ＡＰＳＯ）ＰＳＯｉｓｍｏｒｅａｄａｐｔｉｖｅｔｈａｎＡｄａｐｔｉｖｅＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚｅｒ．Ｋｅｙｗｏｒｄｓ：ｄｙｎａｍｉｃｅｎｖｉｒｏｎｍｅｎｔ；ｎｉｃｈｅ；ＰＳＯ；ＤＦ１摘

要：为了提高在动态环境下追踪变化的极点的可靠性和精确性的能力，避免算法收敛于一个最优解，提出了一种改进的小生

境微粒群算法。使用ＤＦ１（ＤｙｎａｍｉｃＦｕｎｃｔｉｏｎ１）生成的复杂动态环境对这种算法进行了验证，并与经典的ＡＰＳＯ（ＡｄａｐｔｉｖｅＰａｒｔｉｃｌｅ

算法进行了对比，实验结果表明了该算法的有效性。ＳｗａｒｍＯｐｔｉｍｉｚｅｒ）

关键词：动态环境；小生境；微粒群算法；ＤＦ１文章编号：（２００８）文献标识码：１００２－８３３１０９－００５１－０４Ａ中图分类号：ＴＰ１８

１引言

化的最优解。

在文中，提出了一种改进小生境粒子群算法（ＩＮ－ＰＳＯ）。利

用ＰＳＯ算法本身具有的记忆功能，采用聚类分析方法将基本粒子群分割为ｑ个小生境子群，提出一种局部极值排挤策略来保持算法的分布度，并利用分割后的小生境子群，采用分布式评价方式来保证算法对环境变化的感应能力。通过实验验证，并与经典的ＡＰＳＯ（ＡｄａｐｔｉｖｅＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚｅｒ）算法［２］进行了对比，实验结果表明了该算法在动态环境下追踪变化极点的有效性。

当前进化计算在解决静态问题时取得了巨大的成功，但是实际上许多问题都不是静态的，它们非常普遍地出现在工程优化，生产计划以及经济学上。动态优化问题在计算机科学和工程学很多方面是很常见的，如调度问题：在生活中，新的工作随时都有可能加进来，而原材料的质量和数量并不总是一成不变的。又如优化控制规则的确定，等等。所以，近年来将进化算法应用到动态系统中去追踪动态系统变化的极值成为一个新的研究领域。

求解静态问题使用进化计算要求种群收敛于最优解，而动态问题中收敛却是危险的，会导致算法中的个体收敛于解空间的一个最优解，当前最优解由于环境的变化而将成为一个局部最优解，从而使算法对变化了的最优解失去追踪能力。最近，国外提出了一些针对传统进化算法的改进，用来解决动态优化问题。传统的进化计算运行时，由于遗传操作等等一些原因存在，会逐渐失去分布度而导致算法运行时收敛，这是进化计算在解决动态优化问题与静态问题最大的不同。Ｊ．Ｂｒａｎｋｅ［１］据此将所有算法归为四类：（１）在环境变化之后加大分布度。（２）一直在算法运行中保持分布度。（３）使算法具有记忆功能。（４）多群体策略。显然，如果能够提供记忆方式让算法存储一些历史上好的解，并很好地保持算法的分布度，能保证算法有效地追踪到变

２小生境与微粒群算法

自从Ｋｅｎｎｅｄｙ和Ｅｂｅｒｈａｒｔ在１９９５年提出微粒群优化算法

［３］

（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ）以来，微粒群优化算法被许ＰＳＯ

多研究人员视为一种很有效的新的群体智能优化算法。

目前，国外有很多关于ＰＳＯ方法的研究，其中文献［４］提出了一种自由参数ＰＳＯ方法，以解决ＰＳＯ方法参数选择难的问题，文献［５］介绍了一种控制粒子距离的方法，通过控制粒子间距离来保证粒子的多样性。

粒子群中的个ＰＳＯ算法是基于群体与粒子适应度的算法。体随机初始化代表问题的一个可行解，每个粒子具有位置和速

度２个特征可以用一个三元组（ｘｉ，表示，其中，ｖｉ，ｐｉ）ｘｉ表示粒子

基金项目：湖南省自然科学基金（ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＨｕｎａｎＰｒｏｖｉｎｃｅｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．０６ＪＪ５１０６）。（男，收稿日期：２００７－０７－１１

修回日期：２００７－１０－０９

５２２００８，４４（９）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

者Ｐｂｅｓｔ粒子跳出现在的轨迹，恢复到上一次运行的状态。这

样使得整个群体保持了一定的距离，并使得群体在整个搜索空间分散开来，保证了个体的多样性，使得整个群体搜索范围不局限于最优解Ｇｂｅｓｔ粒子，当环境发生变化时，整个群体将进行重新评价，这时最优解Ｇｂｅｓｔ外围的粒子往往更加容易接近新的变化了的全局最优点而成为新的群体最优，这样整个群体的搜索趋势也随之改变，粒子群将追随新的群体最优在新的空间进行搜索，使群体避免在原业的搜索区域内停滞不前。

要将ＰＳＯ算法应用到动态环境中去，还需要使种群或微粒获得感知外部环境变化的能力，在这些方面研究者已经做了一些工作。窦全胜和周春光提出了群核进化粒子群优化方法

［６］

（ＳＣＥＰＳＯ），Ｈｕ和Ｅｂｅｒｈａｒｔ提出一种监测全局最优解Ｇｂｅｓｔ和次全局最优解的方法检测最优解的变化［７］，Ｃａｒｌｉｓｌｅ和Ｄｏｚｉｅｒ则提出了ＡＰＳＯ［２］。窦全胜的ＳＣＥＰＳＯ方法提出“群核”的定义，通过把整个群体分为３个互不交叉子群体，每个群体都采用不同的运行策略，去追踪全局最优点的动态改变。Ｅｂｅｒｈａｒｔ的方法通过对最优值停滞情况的观察来估计环境的变化，但这种方法在复杂环境下对环境变化不能总做出及时反应，而且此方法的集中式处理模式使得在环境没有变化时，也会定期对整个或部分种群进行初始化寻优操作。而Ｃａｒｌｉｓｌｅ则通过引入感应微粒的方式，通过随机选取一个或多个粒子作为感应粒子，但不足的是，在某一时刻，种群已经收敛到某一极值，而此极值所在区域是一个静止区域（可能是暂时的），而其它的区域不断变化。此时，由于所有的感应粒子收敛于极值点，失去了对其它区域变化的感应能力，不能追踪到最新的极值。针对以上的不足，本文提出了利用小生境最优粒子作为感应粒子的分布式感应方法。该方法的基本思想是：首先将种群按照适应值降序排序，然后应用聚类分析将种群分割为ｑ个小生境。如果一组个体之间的距离小于小生境半径，这些个体则属于同一小生境。其中，个体之间的距离公式既可用基因型之间的Ｈａｍｉｎｇ距离测度，也可用表现型之间的欧几里德距离测度。然后在每一个小生境内部，找出最好的粒子作为感应粒子。

采用小生境的方法形成和维持了稳定的多样化子种群，可在搜索空间的不同区域中并行地进化搜索。避免了ＡＰＳＯ算法感应粒子陷入一个区域的不足。同时由于利用多个小生境子群中最优粒子作为感应粒子，可以解决Ｅｂｅｒｈａｒｔ的方法对环境变化反应不及时的问题。而且子群之间采用分布式处理模式使得某一子群中的感应粒子检测到环境变化时，感应粒子所在的子群被重新初始化机而不对群体中其它微粒发出信号，从而减少了集中控制因素，避免了采用集中式处理模式时对无关微粒的初始化操作。

根据上面的设计分析思想，提出了ＩＮ－ＰＳＯ算法主要框架如下：

（１）初始化种群，种群Ｐｏｐ大小为Ｎ：Ｆｏｒｉ＝１ＴｏＮ（１ａ）ｐｏｐ［ｉ］的初始位置随机产生；（１ｂ）计算粒子ｉ的目标函数值；（１ｃ）（Ｖｅｌ［ｉ］是粒子ｉ的速度）；Ｖｅｌ［ｉ］（１ｄ）（Ｐｂｅｓｔ［ｉ］保存了粒子ｉ的Ｐｂｅｓｔ［ｉ］初始化为粒子ｉ本身个体极值）；

（２）将整个微粒群进行小生境划分：（２ａ）（２ｂ）应用聚类方法，以整个微粒群适应值大的微粒为中

的当前位置；ｖｉ表示粒子的当前速度；ｐｉ表示粒子本身搜索过

的最好的位置（个体经验）。目标函数可作为粒子的适应度，算法通过适应度来衡量粒子的优劣，算法首先初始化一群随机产生的粒子，然后通过迭代找到最优解。在每一次迭代中（假设为第ｔ代），每个粒子通过跟踪２个“极值”来更新自己，一个是粒子本身所找到的最优解Ｐｉｄ，另一个是整个群体目前找到的最（ｔ）优解，称为全局极值Ｐｇｄ。粒子找到这两个极值后，根据下面两（ｔ）个公式来调整自己的飞行，搜索问题的最优解。

（ｐｉｄ－ｘｉｄ）（ｐｇｄ－ｘｉｄ）（１）ｖｉｄ＝! ＊ｖｉｄ＋ｃ１＊ｒａｎｄ（＊＋ｃ２＊ｒａｎｄ（＊１）２）

（２）ｘｉｄ＝ｘｉｄ＋ｖｉｄ

（ｉｎｅｒｔｉａｗｅｉｇｈｔ）。，其中：Ｃ１和Ｃ２为加速因子，ｒａｎｄ（! 为惯性权重１）

为两个在［０，ｒａｎｄ（１］范围内的随机函数。２）

构造出一种小生Ｂｒｉｔｓ．Ｒ等将小生境技术引入微粒群算法，

境微粒群算法（ＮｉｎｃｈｉｎｇＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＮｉｃｈｅＰ－，算法的基本思想是将生物学中处于分散状态的孤立地理ＳＯ）

小生境中不同物种之间不进行竞争或交配等信息交流而独立进化这一概念移植到微粒群算法当中，以便在迭代过程中保持微粒群的多样性，并使得各个个体保持一定的距离。

（ＩｍｐｒｏｖｅＮｉｃｈｅＰＳＯ，３改进的小生境粒子群算法ＩＮ－ＰＳＯ）

ＰＳＯ算法着眼于如何更有效地用一个粒子群在解空间中搜索最优解。但是分析（１）和（２）式不难发现，粒子们在搜索时，总是追逐当前全局最优点，和自己迄今搜索到的最优点，因此粒子们向全局最优点飞行时，越接近全局最优点，速度越小，粒子们的速度很快降到接近于０，并快速收敛于全局最优点。当环境发生变化时，粒子在原来的搜索区域内停滞不前，容易陷入局部最优解。因此，需要控制好群体粒子间的飞行距离，使其能以较大的分布度在整个解空间中进行快速搜索。为了避免群体收敛于全局最优点，本文提出一种保持分布度的局部极值排挤策略思想：

为了方便对粒子群进行分析，根据ＰＳＯ算法的中粒子的更新公式和性质，将粒子分为三类：（１）指那些既是群体最优，又是个体最优的粒子。Ｇｂｅｓｔ粒子：

（２）指那些不是群体最优，但是为个体最优的Ｐｂｅｓｔ粒子：粒子。

（３）所有既不是群体最优，又不是个体最优Ｃｏｍｍｏｎ粒子：的粒子。

在粒子群在解空间搜索时，本文对Ｇｂｅｓｔ粒子和Ｐｂｅｓｔ粒子间的距离进行比较，若粒子距离过小，说明粒子集中，这时，保留其中一部分Ｐｂｅｓｔ粒子，其余Ｐｂｅｓｔ粒子则发生速度停滞，跳出原来的最优“轨迹”，不再向全局最优点靠拢，或者将已经进入Ｇｂｅｓｔ粒子过小范围的Ｐｂｅｓｔ粒子排挤出来。这样，通过保留的粒子“记忆”已得到的优化结果，同时，通过速度停滞的或排挤出来的Ｐｂｅｓｔ粒子来保持搜索领域，保证了粒子在整个解空间上较大的分布度。定义公式如下：

ｉｊｉｊ（３）" ｉ，ｊ＝! 上式中，" ｉ，ｊ是算法实现时由人工设置的一个表示粒子ｉ和ｊ的距离阈值，ｖｉ和ｖｊ是粒子ｉ和ｊ的当前速度，ｘｉ和ｘｊ是粒子ｉ和ｊ的当前位置，%、&是权系数。

当粒子的速度与位置不再发生变化，不再向Ｇｂｅｓｔ粒子靠拢，或

李孝源，李枚毅，宋凌：动态环境下一种改进的小生境粒子群算法２００８，４４（９）

５３

心，根据欧几里德距离测度计算它与最近粒之间的距离为半径，形成一个圆形的小生境，进入小生境的微粒群的微粒被吸

收。然后，如此类推，以剩余微粒中的适应值最大的微粒为中心，生成新的小生境。

（３）在每个小生境中找出最好的全局引导作为感应粒子，采用分布式评价策略对环境进行响应。（４）判断环境是否发生变化，如果发生变化，重新初始化感应粒子所在的子群，转到（３）。

（５）每个微粒执行飞行操作，到达新的位置，并计算新的适应度：

对粒子群中每个粒子更新其速度；（５ａ）（５ｂ）根据上一步求得的每个粒子的更新速度，重新计算其新的位置变量值：

ｐｏｐ［ｉ］＝ｐｏｐ［ｉ］＋Ｖｅｌ［ｉ］（５ｃ）按照公式（３）对Ｐｂｅｓｔ粒子执行局部极值排挤操作，调整分布度；（５ｄ）计算每个粒子的目标函数值，更新个体极值。（６）判断是否到达最大进化代数，若满足则结束，否则转（３）。

的中期，Ｂ的高度在一段时间内要高于Ａ的高度，此时全局极

点就是Ｂ的顶点，在实验后期，使它的高Ｂ的高度又逐步变低，度又低于Ａ，Ａ的顶点又重新成为全局极点。锥体高度变化如图２所示。

１６１５１４１３１２１１１０９８７０

ＣｏｎｅＡＣｏｎｅＢ

Ｈｅｉｇｈｔ

１００

５００ｌｔｅｒａｔｉｏｎ

１０００

图２锥体高度变化

锥体Ｂ的初始高度实验过程中，锥体Ａ的高度被设为１３，

设为８，锥体Ｂ的高度变化范围为［８，斜度参数随机生１８］之间，

成并保持不变。为了进一步验证ＩＮ－ＰＳＯ算法的有效性，本文还进行了其它几个实验，实验的参数设置如表１所示。

表１实验参数的设置

名称

初始环境３个锥体３个锥体

动态锥体个数

２２

高度变化范围

［８，２２］［８，２２］

锥体位置变化

否是

实验２实验３

４实验设计与结果

为了测试上述算法的在动态环境下追踪变化最优解的能

力，在ＤＦ１产生的二维环境下进行了一系列实验，ＤＦ１函数是由Ｍｏｒｒｉｓｏｎ和ＤｅＪｏｎｇ’它通过利用一些ｓ［８］在１９９９年提出的，锥体（ｃｏｎｅ）的组合产生复杂的环境。这个函数产生器曾经被设计用来在动态环境下对ＥＡ进行研究。ＤＦ１函数定义为下面这个公式，产生一个二维的多锥体环境。

ｉｉ（（（４）ｆＸ，Ｙ）＝ｍａｘｔ＝１，ＮＨｉ－Ｒｉ＊!

上式说明在搜索空间的适应值曲面上任一点的取值可以由一个最大化函数决定。其中，每个锥体的高度由Ｈ决定，Ｈｉ是第ｉ个锥体的高度，Ｒ是斜度参数，Ｒｉ表示第ｉ个锥体的斜度。顶点

（２）实验算法设置

种群由５０个随机分布在［０，初２０］的搜索空间的微粒组成。始速度与位置随机设定。

惯性权重! ＝０．７５。最大迭代次数１０００次，在每Ｃ１＝Ｃ２＝２．０，

次运行过程中，动态变化的锥体每经过１００次就进行一次变化更新。两种算法（ＡＰＳＯ，都重复进行１００次运算过程。ＩＮ－ＰＳＯ）实验允许误差设定为１０－６数量级。

（３）实验结果

在三个不同动态条件下，运行ＡＰＳＯ和ＩＮ－ＰＳＯ方法１００次算法追踪变化的极值的效果比较图，如下图３至图５所示。

１８１７１６ＹＦｉｔｎｅｓｓ

１５１４

１３１２１１１０９

０

２００

４００６００Ｘｌｔｅｒａｔｉｏｎ

８００１０００ＡＰＳＯＩＮ－ＰＳＯ

位置由Ｘ，（Ｘｉ，表示第ｉ个锥体的顶点位置。（Ｙ决定，Ｙｉ）ｆＸ，Ｙ）是在（Ｘ，位置的适应值。Ｙ）

实验中，算法的目标为寻找环境中高度最大值。图１是有３个锥体的适应度曲面。

１．００．５０－０．５－１．０－１．５－１．０

０．５

１．０

－０．５

０

０．５

０－０．５１．０－１．０

图１由ＤＦ１生成的３锥体适应度曲面

图３实验１追踪变化极值结果图

（１）实验环境设置

在由ＤＦ１生成的二维动态环境中进行了多个实验，并在同样的实验条件下与ＡＰＳＯ进行了比较。实验中，算法的目标为寻找环境中高度最大值。

实验１是由ＤＦ１生成两个锥体的典型的环境，其中一个锥体标记为Ａ，另一个锥体标记为Ｂ，其中Ａ的位置和高度保持不变，它的高度以一定的频率发生变化。Ｂ是动态变化的，

ＡＢＡ点，随着实验迭代运算的不断进行，在实验Ｂ的高度越来越高，

５４２００８，４４（９）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

图５是实验３的效果图。沿Ｘ轴移动，

５结论

本文提出了一种改进的小生境粒子群算法来解决适应非静态优化问题，通过多子群分布式评价策略来监测环境的变化。通过这种方式，可以立即得知环境的变化。还采用局部极值排挤策略来提高群体在解空间中的分布度，如果环境发生变化，可以让种群迁入更有希望的区域。简而言之，不论是在周期性变化还是在非周期性变化的环境中，新的算法都可以及时追

实验１中动态变化的Ｂ锥体每经过１００迭代次就进行一次变化更新，在图３中，虚线表示ＩＮ－ＰＳＯ的追踪效果，实线表示ＡＰＳＯ的追踪效果，可以明显地看出，实验初期，ＩＮ－ＰＳＯ与都能有效地追踪到变化的ＡＰＳＯ追踪变化极值效果相差不大，

极值，但是到了实验中期，在ＡＰＳＯ算法中种群收敛到某一极值［１４，此时，由于所有的感应粒子收敛于该极值１５］所在区域，点，失去了对其它区域变化的感应能力，不能追踪到最新的变化的极值，而ＩＮ－ＰＳＯ算法由于能保持很好的分布度，使得粒子群在搜索空间始终保持较好的分布，并且由小生境形成的多样化子种群保证了在搜索空间的不同区域中并行地进化搜索。能及时的追踪到变化了极值。

实验２中，动态变化的锥体个数为两个，锥体Ｂ和锥体Ｃ，锥体Ａ保持不变。在实验前期，Ｂ锥体变化幅度大于Ｃ锥体，在实验后期Ｂ锥体的变化幅度小于Ｃ锥体。它们的位置不发生变化。最初是锥体Ａ的顶点是极点，随着实验的时行，锥体Ｂ和Ｃ不断增高，由于开始Ｂ的增长幅度大，Ｂ的顶点先为极点，在实验执行的前５００次迭代中，ＡＰＳＯ与ＩＮ－ＰＳＯ都能很好地追踪到极值点，如图４所示，而在实验执行的５００次以后，Ｃ的增长幅度大于Ｂ的，而ＡＰＳＯ算法中粒子开始在［１６，１７］中附近而ＩＮ－ＰＳＯ能及时调整。这说明搜索，失去了对Ｃ顶点的追踪，了ＩＮ－ＰＳＯ方法对环境的动态改变有很强的适应性，有能力跟踪最优解的动态改变。

实验３在实验２的基础上，使Ｃ锥体的位置以一定的速度发生水平平移。锥体Ｃ高度在不断变换的同时，其水平位置

踪变化并采取相应的措施来尽量在最短的时间增大找到最优解的概率。

参考文献：

［１］ＢｒａｎｋｅＪ．Ｅｖｏｌｕｔｉｏｎａｒｙａｐｐｒｏａｃｈｅｓｔｏｄｙｎａｍｉｃｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂ－

ｌｅｍｓ－ｕｐｄａｔｅｄｓｕｒｖｅｙ［Ｃ］／／ＰｒｏｃｏｆＧＥＣＣＯＷｏｒｋｓｈｏｐｏｎＥｖｏｌｕｔｉｏｎ－２００１：２７－３０．ａｒｙＡｌｇｏｒｉｔｈｍｓｆｏｒＤｙｎａｍｉｃＯｐｔｉｍｉｚａｔｉｏｎＰｒｏｂｌｅｍｓ，

ＤｏｚｉｅｒＧ．ＡｄａｐｔｉｎｇＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎｔｏｄｙ－［２］ＣａｒｌｉｓｌｅＡ，

ｎａｍｉｃｅｎｖｉｒｏｎｍｅｎｔｓ［Ｃ］／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ．ＬａｓＶｅｇａｓＮｅｖａｄａ，ＵＳＡ，２０００：４２９－４３４．［３］ＫｅｎｎｅｄｙＪ，ＥｂｅｒｈａｒｔＲＣ．ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄ－

ｉｎｇｓｏｆｔｈｅＩＥＥＥＩｎｔＣｏｎｆＯｎＮｅｕｒａｌＮｅｔｗｏｒｋｓ．ＰｉｓｃａｔａｗａｙＮＪ，１９９５：１９４２－１９４８．

［４］ＣｌｅｒｃＭ．ＴＲＩＢＥＳ－Ａｐａｒａｍｅｔｅｒｆｒｅｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚｅｒ［ＥＢ／

（２００２－０８－１０／２００３－１０－０８）．ｈｔｔｐ：／／ｃｌｅｒｃ．ｍａｕｒｉｃｅ．ｆｒｅｅ．ｆｒ／ＰＳＯ．ＯＬ］．

ＶｅｓｔｅｒｔｒｏｍＪＳ，ＲｉｇｅｔＪ．ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎｗｉｔｈ［５］ＫｒｉｎｋＴ，

ｓｐａｔｉａｌｐａｒｔｉｃｌｅｅｘｔｅｎｓｉｏｎ［Ｃ］／／ＴｈｅＩＥＥＥＣｏｎｇｒｅｓｓｏｎＥｖｏｌｕｔｉｏｎａｒｙＨｏｎｏｌｕｌｕ，Ｈａｗａｉｉ，ＵＳＡ，２００２．Ｃｏｍｐｕｔａｔｉｏｎ，

周春光，徐中宇，等．动态环境下的群核进化粒子群优化方［６］窦全胜，

法［Ｊ］．计算机研究与发展，（１）：２００６，４３８９－９５．

ＳｈｉＹ．Ｔｒａｃｋｉｎｇａｎｄｏｐｔｉｍｉｚｉｎｇｄｙｎａｍｉｃｓｙｓｔｅｍｓ［７］ＥｂｅｒｈａｒｔＲＣ，

ｗｉｔｈｐａｒｔｉｃｌｅｓｗａｒｍｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２００１ＣｏｎｇｒｅｓｓｏｎＥｖｏ－（ＣＥＣ２００１），ｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ２００１：９４－１００．

ＭｏｒｒｉｓｏｎＲＷ．Ａｔｅｓｔｐｒｏｂｌｅｍｇｅｎｅｒａｔｏｒｆｏｒｎｏｎ－［８］ＤｅＪｏｎｇＫＡ，

ｓｔａｔｉｏｎａｒｙｅｎｖｉｒｏｎｍｅｎｔｓ［Ｃ］／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＣｏｎｇｒｅｓｓｏｎＥｖｏｌｕ－ｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ．ＩＥＥＥＰｒｅｓｓ，１９９９：２０４７－２０５３．

（上接３９页）

ＫｅｒｎｉｇｈａｎＢＷ．Ａｎｅｆｆｅｃｔｉｖｅｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｔｈｅ［２］ＬｉｎＳ，

ｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ［Ｊ］．ＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ，１９７１，１９：４８６－５１５．［３］ＧｏｌｄｂｅｒｇＤＥ．Ａｌｌｅｌｅｓ，ｌｏｃｉａｎｄｔｈｅｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ［Ｃ］／／

ＧｒｅｆｅｎｓｔｅｔｔｅＪＪ．ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＦｉｒｓｔＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓａｎｄＴｈｅｉｒＡｐｐｌｉｃａｔｉｏｎｓ．Ｐｉｔｔｓｂｕｒｇｈ：ＰｉｔｔｓｂｕｒｇｈＰＡＣａｒｎｅｇｉｅ－ＭｅｌｌｏｎＵｎｉｖｅｒｓｉｔｙ，１９８５：１５４－１５９．

［４］ＧｏｌｄｂｅｒｇＤＥ．Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓｉｎｓｅａｒｃｈ，ｏｐｔｉｍｉｚａｔｉｏｎａｎｄｍａ－

ｃｈｉｎｅｌｅａｒｎｉｎｇ［Ｍ］．ＭＡ：ＡｄｄｉｓｏｎＷｅｓｌｅｙＲｅａｄｉｎｇ，１９８９：１－１０．

ＴＳＰ１４０－４３．

［６］ＯｌｉｖｅｒＬＭ，ＳｍｉｔｈＤＪ，ＨｏｌｌａｎｄＪＲＣ．Ａｓｔｕｄｙｏｆｐｅｒｍｕｔａｔｉｏｎ

ｃｒｏｓｓｏｖｅｒｏｐｅｒａｔｏｒｉｎｔｈｅＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ［Ｃ］／／Ｐｒｏｃｅｅｄ－ｉｎｇｏｆｔｈｅＳｅｃｏｎｄＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＧｅｎｅｔｉｃＡｌｇｏ－１９８７：２２４－２３０．ｒｉｔｈｍｓ，

（１９９６）［７］ＲｅｉｎｅｌｔＧ．ＴＳＰＬＩＢ［ＤＢ／ＯＬ］．．ＨＴＴＰ：／／ｗｗｗ．Ｉｗｒ．ｕｎｉ＿ｈｅｉｄｅｌｂｅｒｇ．

ｄｅ／ｉｗｒ／ｃｏｍｏｐｔ／ｓｏｆｔ／ＴＳＰＬＩＢ９５／ＴＳＰＬＩＢ．ｈｔｍｌ．

［８］卿翊轩．基于基因库求解ＴＳＰ问题的改进的反序－杂交算法［Ｊ］．计算

（７）：机工程与应用，２００５，３９３７－３９．

［９］ＣｈｅｎｇＲＷ，ＧｅｎＭ．Ｃｒｏｓｓｏｖｅｒｏｎｉｎｔｅｎｓｉｖｅｓｅａｒｃｈａｎｄｔｒａｖｅｌｉｎｇ

ｓａｌｅｓｍａｎｐｒｏｂｌｅｍ［Ｃ］／／ＧｅｎＭ．Ｐｒｏｃｅｅｄｉｎｇｏｆ１６ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎ－１９９４：５６８－５７９．ｏｆＴｅｃｈｎｏｌｏｇｙ，