hill climbing algoritması

hill.cpp

//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;
}