S. Ding and N. Ishii (Japan)
Genetic Algorithms, Graph theory.
Based on the Steiner minimal tree problem(SMTP), we propose a new problem called Multi-Objective Steiner tree problem(MOSTP). Multi-Objective Steiner Tree Problem should be found a number of solutions, in order to provide the decision can be made with insight into the characteristics of relation between minimal weight cost and the edge number of Steiner spanning tree. As a Multi-Objective optimization problem(MOP), a Pareto-optimal solution is a rational solution to the MOP. This problem is a NP-hard problem because Steiner Minimal Tree Problem is NP-hard problem. Therefore, we propose a genetic algorithm to solve this problem. Steiner spanning tree is calculated based on greedy algorithm in MOSTP. The GA approach performs a search for Pareto-optimal set and evolves them in each generation. In order to prove our algorithm robust, we tested the B-problem set from Beasley. From the experimental results, it really provides enough information such as path, edge number and tree weight cost for decision maker to choose the best way.
Important Links:
Go Back
