Sample Problem

For this algorithm, we'll look at a very famous problem that has been attacked by a wide variety of search algorithms. The N-Queens problem (or NQP) is defined as the placement of N queens on an N-by-N board such that no queen threatens any other queen using the standard rules of chess (see Figure 2.3).

Figure 2.3: One of 92 8-Queens solutions.

The 8-Queens problem was first solved in 1850 by Carl Friedrich Gau . The search algorithm, as can be inferred by the date of the solution, was trial and error. The N-Queens problem has since been solved using depth-first search (1987), divide and conquer (1989), genetic algorithms (1992), and a variety of other methods . In 1990, Rok Sosic and Jun Gu solved the 3,000,000-Queens problem using local search and conflict minimization [Schaller 2001].

Solution Encoding

The encoding for the N-Queens solution is a standard one that takes into account the final solution, and thus reduces the search space. Note from Figure 2.3 that only one queen can be found in each row and in each column. This constraint makes it much easier to create an encoding that will be manipulated by the simulated annealing algorithm.

Since each column contains only one queen, an N-element array will be used to represent the solution (see Figure 2.4).

Figure 2.4: N-Queens solution encoding.

The N-element array represents the row indices of queen placement. For example, in Figure 2.4, column 1 contains the value 5, which represents the row for which the queen will be placed.

Creating a random solution is also a very simple process. We initialize our solution with each queen occupying the same row as its column. We then walk through each column and pick a random number from 1 to N for each. The two elements are then swapped (the current column with the randomly selected column). When we reach the end, the solution will be randomly perturbed.

Finally, given the encoding, there are never horizontal or vertical conflicts on the board. Therefore, only diagonal conflicts need to be checked when assessing the energy of the solution.

Energy

The energy of a solution is defined as the number of conflicts that arise given an encoding. The goal is to find an encoding that exhibits energy of zero, or no conflicts on the board.

Temperature Schedule

For this problem, we'll begin with a temperature of 30 degrees C and step down to zero using a geometric schedule (as defined in Equation 2.2). Our source will utilize 0.98 as ± . As we'll see later, the temperature schedule shows a fast decline and slow convergence to the final temperature of zero.

At each temperature change, we'll perform 100 steps. This permits the algorithm a number of search steps at this plateau.

On the CD  

The source for the simulated annealing algorithm to solve the N-Queens problem can be found on the CD-ROM at ./software/ch2/emsa/. Also on the CD-ROM is an experimental population-based simulated annealing algorithm that has been used to solve the NQP for N of up to 80. This is on the CD-ROM at ./software/ch2/emsapop/.