罗金炎

(闽江学院 数学系， 福建 福州 350108)

旅行商问题(TSP)是组合优化领域中经典的NP难问题[1]，具有很强的现实意义.由于在许多领域都有广泛的应用，如计算机网络设计、通信节点设置、集成电路布线、物流配送等，因而一直以来是研究热点，为解决实际问题，广大研究者提出了许多求解算法(精确式或启发式).精确式算法能够得到问题最优解，但是需要与问题维数成指数级增长的时间成本，所能够求解的问题规模非常有限.启发式算法也称作近似算法，它以牺牲找到最优解的保证为代价，在合理的时间内找到近似解甚至最优解，其求解复杂度多是多项式阶数的.随着人工智能的发展，许多智能优化算法应用于TSP问题的求解，取得了较好结果.比如神经网络算法[2]、模拟退火算法[3]、禁忌搜索算法[4]、遗传算法[5]、蚁群算法[6]、粒子群算法[7]等.这些智能优化算法求解TSP问题，大多采用二进制编码求解0-1整数规划问题的思路进行寻优.本文利用等式约束规划问题K-T点的一个充分条件，将TSP问题的线性等式约束非线性规划进行降维使之转化为无约束极大极小优化问题.并基于基因调节原理运用外推技巧来改进粒子群算法，新的算法通过利用不同位置粒子的差异来引导外推方向，采用满足有限平方和准则的动态调节因子并在速度项中添加高斯扰动，来提高算法的寻优效率.数值实验结果验证了本文提出算法的有效性并具有较好的收敛效率.

1 等……

登录APP查看全文