Extending evolutionary algorithms to discover tri-criterion and non-supported solutions for the minimum spanning tree problem
Madeleine Davis-Moradkhan, Will Neil Browne, Peter Grindrod · 2009
The study of multi-criterion minimum spanning trees is important as many optimization problems in networks, such as communication, transport and utilities can be represented by this model. Conventional evolutionary approaches struggle to discover near-optimal solutions due to the combinatorial search space, and the difficulty in discovering the non-supported solutions. Recently, a knowledge-based evolutionary approach, KEA, has been developed that overcomes some of the problems of the earlier algorithms as it is not restricted to the bi-criterion case, finds non-supported solutions and scales well to larger problems; however, the mid-point of its Pareto front is often dominated by alternative algorithms where they are applicable. Novel extensions to KEA, increasing the knowledge of the mid-point, termed KEA-W are examined, eliminating the mid-point deficiencies at the cost of computational time.