Kombinatoryal Problemler ve Arama

Kombinatoryal problemler

Kombinatoryal problemler bilgisayar biliminin ve uygulama alanlarının pek çok yerinde karşımıza çıkar:

• en kısa ya da en ucuz turları bulmak (TSP),
• önermesel formüllerin modellerini bulmak (SAT),
• planlama, çizelgeleme, ders programı hazırlama,
• internette veri paketlerinin yönlendirilmesi,
• protein yapısı tahmini,
• kombinatoryal ihalelerde kazananın belirlenmesi.

Çözüm bileşenleri (solution components)

Çözümlerin yapıldığı parçalar; örneğin bir turdaki tek bir kenar.

Aday çözümler (candidate solutions)

Çözüm bileşenlerinin, bir çözüm girişimi sırasında karşılaşılabilecek kombinasyonları. Bütün koşulları sağlamaları gerekmez.

Çözümler (solutions)

Verilen bütün koşulları sağlayan aday çözümler.

Örnek: düzlemde en kısa tur

Verilen: Öklid düzleminde bir nokta kümesi. Amaç: en kısa turu bulmak. Bir tur, noktaların bir sırasıdır, yani noktaların sıra pozisyonlarına atanmasıdır.

Problem ve problem örneği

Teknik olarak problemler, problem örneklerinin kümeleri olarak biçimselleştirilir. Projede “problem örnekleri” (problem instances) derken kastedilen budur: aynı problemin farklı boyut ve verilerdeki somut hâlleri.

Karar problemleri ve optimizasyon problemleri

Karar problemleri

Çözümler, verilen mantıksal koşulları sağlayan aday çözümlerdir. Örnek, graf boyama problemi: bir \(G\) grafı ve bir \(C\) renk kümesi verilmiş; \(G\)'nin her düğümüne \(C\)'den bir renk ata ve bir kenarla bağlı iki düğüm hiçbir zaman aynı rengi almasın.

Optimizasyon problemleri

• Karar problemlerinin genellemesi olarak görülebilir.
• Bir amaç fonksiyonu \(f\) çözüm kalitesini ölçer; çoğunlukla bütün aday çözümlerde tanımlıdır.
• Tipik hedef optimal kaliteli bir çözüm bulmaktır. Minimizasyonda optimal kalite \(f\)'nin en küçük değeri, maksimizasyonda en büyük değeridir.

Örnek: graf boyamanın, geçerli bir boyamayı en az sayıda renkle bulmayı amaçlayan çeşidi. Her minimizasyon problemi bir maksimizasyon problemi olarak yazılabilir, tersi de doğrudur: \(\min f = -\max(-f)\).

Birçok optimizasyon probleminde hem bir amaç fonksiyonu hem de çözümlerin sağlaması gereken mantıksal koşullar vardır. Bu koşulları sağlayan aday çözüme olurlu ya da geçerli (feasible, valid) denir.

SAT: önermesel sağlanabilirlik

Kavramsal olarak basit problemleri incelemek, algoritmaların geliştirilmesini, analizini ve sunumunu kolaylaştırır. Kitap boyunca iki problem prototip olarak kullanılır: SAT prototip karar problemi, TSP prototip optimizasyon problemidir.

Çoğunlukla SAT'ın CNF formüllerine kısıtlanmış hâli ele alınır. Bir formül, aşağıdaki biçimdeyse birleşimli normal formdadır (conjunctive normal form, CNF):

• Her literal \(l_{ij}\) bir önermesel değişken ya da onun değillemesidir.
• \((l_{i1} \lor \dots \lor l_{ik(i)})\) ayrışımlarına cümle (clause) denir.
• Bir formül CNF'deyse ve bütün cümleleri tam \(k\) literal içeriyorsa (her \(i\) için \(k(i) = k\)) k-CNF'dedir. SAT'ın k-CNF formüllerine kısıtlanmış hâline k-SAT denir.

