Python ile Diferansiyel Evrim Kullanarak Tamsayı Kısıtlı Daire Yerleştirme Optimizasyonu

Python ile Diferansiyel Evrim Kullanarak Tamsayı Kısıtlı Daire Yerleştirme Optimizasyonu

Daire yerleştirme problemi, belirli bir alan içerisine mümkün olan en fazla sayıda veya en büyük çaplı daireleri, çakışmayacak şekilde yerleştirmeyi amaçlayan klasik bir optimizasyon problemidir. Bu makalede, özellikle endüstriyel uygulamalarda sıkça karşılaşılan tamsayı kısıtları altında daire yerleştirme probleminin, güçlü bir evrimsel algoritma olan Diferansiyel Evrim (DE) kullanılarak Python ile nasıl optimize edileceği detaylı bir şekilde incelenecektir.

1. Daire Yerleştirme Problemi ve Önemi

Daire yerleştirme, matematiksel optimizasyonun en zorlu ve ilgi çekici alanlarından biridir. Genellikle NP-hard olarak kabul edilen bu problem, çeşitli endüstriyel ve bilimsel senaryolarda karşımıza çıkar.

1.1. Problem Tanımı ve Amaç

Temel olarak, daire yerleştirme problemi, belirli bir geometrik bölgeye (genellikle bir dikdörtgen veya başka bir daire) önceden tanımlanmış bir dizi daireyi (aynı veya farklı yarıçaplarda) birbirleriyle çakışmayacak şekilde sığdırmayı amaçlar. Amaç, genellikle yerleştirilebilecek daire sayısını maksimize etmek veya belirli sayıda daireyi en küçük alana sığdırmaktır. Tamsayı kısıtları ise dairelerin konumlarının (x, y koordinatları) veya yarıçaplarının belirli bir ızgara üzerinde olmasını ya da ayrık değerler almasını gerektirir.

1.2. Gerçek Dünya Uygulamaları

Daire yerleştirme probleminin pratik uygulamaları oldukça geniştir:

• Malzeme Kesimi: Metal, kumaş, cam gibi malzemelerden dairesel parçaların en az fireyle kesilmesi.
• Ambalajlama ve Lojistik: Dairesel ürünlerin kutulara veya konteynerlere en verimli şekilde yerleştirilmesi.
• Elektronik Tasarım: Baskılı devre kartları (PCB) üzerinde dairesel bileşenlerin düzenlenmesi.
• Uzay ve Savunma: Anten dizilimleri veya sensör yerleşimleri.
• Şehir Planlama: Kentsel alanlarda dairesel hizmet noktalarının (örn. baz istasyonları) optimal konumlandırılması.

1.3. Zorluklar ve Karmaşıklık

Bu problemin karmaşıklığı, daire sayısının artmasıyla üstel olarak büyür. Çakışmama kısıtları doğrusal olmayan yapıya sahiptir ve tamsayı kısıtları, sürekli optimizasyon tekniklerinin doğrudan uygulanmasını engeller, bu da problemin çözümünü daha da zorlaştırır. Geleneksel optimizasyon yöntemleri genellikle yerel optimumlarda takılı kalabilirken, evrimsel algoritmalar daha geniş bir arama uzayını keşfetme yeteneği sunar.

2. Diferansiyel Evrim Algoritmasının Temelleri

Diferansiyel Evrim (DE), sürekli ve küresel optimizasyon problemleri için etkili bir meta-sezgisel algoritmadır. Sezgisel doğası gereği, zorlu ve doğrusal olmayan problemlerin çözümünde başarılıdır.

2.1. Evrimsel Algoritmalara Genel Bakış

Evrimsel algoritmalar (EA’lar), doğal seçilim ve genetik mutasyon gibi biyolojik evrim prensiplerinden esinlenerek geliştirilmiş optimizasyon teknikleridir. Popülasyon tabanlıdırlar ve potansiyel çözümlerden oluşan bir “popülasyonu” sürekli olarak iyileştirerek optimum çözüme yaklaşmaya çalışırlar. Genetik Algoritmalar, Parçacık Sürü Optimizasyonu ve Diferansiyel Evrim, bu kategorinin popüler örnekleridir.

