![]() |
Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications
by Lakhmi C. Jain; N.M. Martin CRC Press, CRC Press LLC ISBN: 0849398045 Pub Date: 11/01/98 |
Previous | Table of Contents | Next |
First, an initial population of chromosomes is created at Generation 0, either randomly or through heuristic means, and the fitness value of each chromosome is evaluated. A new generation is then created, by selecting the best fit chromosomes from the previous generation. A typical randomized selection procedure for the GA is the proportional or roulette wheel selection, where the selection probability of each chromosome is proportional to its fitness. To create new chromosomes (new solutions in the search space), crossover and mutation operators are applied to a certain proportion of chromosomes in the new population. Crossover creates two new offspring by merging different parts of two parent chromosomes. The one-point crossover is illustrated in Figure 5; a random cut point is selected on the parent chromosomes and their end parts are exchanged. Other variants exist, like two-point crossover where the substring located between two randomly selected cut points is exchanged, or uniform crossover where the parent that contributes its bit value to the first offspring is randomly selected at each position (while the other parent contributes its bit value to the second offspring). Mutation is a secondary operator that changes a bit to its complementary value with a small probability at each position.
Figure 5 The one-point crossover.
Together, selection and crossover effectively search the problem space by combining bit patterns found on good chromosomes to produce offspring with potentially higher fitness values (building block hypothesis). Mutation acts as a background operator to prevent the premature loss of bit values at particular loci. The genotypes that survive, over time, will be those that have proven to be the most fit. The termination criteria of a GA are convergence within a given tolerance or completion of a predefined number of generations. Note that the sequence of populations generated by the GA can be viewed as parallel search trajectories in the space of admissible strings.
Although theoretical results that characterize the behavior of the GA have been obtained for bit-string chromosomes [15], not all problems lend themselves easily to this representation. This is the case, in particular, for sequencing problems where an integer representation is often more appropriate. In the case of the VRP, an integer could stand for a particular customer, while a string of integers would represent a vehicle route. For example, the string 3 1 2 would mean that, starting from the central depot, customer 3 is visited first, customer 1 is visited second, and customer 2 is visited last.
However, a straightforward application of the GA on this integer representation would not be effective, because traditional crossover and mutation operators are not designed to preserve orderings. For example, assuming m = 1 vehicle and n = 5 customers numbered from 1 to 5, the one-point crossover always produces infeasible offspring from the integer strings 1 2 3 4 5 and 5 4 3 2 1; at each cut point, customers are duplicated while others are missing from the resulting offspring routes (see Figure 6).
Figure 6 One-point crossover does not produce valid orderings
A number of studies have thus been conducted to address the VRP with GAs based on innovative representation schemes and special crossover operators that preserve sequential information. The approaches presented in the next section have been successful in solving VRPs with complex side constraints [43]. They are illustrative of different coding schemes, either binary- or integer-based, as well as different ways of handling side constraints through penalties, decoders, and repair operators.
The methods presented in this section follow the cluster-first, route second problem-solving approach, where clusters of customers that naturally fit in the same vehicle route (due, for example, to spatial proximity) are first identified. Then, the customers are sequenced within each cluster. Here, the GA is used in the clustering phase, while the routing or sequencing is done using classical operations research approaches.
Previous | Table of Contents | Next |