search

Grenadingue / 2-wheels-1-arm

A genetic algorithm searching for solutions to move a simple robot straightforward in a virtual environment
GNU General Public License v3.0
2 stars 0 forks source link

Describe a simple algorithm for the first implementation #4

Open Grenadingue opened 7 years ago

Grenadingue commented 7 years ago

Describe the first implementation of our genetic algorithm in pseudo code

Useful ressources:

Grenadingue commented 7 years ago

For the practical test (the predefined string finder), the algorithm looked like the following (the chromosomes being the letters in the string):

  1. [Start] Generate random population of n chromosomes (suitable solutions for the problem)
  2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
  3. [New population] Create a new population by repeating following steps until the new population is complete
    1. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
    2. [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
    3. [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
    4. [Accepting] Place new offspring in a new population
  4. [Replace] Use new generated population for a further run of algorithm
  5. [Test] If the end condition is satisfied, stop, and return the best solution in current population
  6. [Loop] Go to step 2

One major difference between the practical tests and this project will be the way of evaluating each individual in the population (fitness). We will surely need to make each individual go into the simulator (virtual environment), then evaluate its success to get closer to its goal (to move).

One other difference will be the way of encoding the chromosomes of an individual. We can use binary strings, characters strings, integers, floats, etc... We can almost choose whatever we want to represent an individual genome. But choosing what each gene represents, and how the genes are organized (read) together is a bigger question.