Optimizasyon nedir?
Optimizasyon, belirli bir amaca ulaşmak için, belirli kısıtlar altında en iyi olurlu çözümü (best feasible solution) bulma sürecidir.
Tanımın iki anahtar kelimesi olurlu ve kısıt. Gerçek problemlerde kaynaklar sınırlıdır (zaman, para, kapasite, işgücü) ve kararlar birbirini etkiler: bir ürüne ayrılan makine saati öteki üründen eksilir. Aradığımız şey, bu sınırların içinde kalan seçenekler arasında en iyisidir.
Gündelik dille sorulan sorular hep aynı kalıptadır: neyi seçmeliyiz, neyi nereye atamalıyız, işleri hangi sırayla çizelgelemeliyiz, tesisi nereye yerleştirmeliyiz? Optimizasyon yalnızca hesap yapmak değildir; fiziksel ve mantıksal sınırlara uyarak en kaliteli çözümü bilinçli olarak arama sürecidir. Kısaca: kısıt altında karar verme bilimi.
Karar verme ve modelleme
Karar verme (decision making), mevcut seçenekler arasından en uygun ya da tercih edilen seçeneği belirlemek için gereken etkinliklerin tümüdür. Üç temel gereksinimi vardır:
- bir amaçlar ya da hedefler kümesi,
- seçenekleri değerlendirme yöntemleri,
- her eylem seçeneğinin sonuçlarının değerlendirilmesi.
Karar verme iki evrede ilerler. Birinci evrede amaçlar ve hedefler formüle edilir, kısıtlar sıralanır, seçenekler belirlenip değerlendirilir. İkinci evrede, verilen kısıtlar altında en iyi eylem seçeneği seçilir. Optimizasyon modelleri ikinci evreyi matematiğe döker; ama birinci evre iyi yapılmazsa doğru problemi çözmüş olmayız.
Model geliştirme bir döngüdür
Modelleme düz bir çizgi değildir. Model sürekli gerçeğe karşı doğrulanır; matematiksel çözüm pratikte uygulanamıyorsa geri dönülüp model ya da problem tanımı düzeltilir.
Bir optimizasyon probleminin parçaları
Model, bir problemin soyutlaması ya da matematiksel temsilidir. Bir dizi değişkenin matematiksel bir fonksiyonunu kısıtlar altında en büyüklemeye (maksimize) ya da en küçüklemeye (minimize) çalışan problemlere optimizasyon problemi denir.
Slaytlardaki örnek soru: “40 saatlik işçilik sınırını aşmadan kârı en büyüklemek için A ve B ürünlerinden kaçar adet üretmeliyiz?” Bu tek cümle bir modelin dört parçasını da içerir:
A ve B ürünlerinden kaçar tane üretelim ki kârımız en büyük olsun, ama toplam işçilik 40 saati aşmasın? Üretim tam sayı adetlerle yapılır.
- Karar değişkenleri (decision variables)
- Kontrol ettiğimiz büyüklükler: A ve B'nin üretim miktarları. Bütün değişkenlere değer atandığında bir aday çözüm elde edilir.
- Amaç fonksiyonu (objective function)
- En büyüklenen ya da en küçüklenen ölçü; çözüm kalitesinin tanımı. Burada toplam kâr.
- Değişken tanım kümeleri (variable domains)
- Değişkenlerin alabileceği değerler. Ürün adetleri negatif olmayan tamsayılardır: \(A, B \in \{0, 1, 2, \dots\}\).
- Kısıtlar (constraints)
- Bir çözümün olurlu sayılması için sağlanması gereken sert mantıksal koşullar. Burada toplam işçilik en fazla 40 saat.
Birim kârlara \(p_A, p_B\), birim işçilik sürelerine \(t_A, t_B\) dersek model şöyle yazılır:
\[ \max\; p_A A + p_B B \qquad \text{öyle ki}\qquad t_A A + t_B B \le 40,\qquad A, B \in \{0, 1, 2, \dots\} \]Slayt sayısal değer vermiyor; \(p\) ve \(t\) simgeleri örneği tamamlamak için eklendi.
Gerçek problemden matematiksel modele
Sözel bir problemi modele çevirirken izlenen beş adım:
- Kararı tanımla. Neye karar veriyoruz? Bu, karar değişkenlerini verir.
- Amacı belirle. Neyi en büyüklüyor ya da en küçüklüyoruz?
- Kısıtları formüle et. Hangi kaynak sınırları ve mantıksal koşullar var?
- Değişkenlerin tanım kümelerini belirle. Sürekli mi, tamsayı mı, ikili mi; alt ve üst sınırlar neler?
- Modeli doğrula. Model gerçek sistemin davranışını yansıtıyor mu? Bilinen durumlarla sınanır, geçer ya da kalır.
Genel matematiksel form
Bir optimizasyon problemi genel biçimde şöyle yazılır:
\[ \begin{aligned} \underset{x \in \mathbb{R}^n}{\text{minimize}}\quad & f_i(x), && i = 1, 2, \dots, M \\ \text{subject to}\quad & h_j(x) = 0, && j = 1, 2, \dots, J \\ & g_k(x) \le 0, && k = 1, 2, \dots, K \end{aligned} \]Burada \(f_i\), \(h_j\) ve \(g_k\), tasarım vektörü \(x = (x_1, x_2, \dots, x_n)^T\) üzerinde tanımlı fonksiyonlardır. \(x\)'in bileşenleri \(x_i\) tasarım ya da karar değişkenleridir; sürekli, ayrık ya da ikisinin karışımı olabilirler. \(h_j\) eşitlik kısıtlarını (\(J\) tane), \(g_k\) eşitsizlik kısıtlarını (\(K\) tane) verir.
Bu form genelliği kaybettirmez. Bir maksimizasyon problemi minimizasyona çevrilebilir, çünkü \(\max f(x) = -\min\,(-f(x))\). \(g(x) \ge 0\) biçimindeki bir kısıt da \(-g(x) \le 0\) olarak yazılır.
Amaç sayısına göre
| Amaç sayısı | Problem türü |
|---|---|
| \(M = 1\) | Tek amaçlı (single-objective) |
| \(M = 2\) veya \(3\) | Çok amaçlı (multi-objective) |
| \(M \gt 3\) | Çok-fazla-amaçlı (many-objective) |
Slaytta many-objective için \(M \ge 3\) yazıyor. Literatürde \(M = 3\) genellikle çok amaçlı sayılır; many-objective terimi çoğunlukla dört ve daha fazla amaç için kullanılır.
Karar uzayı ve amaç uzayı
Karar değişkenlerinin oluşturduğu uzaya tasarım uzayı ya da arama uzayı (design / search space) denir; sürekli durumda bu \(\mathbb{R}^n\)'dir. Amaç fonksiyonlarının değerlerinin oluşturduğu uzay ise amaç uzayıdır (objective space). Her karar vektörü \(x\), \(F(x) = (f_1(x), \dots, f_M(x))\) eşlemesiyle amaç uzayında bir noktaya gider. Arama algoritmaları karar uzayında dolaşır; çözümlerin kalitesini ise amaç uzayında karşılaştırırız.
Kısıtlar ve olurluluk
- Kısıtlı ve kısıtsız problemler (constrained vs. unconstrained). Kısıtlar, çözümlerin sağlaması gereken koşullardır.
- Sert ve yumuşak kısıtlar (hard vs. soft). Sert kısıt mutlaka sağlanmalıdır, örneğin bir kamyonun taşıma kapasitesi. Yumuşak kısıt ihlal edilebilir ama ihlal amaç fonksiyonunda cezalandırılır, örneğin bir çalışanın tercih ettiği vardiya.
- Eşitlik ve eşitsizlik kısıtları (equality vs. inequality).
- Olurlu ve olursuz çözümler (feasible vs. infeasible). Olurlu çözüm bütün kısıtları sağlar; en az bir kısıtı ihlal eden çözüm olursuzdur.
Optimizasyonu bir arama uzayı olarak düşünmek işe yarar. Her aday çözüm bir arazideki bir noktadır; arazinin bir kısmı olurlu bölgedir, kalanı olursuz. Noktanın yüksekliği amaç değeridir ve optimum çözüm bu arazinin en derin (ya da en yüksek) noktasıdır. Algoritmalar, bu arazide noktadan noktaya nasıl ilerleyeceğimizi belirleyen araçlardır; her adımda amaç fonksiyonunun kalite ölçüsünü hesaplarlar.
Yerel ve global optimum
Yerel optimum (local optimum): arama uzayında bütün komşu noktalarından daha iyi olan nokta.
Global optimum (global optimum): arama uzayındaki bütün noktalardan daha iyi olan nokta.
“Komşu” kavramı hangi noktaların birbirine yakın sayıldığına bağlıdır. Sürekli problemlerde bu uzaklıkla tanımlanır; ayrık problemlerde ise seçtiğimiz komşuluk yapısı belirler (Not 02 ve 03). Bir yerel optimumda algoritma kazandığını sanır: hiçbir komşu daha iyi değildir. Oysa çok daha iyi bir tepe başka bir yerde olabilir. Kendi hâline bırakılan, hep daha iyiye giden bir algoritma ilk bulduğu tepede kalır ve gerçek zirveyi hiç görmez.
Optimizasyon problemlerinin sınıflandırılması
| Ölçüt | Sınıflar |
|---|---|
| Kısıtların türü | Kısıtlı / kısıtsız |
| Denklemlerin yapısı | Doğrusal / doğrusal olmayan; ayrıca dışbükey / dışbükey olmayan, türevlenebilir / türevlenemez |
| Değişkenlerin deterministik olup olmaması | Deterministik / stokastik |
| Tasarım değişkenlerinin alabileceği değerler | Sürekli / tamsayı-ayrık / karışık |
| Fonksiyonların ayrılabilirliği | Ayrılabilir, yani \(f(x) = \sum_i f_i(x_i)\) / ayrılamaz |
| Amaç fonksiyonu sayısı | Tek amaçlı / çok amaçlı |
Slayttaki hiyerarşi bu ölçütleri art arda sorulan sorular olarak dizer. Bu dersin odağı tamsayı/ayrık daldır: kararların sayılabilir ve birbirinden ayrık olduğu, olasılık sayısının hızla patladığı problemler.
Ayrık optimizasyon
- Karar değişkenleri ayrık, tamsayı, ikili (binary) ya da kombinatoryaldir (sıralama, atama, alt küme seçimi).
- Olurlu küme çoğunlukla sonludur ama muazzam büyüklükte olabilir.
- Birçok önemli planlama ve tasarım problemi ayrıktır.
Ayrık optimizasyon evet/hayır kararlarıyla, permütasyonlarla ve atamalarla uğraşır. Slaytlardaki iki örnek iki tipik karar türünü temsil eder.
Sırt çantası problemi (knapsack)
Toplam ağırlık sınırını aşmadan toplam değeri en büyükleyen eşya alt kümesini seç. Her eşya için tek karar: alınır mı? \(x_i \in \{0, 1\}\).
Gezgin satıcı problemi (TSP)
Her düğümü tam bir kez ziyaret eden en düşük ağırlıklı çevrimi (Hamilton çevrimi) bul. Karar bir sıradır: şehirlerin permütasyonu.
Çalışılmış örnek: slayttaki sırt çantası
Kapasite 10; altı eşyanın (ağırlık, değer) çiftleri: (3, 5), (2, 3), (2, 3), (4, 7), (1, 2), (5, 6). Altı eşya için \(2^6 = 64\) alt küme vardır, hepsi denenebilir. Sonuç: ağırlıkları 4, 3, 2 ve 1 olan eşyalar alınır; toplam ağırlık 10, toplam değer 17. Ağırlığı 2 olan iki eşya özdeş olduğu için iki ayrı optimal çözüm vardır.
Bu çözüm slaytta yok; tüm alt kümeler sayılarak bulundu. Değer/ağırlık oranına göre açgözlü seçim (1, 4, 3, 2) burada şans eseri optimumu verir; genelde vermez.
Kombinatoryal patlama
Simetrik TSP'de \(n\) şehir için farklı tur sayısı
\[ \frac{(n-1)!}{2} \]olur: başlangıç şehri sabitlenir (\((n-1)!\) sıra kalır) ve bir turun iki yönü aynı sayılır (\(/2\)). Bu sayı çok hızlı büyür:
| Şehir sayısı \(n\) | Farklı tur | Saniyede \(10^9\) tur denetlenirse tam sayım |
|---|---|---|
| 5 | 12 | anında |
| 10 | 181.440 | ≈ 0,2 milisaniye |
| 15 | ≈ 4,36 × 1010 | ≈ 44 saniye |
| 20 | ≈ 6,08 × 1016 | ≈ 1,9 yıl |
| 25 | ≈ 3,10 × 1023 | ≈ 9,8 milyon yıl |
Bütün turları sayarak çözmek gerçek ölçekli problemlerde hesaplama açısından imkânsızdır. Zorluk en iyi çözümü tanımlamakta değil, onu verimli biçimde bulmaktadır.
Slayttaki değerler n = 10 için 181.440 ve n = 20 için ≈ 6,08 × 1016; süre sütunu karşılaştırma için eklendi.
Çözüm yaklaşımları
| Kesin yöntemler (exact) | Sezgiseller (heuristics) | Üst-sezgiseller (metaheuristics) | |
|---|---|---|---|
| Garanti | Optimal çözümü garanti eder ya da çözüm olmadığını kanıtlar. | Optimallik garantisi yok. | Garanti yok, ama yerel optimumlardan kaçmada çok etkili. |
| Mekanizma | Sistematik sayım ve arama (ör. doğrusal ve tamsayılı programlama). | Probleme özgü, pratik kurallara dayalı algoritmalar; iyi çözümleri hızla bulur. | Üst düzey, probleme bağımsız arama çerçeveleri (ör. benzetimli tavlama). |
| Ölçeklenebilirlik | Kombinatoryal patlama yüzünden zayıf; küçük ya da basit problemler için uygun. | Çok iyi; problemin yapısına dair derin bilgiden yararlanır. | Büyük ve karmaşık arama uzayları için çok uygun. |
Dönem projesi bu üç sütunu yan yana getirir: küçük örneklerde kesin bir yöntemle optimum bulunur (Ödev 2), sonra bir sezgisel ya da üst-sezgiselin bu optimuma ne kadar yaklaştığı ölçülür.
Arama paradigmaları
Yapıcı ve değiştirici arama
Yapıcı arama (constructive)
Kısmi aday çözümler üzerinde çalışır; çözümü sıfırdan adım adım genişletir. Örnek: en yakın komşu sezgiseli, her adımda henüz ziyaret edilmemiş en yakın düğüme gider.
Değiştirici arama (perturbative)
Tam, eksiksiz aday çözümler üzerinde çalışır; bileşenleri bir hamle (move, step) ile değiştirir. Örnek: SAT'ta 1-flip komşuluğu, tek bir değişkenin doğruluk değerini çevirir.
Sistematik ve yerel arama
Sistematik arama
Arama uzayını eksiksiz tarar. Optimumu bulmayı ya da çözüm olmadığını kesin olarak kanıtlamayı garanti eder. Zaman kısıtı gevşekse ya da matematiksel kanıt şartsa gerekir.
Stokastik yerel arama
Yerel değerlendirme ölçütleriyle komşu konumlara geçer. Tam değildir (garanti yok), ama çok zor kombinatoryal problemlerde hızla son derece iyi çözümler üretir.
Bir SLS algoritmasının parçaları
Stokastik yerel arama (SLS) algoritmaları rastgele seçimler ve yerel sezgisel bilgiyle konumdan komşu konuma ilerler. Döngüyü dört parça oluşturur:
- Başlatma (initialization)
- Başlangıç konumları üzerindeki olasılık dağılımı; örneğin tekdüze rastgele seçim.
- Adım fonksiyonu (step function)
- Mevcut konumdan komşu bir konuma geçişi belirler; komşuları sıralamak için değerlendirme fonksiyonunu kullanır.
- Bellek durumu (memory state)
- Döngüye girmemek için geçmiş hamleleri izler; gelişmiş SLS yöntemlerinde kullanılır.
- Sonlandırma (termination)
- Döngüyü bitiren koşul; örneğin azami adım sayısına ya da bir yerel minimuma ulaşmak.
Bu parçaların biçimsel tanımı Not 03'te.
Yoğunlaştırma ve çeşitlendirme
Yoğunlaştırma (intensification)
Değerlendirme fonksiyonunu açgözlü biçimde kullanarak umut verici, bilinen bölgelerde çözümü derinlemesine iyileştirmek.
Risk: erken yakınsama, yerel optimuma takılmak.
Çeşitlendirme (diversification)
Arama uzayının henüz keşfedilmemiş bölgelerini incelemek ve böylece aramanın durgunlaşmasını önlemek.
Risk: verimsiz, amaçsız arama.
Gelişmiş SLS yöntemlerini tanımlayan şey bu iki karşıt kuvveti dengeleyebilmeleridir: umut verici bir vadiyi derinlemesine kazarken, daha derin bir vadiyi kaçırmamak için düzenli olarak başka yerlere sıçramak.
No Free Lunch teoremi
Hiçbir optimizasyon algoritması, olası bütün problemler için evrensel olarak en iyi değildir.
Wolpert ve Macready'nin (1997) gösterdiği sonuca göre, olası bütün amaç fonksiyonları üzerinden ortalama alındığında her arama algoritmasının başarımı aynıdır. Bir problem sınıfında üstün olan algoritma, bunun bedelini başka bir sınıfta öder. Pratik sonuçları:
- Yapı önemlidir. Bir problem sınıfında çok iyi çalışan bir algoritma başka bir sınıfta felaket sonuçlar verebilir.
- Algoritma seçimi problemin matematiksel yapısına dayanmalıdır.
- Değişken temsili, komşuluk yapıları ve parametre ayarları çözümü doğrudan belirler.
- Deneysel karşılaştırma ve analiz, optimizasyon mühendisliğinin ayrılmaz bir parçasıdır. Projede kesin ve sezgisel yöntemleri karşılaştırmamızın nedeni budur.
Özet ve dönem yol haritası
- Optimizasyon, belirli bir amaca yönelik, kısıtlı bir arama problemidir.
- Ayrık optimizasyon, kombinatoryal yapısı yüzünden devasa arama uzayları üretir.
- Büyük ölçekli problemlerde kesin optimum garantisi yerine akıllı sezgisel aramalara ihtiyaç duyarız.
Dönem projesinin adımları
- Problem tanımıÖdev 1
- Matematiksel modellemeÖdev 1
- Kesin çözüm analiziÖdev 2
- Sezgisel tasarımıÖdev 3 + proje
- Deneysel sonuçlarFinal proje
Ödevlerin ayrıntıları ana sayfada.