Monday, December 14, 2009

Roultte Wheel Selection in Genetic Algorithm

Roulette Wheel was one of most common method among selection methods in GA. It start after generate population of chromosome work has been completed. The problem is how to select individual population in crossovering method. Before selecting each, every individual population need to calculate their fitness and rank it by good solution in higher and lower for less good solution. Then it can represent by a big round cake or circle. The big partition cake for good solution and small partition cake for less good solution. The idea was every good solution will have more probability compare with less good solution. This picture below are taken from others website. Population no. 2 have small shape because of less good solution compare with no. 2 and no.3 where it was more good solution chromosome.
After that throw the dice to get random number, then two selection from population cromosome for crossover process. It also can be use to select which population that can be use for mutation process. Finally we can select the best solution among every population, crossover and mutation process. These idea for fast searching solution compare with conventional method. Thank you for reading.

Saturday, December 5, 2009

Encoding Problem into Genetic Algorithm process

When dealing with Genetic Algorithm optimization method, there is need to encode problem that can be suite in Genetic Algorithm process.
In last article I have mention some about few ways to encode problem. Now I just want to explain more about one of the method that what I be use which is Permutation Encoding.
Permutation encoding can be used in ordering problems, such as traveling salesman problem or task ordering problem. In permutation encoding, every chromosome is a string of numbers, which represents number in a sequence.
In my research I use permutation where it can give order chosen node to be sleep mode, than monitor the delay on network as it fitness. Time slot of node to be sleep mode will be change for each chromosome population if packet delay of network increase. The process will be repeated until one solution have been found.
  • Crossover
Single point crossover - one crossover point is selected, till this point the permutation is copied from the first parent, then the second parent is scanned and if the number is not yet in the offspring it is added
(1 2 3 4 5 6 7 8 9) Chromosome A +
(4 5 3 6 8 9 7 2 1) Chromosome B
=> (1 2 3 4 5 6 8 9 7) After crossover
  • Mutation
Order changing - two numbers are selected and exchanged
(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Thursday, December 3, 2009

Process involve in Genetic Algorithm

Hai, today I would like to tell more detail about process that need to be understand when dealing with Genetic Algorithm. Before that, there is need to encoding the problem to be represent by individual cromosome, so that can be process in Genetic Algorithm. There are four main type that can be represent of problem situation. There are:
  1. Binary Encoding
  2. Permutation Encoding
  3. Value Encoding
  4. Tree Encoding
After complete identify which type encoding need to be choosen, then can go through futher prosess. There are four main processes there are:

  1. Selection
  2. Crossover
  3. Mutation
  4. Regeneration

1. Selection

Under this process also have 3 methods where:

  1. Elitism
  2. Roulette Wheel
  3. Tournament Selection

2. Crossover

Under this process also have many methods but 2 of them are:

  1. Exponential Scaling
  2. Linear Normalize

3. Mutation

Under this process just similar between all researchers that using GA

4. Regeneration

Under this process it will select the best population for next iteration, so if there are new child cromosome that better with their parent cromosome from previous generation then it will replace or overwrite that parent cromosome.

Newer Posts Older Posts Home


blogger templates | Make Money Online