Skip to content

Instantly share code, notes, and snippets.

@volkansalma
Created March 27, 2011 09:00
Show Gist options
  • Save volkansalma/889070 to your computer and use it in GitHub Desktop.
Save volkansalma/889070 to your computer and use it in GitHub Desktop.
hill climbing algoritması
//f(bd) = |20 * bir_sayisi(bd) - 100| fonksiyonunu max yapan
// 30 karakterlik binary dizisinin(bd) hill climbing algoritmasi ile
//bulunmasi.
//Volkan SALMA. http://volkansalma.blogspot.com
#include <iostream>
#include <vector>
#include <stdlib.h> //for rand funct.
#include <time.h> //time for rand function seed.
#include <math.h> // for abs function
using namespace std;
#define BINARY_ARRAY_SIZE 30
#define ITERATION_NUM 15
#define SOLUTION_SET_ELEMENT_CNT 30
struct Solution
{
bool value[BINARY_ARRAY_SIZE];
};
vector<Solution> generate40NeighbourSolutionToInput(Solution); //generate new solution depending old one.
Solution generateFirstSolutionRandomly(void);
int countOnes(bool); //number of 1's
long evaluteMyFunctionAndGiveResult(Solution); // f(bd) = |20 * bir_sayisi(bd) - 100|
void printSolutionResult(Solution,int,bool);
int main()
{
Solution myBestSolution; //holds best solution.
vector<Solution> testSolutionSet;
myBestSolution = generateFirstSolutionRandomly();
for(int i = 0; i < ITERATION_NUM; i++)
{
testSolutionSet = generate40NeighbourSolutionToInput(myBestSolution);
for(int j = 0 ; j < SOLUTION_SET_ELEMENT_CNT; j++)
{
if(evaluteMyFunctionAndGiveResult(testSolutionSet[j]) > evaluteMyFunctionAndGiveResult(myBestSolution) )
{
myBestSolution = testSolutionSet[j];
break;
}
}
printSolutionResult(myBestSolution,i+1,false);
}
printSolutionResult(myBestSolution,-1,true);
return 0;
}
vector<Solution> generate40NeighbourSolutionToInput(Solution in)
{
Solution newSln;
vector<Solution> result;
for(int i = 0; i < SOLUTION_SET_ELEMENT_CNT; i++)
{
for(int j = 0; j < BINARY_ARRAY_SIZE; j++ )
{
if(i != j) newSln.value[j] = in.value[j];
else newSln.value[j] = !in.value[j];
}
result.push_back(newSln);
}
return result;
}
Solution generateFirstSolutionRandomly(void)
{
Solution result;
srand((unsigned)time(NULL));
for(int i = 0; i < BINARY_ARRAY_SIZE; i++)
{
result.value[i] = rand()%2;
}
return result;
}
int countOnes(Solution in)
{
int cnt = 0;
for(int i= 0; i < BINARY_ARRAY_SIZE; i++)
{
if(in.value[i] == 1) cnt++;
}
return cnt;
}
long evaluteMyFunctionAndGiveResult(Solution solution)
{
// f(bd) = |20 * bir_sayisi(bd) - 100|
return abs(20*countOnes(solution)-100);
}
void printSolutionResult(Solution bestSolution,int iteration, bool isBest)
{
if (isBest)cout<<"Best Solution is:"<<endl;
else cout<<iteration<<". iteration:"<<endl;
for(int i = 0; i < BINARY_ARRAY_SIZE; i++)
{
cout<<bestSolution.value[i];
}
cout<<endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment