Genetik Algoritma

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 (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.

GA’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)

Kavramlar

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.

Nüfus-Birey-Kromozom

Ö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.

Global vs Local

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

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

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.

Rulet Tekerleği

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ılabilkmektedir.

Çaprazlama

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.

Çaprazlama Yöntemleri

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.

Mutasyon

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, gen dizisi) 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ı (rotalar) arasında ya da kromozom parçaları (rota) içinde şeklinde de uyarlanabilmektedir.

Nesil

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.

Bu strateji ile GA tarafından 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 azaltacak ve daha kaliteli çözümler bulmayı zorlaştıracaktır.

Uygunluk Fonksiyonu (Fitness Function)

Uygunluk fonksiyonu; popülasyondaki çözümlerin kalitesini belirlemek için kullanılan fonksiyondur.Genel olarak; kombinatoryal problemlerde amaç fonksiyonun kendisi kullanılabilir.

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.

Uygunluk Fonksiyonu Kullanımı

Sözde Kod (PSEUDOCODE)

Genetik algoritma için düşünülebilecek 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ış

Genetik algoritmanın akışı kısaca şu şekilde:

1. Nüfusu oluştur
2. Ebeveyn seçimi yap ve çocukları oluştur.
3. Mutasyon yap
4. Nesli güncelle
5. Önceki nesilden en iyi çözümleri belirle ve yeni nesile ekle
6. Değerlendir

Son sözler…

Genetik algoritmayı genel olarak ve basit haliyle anlatmaya çalıştım. Çok daha detaylı olarak anlattığım ve Python ile örnek problemleri kodladığım eğitimime indirimli olarak aşağıdaki link ile UDEMY üzerinden ulaşabilirsiniz.

Python ile Genetik Algoritma

Diğer tüm ilgi çekici yazılarıma ulaşabileceğiniz bağlantı ise:

HypiosBlog

Sevgiler…