Are Genetic Algorithms Effective for Computationally Intense Problems?

Overview

Objectives/Goals Efficient energy use can help to combat global warming. Transportation of people and goods has increased with the expansion of global markets, leading to greater energy consumption. Finding the shortest transportation routes reduces energy needs. This challenge is represented by the traveling salesman problem (TSP), which attempts to find the shortest travel distance to visit each city of a given list once. A brute-force method, which calculates all possible routes between cities, is optimal for small city numbers, but it takes a powerful computer 30,000 years to solve a modest 25-city problem. Faster methods are needed. In this project, I have tested the hypothesis that genetic algorithms, which emulate the principles of evolution and natural selection, can find better solutions to the TSP than other common algorithms. Methods/Materials Java programs were written to address the TSP, and were tested with model sets of cities. Specifically, a virtual population of organisms representing specific travel routes was generated. An organism was allowed to produce offspring when its route was among the shortest in the population. Each offspring was mutated by swapping pairs of cities relative to its parent, and the algorithms were optimized for population sizes and survival parameters. Results By testing different model city sets, I found that a genetic strategy outperformed brute force and random algorithms, while it was inferior to the nearest neighbor algorithm in most cases. Furthermore, to optimize the parameters of the genetic algorithm, such as population size and survival characteristics, a nested genetic strategy was implemented as an additional level of genetic selection. This nested genetic strategy was found to outperform the simple genetic strategy. Taken together, my results demonstrate that genetic strategies can be effective at solving the TSP. Conclusions/Discussion My findings suggest that applying biological principles to algorithm design has great potential for improving computational performance and finding solutions that minimize energy consumption in transportation challenges.

Competition history

• CSEF 2016 Mathematics & Computer Science · Entry J1405

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2016 project