Küçük bir örnek

Üç değişken, altı cümle, her cümlede iki literal: \(F\) bir 2-CNF formülüdür. İlk iki cümle birlikte \(x_1 = 1\)'i zorlar (\(x_2\) ne olursa olsun biri yanlış kalırdı); sonra \(\lnot x_1 \lor x_2\) cümlesi \(x_2 = 1\)'i, \(\lnot x_1 \lor x_3\) cümlesi \(x_3 = 1\)'i zorlar. Bu yüzden sekiz atamadan yalnızca \((x_1, x_2, x_3) = (1, 1, 1)\) \(F\)'yi sağlar; formülün tek modeli budur. Bu formüle iteratif iyileştirme bölümünde döneceğiz.

Örnek formül slaytta yok; notta tanımları somutlaştırmak için kullanılıyor.

TSP: gezgin satıcı problemi

TSP örneklerinin türleri

Simetrik

\(G\)'deki her \((v, v')\) kenarı için \((v', v)\) de \(G\)'dedir ve \(w((v, v')) = w((v', v))\). Aksi hâlde asimetrik.

Öklid

Düğümler bir Öklid uzayındaki noktalardır, ağırlık fonksiyonu Öklid uzaklığıdır.

Coğrafi

Düğümler bir küre üzerindeki noktalardır, ağırlık fonksiyonu coğrafi (büyük çember) uzaklıktır.

Slayttaki harita, Akdeniz'de 16 duraklı bir TSP örneğidir (Troya, İthaka, Korfu, Messina, Cebelitarık ve diğerleri): Odysseus'un yolculuğunu en kısa tur sorusu olarak sorar.

Arama paradigmaları

Kombinatoryal problemleri arama ile çözmek, aday çözümleri yinelemeli olarak üretip değerlendirmek demektir. Karar problemlerinde değerlendirme, adayın bir çözüm olup olmadığını sınamaktır; optimizasyon problemlerinde amaç fonksiyonunun değerini hesaplamaktır. Bir aday çözümü değerlendirmek, (optimal) çözümü bulmaktan çoğunlukla çok daha ucuzdur.

Değiştirici arama

• Arama uzayı = tam aday çözümler.
• Arama adımı = bir ya da daha fazla çözüm bileşenini değiştirmek.

SAT örneğinde arama uzayı bütün tam değişken atamalarıdır; bir adım bir ya da daha fazla değişkenin doğruluk değerini değiştirir.

Yapıcı arama (kurucu sezgiseller)

• Arama uzayı = kısmi aday çözümler.
• Arama adımı = bir ya da daha fazla çözüm bileşeniyle genişletmek.

Örnek, TSP için en yakın komşu sezgiseli (nearest neighbour heuristic, NNH):

1. Tek bir düğümle başla (tekdüze rastgele seçilir).
2. Her adımda, henüz ziyaret edilmemiş bir sonraki düğüme giden en düşük ağırlıklı kenarı izle.
3. Yolun sonuna başlangıç düğümünü ekleyerek Hamilton çevrimini tamamla.

NNH genellikle çok kaliteli çözümler bulmaz, ama değiştirici arama yöntemleriyle birlikte sık ve başarıyla kullanılır: değiştirici aramaya iyi bir başlangıç noktası verir.

Çalışılmış örnek: beş şehirde NNH

A'dan başlayan NNH: A'dan en yakın şehir D (2); D'den ziyaret edilmemişlere uzaklıklar B 6, C 5, E 6, en yakını C (5); C'den B (4); B'den E (3); son olarak E'den A'ya dönülür (7). Tur A–D–C–B–E–A, uzunluk 2 + 5 + 4 + 3 + 7 = 21.

Beş şehirde \((5-1)!/2 = 12\) farklı tur vardır; hepsi sayıldığında optimum A–C–B–E–D–A, uzunluk 19 çıkar. NNH'nin tipik zaafı görülüyor: son kenar (E→A, 7) seçilmez, mecburen eklenir. NNH turundan tek bir 2-opt hamlesi optimuma götürür: (D, C) ve (E, A) kenarlarını çıkarıp (D, E) ve (C, A) eklemek \(\Delta = 6 + 4 - 5 - 7 = -2\) kazandırır ve A–D–E–B–C–A turunu (uzunluk 19) verir. Yapıcı ve değiştirici aramanın birlikte kullanılmasının nedeni budur.

Bu örnek slaytta yok; uzaklık matrisi örnek için seçildi, sonuçlar tam sayımla doğrulandı.

Sistematik arama ve yerel arama

Örnek: SAT için bilgisiz rastgele yürüyüş

procedure URW-for-SAT(F, maxSteps)
    input:  önermesel formül F, tamsayı maxSteps
    output: F'nin bir modeli ya da ∅

    a ← F'deki bütün değişkenlere tekdüze rastgele seçilmiş doğruluk değerleri
    steps ← 0
    while not ((a, F'yi sağlıyor) or (steps ≥ maxSteps)) do
        F'den rastgele bir x değişkeni seç
        a'da x'in değerini değiştir
        steps ← steps + 1
    end
    if a, F'yi sağlıyor then return a
    else return ∅
end

Stokastik yerel arama (SLS)

Öne çıkan birçok yerel arama algoritması, aday çözümleri üretirken ve değiştirirken rastgele seçimler kullanır. Bu stokastik yerel arama (SLS) algoritmaları, zor kombinatoryal problemleri çözmek için en başarılı ve en yaygın yaklaşımlardandır. Bilinen örnekler: evrimsel algoritmalar, benzetimli tavlama, TSP için Lin-Kernighan algoritması.

Biçimsel tanım

Verilen bir \(\pi\) problem örneği için bir SLS algoritması şu parçalardan oluşur:

Arama uzayı \(S(\pi)\)

SAT için: önermesel değişkenlerin bütün tam doğruluk atamalarının kümesi.

Çözüm kümesi \(S'(\pi) \subseteq S(\pi)\)

SAT için: verilen formülün modelleri.

Komşuluk ilişkisi \(N(\pi) \subseteq S(\pi) \times S(\pi)\)

SAT için: tam olarak bir değişkenin doğruluk değerinde farklı olan atamalar komşudur.

Bellek durumları kümesi \(M(\pi)\)

Bellek kullanmayan SLS algoritmalarında tek bir durumdan oluşabilir.

Başlatma fonksiyonu \(\mathit{init}: \emptyset \mapsto \mathcal{D}(S(\pi) \times M(\pi))\)

Başlangıç arama konumları ve bellek durumları üzerindeki olasılık dağılımını belirler.

Adım fonksiyonu \(\mathit{step}: S(\pi) \times M(\pi) \mapsto \mathcal{D}(S(\pi) \times M(\pi))\)

Her arama konumunu ve bellek durumunu, sonraki komşu konumlar ve bellek durumları üzerindeki bir olasılık dağılımına eşler.

Sonlandırma yüklemi \(\mathit{terminate}: S(\pi) \times M(\pi) \mapsto \mathcal{D}(\{\top, \bot\})\)

Her arama konumu ve bellek durumu için sonlandırma olasılığını belirler.

\(\mathcal{D}(X)\), \(X\) kümesi üzerindeki olasılık dağılımlarını gösterir. Algoritmayı “stokastik” yapan şey budur: başlatma, adım ve sonlandırma kararları birer dağılımdan örneklenir.

procedure SLS-Minimisation(π′)
    input:  problem örneği π′ ∈ Π′
    output: çözüm ŝ ∈ S′(π′) ya da ∅

    (s, m) ← init(π′)
    ŝ ← s
    while not terminate(π′, s, m) do
        (s, m) ← step(π′, s, m)
        if f(π′, s) < f(π′, ŝ) then
            ŝ ← s                          // en iyi bulunan çözümü güncelle
        end
    end
    if ŝ ∈ S′(π′) then return ŝ
    else return ∅
end

Dikkat: algoritma aramanın bittiği konumu değil, yol boyunca görülen en iyi konumu (\(\hat{s}\), incumbent) döndürür. Kötüleştiren adımlara izin veren yöntemlerde (Not 04) bu ayrım önemlidir.

Örnek: SAT için tekdüze rastgele yürüyüş

Arama adımı, yörünge ve strateji

Arama adımı (hamle) (search step, move)

\(s'\)'ye \(s\)'den tek adımda ulaşılabilen \((s, s')\) arama konumları çifti.

Arama yörüngesi (search trajectory)

Her \(i \in \{1, \dots, k\}\) için \((s_{i-1}, s_i)\) bir arama adımı olan ve aramanın \(s_0\)'da başlama olasılığı sıfırdan büyük olan sonlu \((s_0, s_1, \dots, s_k)\) dizisi.

Arama stratejisi (search strategy)

init ve step fonksiyonlarıyla belirlenir; bir ölçüde problem örneğinden ve SLS algoritmasının diğer bileşenlerinden bağımsızdır.

Bilgisiz stratejiler

Bu bilgisiz stratejiler tek başlarına oldukça etkisizdir; ama daha yönlendirilmiş arama stratejileriyle birleştirildiklerinde önemli rol oynarlar (Not 04'teki RII ve yeniden başlatma).

Değerlendirme fonksiyonu

Bazı SLS yöntemleri, verilen amaç fonksiyonundan farklı bir değerlendirme fonksiyonu kullanır (örneğin ceza terimli \(g\)).

İteratif iyileştirme (II)

• Bellek kullanmaz.
• init: \(S\)'den tekdüze rastgele seçim.
• step: iyileştiren komşular arasından tekdüze rastgele seçim.
• İyileştiren komşu kalmayınca sonlanır.
• Adım fonksiyonu değiştirilerek farklı çeşitleri elde edilir (Not 04: best ve first improvement).

II, yinelemeli iniş (iterative descent) ya da tepe tırmanma (hill-climbing) olarak da bilinir.

SAT için iteratif iyileştirme

• Arama uzayı \(S\): \(F\)'deki değişkenlerin bütün doğruluk atamaları.
• Çözüm kümesi \(S'\): \(F\)'nin bütün modelleri.
• Komşuluk \(N\): 1-flip komşuluğu.
• Bellek: kullanılmaz, \(M := \{0\}\).
• Başlatma: \(S\)'den tekdüze rastgele, yani her \(a'\) ataması için \(\mathit{init}()(a') := 1/\#S\).
• Değerlendirme fonksiyonu: \(g(a) :=\) \(a\) altında sağlanmayan cümle sayısı. \(g(a) = 0 \iff a\), \(F\)'nin bir modelidir.
• Adım fonksiyonu: iyileştiren komşular arasından tekdüze rastgele seçim: \[ \mathit{step}(a)(a') := \begin{cases} 1/\#I(a) & a' \in I(a) \\ 0 & \text{aksi hâlde} \end{cases} \qquad I(a) := \{a' \mid N(a, a') \land g(a') \lt g(a)\} \]
• Sonlandırma: iyileştiren komşu kalmadığında: \(I(a) = \emptyset\) ise \(\mathit{terminate}(a)(\top) := 1\), aksi hâlde 0.

Çalışılmış örnek

Yukarıdaki \(F\) formülü için \(a = (0, 0, 1)\) atamasından başlayalım. \(x_1 \lor x_2\) ve \(x_1 \lor \lnot x_3\) cümleleri sağlanmıyor: \(g(a) = 2\). Üç komşu:

\(I(a) = \{(1, 0, 1), (0, 0, 0)\}\): iki iyileştiren komşu var ve II her birine 1/2 olasılıkla gider. Bundan sonrası seçime bağlıdır:

• (1, 0, 1)'e giderse: komşuları \((0, 0, 1)\), \((1, 1, 1)\), \((1, 0, 0)\) ve \(g\) değerleri 2, 0, 2. Tek iyileştiren komşu \((1, 1, 1)\); II oraya gider ve modeli bulur.
• (0, 0, 0)'a giderse: komşuları \((1, 0, 0)\), \((0, 1, 0)\), \((0, 0, 1)\) ve üçünün de \(g\) değeri 2. İyileştiren komşu yok, \(I = \emptyset\) ve arama durur. Ama \((0, 0, 0)\) bir model değildir: II, \(g = 1\) olan bir yerel minimumda takıldı.

Yerel minimumlar ve kaçış mekanizmaları

Yukarıdaki örnekteki \((0, 0, 0)\) bir kesin yerel minimumdur: \(g = 1\) ve üç komşusunun hepsinde \(g = 2\). Kesin olmayan yerel minimumlar ise genellikle platolarda görülür:

II bir yerel minimumda durur. Bu noktadan kaçmanın iki basit yolu vardır:

Yeniden başlatma (restart)

Her yerel optimuma gelindiğinde aramayı baştan başlat. Başlatmanın maliyeti yüzünden çoğu zaman oldukça etkisizdir.

İyileştirmeyen adımlar (non-improving steps)

Yerel optimumda değerlendirme değeri eşit ya da daha kötü olan adaylara geçmeye izin ver; örneğin en az kötüleştiren adımı seç. Değerlendirme değeri aynı olan konumlardan oluşan platolarda uzun yürüyüşlere yol açabilir.

İki mekanizma da yerel optimumlardan her zaman etkili biçimde kaçmayı garanti etmez. Not 04'teki yöntemler bu sorunu daha sistemli çözer.

Yoğunlaştırma ve çeşitlendirme

Bir SLS stratejisinin hedefe yönelik ve rastgele bileşenleri dikkatle dengelenmelidir.

Yoğunlaştırma (intensification)

Çözüm kalitesini ya da çözüm bulma olasılığını açgözlü biçimde artırmayı hedefler; örneğin değerlendirme fonksiyonundan sonuna kadar yararlanarak. Örnek: iteratif iyileştirme.

Çeşitlendirme (diversification)

Arama sürecinin sınırlı bölgelerde sıkışmasını engelleyerek durgunluğu önlemeyi hedefler. Örnek: bilgisiz rastgele yürüyüş.

Yoğunlaştırma ve çeşitlendirme mekanizmalarının dengeli birleşimi, gelişmiş SLS yöntemlerinin temelidir.

Özet

• Kombinatoryal problemler ayrık, sonlu bir kümenin koşulları sağlayan gruplamasını, sıralamasını ya da atamasını arar. Aday çözüm koşulları sağlamak zorunda değildir; çözüm sağlar.
• SAT prototip karar problemi, TSP prototip optimizasyon problemidir.
• Yapıcı arama kısmi çözümleri genişletir (NNH), değiştirici arama tam çözümleri değiştirir. İkisi birlikte iyi çalışır.
• Sistematik arama tamdır ve kanıt üretir; yerel arama tam değildir ama hızlıdır.
• Bir SLS algoritması \(S, S', N, M\), init, step ve terminate ile tanımlanır; değerlendirme fonksiyonu \(g\) algoritmaya, amaç fonksiyonu \(f\) probleme aittir.
• İteratif iyileştirme yalnızca yoğunlaştırır ve ilk yerel minimumda durur; aynı başlangıçtan bile, rastgele seçimlerine göre modele ulaşabilir ya da bir yerel minimumda takılabilir. Rastgele yürüyüş yalnızca çeşitlendirir. İyi yöntemler ikisini dengeler.