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

Discrete Firefly Algorithm for Probabilistic Traveling Salesman Problem

对随机组合优化问题中的概率旅行商问题(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.