SLS Yöntemlerine Genel Bakış

İteratif iyileştirmede pivot kuralları

İteratif iyileştirmede (II) her adımda iyileştiren komşuyu seçmek için farklı mekanizmalar, yani pivot kuralları (pivoting rules) kullanılabilir.

for each s′ ∈ N(s) // sabit (ya da rastgele karıştırılmış) bir sırada
    if g(s′) < g(s) then return s′
return s                          // iyileştiren komşu yok: yerel minimum

Sözde kod slaytta yok; iki kural arasındaki farkı göstermek için eklendi.

“Basit” SLS yöntemleri

Hedef: verilen değerlendirme fonksiyonunun yerel minimumlarından etkili biçimde kaçmak.

Genel yaklaşım: komşuluk sabit tutulur, ama adım fonksiyonu kötüleştiren adımlara izin verir.

Bu ailenin üyeleri: rastgeleleştirilmiş iteratif iyileştirme (RII), olasılıksal iteratif iyileştirme (PII), benzetimli tavlama (SA), tabu arama (TS) ve dinamik yerel arama. Dinamik yerel arama slaytlarda yalnızca adıyla geçiyor: komşuluğu değil, değerlendirme fonksiyonunu arama sırasında değiştirir (örneğin takılınan yerel minimumdaki bileşenlere ceza ekler).

Rastgeleleştirilmiş iteratif iyileştirme (RII)

Ana fikir: her adımda, sabit bir olasılıkla, iteratif iyileştirme adımı yerine bilgisiz bir rastgele yürüyüş adımı at.

s ← başlangıç aday çözümü
while sonlandırma koşulu sağlanmadı do
    with probability wp:
        s′ ← N(s)'den tekdüze rastgele bir komşu
    otherwise:
        s′ ← g(s′) < g(s) olan bir komşu;
             böyle bir komşu yoksa g(s′)'yü en küçük yapan komşu
    s ← s′

• Yerel minimuma gelindiğinde aramayı bitirmek gerekmez. Bunun yerine adım sayısı ya da CPU süresi sınırlanır; sınır aramanın başından ya da son iyileşmeden itibaren sayılabilir.
• Olasılıksal mekanizma, keyfi uzunlukta rastgele yürüyüş dizilerine izin verir. Bu nedenle yeterince uzun çalıştırıldığında RII'nin herhangi bir problem örneğinde (optimal) çözümü keyfi yüksek bir olasılıkla bulacağı garanti edilir.
• RII'nin bir çeşidi SAT'a başarıyla uygulanmıştır (GWSAT algoritması); ama genel olarak RII daha karmaşık SLS yöntemlerinin gerisinde kalır.

\(wp\) (walk probability) burada çeşitlendirmeyi ayarlayan tek düğmedir: \(wp = 0\) saf II'dir (yalnızca yoğunlaştırma), \(wp = 1\) saf rastgele yürüyüştür (yalnızca çeşitlendirme).

Olasılıksal iteratif iyileştirme (PII)

Ana fikir: kötüleştiren adımları, değerlendirme fonksiyonundaki kötüleşmeye bağlı bir olasılıkla kabul et: kötüleşme büyüdükçe olasılık küçülür.

• \(p(g, s)\) fonksiyonu, \(s\)'nin komşuları üzerinde, onların \(g\) değerlerine dayanan bir olasılık dağılımı belirler.
• Adım fonksiyonu bu dağılımdır: \(\mathit{step}(s)(s') := p(g, s)(s')\).
• PII'nin davranışı büyük ölçüde \(p\)'nin seçimine bağlıdır.
• II ve RII, PII'nin özel durumlarıdır.

Tipik bir seçim, sabit bir \(T\) sıcaklığıyla Metropolis kuralıdır: rastgele bir komşu önerilir ve aşağıdaki SA bölümündeki olasılıkla kabul edilir. Sıcaklık sabit kalırsa bu PII'dir; sıcaklık zamanla düşürülürse benzetimli tavlama olur.

