Computational Intelligence. Genetic Algorithms

Genetic Algorithms. Genetic algorithms were proposed by Holland as a search mechanism in artificially adaptive populations. A genetic algorithm (GA) is a problem-solving method that simulates Darwinian evolutionary processes and naturally occurring genetic operations on chromosomes (39). In nature, a chromosome is a thread-like linear strand of DNA and associated proteins in the nucleus of animal and plant cells.

A chromosome carries genes and serves as a vehicle in transmitting hereditary information. A gene is a hereditary unit that occupies a specific location on a chromosome and that determines a particular trait in an organism. Genes can undergo mutation (alteration or structural change). A consequence of the mutation of genes is the creation of a new trait in an organism. In genetic algorithms, the traits of artificial life forms are stored in bit strings that mimic chromosome strings found in nature.

The traits of individuals in a population are represented by a set of evolving chromosomes. A GA transforms a set of chromosomes to obtain the next generation of an evolving population. Such transformations are the result of applying operations, such as reproduction based on survival of the fittest, and genetic operations, such as sexual recombination (also called crossover) and mutation.

Each artificial chromosome has an associated fitness, which is measured with a fitness function. The simplest form of fitness function is known as raw fitness, which is some form of performance score (e.g., number of pieces of food found, amount of energy consumed, or number of other life forms found). Each chromosome is assigned a probability of reproduction that is proportional to its fitness. In a Darwinian system, natural selection controls evolution.

Consider, for example, a collection of artificial life forms with behaviors resembling ants. Fitness will be quantified relative to the total number of pieces of food found and eaten (partially eaten food is counted). Reproduction consists in selecting the fittest individual x and the weakest individual y in a population and replacingy with a copy of x.

After reproduction, a population will then have two copies of the fittest individual. A crossover operation consists in exchanging genetic coding (bit values of one or more genes) in two different chromosomes. The steps in a crossover operation are as follows: (1) Randomly select a location (also called the interstitial location) between two bits in a chromosome string to form two fragments, (2) select two parents (chromosomes to be crossed), and (3) interchange the chromosome fragments. Because of the complexity of traits represented by a gene, substrings of bits in a chromosome are used to represent a trait.

The evolution of a population resulting from the application of genetic operations results in changing the fitness of individual population members. A principal goal of GAs is to derive a population with optimal fitness.

The pioneering works of Holland and Fogel et al. gave birth to the new paradigm of population-driven computing (evolutionary computation) resulting in structural and parametric optimization. Evolutionary programming was introduced by Fogel in the 1960s. The evolution of competing algorithms defines evolutionary programming.

Each algorithm operates on a sequence of symbols to produce an output symbol that is likely to maximize an algorithm’s performance relative to a well-defined payoff function. Evolutionary programming is the precursor of genetic programming. In genetic programming, large populations of computer programs are bred genetically. One may also refer to biologically inspired optimization, such as particle swarm optimization (PSO), ant colonies, and others.