Genetic
Algorithms
Sources:
1) Source #1: The
original source for Problem #1. The description below is a modified version.
2) Source #2 :
Roulette-wheel illustration.
3) Source #3:
Illustration of how mutation is able to solve the local maximum problem
Problem #1:
Let’s say we
would like to solve the following equation:
· a + 2 * b + 3 * c + 4 * d =
30
Such
that, 1 <= a, b, c, d <=21
Since we
have one equation and four unknowns, we are unable to utilize any of the
mathematical or conventional algorithmic techniques to solve the above
equation. In instances like this, we will employ the principles of evolutionary
biology to solve the problem.
Definition: A genetic
algorithm is an algorithmic technique that utilizes the principles of fitness,
selection, crossover and mutation from evolutionary biology to solve problems
that may be intractable if we simply employ the conventional algorithmic
techniques.
Examples of conventional
algorithmic techniques:
· Greedy strategy in computing
Minimum Spanning Trees using the Prim’s Algorithm (Refer to the unit on Undirected Graphs)
· A combination of greedy strategy
and dynamic programming in Dijkstra’s algorithm (Refer to the unit on Undirected
Graphs)
· Divide and conquer in merge
sort (Refer to the unit on Merge Sort)
NOTE: In the description below, I have
deliberately avoided terms like chromosomes, genes and DNA. If you wish to
learn more about these terms and Darwin’s theory of natural selection (with
random mutation), I suggest you refer to an introductory textbook in
Evolutionary Biology.
Before we
describe the particular steps of our genetic algorithm to solve Problem #1, I
will describe the generic steps that are a part and parcel of every genetic
algorithm as below:
1)
Generate the
members of the initial population. These members are typically randomly
generated.
2)
Evaluate the
fitness for each member. A fitness function is used to evaluate the fitness for
each member.
3)
Select the
members with the best fitness as candidates for crossover (or mating). A
selection function is utilized to select the best-fit members.
4)
Implement
the crossover process to produce a new population. A crossover function is
utilized to generate the new population.
5)
Randomly
mutate a small number of members from the new population. A mutation function
is employed.
6)
Check if any
member of the new population is an acceptable solution to the problem:
a.
If no,
utilize the new population as the initial population in Step 1) and repeat the
process.
b.
If yes,
print the member as the solution and terminate the algorithm.
A single run
from Steps 1) through 5) is called a generation. The genetic algorithm will run
through lots of generations until an accurate (or approximate as defined by the
error you are willing to tolerate) solution is found.
If the
methods for fitness, selection and crossover are designed optimally, the newer
populations will have the patterns of the best-fit members of the previous
generations and the least-fit members would be eliminated from successive
generations (Steps 2 through 4). Why is
the random mutation being performed on an already fit population in Step
#5? Observe the graph in the link below:
· Genetic Mutation:
Local Maximums
As you can
see in the above link, if there was no random mutation and we simply found the
most optimal solution for the problem, we would be stuck at the local maximum
(Point A). Instead, when we reach the local maximum, if we change our direction
slightly around the peak (random mutation), and run our genetic
algorithm further, we would be able to compute the global maximum (Point B).
Problem #1 - Rewriting the
Equation:
· selection = Math.abs
(a + 2 * b + 3 * c + 4 * d – 30)
In each
generation of our genetic algorithm, we will find values for a, b, c and d such
that resulting value of selection is
minimized. For this purpose, we will define our fitness function as below:
· fitness = (1/(1+selection))
Hence, lower
values for selection will yield
higher values for fitness. This will
enable us to select the best-fit members (explained below in pseudocode). We add a 1 to selection to avoid the scenario of a 1/0 when the value of selection is 0.
Programs for Problem #1:
1)
The program,
“Chromosome.java” implements a member of the population. Each member will be
defined by an array list (of type integer) that will store the value of its
attributes (values for a, b, c and d). It also contains several other private
variables (of type double) and public methods that will be utilized for
selection, fitness and crossover. I have implemented this program.
2)
Using the
pseudocode described in the algorithm (link below), write the program,
“GeneticAlgorithm.java” (I have attached the solution for your reference).
Pseudocode for “GeneticAlgorithm.java”
Java Files:
