Genetic Algorithm (GA) is an artificial intelligence procedure. It is based on the theory of natural selection and evolution.
This search algorithm balances the need for:
For details of Genetic Algorithm, please refer to my partner's first article in GA Project.
Traditional methods of search and optimization are too slow in finding a solution in a very complex search space, even implemented in supercomputers. Genetic Algorithm is a robust search method requiring little information to search effectively in a large or poorly-understood search space. In particular a genetic search progress through a population of points in contrast to the single point of focus of most search algorithms. Moreover, it is useful in the very tricky area of nonlinear problems. Its intrinsic parallelism (in evaluation functions, selections and so on) allows the uses of distributed processing machines.
Basically, Genetic Algorithm requires two elements for a given problem:
Finding good parameter settings that work for a particular problem is not a trivial task. The critical factors are to determine robust parameter settings for population size, encoding, selection criteria, genetic operator probabilities and evaluation (fitness) normalization techniques.
Coding the solutions is based on the principle of meaningful building blocks and the principle of minimal alphabets, by using the binary strings.
The fitter member will have a greater chance of reproducing. The members with lower fitness are replaced by the offspring. Thus in successive generations, the members on average are fitter as solutions to the problem.
Too high mutation introduces too much diversity and takes longer time to get the optimal solution. Too low mutation tends to miss some near-optimal points. Two point crossover is quicker to get the same results and retain the solutions much longer than one point crossover.
The fitness function links the Genetic Algorithm to the problem to be solved. The assigned fitness is used to calculate the selection probabilities for choosing parents, for determining which member will be replaced by which child.
Genetic Algorithm is applicable in many ways:
This State Assignment Problem (SAP) belongs to a broader class of combinatorial optimization problems, including the Traveling Salesman Problem (TSP). The aim is to find the best state assignment for implementing a synchronous sequential circuit which is crucial for reducing silicon area or chip count in many digital designs. In TSP, it is to find the optimal routine for visiting all cities.
The mutation operator allows a highly parallel local search, while crossover allows members of the population to share information. Thus in TSP, the genetic search (hopefully) benefits from the good sub-tours from different members.
However, this approach with permutation crossovers suffers in two aspects:
To overcome these problems, a new approach, called Evolutionary Divide and Conquer (EDAC) uses Genetic Algorithm to explore the space of problem subdivisions in the range 500 - 5000 cities rather than the space of solutions themselves. The sub-tours are then patched together to form a global tour. More sophisticated algorithms, such as iterated Lin-Kernighan are developed for solving large Traveling Salesman Problems. [Valenzuela 1995]
Here is the on-line Traveling Salesman Solver.
Genetic Algorithm is applied in game theory to find equilibrium points in non-zero sum and non-cooperative situations, and in the game of iterated prisoner's dilemma to explore the possibility of evolving cooperative behaviour. [Chughtai 1995]
Game theory is the study of multi-person decision problems. In economics, it is relevant to oligopoly because each rival player has to consider what the others will do. All players are rational and choose their strategy in order to maximise their reward. In order for Genetic Algorithm to identify multiple equilibrium points, sharing is implemented:- to reduce the fitness of a member by a factor in relation to the number of other members in its proximity. This results in a promotional increase in the fitness of strings in areas of lower member clustering.
In prisoner's dilemma, players tend to defect to improve their own payoff rather than cooperate. The tit-for-tat strategy proves to be the best. For cooperation to evolve in the long run, it is important for the same players to meet repeatedly and to learn to cooperate.
Genetic Algorithm is used for inspection and repair of oil tanks and pipelines. The implementation is built on Peter Ross' PGA testbed and the data is taken from the Expert Systems for the Inspection of Tanks and Pipelins SITA and SIGO. The fitness function evaluates the constraints: level of production, condition and location of installations, type of products, human resources, the dates and costs of inspection and repairs. A good inspection schedule for oil installations is constructed. A good schedule ensures that repair times are kept to a minimum and faults are found before they become too serious. An automatic way of assigning maintenance activities to inspectors is devised in such a way as to minimize the loss in capacity, while keeping within resource constraints.
The schedule is evaluated taking into account the following priorities:
The application distributes the repairs such that the available capacity is always larger than the required minimum, then the production is not affected. Moreover, the assignment of activities is appropriate, it reduces the cost of unbalanced distribution. A robust schedule of activities is obtained.
Genetic Algorithm uses the feedback from the evaluation process to select the fitter designs, generating new designs through the recombination of parts of the selected designs. Eventually, a population of high performance designs are resulted.