欧氏Steiner最小树的Delaunay三角网混合智能求解方法

欧氏Steiner最小树问题是组合优化中一个经典的NP难题,在许多实际问题中有着广泛的应用.由于使用普通智能算法求解较大规模问题时,极易陷入拓扑结构的局部最优,因此,基于Delaunay三角网技术并结合智能算法的有关思想,设计了一种改进的混合型智能求解方法,可大幅度提高算法在寻找更好拓扑结构上的有效性.算法在Matlab环境下编程实现,经大量STEINLIB中的标准数据实例测试和验证,获得了满意的效果,为求解较大规模的欧氏Steiner最小树问题提供了新的有效方法.

Hybrid Intelligent Algorithm Based on Delaunay Triangulation for Euclidean Steiner Minimum Tree Problem

Euclidean Steiner minimum tree problem is a classical NP-hard problem in combination optimization, with a wide range of application in many practical problems. Because of the easiness of getting stuck into local optimal topology by using general intelligent algorithms for large scale problems, a combination of Delaunay triangulation technique and the intelligent algorithm is modified to design a hybrid intelligent method, which can apparently improve the effectiveness of searching for better topology structures. The proposed algorithm is coded in Matlab, and is tested through series of standard instances from STEINLIB. The algorithm can obtain satisfied results and provide a new effective way to solve large scale Euclidean Steiner minimum tree.