2.2. Diferansiyel Evrim’in Çalışma Prensibi

DE, diğer evrimsel algoritmalara benzer şekilde bir popülasyonla başlar, ancak yeni aday çözümler üretme mekanizması farklıdır. Temel adımları şunlardır:

1. Başlangıç Popülasyonu: Belirli bir aralıkta rastgele oluşturulan çözüm adaylarından (vektörler) oluşan bir popülasyon başlatılır.
2. Mutasyon: Her hedef vektör (X_i) için, popülasyondan rastgele seçilen üç farklı vektör (X_a, X_b, X_c) kullanılarak bir “mutant vektör” (V_i) oluşturulur. En yaygın mutasyon stratejisi: V_i = X_a + F * (X_b - X_c). Burada F, diferansiyel ağırlık (scaling factor) olarak adlandırılan bir sabittir.
3. Çaprazlama (Crossover): Mutant vektör (V_i) ile hedef vektör (X_i) arasında çaprazlama yapılarak bir “deneme vektörü” (U_i) oluşturulur. Bu adım, her bir boyut için belirli bir olasılıkla (çaprazlama oranı, CR) mutant vektörden veya hedef vektörden değerler alır.
4. Seçilim (Selection): Deneme vektörü (U_i) ile hedef vektör (X_i) arasındaki uygunluk değerleri karşılaştırılır. Eğer U_i‘nin uygunluğu daha iyiyse, X_i yerine U_i yeni popülasyona geçer; aksi takdirde X_i korunur.

Bu adımlar, belirli bir iterasyon sayısına veya bir durdurma kriterine ulaşana kadar tekrarlanır.

2.3. Avantajları ve Dezavantajları

Avantajları:

• Az sayıda parametreye (F, CR, popülasyon boyutu) sahip olması ve bu parametrelerin genellikle kolay ayarlanabilmesi.
• Küresel optimumu bulma konusunda güçlü olması.
• Doğrusal olmayan ve dışbükey olmayan problemler için uygun olması.

Dezavantajları:

• Bazı durumlarda yavaş yakınsama.
• Parametre seçimi performans üzerinde etkili olabilir.

3. Tamsayı Kısıtlı Daire Yerleştirme Probleminin Modellenmesi

Daire yerleştirme problemini Diferansiyel Evrim ile çözmek için, öncelikle problemi matematiksel olarak formüle etmeli ve bir amaç fonksiyonu tanımlamalıyız.

3.1. Amaç Fonksiyonu Tanımı

Amacımız, belirli bir alana yerleştirilecek daire sayısını maksimize etmek veya belirli sayıda daireyi en küçük alana sığdırmak olabilir. En yaygın yaklaşım, dairelerin çakışmasını cezalandıran bir uygunluk (fitness) fonksiyonu tanımlamaktır. Örneğin, belirli bir dikdörtgen alana N adet daireyi yerleştirirken, amaç fonksiyonu dairelerin çakışma miktarını minimize etmeye odaklanabilir. Bu durumda, uygunluk değeri ne kadar düşükse çözüm o kadar iyidir.

Bir çözüm vektörü X = [x1, y1, r1, x2, y2, r2, ..., xN, yN, rN] şeklinde temsil edilebilir. Burada (xi, yi) i-inci dairenin merkezi, ri ise yarıçapıdır.

3.2. Kısıtlayıcılar (Çakışmama, Sınırlar, Tamsayı Kısıtları)

Problemin çözümünü kısıtlayan temel unsurlar şunlardır:

• Çakışmama Kısıtı: Herhangi iki daire i ve j için, merkezleri arasındaki mesafe, yarıçaplarının toplamından küçük olmamalıdır: sqrt((xi-xj)^2 + (yi-yj)^2) >= ri + rj.
• Sınır Kısıtı: Tüm daireler, tanımlanan alanın (örn. dikdörtgenin) içinde kalmalıdır. Örneğin, xmin <= xi - ri, xi + ri <= xmax, vb.
• Tamsayı Kısıtları: Daire merkezlerinin x ve y koordinatları veya yarıçapları gibi parametreler, sadece tamsayı değerler alabilir. Bu, problemin doğasını önemli ölçüde değiştirir ve standart DE uygulamalarını zorlar.

