02-03-2013, 02:11 PM
General Structure of Genetic Algorithm
General Structure.docx (Size: 17.84 KB / Downloads: 20)
INTRODUCTION
A genetic Algorithm is an intelligent probabilistic search algorithm that simulates the process of evolution by taking a population of solution and applying genetic operators in each reproduction. Each solution in the population is evaluated according to some fitness measures. Fitter solutions in the population are used for reproduction. New offspring solutions are generated and unfit solutions in the population are replaced. The cycle of evaluation-selection-reproduction is continued until a satisfactory solution is found [37], [38]. Genetic algorithms have received considerable attention regarding their potential as an optimization technique for complex problems and have been successfully applied in the area of industrial engineering. Hollond [39] introduced genetic algorithms which, later on, were applied to a wide variety of problems.
Genetic Algorithm
The usual form of genetic algorithm was described by Goldberg. Genetic algorithms are stochastic search techniques based on the mechanism of natural selection and natural genetics. Genetic algorithms, differing from conventional search techniques, start with an initial set of random solution called population. Each individual in the population is called a chromosome, representing a solution to the problem at hand. A chromosome is a string of symbols; it is usually, but not necessarily, a binary bit string. The chromosomes evolve through successive iterations, called generations. During each generation, the chromosomes are evaluated, using some measure of fitness. To create the next generation, new chromosomes, called offspring, are formed by either (a) merging two chromosomes from current generation using a crossover operator or (b) modifying a chromosome using a mutation operator. A new generation is formed by (a) selecting according to the fitness values, some of the parents and offspring and (b) rejecting others so as to keep the population size constant. Fitter chromosomes have higher probabilities of being selected. After several generations, the algorithms converge to the best chromosome, with hopefully represents the optimum or sub optimal solution to the problem.
Representation
It is very important step for developing the GAs because it influences all the subsequent steps of GA. It plays a major role in the development of GAs. A candidate solution is represented by one string. This string can be coded in regular binary coding or integer coding. In this work, we have considered integer coding with dynamic array. Grefenstette et al. [55] discussed a representation scheme known as adjacency representation. Similarly, Goldberg and Lingle [56] presented a permutation representation scheme. Swaska et al. [57] discussed a matrix based representation scheme while solving the problems of flexible scheduling in a machining center. The string length is not defined at the initial stage. The length of string is kept dynamic to take care of all the constraint.
Initialization and Choice of Fitness Function
A genetic algorithm operates on a population of individual strings. Several researchers have used either heuristic procedures or random techniques to generate feasible strings that form the initial population. The random start technique is used for generating the feasible strings because the performance of GA is improved by using the random start [58]. For the effective search, the population should be more diverse. For initialization, the main aim is to improve the average fitness function value for minimizing the computation time. Therefore, in generating all the initial populations with different procedures, it is aiming to improve effectively the average fitness value of the population that does not significantly affect the diversity of the population. This is the main reason for randomly generating an initial population in this thesis.
Selection of GA parameter
The most difficult and time-consuming issue in the successful operation of GAs is determining good parameter settings. These parameters are: crossover probability (PC), mutation probability (PM), population size (POP_SIZE), number of generation (MAX_GEN), etc. Grefenstette [55] discussed the importance of choosing the appropriate value for these parameters of the optimization algorithm, which needs to be tuned for efficiency. However, Michalewicz [38] mentioned that the determination of proper values of these genetic operators still remains an art rather than science.