All right, I'll tell the full story about my genetic algorithm :-)
1. Create a database that holds data classes, for example table:
ID KelasPerkuliahan ID_Course ID_Lecture Duration(1=45 minutes)
1 PBIO_012 MRA 3
2 PBIO_013 RZI 2
3 FKIP_012 SFI 2
4 FKIP_011 ADI 2
5 PBIO_014 YNI 3
6 PBIO_015 JTI 3
7 PBIO_018 SRI 2
8 FKIP_009 NTR 2
9 PBIO_010 PRM 3
2. Create kromosom_waktu with the size of the result times the number of active hours, the number of days in college, and the amount of space.
Kromosom_waktu = max day * max hour * Sum of room
= 5 dats x 12 hours x 9
= 540 Slot
Then take the ID KelasPerkuliahan and enter into kromosom_waktu randomly. This is done until the population are met.
3. Kromosom_waktu conversion into chromosome-sized number of rows in the table KelasPerkuliahan. This is done to streamline the use of slots on the chromosome. Every kromosom_waktu in the population will in conversion.
4. Evaluation of Fitness value of each chromosome in the population. Chromosomes that do not have a timetable clash will have the highest fitness value. Sample evaluation on chromosome fitness values above:
ID KelasPerkuliahan Score Placement
1 2
2 2
3 2
4 1
5 1
6 2
7 2
8 2
9 2
= 2 +2 +2 +1 +1 +2 +2 +2 +2
9 x 2
= 16/18
= 0.89
• The calculation of fitness value:
Chromosome [1] = 0.89
Chromosome [2] = 0.76
Chromosome [3] = 0.46
Chromosome [4] = 0.83 +
TotalFitness = 2.94
• Calculate the probability Fitness
P [i] = fitness [i] / Fitness
P [1] = 0.89 / 2.94 = 0.34
P [2] = 0.76 / 2.94 = 0.26
P [3] = 0.46 / 2.94 = 0.16
P [4] = 0.83 / 2.94 = 0.24
• Find the value of the cumulative probability of population
C1 = P1 = 0.34
C2 = P1 + P2 = 0.60
C3 = P1 + P2 + P3 = 0.76
C4 = P1 + P2 + P3 + P4 = 1
5. Roulette Wheel Selection method Selection. The steps that have to do is:
• Generate a random number of population with a range of 0 s / d 1
R [1] = 0.201
R [2] = 0.284
R [3] = 0.009
R [4] = 0.822
• If R [k] <C [1] is the parent chromosome [i]
If C [k-1] <R [k] <C [k] is the parent chromosome [k]
Table 4.4 Table Selection Chromosome to be a Parent
Chromosome R Value Range Probability (C) Parent
1 .201 - C1 1
2 .284 - C1 1
3 .009 - C1 1
4 0.822 C3 - C4 4
• The Selection is a selected chromosome to be a parent, namely:
Chromosome [1] = 22, 37, 1, 16, 495, 523, 56, 530, 483
Chromosome [2] = 22, 37, 1, 16, 495, 523, 56, 530, 483
Chromosome [3] = 22, 37, 1, 16, 495, 523, 56, 530, 483
Chromosome [4] = 29, 7, 16, 19, 95, 93, 46, 60, 33
6.) Perform crossover with probability of crossover (Pc) which have been determined. Suppose, Pc = 25% = 0.25.
• Generate a random number of population with a range of 0 s / d 1
Rc [1] = 0.191
Rc [2] = 0.259
Rc [3] = 0.760
Rc [4] = 0.066
Table 4.5 Table Crossover between the elected Parent
Parent 1 Parent 2 Offspring
Chromosome [1]
= 22, 37, 1, 16, 495, 523, 56, 530, 483 Chromosomes [4]
= 29, 7, 16, 19, 95, 93, 46, 60, 33 Offspring [1]
= 22, 7.16, 19, 95, 93, 56, 530, 483
Chromosome [4]
= 29, 7, 16, 19, 95, 93, 46, 60, 33 chromosomes [1]
= 22, 37, 1, 16, 495, 523, 56, 530, 483 Offspring [4]
= 29, 37, 1, 16, 495, 523, 46, 60, 33
• Population after crossover
Chromosome [1] = 22, 7.16, 19, 95, 93, 56, 530, 483
Chromosome [2] = 22, 37, 1, 16, 495, 523, 56, 530, 483
Chromosome [3] = 22, 37, 1, 16, 495, 523, 56, 530, 483
Chromosome [4] = 29, 37, 1, 16, 495, 523, 46, 60, 33
7.) Perform mutation with probability of mutation (Pm), which has been determined. Suppose, Pm = 10% = 0.10.
• Calculate the total genes present in the population
Total genes = total population x size of chromosome
= 4 x 9
= 36 genes
The genes in the mutation = Pm x Total genes
= 0.10 x 36
= 3.6 = 4 gene (Rounded)
• Generate a random number of genes to be mutated with a range 1s / d 36 (limit range is the total length of the gene)
Rm [1] = 6
Rm [1] = 21
Rm [1] = 26
Rm [1] = 34
• Generate a random number of genes to be mutated with a range 1s / d 36 (limit range is the total length of the gene)
Rm [1] = 9
Rm [1] = 25
Rm [1] = 28
Rm [1] = 36
• The population of the mutations:
Chromosome [1] = 22, 7.16, 19, 95, 483, 56, 530, 93
Chromosome [2] = 22, 37, 1, 16, 495, 523, 56, 530, 483
Chromosome [3] = 22, 37, 56, 16, 495, 523, 1, 29, 483
Chromosome [4] = 530, 37, 1, 16, 495, 523, 33, 60, 46
After making the mutation, the resulting new population. On each chromosome in the new population will be evaluated fitness value. This cycle continues over and over until the finish condition is fulfilled. Suppose in the above calculation, the chromosomes [1] is a chromosome that has the best fitness value, then the output lecture schedule is:
NB: I can't load a table ang an image here. This paper have so many image. If you really want to see my full paper, I'll send it by email :-)
Please, need help to making a code in vb.net from this one :-(