Introduction to Genetic Algorithms
Genetic algorithms are an heuristic search and optimization technique that uses a mechanism inspired in the way living organisms pass their traits from one generation to the next. The genetic algorithm as we know it was first presented by John Holland in the book Adaptation in Natural and Artificial Systems.
To create make an analogy with nature, so solutions are called individuals and a group of solutions is called a population.
With a Darwinian approach, GAs try to mimic evolution and natural selection. Evolution is achieved by using operations that create change into the individuals and consequently to the population, the main mechanisms of evolution are: crossover and mutation. Natural selection is attained by classifying individuals using a fitness function; this function will evaluate how good the individual is and will affect the chance it has to pass traits to the next generation. The fitness function is highly dependent on the problem being solved.
Genetic algorithms are appropriate for problems where an accurate solution (that may not be optimal) is needed and when there is no need for a real-time response.
Advantages of GA.
Some benefits of Genetic algorithms are the ability to provide a very accurate result and usually provide an easy to understand solution to a problem, contrary to neural networks, where the inner workings are very hard to interpret.
Limitations of GA.
Some of the limitations of GA are: the cost of computing the fitness function, they are highly stochastic method, each run usually provides a different solution, so it is better to run several runs with the same parameters to obtain a solution, high dependence on the initial population that is randomly generated, high dependence on parameter settings, that is very hard to tweak, they do not guarantee to find the optimal solution.
The travelling salesman iPython notebook can be found here
https://github.com/jcanelhas/GAIntro/blob/master/Travel%20Salesman%20GA%20v2.ipynb
The objective of this repo is to serve as an introduction to genetic algorithms.
feel free to contribute.