:::: MENU ::::
Optimizasyon problemleri

Genetik Algoritma Nedir? Genetik Algoritma Nasıl Çalışır?

Genetik Algoritma, evrimsel hesaplama algoritmalarının ilki ve en bilinenidir. Charles Darwin’in “En güçlü ve en akıllı bireyler değil, değişime en iyi adapte olan bireyler yaşam mücadelesini sürdürür” mealindeki bir sözü üzerine bina edildiği belirtilen Genetik Algoritma, optimizasyon problemlerini çözmeyi amaçlamaktadır.

En iyi adapte olan bireyler kısmını daha iyi anlatabilmek için şu şekilde bir örnek verilebilir. Örneğin bir ülkedeki nüfusun kalitesini kontrol altına almak istiyorsunuz. Bunu insanları iyi insanlar ve kötü insanlar olarak ayırıp, sonra kötü insanları yok edip, daha sonra iyi insanların iyi insanlarla çiftleşmeleri sonucunda iyi çocuk bireylerle toplumun kalitesini artırmayı teorik olarak hedefleyebilirsiniz lakin her zaman iyi anne babalardan iyi çocuklar doğmayabilir. Ayrıca kötü bireyleri yok etmekte epey vahşice bir yaklaşım oldu 🙂

Canlının en küçük yapı taşı hücredir. Genetik Algoritma hücre yapısını taklit ederek bilgileri saklar.

Bilgiler temel GA’da ikili(binary) formda tutulmaktadır. Sonraki süreçte sürekli ve ayrık değerler ile çalışan GA’larda önerilmiştir.

En temel anlamda bir GA aşağıdaki akış şemasına uygun çalışır:

Yukarıdaki adımları Knapsack (Sırt Çantası) Problemi üzerinde ayrıntılı olarak anlatıp, izah etmeye çalışalım.

Örneğin maksimum 30 kg alan çantanıza alacağınız eşyalarla doğada yaşamaya çalışacaksınız ve bunun için Survival Points kısmını maksimum yapmaya çalışacaksınız. Hangi ürünleri yanınıza alacaksınız?

Mesela Glucose + Sleeping Bag=35 kg olduğundan ikisi birlikte alınamamaktadır. Bu iki eşya puanı en yüksek olanlar olduğu için direk onları seçtim ama ağırlık kısıtına takıldım, o yüzden başka ürünler seçmeliyim.

Şimdi bu problemi Genetik Algoritma ile çözülecek hale getirelim.
6 farklı ürün olduğundan maksimum 6 ürün alabiliriz, minimum 0 ürün alabiliriz. Bir ürünün alınıp, alınmayacağını ise 0 ve 1 sayıları ile belirtebiliriz. Başlangıçta kendi belirleyeceğimiz kadar birey ile popülasyonu oluşturuyoruz:

Burada A1,A2,A3,A4 bireylerimizdir. Hepsi 6 boyutludur.

Şimdi sırada amaç fonksiyonu yazmada. Amacımız en çok Survival Points değerine ulaşmak, dolayısıyla seçtiğimiz ürünlerin değerlerini toplamamız gerekiyor lakin maksimum çanta ebatımız 30 kg, bunu göz önünde bulundurmalıyız.

A1 kromozomu için [100110] hesaplayalım:

A2 kromozomu için [001110] hesaplayalım:

Burada A1’in A2’ye göre daha fit olduğu görülmektedir.

Yeni bireyleri oluşturmak için bu fit bireyler kullanılır. Seçim işlemi için farklı yöntemler kullanılsa da biz burada Rulet Tekerleği Seçim Yöntemi ile aşağıdaki şekilde seçim yapılır:

Böylece her zaman en fit bireyler değil rastgeleliğe bağlı olarak daha düşük fitlikteki bireylerde seçilebilir.

İki atay birey seçildikten sonra çaprazlama (crossover) işlemi aşağıdaki şekilde yapılır. Literatürde bu işleme tek noktalı çaprazlama ismi verilmiştir.

Çok noktalı çaprazlama yapmak istersek:

Bu işlemin sonucunda iki ata bireyden iki yavru birey oluşturulmuş olur.

Bireyler atalarından özellik almakla beraber çevresel faktörlerde onların gelişimini etkilemektedir. Bu işleme de mutasyon adı verilir.

Mutasyon en basit haliyle bir boyuttaki bilginin terslenmesiyle yapılabilir.

Böylece yeni bireyler oluşmuş olur, bu bireylerin amaç fonksiyonu değeri hesaplandıktan sonra belirlenmiş olan sonlanma kriterine kadar süreç devam eder.

Sonlandırma kriteri ne olabilir?
-Başta belirlenmiş sabit jenerasyon sayısı kadar gelişim yapılır ve durdurulur.
-Başta belirlenmiş bir sayı kadar jenerasyonda amaç fonksiyonu gelişi olmazsa durdurulur.
-Amaç fonksiyon değeri belirlenmiş bir değere ulaştıysa durdurulur.

Kaynaklar:

Introduction to Genetic Algorithm & their application in data science


https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_fundamentals.htm
https://www.neuraldesigner.com/blog/genetic_algorithms_for_feature_selection


Optimizasyon Algoritmaları Nelerdir?

Optimizasyon problemlerini çözmek için sezgisel optimizasyon algoritmaları ve klasik çözüm yöntemleri mevcuttur. Ancak son yıllarda özellikle doğal süreçlerden esinlenilmiş birçok optimizasyon algoritması geliştirilmiştir.

Genetik Algoritma(Genetic Algorithm)(GA)
Karınca Kolonisi Optimizasyonu(Ant Colony Optimization)(ACO)
Parçacık Sürü Optimizasyonu(Particle Swarm Optimization)(PSO)
Yapay Arı Kolonisi(Artificial Bee Colony)(ABC)
Diferansiyel Gelişim Algoritması(Differential Evolution Algorithm) (DEA)
Benzetim Tavlama( Simulated Annealing)(SA)
Yerçekimi Arama Algoritması(Gravity Search Algorithm)(GSA)
Gaz Brownian Hareketi Optimizasyonu( Gases Brownian Motion Optimization) (GBMO)
Isı Transferi Arama (Heat transfer search)(HTS)
Elektromanyetik Alan Optimizasyonu (Electromagnetic Field Optimization) (EFO)
Optikten Esinlenen Optimizasyon (Optic Inspired Optimization)(OIO)
Ağırlıklı Süperpozisyon Çekimi (Weighted Superposition Attraction (WSA)
Orman Optimizasyonu Algoritması(Forest Optimization Algorithm)(FOA)
Kasırga Temelli Optimizasyon Algoritması(Hurricane Based Optimization Algorithm)
Kara Delik Optimizasyon Algoritması
Su Döngüsü Optimizasyon Algoritması
Karınca Sistemi
Max-Min Ant System
Karınca Kolonisi Optimizasyonu
Meyve Sineği Optimizasyon Algoritması
Levy Uçuşuna dayalı Guguk kuşu optimizasyonu
Krill Sürü Optimizasyon Algoritması
BakTeri Yiyecek Arama Davranışı
Yarasa Algoritması
Ateş Böceği Algoritması
Aslan Algoritması
Gri Kurt Algoritması
Yunus Balığı Algoritması
Çalı Kolonisi Algoritması
Yapay Alg Algoritması
Virüs Koloni Arama Algoritması
Köpekbalığı Koku Alma Optimizasyon Algoritması
Sosyal Örümcek Algoritması
Ağaç-Tohum Algoritması(Tree-Seed Algorithm)(TSA)