Introduction to Genetic Algorithm

What is Optimization?

• Making something better.
• Increase efficiency.

Optimization problem

• A problem in which we have to find the values of inputs (also called solutions or decision variables) from all possible inputs in such a way that we get the “best” output values.
• Definition of “best”- Finding the values of inputs that result in a maximum or minimum of a function called the objective function.
• There can be multiple objective functions as well (depends on the problem).

Optimization algorithm

An algorithm used to solve an optimization problem is called an optimization algorithm.

Evolutionary Algorithms

Algorithms that simulate physical and/or biological behavior in nature to solve optimization problems.

Genetic Algorithm (GA)

• It is a subset of evolutionary algorithms that simulates/models Genetics and Evolution (biological behavior) to optimize a highly complex function.
• A highly complex function can be:
  1. Very difficult to model mathematically.
  2. Computationally expensive to solve. Eg. NP-hard problems.
  3. Involves a large number of parameters.

Background of GA

• Introduced by Prof. John Holland in 1965.
• The first article on GA was published in 1975.
• GA is based on two fundamental biological processes:
  1. Genetics (by G.J. Mendel in 1865): It is the branch of biology that deals with the study of genes, gene variation, and heredity.
  2. Evolution (by C. Darwin in 1875): It is the process by which the population of organisms changes over generations.

Q. So what’s the relation between genetics and evolution ??
Ans. Gene variation → changes in population

Natural selection in Evolution

1. A population of individuals exists in an environment with limited resources.
2. Competition for those resources causes the selection of those fitter individuals that are better adapted to the environment.
3. These individuals act as seeds for the generation of new individuals through recombination and mutation.
4. Evolved new individuals act as initial population and Steps 1 to 3 are repeated.

Over time Natural selection causes a rise in the fitness of the population.

“Select The Best, Discard The Rest”

Example: Giraffes have long necks

1. In earlier days, some giraffes had short necks whereas some had slightly longer necks.
2. Giraffes with sightly longer necks could feed on leaves of higher branches when all lower ones had been eaten off. Hence, they had a better chance of survival.
3. Favorable characteristics propagated through generations of giraffes.
4. Now, evolved species have long necks.

Nature-GA Analogy

Structure of GA

GA vs Traditional Algorithms

¹ GA deals with a coded form of the function values (parameter set), rather than with the actual values themselves. So, for example, if we want to find the maximum of a function f(x1, x2) of two variables, the GA would not deal directly with x1 or x2 values, but with strings that encode these values.

² GA uses a population of points to search, not just a single point on the problem space. This gives GA the power to search noisy spaces littered with local optimum points. Instead of relying on a single point to search through space, the GA looks at many different areas of the problem space at once and uses all of this information to guide it.

³ GA uses only payoff information to guide themselves through the problem space. Many search techniques need a variety of information to guide themselves. Hill climbing methods require derivatives, for example. The only information a GA needs is some measure of fitness about a point in the space (sometimes known as an objective function value). Once the GA knows the current measure of “goodness” about a point, it can use this to continue searching for the optimum.

⁴ GA is probabilistic in nature, not deterministic. This is a direct result of the randomization techniques used by GA. Probabilistic — random population with random mating, cross-over, and mutation.

Applications of GA

1. Acoustics

• Distinguish between sonar reflections and different types of objects.
• Design Active noise control systems which cancel out the undesired sound by producing sound waves that destructively interfere with the unwanted noise.

2. Aerospace Engineering

Design Super Sonic aircraft by minimizing aerodynamic drag at supersonic cruising speeds, minimizing drag at subsonic speeds, and minimizing aerodynamic load.

3. Financial Markets

To predict the future performance of publicly traded stocks.

4. Geophysics

Locate earthquake hypocenters based on seismological data.

5. Materials Engineering

• Design electrically conductive carbon-based polymers known as polyanilines.
• Design exposure pattern for an electron lithography beam.

6. Routing and Scheduling

Find optimal routing paths in telecommunication networks that are used to relay data from sender to recipients.

7. Systems Engineering

To perform the multi-objective task of designing wind turbines used to generate electric power.

Problems with GA

1. Population Selection Problem

Defining the population size and selecting the initial individuals can be a bit challenging.

2. Defining Fitness Function

To find out the optimal minimum or maximum value, we must define our fitness function in such a way so that optimal solution fitness can increase with every iteration.

3. Premature or rapid convergence of GA

• Rapid convergence is a very common as well as very general problem in GA. It occurs because the fitness function changes its value rapidly, resulting in a premature convergence.
• There are several methods to modify our fitness function in such a way so that convergence occurs slowly which will allow enough time for GA to search in the whole space and find the global optima. Three ways are defined below:
  1. F’ = a*F + b
  F = normal fitness value of the population string.
  a = small number
  b = relatively larger number
  Now it can be clearly seen that even if F rapidly increases then after F’ will increase slowly.
  2. F’ = a*(F^k)
  k = constant number in (0,1)
  So even if F increases rapidly it may not create rapid convergence.
  3. F’ = a*(F^k)
  k = func(t) , t is generation
  Here fitness function is modified in each generation.

4. Convergence to Local Optima

• Another important problem is that most of the time GA converges to local optima. We may think that we have found the optimal solution but actually, we didn’t.
• Now, it is important to note that GA’s ability to find the optimal solution lies in the hand of the user. An optimal solution will be achieved only if the programmer has written the code so that GA can search over the whole space to find the optimal solution. So what we should do in such a case is that we should modify our crossover and mutation function because they are responsible for changing the population in each iteration.

That will be it for this article.

Don’t forget to 👏 if you liked the article.

If you want to learn more about GA, check out my series of articles:

Genetic Algorithm (GA) series

If you have any questions or would like something clarified, you can find me on LinkedIn.

~happy learning.