Hybrid Evolutionary Algorithms for Selected Graph Problems with Constraints

Research project P 13602 Hybrid Evolutionary Algoriths for Selected Graph Problems Günther RAIDL 28.06.1999 The problem of identifying a shortest or cheapest interconnection between all nodes in a given graph occurs frequently in different practical areas as e.g. the design of communication networks or the development of electronic circuits. This problem is known as minimum spanning tree problem (MSTP), and normally it can be solved efficiently with existing algorithms. In many cases, however, various constraints must be regarded which make the classical algorithms unapplicable or inefficient. For example the number of edges entering or leaving a node (the degree of a node) may be limited to some maximum. Furthermore, it may be required that for each pair of nodes, the total length of the interconnection does not exceed a given upper bound or the number of nodes lying on this interconnection is less than or equal to a certain maximum. For such problems, no efficient exact algorithms, i.e. polynomial-time algorithms, are known. A problem similar to the MSTP is the Steiner problem in a graph (SPG): Not all nodes of a given graph, but only a predefined subset need to be interconnected in the cheapest way. This problem is known to be NP-complete, but heuristics and approximation techniques exist which find nearly optimal solutions in reasonable computing time. But if constraints like those described for the MSTP need to be regarded again, these heuristics and approximation techniques usually cannot be applied or often give only poor results. Especially in the last years, evolutionary algorithms (EAs) have shown their capabilities in finding high-quality solutions to many complex problems in reasonable computing time. Different publications document the principal applicability of EAs to the described graph problems, but various questions need to be answered which influence the efficiency essentially. For example, there axe manifold possibilities for representing a potential solution to the MSTP (SPG)-therefore a subtree of the graph-in the EA. Furthermore, it is crucial which variation operators are used to generate a new, possibly better potential solution from one or more existing solutions. Often, the combination of an EA and a classical heuristic or a local optimization method (hybridization) entails many advantages, but it is not clear in which way this can best be done. In this project, various possibilities to regard the described constraints will be investigated. Existing approaches for similar problems will be adapted accordingly, but new methods shall also be realized. Another central research topic is the efficient combination of these EAs with heuristics and local optimization algorithms. For this purpose, heuristic-based encoding - a kind of "intelligent" method of representing potential solutions in the EA - is a promising technique, which has already proved to be very effective for other combinatorial optimization problems. The different EA approaches will be characterized and compared to each other, but also to traditional problem solving methods on the basis of a large number of test problems. The main goal is therefore to develop efficient optimization techniques for finding near-optimal solutions to real-world MSTPs and SPGs. Furthermore, the results to be obtained by this project can also support the development of strategies for other combinatorial optimization problems.