Benzetimli tavlama (simulated annealing)

Ana fikir: PII'de kötüleştiren hamleleri kabul etme olasılığını belirleyen sıcaklık parametresini bir soğutma planına (annealing / cooling schedule) göre değiştir.

Yöntem, metallerin fiziksel tavlanmasından esinlenir:

Fiziksel süreçte (örneğin metallerin tavlanmasında) kusursuz temel durumlara, sıcaklık çok yavaş düşürülerek ulaşılır.

s ← başlangıç aday çözümü
T ← soğutma planına göre başlangıç sıcaklığı
while sonlandırma koşulu sağlanmadı do
    s′ ← öneri mekanizmasıyla olasılıksal olarak seçilen bir komşu
    if s′ olasılıksal kabul ölçütünü sağlıyorsa (T'ye bağlı) then
        s ← s′
    T ← soğutma planına göre güncelle

İki aşamalı adım fonksiyonu

SA'nın adımı iki parçadan oluşur: bir öneri mekanizması (çoğunlukla \(N(s)\)'den tekdüze rastgele seçim) ve bir kabul ölçütü (çoğunlukla Metropolis koşulu). Minimizasyonda \(\Delta = g(s') - g(s)\) olmak üzere Metropolis koşulu:

Sıcakken küçük ve büyük kötüleşmeler sık kabul edilir; arama geniş bir bölgeyi dolaşır (çeşitlendirme). Soğudukça kötüleşmeler neredeyse hiç kabul edilmez ve SA iteratif iyileştirmeye dönüşür (yoğunlaştırma).

Formül ve tablo slaytta yok; slayt yalnızca “Metropolis koşulu” adını veriyor.

Soğutma planı

Soğutma planı, çalışma süresi \(t\)'yi sıcaklık \(T(t)\)'ye eşleyen fonksiyondur. Üç parçası vardır:

• Başlangıç sıcaklığı \(T_0\): verilen problem örneğinin özelliklerine bağlı olabilir.
• Sıcaklık güncelleme şeması: örneğin geometrik soğutma, \(T := \alpha \cdot T\) (\(0 \lt \alpha \lt 1\)).
• Her sıcaklıkta atılacak adım sayısı: çoğunlukla komşuluk büyüklüğünün bir katı.

Sonlandırma yüklemi çoğunlukla kabul oranına, yani önerilen adımlara göre kabul edilen adımların oranına dayanır: kabul oranı çok düştüğünde arama fiilen donmuştur.

Gerçek bir koşu

Aşağıdaki grafik, rastgele yerleştirilmiş 40 şehirlik bir TSP örneğinde benzetimli tavlamanın bir koşusudur. Öneri mekanizması rastgele bir 2-opt hamlesi, kabul ölçütü Metropolis; \(T_0 = 40\), her 400 iterasyonda \(T := 0{,}93 \cdot T\).

Yakınsama sonucu

Belirli koşullar altında (aşırı yavaş soğutma), SA'nın yeterince uzun her yörüngesinin optimal bir çözümde biteceği garanti edilir [Geman ve Geman, 1984; Hajek, 1988].

• Gereken koşullar uygulanamayacak kadar yavaş olduğu için bu sonucun kombinatoryal problem çözmede pratik önemi çok sınırlıdır.
• Kombinatoryal problem çözmede optimal çözümde bitirmek genellikle önemsizdir; önemli olan optimal çözümü arama sırasında bulmaktır, bir kez karşılaşılsa bile. Bu yüzden SA uygulamalarında görülen en iyi çözüm ayrıca saklanır (SLS-Minimisation'daki \(\hat{s}\)).

Slaytta kaynak “Hajek, 1998” olarak yazılmış; ilgili makale B. Hajek, “Cooling schedules for optimal annealing”, Mathematics of Operations Research, 1988.

Tabu arama

Ana fikir: yerel minimumlardan kaçmak için arama geçmişinin bazı yönlerini, yani belleği kullan.

Basit tabu arama:

• Aday çözümlere ya da çözüm bileşenlerine tabu nitelikleri (tabu attributes) ilişkilendir.
• Alttaki iteratif best-improvement sürecinin yakın zamanda ziyaret ettiği arama konumlarına giden adımları, bu niteliklere dayanarak yasakla.

s ← başlangıç aday çözümü
while sonlandırma ölçütü sağlanmadı do
    N′ ← s'nin tabu olmayan komşuları
    s′ ← N′ içindeki en iyi aday çözüm     // iyileştirmese bile
    s′'ye göre tabu niteliklerini güncelle
    s ← s′

• \(N(s)\)'deki tabu olmayan konumlara \(s\)'nin izin verilen komşuları (admissible neighbours) denir.
• Bir arama adımından sonra mevcut konum ya da ona yeni eklenen/çıkarılan çözüm bileşenleri, sonraki sabit sayıda adım boyunca tabu ilan edilir. Bu sayıya tabu süresi (tabu tenure) denir.
• Çoğunlukla bir aspirasyon ölçütü de kullanılır: tabu durumunun hangi koşullarda geçersiz sayılacağını belirler; örneğin söz konusu adım şimdiye kadarki en iyi çözümü (incumbent) iyileştiriyorsa.

TSP'de 2-opt kullanan bir tabu aramada tipik bir tabu niteliği şudur: bir hamlede çıkarılan iki kenarın, sonraki \(tt\) adım boyunca tura geri eklenmesi yasaktır. Böylece arama bir önceki yerel minimuma hemen geri dönemez.

TSP örneği slaytta yok; tabu niteliği kavramını somutlaştırmak için eklendi.

Tabu süresinin seçimi

Tabu aramanın başarımı büyük ölçüde tabu süresi \(tt\)'nin ayarına bağlıdır:

Orta ve uzun vadeli bellek

Ek yoğunlaştırma ya da çeşitlendirme için orta veya uzun vadeli bellek kullanılarak daha fazla iyileşme sağlanabilir. Örnekler:

• Ara sıra seçkin aday çözümlere (aramada daha önce karşılaşılan yüksek kaliteli konumlara) geri dönmek; bunu yaparken ilgili bütün tabu nitelikleri temizlenir.
• Bazı çözüm bileşenlerini dondurup uzun süre sabit tutmak.
• Ara sıra, nadiren kullanılan çözüm bileşenlerini mevcut aday çözüme zorla eklemek.
• Değerlendirme fonksiyonunu, aday çözümlerin ya da bileşenlerin kullanım sıklığını da yansıtacak şekilde genişletmek.

Tabu arama algoritmaları SAT ve MAX-SAT, kısıt sağlama problemi (CSP) ve birçok çizelgeleme problemi dahil pek çok kombinatoryal problemde en iyi yöntemler arasındadır. Uygulamalarda kritik iki etken: komşuluk ilişkisinin seçimi ve aday çözümlerin verimli değerlendirilmesi (önbellekleme ve artımlı güncelleme).

Melez SLS yöntemleri

“Basit” SLS yöntemlerini birleştirmek çoğu zaman başarımı ciddi biçimde artırır. Basit örnekler:

• Yaygın yeniden başlatma mekanizmaları, bilgisiz rastgele seçimle (uninformed random picking) yapılmış bir melezleme olarak görülebilir.
• İteratif iyileştirme + bilgisiz rastgele yürüyüş = rastgeleleştirilmiş iteratif iyileştirme (RII).

Yinelemeli yerel arama (ILS)

Ana fikir: iki tür SLS adımı kullan:

• Alt yerel arama (subsidiary local search) adımları, yerel optimumlara olabildiğince verimli ulaşmak için (yoğunlaştırma);
• Pertürbasyon adımları, yerel optimumlardan etkili biçimde kaçmak için (çeşitlendirme).

Ayrıca bir kabul ölçütü, çeşitlendirme ile yoğunlaştırma arasındaki dengeyi denetler.

s ← başlangıç aday çözümü
s ← alt yerel arama(s)
while sonlandırma ölçütü sağlanmadı do
    r ← s
    s ← pertürbasyon(s)
    s ← alt yerel arama(s)
    kabul ölçütüne göre s'yi koru ya da s ← r'ye geri dön

• Alt yerel aramanın sonucu bir yerel minimumdur.
• ILS yörüngeleri, verilen değerlendirme fonksiyonunun yerel minimumlar uzayında yürüyüşler olarak görülebilir.
• Pertürbasyon evresi ve kabul ölçütü arama geçmişini (sınırlı bir belleği) kullanabilir.
• Yüksek başarımlı bir ILS algoritmasında alt yerel arama, pertürbasyon mekanizması ve kabul ölçütü birbirini iyi tamamlamalıdır.

Alt yerel arama

• Daha etkili alt yerel arama, daha iyi ILS başarımı getirir. TSP örneği: 2-opt, 3-opt ve Lin-Kernighan (LK) sırasıyla daha güçlüdür.
• Alt yerel arama çoğunlukla iteratif iyileştirmedir, ama daha gelişmiş SLS yöntemleri de kullanılabilir (örneğin tabu arama).

Pertürbasyon mekanizması

• Etkisi sonraki yerel arama evresinde kolayca geri alınamayacak şekilde seçilmelidir. Bu çoğunlukla daha büyük bir komşulukta adım atarak sağlanır. TSP için ILS örneği: yerel arama 3-opt, pertürbasyon 4-exchange adımları.
• Bir pertürbasyon evresi bir ya da daha fazla pertürbasyon adımından oluşabilir.

Gelişmiş ILS algoritmaları, pertürbasyonun türünü ve gücünü arama sırasında uyarlamalı olarak değiştirebilir.

Kabul ölçütleri

Popülasyon tabanlı SLS yöntemleri

Şimdiye kadarki SLS yöntemleri her adımda verilen problem örneğinin tek bir aday çözümüyle çalışır. Doğrudan bir genişletme: bunun yerine aday çözümlerden oluşan bir popülasyon (küme) kullanmak.

• Popülasyon kullanmak, aramayı çeşitlendirmenin genel bir yoludur.
• Popülasyon tabanlı SLS yöntemleri, aday çözüm kümelerini arama konumu sayarak Not 03'teki genel SLS tanımına uyar.

Evrimsel algoritmalar, karınca kolonisi optimizasyonu ve parçacık sürüsü gibi yöntemler 11. haftada (popülasyon tabanlı üst-sezgiseller) işlenecek.

Yöntemlerin karşılaştırması

Tablo, slaytlardaki yöntemleri yan yana koymak için hazırlandı.

Özet

• Best improvement bütün komşuları değerlendirir; first improvement ilk iyileştiren komşuyu alır ve çoğu zaman daha hızlıdır.
• “Basit” SLS yöntemleri komşuluğu sabit tutar, kötüleştiren adımlara izin vererek yerel minimumdan kaçar.
• RII \(wp\) olasılıkla rastgele adım atar; PII kötüleşmeyi olasılıkla cezalandırır; SA bu olasılığı bir soğutma planıyla azaltır.
• Tabu arama belleği kullanır: yakın geçmişi yasaklar; başarımı tabu süresine çok duyarlıdır.
• ILS, alt yerel arama (yoğunlaştırma), pertürbasyon (çeşitlendirme) ve kabul ölçütüyle yerel minimumlar uzayında yürür.
• Popülasyon tabanlı yöntemler tek bir aday yerine bir küme taşır; bu genel bir çeşitlendirme aracıdır.