Yöntemden kabaca bahsetmek için Hill Climbing yö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.
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 "VOLKANSALMA@BLOGSPOT@COM" dizisini 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. .
Bunlara girmeden basit bir problemi tavlama benzetimi algoritması ile çözelim. Aşağıda C++ kodu çözüm olarak string şeklinde "VOLKANSALMA@BLOGSPOT@COM" dizisini 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 hocam 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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //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); | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 > 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 > MyRandom: 0.7 | |
| ********************************************************************** | |
| 30 My Solution: VOLLANRALNA@BMOGSPOTACOM (5) Temp:89.6667 | |
| Boltzman: 0.896667 > MyRandom: 0 | |
| ********************************************************************** | |
| 31 My Solution: VOLLANRALNA@BKOGSPOTACOM (5) Temp:89.3333 | |
| Boltzman: 0.893333 > MyRandom: 0.5 | |
| ********************************************************************** | |
| 32 My Solution: VOLLANRALNA@BKOGSPOTACOM (5) Temp:89 | |
| 33 My Solution: VOLLANRALNA@BKOGSPOTACOM (5) Temp:88.6667 | |
| Boltzman: 0.326186 > MyRandom: 0.3 | |
| ********************************************************************** | |
| 34 My Solution: VNLLANRALNA@BKOGSPOTACOM (6) Temp:88.3333 | |
| Boltzman: 0.883333 > MyRandom: 0.2 | |
| ********************************************************************** | |
| 35 My Solution: VNLLANRALNA@BKOGSPOTACOM (6) Temp:88 | |
| 36 My Solution: VNLKANRALNA@BKOGSPOTACOM (5) Temp:87.6667 | |
| Boltzman: 0.876667 > 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 > MyRandom: 0.8 | |
| ********************************************************************** | |
| 41 My Solution: VOLKANSALNA@BKOGSPOTACOM (3) Temp:86 | |
| 42 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:85.6667 | |
| Boltzman: 0.31515 > MyRandom: 0.3 | |
| ********************************************************************** | |
| 43 My Solution: VPLKANSALMA@BKOGSPOTACOM (3) Temp:85.3333 | |
| Boltzman: 0.313924 > 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 > MyRandom: 0.1 | |
| ********************************************************************** | |
| 47 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:84 | |
| Boltzman: 0.309019 > MyRandom: 0 | |
| ********************************************************************** | |
| 48 My Solution: VPLKANSALMA@BKOGSPOTACOM (3) Temp:83.6667 | |
| 49 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:83.3333 | |
| Boltzman: 0.833333 > MyRandom: 0.3 | |
| ********************************************************************** | |
| 50 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:83 | |
| 51 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:82.6667 | |
| Boltzman: 0.826667 > MyRandom: 0.2 | |
| ********************************************************************** | |
| 52 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:82.3333 | |
| Boltzman: 0.823333 > MyRandom: 0.5 | |
| ********************************************************************** | |
| 53 My Solution: VOLKANSALMA@BKOGSPOTACOM (2) Temp:82 | |
| 54 My Solution: VOLKANSALMA@BLOGSPOTACOM (1) Temp:81.6667 | |
| Boltzman: 0.816667 > MyRandom: 0.7 | |
| ********************************************************************** | |
| 55 My Solution: VOLKANSALMA@BLOGSPOTACOM (1) Temp:81.3333 | |
| Boltzman: 0.813333 > 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) |
Output
1 yorum - yorum yaz:
on numara anlatım olmuş gerçekten okulda anlamamıştım şıp diye kaptım, takipteyim :)
teşekkürler.
Yorum Gönder