标题：An estimation of distribution algorithm for steiner tree problem
作者：Wang, Yaqing ;Wang, Hua ;Kong, Guohong
作者机构：[Wang, Yaqing ;Wang, Hua ;Kong, Guohong ] School of Computer Science and Technology, Shandong University, Shunhua Road, Jinan, Shandong Province, 2501 更多
会议名称：15th IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 11th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2013
会议日期：13 November 2013 through 15 November 2013
来源：Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013
关键词：approximation algorithm; estimation distribution algorithm; intelligence optimization; probabilistic model; Steiner Tree
摘要：As one of the most well-known combinatorial optimization problems, Steiner tree problem is widely applied to optimization in transportation design, biological engineering, and communication networks. It has been proved to be NP complete, though. To solve this problem, researchers have provided many classic solutions. This paper proposes a new method of solving Steiner tree problem by using estimation of distribution algorithms (EDA). The basic idea is to initialize randomly n trees which contain the source node and the destination nodes. Some elites are selected by the selection operator. The algorithm then constructs a probabilistic model which attempts to estimate the probability distribution of the selected elites. Once the model is constructed, new trees are generated by sampling the distribution encoded by this model. These new trees are then incorporated back into the old population, possibly replacing it entirely. The process is repeated until some termination criteria are met. The algorithm constantly evolves trees to obtain a better solution tree with EDA ideas. This method leads to better performance, reduced time complexity, and optimized solution. Simulation results also show that the algorithm has better performance in searching and converging. © 2013 IEEE.