Implementation and analysis of performance of Genetic Algorithm (GA) in solving Asymmetric Travelling Salesman Problem (ATSP) — a well-known NP-complete problem. The ATSP involves finding the shortest possible Hamiltonian cycle in a directed graph where the cost of travel between nodes may differ depending on the direction.
The algorithm begins by initializing a population of potential solutions, which are then iteratively improved using genetic operations such as selection, crossover, mutation, and succession. Each individual in the population is evaluated using a fitness function based on the total weight (distance) of the corresponding tour.
The project explores several variants of genetic operators, including different selection strategies (e.g., tournament, roulette wheel), crossover techniques, and mutation mechanisms, to determine their influence on solution quality and convergence speed.
Experiments are conducted to analyze the impact of key parameters such as population size, mutation rate, and crossover rate. Additionally, the effectiveness of the GA is compared with another heuristic method—Tabu Search—to assess relative performance.
All experiments were done for graph with 170 nodes from file ftv_170.xml
Result are described in: Efficient_Algorithm_Design_report
cd src/
To compile use:
g++ -g *.cpp -o ga
To run:
./ga
or to run with custom parameters:
./ga --config <population_size> <crossover_rate> <mutation_rate> <crossover_type> <mutation_type> <stop_time>
👤 triplo098
- Github: @triplo098
- LinkedIn: @piotr-koronczok
Give a ⭐️ if this project helped you!
This README was generated with ❤️ by readme-md-generator