Introduction

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:

  1. exploitation -
    Selection and crossover tend to converge on a good but sub-optimal solution.
  2. exploration -
    Selection and mutation create a parallel, noise-tolerant, hill climbing algorithm, preventing a premature convergence.

For details of Genetic Algorithm, please refer to my partner's first article in GA Project.


Applications

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:

encoding of candidate structures (solutions)
method of evaluating the relative performance of candidate structure, for identifying the better solutions
Genetic Algorithm codes parameters of the search space as binary strings of fixed length. It employs a population of strings initialized at random, which evolve to the next generation by genetic operators such as selection, crossover and mutation. The fitness function evaluates the quality of solutions coded by strings. Selection allows strings with higher fitness to appear with higher probability in the next generation. Crossover combines two parents by exchanging parts of their strings, starting from a randomly chosen crossover point. This leads to new solutions inheriting desirable qualities from both parents. Mutation flips single bits in a string, which prevents the GA from premature convergence, by exploiting new regions in the search space. GA tends to take advantage of the fittest solutions by giving them greater weight, and concentrating the search in the regions which lead to fitter structures, and hence better solutions of the 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.

Genetic Algorithm is applicable in many ways:

  1. State Assignment Problem
  2. Economics
  3. Scheduling
  4. Computter-Aided Design

State Assignment Problem

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:

  1. the algorithm scales poorly as the number of cities increases - time complexity
  2. the solution quality degrades rapidly

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]

Interesting Stuff

Here is the on-line Traveling Salesman Solver.


Economics

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.


Scheduling

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:

  1. A tank which requires urgent maintenance is checked early in the schedule (very good).
  2. A tank or pipeline requiring a periodic maintenance or inspection is included in the schedule (good), given higher priority to the first case.
  3. Because of several tanks in one location being out of service simultaneously, the capacity of that location for a certain time drops significantly (very bad).
  4. Some inspectors have more work to do than the others in the same area (bad).

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.


Computer-Aided Design

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.


References

  1. [Valenzuela 1995] Evolutionary Divide and Conquer: a novel genetic approach to the TSP, by Christine L. Valenzuela, in 28 June 1995. Unpublished Thesis.
  2. [Chughtai 1995] Determining Economic Equilibria using Genetic Algorithms, by Meliha Chughtai, in September 1995. Unpublished Thesis.