求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．

An Ant Colony Optimization Algorithms for the Minimum Steiner Tree Problem and its Convergence Proof

The minimum Steiner tree problem is one of the NP-hard problems, which has extensive applications in many real-world problem,such as communications network. Ant colony optimization algorithms is a recently proposed metaheurestic approach for solving complex combinatorial optimization problem. Taken one of the most important issues to the wireless sensor network,routing problem, as an example, the Steiner tree model is presented in this paper. A general framework of ant colony optimization algorithms for the minimum Steiner tree problem is developed and the iterative process of the algorithms is interpreted as a Markov process in discrete time. It is shown that under certain conditions, the solutions generated in each iteration converge with a probability that can be made arbitraily close to 1 to the optimal solution of the routing problem.