| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

Algorithms

Page history last edited by fred.f.chopin@... 12 years, 10 months ago

Some of the algorithms that we talked about:

Simulated Annealing:  Wikipedia has a decent description here: http://en.wikipedia.org/wiki/Simulated_annealing

The general idea is that in a search space, it is possible to get "stuck" between states that are equally "good" but not the correct solution.  For example, the problem under consideration is the n-queens problem, where you can place n queens on a chessboard of size nxn such that they do not attack each other.  In general, a "state" is the position of some number of queens on the board.  For any state S, a substate of S is defined as the movement of any arbitrary queen to any arbitrary square on the chess board.  A state's energy level (or how "good" it is) is determined by some sort of heuristic, in this case I chose the number of pairs of queens that are attacking each other.   

 

The way that this could get "stuck" is if there are multiple child states that are different, but have the same "energy" value, and thus moving from one state to another may slightly decrease the energy value (our goal is zero energy, or no pairs of queens under attack).  This may result in either not selecting a new substate (if all substates are worse than the current state) or getting stuck in a circular pattern such that you're cycling back and forth from parent to child state.  This can occur specifically because Simulated Annealing is a local search algorithm, which means that it does not care about the path it took to get to the solution; only the solution state itself.  Therefore, it does not keep track of previous states visited, except for the current state being considered and the state which has the lowest energy so far that we've seen.  

 

The way Simulated Annealing gets "unstuck" is that it will select a new state based on a certain probability, which means that it has a very high chance of selecting a better state, but a non-zero chance of selecting a state with the same or even worse energy value.  This probability is called the "temperature" and we want to decrease it over time at a given rate, called the "cooling schedule" such that with time, the probability of accepting a worse state becomes lower and lower.  The probability is defined as e^(dt/temp), where dt is the difference between the current energy value of the state under consideration and the best energy value that has been seen so far.  We then roll the dice and if the number we generate is within the probability of accepting that state, we accept the state regardless of if it's a "better" state or not, although we will not update the best energy value unless the new state has a better energy value.  This also means that the probability that we'll accept a new state of lower energy is extremely high in general.  We run several iterations of selecting child states at each temperature value.  One can tweak this algorithm by both changing the number of states that we examine for each temperature, or by modifying the rate and manner at which the temperature decreased (called the "cooling schedule").  Here's an implementation in C++.  I did not bother with TDD for the most part, nor did I refactor in any particularly meaningful way, so the code isn't that great, but it does work and does illustrate the algorithm. Some of the other functions that are called should be readily apparent as to what they do based on their names and the context in which they are used:

 

#pragma once

#include "searchbase.h"

 

 

class SearchSA :

public SearchBase

{

public:

SearchSA(void);

~SearchSA(void);

searchResult DoSearch(State initialState);

float Temperature;

Node* currentSolution;

int TurnCount;

int AcceptedSolutions;

float BestEnergyLevel;

float CoolingSchedule;

};

 

#include "StdAfx.h"

#include "SearchSA.h"

#include "NQueensGoal.h"

 

SearchSA::SearchSA(void)

{

float Temperature;

Node* currentSolution;

int TurnCount;

int AcceptedSolutions;

}

 

 

searchResult SearchSA::DoSearch(State initialState)

{

searchResult result;

result.StillRunning = true;

result.LastNode = currentSolution;

result.NoSolution = true;

 

if(!searching)

{

currentSolution = new Node();

currentSolution->Cost = 0;

currentSolution->Depth = 0;

currentSolution->parent = NULL;

currentSolution->state = initialState;

currentSolution->HeuristicCost = heuristic->GetCostFor(initialState);

currentSolution->Cost = currentSolution->HeuristicCost;

searching = true;

BestEnergyLevel = currentSolution->HeuristicCost;

}

 

AcceptedSolutions = 0;

Node ws;

 

// make it stop at some point

if(Temperature <= 0.000001)

{

result.StillRunning = false;

return result;

}

 

for(int i = 0; i < TurnCount; ++i)

{

ws.state = currentSolution->state;

 

if(NQueensGoal::IsSatisfiedBy(ws.state, nQueens))

{

result.StillRunning = false;

result.NoSolution = false;

currentSolution->state = ws.state;

currentSolution->HeuristicCost = ws.HeuristicCost;

result.LastNode = currentSolution;

return result;

}

 

// option 1:  we can generate all substates and pick the cheapest we find

//vector<Node*> substates = GenerateCompleteChildStateNodes(&ws);

//assert(substates.size() > 0);

//Node* cheapest = substates[0];

//for(int k = 1; k < substates.size(); ++k)

//{

// if(substates[k]->HeuristicCost < cheapest->HeuristicCost)

// {

// delete cheapest;

// cheapest = substates[k];

// }

// else

// {

// delete substates[k];

// }

//}

//ws.state = cheapest->state;

//delete cheapest;

 

 

// Option 2: pick random state from all possible sub states

vector<Node*> substates = GenerateCompleteChildStateNodes(&ws);

ws.state = substates[rand() % substates.size()]->state;

 

 

// OPTION 3:  Swap two rows randomly.  This only works if queens are uniformly distributed between rows and cols

 

//  randomly tweak

//int r1 = rand() % nQueens;

//int r2 = r1;

//while(r2 == r1)

//{

// r2 = rand() % nQueens;

//}

//// now swap the cols;

//int temp = ws.state.Queens[r1].y;

//ws.state.Queens[r1].y = ws.state.Queens[r2].y;

//ws.state.Queens[r2].y = temp;

//

 

 

// compare energy

ws.HeuristicCost = heuristic->GetCostFor(ws.state);

 

if(ws.HeuristicCost < BestEnergyLevel)

BestEnergyLevel = ws.HeuristicCost;

 

// Does workingSolution have less energy?  If so, working solution is now currentSolution

if(ws.HeuristicCost < currentSolution->HeuristicCost)

{

currentSolution->state = ws.state;

currentSolution->HeuristicCost = ws.HeuristicCost;

}

else

{

// else what is the probability of accepting it?

float de = 0.0;

de = currentSolution->HeuristicCost - ws.HeuristicCost;

 

// Did we hit that probability?  

float rprob = (float)((float)rand() / (float)RAND_MAX);

float prob = exp(de / Temperature);

if( rprob < prob )

{

// yes:  take that solution

currentSolution->state = ws.state;

currentSolution->HeuristicCost = ws.HeuristicCost;

AcceptedSolutions++;

}

// no:  ignore solution

}

 

}

 

// reduce T

Temperature = CoolingSchedule * Temperature;

result.LastNode = currentSolution;

 

return result;

}

 

 

Comments (0)

You don't have permission to comment on this page.