离散萤火虫优化算法求解概率旅行商问题  

Discrete Firefly Algorithm for Probabilistic Traveling Salesman Problem

作　　者：薛晗[1] 赵强[1] 马峰[1] 邵哲平[1] 

机构地区：[1]集美大学航海学院,福建厦门361021

出　　处：《测控技术》2016年第5期115-118,123,共5页Measurement & Control Technology

基　　金：国家自然科学基金资助项目(51109090);福建省自然科学基金项目(2015J01214);福建省科技计划重点项目(2012H0030);福建省高等学校新世纪优秀人才支持计划项目(JA12181);厦门市科技计划高校创新项目(3502Z20123019)

摘　　要：对随机组合优化问题中的概率旅行商问题(PTSP)的理论和方法进行了研究分析,采用现代进化算法中有代表性发展优势的萤火虫优化算法(FA),提出一种离散萤火虫优化算法(DFA)以求解。其中引入了新的学习机制使其相比原始的萤火虫优化算法,更容易搜索到全局最优解,有更好的收敛性能。实验中用TSPLIB中的经典实例进行测试来验证其可行性。考察了萤火虫数量和进化迭代次数对求解结果性能的影响,并将DFA与GA、PSO和ACO等其他著名的进化计算算法进行性能比较。实验结果证实了DFA无论对固定访问概率,还是访问概率为区间内随机数等不同情况,都具有良好的有效性和高效性,因此对求解随机组合优化系列问题的有效解决具有一定参考和借鉴价值。Based on the research and analysis of the theory and method of the probabilistic traveling salesman problem（PTSP）,one of the stochastic combinatorial optimization problems,a discrete firefly algorithm（DFA）which has representative development advantages in modern evolutionary computing algorithms,is proposed.A new learning mechanism is introduced into the new algorithm,which makes it easier to search global optimum solution than the original firefly algorithm and obtain better convergence performance.Several benchmark TSPLIB instances are used to experimentally verify the advantages of the proposed algorithm over the original firefly algorithm.Several parameters such as the number of fireflies and maximal iteration times are tested to investigate their influence to the performance of solving results.Other famous evolutionary computing algorithms such as GA,PSO and ACO are used to compare the performance of the proposed algorithm.The result shows that DFA can efficiently and effectively solve PTSP under fixed accessing probability and also stochastic accessing probability among random interval.Thus,DFA has reference value for the effective solution of stochastic combinatorial optimization problems.

关 键 词：萤火虫算法(FA) 概率旅行商问题(PTSP) 随机组合优化 进化计算 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]