应用捕食搜索策略的改进多态蚁群算法
发布时间：2021-09-08 15:37
结合捕食搜索策略对多态蚁群算法进行改良。该算法引入以下机制:在人工蚁选择路径阶段,设置侦查素路径为优先,为非侦查素路径设置惩罚因子;利用权值在侦查素和非侦查素路径都施加信息素,通过该机制避免多态蚁群算法陷入停滞;在每轮人工蚁最优结果的邻域应用捕食搜索策略,并通过竞争机制选择最优解更新信息素。通过TSP的仿真实验结果表明,提出的融合算法可以有目的地指导信息素分布,加快算法向最优解的收敛速度及提高最优解质量,克服传统多态蚁群算法的缺陷。
【文章来源】：计算机工程与应用. 2019,55(14)北大核心CSCD
【文章页数】：7 页
【部分图文】：
多态蚁群算法的停滞示意
2019，55（14）4侦查素指导信息素分布的机制针对上述停滞问题，本文提出的PS-PACA采取如下策略：（1）合理设置nMAXPC，均匀化各路径的信息素分布；（2）为信息素设置最大最小阈值，防止各路径信息素差别过大；（3）优化搜索蚁搜索路径的方式；（4）优化信息素挥发策略的方式对多态蚁群算法进行改良。对PACA停滞发生时蚂蚁已走过的城市数进行统计，得出nMAXPC,TSP问题规模与已走过的城市数的关系如图2所示，可见，nMAXPC设置得越小，停滞发生得越早；按照原PACA设置的nMAXPC显然过小，这也是该算法很快陷入停滞的原因。此外，随着TSP问题规模的扩大，PACA的停滞问题并没有得到好转。由图2可知，随着nMAXPC值的扩大，每轮蚂蚁停滞前走过的城市增多。当nMAXPC=0时，蚂蚁无法选择城市。即算法刚开始就陷入停滞；当nMAXPC=n（n为城市数）时，停滞现象消失，nMAXPC值丧失减小搜索空间的意义；结合下面的优化步骤，本文将nMAXPC选为n/2较为合理。Stutzle等[3]提出的最大-最小蚂蚁系统（MAX-MINAntSystem，MMAS），通过为信息素设置上下限阈值的方法，改良了信息素浓度相差过大的情况。对于PACA，信息素的上下限阈值设置需满足既可避免各路径信息素相差过大，又能使最优路径有足够的信息素留存。当侦查蚁在城市周围留下侦察素后，搜索蚁首先按照式（6）从邻近的nMAXPC个城市中选择，当邻近的nMAXPC个城市已被选尽时，则依据基本蚁群算法概率选择公式进行选择，并且设置惩罚因子λ，提高侦察素在寻优过程中起到的作用。这样兼顾了多态蚁群算法快速收敛的特点，又使算法避免了停滞的问题。Pkij=ìí
平均最优值429.11428.877544.447898.60556.20578.2021763.1524393.90实验设定代数10001000100010002000200020002000平均收敛代数6764796>1000681362550>2000σ/%0.730.6700.482.016.062.2514.60表1TSP问题测试结果050100150200250300Iterationtimes560540520500480460440420LengthMMASPS-PACA10203040506070706050403020100YX（a）最优解随迭代次数的收敛情况（b）经PS-PACA优化的最优路径图4eil51问题测试结果050100150200250300Iterationtimes1000095009000850080007500LengthMMASPS-PACA12001000800600400200020040060080010001200140016001800YX（a）最优解随迭代次数的收敛情况（b）经PS-PACA优化的最优路径图5berlin52问题测试结果赵亚文，等：应用捕食搜索策略的改进多态蚁群算法119
【参考文献】：
期刊论文
[1]基于加工操作单元的多态蚁群装夹规划方法[J]. 黄风立,左春柽,顾金梅,王海燕,张礼兵. 机械工程学报. 2017(07)
[2]CCN中基于邻居协作的多态蚁群路由算法[J]. 刘期烈,夏远鹏,秦庆伟,冯志宇,吴凤阳. 计算机工程与应用. 2017(24)
[3]多态蚁群算法的认知无线电频谱分配[J]. 张婧怡,向新,王锋,孙晔,鲁阳,李斌. 空军工程大学学报(自然科学版). 2016(02)
[4]基于多态蚁群算法的高光谱遥感影像最优波段选择[J]. 丁小辉,李华朋,张树清. 遥感技术与应用. 2016(02)
[5]加权值多态蚁群算法[J]. 鲍文杰,朱信忠,赵建民,徐慧英. 软件工程. 2016(04)
[6]基于信息素的自适应连续域混合蚁群算法[J]. 周袅,葛洪伟,苏树智. 计算机工程与应用. 2017(06)
[7]基于二次退火机制的改进多态蚁群算法[J]. 杜振鑫,王兆青,王枝楠,秦伟,段云涛. 中南大学学报(自然科学版). 2011(10)
[8]基于自适应多态免疫蚁群算法的TSP求解[J]. 吴建辉,章兢,刘朝华. 计算机应用研究. 2010(05)
[9]Linux集群下基于改进多态蚁群负载均衡算法研究[J]. 师淳,李志蜀. 四川大学学报(自然科学版). 2009(05)
[10]多态蚁群算法[J]. 徐精明,曹先彬,王煦法. 中国科学技术大学学报. 2005(01)
硕士论文
[1]多态蚁群算法在TSP问题应用中的改进与优化[D]. 鲍文杰.浙江师范大学 2016
[2]多态蚁群算法研究及其应用[D]. 岳凤.山东师范大学 2009
本文编号：3391042
【文章来源】：计算机工程与应用. 2019,55(14)北大核心CSCD
【文章页数】：7 页
【部分图文】：
多态蚁群算法的停滞示意
2019，55（14）4侦查素指导信息素分布的机制针对上述停滞问题，本文提出的PS-PACA采取如下策略：（1）合理设置nMAXPC，均匀化各路径的信息素分布；（2）为信息素设置最大最小阈值，防止各路径信息素差别过大；（3）优化搜索蚁搜索路径的方式；（4）优化信息素挥发策略的方式对多态蚁群算法进行改良。对PACA停滞发生时蚂蚁已走过的城市数进行统计，得出nMAXPC,TSP问题规模与已走过的城市数的关系如图2所示，可见，nMAXPC设置得越小，停滞发生得越早；按照原PACA设置的nMAXPC显然过小，这也是该算法很快陷入停滞的原因。此外，随着TSP问题规模的扩大，PACA的停滞问题并没有得到好转。由图2可知，随着nMAXPC值的扩大，每轮蚂蚁停滞前走过的城市增多。当nMAXPC=0时，蚂蚁无法选择城市。即算法刚开始就陷入停滞；当nMAXPC=n（n为城市数）时，停滞现象消失，nMAXPC值丧失减小搜索空间的意义；结合下面的优化步骤，本文将nMAXPC选为n/2较为合理。Stutzle等[3]提出的最大-最小蚂蚁系统（MAX-MINAntSystem，MMAS），通过为信息素设置上下限阈值的方法，改良了信息素浓度相差过大的情况。对于PACA，信息素的上下限阈值设置需满足既可避免各路径信息素相差过大，又能使最优路径有足够的信息素留存。当侦查蚁在城市周围留下侦察素后，搜索蚁首先按照式（6）从邻近的nMAXPC个城市中选择，当邻近的nMAXPC个城市已被选尽时，则依据基本蚁群算法概率选择公式进行选择，并且设置惩罚因子λ，提高侦察素在寻优过程中起到的作用。这样兼顾了多态蚁群算法快速收敛的特点，又使算法避免了停滞的问题。Pkij=ìí
平均最优值429.11428.877544.447898.60556.20578.2021763.1524393.90实验设定代数10001000100010002000200020002000平均收敛代数6764796>1000681362550>2000σ/%0.730.6700.482.016.062.2514.60表1TSP问题测试结果050100150200250300Iterationtimes560540520500480460440420LengthMMASPS-PACA10203040506070706050403020100YX（a）最优解随迭代次数的收敛情况（b）经PS-PACA优化的最优路径图4eil51问题测试结果050100150200250300Iterationtimes1000095009000850080007500LengthMMASPS-PACA12001000800600400200020040060080010001200140016001800YX（a）最优解随迭代次数的收敛情况（b）经PS-PACA优化的最优路径图5berlin52问题测试结果赵亚文，等：应用捕食搜索策略的改进多态蚁群算法119
【参考文献】：
期刊论文
[1]基于加工操作单元的多态蚁群装夹规划方法[J]. 黄风立,左春柽,顾金梅,王海燕,张礼兵. 机械工程学报. 2017(07)
[2]CCN中基于邻居协作的多态蚁群路由算法[J]. 刘期烈,夏远鹏,秦庆伟,冯志宇,吴凤阳. 计算机工程与应用. 2017(24)
[3]多态蚁群算法的认知无线电频谱分配[J]. 张婧怡,向新,王锋,孙晔,鲁阳,李斌. 空军工程大学学报(自然科学版). 2016(02)
[4]基于多态蚁群算法的高光谱遥感影像最优波段选择[J]. 丁小辉,李华朋,张树清. 遥感技术与应用. 2016(02)
[5]加权值多态蚁群算法[J]. 鲍文杰,朱信忠,赵建民,徐慧英. 软件工程. 2016(04)
[6]基于信息素的自适应连续域混合蚁群算法[J]. 周袅,葛洪伟,苏树智. 计算机工程与应用. 2017(06)
[7]基于二次退火机制的改进多态蚁群算法[J]. 杜振鑫,王兆青,王枝楠,秦伟,段云涛. 中南大学学报(自然科学版). 2011(10)
[8]基于自适应多态免疫蚁群算法的TSP求解[J]. 吴建辉,章兢,刘朝华. 计算机应用研究. 2010(05)
[9]Linux集群下基于改进多态蚁群负载均衡算法研究[J]. 师淳,李志蜀. 四川大学学报(自然科学版). 2009(05)
[10]多态蚁群算法[J]. 徐精明,曹先彬,王煦法. 中国科学技术大学学报. 2005(01)
硕士论文
[1]多态蚁群算法在TSP问题应用中的改进与优化[D]. 鲍文杰.浙江师范大学 2016
[2]多态蚁群算法研究及其应用[D]. 岳凤.山东师范大学 2009
本文编号：3391042
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3391042.html
