5 Simulated annealing

 

This chapter covers

  • Introducing trajectory-based optimization algorithms
  • Understanding the simulated annealing algorithm
  • Solving function optimization as an example of continuous optimization problems
  • Solving puzzle game problems like Sudoku as an example of constraint-satisfaction problems
  • Solving permutation problems like TSP as an example of discrete problems
  • Solving a real-world delivery semi-truck routing problem

In this chapter, we’ll look at simulated annealing as a trajectory-based metaheuristic optimization technique. We’ll discuss different elements of this algorithm and its adaptation aspects. A number of case studies will be presented to show the ability of this metaheuristic algorithm to solve continuous and discrete optimization problems.

5.1 Introducing trajectory-based optimization

Imagine yourself on a hiking trip looking for the lowest valley in a rugged landscape that has many valleys and hills. You don’t have access to global information or a map that shows the location of the lowest valley. You start your hiking journey by randomly choosing a direction. You keep moving step by step until you get stuck in a local valley surrounded by hills. You are not highly satisfied with the location, as you believe that there is a lower valley in the area that may be behind the hills. Your curiosity drives you to move up one of the hills to find the lowest valley.

5.2 The simulated annealing algorithm

5.2.1 Physical annealing

5.2.2 SA pseudocode

5.2.3 Acceptance probability

5.2.4 The annealing process

5.2.5 Adaptation in SA

5.3 Function optimization

5.4 Solving Sudoku

5.5 Solving TSP

5.6 Solving a delivery semi-truck routing problem

Summary