programlama: Tavlama Benzetimi

Kategori: C++, Optimizasyon, Programlama

Optimizasyon algoritmalarımızdan sıradaki algoritma Simulated Annealing olarak ta bilinen tavlama benzetimi algoritması. İsmi Metalurji biliminden gelmektedir. Metallerin tavlanması işleminden esinlenerek ortaya çıktığı için bu ismi almıştır. Genellikle ayrık optimizasyon problemleri için kullanılır.

Yöntemden kabaca bahsetmek için Hill Climbingyöntemimizi hatırlayalım. Hill-Climbing yönteminde ilk çözüm üretmiş, bir komşu üreteci fonksiyonu ile ilk çözümümüze komşu olan yeni bir çözüm kümesi üretmiştik.*Bu yeni kümeyi kendi içerisinde değerlendirip en iyi elemanını seçmiştik. Eğer bu seçtiğimiz en iyi eleman bizim eski çözümümüzden daha iyi bir çözümse yeni çözümümüz olarak bu değeri kabul etmiştik. Ayrıca Hill-Climbing yönteminin kolay uygulanmasının yanında kötü bir özelliği olarak local çözümlere takılma olarak belirtmiştik.
Algoritmanın bu lokal çözümlere takılmasının nedeni bulduğumuz bir eğim doğrultusunda ilerlememiz, bu yönde çözümleri kısıtlamamızdır. Lokal çözüme doğru hızla ilerlerken çözüm kümesinin diğer kısımlarını göz ardı ederiz. Eğer şans eseri ilk çözüm üretecimiz başlangıç çözümünü global çözüme yakın bir bölgede üretirse muhtemelen global çözüme ulaşırız. Bundandır ki, Hill Climbing algoritması başlangıç noktasına çok bağımlıdır demiştik.

Hill Climbing algoritmamız üzerine bir takım modifikasyonlar yaptığımızı düşünelim. Yine ilk çözüm üretecimiz bir çözüm oluştursun, komşu çözüm üretecimiz komşu çözümler kümesini oluştursun, yine üretilen komşu çözüm kümesini kendi içerisinde değerlendirerek buradan en iyi çözümü seçelim. Klasik Hill Climbing algoritmamızda komşu çözüm kümesinden seçilen en iyi çözüm eğer eski çözümümüzden daha kötü ise bu değeri kullanmayıp elimizdeki çözümü saklıyorduk. Şimdi biraz daha insaflı davranıp komşu kümeden seçilen kötü çözüme bir şans verelim. Bu şans P olsun. Belkide verdiğimiz bu şans hatırına kötü çözüm bizi komşusu olan daha iyi çözümlere götürebilir. Hem böylece Hill-Climbing in local çözümlere takılıp kalma özelliğinden kurtulabiliriz. Eğer kötü çözümlere verdiğimiz seçilme şansı(olasılığı) P çalışma boyunca sabit kalırsa bu sefer tam güzel çözümlere doğru ilerlerken oradan oraya oradan oraya atlarız. Bu nedenle bu P olasılığının(iyi çözümü feda ederek yerine kötü çözümü kabul etme olasılığı) dinamik olması gereklidir. Bu dinamiklik iterasyonla P nin azaltılması şeklinde(ve daha pek çok şekilde) yapılablir. Böylece problem çözümünün ilk kısımlarında çözüm bölgeleri arasında sıçrayış daha fazla olurken iterasyon sayımız artıp elde ettiğimiz çözümler iyice güzelleştikçe 0 a yaklaşır. (Arama bölgemiz daralır.)

İşte yukarıda modifiye edilmiş bir Hill-Climbing algoritması gördük. Tavlama Benzetimi algoritmasının temel prensibi tam olarak budur. Kötü çözümü seçme olasılığı sistemli bir şekilde sıcaklıkla azaltılır. Sıcaklık iterasyona bağlı(genellikle düzgün veya logaritmik azalan) bir ifadedir.

Tavlama benzetimi algoritmasının temel amacı çözüm uzayında aranmadık bölge bırakmamaktır.

Ayrıca Tavlama Benzetimi algoritmasında komşu çözüm kümesinin büyüklüğüde dinamik şekilde değiştirilebilir. (Probleme göre değişse de genel olarak çözümü çok fazla etkilememektedir) Bu şekilde bir kullanım benimsenirse yaygın kullanım küçük bir kümeyle başlayıp iterasyonla büyütmek şeklinde olur.

