Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: VB.NET
If you have a table with 10 rows.
And you make a chromosome that size is : max day * max hour * Sum of room.
Ex: chromosome: 5 days * 12 hours * 5 rooms = 300 slots
And then insert the data of the table to the chromosome by random.
 
The data was 10 records but the chromosome has 300 slots, it's not effective. So, we turn the score in the chromosome to other chromosome with size 10 slots( depend how much the table's row). In this chromosome number of array is the row number, and the value is the record position(value) on the first chromosome
 
Ex: first Chromosome= 300 slots. 10 slots have a record(randomly). We convert that chromosome the second chromosome(size 10 slots).
 
I can't make a code n vb.net Cry | :((
Need some help.
Thanks alot Cry | :((
 
[orig. title]
Genetic Algorithm, class scheduling]Convert a chromosom to other chromosome with different size of array
Posted 3-Jan-11 22:51pm
Edited 4-Jan-11 2:20am
Slacker00774.2K
v3
Comments
Slacker007 at 4-Jan-11 8:21am
   
Shortened title and improved readability.
Abdi tombang at 4-Jan-11 10:14am
   
Hmm, my problem is how to make other chromosome that have a value from the first one with different size(number of slot is depend row of the tabel)
The first chromosome just like what mladen make in : http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx
 
But, he make the first chromosome has too much slot. I want to convert the first chromosome into the chromosome that have a slot as the number of record in the table. So, it'll be more efficient.
 
But, I have some problem to making the code in vb.net.
Anyone can help me?? :'(
SAKryukov at 4-Jan-11 13:30pm
   
William, it's all right. As genetic programming takes inside from genetics, the term chromosome take a bit different meaning. At the same time, I thought the term chromosome is justified if the pseudo-random algorithm imitates cross-over. If applied to room occupation, it is not the size of a chromosome should be considered, but understood as some trait encoded in the chromosome "digital proteins".
 
So far, I don't see an actual genetic programming idea in this question. Perhaps Abdi is solving only a part of the problem. If so, I think it would be not very nice.
 
Abdi, you should really tell us the whole story. Remember, CodeProject members are driven by sheer interest and a fun of helping.
William Winner at 4-Jan-11 12:28pm
   
I do not think anyone understands what you are asking. Especially since the word "Chromosome" does not mean what you think it means. From dictionary.com:
 
"any of several threadlike bodies, consisting of chromatin, that carry the genes in a linear order: the human species has 23 pairs, designated 1 to 22 in order of decreasing size and X and Y for the female and male sex chromosomes respectively. "
Richard MacCutchan at 4-Jan-11 12:19pm
   
I have looked at the link you posted and it is something to do with class scheduling, so I think your use of the word "Chromosome" is not correct. Perhaps you could explain using some other term for the actual "base unit" you are trying to model.
Henry Minute at 4-Jan-11 9:44am
   
Did you actually mean Chromasome? So far as I am aware Chromasomes have little to do with rooms, days or hours.
Abdi tombang at 5-Jan-11 1:42am
   
I can't post a full story as a coment here :-(
So I post the full story on the answer.
Thanks :)

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

All right, I'll tell the full story about my genetic algorithm Smile | :)
 
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 Smile | :)
Please, need help to making a code in vb.net from this one Frown | :-(
  Permalink  
Comments
scutterizta at 18-Oct-12 12:34pm
   
hi bro abdi, i'm yogi from indonesia.
in this semester, i take thesis about scheduling my college with using GA.
i need more references about that, can you help me...
thanks before.
email : ariezta_slash@yahoo.com
fb : yogi ariezta

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 530
1 Sergey Alexandrovich Kryukov 330
2 BillWoodruff 299
3 PIEBALDconsult 230
4 CPallini 220
0 Sergey Alexandrovich Kryukov 10,615
1 Maciej Los 5,354
2 OriginalGriff 5,254
3 CPallini 3,719
4 BillWoodruff 3,476


Advertise | Privacy | Mobile
Web02 | 2.8.141029.1 | Last Updated 5 Jan 2011
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100