A Genetic-based Hyper-heuristics framework to optimize the parameters of Simulated Annealing Algorithm with application in Travelling Salesman Problem (TSP), using Matlab
1. Simulation Annealing (SA) Parameters
| Parameter of SA | Range |
|---|---|
| Initial temperature (𝜏0) | Between 1 and 20 |
| Final temperature (𝜏𝑓) | Between 0.1 and 0.5 |
| The number of neighbours to visit (𝑟𝜏) | An integer value between 10 and 500 |
| Temperature control function (TCF) | Either option 1 or 2, which is exponential multiplicative cooling or non-monotonic scheme respectively |
| Cooling rate (𝛼) | Between 0.8 and 0.99 |
| Acceptance probability function (APF) | Either function 1 or 2, which is Metropolis criterion or Barker function respectively |
2. Simulation Annealing Pseudo-code
(1) Start with an initial feasible tour which generated by Farthest Insertion Procedure
(2) Set the best solution as the first tour in Step 1
(3) Select the initial temperature (𝜏0), the final temperature (𝜏𝑓), the temperature control function and the cooling rate
(4) Set the current temperature (𝜏) as 𝜏0
(5) REPEAT
(6) Choose the number of neighbours to visit at each temperature (𝑟𝜏)
(7) Set the repetition counter (𝑟) as 0
(8) REPEAT
(9) Randomly generate a new neighbour set by using 2-opt and calculate Improvement Cost
(10) Calculate the Acceptance Probability;
(11) IF (Random Selected Number from 0 to 1 < APF) THEN
(12) Update the current tour and TSP cost
(13) IF (Best Cost > TSP cost) THEN replace best solution with new generated tour
(14) Increase repetition counter (by 1)
(15) UNTIL 𝑟=𝑟𝜏
(16) Reduce 𝜏 according to the temperature reduction schedule
(17) UNTIL 𝜏≤𝜏𝑓
3. Genetic Algorithm (GA) Elements
| Element | Value | Element | Value |
|---|---|---|---|
| Population Size | 50 | Mutation Rate | 0.001 |
| Tournament Size | 4 | Elitism | 0.1 |
| Crossover Rate | 0.6 | Stopping Condition | 10 minutes each |
4. Genetic Algorithm Pseudo-code
(1) Select an initial population of 50 individuals (each individual is a parameter set of SA) and evaluate the fitness of each individual (the cost of TSP tour generated by using SA with corresponding parameter set)
(2) Set the best solution found so far to the best individual
(3) Set time counter (Total_Time) as 0
(4) REPEAT
(5) IF Crossover condition hold THEN
(6) Select a subset of individuals from the current population using Tournament Selection to create a parent pool for reproduction
(7) Use each pair of parents and perform One-point Crossover to generate 2 children for each pair
(8) IF Mutation condition hold THEN
(9) Select a subset of new generation to perform mutation
(10) Randomly choose a parameter of the individual and change it (within the given range)
(11) Calculate the running time for Crossover and Mutation
(12) Evaluate the fitness of each child and update the best solution found so far, if necessary;
(13) Replace a subset of Individuals in the current population by a subset of the current children using Elitism strategy to produce a new generation
(14) Increase the time counter
(15) UNTIL Total_Time (for Crossover and Mutation) > 10 minutes