3.3. Problem Uzayının Temsili

DE algoritması sürekli değerlerle çalıştığı için, tamsayı kısıtlarını doğrudan ele almak için bazı stratejiler geliştirmemiz gerekir. Bir çözüm vektöründeki her bir değişken (x, y, r), algoritma tarafından sürekli bir aralıkta optimize edilir. Daha sonra bu sürekli değerler, tamsayı kısıtlarına uyması için işlenir.

4. Python ile Diferansiyel Evrim Uygulaması

Python, bilimsel hesaplama ve optimizasyon için zengin kütüphaneleri sayesinde Diferansiyel Evrim gibi algoritmaları uygulamak için ideal bir platformdur.

4.1. Gerekli Kütüphaneler (SciPy, NumPy)

Python'da Diferansiyel Evrim'i uygulamak için başlıca kütüphaneler:

• NumPy: Sayısal işlemler, vektör ve matris manipülasyonları için temel kütüphane.
• SciPy: Bilimsel ve teknik hesaplama araçları sunar. Özellikle scipy.optimize modülü, Diferansiyel Evrim'in hazır bir uygulamasını (differential_evolution) içerir.

import numpy as np
from scipy.optimize import differential_evolution

4.2. Amaç Fonksiyonunun Kodlanması

Amaç fonksiyonu, bir çözüm vektörünü (dairelerin konum ve yarıçaplarını) girdi olarak alır ve bu çözümün "kötülüğünü" (çakışma miktarını ve sınır dışına taşmayı) temsil eden bir sayı döndürür. DE algoritması bu değeri minimize etmeye çalışır.

def objective_function(solution_vector, num_circles, container_width, container_height):
    # solution_vector: [x1, y1, r1, x2, y2, r2, ...]
    # Tamsayı kısıtları için yuvarlama burada yapılabilir
    solution_vector = np.round(solution_vector) # Tamsayı kısıtını burada uyguluyoruz

    penalty = 0
    circles = []
    for i in range(num_circles):
        x = solution_vector[i * 3]
        y = solution_vector[i * 3 + 1]
        r = solution_vector[i * 3 + 2]
        circles.append({'x': x, 'y': y, 'r': r})

        # Sınır kısıtları
        if not (0 <= x - r and x + r <= container_width and \
                0 <= y - r and y + r <= container_height):
            penalty += 1000 # Büyük bir ceza ekle

    # Çakışma kısıtları
    for i in range(num_circles):
        for j in range(i + 1, num_circles):
            c1 = circles[i]
            c2 = circles[j]
            dist = np.sqrt((c1['x'] - c2['x'])2 + (c1['y'] - c2['y'])2)
            min_dist = c1['r'] + c2['r']
            if dist < min_dist:
                penalty += (min_dist - dist) * 100 # Çakışma miktarına göre ceza

    return penalty

Yukarıdaki örnekte, np.round() fonksiyonu ile tamsayı kısıtı basitçe uygulanmıştır. Bu, DE'nin sürekli uzayda arama yapıp, uygunluk hesaplanmadan önce aday çözümü tamsayıya yuvarlaması anlamına gelir.

4.3. DE Algoritmasının Yapılandırılması

scipy.optimize.differential_evolution fonksiyonu, DE algoritmasını çalıştırmak için kullanılır. Bu fonksiyon, amaç fonksiyonunu, değişkenlerin sınırlarını ve DE parametrelerini (popülasyon boyutu, F, CR, iterasyon sayısı) alır.

# Parametreler
num_circles = 5
container_width = 100
container_height = 100

# Her daire için (x, y, r) -> 3 değişken
# x: [r, container_width - r]
# y: [r, container_height - r]
# r: [min_radius, max_radius]
# Basitlik adına r'yi de tamsayı kısıtlı kabul edelim ve sabit tutalım
min_r = 5
max_r = 15 # Yarıçaplar için de tamsayı kısıtı olabilir

