Genetic algorithms
randomly to create new children. These three stages are then repeated multiple times, producing more optimal solutions in every iteration. Just as with evolution, the results cannot be entirely predicted.
However, the effectiveness of the algorithm is best compared to other methods, which will be done using the Travelling salesman problem . Firstly, to achieve a comparison, I am going to compare a more rudimentary method to find optimal solutions to the algorithm, namely, a brute force attack. Brute force works by creating every single possible option and then testing their fitness for the solution. Firstly, this means that, as long as the attack is completed, it will always find the best possible solution. The great weakness of this method is that it must finish. For a brute force attack on the Travelling salesman problem, as the number of cities increases so does the number of possible solutions required to check. The time complexity of this algorithm is O(n!) which means that the time required grows incredibly fast as the problem expands. For example, with 25 cities there are 25! possible solutions (i.e. 15.5 septillion different solutions) with the possibility that the most optimal is at the end of the brute force attack. For testing the brute force method, I used an algorithm 6 in Python3, my preferred programming language. Using this algorithm, I tested the brute force attack approach on 10 cities in the travelling salesman problem. From this, I discovered that it had a 100% success rate as every possible solution is checked and the best result is always discovered. Furthermore, using Pyt hon’s inbuilt timer function 7 I calculated the time the programme took to execute. I tested it 10 times and my findings were that the slowest was 35.79 milliseconds and the fastest was 26.70 milliseconds with an average of 28.26 milliseconds. This is practically instantaneous. Overall, the brute force method is extremely effective on small-scale problems owing to its speed and guaranteed results but it is more tedious with larger problems. The process of a genetic algorithm is more difficult to determine. For a genetic algorithm, it doesn’t review every single possible solution instead it uses a population and ‘ evolves ’ them through multiple generations. I used an algorithm 8 in Python3 to test the algorithm in a 5-city problem with chromosomes consisting of 5 genes and 5 generations. I tested the algorithm 10 times and the results showed that 50% of the time by the 5th generation the algorithm discovered one or more of the most optimal routes; 40% were suboptimal results, and 10% were failures where the results were not at all efficient. This shows that it is relatively effective at handling this problem as 90% produced good results. Furthermore, using the Python timer function, I discovered that the programme ran very quickly, with the fastest time being 36.28 milliseconds and an average of a slightly higher 39.98 milliseconds. So, the algorithm can solve the problem with little latency, further implying its effectiveness. But this was only on a 5-city problem; as the number of cities increases, more generations are required. This means not only more time and space is required, but raises the problem of how many generations will be suitable, as too few will lead to inadequate results but too many would be a waste of time and space as the algorithm will just plateau. For its time complexity, just like evolution, is 6 Westphal, S. (2010). TSP brute-force solution . Gist. Retrieved September 3, 2022, from https://gist.github.com/westphahl/432876. 7 Time - Time Access and conversions . Python 3.10.7 documentation. (n.d.). Retrieved September 15, 2022, from https://docs.python.org/3/library/time.html#time.time. 8 chitrankmishra. (2021, December 23). Traveling salesman problem using genetic algorithm . GeeksforGeeks. Retrieved September 15, 2022, from https://www.geeksforgeeks.org/traveling-salesman-problem-using- genetic-algorithm/.
63
Made with FlippingBook - Online catalogs