欧氏Steiner最小树问题的智能优化算法

Intelligent Optimization Algorithms for Euclidean Steiner Minimum Tree Problem

欧氏平面内连接固定原点的最小树长问题,即欧氏Steiner最小树问题,为组合优化中的NP难题,因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将平面划分成网格,然后分别介绍两种算法的原理及实现过程,最后通过一系列计算实验,测试了算法的运行性能,获得了较好的效果。

The Euclidean Steiner tree problem, which concerns the construction of a tree that connects a given set of terminal points in Euclidean space with the minimal total lengths, is NP-hard in eomhinatorial optimization. This paper presents two intelligent optimization algorithms-the simulated annealing algorithm and the ant algorithm. Firstly, this paper summarizes the intelligent optimization algorithm and divides space into grids, then introduces the principles of two algorithms and their implementations. Finally, it implements serics of computational experiments and tests the performances, that result within satisfaction.