An improved EDA for solving Steiner tree problem

作者：Liu Lei; Wang Hua^*; Kong Guohong

来源：Concurrency and Computation: Practice and Experience (CCPE) , 2015, 27(13): 3483-3496.

DOI：10.1002/cpe.3466

• Steiner tree
• estimation of distribution algorithm
• approximation algorithm
• intelligence optimization
• probabilistic model

Steiner tree problem and its derivations are widely employed to optimize the design of transportation, communication networks, biological engineering and the QoS multicast routing problem. It is one of well-defined open issues which have attracted many research efforts. Different from the existing works, this paper develops a new method of solving Steiner tree problem by using the improved estimation of distribution algorithms (EDA). Further, the performance of developed method is validated by applying on multicast routing optimization. The developed method randomly initializes n trees which contain the source node and the destination nodes. And some individuals select the crossover operation randomly to add the population diversity and avoid the algorithm premature convergence. The algorithm constructs a probabilistic model according to the selected elites, which is capable of estimating the probability distribution of the solution. The probabilistic model is updated according to the new population. New trees are generated based on the probabilistic model. This process iterated until designated termination criteria are met. The improved EDA algorithm gradually evolves trees to obtain a better solution. Simulation validations suggest that the developed method leads to better performance. In particular, the complexity in terms of the converging speed improves significantly compared to other algorithms.

• 出版日期2015-9-10
• 单位山东大学