bounds = []
for _ in range(num_circles):
    # x koordinatı için sınırlar
    bounds.append((min_r, container_width - min_r))
    # y koordinatı için sınırlar
    bounds.append((min_r, container_height - min_r))
    # r yarıçapı için sınırlar (eğer değişken ise)
    bounds.append((min_r, max_r))

# Diferansiyel Evrim'i çalıştırma
result = differential_evolution(
    objective_function,
    bounds,
    args=(num_circles, container_width, container_height),
    strategy='best1bin',
    maxiter=1000,
    popsize=10,
    tol=0.01,
    mutation=(0.5, 1.0),
    recombination=0.7,
    seed=42
)

print("En iyi çözüm bulundu (yuvarlanmış):", np.round(result.x))
print("Minimum ceza (uygunluk):", result.fun)

5. Kısıtların Yönetimi ve Optimizasyon Stratejileri

Tamsayı kısıtları, DE gibi sürekli optimizasyon algoritmaları için özel stratejiler gerektirir.

5.1. Sert Kısıtların Ele Alınması (Penalty Fonksiyonları)

Çakışmama ve sınır dışına çıkmama gibi "sert kısıtlar", amaç fonksiyonuna eklenen büyük cezalar (penalty) ile yönetilir. Eğer bir çözüm bu kısıtları ihlal ediyorsa, uygunluk değeri önemli ölçüde artırılır, böylece algoritma bu çözümlerden kaçınmaya teşvik edilir. Yukarıdaki kod örneğinde bu yaklaşım kullanılmıştır.

5.2. Tamsayı Kısıtlarının Entegrasyonu (Yuvarlama, Karma Yaklaşım)

Tamsayı kısıtlarını ele almak için birkaç yaygın strateji bulunmaktadır:

1. Basit Yuvarlama: En basit yöntem, DE'nin sürekli uzayda arama yapmasına izin vermek ve amaç fonksiyonunu çağırmadan hemen önce veya amaç fonksiyonunun içinde, ilgili değişkenleri en yakın tamsayıya yuvarlamaktır (np.round()). Bu yöntem hızlıdır ancak optimal tamsayı çözümlerini kaçırma riski taşır çünkü algoritma yuvarlama nedeniyle oluşan "düz" bölgelerde etkili arama yapamayabilir.
2. Karma Yaklaşım (Hybrid Approach): DE'yi sürekli değişkenler için kullanırken, tamsayı değişkenler için ayrı bir optimizasyon adımı (örn. yerel arama veya kısıt programlama) entegre edilebilir. Bu daha karmaşık bir yaklaşımdır ancak daha iyi sonuçlar verebilir.
3. Özel Operatörler: DE'nin mutasyon ve çaprazlama operatörlerini tamsayı değişkenlere uygun hale getirmek. Ancak bu, standart scipy.optimize.differential_evolution fonksiyonunun doğrudan kullanımını zorlaştırır ve algoritmanın manuel olarak uygulanmasını gerektirebilir.

Bu makalede, basit yuvarlama stratejisi (1. madde) kullanılmıştır. Pratik uygulamalarda, problemin hassasiyetine göre daha gelişmiş yöntemler denenebilir.

5.3. Parametre Ayarlama ve İterasyon Yönetimi

Diferansiyel Evrim'in performansı, popsize (popülasyon boyutu), mutation (F) ve recombination (CR) parametrelerinin seçimine bağlıdır. Bu parametreler genellikle deneme yanılma yoluyla veya adaptif stratejilerle ayarlanır. maxiter (maksimum iterasyon sayısı) ise algoritmanın ne kadar süre çalışacağını belirler. Daha fazla iterasyon genellikle daha iyi sonuçlar verir ancak hesaplama süresini artırır.

Yaygın olarak kullanılan başlangıç değerleri: popsize=10*D (D: problem boyutu), F=0.5-1.0, CR=0.7-0.9.

6. Uygulama Sonuçları ve Değerlendirme

Yukarıdaki Python kodunu kullanarak basit bir tamsayı kısıtlı daire yerleştirme senaryosunu değerlendirelim.

