Optimizasyon Teknikleri

of 65

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
65 pages
0 downs
3 views
Share
Description
Optimizasyon Teknikleri. Doç. Dr. Bilal ALATAŞ Sezgisel Optimizasyon Ders Notları - 7. İÇERİK. Optimizasyon özet Klasik Optimizasyon özet Sezgisel Optimizasyona Giriş Tepe Tırmanma Algoritması Tabu Arama Algoritması Isıl İşlem Algoritması Metasezgisel algoritmaların tanımı
Transcript
Optimizasyon TeknikleriDoç. Dr. Bilal ALATAŞSezgisel OptimizasyonDers Notları - 7İÇERİK
  • Optimizasyon özet
  • Klasik Optimizasyon özet
  • Sezgisel Optimizasyona Giriş
  • Tepe Tırmanma Algoritması
  • Tabu Arama Algoritması
  • Isıl İşlem Algoritması
  • Metasezgisel algoritmaların tanımı
  • Metasezgisel algoritmaların sınıflandırılması
  • Çok Noktalı (Popülasyon Tabanlı) Algoritmalara örnekler
  • OPTİMİZASYON
  • Optimizasyon
  • karar değişkenleri
  • amaç fonksiyonu
  • sınırlayıcılar
  • Matematiksel modeller
  • İKİ TEMEL BASAMAK
  • Problem modelinin kurulması
  • Çözüm üretmek için modelin kullanılması
  • Klasik Optimizasyon Algoritmaları
  • Sistemin modeli ve amaç fonksiyonu için matematiksel modellere ihtiyaç duymaktadır.
  • Karmaşık sistemler için matematiksel modelin kurulması çoğu zaman zordur. Model kurulsa bile çözüm zamanı maliyeti çok yüksek olduğundan kullanılamamaktadır.
  • Büyük ölçekli kombinasyonsal ve doğrusal olmayan problemlerde yetersizdir.
  • Verilen bir probleme bir çözüm algoritması uyarlamada etkin değildir.
  • Varsayımlar
  • İlgilenilen problem algoritmanın onu idare edeceği şekilde modellenir. Klasik optimizasyon algoritmalarının çözüm stratejisi genellikle amaç ve sınırlayıcıların tipine ve problemi modellemede kullanılan değişkenlerin tipine bağlıdır.
  • Klasik Optimizasyon Algoritmaları (devam)
  • Bunların etkinliliği aynı zamanda problem modellemede çözüm uzayı, karar değişken sayısı ve sınırlayıcı sayısına oldukça bağlıdır.
  • Diğer önemli bir eksiklik ise farklı tipte karar değişkenleri, amaç ve sınırlayıcıların olması durumunda problem formülasyonlarına uygulanabilecek genel çözüm stratejileri sunmamalarıdır.
  • Özetle…
  • Hiç biri robust (Yeni problem için yeni bir yöntem tasarlanmalı) değildir.
  • Problem matematiksel terimlerle çok iyi tanımlanmalıdır.
  • Özellikle gerçek dünya problemlerini çok iyi tanımlamak mümkün değildir.
  • Küresel optimumu garanti edebilir ama aşırı derecede hesaplama zamanına ihtiyaç duyarlar.
  • Kısa sürede bölgesel optimaya yakınsama eğilimindedirler.
  • AMAÇ
  • Erken yakınsamadan kaçış,
  • Bölgesel araştırmada optimuma hızlı yakınsama,
  • Dinamik gerçek dünya optimizasyonu.
  • Klasik sezgisel ve genel amaçlı sezgisel optimizasyon algoritmaları
  • Hesaplama gücü iyidir.
  • Dönüşümleri kolaydır.
  • Klasik ve sezgisel optimizasyon algoritmalarının karşılaştırılmasıKLASİKSEZGİSEL ARAMA ALGORİTMALARIANAHAT
  • GİRİŞ
  • TEPE TIRMANMA ALGORİTMASI
  • ISIL İŞLEM ALGORİTMASI
  • TABU ARAMA ALGORİTMASI
  • ANAHAT
  • GİRİŞ
  • TEPE TIRMANMA ALGORİTMASI
  • ISIL İŞLEM ALGORİTMASI
  • TABU ARAMA ALGORİTMASI
  • OPTİMİZASYON-ARAMA
  • Optimizasyon, problemin karar değişkenlerinin mümkün tüm kombinasyonları arasından en iyi performansı (en iyi amaç fonksiyonu değerini) veren kombinasyonun bulunmasıdır. Bu amaçla literatürde birçok optimizasyon algoritması önerilmiştir. Bu algoritmaların çoğu sistemin modeli ve amaç fonksiyonu için matematiksel modellere ihtiyaç duymaktadır. Karmaşık sistemler için matematiksel modelin kurulması çoğu zaman zordur. Model kurulsa bile çözüm zamanı maliyeti çok yüksek olduğundan kullanılamamaktadır.
  • Arama algoritmaları, algoritmanın yapısına uygun olarak seçilen bir başlangıç çözümünden ya da çözümlerinden başlar ve farklı yapılar kullanarak yeni çözümlere ulaşırlar.
  • Ayrık optimizasyon problemleri için genel olarak, tanımlanması kolay çözümü zor problemlerdir denilebilir. Ayrık optimizasyon problemlerini genellikle belirli bir matematiksel fonksiyon olarak ifade etmek güçtür. Bu nedenle, bu türdeki problemleri klasik optimizasyon yöntemleri ile çözmek zordur. Bilinen klasik algoritmalar sadece bu türdeki küçük boyutlu problemleri çözebilir. Bu durumda büyük boyutlu optimizasyon problemleri için, kabul edilebilir sürede optimuma yakın çözümler verebilen heuristik (sezgisel) algoritmalara ihtiyaç duyulur. GİRİŞ
  • TEPE TIRMANMA ALGORİTMASI
  • ISIL İŞLEM ALGORİTMASI
  • TABU ARAMA ALGORİTMASI
  • Tepe Tırmanma
  • Sezgisel arama işlemini gerçekleştirmenin en kolay yolu hill climbing olarak adlandırılan bir arama stratejisidir. Tepe tırmanma stratejisinde arama işleminde o anda aktif olan düğüm genişletilir ve çocuk düğümler değerlendirilir. Bunlardan en iyi değerle sahip olan düğüm bir sonraki genişletme işleminde kullanılmak üzere seçilir. Genişletme, ilk en iyi bulunduğunda ya da en iyi bulunduğunda olabilir.
  • Sezgi: Daima daha iyi bur duruma hareket et
  • Arama işlemi çocukların hepsinden daha iyi bir duruma erişildiğinde sona erer. Bu sistemde hatalı sezgisel değerler sonsuz yollara, dolayısıyla arama işleminin başarısızlıkla sonuçlanmasına neden olur. Bu yöntemin başarısı için sezgisel değerlerinin doğru belirlenmesi büyük önem taşır. Algoritmada önceki basamaklarla ilgili bilgi tutulmamaktadır, dolayısıyla hata durumu ile karşılaşıldığında eldeki yanlış çözüm üzerinde bir düzeltme yapılabilmesi söz konusu değildir. Algoritma tüm çocuklardan daha iyi durumda bir düğüme erişildiğinde sona erdiğinden yerel maksimum noktaları da sorun yaratmaktadır. İyi mutlak açıdan en iyi olmak zorunda değildir. Tepe tırmanma algoritması yerel ve global maksimum arasındaki ayrımı yapamamaktadır
  • Tepe TırmanmafunctionTEPE-TIRMANMA(problem) returnsbir çözüm durumuinputs: problem // bir problemlocal variables: mevcut // birdüğümsonraki // bir düğümmevcut <= DÜĞÜM_YAP(BAŞLANGIÇ-DURUM[problem]) loop dosonraki <= mevcut’un en yüksek değerli çocuğu ifDEĞER(sonraki) < DEĞER(mevcut) then returnmevcutmevcut <= sonrakiendKüçük Bir Örnek…(En kısa yol)583164724814765231352857563847631817645138 476222Bir Örnek Daha…(8-taş)başlangıçh = 0hedefh = -4-2-5-5h = -3h = -1-3-4h = -2h = -3-4f(n) = -(yerinde olmayan taş sayısı)6 27486 31238476 5186 1258433255774131257486 Başka Bir Örnek Daha…?!?!-4başlangıçhedef-40-3-4Bir Örnek Daha…(8-vezir)
  • h = birbirlerini direkt ya da dolaylı yiyen vezir sayısı
  • h = 17 (yukarıdaki durum için)
  • Devam…?!?!
  • h = 1li lokal bir minimum
  • Başka Bir Örnek (Blok Dünyası)başlangıçhedefAD04DCCBBABlok DünyasıLokal sezgisel: +1üzerinde olması düşünülen blokta yer alan her blok için. -1 yanlış yerde yer alan her blok için.Devam…02ADDCCBBADevam…?!?!D2CBAA00D0CCDCBBABADbaşlangıçhedefAD-66DCCBBABlock DünyasıGlobal sezgisel: Doğru destek yapısına sahip her blok için : +1 destek yapısındaki her bloğa. Yanlış destek yapısına sahip her blok için : -1 t destekyapısındaki her bloğaD-5CBAA-6-2D-1CCDCBBABADEksiklikler…hedefbayır
  • Bayır
  • Greedy algoritmanın gezinti yapması zor olan lokal maksimumlar sırası
  • Plato (Düz alan)
  • Değerlendirme fonksiyonunun düz olduğu durum uzaylarının alanı
  • platohedefAlgoritmaya Yapılan Modifikasyonlar
  • Stokastiktepe tırmanma
  • Yukarı çıkışlar arasında gelişigüzel seçim
  • Seçim olasılığı yukarı çıkışın dikliğiyle değişebilir.
  • İlk-seçimli tepe tırmanma
  • Stokastiktepe tırmanmayı, daha iyi bulunana kadar çocukları gelişigüzel üreterek kullanma
  • Rassal-tekrar başlatmalı tepe tırmanma
  • Algoritma, eğer tek tepe varsa çalışır. Lokal maksimumlara takılıp kalmayı önlemek için ve bulunan çözümü iyileştirmek için
  • Tekrarlı olarak tepe tırmanmayı uygula (çoklu tepe varsa tekrar başlatılır)
  • Sonuç
  • Tepe tırmanma lokal bir yöntemdir, bir sonraki adımda ne yapacağını sadece seçimlerinin “anlık” sıralarına bakarak karar verir.
  • Global bilgi sezgisel fonksiyona kodlanabilir.
  • Büyük, inişli çıkışlı problem uzayları için çok etkili olabilir. Global sezgisel ile hesapsal karmaşıklık artabilir.
  • Diğer yöntemlerle birleştirildiğinde kullanışlı olabilir.
  • ANAHAT
  • GİRİŞ
  • TEPE TIRMANMA ALGORİTMASI
  • ISIL İŞLEM ALGORİTMASI
  • TABU ARAMA ALGORİTMASI
  • Isıl işlem algoritması
  • Isıl işlem algoritması, katıların belirli bir başlangıç sıcaklığından başlayarak yavaş yavaş soğutulduğu tavlanma sürecinin benzetimi olan stokastik bir arama algoritmasıdır. Kirkpatrick, Gerlatt ve Vecchi (1983) ve Cerny (1985) tarafından ayrı ayrı önerilmiştir. Günümüze kadar, bilgisayar tasarımı, görüntü işleme, moleküler fizik ve kimya, çizelgeleme gibi farklı alanlardaki bir çok optimizasyon problemine uygulanmıştır. Son yıllarda birçok araştırmacı bu algoritmayı kombinatoryal optimizasyon problemlerinde etkili olarak kullanmaktadır.
  • Isıl işlem algoritması
  • Tavlama terimi fiziksel olarak, ısı banyosundaki bir katının yüksek enerji durumlarından başlayarak daha düşük enerji durumlarının elde edilme sürecini temsil etmektedir. Bu süreç çok genel olarak iki işlemden oluşmaktadır:
  • Isı banyosunun başlangıç sıcaklığının katının eriyebileceği bir değere kadar yükseltilmesi.
  • Katılar düşük enerjili durumda, yani düşük sıcaklıkta daha kararlıdır. Yani katıların parçacıkları düşük sıcaklıklarda daha düzenlidir. Bundan dolayı katının parçacıkları kendini düzenleyene kadar ısı banyosunun sıcaklığının giderek azaltılması.
  • Isıl işlem
  • Katının sıvı durumunda tüm parçacıkları gelişi güzel hareket ederler. Katı durumda ise bir kafes şeklinde düzenlenirler. Bu durumda sistemin enerjisi en azdır ve bu duruma yer durumu denmektedir. Bir katının yer durumu, sıcaklık yeteri kadar yükseltilmiş ve soğutma da yeteri kadar yavaş yapılmışsa elde edilir. Aksi halde katının bulunduğu durum yarı kararlı bir durumdur. Eğer soğutma işlemi çok hızlı gerçekleşirse, kristal yapıda bozukluklar ve düzensizlikler ortaya çıkacaktır. Bu nedenle soğutma işleminin dikkatle yapılması gerekmektedir.
  • Isıl işlem algoritması
  • Optimizasyon problemleriyle Isıl İşlem arasındaki benzerlikler aşağıdaki gibi gösterilebilir:
  • Katının farklı fiziksel durumları problemdeki mümkün çözümlere,
  • Sistemin enerjisi amaç fonksiyonuna,
  • Bir durumun enerjisi bir çözümün amaç fonksiyonu değerine,
  • Yarı kararlı durum yerel en iyi çözüme,
  • Yer durumu genel en iyi çözüme karşılık gelir.
  • Isıl işlem
  • Katıların bu tavlanma sürecinde geçirdiği fiziksel durumları benzetebilmek için Metropolis vd (1953) tarafından Monte Carlo tekniği üzerine dayalı olarak "Metropolis Algoritması" geliştirilmiştir. Algoritmada i durumunda bulunan katının enerjisi Ei iken, bir sonraki j durumuna geçen katının enerjisi Ej'dir. Eğer j durumundaki enerji i durumundaki enerjiden küçük veya eşitse, j durumu yeni mevcut çözüm olarak kabul edilir. Aksi takdirde j durumu aşağıdaki formüle göre elde edilen olasılık değeri ile kabul edilir. Uniform dağılımdan [0,1] aralığında rasgele bir δ sayısı üretilir ve bu aşağıda verilen olasılık değerinden küçükse yeni çözüm, mevcut çözüm olarak kabul edilir. Aksi takdirde, mevcut çözüm değiştirilmez. Bu olasılık değeri "Metropolis Kriteri" olarak anılır. Burada kB fiziksel tavlama sürecinde "Boltzman Sabiti" olarak bilinen fiziksel bir sabiti ifade eder.
  • P(E) =Yani, yeni çözümü sonraki iterasyona taşımak istiyorsak, ya eski çözümden daha iyi olması ya da daha kötü olmasına rağmen stokastik kuralı tatmin etmesi gerekmektedir. Stokastik kuralın tatmin edilmesinin sebebi, optimizasyon sürecinin yerel minimumdan kurtulmasını sağlamasıdır. Bu da Isıl işlemin ana özelliklerinden birisidir. Çünkü, Isıl işlemde hedef yerel optimumdan kurtulup genel optimuma ulaşmaktır.Eşitliğe göre, yüksek sıcaklıklarda tüm enerji durumları için P(E), 1’e yakınsar. Düşük sıcaklıklarda bile sistemin yüksek enerji seviyesine sahip olması küçük bir olasılıkla görülebilir. Bu nedenle enerjilerin istatistiksel dağılımı, sistemin bir yerel enerji minimumundan çıkmasına izin verir P(E) =Isıl işlem algoritması
  • Isıl işlem algoritması iteratif bir algoritmadır, yani algoritma çözüm uzayında sayıların vektörü formundaki tek bir çözümü sürekli olarak geliştirme şeklinde çalışır. Isıl işlem algoritmasının amacı, tüm mümkün çözüm noktalarının bir alt kümesinde (S) tanımlanmış bir f(x) fonksiyonunu eniyileyecek bir x çözümü bulmaktır. Isıl işlem algoritması rassal olarak seçilen bir başlangıç çözümüyle aramaya başlar. Bundan sonra uygun bir mekanizma ile bu çözüme komşu bir çözüm seçilir ve f(x)'de meydana gelen değişim hesaplanır. Eğer değişim istenilen yönde ise komşu çözüm mevcut çözüm olarak alınır. Eğer istenen yönde bir değişim sağlanmamışsa, Isıl işlem algoritması bu çözümü "Metropolis Kriteri" ile elde edilen olasılık değeri ile kabul eder. Amaç fonksiyonunda ters yönde bir değişim yaratan bir çözümün belli olasılık değeri ile kabulü, Isıl işlem algoritmasının yerel en iyi noktalardan kurtulmasını sağlamaktadır. Yukarıdaki olasılık değerine göre T değeri yüksek olduğunda amaç fonksiyonunda meydana gelen artışların çoğu kabul edilecektir. T değeri azaldıkça kabul edilme oranı da azalacaktır. Bu nedenle Isıl işlem algoritmasında yerel noktalara takılmamak için başlangıç sıcaklık değeri yüksek seçilerek yavaş yavaş azaltma yoluna gidilmektedir. Isıl işlem algoritması, bir taraftan sıcaklık yavaş yavaş azaltılırken, her sıcaklık değerinde belli sayıda hareket deneyerek arama işlemini sürdürür.
  • Algoritma temel adımlarıfunctionISIL_ISLEM( problem, plan) returnsbir çözüm durumuinput:problem, bir problemplan, zamandan sıcaklığa bir haritalamalocal variables: mevcut, bir düğüm.sonraki, bir düğüm.T, düşen adımları kontrol eden bir “sıcaklık”mevcut DUGUM_OLUSTUR(IBAŞLANGIC_DURUM[problem])for t  1 to ∞ doT  plan[t]ifT = 0then returnmevcutsonraki mevcutun gelişigüzel seçilen bir çocuğu ∆E DEGER[sonraki] - DEGER[mevcut]if∆E > 0 then mevcut sonrakielsemevcut sonrakisadece e∆E /TolasılığıylaAlgoritma
  • Algoritma, önceden tanımlanmış iterasyon sayısına bağlı olarak da çalışabilir. İlk önce rassal olarak başlangıç çözüm kümeleri üretilmekte ve kaç iterasyonda sonlandırılacağı belirlenmektedir. Daha sonra Isıl işlem en yüksek ısı (100) ile başlamakta ve t=0.995t fonksiyonu ile ısı 0,01’den küçük olana kadar soğutulmaktadır. Böylece, seçilen ve işlenen çözüm kümesi, tekrardan çözüm kümeleri içine diğerleriyle kıyaslanmak için konmaktadır. Daha sonra çözüm kümeleri içindeki diğer herhangi bir çözüm rassal olarak seçilmekte ve işlenmektedir.
  • Isıl işlem algoritmasının performansı büyük oranda seçilen soğutma planına bağlıdır. Günümüze kadar çok çeşitli soğutma planları önerilmiştir. Önerilen en eski plan Kirckpatrick ve arkadaşlarının fiziksel tavlama ile olan benzerliğe dayanarak ileri sürdükleri plandır. Bu tavlama planına göre, maddenin sıvı safhaya ulaştığında tüm parçacıkların rasgele düzenlenmesini taklit etmek için, T sıcaklık parametresinin başlangıç değeri, denenen tüm hareketler kabul edilecek kadar yüksek seçilmiştir. Sıcaklık parametresinin değerini azaltmak için ise, oransal bir sıcaklık fonksiyonu kullanarak sabit bir r için, T(t+1)=r.T(t) dikkate alınmıştır. Burada, r değeri 1’ den küçük fakat 1’e yakın bir sabittir ve genellikle değeri 0.8 ile 0.99 arasında bir değer almaktadır. Bu sıcaklık fonksiyonu ile sıcaklık parametresinin değeri, sıfıra yaklaştıkça daha da yavaş azalmaktadır. Sıcaklık parametresinin her değerinde gerçekleştirilecek yeterli tekrar sayısı sabit bir üst sınıra göre belirlenerek problemin, fiziksel tavlamadaki ısıl dengeye karşılık gelen bir denge durumuna ulaşması amaçlanmaktadır. Bu tavlama planı ile, sıcaklık parametresinin her değerinde elde edilen çözüm, belli sayıda ardışık sıcaklık değişimleri boyunca aynı kalırsa Isıl işlem algoritması durdurulmaktadır. Buna göre elde edilen son durum, fiziksel tavlamadaki donma durumuna (frozen state) karşılık gelmektedir.Isıl işlemTepe tırmanma algoritmasının aşağı inişleri de olabilen versiyonudur…7624351Parametreleri başlat ve başlangıç çözümüne ulaşYeni çözüm üretYeni çözümü değerlendirhayırYeni çözümü kabul et?evetParametreleri güncelleSıcaklığı ayarlahayırAramayı sonlandır?evetDurGİRİŞ
  • TEPE TIRMANMA ALGORİTMASI
  • ISIL İŞLEM ALGORİTMASI
  • TABU ARAMA ALGORİTMASI
  • TABU ARAMA ALGORİTMASI
  • Tabu Arama (TA) algoritması ilk defa F. Glover tarafından insan hafızasının çalışmasından esinlenilerek önerilmiş bir yerel arama yöntemidir. Tabu araştırması temel olarak belirli bir problem üzerine elde edilen ilk çözüm etrafındaki komşuluklar oluşturmaktır. Komşuluk mekanizması ele alınarak birbirini izleyen seçilmiş çözümlerden daha iyi olanı Tabu Listesi olarak atanır.
  • TABU ARAMA ALGORİTMASI
  • Tabu arama algoritmasında tabu listesi olarak oluşturulan ilk aday çözüm ve değişken komşu çözüm sayısı, bir tür tabulaştırma görevi yapmaktadır. Kötü sonuç veren bölgelerde daha fazla işlem yapılmaması (bu elemanların komşu sayılarının azaltılması), istenen çözüme daha az hesaplamayla, dolayısıyla daha hızlı ulaşmayla sağlamaktadır. iyi sonuç veren parametrelerin bir sonraki iterasyonda komşu sayıları artmakta, böylece algoritmanın verimliliği de artmış olmaktadır.
  • TABU ARAMA ALGORİTMASI
  • Tabu listesinin en önemli özelliklerinden birisi, mevcut tabu listesinin aday komşu çözümler ile karşılaştırıldıktan sonra bir sıralama ve karşılaştırma işlemi yaparak kendisini yenileyebilmesidir Bu amaçla, geliştirilen algoritmada, önceki döngüler de elde edilen çözümlerin listesinin tutulduğu bir tabu listesi oluşturulmuştur. Eğer bir komşu çözüm adayı, tabu listesinde yer alan bir çözümle aynıysa (bu durumda aday çözüm, zaten daha önce denenmiştir), bu çözüm değerlendirme dışı bırakılmaktadır. Tabu listesi oluşturulurken her döngüdeki en iyi çözüm listeye alınmakta, listenin dolduğu durumda listedeki ilk kayıtlar (başlangıçtaki çözümler) listeden atılıp, son döngüler de elde edilen çözümler listeye alınmaktadır.
  • Tabu Listesi ilk en iyi çözüm kümesinin oluşturularak hafızaya alınma yöntemi ile oluşturulur. Tabu listesi oluşturmanın önemli bir kuralı da giriş değerleri oluşturulurken çeşitli filtrezizasyon işlemlerinden geçirilmesidir
  • TABU ARAMA ALGORİTMASI
  • Oluşturulan Tabu listesinin en temel özelliği yeni çözüm adaylarını değerlendirmeye alarak dairesel bir döngü içerisinde yol alarak her yeni döngüden sonra yeni özellikler kazanmasıdır.
  • Tabu listesinin yeni elde edilen çözümler ile liste uzunluğu artacak ve çözüm aramada büyük bir etki yaparak kısa çözümlerin daireselliği sayesinde nesnel bir çözüm arama tekniği olduğunu gösterecektir. Burada istenilen durum çözüm adaylarının mevcut bu döngüsü ile Tabu listesinin geliştirilmesidir. Tabu listesine dahil edilen yeni çözümler oluşturulurken eğer elde edilen çözüm tabu listesindeki çözümlerden daha iyi ise elde edilen çözüm tabu listesine eklenebilir. Bunun tersi durumunda, yani daha kötü bir çözüm ise tabu listesine eklenmeyecek ve doğal olarak belirli bir bellek kaplamayacaktır. En iyi çözüm bulunana kadar bu işlemler mevcut döngü ile devam edecektir.
  • TABU ARAMA ALGORİTMASI
  • TA ana olarak basit tepe tırmanma (BTT) yönteminin zaaflarını gidermek için düşünülmüştür. BTT eldeki aday çözüme, bir komşuluk işleci uygulayarak, yeni adaylar üretir. Yeni adaylar bir değerlendirmeye tabi tutulur. Değerlendirme çözümün sonuca yakınlığını ölçer. Yeni adaylar ile eldeki eski aday içerisinden çözüme en yakın olan eskinin yerine geçer. BTT bu haliyle kısır bir döngüye sebep olabilir. Komşuluklar kapsamında birbirine eşit değerdeki iki yada daha fazla komşu arasında BTT takılıp kalabilir. Arama yapılan alanın özellikleri yada BTT yönteminin iyi seçilmemesi, herhangi bir denetim mekanizması kullanılmadan yapılan aramayı yerel en iyi noktalara götürebilir. Fakat gerçek hayattaki problemler yerel en iyilerin bol olduğu, fakat global iyinin az, hatta tek olabildiği problemlerdir. Kısacası kısır döngü kaçınılmazdır. Tabu arama yöntemi kısır döngüden kurtulmak için hafıza kullanılmasını, hatırlamayı önerir. Daha önce ziyaret edilmiş ya da herhangi bir nedenle ziyaret edilmesi istenilmeyen aday çözümlerle ilgili özellikler, tabu listesi adı verilen, kısa dönem hafızaya benzer bir yapıda tutulur. Yöntem bu listedeki hamlelerin belirli bir süre yapılmasını yasaklar. Böylece
  • Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks