Global Optimization 1: Using Genetic Methods on the (0,1)-Knapsack Problem

Finding the best solution to a combinatorial problem can be difficult due to the extremely large number of possible solutions. This book describes the application of Genetic Methods to one such problem; the (0,1)-Knapsack Problem. Part I presents an overview of several combinatorial problems and different solution methods. It then gives a detailed description of two search strategies; Genetic Algorithms and Evolutionary Programming. Both of these search strategies are population-based methodologies that use one or two members of the current population of solutions to generate a new solution and a heuristic "survival of the fittest" strategy to improve the performance of the population. Procedures are described for selecting parent solutions, generating new solutions and processing these offspring. Part II examines the performance of these algorithms on the (0,1)-Knapsack Problem and describes how software can be obtained and run to test other parameters.