6.1. Örnek Senaryo ve Veri Seti

Bir 100x100 birimlik kare alana, 5 adet daireyi, yarıçapları 5 ile 15 birim arasında tamsayı değerler alacak şekilde ve merkez koordinatları da tamsayı olacak şekilde yerleştirmeye çalışalım. Amaç, çakışmayı ve sınır dışına çıkmayı minimize etmektir.

Daire Sayısı: 5
Konteyner Boyutları: Genişlik=100, Yükseklik=100
Yarıçap Sınırları: 5 <= r <= 15 (tamsayı)

6.2. Optimizasyon Süreci ve Gözlemler

Diferansiyel Evrim algoritması, başlangıçta rastgele oluşturulan daire yerleşimlerinden başlayarak, mutasyon, çaprazlama ve seçilim adımları aracılığıyla popülasyonu sürekli olarak iyileştirir. Amaç fonksiyonu, her iterasyonda dairelerin çakışma ve sınır ihlali miktarını hesaplar ve algoritma daha düşük ceza puanına sahip çözümlere doğru ilerler.

Tamsayı kısıtları nedeniyle, algoritma sürekli uzayda arama yaparken yuvarlama işlemi, uygunluk yüzeyinde "basamaklar" oluşturur. Bu durum, algoritmanın bazen yerel optimumlarda takılmasına neden olabilir. Ancak DE'nin küresel arama yeteneği sayesinde, genellikle tatmin edici sonuçlara ulaşılır.

6.3. Elde Edilen Çözümlerin Analizi

Yukarıdaki örnek kodun çalıştırılması sonucunda elde edilen result.x vektörü, optimize edilmiş daire merkezleri ve yarıçaplarını içerir. result.fun değeri ise elde edilen en iyi çözümün ceza puanını gösterir. İdeal bir senaryoda, bu ceza puanı sıfıra yakın olmalıdır, bu da dairelerin hiç çakışmadığı ve sınırlar içinde kaldığı anlamına gelir.

Çözüm vektörünü görselleştirmek, elde edilen yerleşimin kalitesini anlamak için kritik öneme sahiptir. Örneğin, bir matplotlib çizimi ile dairelerin konteyner içindeki konumları gösterilebilir.

# Görselleştirme (Örnek)
import matplotlib.pyplot as plt

# ... (Yukarıdaki DE çalıştırma kodu) ...

if result.fun < 100: # Kabul edilebilir bir çözüm bulunduysa
    optimized_circles = []
    solution = np.round(result.x)
    for i in range(num_circles):
        x = solution[i * 3]
        y = solution[i * 3 + 1]
        r = solution[i * 3 + 2]
        optimized_circles.append({'x': x, 'y': y, 'r': r})

    fig, ax = plt.subplots(figsize=(8, 8))
    ax.set_xlim(0, container_width)
    ax.set_ylim(0, container_height)
    ax.set_aspect('equal', adjustable='box')

    for circle_data in optimized_circles:
        circle = plt.Circle((circle_data['x'], circle_data['y']), circle_data['r'],
                            color='blue', alpha=0.6, ec='black')
        ax.add_patch(circle)
        ax.text(circle_data['x'], circle_data['y'], f'R={int(circle_data["r"])}',
                color='white', ha='center', va='center', fontsize=8)

    plt.title(f'Optimize Edilmiş Daire Yerleşimi (Ceza: {result.fun:.2f})')
    plt.xlabel('X Koordinatı')
    plt.ylabel('Y Koordinatı')
    plt.grid(True)
    plt.show()
else:
    print("Tatmin edici bir çözüm bulunamadı veya ceza çok yüksek.")

Bu görselleştirme, dairelerin birbirine değip değmediğini ve konteyner içinde kalıp kalmadığını net bir şekilde görmemizi sağlar.

7. Sonuç

Bu makalede, tamsayı kısıtlı daire yerleştirme probleminin karmaşıklığına ve bu zorluğun üstesinden gelmek için Diferansiyel Evrim algoritmasının Python ile nasıl kullanılabileceğine odaklandık. Diferansiyel Evrim, esnek yapısı ve küresel arama yeteneği sayesinde bu tür NP-hard problemler için güçlü bir çözüm sunmaktadır.

