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.