CSCI5260- Project 2: Genetic Search Solved

Project 2 – Genetic Search

Bucky’s Quest
Background
Bucky is almost 110 years old, but is having a terrible time convincing local public health officials that he is part of the current phase of the COVID vaccine rollout. He heard that physicians offices in Johnson City will administer the vaccine at some point, so Bucky has made it a daily task to visit each of the physicians offices in town to check on vaccine availability. Because he has so many responsibilities on campus, he needs to make his route as optimal as possible— resulting in the shortest distance. He will begin and end at ETSU’s campus so he can attend to other things both before he leaves and after he returns. Preparation

Download the project2_tsp.py file from D2L.

Necessary Libraries

Probably needed from pip install—osmnx – A library that allows you to pull data from the Open Street GPS and store it as an undirected graph of GPS coordinates.https://osmnx.readthedocs.io/en/stable/
graph_objects – plotly is a data visualization library, and the graph_objects class represents parts of a figure.https://plotly.com/python/
networkx
pandas
Built-in Python libraries—csv – used for CSV file reading/writing
collections – allows you to use python’s double-ended and other queue structures.
random – the Python random number generator
numpy – the Python library for matrix manipulation and other scientific operations
operator – allows for targeted list sorting
math – for floor, ceiling, square root, etc.
pyplot (optional) – for providing additional data plot functionality.
Requirements
You must complete the code for the following:

run_ga()This should initialize the population and then repopulate until the max number of generations is reached.
calculate_fitness()This code should determine the appropriate fitness for a particular chromosome.
The chromosome should represent the ordering of the points list.
initialize_population()This code will initialize an entire population (a single generation) of chromosomes.
The number of chromosomes to generate is controlled by the POPULATION_SIZE
Each chromosome will be of size len(points). Note that the chromosome will not contain the start/end locations.
You should calculate the fitness for each chromosome in the population. Add the chromosomes to the population in the format [chromosome, fitness].
Sort the population based on the fitness and add it to the generations list.generations[x][0] will be the best route for a particular generation x.
repopulate(gen)Creates a new population for generation gen, by doing the followingSelection(gen-1)
Crossover(parent1, parent2)
Mutate(child) [at an acceptable mutation rate] iv. Appends the child to the new population until full
Sorts the new population by fitness
Appends the population to the generations list.
selection(gen)Selects and returns two parent chromosomes from generation gen (the generation number).
crossover(p1,p2)Employs a crossover strategy on parents p1 and p2 (passed in the form of chromosomes). b. Returns a child chromosome.
mutate(chromosome)Accepts a chromosome that represents the ordering of the points list.
Returns the mutated version of the chromosome.
Provided Functions
plot_path(lat, long, origin_point, destination_point, fitness)
 

Given (1) a path-ordered list of latitudes, (2) a path-ordered list of longitudes, (3) an origin point as a tuple in the format (osmid, {"y": latitude, "x": longitude, "osmid": long_integer}), (4) a destination point as a tuple in the format (osmid, {"y": latitude, "x": longitude, "osmid": long_integer}), and (5) the fitness score for the route, open a browser and display a map of the route.

 

plot_ga()
Plots the results of the genetic algorithm run, including the best and worst for each generation.

haversine(point1, point2)
 

Returns the Great Circle Distance in miles between point1 and point2. Both points should be an osmid.

 

show_route(generation_number)
 

Displays the route for generation_number as a map. Note that this only depicts the haversine distances rather than navigation routing.

 

main()
 

Reads the file addresses_geocoded.csv, which corresponds to the addresses in addresses.csv and initializes the points array as nodes.