Implement and evaluate two search algorithms.

Input data file:

Your input file will be a CSV $($comma separated values$)$ file

Each row in that input file will correspond to STATE information: STATE$\_$LABEL, and state $2$D Cartesian space coordinates: X and Y$.$ You can assume X and Y to be positive integers.

Problem description:

You are given a weighted complete graph G$.$ Your task is to solve a Traveling Salesman Problem $[$TSP$]($find minimum cost$/$weight Hamiltonian Cycle$)$ on G using algorithms specified below.

Assume that edge weights represent straight line distances between states.

Your task is to implement two search algorithms in Python:

Simulated Annealing, and

Genetic Algorithm,

and apply them to solve the TSP $($starting at Stuart Building $[$SB$]$ node$)$ problem using provided data.

Your program should:

Accept four $(4)$ command line arguments corresponding to two states $/$ state capitals $($initial and goal states$)$ so your code could be executed with

python file.py FILENAME ALGO P$1$ P$2$

where:

file.py is your python code file name,

FILENAME is the input CSV file name $($graph G data$),$

ALGO is mode in which your program should operate

$1$ Simulated Annealing,

$2$ Genetic Algorithm,

P$1$ is a value for a specific algorithm parameter:

Simulated Annealing: P$1$ is the initial temperature T value,

Genetic Algorithm: P$1$ is the number of iterations K$,$

P$2$ is a value for a specific algorithm parameter:

Simulated Annealing: P$2$ is the $\backslash$alpha parameter for the temperature cooling schedule,

Genetic Algorithm: P$2$ is the mutation probability Pm value,

If the number of arguments provided is NOT four your program should display the following error message:

ERROR: Not enough or too many input arguments.

and exit.

Run Simulated Annealing and Genetic Algorithm searches to find the Traveling Salesman Problem solution starting at INITIAL $($first state$/$line in the input CSV file$)$ state and measure execution time $($in seconds$)$ for both methods.

Report results on screen in the following format:

Initial state: INITIAL

Simulated Annealing:

Command Line Parameters:

Initial solution: LABEL$1,$ LABEL$2,$ LABEL$3,...,$ LABELN$-1,$ LABELN

Final solution: LABEL$1,$ LABEL$2,$ LABEL$3,...,$ LABELN$-1,$ LABELN

Number of iterations: AAAA

Execution time: T$1$ seconds

Complete path cost: Y$1$

Genetic Algorithm:

Command Line Parameters:

Initial solution: LABEL$1,$ LABEL$2,$ LABEL$3,...,$ LABELN$-1,$ LABELN

Final solution: LABEL$1,$ LABEL$2,$ LABEL$3,...,$ LABELN$-1,$ LABELN

Number of iterations: AAAA

Execution time: T$2$ seconds

Complete path cost: Y$2$

where:

START$\_$NODE is the label$/$name of the initial graph node,

AAAA is the number of iterations completed before termination,

LABEL$1,$ LABEL$2,$ LABEL$3,...,$ LABELN$-1,$ LABELN is a solution represented as a list of visited states $($with LABEL$1=$ START$\_$NODE and LABELN $=$ INITIAL$),$

Save your solutions to a file named:

Simulated Annealing: INPUTFILENAME$\_$SOLUTION$\_$SA$.$csv file.

Genetic Algorithm: INPUTFILENAME$\_$SOLUTION$\_$GA$.$csv file.

Where: INPUTFILENAME is the input file name WITHOUT extension $($for example for input file DATA$2.$CSV$,$ the GA solution file should be named DATA$2\_$SOLUTION$\_$GA$.$csv$.$

Algorithm Parameters $[$SPECIFY WHAT IS NOT GIVEN BELOW$]$:

Simulated Annealing parameters are:

Initial state: pick one at random

Initial temperature: T $=$ P$1$

What is a move? $2-$edge swap

Termination condition: Temperature T $>0.$

Temperature cooling schedule: exponential $($P$2=\backslash$alpha provided as command line argument$)$

Ti$=$Tinitial $*$ e$^(-$I$*$alpha$)$

Cost $/$ objective function:

Genetic Algorithm parameters are:

Individual representation $($it does not need to be binary$)$:

Population size N $=$

Fitness function:

Selection mechanism: Roulette Wheel,

Probability of crossover: Pc $=1,$

Crossover mechanism: $2-$point crossover with crossover points

Probability of mutation: Pm $=$ P$1,$

Termination condition: number of iterations $>$ P$2=$ K$.$

Results and Conclusions

and for every ALGO$-$P$1-$P$2$ value combination provide ONE min$/$average$/$max fitness function plot $($one plot with three traces; add labels and legend$).$ Pick a run that was interesting or best and explain your choice.

What are your conclusions? What have you observed? Which algorithm$/$parameter set performed better? Was the optimal path found? Write a summary below.campus