Content deleted Content added
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8 |
Rcarrasco8 (talk | contribs) |
||
Line 13:
A more realistic problem we might wish to solve is the [[travelling salesman problem]]. In this problem, we seek an ordered list of cities that results in the shortest trip for the salesman to travel. Suppose there are six cities, which we'll call A, B, C, D, E, and F. A good design for our chromosome might be the ordered list we want to try. An example chromosome we might encounter in the population might be <code>DFABEC</code>.
==Selection, crossover, elitism and mutation==
{{see also|Selection (genetic algorithm)|Crossover (genetic algorithm)|Mutation (genetic algorithm)}}
'''Fitness Function'''
Each generation in the genetic algorithm is the set of all current solutions. In each generation of the genetic algorithm, two parent chromosomes (encodings) are selected based on their fitness values which is determined by the [[fitness function]]; these chromosomes are used by the mutation and crossover operators to produce two offspring chromosomes for the new population.<ref name=what-are-gas /> Each encoding is an argument to the fitness function and outputs a score. In the real world you can imagine a fitness function being an organisms ability to survive and the score being the ease at which it does so. This determines how "good" a genetic encoding is with respect to the fitness function. Not all solutions pass the threshold and are therefore not considered for the next step.
'''Crossover'''
Two parent chromosomes are selected and using the single point [[Crossover (genetic algorithm)]] they create two new solutions. One factor to consider is that because the selection and crossover functions are governed by randomness there is no way to ensure an improvement in solutions across evolutions.
'''Elitism'''
[[Elitism]] remedies this however by selecting the nth top solutions in regard to the fitness function and copy them into the next generation. This ensures our best solutions are not lost while still utilizing the algorithm.
'''Mutation'''
The next step is the introduction of [[mutation]]. Mutation will change a random bit of the genome for example, To discover solutions that may otherwise be impossible by regular crossover of existing solutions. These new solutions are introduced to the algorithm and it runs on a loop until a satisfactory solution has been found. How genetic algorithms differ is by changing the functions(fitness function, crossover function, selection function, mutation function and function to generate new solutions) used in the algorithm. You may also change the genetic representation of a solution.
==References==
| |||