An improved EDA for solving Steiner tree problem. (17th March 2015)

• Record Type: Journal Article
• Authors: Liu, Lei; Wang, Hua; Kong, Guohong; Limet, Sébastien; Smari, Waleed W.; Spalazzi, Luca; Hu, Jia; Gao, Jianliang
• Is Part Of: Concurrency and computation. Volume 27:Number 13(2015:Sep.)
• Page Start: 3483
• Page End: 3496
• Publication Date: 2015-03-17
• Subjects: Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3466
• Languages: English
• ISSNs: 1532-0626

Abstract

<abstract abstract-type="main"> <title>Summary</title> <p>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 <italic>n</italic> 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. Copyright © 2015 John Wiley & Sons, Ltd.</p> </abstract>