Genetic algorithms use an evolutionary theory approach to computationally approximate optimal solutions for NP-hard problems. This work focuses on two such examples - the 0/1 Knapsack Problem and the Travelling Salesman Problem. There exist numerous representations, crossover operators, mutation strategies and selection procedures that can successfully tackle both problems. In this repository, we implement several techniques from literature but also propose custom ones based on observations. All the newly introduced approaches are described in the paper provided. The paper also reports and comments on the computational results of the custom experiments.
Genetic Algorithms provide a wide variety of parameters to adjust in order to successfully and quickly reach optimality. These GA specifications vary greatly depending on the problem definition and size. This report focuses on the 0/1 Knapsack and the Travelling Salesman problems. Our research shows that specific GA parameters are of greater interest based on the problem formulation. The 0/1 Knapsack section puts accent on the mutation and crossover properties of the GA. We show that a mutation that removes two items and adds a one other is much more suitable for our problem than removing only one item. Moreover, we proved that a single-point crossover performs worse than our "swap-one" crossover in a complex 0/1 Knapsack setting. The TSP section introduces a modified crossover operator and emphasises on the general problem representation. We illustrate that the proposed CPMX crossover operator outperforms the other two algorithms from the literature given the correct mutation rate. Future work suggestions from this report are to thoroughly examine the performance of the CPMX over different GA approaches and formulations.
This section lists the major frameworks that the project was built with.
Contributions are what make the open source community such an amazing place to be learn, inspire, and create. Any contributions you make are greatly appreciated.
- Fork the Project
- Create your Feature Branch (
git checkout -b feature/AmazingFeature) - Commit your Changes (
git commit -m 'Add some AmazingFeature') - Push to the Branch (
git push origin feature/AmazingFeature) - Open a Pull Request
Distributed under the MIT License. See LICENSE for more information.
Hristo Minkov - minkov.h@gmail.com
Zhecho Mitev - zhecho15@yahoo.com
Codebase Link: https://github.com/icaka98/TSP-GeneticAlgorithm