Zeki Optimizasyon Teknikleri - 1 (Hill Climbing)

    Optimizasyon Algoritmalarımızdan ilki Stochastic(içerisinde rastgelelik bulunan) tekniklerden birisi olan Hill Climbing algoritması. Bu yöntem pek çok uygulamada uygulama kolaylığı nedeniyle seçilebilir.

   Optimizasyonu istenen problemin gösterimi, elde olan çözüme göre komşu çözüm üreteci, ilk çözüm üreteci ve çözüm değerlendirme fonksiyonu uygulama için yeterli olmaktadır.

  Algoritmanın dezavantajları olarak yerel çözümlere takılabilmesini ve  çözümün seçilen başlangıç noktasına çok bağlı olmasını sayabiliriz.

   Hill Climbing yöntemden bahsedersek:

 İlk olarak başlangıç çözümü üretilir ve bu çözüm eniyi çözüm olarak kabul edilir. (Bu çözümün üretimi probleme göre rastgele olabileceği gibi problem konusunda uzman görüşü veya daha önce yapılmış çalışmalar yardımıyla da olabilir.)

   Daha sonra bu probleme komşu bir çözüm kümesi üretilir.(Değişik sayıda olabilir.) Çözüm kümesi elemanları değerlendirilir. Çözüm kümesinin en iyi elemanı eğer bir önceki adımdaki eniyi çözümden daha iyi ise, eniyi çözüm güncellenir. Sonrasında en iyi çözüme göre yeni komşular üretilir ve iteratif olarak devam edilir. Belirli iterasyon sayısına ulaşıldığında, yeterli bir çözüm elde edildiğinde veya artık çözümler değişmediğinde iterasyon sonlandırılır.

 Hill Climbing yöntemini kullanarak derste geçen bir basit problem için C++ uygulama kodu hazırladım. Problem: bd 30 karakterlik bir binary dizisi olmak üzere f(bd) = |20 * dizideki_bir_sayisi(bd) - 100| fonksiyonunu max yapan bd değeri? (Problemimizin çözümünün "111111111111111111111111111111" olduğu rahatça görülüyor.)

Bu yazının hazırlanmasında hocam Doç.Dr. M.Ali Akcayol' un Zeki Optimizasyon Teknikleri Dersi ders notları kullanılmıştır.

*Biçimlendirme güçlükleri nedeni ile kodda "<" ve ">" işaretleri yerine "-" işareti kullanılmıştır.

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