Programming Language : Python
Number of cities : 11
General flow of solving a problem using Genetic Algorithm
{ initialize population; evaluate population; while TerminationCriteriaNotSatisfied { select parents for reproduction; perform recombination and mutation; evaluate population; } } pip install -r requirements.txt conda install basemap or run bash setup.sh (if running a linux based system) data = pd.read_csv("data/cities_and_distances.csv") data.reset_index(inplace=True) data1 = data.iloc[:,2:] data1.index = data1.columns.values data1 Initialize population: The initial population is a set of random routes generated using numpy.
Evaluate population: The evaluation is a process of finding how good the solutions is. This is 
Mutation:
Crossover: Implemented PMX by goldberg - https://www.hindawi.com/journals/cin/2017/7430125/
ga_obj = GeneticAlgoLibrary.OverallGaRun(noverall=1, number_of_cities=11, initial_pop_size=1000, nelite=10, percentage_to_crossover=20, percentage_to_mutate=20, dist_mat=data1) for i in [10,100,1000]: ga_obj = GeneticAlgoLibrary.OverallGaRun(noverall=i, number_of_cities=11, initial_pop_size=10000, nelite=10, percentage_to_crossover=20, percentage_to_mutate=20, dist_mat=data1) ga_obj.run_overall_ga() Starting:
Final solution plotted with folium
Note:
1. The final solution was obtained after multiple runs of the Genetic Algorithm with different inital population sizes and overall runs.
_2. The map needs access to city_lat_lon data, in the code to the file that is availabe in the data folder, if you are running the code from a different folder, the path should be changed accordingly.
_3. basemap is now deprecated, will update the plots with new code when I find a package which can generate these kind of plots, if you have any suggestions, please forward them to Chaithanya Kumar
Update: Added plot support with folium and branca, updated the requirements file and lat lon file with required format data. Update 20-04-2021: Fitness value calculation is now using ray multiprocessing to speed up the process.