Understanding Genetic Algorithms

Understanding Genes

In a genetic algorithm genes represent individual components of a solution. This is a very important part of the analysis of a problem that is to be used with a genetic algorithm. To effectively solve a problem you must determine a way to break the problem into related components, or genes.

Later in this chapter we will examine the traveling salesmen problem. You will be shown how to break up the solution to this problem into individual genes. Additionally, in Chapter 10 you will be shown how you can make the individual weights in a neural network represent the genes in the chromosome.

It is also important to note that there is a finite number of genes in that are used. Individual genes are not modified as the organisms evolve. It is the chromosomes that evolve by changing the order and makeup of their genes. Now that you understand genes and chromosomes we will examine how the genetic algorithm works.

How Genetic Algorithms Work

Now that you understand the structure of a genetic algorithm, we will proceed to discuss how genetic algorithms actually work. A genetic algorithm begins by creating an initial population. This population consists of chromosomes that are given a random collection of genes. The steps involved in a genetic algorithm are as follows.

1. Create an initial population of chromosomes

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

3. Based on this fitness, select the chromosomes that will mate or those that have the “privilege” to mate

4. Cross over 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

The steps listed above will be discussed in more detail in the following sections. Genetic algorithms strive to determine the optimal solution to a problem by utilizing three genetic operators. These operators are selection, cross over, and mutation. GAs’ search for the optimal solution until specific criteria is met causing termination. These results include providing good solutions as compared to one “optimal” solution for complex (such as “NP hard”) problems. NP-hard defers to a problem 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 P-problem, or polynomial problem is a problem where the number of steps to complete the answer is bounded by a polynomial. A polynomial is a mathematical expression involving exponents and expressions. A NP-hard problem does not increase exponentially. An NP-hard problem often increases at a much greater rate, often described by the factorial operator (n!). One example of an NP-hard problem is the traveling salesman problem. The traveling salesman problem will be discussed later in this chapter.

Initial Population

In a genetic algorithm the population is comprised of organisms. Each of these organisms is usually composed of a single chromosome. 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. Chromosomes are comprised of genes and these genes are usually initialized to random values based on the boundaries defined.

Each chromosome in the initial population must be evaluated. This is done by evaluating the “fitness” of each chromosome and represents the quality of the solution. The fitness is determined by a function and is specific to the defined problem the genetic algorithm is designed to solve.

Suitability and the Privilege to Mate

The purpose of mating in a genetic algorithm is to create a new improved population. The “suitability” to mate refers to how we determine those chromosomes that are qualified to mate or those that have the “privilege” to mate.

Determining the specific chromosomes that will mate is based upon each individuals chromosomes fitness. The chromosomes are selected from the old population, mate, and produce children or new chromosomes. These new children are joined with the existing population. In subsequent generations this combined will be the basis for selection of the mating population.

Mating

We will now examine the crossover process that allows genetic algorithms to mate. Mating works by taking two parents and taking a "splice" from their gene sequence. This splice effectively divides the chromosome into three gene sequences. The children will be built based on genes from each of these three sections.

The process of mating simply jumbles the genes from two parents into a new offspring chromosome. This is useful in that it allows the new chromosomes to take traits from each parent. This method can also lead to the problem of no new genetic material being introduced. To introduce new genetic material, the process of mutation is used. Mutation will be discussed in the next section.

Mutation

Without mutation the only genetic material that will be used is that which comes from the parents. Mutation allows new genetic patterns to be introduced that were not already contained in the population. This 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 if this mutation will produce a desirable or undesirable attribute.

It does not matter if the mutation produces desirable or undesirable feature. 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 a 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 percent. The example program that will be examined later in this chapter will use a mutation level of 10%. There are many ramifications that are directly tied to this mutation level. If you choose two high of a mutation level, you will be performing nothing more than a random search. There will be no adaptation; simply a completely new solution will be tried until no better solution can be found. Now that you understand the general structure of a genetic algorithm we will examine a common problem that genetic algorithms are often applied to. In the next section you will be introduced to the traveling salesmen problem.