多群体并行演化算法的研究

《多群体并行演化算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京邮电大学硕士研究生学位论文第一章绪论题等）、最优管理（生产调度、系统决策与控制等）[3]。1.2群体演化算法1.2.1群体演化算法概述群体演化算法与是近年来通过学者对模仿自然界中动物或社会中人类的群体表现出的某些合作、协调等特征上发展而来的新算法。比如模拟鸟群觅食规律发展而来的粒子群算法[4](PartialSwarmOptimization,PSO)；模仿人类群体劳动中相互合作发展而来的团队进步算法[5](TeamProgressAlgorithm,TPA)；模仿蜂群采蜜机制的人工蜂群算法[6](ArtificialBeeColonyAlgorithm,ABC)等等。

2、各种群体演化算法来自于模仿不同的群体，具有不同的搜索机制和特点，但都具有以下共同特征：(1)群体性：算法初始化对象是包含多个个体的群体，算法每次迭代过程中可以产生多个解，每个个体代表一个可行解，寻优过程中只要有一个解满足要求，就可以求解到全局最优解，适用于复杂的多极值问题。(2)全局寻优能力：当优化问题为多峰函数，在有限区域内具有多个局部极值点、可行域和目标函数不是凸函时能通过全局搜索求解到可接受的近似全局最优解。(3)并行性：每种群体演化算法都内含并行性，即每个群体可以分解为若干个个体数目较少子群体，每个子群体可以各自在求解区间内的不同区域同时进行寻优。群体演化算法还具有

3、计算上的并行性，群体中的每个个体的目标函数计算，候选新个体的生成都可以并行执行。(4)随机性与智能性：各个演化算法搜索时个体的选择，以及全局寻优的机制都带有一定的随机性，寻优过程中自适应、自组织、自学习。1.2.2群体演化算法发展现状当前群体演化算法正处于蓬勃发展阶段，出现较早的粒子群算法、蚁群算法等已经获得了广泛的应用，算法的改进和发展趋于成熟。然而，粒子群算法虽然原理简单、程序实现容易、调节参数少，但是在面对高维度复杂性问题时容易出现早熟收敛、计算效率低等缺陷，在某些复杂工程问题上无法得到应用。近年来，新出现的一些群体演化算法在计算效率、鲁棒性和稳定性上都优于早先的粒子

4、群算法，其中效果最优的就是人工蜂群算法[7]。2万方数据南京邮电大学硕士研究生学位论文第一章绪论1.2人工蜂群算法ABC是由Karaboga于2005年提出的一种根据蜜蜂采蜜机制所启发的群体演化算法，在函数优化上ABC算法比PSO、GA等具有更好的全局收敛性[8]，表明人工蜂群算法在函数优化上的优越性，相对于其他演化算法具有算法参数少，鲁棒性强，计算效率高等优点。某个优化问题可以表示为：min/max{f(x)}x=[x1,x2,...,xn]T(1-1)푥푖∈[푎푖,푏푖],i=1,2,...,nABC算法原理是通过模拟蜜蜂采蜜过程并应用于函数优化上，将蜂群分为3类：雇佣

5、蜂、观察蜂和侦查蜂。雇用蜂和观察蜂用于对蜜源的开采，侦查蜂用于丰富蜜源的种类。函数的解和目标函数值分别对应于蜜源的位置和花蜜的数量。寻找最优花蜜源的过程如下：在函数取值范围[a,b]内随机生成N个花蜜位置，即函数的可行解，根据花蜜的数量，即目标函数值进行排序，雇用蜂取较优异的前N/2个花蜜位置作为蜜源位置，随后在其发现的各个相邻的蜜源按式(1-2)搜索新的蜜源：vij=x+f(xij-xkj)(1-2)ijij式中，vij为搜索到的新蜜源位置，xij为原来第i个蜜源位置的第j维分量，xkj为相邻的不等于本身的蜜源位置的第j维分量，ϕij为[-1,1]之间的随机数。雇用蜂比较

6、前后两个蜜源花蜜的数量，即适应度值，选择花蜜数量较多的作为新的蜜源位置，并保存所有蜜源中花蜜数量最多的蜜源位置作为最优蜜源位置，即全局最优解，观察蜂根据雇用蜂蜜源位置的花蜜数量，即适应度值，通过轮盘赌方式选择某一雇佣蜂开采的蜜源位置，如式(1-3)所示：Pi=fitiNåfitnn=1(1-3)式中fiti代表第i个蜜源的适应度值。搜索后的蜜源位置即为观察蜂的依附蜜源，随后观察蜂在依附蜜源附近按(1-2)式搜索新的蜜源位置，并比较新的蜜源位置和当前所依附的蜜源位置的花蜜数量，选择花蜜数量更多的蜜源位置作为新的蜜源位置，同时更新所有蜜源中花蜜数量最多的蜜源作为最优蜜源位置。为

7、了避免ABC算法出现早熟收敛，在采蜜过程中，如果一个蜜源经过若干次搜索都没有出现变化，那么依附在该蜜源位置上的雇用蜂变成侦查蜂，在整个范围内随机搜索一个新的蜜源位置替换当前的蜜源位置。3万方数据南京邮电大学硕士研究生学位论文第一章绪论人工蜂群算法因其良好的全局寻优性能、简单的原理和较少的参数调节已经成为近年来热门的演化算法，被应用于诸多领域[9][10]。1.2多群体并行演化算法1.2.1演化算法的并行化当前串行演化算法的应用已经十分广泛，但是随着最优化问题需求的增加，演化算法需要解决的问题的发杂度和维度也随之增加