Multi-Objective GA For The Steiner Tree Problem

Steiner tree problem is a classical problem in combinatorial optimization, it has been broadly used and deeply developed in many fields. Currently, the study of Steiner tree problem almost focused on one objective, that is to obtain only one optimization objective. But the problems we faced in the real world are always not only one objective, they always have several objectives which restrict or affect one another. So a kind of Steiner tree problem with more than one objective is proposed in this paper, hence such problem is translated into multi-objective problem (MOP).Multi-objective problem should be found a number of solutions, but these traditional algorithms just provide several different approaches to translate the MOP into single-objective problem (SOP), then use the relatively perfect algorithms for SOP to solve the problem. The foundation of such algorithms is relied on single-objective optimization, so it's hard to obtain the satisfactory solution set every time. MOGA is deemed to be a perfect algorithm for MOP because MOGA is intrinsically suitable for parallel implementation and can find the global optimum of a problem with very high probability. In this paper, a MOGA is proposed to solve a kind of Steiner tree problem with two objectives.In the algorithm of this paper, the Steiner spanning tree is calculated based of greedy algorithm, the MOGA approach performs a search for Pareto-optimal set and evolves them in each generation until the algorithm stops. In the last generation, a Pareto-optimal set is found. These solutions in the set provide enough information of tree weight cost and edge number for decision maker to choose the best way. In order to prove the algorithm robust, the B-problem set from Beasley is tested. Three classical algorithms for Steiner tree problem are used to be compared in single objective. From the experimental results, the algorithm can find the optimal soluthin of single-objective Steiner tree, and it can also find the Pareto-optimal set of multi-objective Steiner tree.