Sıcaklığın azaltılması, olasılık değerinin sıcaklıkla azaltılması, çözüm kümesinin değiştirilmesi için pek çok yöntem kullanılır.

Bunlara girmeden basit bir problemi tavlama benzetimi algoritması ile çözelim. Aşağıda C++ kodu çözüm olarak string şeklinde bir dizisyi oluşturmaya çalışmaktadır.

Örnek bu sitedeki genetik algoritma ile Hello! World yazısını oluşturma probleminden esinlenilmiştir. Çözümün kalitesini değerlendirmek için gerekli fonksiyon (Fitness function) linki verilen siteden direk alınmıştır. .

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

*Hill-Climbing için yazmış olduğum C++ kod örneğinde bir yanlışlık yaptığımın farkına vardım. Aslında çözüm kümesi kendi içerisinde değerlendirilip en iyi eleman seçilmesi gerekirken, ben ilk bulduğum iyi çözüm ile mevcut çözümü değiştirdim. Sonrada diğer iterasyona geçtim. Bu yanlışlık daha güzel çözümleri kullanamamıza neden oldu. Böyle bir hata çözüme yakınsama hızımızı düşürür.

codes:


/Simulated Annealing C++ Sample Code

//generates "VOLKANSALMA@BLOGSPOT@COM" string.

//inspired from http://www.generation5.org/content/2003/gahelloworld.asp

//by volkan salma

//http://volkansalma.blogspot.com

 

#include <iostream>     // for cout etc.

#include <vector>     // for vector class

#include <string>     // for string class

#include <algorithm>    // for sort algorithm

#include <time.h>     // for random seed

#include <math.h>     // for abs()

 

#define SA_POPSIZE  50  // sa population size

#define SA_MAXITER  300  // maximum iterations

#define COEF            0.01

#define SA_TARGET  std::string("VOLKANSALMA@BLOGSPOT@COM")

 

using namespace std;

 

struct sa_struct

{

 string str;      // the string

 unsigned int fitness;   // its fitness

};

 

typedef vector-sa_struct- sa_vector;// for brevity

 

void generateNeighbourSolutionsToMySolution(sa_struct myCurrentSolution,sa_vector &neighbourSolutionSet);

void calcFitnessOfEveryElementInNeighbourSet(sa_vector &neighbourSolutionSet);

void init_population(sa_vector &population, sa_vector &buffer);

void calc_fitness(sa_vector &population);

bool fitness_sort(sa_struct x, sa_struct y);

void sort_by_fitness(sa_vector &population);

sa_struct generateFirstSolution();

sa_struct getNeighbourSolutionSetsBestElement(sa_vector &population);

void print_best(sa_vector &sav);

 

 

int main()

{

    srand(unsigned(time(NULL)));

    sa_struct myCurrentSolution;

    sa_struct buffer;

 vector -sa_struct- neighbourSolutionSet;

 double myRandomNumber;

 

 myCurrentSolution = generateFirstSolution();

 

 double Temperature = 100;

 double boltzman;

 

 

 for (int i=0; i - SA_MAXITER; i++)

 {

     generateNeighbourSolutionsToMySolution(myCurrentSolution,neighbourSolutionSet);

 

  calcFitnessOfEveryElementInNeighbourSet(neighbourSolutionSet);

 

  buffer = getNeighbourSolutionSetsBestElement(neighbourSolutionSet);

 

  if( buffer.fitness < myCurrentSolution.fitness) myCurrentSolution = buffer;

 

  else ///here is critical section. ;)

                     // we can change or not change the ourSolution with worst one.

  {

            myRandomNumber = rand()%10;

            myRandomNumber /= 10.0;   // i want to generate a rondom value in [0,1] range.

            boltzman = COEF * (1.0/ (exp(buffer.fitness - myCurrentSolution.fitness)/Temperature));

 

            if( boltzman > myRandomNumber)

            {

                cout--"Boltzman: "--boltzman--" > MyRandom: "--myRandomNumber--endl;

                myCurrentSolution = buffer;

                cout--"**********************************************************************"--endl;

            }

  }

 

  Temperature -= (100.0 / SA_MAXITER);

 

  cout --i--" My Solution: " -- myCurrentSolution.str -- " (" -- myCurrentSolution.fitness << ") Temp:"--Temperature-- endl;

 

  if(myCurrentSolution.fitness == 0) break;

 

 }

 

    cout -- "My Best Solution Is: " -- myCurrentSolution.str -- " (" -- myCurrentSolution.fitness -- ")" -- endl;

    cin--boltzman;

 

    return 0;

 

 

}

 

