文献类型：期刊文献

中文题名：TSP湖水能量优化算法

英文题名：Lake-Energy Optimization Algorithm for Travelling Salesman Problem

作者：冯翔[1];马美怡[1];虞慧群[1]

机构：[1]华东理工大学信息科学与工程学院,上海200237

年份：2013

卷号：50

期号：9

起止页码：2015

中文期刊名：计算机研究与发展

外文期刊名：Journal of Computer Research and Development

收录：CSTPCD;;EI(收录号：20134116841948);Scopus;北大核心:【北大核心2011】；CSCD:【CSCD2013_2014】；

基金：国家自然科学基金项目(60905043;61073107;61173048);上海市教育委员会科研创新基金项目;中央高校基本科研业务费专项基金项目

语种：中文

中文关键词：湖水能量优化;冰冻模型;启发式算法;分布并行算法;旅行商问题

外文关键词：lake-energy optimization; freezing model; heuristic algorithm; distributed and parallelalgorithm; travelling salesman problem （TSP）

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