Welcome to the repository for Assignment #1 for CSCI-561, USC's Foundations of Artificial Intelligence graduate course. This project is an exploration of solving the 3D Traveling Salesman Problem (TSP) using a Genetic Algorithm implemented in Python.
The TSP is a classic problem in computer science, considered NP-hard. To learn more, click here.
The Genetic Algorithm is a heuristic search inspired by the process of natural selection. To learn more, click here.
GeneticAlgorithm Class (genetic_algorithm.py
)
- Methods:
nearest_cities(self, current_city, unvisited_cities, N)
:- Finds closest 'N' cities to the current city.
generate_path(self, start_city, city_list, random_factor)
:- Generates a single path using the nearest neighbor algorithm with randomization.
generate_population(self, size, city_list, random_factor)
:- Generates an initial population.
createMatingPool(population, tournamentSize, matingPoolSize)
:- Creates a mating pool.
select_elites(self, population, number_cities, number_elites)
:- Selects elite paths from the population.
create_pool(self, population, tournament_size, pool_size)
:- Creates a mating pool.
order_crossover(self, parent1, parent2)
:- Performs order crossover on two parents.
swap_mutation(self, child)
:- Performs swap mutation on a child.
generate_children(self, percentage, mating_pool)
:- Generates children from the mating pool.
distance_coordinates(self, coordinate1, coordinate2)
:- Calculates distance between coordinates.
distance_path(self, path, number_cities)
:- Calculates path distance.
valid_path(self, path)
:- Validates a path.
collect_input(self)
:- Collects input information.
write_output(path_distance, path)
:- Writes best path info to output file.
print_stats(self, elapsed_time, initial_best_distance, population)
:- Prints statistics after Genetic algorithm execution.
Main (main.py
)
- Orchestrates the execution of the Genetic algorithm.
Algorithm Configuration (algorithm_config.py
)
- Configues the hyperparameters for the Genetic algorithm based on city size.
Here's how to clone the repository and run the main program on your local machine.
git clone [repository-URL]
cd [repository-name]
Using pip, you can install all required packages by running the following command:
pip install -r requirements.txt
📝 Note: If you're using a different dependency management tool, the installation command might differ.
Execute the main program with the following command:
python main.py
✅ Now, the program should be up and running!