Application

Application of Simulated Annealing

Cube Representation

To represent the cube, a d x d x 6 three-dimensional matrix is used where d is the dimension of the cube (we will be using a 3 x 3 cube) and the “6” represents the number of faces we have. Each layer of this matrix will represent a color, with the numbers 1 through 6 representing the colors of each face. Below is a visual representation of this matrix expanded into a 2D matrix.

Figure 2: Visual representation of the representation of the Rubik's Cube. Note that each number/color is related to a face on the cube, and there are 6 faces on a cube. In our implementation, each face is one layer of a 3x3x6 matrix.

Determining the Neighbor State

Single face turns will be applied to the cube's matrix representation in the form of standard cube notation U, D, L, R, F, B (up, down, left, right, front, back) face turns in the clockwise direction. Face turns are also able to be turned twice as denoted with a 2 (ex. U2 -> turn the upward face twice) and can also be turned counter clockwise with a single quotation (ex. F' -> turn the front face counter clock wise). These moves create the neighboring representations that the simulated annealing algorithm can use to explore the sample space.

Cost Function

The cost function used is the sum of colored indices, called facelets, in the wrong position. This method is used in the reference paper on solving a Rubik's Cube using simulated annealing and genetic algorithms [1]. With this cost function representation, the goal of the SA algorithm is to minimize the cost, which therein implies smaller costs mean more faces in the correct position. By keeping track of facelets on the wrong face, keeping track of corner and edge pieces are not necessary and avoids the complexity of pieces being in the correct position but wrong orientation.

Probability of Acceptance and Temperature

The driving force of simulated annealing is the use of probabilities to accept neighboring states that do not have a favorable cost. This allows the algorithm to explore the sample space and approximate the global min/max without getting stuck at a local min/max. As the algorithm searches, the temperature of the system decreases making the algorithm more and more greedy by accepting less favorable evaluations with lower probability. These concepts can be represented mathematically in the equations below. The left equation represents the calculation of the probability (p) to accept a move given a change in cost in cost and temperature. The temperature after each evaluation is updated with the cooling rate as seen in the right equation below.

Whenever the algorithm decides to accept a neighboring state (i.e. if it reduces the cost function or won the probability wager if it does not reduce the cost function), the move performed is added to a vector of moves that the algorithm has previously chosen from its start state. With this in mind, the SA algorithm is building a vector of moves that aim to solve the scrambled cube.

Pseudocode

Below is the pseudocode presented in [1] and is the model we are basing our SA algorithm off of.

Page updated

Google Sites

Report abuse