AlgoMotion | Genetic Algorithm Solves the Traveling Salesman Problem by Mimicking Evolution @AlgoMotion | Uploaded July 2024 | Updated October 2024, 1 hour ago.
Watch & hear a genetic algorithm progress as it mimics evolution to solve the traveling salesman problem.
Cities are named after the 12 notes of the chromatic scale, so we have something to listen to as we operate on the graph.
Includes a quick primer on the traveling salesman problem (TSP), conventional approaches to solving it and why they're difficult for larger problem sizes (combinatorial explosion, NP-hardness), some basic heuristics (nearest neighbor algorithm, optimal bitonic tour), and an explanation of genetic algorithms (tournament selection, elitism, crossover, mutation, and a termination condition) and their application to the TSP.
We use "edge recombination crossover" a.k.a. the "edge recombination operator" to crossover parent solutions in the TSP, and "displacement mutation" to mutate offspring.
A genetic algorithm is applied to the TSP with a population of size 20, then again with a population of size 100.
The genetic algorithm visualizations were programmed in Java using a graphical library called Processing (processing.org/).
________________________
Sources:
• Razali, N. M., & Geraghty, J. (2011, July). Genetic algorithm performance with different selection strategies in solving TSP. In Proceedings of the world congress on engineering (Vol. 2, No. 1, pp. 1-6). Hong Kong, China: International Association of Engineers. iaeng.org/publication/WCE2011/WCE2011_pp1134-1139.pdf
• Larranaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial intelligence review, 13, 129-170. cig.fi.upm.es/wp-content/uploads/2024/01/Genetic-algorithms-for-the-travelling-salesman-problem-A-review-of-representations-and-operators.pdf
• Estimate for number of atoms in the observable universe: "How many atoms are in the observable universe?" by Harry Baker, July 10, 2021: livescience.com/how-many-atoms-in-universe.html
________________________
Further Reading (affiliate links):
▶ "Genetic Algorithms in Search, Optimization, and Machine Learning" by David E. Goldberg: amzn.to/3YgQkpw
▶ "Evolutionary Deep Learning: Genetic algorithms and neural networks" by Micheal Lanham: amzn.to/4flymbN
▶ "Introduction to Algorithms" (4th Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein : amzn.to/3WlnnGj
▶ “Algorithms” (4th Edition) by Robert Sedgewick & Kevin Wayne: amzn.to/3uo25xR
▶ “Effective Java” (3rd Edition) by Joshua Bloch: amzn.to/3HOnYJL
0:00 The Traveling Salesman Problem
0:33 Naive Brute Force, Combinatorial Explosion
1:13 Held-Karp Algorithm
1:43 Other Exact Algorithms for the TSP
1:54 NP-Hardness
2:04 Heuristics
2:13 Nearest Neighbor Algorithm
2:59 Optimal Bitonic Tour
3:23 Genetic Algorithm Overview
3:38 Fitness
3:52 Initial Population Generation
4:07 Elitism
4:15 k-Way Tournament Selection
4:36 Crossover
5:10 Mutation
5:38 Termination Condition
5:59 Genetic Algorithm Summary
6:11 Genetic algorithm evolves a solution to the TSP with population size 20
36:09 Genetic algorithm evolves a solution the TSP with population size 100
#visualization #computerscience #computation #geneticalgorithm #java #processing #computermusic #algorithmiccomposition #satisfying #educational #algorithm #ai
Watch & hear a genetic algorithm progress as it mimics evolution to solve the traveling salesman problem.
Cities are named after the 12 notes of the chromatic scale, so we have something to listen to as we operate on the graph.
Includes a quick primer on the traveling salesman problem (TSP), conventional approaches to solving it and why they're difficult for larger problem sizes (combinatorial explosion, NP-hardness), some basic heuristics (nearest neighbor algorithm, optimal bitonic tour), and an explanation of genetic algorithms (tournament selection, elitism, crossover, mutation, and a termination condition) and their application to the TSP.
We use "edge recombination crossover" a.k.a. the "edge recombination operator" to crossover parent solutions in the TSP, and "displacement mutation" to mutate offspring.
A genetic algorithm is applied to the TSP with a population of size 20, then again with a population of size 100.
The genetic algorithm visualizations were programmed in Java using a graphical library called Processing (processing.org/).
________________________
Sources:
• Razali, N. M., & Geraghty, J. (2011, July). Genetic algorithm performance with different selection strategies in solving TSP. In Proceedings of the world congress on engineering (Vol. 2, No. 1, pp. 1-6). Hong Kong, China: International Association of Engineers. iaeng.org/publication/WCE2011/WCE2011_pp1134-1139.pdf
• Larranaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial intelligence review, 13, 129-170. cig.fi.upm.es/wp-content/uploads/2024/01/Genetic-algorithms-for-the-travelling-salesman-problem-A-review-of-representations-and-operators.pdf
• Estimate for number of atoms in the observable universe: "How many atoms are in the observable universe?" by Harry Baker, July 10, 2021: livescience.com/how-many-atoms-in-universe.html
________________________
Further Reading (affiliate links):
▶ "Genetic Algorithms in Search, Optimization, and Machine Learning" by David E. Goldberg: amzn.to/3YgQkpw
▶ "Evolutionary Deep Learning: Genetic algorithms and neural networks" by Micheal Lanham: amzn.to/4flymbN
▶ "Introduction to Algorithms" (4th Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein : amzn.to/3WlnnGj
▶ “Algorithms” (4th Edition) by Robert Sedgewick & Kevin Wayne: amzn.to/3uo25xR
▶ “Effective Java” (3rd Edition) by Joshua Bloch: amzn.to/3HOnYJL
0:00 The Traveling Salesman Problem
0:33 Naive Brute Force, Combinatorial Explosion
1:13 Held-Karp Algorithm
1:43 Other Exact Algorithms for the TSP
1:54 NP-Hardness
2:04 Heuristics
2:13 Nearest Neighbor Algorithm
2:59 Optimal Bitonic Tour
3:23 Genetic Algorithm Overview
3:38 Fitness
3:52 Initial Population Generation
4:07 Elitism
4:15 k-Way Tournament Selection
4:36 Crossover
5:10 Mutation
5:38 Termination Condition
5:59 Genetic Algorithm Summary
6:11 Genetic algorithm evolves a solution to the TSP with population size 20
36:09 Genetic algorithm evolves a solution the TSP with population size 100
#visualization #computerscience #computation #geneticalgorithm #java #processing #computermusic #algorithmiccomposition #satisfying #educational #algorithm #ai
