冯 翔 马美怡 虞慧群. TSP湖水能量优化算法[J]. 计算机研究与发展, 2013, 50(9): 2015-2027.
 引用本文: 冯 翔 马美怡 虞慧群. TSP湖水能量优化算法[J]. 计算机研究与发展, 2013, 50(9): 2015-2027.
Feng Xiang, Ma Meiyi, and Yu Huiqun. Lake-Energy Optimization Algorithm for Travelling Salesman Problem[J]. Journal of Computer Research and Development, 2013, 50(9): 2015-2027.
 Citation: Feng Xiang, Ma Meiyi, and Yu Huiqun. Lake-Energy Optimization Algorithm for Travelling Salesman Problem[J]. Journal of Computer Research and Development, 2013, 50(9): 2015-2027.

## Lake-Energy Optimization Algorithm for Travelling Salesman Problem

• 摘要: 冬季湖面冰冻是一种常见的自然现象.受这一自然现象启发，提出了一种新的智能并行算法——湖水能量优化算法，并应用该算法解决旅行商问题.湖水能量优化算法模拟湖水降温时湖面的冰冻过程.随着温度的降低，湖水分子失去能量，当能量达到冰冻阈值时，分子析出结冰.湖水能量受到湖水中心能量、大气能量、湖水分子能量以及湖面风吹动等多方面影响.由此建立湖水能量优化算法的数学模型——湖水能量模型和风动模型等，并通过收敛性定理和Lyapunov稳定性定理进行理论证明，验证了算法的收敛性和解决旅行商问题的有效性.最后，通过实验模拟湖水能量优化算法解决TSPLIB中标准实例问题，并将实验结果与其他经典算法进行比较，进一步说明了湖水能量优化算法解决复杂NP难题时高效率、低迭代次数及强收敛性的特性.

Abstract: Lake freezing is a common natural phenomenon in winter. Inspired by this phenomenon, a novel intelligent and parallel algorithm, lake-energy optimization algorithm (LEO), is proposed in this paper. The LEO algorithm simulates the process of lake freezing. With the temperature of lake reducing, the water loses energy to the environment and starts to precipitate and freeze when its energy is below the threshold of freezing point. The LEO approach consists of two major models: the lake energy model and the wind-blow model. For the lake energy model, the center energy of lake, atmospheric energy, molecular energy of lake, as well as the wind are the main factors that affect the energy of lake with different weights under each stage of freezing. Meanwhile, the wind-blow model, as a supportive role, is responsible for agitating after freezing to prevent the solution from local optimum. Furthermore, the properties of the approach, including the correctness, convergence and effectiveness of the algorithm, are verified theoretically through the Convergent Theorem and the Lyapunov Second Theorem on stability. Via numerous simulations of TSPLIB and comparison with other classical algorithms, the characters of high efficiency, low computational complexity and strong convergence of the LEO algorithm are illustrated, which are especially crucial for the functioning of large-scale distribution problems.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