1. Introduction
Optimization refers to finding feasible solutions which correspond to extreme values of one or more objectives. The optimization methods are of great importance in practice, particularly in engineering design, scientific experiments and business decision-making. The difficulties associated with using mathematical optimization on large-scale engineering problems have contributed to the development of alternative solutions based on heuristics and natural or physical principles.
Evolutionary algorithms are one example of such algorithms. Evolutionary algorithms (EAs) are stochastic search methods that mimic the metaphor of natural biological evolution and/or the social behavior of species. Examples include Genetic Algorithms (GA), Memetic Algorithms, Ant Colony Optimisation (ACO), Particle Swarm Optimisation (PSO), and Shuffled Frog Leaping (SFL) Algorithms. These algorithms are guided by interaction, learning, adaptation, and evolution.
2. Genetic Algorithms
The first evolutionary-based technique introduced in the literature was the genetic algorithms which were developed based on the Darwinian principle of the ‘survival of the fittest’ and the natural process of evolution through reproduction. Genetic algorithms (GAs) were invented by John Holland in the 1960s. The fitness of an organism is typically defied as the probability that the organism will live to reproduce. Genetic algorithm requires the natural parameter set of the optimization problem to be coded as a finite length string similar to chromosome. They are unconstrained by the limitations of other methods (continuity, derivative existence, unimodality and so on).
The procedure for GA starts with representation of solutions, in the form of an encoded string (analogous to chromosome) that hold a set of values for the optimization variables. GAs work with a random population of solutions (chromosomes). The fitness of each chromosome is determined by evaluating it against the objective function. The natural paradigm of survival of the fittest is used to screen the population and the best solutions are allowed to exchange information (through crossover or mutation) to produce offspring solutions, the probability of selection being an increasing function of fitness. The offspring solutions are then evaluated and allowed to evolve. Usually, the process is continued for a large number of generations (50 to 500 or more generations).
The basic genetic operators are Selection, Cross over and mutation. The purpose of selection is, to emphasize the fitter individuals in the population in hopes that their offspring will in turn have even higher fitness. The Crossover operator roughly mimics biological recombination between two single-chromosome organisms. There is every likelihood of the offspring having the traits of both parents. Crossover among parent chromosomes is a common natural process and traditionally is given a probability that ranges from 0.6 to 1.0. The mutation is used to maintain diversity in the population, wherein a single chromosome is modified. As opposed to crossover, mutation is a rare process and a mutation rate less than 0.1 is usually used The parameters for GA are the population size, number of generations, probability of cross-over and probability of mutation.
3. Memetic Algorithms
Memetic Algorithms(MAs) are inspired by Dawkins’ notion of a meme. The term MAs is used to describe GAs that heavily use local search. MAs are similar to GAs but the elements that form a chromosome are called memes, not genes. The unique aspect of the MAs algorithm is that all chromosomes and offsprings are allowed to gain some experience, through a local search, before being involved in the evolutionary process.
After creating a random initial population, a local search is performed on each population member to improve its experience and thus obtain a population of local optimum solutions. Then, crossover and mutation operators are applied, to produce offsprings. These offsprings are then subjected to the local search so that local optimality is always maintained. A pair- wise interchange heuristic can be used to perform local search. In this method, the local-search neighborhood is defined as the set of all solutions that can be reached from the current solution by swapping two elements (memes) in the chromosome. The parameters involved in MAs are population size, number of generations, crossover rate, and mutation rate in addition to a local-search mechanism.
4. Ant Colony Optimization
Real ants are capable of finding the shortest path from a food source to the nest without using visual cues and also they are capable of adapting to changes in the environment (finding a new shortest path once the old one is no longer feasible due to a new obstacle).
Ants coordinate their activities via stigmergy, a form of indirect communication mediated by modifications to the environment. The primary means for ants to form and maintain a route is a pheromone trail. It is inferred that ants deposit a certain amount of pheromone while walking and each ant probabilistically prefers to follow a direction rich in pheromone. Although all ants move at approximately the same speed and deposit pheromone at approximately at the same rate, the pheromone trail ac*****ulates quicker on the shorter paths. Although a single ant is in principle capable of building a solution, it is only the colony of ants which presents the shortest path finding behaviour.
The Ant Colony Optimization metaheuristic was developed by Dorigo, Di Caro and Gambardella, as a multi-agent approach to difficult classical NP-hard combinatorial optimization problems like the traveling salesman problem (TSP) and the quadratic assignment problem (QAP). In the ant colony optimization (ACO) a colony of artificial ants cooperate in finding good solutions to difficult optimization problems. Autocatalysis plays an important role in ACO algorithms functioning (the more ants choose a move, the more the move is rewarded, by adding pheromone, and the more interesting it becomes for the next ants). In general, the amount of pheromone deposited is made proportional to the goodness of the solution an ant has built (or is building). Usually, in ACO algorithms an evaporation mechanism, similar to real pheromone evaporation, modifies pheromone information over a period of time which allows the ant colony to slowly forget its past history so that it can direct its search towards new directions without being over-constrained by past decisions. A solution is expressed as a minimum cost (shortest) path through the states of the problem in accordance with the problem’s constraints. The key to the application of ACO to a new problem is to identify an appropriate representation for the problem (to be represented as a graph searched by many artificial ants), and an appropriate heuristic that defines the distance between any two nodes of the graph. ACO algorithms, as a consequence of their concurrent and adaptive nature, are particularly suitable for distributed stochastic problems such as communications or transportation networks.
5. Particle Swarm Optimization
The PSO was developed by Kennedy and Eberhart [8] in 1995, inspired by the social behavior of a flock of migrating birds trying to reach an unknown destination. Physically, this mimics a flock of birds that communicate together as they fly. Each bird looks in a specific direction, and then when communicating together, they identify the bird that is in the best location. Accordingly, each bird speeds towards the best bird using a velocity that depends on its current position. Each bird, then, investigates the search space from its new local position, and the process repeats until the flock reaches a desired destination. It is important to note that the process involves both social interaction and intelligence so that birds learn from their own experience (local search) and also from the experience of others around them (global search).
The PSO is an algorithm for finding optimal regions of complex search spaces through interaction of individuals in a population of particles. In PSO, each solution is a ‘bird’ in the flock and is referred to as a ‘particle’. The particles in the population have positions and velocities assigned to them. The process is initialized with a group of random particles (solutions), N . The position (Pg) of the best particle (g) is calculated as the best fitness of all particles, the best position of each particle is also known. In each iteration, the best solution of the current population is calculated (pg). The movement of each bird is influenced by three factors. Firstly the previous history of velocities (inertia), secondly cognition or the private thinking of the particle when comparing its current position to its own best (self confidence), and finally the knowledge of the best ever position in the swarm (swarm confidence). Relative importance given to each of this will decide the updated position of the particle in an iteration. The main parameters used in the PSO technique are: the population size (number of birds); number of generation cycles, inertia weight, self confidence factor, and swarm confidence factor.
6. Shuffled Frog Leaping Algorithm
The SFL algorithm, combines the benefits of the genetic-based MAs and the social behavior-based PSO algorithms. In the SFL, the population consists of a set of frogs (solutions) that is partitioned into subsets referred to as memeplexes. The different memeplexes are considered as different cultures of frogs, each performing a local search. Within each memeplex, the individual frogs hold ideas, that can be influenced by the ideas of other frogs, and evolve through a process of memetic evolution. After a defined number of memetic evolution steps, ideas are passed among memeplexes in a shuffling process. The local search and the shuffling processes continue until defined convergence criteria are satisfied.
An initial population of P frogs is created randomly. For S-dimensional problems (S variables), a frog i is represented as XiZ(xi1, xi2,., xiS). Afterwards, the frogs are sorted in a descending order according to their fitness. Then, the entire population is divided into m memeplexes, each containing n frogs. In this process, the first frog goes to the first memeplex, the second frog goes to the second memeplex, frog m goes to the mth memeplex, and frog m+1 goes back to the first memeplex, etc. Within each memeplex, the frogs with the best and the worst fitnesses are identified as Xb and Xw, respectively. Also, the frog with the global best fitness is identified as Xg. Then, a process similar to PSO is applied to improve only the frog with the worst fitness (not all frogs) in each cycle. Accordingly, the position of the frog with the worst fitness is adjusted and the resulting frog replaces the worst frog, if it produces a better solution. If no improvement becomes possible in this case, then a new solution is randomly generated to replace that frog. The calculations then continue for a specific number of iterations. Accordingly, the main parameters of SFL are: number of frogs P; number of memeplexes; number of generation for each memeplex before shuffling; number of shuffling iterations; and maximum step size.
References
1. Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization & Machine Learning. Pearson Education. Singapore
2. Dawkins R. The selfish gene. Oxford: Oxford University Press; 1976.
3. Dorigo, M., Maniezzo, V., & Colorini, A. (1996). The ant system: optimization by a colony of coorporating agents.
IEEE Trans. on Systems, Man and Cybernetics-Part B, 26, No:1, 1-13
4. Kennedy J, Eberhart R. Particle swarm optimization.
Proceedings of the IEEE Int. conf. on neural networks (Perth, Australia), 1942–1948.
Piscataway, NJ: IEEE Service Center; 1995.
5. Eusuff MM, Lansey KE. Optimization of water distribution network design using the shuffled frog leaping algorithm.
J Water Resour Plan Manage 2003;129(3):210–25.
6. Elbeltagi, E., Hegazy, T., & Grierson, D. (2005).
Comparison among five evolutionary - based optimization algorithms. Advanced Engineering Informatics, 19, 43-53.
Note: By B.Anil,Professor,Mechanical Engineering
This article was published in CET College Magazine 2007.
