We would examine the basics of Genetic Algorithm and dive a little deeper into the actual steps in genetics algorithm. I will try to be clear and also explain the any term I use clearly.
We would cover the following topics:
- Introduction of Genetic Algorithm
- How Genetic Algorithm Works
- Motivation for Genetic Algorithm
- Phases in Genetic Algorithm
1. Introduction of Genetic Algorithm
Genetic Algorithm(GA) is a class of random-based classical algorithms based on Charlse Darwin’s theory of evolution. It is also regarded as a process of solving optimization problems by method of natural selection. It is yet another human’s desperate attempt to mimic what is thought to happen in nature. It answers questions like:
- Why do some organisms die off while some live on?
- Why are there more women than men in certain places?
- Why do certain plants thrive in certain region, but don’t survive in other region
- Why is there difference in the population of various living things
It then appears that there is something about living things, deep in their genes that could explain this. Some kind of biological process (algorithm) that explains this. Genetic Algorithm tend to explain the concept of ‘survival of the fittest’ in a formal and systematic way.
2. How Genetic Algorithm Works
Just a mentioned before, Genetic Algorithm works by the process of natural selection. It starts from an initial, maybe random population (which represent a pool of all possible solutions to a problem). Then these population undergoes several processed such as Selection, Cross-Over and Mutation and finally produces the best results (optimal solution) at the end of the process.
3. Motivation for Genetic Algorithm
By application of Genetic Algorithms, we are able to find optimal solutions to difficult problems. How? In the field of Artificial Intelligence and Machine Learning, there seems to be problem that does not have an exact solution, a class of optimization problems. Attempt to find exact solution would require time as well as much complexity that exceeds the current available computing systems. But by applying GA, the problems can then be solved or optimized and in lesser time. The motivation for GA can be classified into three:
- Solving Difficult Problems
- Alternative to Gradient-Based Methods
- Speed of Convergence
4. Phases in Genetic Algorithm
Genetic Algorithm proceeds from an initial population through several phases till the termination when the optimal solution have been deduced. Let’s now examine the different phases of Genetic algorithm.
a. Initial Population
This is the first phase of the process where an initial population is selected. The initial population is simply a set of individuals which are potential solution to the problem we want to solve. It could actually be made of of thousands or even hundreds of thousands of individuals that may have been randomly selected or selected based on some specified criteria. The two methods of initializing the population are summarized as:
- Random Initialization: selection is made randomly
- Heuristic Initialization: based on some rules
b. Fitness Function Definition
This phase could also be regarded as part of the Initial phase (Initial Population) and it could also be part of the Selection phase. This is a way of specifying the criteria for the ‘goodness’ of a given solution compared to others and to the problem being solved. Based on the fitness, members of the population are separated into two parts: those that are fit enough to be selected into the next generation and those that would be dropped.
One approach to this is to have a fitness score for each individual in the population. So when this score is passed into the fitness function, it returns either 1(pass) or 0 (fail).
Selection is simple the process of selecting the portion of the population that would pass into the next generation. The selection process is based on the fitness criteria from the preceding phase. Two pairs of individual members of the population are selected (like parents) based on their fitness. These parents would be used to produced individual for the next generation. In this way we are sure that the parents would pass on their ‘genes’ to the next generation
Cross-over is the most noteworthy of the phases of genetic algorithm. This is also called recombination. It is a genetic operator that determines what information is passed from the the two parents to the new offspring. This is illustrated below in Figure 1.1:
Cross-over point is the point in within the genes of the parents at which the cross-over occurs.
Mutation is a random change in the chromosome of the new offspring. This change occurs with a little probability. The benefit of this phase is that if tends to prevent the algorithm from converging in a local minimum. To do this, a mutation rate is carefully chosen. This is illustrated in Figure 1.2
After a number of iterations through the phases of the algorithm, the process terminates based on certain defined termination criteria. At this stage the optimal solution is reached. Some of the possible termination conditions include:
- there is no further improvements
- given number of generations is reached
- objective function reaches minimum value
5. Application Areas of Genetic Algorithm
Genetic Algorithm is used in many areas same as Neural Network, Fuzzy Logic etc. Some of the application areas of GA include:
- Image Processing & Recognition: GA is applied in digital image processing and recognition. This if further applied in pattern matching, image compression and reconstruction
- Optimization Problem Solving: This is the most common application of genetic algorithm. It can be applied to find optimal solution to certain problems that can be represented as a cost or objective function.
- DNA Analysis: Genetic Algorithms have been applied to create DNA profiles using spectrometric data from DNA samples
- Neural Network: Training of neural network require an iterative process of reducing particular error quantity untill it reaches a minimum value. GA is applied here.
6. The Actual Algorithm (Simplified)
Now, I’m going to present a simplified form of the high-level view of the genetic algorithm. This algorithm is given below in Listing 1.0. We consider the implementation of the generalized algorithm (more detailed) in a different lesson
Listing 1.0: Simplified Genetic Algorithm
7. Advantages of Genetic Algorithms
Some of the advantages of GA includes:
Can be applied to both continuous and discreet function
Can be applied in multi-objective problems
Very efficient in terms of time and space complexity
Provides improved solution over time
Can be applied when the search space is very large and involved many parameters
Requires no derivative information