Genetic Algorithm: Chromosomes

Question

0.00/5 (No votes)

See more:

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 :((
Need some help.
Thanks alot :((

[orig. title]
Genetic Algorithm, class scheduling]Convert a chromosom to other chromosome with different size of array

Posted 3-Jan-11 22:51pm

Abdi tombang

Updated 4-Jan-11 2:20am

Slacker007

v3

Add a Solution

Comments

Slacker007 4-Jan-11 8:21am

Shortened title and improved readability.

Henry Minute 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 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?? :'(

Richard MacCutchan 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.

William Winner 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. "

Sergey Alexandrovich Kryukov 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.

Abdi tombang 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

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Abdi tombang · Answer 1 · 2011-01-04T19:40:00

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 :-(