Meta-Sezgisel (Meta-heuristics) algoritmalar, büyük ölçekli optimizasyon problemlerinin çözümü için algoritma ve arama tekniklerine yol gösteren (üst akıl) yöntemlerdir.
Yerel arama için sezgisel algoritmaların avantajlarına sahip olduğu gibi; yerel optimum sonuçları atlatarak global optimum çözüme ulaşmak için de ilham aldığı konulardaki stratejileri kullanır.
İşte bu algoritmalar arasında en popüler olanlardan biri de Genetik Algoritma (GA)’dır.
Genetik Algoritma Nedir?
Peki nedir genetik algoritma?
Genetik algoritma (GA), biyolojik evrimi taklit eden doğal seleksiyon sürecine dayalı, hem kısıtlı hem de kısıtsız optimizasyon problemlerini çözmek için kullanılan esnek yapıda ve uyarlanabilir bir algoritmadır. Genetik Algoritma’nın çıkış noktası doğa ve evrimdir. Evrimden ilham alan yapısı gereği, motto’su: “En güçlü olanın hayatta kalması”
John Holland ve öğrencileri tarafından Michigan Üniversitesi’ndeki çalışmaları sırasında geliştirilmiştir. (1960’lar ve 1970’ler)
Genetik Algoritma Nasıl Çalışıyor?
Genetik algoritmayı oluşturmak ve kodlamak için aşağıdaki kavramları iyice anlamak gerekiyor.
Nüfus (Population)
Birey (Phenotype/Individual)
Kromozom (Chromozome/Genotype)
Seçim (Selection)
Ebeveyn (Parents)
Çiftleşme/Eşleşme (Mating)
Çaprazlama (Crossover)
Yavru/Çocuk (Offspring/Child)
Mutasyon (Mutation)
Elitizm (Elitism)
Uygunluk Fonksiyonu (Fitness function)
Nesil/Jenerasyon (Generation)
Genetik Algoritma, basit olarak bir başlangıç nüfusu ile başlar ve her bir nesilde nüfus içindeki bireylerin çaprazlanması ile yeni nesile yavrular (offspring) üretir. Zaman içinde çeşitli mutasyonlara da uğrayan nüfusta en güçlü (en iyi çözümler) bireyler bir sonraki nesile aktarılarak istenilen noktaya ulaşılır.
Gelin şimdi bu kavramları detaylı olarak inceleyelim:
Nüfus-Birey-Kromozom
Nüfus, genetik algoritmaya konu problemimiz için incelediğimiz çözüm kümesidir. Tüm arama çalışmalarımızı bu nüfus üzerinden ilerletiriz. Bireyler ise nüfusu oluşturan bileşenlerdir (çözümlerdir). Her bir birey, kendine has genetik materyalden yani kromozomlardan oluşur.
Örnek bir TSP-Traveling Salesman Problem (Gezgin Satıcı Problemi) problemi üzerinden konuşacak olursak; incelediğimiz tüm rotalar bizim nüfusumuzu ve her bir rota bireyleri göstermektedir. Bireyleri (rotaları) oluşturan genetik materyal ise kromozomları yani örneğimizde gezilecek şehir dizinlerini göstermektedir.
Genetik algoritmanın en güzel yanlarından bir tanesi; geniş çözüm kümesi uzayında tek bir noktaya bağlı kalmadan, bir çok nokta üzerinden çözüme ulaşmayı amaçlamasıdır. Bunu da oluşturduğumuz nüfus ile sağlıyoruz.
Seçim ve Ebeveynler
Genetik algoritma için nüfusumuzu geliştirmek ve daha iyi çözümlere ulaşmak için nüfusun çoğalması gerekiyor. Bunun için de ebeveynlere ihtiyacımız var.
Ebeveyn seçimi, daha kaliteli çözümlere ulaşmak için ilk adım olarak karşımıza çıkıyor. Literatürde birçok seçim algoritması mevcut; bunlardan hızlı ve pratik olanları:
Rastgele Seçim
Popülasyon içinden rastgele 2 birey belirlenir.
Eğer iki birey birbirinin aynısı ise 2. yeniden belirlenir.
Rulet Tekerleği Seçimi (Roulette Wheel Selection)
Popülasyon içinden rastgele n tane birey belirlenir.
Uygunluk fonksiyonları hesaplanır.
Aşağıdaki formüle uygun şekilde rulet tekerleğine yerleştirilir.
Olasılıklara göre rastgele bir seçim yapılır.
Ebeveynler belirlenene kadar tekrarlanır.
Turnuva Seçimi (Tournament Selection)
Popülasyon içinden rastgele n tane birey belirlenir
Belirlenen bu n birey içinden uygunluk fonksiyonuna göre en iyi aday belirlenir.
Ebeveynler belirlenene kadar tekrarlanır.
Çaprazlama ve Yavru Oluşturma (Crossover and Offsprings)
Çaprazlama, Genetik Algoritma’nın en önemli operasyonlarından biridir. Bu operasyon, oluşturulan yavrular ile nüfus içindeki genetik çeşitliliği arttırmak için çok önemlidir.
Çaprazlama için genetik materyalin yavrulara aktarılabilmesi için basit algoritmalar kullanılabileceği gibi literatürde belirtilen çok sofistike yöntemler de kullanılır.
Genetik algoritmada çaprazlama için kullanılan bazı yöntemler:
1-point crossover: Özellikle binary kromozom yapısındaki (1/0) çözümler için sıklıkla kullanılan basit yöntemlerden birisidir. Her bir ebeveynin kromozomlarında 1 nokta belirlenir ve bu noktalar referans alınarak genetik materyal değişimi gerçekleştirilir.
2-points/k-points crossover: Her bir ebeveyn kromozomunda en az iki nokta belirlenir ve belirlenen noktalar arasında kalan genetik materyal çaprazlama olarak yavrulara aktarılır.
Order crossover: Her bir ebeveyn kromozomunda en az iki nokta belirlenir ve belirlenen noktalar arasında kalan genetik materyal çaprazlama olarak yavrulara aktarılır. Bu noktalar dışında kalan genetik materyal ise karşılıklı ebeveynlerdeki “dizilim” dikkate alınarak yavrulara aktarılır.
Partial mapping crossover: Her bir ebeveyn kromozomunda en az iki nokta belirlenir ve belirlenen noktalar arasında kalan genetik materyal çaprazlama olarak yavrulara aktarılır. Yavrulara aktarılan bu kromozom parçaları karşılıklı olarak eşleşmiş (mapped) kabul edilir ve geriye kalan genetik materyal bu eşleşmeye (map) göre yavrulara aktarılır.
Cycle crossover: Belirlenen ebeveynlerdeki kromozomlar içinde karşılıklı olarak map’ler ve cycle’lar aranır. Ortaya çıkan cycle’lardan birisini kromozomlarda bırakarak diğer cycle’lar içindeki genler karşılıklı olarak değiştirilir ve yavrular oluşturulur.
Mutasyon
Genetik algoritmanın önemli operasyonlarından bir diğeri de mutasyondur. Mutasyon biyoloji temelli olarak, genetik materyalin değişime uğraması olarak düşünebiliriz. Çözüm kalitesi düşünüldüğünde bu değişim iyi yönde olabileceği gibi daha kötü çıktılar da üretebilir.
Genetik algoritmada mutasyon, yerel arama yaparak nüfusun çözüm kalitesini arttırmayı amaçlamaktadır. Yerel arama algoritmaları birçok heuristic ve meta-heuristic’in başvurduğu yöntemlerdir. Elde bulunan çözümün komşulukları taranarak daha iyi bir çözüm olup olmadığı araştırılmaktadır.
Literatürde çok sayıda yerel arama tekniği öne sürülmüştür. TSP gibi tek parçalı kromozom dizisine sahip problemler için düşünülen önde gelen yöntemleri derleyecek olursak:
Insertion: Bir genin bulunduğu noktadan alınarak başka bir noktaya taşınması.
Swap: Belirlenen iki genin yerlerinin değiştirilmesi.
Displacement: Bir kromozom parçasının (genin değil) yerinin değiştirilmesi.
2-opt: Belirlenen iki gen arasının ters çevrilerek yeniden konumlandırılması.
3-opt/k-opt: Belirlenen en az 3 gen arasındaki dizilerin yer değiştirilmesi ve/veya ters çevirilerek yeniden konumlandırılması.
Bunlar haricinde VRP-Vehicle Routing Problem gibi çok parçalı kromozom dizisine sahip problem tiplerinde bu yöntemler kromozom parçaları arasında ya da kromozom parçaları içinde şeklinde de uyarlanabilmektedir.
Nesil
Genetik algoritmada nesil yapısının ana amacı; her iterasyonda bir sonraki nesile daha kaliteli çözümler (kromozomlar) aktarabilmektir.
Nesiller; belirlenen popülasyon sayısında sabit kalabileceği gibi değişken de olabilir.
Nesil sayısı sonlandırma kriteri (termination criteria) olarak da kullanılır. Nesil sayısının artması; hesaplama süresini artırırken; az olması da yeterince çözüm uzayının incelenememesine ve optimum sonuca uzak kalmaya neden olacaktır.
Elitizm
Yeni bir nüfus/popülasyon oluşturma sürecinde; mevcut nesilden en iyi bireylerin herhangi bir değişime uğramadan (mutasyon olmadan) bir sonraki nesile aktarılması stratejisidir.
Genetik algoritmada elitizm stratejisi ile elde edilen çözüm kalitesinin bir nesilden diğerine düşmeyeceğini garanti edilir. Diğer bir taraftan yüksek bir oranda elitizm seçimi nesildeki genetik çeşitliliği azaltacaktır.
Uygunluk Fonksiyonu (Fitness Function)
Uygunluk fonksiyonu; popülasyondaki çözümleri kalitesini belirlemek için kullanılan fonksiyondur. Genel olarak; kombinatoryal problemlerde amaç fonksiyonun kendisi kullanılabilir. Genetik algoritmada uygunluk fonksiyonu; amacına uygun olarak (sıralama, seçme, karşılaştırma) amaç fonksiyonunun doğrudan kendisi kullanılabileceği gibi; 1/F olarak ya da farklı hesaplamalar ile de kullanılabilir.
Genetik Algoritma Sözde Kodu (Pseudocode)
Genetik algoritma sözde kod yapısı aşağıdaki gibidir:
N_pop: Nüfus büyüklüğü
N_gen: Nesil sayısı
p_c: Çaprazlama olasılığı
p_m: Mutasyon olasılığı
K: Turnuva seçimi büyüklüğü
E: Elitizm seçimi büyüklüğü
olmak üzere:
Akış Şeması
Genetik algoritmanın akışı kısaca şu şekilde:
Nüfusu oluştur
Ebeveyn seçimi yap ve çocukları oluştur.
Mutasyon yap
Nesli güncelle
Önceki nesilden en iyi çözümleri belirle ve yeni nesile ekle
Değerlendir
Son sözler…
Genetik algoritmayı genel olarak ve basit haliyle anlatmaya çalıştım.
Genetik algoritmayı tüm detayları ile anlattığım Python ile Genetik Algoritma eğitimime UDEMY üzerinden ulaşabilirsiniz. Bu eğitimde; genetik algoritma python ile adım adım nasıl kodlanır ve genetik algoritma örnek problemlerini (gezgin satıcı problemi, karesel atama problemi) bulabilirsiniz.
Bu konu ya da diğer konular ile ilgili sorularınız için iletişim sayfasındaki formu doldurabilir ya da Linkedin üzerinden iletişime geçebilirsiniz.
コメント