Genetic algorithms
incredibly difficult to predict (as shown by the 50% complete success rate). Therefore, the nature of the algorithm makes the time complexity stochastic, 9 as the randomness of both the mutation mixed with the reproduction in the crossover stage makes the algorithm’s success subject to chance. Furthermore, the space complexity can also grow incredibly large depending on the number of generations, the reproduction process, and the size of the population. To achieve the best possible results, many iterations are required and therefore the storage space can become extreme. There is no easy solution of the travelling salesman problem. Genetic algorithms are effective in low to mid-range as through roughly 10 generations they produce fairly successful results, with 50% of the time the best route is found in the 5th generation. However, the a lgorithm doesn’t scale well to a higher number of cities, as the gene’s evolutio n becomes less reliable. The brute force attack is far more reliable, as it always achieves the best possible route. Furthermore, current processors are very powerful. The brute force attack on 5! takes roughly 30 milliseconds while running on AMD Ryzen 7 4800H 10 which runs at 2.90 GHz (not even the most powerful processor on the market), although, similar to a genetic algorithm, as the complexity of the problem increases so will the time required. In conclusion, although the genetic algorithm is fairly effective, it pales in comparison to the brute force attack. The major difference is that the genetic algorithm is skewed by its inherent randomness, with the results showing at best a 90% success rate, while the brute force consistently provides the best answer. Then in relation to time, the test I created had genetic algorithms dealing with only 5 cities while the brute force attack dealt with 10. The time difference showed that even though the brute force attack had double the cities, it was only slightly slower than the genetic algorithm. So, although genetic algorithms are an inventive and innovative idea, they aren’t very effective and that’s why they haven’t been explored further or often used in the industry.
Additional bibliography
Beasley, David, Bull, David R. and Martin, Ralph Robert 1993. An overview of genetic algorithms: Part 1, fundamentals. University Computing 15 (2), pp. 56-69. File Yampolskiy, R. V. (2018, December 1). Why do we not evolve software? Analysis of evolutionary algorithms . Evolutionary bioinformatics online. Retrieved September 3, 2022, from https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6287292/ YouTube. (2015). What is a Genetic Algorithm . YouTube . Retrieved September 3, 2022, from https://www.youtube.com/watch?v=1i8muvzZkPw.
9 Murray-Smith, D. J. (2012). Modelling and simulation of Integrated Systems in engineering: Issues of methodology, quality, testing, and application . Woodhead Publishing. 10 AMD Ryzen ™ processors. the fastest in the game. AMD Ryzen ™ processors. The Fastest in the Game. (n.d.). Retrieved September 2, 2022, from https://ryzen.gg/uk/.
64
Made with FlippingBook - Online catalogs