How Genetic Algorithms Work

    A genetic algorithm begins by creating an initial population of chromosomes that are given a random collection of genes. It then continues as follows:

    1. Create an initial population of chromosomes.

    2. Evaluate the fitness or “suitability” of each chromosome that makes up the population.

    3. Based on the fitness level of each chromosome, select the chromosomes that will mate, or those that have the “privilege” to mate.

    4. Crossover (or mate) the selected chromosomes and produce offspring.

    5. Randomly mutate some of the genes of the chromosomes.

    6. Repeat steps three through five until a new population is created.

    7. The algorithm ends when the best solution has not changed for a preset number of generations.

    Genetic algorithms strive to determine the optimal solution to a problem by utilizing three genetic operators. These operators are selection, crossover, and mutation. GAs search for the optimal solution until specific criteria are met and the process terminates. The results of the process include good solutions, as compared to one “optimal” solution, for complex problems (such as “NP-hard” problems). NP-hard refers to problems which cannot be solved in polynomial time. Most problems solved with computers today are not NP-hard and can be solved in polynomial time. A polynomial is a mathematical expression involving exponents and variables. A P-Problem, or polynomial problem, is a problem for which the number of steps to find the answer is bounded by a polynomial. An NP-hard problem does not increase exponentially, but often increases at a much greater rate, described by the factorial operator (n!). One example of an NP-hard problem is the traveling salesman problem, which will be discussed later in this chapter.

Initial Population

    To recap, the population of a genetic algorithm is comprised of organisms, each of which usually contains a single chromosome. Chromosomes are comprised of genes, and these genes are usually initialized to random values based on defined boundaries. Each chromosome represents one complete solution to the defined problem. The genetic algorithm must create the initial population, which is comprised of multiple chromosomes or solutions.

    Each chromosome in the initial population must be evaluated. This is done by evaluating its “fitness” or the quality of its solution. The fitness is determined through the use of a function specified for the problem the genetic algorithm is designed to solve.

Suitability and the Privilege to Mate

    In a genetic algorithm, mating is used to create a new and improved population. The “suitability” to mate refers to whether or not chromosomes are qualified to mate, or whether they have the “privilege” to mate.

    Determining the specific chromosomes that will mate is based upon each individual chromosome’s fitness. The chromosomes are selected from the old population, mated, and children are produced, which are new chromosomes. These new children are added to the existing population. The updated population is used for selection of chromosomes for the subsequent mating.

Mating

    We will now examine the crossover process used in genetic algorithms to accomplish mating. Mating is achieved by selecting two parents and taking a “splice” from each of their gene sequences. These splices effectively divide the chromosomes’ gene sequences into three parts. The children are then created based on genes from each of these three sections.

    The process of mating combines genes from two parents into new offspring chromosomes. This is useful in that it allows new chromosomes to inherit traits from each parent. However, this method can also lead to a problem in which no new genetic material is introduced into the population. To introduce new genetic material, the process of mutation is used.

Mutation

    Mutation is used to introduce new genetic material into a population. Mutation can be thought of as natural experiments. These experiments introduce a new, somewhat random, sequence of genes into a chromosome. It is completely unknown whether or not this mutation will produce a desirable attribute, and it does not really matter, since natural selection will determine the fate of the mutated chromosome.

    If the fitness of the mutated chromosome is higher than the general population, it will survive and likely be allowed to mate with other chromosomes. If the genetic mutation produces an undesirable feature, then natural selection will ensure that the chromosome does not live to mate.

    An important consideration for any genetic algorithm is the mutation level that will be used. The mutation level is generally expressed as a percentage. The example program that will be examined later in this chapter will use a mutation level of 10%. Selection of a mutation level has many ramifications. For example, if you choose a mutation level that is too high, you will be performing nothing more than a random search. There will be no adaptation; instead, a completely new solution will be tested until no better solution can be found.