|
Abstract : |
A parallel genetic algorithm is presented to solve the well-known capacitated lot-sizing problem. The approach is implemented on a massively parallel single instruction multiple data architecture with 16384 4-bit processors. Based on a random keys representation a schedule is backward oriented obtained which enables us to apply a very simple capacity check. 1 Parallel Genetic Algorithm Genetic algorithms are a general purpose optimization technique inspired by population genetics. The fields in which genetic algorithms are used range from operations research problems [17] and learning classifier systems[7], [11] to training neural networks [3]. For a detailed introduction to genetic algorithms see e.g. [9] or [15]. A genetic algorithm models the development of a population over a number of generations as it happens in nature. The understanding is that in nature the fitter an individual is the better is its chance to survive and the more and better, |
