Algoritmik arayüz
Üst-sezgiseller probleme kördür
Yerel arama, tabu arama ve yinelemeli yerel arama (ILS) şehirleri, kamyonları ya da sunucuları anlamaz. Yalnızca matematiksel durum uzaylarında gezinirler.
Formülasyon araziyi belirler
Seçtiğimiz kodlama ve hamle operatörleri arazinin engebesini, platolarını ve yerel minimumlarını belirler. İyi modelleme zor arama uzaylarını kolaylaştırır.
Sonuç olarak aynı algoritma, aynı problemde, farklı bir formülasyonla çok farklı davranabilir. Bu yüzden sezgisel tasarımı algoritmayla değil, formülasyonla başlar.
Arama formülasyonunun dört temeli
- Temsil (representation)
- Bir aday çözümün bellekte nasıl kodlandığı.
- Değerlendirme (evaluation)
- Arama adımlarını yönlendiren kalite puanı.
- Kısıtlar (constraints)
- Olursuz adayların nasıl ele alınacağı.
- Komşuluk (neighborhood)
- Bir \(s\) durumundan yapılabilecek geçerli geçişler, yani hamleler.
Bu dört karar verildiğinde arama uzayı, her noktanın kalitesi ve noktalar arasındaki yollar tanımlanmış olur. Algoritma bundan sonra yalnızca bu yollarda nasıl yürüneceğini seçer.
Çözüm temsili ve kodlama
\(s \in \{0, 1\}^n\)
\(i\). bit 1 ise \(i\). eşya çantada ya da \(i\). tesis açık. Kullanım: 0-1 sırt çantası, SAT, tesis yerleşimi. Uzay büyüklüğü \(2^n\).
\(\pi \in \Pi_n\)
Şehirlerin ziyaret sırası ya da işlerin makinedeki sırası. Kullanım: TSP, iş atölyesi çizelgeleme (job shop), rotalama. Uzay büyüklüğü \(n!\).
\(c \in \{1, \dots, K\}^n\)
\(i\). düğümün rengi ya da \(i\). eşyanın kutusu. Kullanım: graf boyama, kutu paketleme, hub ataması. Uzay büyüklüğü \(K^n\).
Temsil seçimi bazı kısıtları kendiliğinden sağlayabilir. Permütasyon her şehri tam bir kez içerdiği için TSP'de “her şehir bir kez ziyaret edilir” kısıtı ayrıca denetlenmez. Kötü bir temsil ise olursuz çözümlerle dolu bir uzay yaratır.
Amaç fonksiyonu ve değerlendirme fonksiyonu
Amaç fonksiyonu \(f(s)\)
Gerçek dünyadaki maliyeti ya da kârı tanımlayan, değiştirilemez ölçüt.
TSP: km cinsinden toplam tur uzunluğu
Değerlendirme fonksiyonu \(g(s)\)
Komşu geçişleri düzgün biçimde sıralamak için tasarlanmış sezgisel yönlendirme aracı.
SAT: ihlal edilen cümle (clause) sayısı
Neden ikisi ayrı? SAT bir karar problemidir: formül ya sağlanır ya sağlanmaz. Bu iki değerli bilgi aramaya yön vermez, çünkü neredeyse bütün komşular aynı “sağlanmıyor” cevabını verir. “İhlal edilen cümle sayısı” ise her adımda hedefe ne kadar yaklaştığımızı söyler ve \(g = 0\) tam olarak formülü sağlayan bir atama bulduğumuz anlamına gelir. \(g\) ile \(f\) aynı olmak zorunda değildir, ama \(g\)'nin global optimumları problemin çözümlerine karşılık gelmelidir.
Kısıtlar ve olursuzluğun ele alınması
Katı reddetme (strict rejection)
Yalnızca olurlu uzayda ara; olursuz komşuya hiç gitme.
Risk: olurlu bölge birbirinden kopuk “adalara” bölünebilir ve arama bir adadan ötekine geçemez.
Ceza ekleme (penalty embedding)
İhlallere izin ver, ama onları yumuşak bir ceza maliyetiyle değerlendirmeye kat:
\(g(s) = f(s) + \lambda \cdot \text{İhlal}(s)\)
Onarım operatörleri (repair)
Kısıtsız durumları geçerli çözümlere eşle; örneğin fazla dolu çantadan eşya çıkar.
Fayda: algoritmanın basitliği korunur.
Ceza katsayısını seçmek
Yukarıdaki formül minimizasyon içindir; maksimizasyonda ceza çıkarılır: \(g(s) = f(s) - \lambda \cdot \text{İhlal}(s)\). \(\lambda\) çok küçükse arama olursuz ama “ucuz” çözümlerde kalır; çok büyükse olurlu bölgenin sınırına yaklaşmak bile pahalı olur ve yöntem pratikte katı reddetmeye döner. Yaygın bir uygulama, \(\lambda\)'yı arama sırasında uyarlamaktır: olursuz çözümler çoğaldıkça artırmak, azaldıkça düşürmek.
Bu alt bölüm slaytlarda yok; ceza yaklaşımını uygularken karşılaşılan tipik sorunu özetler.
Komşuluk operatörleri ve hamle topolojisi
Komşuluk büyüklüğü
Operatör seçimi arama grafiğinin kenar yoğunluğunu belirler.
Küçük \(N(s)\): hızlı adımlar, sığ yerel minimumlar.
Büyük \(N(s)\): kaliteli hamleler, yüksek CPU maliyeti.
Artımlı Δ-değerlendirme
Güncel SLS uygulamalarının olmazsa olmazı.
Kaçın: her komşu için amacı baştan \(O(n)\)'de hesaplamak.
Hesapla: hamlenin farkını \(\Delta g(s \to s')\) \(O(1)\)'de.
Bir fikir vermesi için tipik komşuluk büyüklükleri: ikili vektörde 1-flip \(n\) komşu; permütasyonda iki eleman takası (swap) \(n(n-1)/2\) komşu; \(n\) şehirli bir turda 2-opt, bitişik olmayan kenar çifti sayısı kadar, yani \(n(n-3)/2\) komşu. Her adımda bütün komşular değerlendiriliyorsa, Δ-değerlendirme bir adımın maliyetini \(n\) kat düşürür.
Beş prototip problem
| Problem | Amaç | Açıklama |
|---|---|---|
| SAT | \(F = (l_{11} \lor l_{12}) \land (l_{21} \lor l_{22}) \land \dots\) sağlansın | Önermesel bir formülü sağlayan değişken ataması bul. |
| TSP | \(\min \sum w(u_i, u_{i+1})\) | Her düğümü tam bir kez ziyaret eden en düşük ağırlıklı Hamilton çevrimini bul. |
| KSP | \(\max \sum p_i x_i\) | Kapasite \(C\)'yi aşmadan kârı en büyükleyen eşya alt kümesini seç. |
| GCP | \(\min \max_i c_i\) | Bağlı komşular aynı rengi almayacak şekilde bütün düğümleri en az renkle boya. |
| VRP | toplam mesafe min. | Merkezi bir depodan çıkan, kapasite kısıtlı araç rotaları tasarla. |
Gezgin satıcı problemi (TSP)
Kodlama: permütasyon \(\pi = (\pi_1, \pi_2, \dots, \pi_n)\).
Kısıt: olurluluk temsilin içinde; her düğüm tam bir kez ziyaret edilir.
Amaç: toplam tur kenar ağırlığını en küçükle.
2-opt: iki kenarı kes, aradaki parçayı ters çevirerek yeniden bağla.
Swap: iki şehrin ziyaret sırasını değiştir.
Δ: farkı dört uç noktanın uzaklıklarından \(O(1)\)'de hesapla.
Simetrik TSP'de ters çevrilen parçanın içindeki kenarların uzunluğu değişmez. Bu yüzden hamlenin farkı yalnızca dört uç noktaya bağlıdır:
\[ \Delta f = d(a, c) + d(b, d) - d(a, b) - d(c, d) \]\(\Delta f \lt 0\) ise hamle turu kısaltır. Tur uzunluğunu baştan \(O(n)\)'de toplamak yerine bu dört terimi hesaplamak, Δ-değerlendirmenin en bilinen örneğidir.
Swap hamlesi ise iki şehrin turdaki yerini değiştirir. İki şehrin her biri iki komşusundan ayrılıp yeni iki komşuya bağlandığı için, şehirler bitişik değilse dört kenar çıkar ve dört kenar girer:
0-1 sırt çantası problemi (KSP)
Model: kodlama ikili dizi \(x \in \{0, 1\}^n\).
\[ \max \sum_{i=1}^{n} p_i x_i \qquad \text{öyle ki} \qquad \sum_{i=1}^{n} w_i x_i \le C,\qquad x_i \in \{0, 1\} \]Arama mekaniği:
- Değerlendirme: \(g(x) = \sum_i p_i x_i - \lambda \cdot \max\bigl(0,\ \sum_i w_i x_i - C\bigr)\). Kâr eksi, kapasite aşımıyla orantılı ceza.
- 1-flip hamlesi: tek bir eşyanın durumunu değiştir (0 ↔ 1).
- Takas hamlesi (exchange): çantadaki bir eşyayı dışarıdaki bir eşyayla değiştir. Toplam ağırlığı kabaca koruduğu için kapasite sınırında gezinmeye uygundur.
1-flip için Δ da sabit zamanlıdır: \(i\). eşya eklenirse kâr \(p_i\) artar, ağırlık \(w_i\) artar; toplam ağırlık bir değişkende tutulursa yeni ceza da \(O(1)\)'de bulunur.
Graf boyama problemi (GCP)
Kodlama: renk vektörü \(c \in \{1, \dots, K\}^{|V|}\).
Değerlendirme: çakışan kenar sayısı, \(g(c) = \bigl|\{(u, v) \in E : c_u = c_v\}\bigr|\).
Hedef: \(g(c) = 0\) olan çakışmasız durumu bulmak.
1-recolor: çakışmada olan tek bir düğümün rengini değiştir.
Kempe zinciri: iki rengin bağlı bir alt graftaki atamalarını takas et.
Üst-strateji: sıfır çakışmaya ulaşınca \(K\)'yı azalt ve yeniden ara.
Bu üst-strateji “en az renk” optimizasyon problemini bir dizi karar problemine çevirir: “\(K\) renkle boyanabilir mi?” Her başarılı aramadan sonra \(K\) bir azaltılır; başarısız olunca son başarılı \(K\) en iyi bilinen değerdir.
Kapasiteli araç rotalama (CVRP)
Kodlama: dev tur (giant tour) ya da depoyla ayrılmış rota listeleri.
Amaç: toplam yol mesafesi + filo kullanımı en küçük.
Kapasite: bir rotadaki müşterilerin toplam talebi ≤ araç kapasitesi \(Q\).
Ceza: \(g(s) = \text{Mesafe}(s) + \lambda \cdot \max(0, \text{rota aşımı})\).
Rota içi: tek bir tur içinde 2-opt ve düğüm taşıma (relocate).
Rotalar arası taşıma: bir müşteriyi A rotasından B rotasına kaydır.
Cross-exchange: iki rota arasında alt dizileri takas et.
2-opt*: iki bağımsız rotanın kuyruk parçalarını değiştir.
Hub yerleşim problemi (p-hub medyan)
Düğümler: \(n\) başlangıç-varış noktası.
Hub'lar: tam olarak \(p\) düğüm aktarma merkezi olarak seçilir.
İndirim: hub'lar arası akış \(\alpha \lt 1\) katsayısıyla ucuzlar.
Kodlama: ikili hub vektörü \(y \in \{0, 1\}^n\), \(\sum_i y_i = p\).
Amaç: toplama + aktarma + dağıtım maliyetinin toplamı en küçük.
Komşuluk: 1-exchange, yani açık bir hub'ı kapalı bir düğümle takas et.
1-exchange hamlesi açık hub sayısını \(p\)'de tutar; böylece \(\sum_i y_i = p\) kısıtı temsilin içinde kalır ve hiçbir komşu olursuz olmaz. Her düğümün tek bir hub'a bağlandığı durumda, \(i\)'den \(j\)'ye giden \(W_{ij}\) akışının hub \(k\) ve \(m\) üzerinden tipik maliyeti şöyledir:
\[ W_{ij}\,\bigl(c_{ik} + \alpha\, c_{km} + c_{mj}\bigr) \]Maliyet ifadesi slaytta yok; “toplama + aktarma + dağıtım” tanımının yaygın matematiksel karşılığıdır.
Proje konuları: öncelikli uygulama alanları
Slaytlar, dönem projesi için üç uygulama alanında konular öneriyor. Her konunun dayandığı temel problem, formülasyonun nereden başlayacağını gösterir.
| Konu | Temel problem |
|---|---|
| Afet yönetimi ve insani lojistik (deprem sonrası müdahale) | |
| Afet sonrası acil tesis ve yardım merkezi yerleşimi | p-medyan / kapasitesiz hub yerleşim problemi (HLP) |
| Hasarlı yol ağında acil yardım dağıtımı | Zaman pencereli araç rotalama (VRPTW) |
| İnsani yardım hava ikmali ve tahliye için kaynak tahsisi | Çok boyutlu 0-1 sırt çantası (MKP) |
| Avrupa Yeşil Mutabakatı ve sürdürülebilir lojistik | |
| Batarya değişimi ya da şarj duraklı elektrikli araç rotalama | Kapasiteli araç rotalama (CVRP) |
| Dinamik elektrik tarifeleri altında enerji duyarlı üretim çizelgeleme | İş atölyesi / paralel makine çizelgeleme |
| Sağlık operasyonları ve kaynak optimizasyonu | |
| Ameliyathane ve cerrahi ekip çizelgeleme | Kutu paketleme (bin packing) |
| Evde sağlık hizmeti rotalama ve vardiya planlama (HHCR) | Zaman pencereli ve beceri eşleştirmeli araç rotalama |
Statik formülasyondan arama yörüngesine
Formülasyon arama uzayını kurar; arama algoritması bu uzayda bir yörünge çizer. Haftanın kalan iki bölümü bu yörüngeyi çizen yöntemleri anlatır: