Nature-Inspired Search Techniques for Combinatorial Optimization Problems (Ph.D. Thesis)
Cláudio Rossi · 2001
The NP-hard class contains problems that are ``difficult'''' to be solved by exact algorithms due to the exponential growth of their solution search space with the dimension of the input instance. Since many real-life problems map directly into well-known NP-hard problems, a variety of techniques to approach them have been developed. Standard techniques rely on heuristic rules to seek ``good'''' solutions at a reasonable cost. Natural Computation, including techniques like Evolutionary Algorithms, Evolutionary Game Theory, and Simulated Annealing, takes its inspiration by processes present in nature. The aim of this thesis is to investigate how nature-inspired search techniques can be used for the approximate solution of NP-hard optimization problems. Different approaches often have complementary behaviors. Thus algorithms integrating ideas coming from different techniques can be more effective than the single techniques used in isolation. In this thesis we investigate algorithms based on concepts stemming from evolutionary game theory, and their combination with simulated annealing as a technique to escape from local optima. Also, we study the integration between local search techniques and evolutionary algorithms, and develop an algorithm which is able to automatically adapt its parameters to the fitness landscape. We show with this thesis that nature-based algorithms combining ideas coming from different techniques can give better results than the original techniques applied in isolation, and how adaptation mechanisms can be devised to avoid the problem of the parameters'' tuning and help the search. To this end a large number of experiments is conducted on standard problem sets.