Conclusion

The application that has been developed implements two genetic algorithms that solve the shortest path problem between two vertices in a weighted, non-oriented graph.

Even on the small graphs² used to test the application, we noticed that the best solution is rarely found. However, in most cases, the genetic algorithms find a satisfying solution.

Both the genetic algorithms can be tuned by modifying several parameters: the quality of the solution dramatically depends on these values. Unfortunately, there exists no precise method to determine the best set of parameters: the algorithms' tuning is based on a try and fail strategy.

By running several tests, we pointed out a weakness of the Genetic Shortest Path Algorithm Without Constraints. Since this algorithm allows the existence of invalid solutions, the population my contain very short solutions³. Obviously, such solutions have a very small weight and thus their number increases in every following generation. This behaviour quickly produces a population containing only invalid paths.

This project allowed us to get acquaint with the specification and the implementation of a genetic algorithm. Our application could be improved, for example by defining a better strategy to determine the parameters' values. The fitness function for the Genetic Shortest Path Algorithm Without Constraints should be modified, so that the too short paths do not produce a degenerated population. Despite these weaknesses, we believe that this application constitutes a valid proof of concept and it shows that genetic algorithms can be used to solve the shortest path problem in a graph.

The authors have very well appreciated the project. It allowed them to learn a lot about genetic algorithms, an exciting area of computer science.