|
The genetic algorithm is an artificial system based on biological evolutionary mechanisms. A modern biological evolutionary theory came into existence by incorporating genetics and population biology theory into the classical evolution theory. It can be defined as inheritable changes, via genetic materials in a population of chromosomes, from one generation to the next generation. The main goal of evolution is to produce a population of chromosomes with increasing fitness. The fitness is a quantitative measure of the success of a chromosome in survival and reproduction. The main processes of natural evolution are reproduction of some chromosomes within a population, mutation in the DNA sequences within a gene or chromosomes of an organism to create a new character not found in the parental type, and competition and fitness selection to limit expanding populations of different species in finite space.
The genetic algorithm is a search algorithm that operates on pieces of information. It is similar to a natural evolutionary process that operates on the information stored in genes. In the genetic algorithm, chromosomes are represented as binary strings; these strings are modified in the same way that population of chromosomes evolves in nature. The population of strings improves its fitness over interactions, and after a number of generations the population finally evolves to the best solution for a given problem. In each generation, all strings are evaluated by a fitness function for their performance. Based on these evaluations, a new population of strings, with well adapted effectiveness, is formed by using genetic operators such as selection, crossover, and mutation.
The genetic algorithm is a simple computational model compared to the natural mechanisms; however, complex and interesting structures have been developed using genetic algorithms. Most of the genetic algorithms consist of following steps:
-
- Encode the problem variables as a chromosome, representing a fixed-length binary string
- Choose a population size, N.
- Define a fitness function to measure the probability that a chromosome will be selected as a parent chromosome to further generate new chromosomes
- Randomly generate a population of chromosomes of size, N
- Test each chromosome in the population with the fitness function
- Perform the following sub-steps until termination condition such as specified best fitness values, is satisfied.
- Select a pair of chromosomes from the population with the higher fitness value as parent chromosomes for reproduction
- Apply the genetic operators to selected parent chromosomes to create a pair of offspring chromosomes
- Allow the offspring chromosomes and their parents to form the new population
- Replace the current chromosome population with the new population
- Calculate the fitness value of each chromosomes of the new population
- Output the optimal solutions to a given problem as the fittest chromosomes.
Genetic algorithm has the following advantages:
- A genetic algorithm is a parallel search, that is, in each generation several solutions are checked at once. It generates optimized and robust solutions via powerful operators; for example, bad solutions are filtered out by selection, and local optimal solutions can be avoided by mutation.
- A genetic algorithm can provide good solutions even if very little information about the problem is provided. As a result, genetic algorithms are widely used in classification and optimization.
However, there are few limitations with the genetic algorithms, as:
- Encoding a given problem in suitable representation (for example, bit string) is difficult and often changes the nature of the problem being investigated. Natural evolution does not always produce a good solution. It frequently converges to a local optimum.
- A genetic algorithm involves several parameters, such as representation, population size, and fitness function. In practice, it is difficult to define or create these parameters due to the lack of guidelines for choosing them.
The genetic algorithm has been successfully applied for solving many practical problems in many disciplines, in particular, in bioinformatics. Genetic algorithms have been used to solve multiple sequence alignment problems.
|