Python'ın scipy.optimize modülü aracılığıyla Diferansiyel Evrim'i kolayca uygulayabildiğimizi ve tamsayı kısıtlarını basit yuvarlama stratejisiyle entegre edebildiğimizi gördük. Amaç fonksiyonunun dikkatli bir şekilde tanımlanması ve kısıtların ceza terimleri aracılığıyla yönetilmesi, başarılı bir optimizasyon için anahtardır.

7.1. Bulguların Özeti

Diferansiyel Evrim, daire yerleştirme gibi doğrusal olmayan ve kısıtlı optimizasyon problemlerinde etkili bir araçtır. Tamsayı kısıtları, algoritmanın sürekli arama uzayını tamsayı çözümlere yönlendirmek için yuvarlama gibi basit ama etkili stratejilerle ele alınabilir. Bu yaklaşım, malzeme kesimi, ambalajlama ve lojistik gibi birçok gerçek dünya uygulamasında değerli optimizasyonlar sağlayabilir.

7.2. Diferansiyel Evrimin Katkısı

Diferansiyel Evrim, yerel optimumlara takılma riskini azaltarak ve geniş bir çözüm uzayını keşfederek, geleneksel yöntemlerin zorlandığı durumlarda bile rekabetçi çözümler sunar. Parametrelerinin ayarlanabilirliği ve nispeten basit uygulama yapısı, onu mühendislik ve bilimsel problemler için cazip bir seçenek haline getirir.

7.3. Gelecek Çalışma Alanları

Gelecekteki çalışmalar, tamsayı kısıtlarını daha sofistike yöntemlerle (örn. karma tamsayı programlama ile hibrit yaklaşımlar) entegre etmeye odaklanabilir. Ayrıca, farklı mutasyon ve çaprazlama stratejileri deneyerek veya adaptif parametre ayarlama teknikleri kullanarak Diferansiyel Evrim'in performansını daha da iyileştirmek mümkündür. Çok amaçlı daire yerleştirme problemleri (örn. hem daire sayısını hem de yerleşim süresini optimize etme) de ilgi çekici araştırma alanlarıdır.

8. Sıkça Sorulan Sorular (SSS)

Daire yerleştirme neden zor bir problemdir?

Daire yerleştirme, dairelerin çakışmaması gibi doğrusal olmayan kısıtlar ve genellikle büyük bir arama uzayı nedeniyle NP-hard bir problemdir. Daire sayısı arttıkça çözüm uzayı üstel olarak büyür, bu da geleneksel yöntemlerle optimal çözümü bulmayı imkansız hale getirir.

Diferansiyel Evrim yerine başka algoritmalar kullanılabilir mi?

Evet, Genetik Algoritmalar, Parçacık Sürü Optimizasyonu, Simüle Tavlama veya Karınca Kolonisi Optimizasyonu gibi diğer evrimsel ve meta-sezgisel algoritmalar da daire yerleştirme problemleri için kullanılabilir. Her algoritmanın kendine özgü avantajları ve dezavantajları vardır ve performans, problemin spesifik özelliklerine göre değişebilir.

Tamsayı kısıtları performansı nasıl etkiler?

Tamsayı kısıtları, çözüm uzayını ayrık hale getirir ve sürekli optimizasyon algoritmaları için ek bir zorluk teşkil eder. Basit yuvarlama gibi yöntemler, algoritmanın "düz" uygunluk yüzeylerinde arama yapmasına neden olabilir, bu da yakınsama hızını yavaşlatabilir veya suboptimal çözümlere yol açabilir. Daha karmaşık stratejiler genellikle daha iyi sonuçlar verir ancak uygulama karmaşıklığını artırır.

Bu yöntem hangi endüstrilerde kullanılabilir?

Bu yöntem, malzeme kesim endüstrisi (metal, ahşap, tekstil), ambalajlama ve lojistik, elektronik üretim (PCB tasarımı), optik ve anten tasarımı, kentsel planlama ve hatta sanat ve tasarım gibi birçok alanda kullanılabilir.