void calcFitnessOfEveryElementInNeighbourSet(sa_vector &population)

{

 string target = SA_TARGET;

 int tsize = target.size();

 unsigned int fitness;

 

 for (int i=0; i - SA_POPSIZE; i++)

 {

  fitness = 0;

  for (int j=0; j-tsize; j++)

  {

   fitness += abs(int(population[i].str[j] - target[j]));

  }

 

  population[i].fitness = fitness;

 }

}

 

bool fitness_sort(sa_struct x, sa_struct y)

{

    return (x.fitness < y.fitness);

}

 

void sort_by_fitness(sa_vector &population)

{

    sort(population.begin(), population.end(), fitness_sort);

}

 

sa_struct getNeighbourSolutionSetsBestElement(sa_vector &population)

{

    sa_struct bestMemberOfSolutionSet;

    sort_by_fitness(population);

    bestMemberOfSolutionSet = population[0];

 

    return bestMemberOfSolutionSet;

}

 

sa_struct generateFirstSolution()

{

        int tsize = SA_TARGET.size();

        sa_struct result;

 

  result.fitness = 0;

  result.str.erase();

 

  for (int j=0; j-tsize; j++)

  {

   result.str += (rand() % 26) + 64;

  }

 

  string target = SA_TARGET;

 

  for (int j=0; j-tsize; j++)

  {

   result.fitness += abs(int(result.str[j] - target[j]));

  }

 

 

  return result;

}

 

void generateNeighbourSolutionsToMySolution(sa_struct myCurrentSolution,sa_vector &neighbourSolutionSet)

{

    int tsize = SA_TARGET.size();

    sa_struct buffer;

    neighbourSolutionSet.clear();

 

    for (int i=0; i-SA_POPSIZE; i++)

 {

     buffer.str = myCurrentSolution.str;

     buffer.str[i%tsize] = (rand() % 26) + 64;

     neighbourSolutionSet.push_back(buffer);

 }

}

Programın şu şekilde bir çıktısı oluyor: (Yıldızlarla gösterilen bölgelerde bulunan çözüm daha kötü olmasına rağmen olasılık değerlendirmesini geçmiş, çözüm olarak seçilmiştir. )


0 My Solution: SGGYVNFHLND@HEL@RFOYMGEO (143) Temp:99.6667

1 My Solution: SGGYHNFHLND@HEL@RFOYMGEO (129) Temp:99.3333

2 My Solution: SGGYHNFHLND@HEL@RFOYAGEO (117) Temp:99

3 My Solution: SGGYHNRHLND@HEL@RFOYAGEO (105) Temp:98.6667

4 My Solution: SGGLHNRHLND@HEL@RFOYAGEO (92) Temp:98.3333

5 My Solution: SGGLHNRHLND@HEL@RFOYAGRO (85) Temp:98

6 My Solution: SGGLHNRHLND@HEL@RMOYAGRO (78) Temp:97.6667

7 My Solution: SGGLHNRHLND@HML@RMOYAGRO (72) Temp:97.3333

8 My Solution: SNGLHNRHLND@HML@RMOYAGRO (65) Temp:97

9 My Solution: SNGLBNRHLND@HML@RMOYAGRO (59) Temp:96.6667

10 My Solution: SNLLBNRHLND@HML@RMOYAGRO (54) Temp:96.3333

11 My Solution: SNLLBNRHLND@HMLERMOYAGRO (49) Temp:96

12 My Solution: VNLLBNRHLND@HMLERMOYAGRO (46) Temp:95.6667

13 My Solution: VNLLBNRHLND@BMLERMOYAGRO (40) Temp:95.3333

14 My Solution: VNLLBNRHLND@BMLERMORAGRO (37) Temp:95

15 My Solution: VNLLBNRHLND@BMLERMORAARO (35) Temp:94.6667

16 My Solution: VNLLBNRALND@BMLERMORAARO (28) Temp:94.3333

17 My Solution: VNLLBNRALNB@BMLERMORAARO (26) Temp:94

18 My Solution: VNLLANRALNB@BMLERMORAARO (25) Temp:93.6667

19 My Solution: VNLLANRALNA@BMLERMORAARO (24) Temp:93.3333

20 My Solution: VNLLANRALNA@BMOERMORAARO (21) Temp:93

21 My Solution: VNLLANRALNA@BMOERMORAAOO (18) Temp:92.6667

22 My Solution: VNLLANRALNA@BMOERMORAAOM (16) Temp:92.3333

