Simulated Annealing Algorithm

Simulated Annealing Algorithm:

    This algorithm overcomes all the problems occurred in Hill Climbing (i.e Stuck on Flat, local maximum, stuck on shoulder). It randomly chooses current node, basis on the temperature  schedule and the probability of choosing  next node.

 Below picture show the actual algorithm of simulated annealing. you can download full project code on the link given at the end.

	#include <conio.h>
	#include <stdio.h>
	#include <time.h>
	#include <stdlib.h>
	#include <math.h>
	#include <iostream>
	using namespace std;
	class Node
	{
	public:
	int state;
	int value;
	Node *ch1;
	Node *ch2;
	Node *ch3;
	Node *ch4;
	Node()
	{
	ch1=NULL;
	ch2=NULL;
	ch3=NULL;
	ch4=NULL;
	value=0;
	}
	} *root;
	int level = 2;
	Node* best;
	void Problem(Node *current,Node * Parent,int c_level)
	{
	cout<<endl<<"Enter Value: ";
	cin>>current->value;
	current->ch1 = Parent;
	if( c_level < level)
	{
	current->ch2 = new Node;
	Problem(current->ch2, current, c_level + 1);
	current->ch3 = new Node;
	Problem(current->ch3, current, c_level + 1);
	current->ch4 = new Node;
	Problem(current->ch4, current, c_level + 1);
	}
	else
	{
	current->ch2 = Parent;
	current->ch3 = Parent;
	current->ch4 = Parent;
	}
	}
	Node * SimulatedAnnealing(Node * current)
	{
	int temprature = 50000;
	int rand1,E;
	float rand2, p;
	Node *next = new Node;
	srand(time(NULL));
	while(true)
	{
	temprature = temprature*0.99;
	if(temprature == 0)return best;
	rand1 = rand()%4+1;
	if(rand1==1 && current->ch1!=NULL)
	next=current->ch1;
	else if(rand1==2 && current->ch2!=NULL)
	next=current->ch2;
	else if(rand1==3 && current->ch3!=NULL)
	next=current->ch3;
	else if(rand1==4 && current->ch4!=NULL)
	next=current->ch4;
	E = next->value - current->value;
	if(E > 0)
	{
	current = next;
	cout<<endl<<"CURRENT NODE:"<<current->value;
	if(best->value<current->value)
	best = current;
	}
	else
	{
	p = pow(2.71,(E/temprature));
	rand2 = p;
	if(rand2 < p)
	{
	current = next;
	if(best->value<current->value)
	best = current;
	// cout<<endl<<"CURRENT NODE:"<<current->value;
	}
	}
	}
	}
	int main()
	{
	int c_level = 0;
	root = new Node;
	best = root;
	Problem(root, NULL, c_level);
	Node *best = SimulatedAnnealing(root);
	cout<<"Result : "<<best->value;
	getch();
	return 0;
	}

view raw sa_algo_ai hosted with ❤ by GitHub