GeneticAlgorithm.java:
public
static void main (String args [])
{
boolean flag = true;
int count = 0;
ArrayList<Chromosome> Initial = new ArrayList<
Chromosome>();
1)
We will start
with an initial population of 6. Run through a for loop of size = 6 and implement the following:
a.
Create a
Chromosome object, c
b.
Call the
initialize method in “Chromosome.java” for c
c.
Add c to Initial.
while (flag)
{
count++;
System.out.println ("Generation#" + count);
2) Loop through the array
list, Initial and implement the
following:
d.
Compute the
selection value for each Chromosome by calling the selection method in
“Chromosome.java”.
e.
if the
selection value for a Chromosome is 0:
· We have found a solution. Print
the attributes of the Chromosome as the answer. End the while loop by setting
flag to false.
else
· Compute the fitness value for
each Chromosome by calling the fitness method in “Chromosome.java”.
if
(flag)
{
3) For each
Chromosome, compute the probability of being chosen for the next generation, p as below:
§ p = (fitness
value for each Chromosome / sum of fitness values for all Chromosomes)
§ Set the value of p for each Chromosome by calling the
method, setProbability method in “Chromosome.java”
4)
Compute the cumulative probability, c_p for each Chromosome as below:
· c_p for Chromosome #1 = value of p
of Chromosome #1
· c_p for Chromosome #2 = value of p
of Chromosome #1 + value of p of
Chromosome #2
· c_p for Chromosome #3 = value of p
of Chromosome #1 + value of p of
Chromosome #2 + value of p of
Chromosome #3
And so on for Chromosomes, #4, #5 and #6.
Set the value
of c_p for
each Chromosome by calling the method, setCumulativeProbability
method in “Chromosome.java”
5) Implement the “getRouletteWheel()” method
as below (we will need this in Step #7):
public static ArrayList<Double>
getRouletteWheel()
{
Create an
array list, L of type Double.
Add six, random values (of type
double) between 0 and 1 into L. Use “Math.random()”.
Return L
}
6) Create
an array list, rWheel
of type double and assign the return value from getRouletteWheel() to rWheel as below:
· ArrayList<Double> rWheel = getRouletteWheel();
7) In this
step, we will select the best-fit Chromosomes of our population based on their
fitness values by employing the roulette-wheel method as described in the link
below:
If you
visualize the cumulative probabilities of our six Chromosomes mapped onto a
roulette-wheel as described in the link, you can infer that when we rotate the
wheel six times, the best-fit Chromosomes have a higher chance of being
selected as their cumulative probability values cover larger areas in the
roulette wheel. Implement the “getSelection” method
as below:
public
static ArrayList< Chromosome> getSelection(ArrayList< Chromosome> Initial, ArrayList<Double> rWheel)
{
Create
an array list, Selection of type
Chromosome.
For
every value, V in rWheel:
{
Find the
value, W in Initial such that the
cumulative probability of W > V.
Add W to Selection.
}
return
Selection;
}
8)
Overwrite Initial by assigning it the
return value of “getSelection” as below:
o
Initial = getSelection(Initial, rWheel);
9) After Step 8), Initial contains the six Chromosomes
selected for crossover (or mating).
§ Because of the probabilistic
nature of the Roulette-wheel method, we can expect the best-fit Chromosome to
repeat in Initial and the worst-fit
Chromosome to be excluded from Initial.
§ The recurrence of the best-fit
Chromosome in Initial is crucial
because we want the best-fit Chromosome to crossover with more than one other
“next best-fit” Chromosome. That way, we can propagate the fitness across
successive generations.
We will
implement the crossover as illustrated below. Let’s say our selected Chromosome
from Step 8) are as below:
Selection:
5 1 14 6
16 11 11 13
19 21 1 21
13 10 4 15
2 4 17 12
5 1 14 6
Rules for
Crossover:
o
The first
two attributes of the first selected Chromosome is combined with the last two
attributes of the second selected Chromosome to produce the first crossover
Chromosome.
o
The first
two attributes of the second selected Chromosome is combined with the last two
attributes of the first selected Chromosome to produce the second crossover
Chromosome.
o
The above process
is then followed with the rest of the selected Chromosomes (third and fourth
and fifth and sixth) to produce the remaining four crossover Chromosomes.
Crossover
5 1 11 13
16 11 14 6
19 21 4 15
13 10 1 21
2 4 14 6
5 1 17 12
public static ArrayList< Chromosome> getCrossOver
(ArrayList < Chromosome> Selection)
{
ArrayList<
Chromosome> CrossOver
= new ArrayList< Chromosome>();
Loop through Selection and add values to CrossOver as described in the above example
return CrossOver;
}
10) Overwrite
Initial by assigning it the return
value of “getCrossOver” as below:
o
Initial = getCrossOver(
Initial);
11) Implement
the random mutation as below:
public
static ArrayList< Chromosome> getMutation (ArrayList <
Chromosome> CrossOver)
{
Randomly select an integer value, A
between 0 and 5 (Chromosome selected for mutation)
Randomly select an integer value, B between 0 and 3 (attribute selected
for mutation)
Randomly select an integer
value, C between 1 and 21
(replacement value for attribute)
Chromosome
M = Value at cell#A in CrossOver
ArrayList<Integer> list = get attributes of M
list.set(B, C);
return
CrossOver
}
12) Overwrite Initial
by assigning it the return value of “getMutation” as
below:
o
Initial = getMutation
(Initial);
} // end if
}
// end while
} // end main
