Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/HPCC.and.EUC.2013.239 | 2013 IEEE 15TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS & 2013 IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND UBIQUITOUS COMPUTING (HPCC_EUC) |
Keywords | Field | DocType |
Steiner Tree, estimation distribution algorithm, approximation algorithm, intelligence optimization, probabilistic model | Population,Mathematical optimization,Algorithm design,Estimation of distribution algorithm,Computer science,Steiner tree problem,Probability distribution,Statistical model,Probabilistic logic,Time complexity | Conference |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yaqing Wang | 1 | 0 | 0.68 |
| Hua Wang | 2 | 76 | 14.82 |
| Guohong Kong | 3 | 1 | 1.03 |