Implement and evaluate two search algorithms.

Input data file:

Your input file will be a CSV $($comma separated values$)$ file $($campus$.$csv $-$ The csv file has no header, SB is starting node, always strat from SB only$).$

You CANNOT modify nor rename input data files.

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:

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

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 cs$581\_$P$01\_$AXXXXXXXX.py FILENAME ALGO P$1$ P$2$

where:

cs$581\_$P$01\_$AXXXXXXXX.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:

SA: P$1-$ initial temperature T$,$

GA: P$1-$ no$.$ of iterations K$,$

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

SA: P$2-\backslash$alpha parameter for the temperature cooling schedule,

GA: P$2-$ mutation probability,

Example:

python cs$581\_$P$01\_$A$11111111.$py DATA.CSV $210000\mathrm{.}01$

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:

Last Name, First Name, AXXXXXXXX solution:

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:

AXXXXXXXX is your IIT A number,

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$.$

Solution file $($text file$)$ format:

XXXX

STATE$1$

STATE$2$

STATE$3$

STATEN

Where:

XXXX will be the final path $/$ solution cost

STATE$1,$ STATE$2,...,$ STATEN state LABELS $($one per line, names as in the input file$)$ represent solution path $($the one displayed on screen; here assumed to be of length $4)$ in order.

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 $*\backslash$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

Assume that the INITIAL state is the first state in the CSV file. Run both algorithms:

with three different values of P$2$ for both algorithms,

with number of iterations K $/$ T: $100,1000,10000[$repeat each $5$ times and find average min, max, and average path cost and search times$]$ for every P$2$ value,

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.

Report your findings in Table.

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