23 My Solution: VNLLANRALNA@BMOERMORACOM (14) Temp:92

24 My Solution: VNLLANRALNA@BMOERMOTACOM (12) Temp:91.6667

25 My Solution: VNLLANRALNA@BMOESMOTACOM (11) Temp:91.3333

26 My Solution: VNLLANRALNA@BMOESPOTACOM (8) Temp:91

Boltzman: 0.91 &gt; MyRandom: 0.8

**********************************************************************

27 My Solution: VNLLANRALNA@BMOESPOTACOM (8) Temp:90.6667

28 My Solution: VOLLANRALNA@BMOESPOTACOM (7) Temp:90.3333

29 My Solution: VOLLANRALNA@BMOGSPOTACOM (5) Temp:90

Boltzman: 0.9 &gt; MyRandom: 0.7

**********************************************************************

30 My Solution: VOLLANRALNA@BMOGSPOTACOM (5) Temp:89.6667

Boltzman: 0.896667 &gt; MyRandom: 0

**********************************************************************

31 My Solution: VOLLANRALNA@BKOGSPOTACOM (5) Temp:89.3333

Boltzman: 0.893333 &gt; MyRandom: 0.5

**********************************************************************

32 My Solution: VOLLANRALNA@BKOGSPOTACOM (5) Temp:89

33 My Solution: VOLLANRALNA@BKOGSPOTACOM (5) Temp:88.6667

Boltzman: 0.326186 &gt; MyRandom: 0.3

**********************************************************************

34 My Solution: VNLLANRALNA@BKOGSPOTACOM (6) Temp:88.3333

Boltzman: 0.883333 &gt; MyRandom: 0.2

**********************************************************************

35 My Solution: VNLLANRALNA@BKOGSPOTACOM (6) Temp:88

36 My Solution: VNLKANRALNA@BKOGSPOTACOM (5) Temp:87.6667

Boltzman: 0.876667 &gt; MyRandom: 0.6

**********************************************************************

37 My Solution: VNLKANRALNA@BKOGSPOTACOM (5) Temp:87.3333

38 My Solution: VOLKANRALNA@BKOGSPOTACOM (4) Temp:87

39 My Solution: VOLKANSALNA@BKOGSPOTACOM (3) Temp:86.6667

40 My Solution: VOLKANSALNA@BKOGSPOTACOM (3) Temp:86.3333

Boltzman: 0.863333 &gt; MyRandom: 0.8

**********************************************************************

41 My Solution: VOLKANSALNA@BKOGSPOTACOM (3) Temp:86

42 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:85.6667

Boltzman: 0.31515 &gt; MyRandom: 0.3

**********************************************************************

43 My Solution: VPLKANSALMA@BKOGSPOTACOM (3) Temp:85.3333

Boltzman: 0.313924 &gt; MyRandom: 0

**********************************************************************

44 My Solution: VQLKANSALMA@BKOGSPOTACOM (4) Temp:85

45 My Solution: VQLKANSALMA@BKOGSPOTACOM (4) Temp:84.6667

46 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:84.3333

Boltzman: 0.843333 &gt; MyRandom: 0.1

**********************************************************************

47 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:84

Boltzman: 0.309019 &gt; MyRandom: 0

**********************************************************************

48 My Solution: VPLKANSALMA@BKOGSPOTACOM (3) Temp:83.6667

49 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:83.3333

Boltzman: 0.833333 &gt; MyRandom: 0.3

**********************************************************************

50 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:83

51 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:82.6667

Boltzman: 0.826667 &gt; MyRandom: 0.2

**********************************************************************

52 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:82.3333

Boltzman: 0.823333 &gt; MyRandom: 0.5

**********************************************************************

53 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:82

54 My Solution: VOLKANSALMA@BLOGSPOTACOM (1) Temp:81.6667

Boltzman: 0.816667 &gt; MyRandom: 0.7

**********************************************************************

55 My Solution: VOLKANSALMA@BLOGSPOTACOM (1) Temp:81.3333

Boltzman: 0.813333 &gt; MyRandom: 0.3

**********************************************************************

56 My Solution: VOLKANSALMA@BLOGSPOTACOM (1) Temp:81

57 My Solution: VOLKANSALMA@BLOGSPOT@COM (0) Temp:80.6667

My Best Solution Is: VOLKANSALMA@BLOGSPOT@COM (0)

programlama

Tuesday, February 12, 2013

Tavlama Benzetimi

1 comment: