Genetic algorithm to solve machine layout problem
John Holland invented genetic algorithm in the 1960s. Genetic algorithm is a meta-heuristic which is used to solve search and optimization problems. Genetic algorithm mimics the principle of natural genetics. Figure 1 presents the flow chart of genetic algorithm which can be used to solve machine layout problem.
Figure 1: Flow chart of genetic algorithm
Working procedure of genetic algorithm to solve machine layout problem is described as per the following.
1. Chromosome representation
We can use binary encoding, value encoding, permutation encoding, tree encoding and some other encodings to represent chromosomes. Permutation encoding is suited to represent chromosomes for machine layout problem.
2. Initial population
Initial population can be created randomly or using knowledge. Problem complexity and problem size can be taken into account while deciding size of initial population.
3. Fitness function
The fitness function is used to evaluate the goodness of the chromosomes. Generally equation of fitness function is designed using objective function. For maximization problem fitness function is directly proportional to objective function while minimization problem fitness function is inversely proportional to objective function.
4. Selection operator
Roulette wheel selection, Boltzman selection, tournament selection, elitism, rank selection, steady state selection and some other methods can be used to select the chromosomes into the mating pool. Rank selection which avoids premature convergence is suited for machine layout problem.
5. Crossover operator
Single point crossover, two point crossover, uniform crossover, order crossover and some others can be used to perform crossover operation on chromosomes. Appropriate crossover operator can be selected by taking problem and chromosome representation into account. Order crossover is appropriate for machine layout problem and permutation encoding of chromosomes.
6. Mutation operator
Bit-wise mutation, insert mutation, inversion mutation, scramble mutation, swap mutation and some others can be used to perform mutation operation on chromosomes. Appropriate mutation operator can be selected by taking problem and chromosome representation into account. Insert mutation, inversion mutation, scramble mutation, swap mutation can be used for machine layout problem and permutation encoding of chromosomes.
7. Stopping criteria
Stopping criteria of genetic algorithm depends on problem complexity and problem size. Sometimes hundred generations is enough, another time thousands of generations is not enough. Common stopping criteria are as per the following.
- Best fitness function value found in population has not improved in last t generations.
- Genetic algorithm converges.
- Fixed number of generations reached.
- A solution is found that satisfies minimum criteria.
- Allocated budget (computation time/money) reached.
- Manual inspection.
- Combinations of the above.
8. Parameters of genetic algorithm
Population size, stopping criteria, probability of crossover, probability of mutation and generation gap are the parameters of genetic algorithm. According to natural genetics, probability of crossover is ranged from 0.5 to 1, probability of mutation is ranged from 0.001 to 0.5 and probability of crossover is always greater than the probability of mutation.
The generation gap is defined as the proportion of chromosomes in the population which are replaced in each generation. Generation gap of 0.9 means that 90% chromosomes from old population is replaced by 90% best found chromosomes from new population while preserving 10% best found chromosomes from old population into new population.