Advanced Artificial Intelligence - Genetic algorithms Assignment 1: Performance of the swap operator and that of the inversion operator
Advanced Artificial Intelligence Isao Ono Department of Computer Science Tokyo Institute of Technology
Genetic algorithms for combinatorial problems
Assignment 1
Compare the performance of the swap operator and that of the inversion operator when they are applied to TSP. Summarize the results and discuss why the results are obtained.
-
Swap Chooses two cities randomly and swap them.
-
Inversion Choose two cities randomly and inverse the sequence of cities between the two cities.
-
Local search method Evaluation value Decision variableLocal optimumLocal optimum Global optimum Assignment (3)
-
Local search method (2)
- Let 𝑋𝑋current be a random tour. Initialize the iteration counter 𝑖𝑖𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑖𝑖𝑡𝑡𝑡𝑡←0.
- Apply the swap operator or the inversion operator to 𝑋𝑋current to generate a new tour 𝑋𝑋next.
- If the length of 𝑋𝑋nextis shorter than that of 𝑋𝑋current , 𝑋𝑋current← 𝑋𝑋next.
- 𝑖𝑖𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑖𝑖𝑡𝑡𝑡𝑡←𝑖𝑖𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑖𝑖𝑡𝑡𝑡𝑡+1.
- If 𝑖𝑖𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑖𝑖𝑡𝑡𝑡𝑡is smaller than the maximum iteration, go to step 2.
Assignment (4)
-
How to perform an experiment
-
Import a project file, “local_search_tsp.zip”, to the Eclipse.
-
Find TLocalSearchMain.java and open it.
-
Find the main method.
-
You can choose the swap operator or the inversion operator at line 1.
-
This program executes five independent trials.
-
How to perform an experiment (2) -Inversion_log.csv, Swaplog.csv -NoOfEvals -Iteration -Inversion[0 -4] -A tour length at each iteration in the trial [0 -4].
Assignment (7)
- How to perform an experiment (3)
- {Inversion,Swap}[0- 4]_{init,final}.csv
- Inversion0_init.csv
- The initial tour obtained in the trial 0 of the inversion operator.
- Swap1_final.csv
- The final tour obtained in the trial 1 of the swap operator.
- Includes the coordinates of the cities in the visiting order.
Assignment (8) How to perform an experiment (4) (Optional) You can choose a problem at the line 4. The current problem definition file: data/eil51.tsp Definition files can be downloaded from http://comopt.ifi.uni -heidelberg.de/software/TSPLIB95/tsp/ You can try other problems. If you try others, you need to tune “maxIteration ”.
Assignment (9) Put the following information on the first page. Course title, today's date, your student ID number and your name Due date Oct. 17 Upload a PDF file to T2Schola. If you have any questions, please send an e -mail to
