Herself’s Artificial Intelligence

This AI process mimicks the physical process of annealing. Annealing is the process of heating and cooling a metal in a controlled manner. This gives us a stronger metal if the cooling part is done slowly. A higher temperature means more energy. So if I am trying to place a marble on a hilly landscape in the global minimum I may have to shake things up a great deal to bounce the marble out of a local minimum. So I start out with lots of energy hoping to locate the global minimum. Then reduce the energy hoping to zero in on the minimum better.

Start with a random solution or your best solution from a previous run. This is our current solution. The energy of our solution is then measured. For the eight queens problem the amount of energy is the amount of conflicts between our queens.

We then take a copy of the solution, bounce it around a bit and see if it has less energy than the previous solution. If so we use that as our working solution. If not we test it using P(dE) = exp( -dE/T). At higher temperatures we take worse solutions than we do when we get close to finding the correct solution.

Simulated Annealing is used in traveling salesman and scheduling problems and also it has been used to do some image clean up work.

Algorithm:
Set up initial board
Copy initial solution to current, working and best solutions

Loop:
Bounce the queens around a the board
See if this solution is better than last one ( uses less energy / has less conflicts )
if so use new solution
if not test again using P(dE) = exp( -dE/T )
if this gives a lower energy than a random number we pick, use this solution
Switch copy boards as needed
Adjust temperature
Bail from loop if problem solved ( energy < some number )

Java source code 8 queens, Simulated Annealing

Simulated Annealing was developed by S. Kirkpatrick, CD Gelatt and MP Vecchi in 1983 and by Cerny 1985. It is a Monte Carlo type of solution to a problem.

Wiki - Simulated Annealing
Taygeta Scientific - Simulated Annealing Information