Solving nonlinear combinatorial optimization problems with a cooperative genetic algorithm and tabu search meta-heuristic.

摘要

An original and effective approach for solving large, nonlinear discrete combinatorial optimization problems is described herein. The approach integrates two problem solving approaches into a unique and effective method for solving difficult discrete combinatorial optimization problems with modest computational resources. A hybrid genetic algorithm designs initial starting solutions and conditions for a elementary version of tabu search meta-heuristic. The tabu search meta-heuristic employs a form of adaptive memory to guide a local search mechanism through a neighborhood space. The tabu search explores the problem space and records improved solutions and their conditions. This information is used by the genetic algorithm to design new initial search conditions. This iterative, cooperative process continues until pre-specified conditions are satisfied. The combination of these two approaches yields an algorithm that produces solutions that either tie, improve or are within a few percent of the best known solutions, many of which were produced on powerful computing machinery. In contrast, the integrated approach was implemented on a modest personal computer. The approach was applied to several different classes of problems to demonstrate its versatility. The problem classes that comprised the test suite were quadratic assignment and asymmetric traveling salesperson. These problems were obtained from a several widely available Internet sources and have published best known solutions. In each class, several problem instances (varying by size) were used to test the efficacy of the approach and investigate the relationship between problem size and algorithm performance. The results indicate that the integrated approach dominates both the genetic algorithm and tabu search meta-heuristics when each are individually applied to the problem sets.