Genetik Algoritmalar

dna Genetik Algoritmalar

Genetik algoritmalar, doğada gözlemlenen evrimsel sürece benzer bir
şekilde çalışan arama ve eniyileme yöntemidir. Karmaşık çok boyutlu
arama uzayında en iyinin hayatta kalması ilkesine göre bütünsel en iyi
çözümü arar.
Genetik algoritmaların temel ilkeleri ilk kez Michigan
Üniversitesi’nde John Holland tarafından ortaya atılmıştır. Holland 1975
yılında yaptığı çalışmaları ?Adaptation in Natural and Artificial
Systems? adlı kitabında bir araya getirmiştir. İlk olarak Holland evrim
yasalarını genetik algoritmalar içinde eniyileme problemleri için
kullanmıştır.
Genetik algoritmalar problemlere tek bir çözüm üretmek
yerine farklı çözümlerden oluşan bir çözüm kümesi üretir. Böylelikle,
arama uzayında aynı anda birçok nokta değerlendirilmekte ve sonuçta
bütünsel çözüme ulaşma olasılığı yükselmektedir. Çözüm kümesindeki
çözümler birbirinden tamamen bağımsızdır. Her biri çok boyutlu uzay
üzerinde bir vektördür.
Genetik algoritmalar problemlerin çözümü için
evrimsel süreci bilgisayar ortamında taklit ederler. Diğer eniyileme
yöntemlerinde olduğu gibi çözüm için tek bir yapının geliştirilmesi
yerine, böyle yapılardan meydana gelen bir küme oluştururlar. Problem
için olası pekçok çözümü temsil eden bu küme genetik algoritma
terminolojisinde nüfus adını alır. Nüfuslar vektör, kromozom veya birey
adı verilen sayı dizilerinden oluşur. Birey içindeki her bir elemana gen
adı verilir. Nüfustaki bireyler evrimsel süreç içinde genetik algoritma
işlemcileri tarafından belirlenirler.
Problemin bireyler içindeki
gösterimi problemden probleme değişiklik gösterir. Genetik
algoritmaların problemin çözümündeki başarısına karar vermedeki en
önemli faktör, problemin çözümünü temsil eden bireylerin gösterimidir.
Nüfus içindeki her bireyin problem için çözüm olup olmayacağına karar
veren bir uygunluk fonksiyonu vardır. Uygunluk fonksiyonundan dönen
değere göre yüksek değere sahip olan bireylere, nüfustaki diğer bireyler
ile çoğalmaları için fırsat verilir. Bu bireyler çaprazlama işlemi
sonunda çocuk adı verilen yeni bireyler üretirler. Çocuk kendisini
meydana getiren ebeveynlerin (anne, baba) özelliklerini taşır. Yeni
bireyler üretilirken düşük uygunluk değerine sahip bireyler daha az
seçileceğinden bu bireyler bir süre sonra nüfus dışında bırakılırlar.
Yeni nüfus, bir önceki nüfusta yer alan uygunluğu yüksek bireylerin bir
araya gelip çoğalmalarıyla oluşur. Aynı zamanda bu nüfus önceki nüfusun
uygunluğu yüksek bireylerinin sahip olduğu özelliklerin büyük bir
kısmını içerir. Böylelikle, pek çok nesil aracılığıyla iyi özellikler
nüfus içersinde yayılırlar ve genetik işlemler aracılığıyla da diğer iyi
özelliklerle birleşirler. Uygunluk değeri yüksek olan ne kadar çok
birey bir araya gelip, yeni bireyler oluşturursa arama uzayı içerisinde o
kadar iyi bir çalışma alanı elde edilir. Probleme ait en iyi çözümün
bulunabilmesi için;
Bireylerin gösterimi doğru bir şekilde yapılmalı,
Uygunluk fonksiyonu etkin bir şekilde oluşturulmalı,
Doğru genetik işlemciler seçilmeli.
Bu
durumda çözüm kümesi problem için bir noktada birleşecektir. Genetik
algoritmalar, diğer eniyileme yöntemleri kullanılırken büyük zorluklarla
karşılaşılan, oldukça büyük arama uzayına sahip problemlerin çözümünde
başarı göstermektedir. Bir problemin bütünsel en iyi çözümünü bulmak
için garanti vermezler. Ancak problemlere makul bir süre içinde, kabul
edilebilir, iyi çözümler bulurlar. Genetik algoritmaların asıl amacı,
hiçbir çözüm tekniği bulunmayan problemlere çözüm aramaktır. Kendilerine
has çözüm teknikleri olan özel problemlerin çözümü için mutlak sonucun
hızı ve kesinliği açısından genetik algoritmalar kullanılmazlar. Genetik
algoritmalar ancak;
Arama uzayının büyük ve karmaşık olduğu,
Mevcut bilgiyle sınırlı arama uzayında çözümün zor olduğu,
Problemin belirli bir matematiksel modelle ifade edilemediği,
Geleneksel eniyileme yöntemlerinden istenen sonucun alınmadığı alanlarda etkili ve kullanışlıdır.
Genetik
algoritmalar parametre ve sistem tanılama, kontrol sistemleri, robot
uygulamaları, görüntü ve ses tanıma, mühendislik tasarımları, planlama,
yapay zeka uygulamaları, uzman sistemler, fonksiyon ve kombinasyonel
eniyileme problemleri ağ tasarım problemleri, yol bulma problemleri,
sosyal ve ekonomik planlama problemleri için diğer eniyileme
yöntemlerinin yanında başarılı sonuçlar vermektedir.Diğer yöntemlerden farkı
Genetik
algoritmalar problemlerin çözümünü parametrelerin değerleriyle değil,
kodlarıyla arar. Parametreler kodlanabildiği sürece çözüm üretilebilir.
Bu sebeple genetik algoritmalar ne yaptığı konusunda bilgi içermez,
nasıl yaptığını bilir.
Genetik algoritmalar aramaya tek bir noktadan
değil, noktalar kümesinden başlar. Bu nedenle çoğunlukla yerel en iyi
çözümde sıkışıp kalmazlar.
Genetik algoritmalar türev yerine
uygunluk fonksiyonunun değerini kullanır. Bu değerin kullanılması ayrıca
yardımcı bir bilginin kullanılmasını gerektirmez.
Genetik algoritmalar gerekirci kuralları değil olasılıksal kuralları kullanır.
Kuramsal Temeller

Genetik Algoritmanın Tanımı
Genetik
algoritma, doğadaki evrim mekanizmasını örnek alan bir arama metodudur
ve bir veri grubundan özel bir veriyi bulmak için kullanılır. Genetik
algoritmalar 1970?lerin başında John Holland tarafından ortaya
atılmıştır. Genetik Algoritmalar, Evrimsel Genetik ve Darwin?in Doğal
seleksiyonuna benzerlik kurularak geliştirilmiş ?iteratif ?, ihtimali
bir arama metodudur.
Genetik algoritmalar doğada geçerli olan en
iyinin yaşaması kuralına dayanarak sürekli iyileşen çözümler üretir.
Bunun için ?iyi?nin ne olduğunu belirleyen bir uygunluk (fitness)
fonksiyonu ve yeni çözümler üretmek için yeniden kopyalamadeğiştirme
(mutation) gibi operatörleri kullanır. Genetik algoritmaların bir diğer
önemli özelliği de bir grup çözümle uğraşmasıdır. Bu sayede çok sayıda
çözümün içinden iyileri seçilip kötüleri elenebilir.
Genetik
algoritmaları diğer algoritmalardan ayıran en önemli özelliklerden biri
de seçmedir. Genetik algoritmalarda çözümün uygunluğu onun seçilme
şansını arttırır ancak bunu garanti etmez. Seçim de ilk grubun
oluşturulması gibi rasgeledir ancak bu rasgele seçimde seçilme
olasılıklarını çözümlerin uygunluğu belirler.
Genetik Algoritmaları (GA) diğer metodlardan ayıran noktalar şu şekilde sıralanabilir:
(recombination),
GA
, sadece bir arama noktası değil , bir grup arama noktası (adaylar )
üzerinde çalışır. Yani arama uzayında , yerel değil global arama yaparak
sonuca ulaşmaya çalışır. Bir tek yerden değil bir grup çözüm içinden
arama yapar.
GA , arama uzayında bireylerin uygunluk değerini bulmak
için sadece ?amaç – uygunluk fonksiyonu? (objective-fitness function )
ister. Böylelikle sonuca ulaşmak için türev ve diferansiyel işlemler
gibi başka bilgi ve kabul kullanmaya gerek duymaz.
Bireyleri seçme ve birleştirme aşamalarında deterministik kurallar değil ? olasılık kuralları? kullanır.
Diğer
metodlarda olduğu gibi doğrudan parametreler üzerinde çalışmaz. Genetik
Algoritmalar, optimize edilecek parametreleri kodlar ve parametreler
üzerinde değil, bu kodlar üzerinde işlem yapar. Parametrelerin
kodlarıyla uğraşır. Bu kodlamanın amacı, orjinal optimizasyon problemini
kombinezonsal bir probleme çevirmektir.
Genetik algoritma ne yaptığı konusunda bilgi içermez, nasıl yaptığını bilir. Bu nedenle kör bir arama metotudur.
Olasılık
kurallarına göre çalışırlar. Programın ne kadar iyi çalıştığı önceden
kesin olarak belirlenemez. Ama olasıklıkla hesaplanabilir.
GA, kombinezonsal bir atama mekanizmasıdır.
Genetik Algoritmalar, yeni bir nesil oluşturabilmek için 3 aşamadan geçer:

1. Eski nesildeki her bir bireyin uygunluk değerini hesaplama.
2. Bireyleri, uygunluk değerini göz önüne alarak (uygunluk fonksiyonu ) kullanılarak seçme.
3. Şeçilen bireyleri, çaprazlama (crossover), mutasyon (mutation) gibi genetik operatörler kullanarak uyuşturma.

Algoritmik bakış açısından bu aşamalar, mevcut çözümleri lokal olarak değiştirip birleştirmek olarak görülebilir.
Genetik
Algoritmalar; başlangıçta bilinmeyen bir arama uzayından topladığı
bilgileri yığıp, daha sonraki aramaları alt arama uzaylarına
yönlendirmek için kullanılır.

Kodlama Yöntemleri
Kodlama planı
Genetik algoritmanın önemli bir kısmını teşkil eder. Çünkü bu plan
bilginin çerçevesini şiddetle sınırlayabilir. Öyle ki probleme özgü
bilginin bir kromozomsal gösterimiyle temsili sağlanır. Kromozom
genellikle, problemdeki değişkenlerin belli bir düzende sıralanmasıdır.
Kromozomu oluşturmak için sıralanmış her bir değişkene ?gen? adı
verilir. Buna göre bir gen kendi başına anlamlı genetik bilgiyi taşıyan
en küçük genetik yapıdır. Mesela; 101 bit dizisi bir noktanın
x-koordinatının ikilik düzende kodlandığı gen olabilir. Aynı şekilde bir
kromozom ise Bir ya da daha fazla genin bir araya gelmesiyle oluşan ve
problemin çözümü için gerekli tüm bilgiyi üzerinde taşıyan genetik yapı
olarak tanımlanabilir. Örnek vermek gerekirse; 100011101111 x1, y1, x2,
y2 koordinatlarından oluşan iki noktanın konumu hakkında bize bilgi
verecektir.
Bu parametreleri kodlarken dikkat edilmesi gereken en
önemli noktalardan biri ise kodlamanın nasıl yapıldığıdır. Örnek olarak
kimi zaman bir parametrenin doğrusal ya da logaritmik kodlanması GA
performansında önemli farka yol açar.
Kodlamanın diğer önemli bir
hususu ise kodlama gösteriminin nasıl yapıldığıdır. Bu da yeterince açık
olmamakla birlikte GA performansını etkileyen bir noktadır. Bu konu
sonradan anlatılacaktır.

Uygunluk Teknikleri
Başlangıç
topluluğu bir kez oluşturulduktan sonra evrim başlar. Genetik algoritma
bireylerin uygunluk ve iyiliklerine göre ayrılıp fark edilmesine gerek
duyar. Uygunluk, topluluktaki bir kısım bireyin problemi nasıl çözeceği
için iyi bir ölçüdür. O problem parametrelerini kodlamayla ölçülür ve
uygunluk fonksiyonuna giriş olarak kullanılır. Yüksek ihtimalle uygun
olan bu üyeler tekrar üreme, çaprazlama ve mutasyon operatörleriyle
seçilirler.
Bazı problemler için bireyin uygunluğu, bireyden elde
edilen sonuç ile tahmin edilen sonuç arasındaki hatadan bulunabilir.
Daha iyi bireylerde bu hata sıfıra yakın olur. Bu hata genellikle,
girişin tekrar sunulacak kombinezonlarının ortalaması veya toplamıyla
hesaplanır (değerler değişkenlerden bağımsızdır). Beklenen ve üretilen
değer arasındaki korelasyon etkeni, uygunluk değerini hesaplamak için
kullanılabilir. (Koza 1994).
Objektif fonksiyonu (Değerlendirme
fonksiyonu) her bir kromozomun durumunu değerlendirmek için mekanizmayı
sağlayan ana bir kaynaktır. Bu GA ve sistem arasında önemli bir
bağlantıdır. Fonksiyon giriş olarak kodu çözülmüş şekilde kromozom
(Phenotype) alır ve kromozomun performansına bir ölçü olarak bir
objektif değer üretir. Bu diğer kromozomlar için de yapıldıktan sonra
yapıldıktan sonra bu değerler kullanılarak, uygun değerler uygunluk
fonksiyonuyla hesaplanıp belli bir düzende planlanır. Bu planlamayı
sağlayan ve uygunluk teknikleri olarak bilinen birçok yöntem vardır.
Çoğu ortak kullanılan bu yöntemler şunlardır:

1. Pencereleme
Populasyonda
en kötü kromozomun objektif değerinin Vw olduğunu kabul edersek her bir
kromozomun i ve en kötü kromozomu arasında farkla orantılı bir uygunluk
değeri fi atanabilir. Bu durum matematiksel olarak şu şekilde ifade
edilebilir:

Fi=c±/Vi-Vw

Burada Vi kromozom i ?nin
objektif değeri ve c ise uygunluğun negatif çıkmamasını sağlayacak kadar
büyük bir sayıdır. Eğer bir maksimizasyon problemiyle karşılaşılırsa
denklemde pozitif işaret kabul edilir. Diğer yandan minimizasyon
gerekliyse negatif işaret kabul edilir.

N
F=1/(1+å|Rpi-Rdi|)(2.2)
i=1

2. Lineer Normalizasyon
Objektif
fonksiyonun maksimize veya minimize durumuna göre kromozomlar objektif
değerin artma veya azalma düzenine göre sıralanır. En iyi kromozoma
rastgele en iyi bir uygunluk fbest atanarak sıralanmış düzende diğer
kromozomların uyguluğu lineer bir fonksiyonla bulunur:

Fi=fbest-(i-1).d

Burada
d eksilme oranıdır. Bu teknik populasyonun ortalama objektif değerini
ortalama uygunluk içerisinde ayrıntılarıyla planlamayı sağlar.
Bu iki teknikten başka kullanıcının kendisinin belirleyeceği başka yöntemler de mevcuttur.

Genetik Operatörler

Kullanılan genetik operatörler, varolan nesil
(population) üzerine uygulanan işlemlerdir. Bu işlemlerin amacı, daha
iyi özelliğe sahip yeni nesiller üretmek ve arama algoritmasının alanını
genişletmektir.
3 tip genetik operatör vardır:
Seleksiyon (Selection / Reproduction)
Çaprazlama (Crossover)
Mutasyon (Mutation)
1. Seleksiyon (Selection / Reproduction)
Yeniden
üretme operatörü, hazır topluluktan uygun olan bireylerin seçilmesi ve
bunların sonraki topluluğa kopyalanarak hayatta kalmalarıyla ilgilidir.
Seçim modeli, tabiatın hayatta kalabilmek için uygunluk mekanizması
modelidir. Yeniden üretme işleminde, bireyler onların uygunluk
fonksiyonlarına göre kopya edilirler. Uygunluk fonksiyonu, mümkün olduğu
kadar yükseltilmesi gereken bazı faydalı ve iyi ölçülerdir. Topluluk
uzayındaki her bir bireyin uygunlukları baz alınarak ne kadar sayıda
kopyasının olacağına karar verilir. En iyi bireylerden daha fazla kopya
alınır, en kötü bireylerden kopya alınmaz. Bu hayatta kalmak için
uygunluk stratejisinin GA ya sağladığı avantajdır.

1.1. Rulet Tekerleği Seçimi
GA
tarafından üretilen döllerin sayısını belirlemede birkaç yol vardır.
Birbirine yakın parametrelerden kaçınmak için uygun bir seçim metodu
kullanılmalıdır. Tekrar üretme başlangıcında basit bir yöntem ?roulette
wheel selection? (rulet tekerleğiyle seçim)’e göre bireylerin uygunluk
değerlerini bir rulet tekerleğinde hazırlar. Rasgele tekerleğin
döndürülmesinden sonra, bireyin bir sonraki nesil için seçilmesi,
tekerlek üzerinde kapladığı alanla doğrudan bağlantılıdır. Bu yöntem
düşük uygunluğa sahip bireylere de seçilme hakkı verir.

N
Pseçilen=Fi / å Fi (2.4)
i=1

Fi: i. Eleman için uygunluk değeri
N: Birey sayısı

Ebeveynler
uygunluklarına göre seçilirler. Kromozomlar ne kadar iyiyse, o kadar
seçilme şansları fazladır. Şöyle bir rulet tekerleği düşünün.

rulettekerlegi.PNG
Şekil 1. Rulet tekerleği ile seçim

Sonra
bir bilye atılır ve kromozomu seçer. Daha fazla uygunluğu olan
kromozomlar daha çok seçilecektir. Bu aşağıdaki algoritmayla simule
edilebilir:
1. [Sum] Populasyondaki tüm kromozom uygunlukları toplamını hesapla ? toplam S.
2. [Select] (0,S) ? r aralığından rastgele bir sayı üret.
3.
[Loop] Populasyon boyunca git ve uygunlukları 0?dan toplam s ?e kadar
topla. Eğer toplam s , r ?den büyükse dur ve olduğun yerdeki kromozomu
geri gönder.
Tabii ki 1. basamak her populasyon için bir kez performe edilir.

1.2 Rank Seçimi
Yukarıdaki
seçim eğer uygunluklar çok fazla değişiyorsa bazı problemlere yol
açacaktır. Mesela en iyi kromozom uygunluğu tüm rulet tekerleğinin %90?ı
ise diğer kromozomların seçilme şansları çok az olacaktır. Rank seçimi
önce populasyonu sıralar ve daha sonra her kromozom uygunluğu bu
sıralamadan sonra alır. En kötüsü 1 uygunluğunu alacak, ikinci en kötü 2
ve en iyisi N uygunluk değerini alacak ki N de populasyondaki kromozom
sayısıdır.
Sayıları düzenlemek için uygunlukları değiştirdikten sonra durumun nasıl değiştiğini aşağıdaki şekilde görebilirsiniz:

rulettekerlegi_1.PNG
Şekil 2. Rankingden önceki durum (Uygunluk grafiği) ve Rankingden sonraki durum (düzenli sayıların grafiği)

Bundan
sonra her kromozomun seçilme hakkı olacaktır. Fakat bu metod daha yavaş
gibidir, çünkü en iyi kromozomlar diğerlerinden fazla değişiklik
göstermez.

1.3 Steady-State Seçimi (Kararlı Hal)
Bu yerine
geçme yöntemleri olarak da adlandırılabilirler. Bu ebeveynleri seçmek
için kısmi bir metod değildir. Bu seçimin ana fikri kromozomların büyük
kısmı bir sonraki nesilde hayatta kalmak zorundadır.
O zaman GA şu
şekilde çalışır. Yeni çocuklar oluşturmak için her nesilde güzel iyi
uygunluklu birkaç kromozom seçilir. Sonra kötü düşük uygunluklu bazı
kromozomlar atılır ve yeni çocuk onun yerine yerleştirilir. Populasyonun
geri kalan kısmı yeni nesilde hayattadır. Yani kısaca bu yöntemde alt
populasyon oluşturulduktan sonra uygunluklar hesaplanır, en kötü
kromozomlar yerlerini başlangıç populasyonundaki en iyi kromozomlara
terk eder.

1.4 Elitizm
Bu da yerine geçme metodu olarak
bilinir. Elitizm fikriyle zaten daha önce tanışılmıştı. Mutasyon ve
çaprazlamalarla yeni nesil oluştururken en iyi kromozomu seçmek için
büyük bir şansa sahip oluruz.
Elitizm en iyi kromozomu ya da birkaç
en iyi kromozomları yeni nesile kopyalama metodunun adıdır. Gerisi
klasik yolla yapılır. Elitizm çok hızlı bir şekilde GA? nın
performansını arttırır çünkü en iyi bulunan çözümü kaybetmeyi önler.
Ayrıca Musbaka ve Oranlama yöntemleri de vardır.

2. Çaprazlama (Crossover)
Amaç,
ana (parent) kromozom genlerinin yerini değiştirerek çocuk (child)
kromozomlar üretmek ve böylece varolan uygunluk değeri yüksek olan
kromozomlardan, uygunluk değeri daha yüksek olan kromozomlar elde
etmektir. Burada önemli olan bir konuda , çaprazlama noktasının
çaprazlamadan elde edilecek çocuk kromozomların uygunluk değerleri
üzerindeki etkisidir. Bu işlem yapılırken her zaman sonuçlar önceden
tahmin edilemez. Bu yüzden gelişigüzel yapılan değişikliklerde sonucun
mükemmelliğe doğru gitmesi için belirli kriterler bulmak için çalışılır.
Kromozomlardaki genlerin yapısı ve etkileri araştırılarak, bu genlere
yapılan müdahalelerle bireye bazı iyi özellikler kazandırılabilir.
Çaprazlamadan elde edilecek çocuk kromozomların uygunluk değeri bir
önceki ana kromozomlardan daha yüksek olmayabilir.
Tablo 1.’de biyolojik çaprazlamaya bir örnek verilmiştir:

GA_tablo1.PNG
Tablo 1. Biyolojik çaprazlama örneği

Benzer
şekilde GA, çaprazlama işlemini uygunluk değerlerine göre seçilmiş iki
ebeveyn bireyden, iyi özellikte yeni bireyler elde etmek için kullanır.
Çaprazlama rasgele seçilmiş iki çift katarın içindeki alt küme
bilgilerin değiştirilmesi işlemdir. Kendi içindeki bilgilerini 1.
Pozisyondan itibaren, katarın uzunluğunun bir eksik pozisyonuna kadar,
aradaki bilgi kısmen karşılıklı bireyler arasında yer değiştirilir.
Eğer
iki bireyin problemin çözümünde bazı etkileri var ise onların bir
parçaları faydalı, iyi veya uygun nitelenebilecek bilgi taşımaktadır.
Çaprazlama belki problemin çözümünde, bu faydalı bilgileri
birleştirerek, daha çok etkili yeni bireyler üretecektir. Tablo 2.’de
ikili kodda verilmiş bir katarda, örnek 2 bitlik bir çaprazlama işlemi
verilmiştir.

GA_tablo2.PNG
Tablo 2. İki bitlik çaprazlama örneği

Çaprazlamadan
başka tersinme denilen bir üreme yöntemi daha vardır. Holland bunu
tanımlayarak kromozom uzunluğu çok olan bireylerde çaprazlama yerine
bunun kullanılmasını performans açısından önermiştir. Tersinme
(inversion) bir kromozomu oluşturan genlerden ardışık bir grubun kendi
içerisinde birbirleriyle yer değiştirerek ters dizilmeleridir.
Örneğin:011110101 kromozomu (her genin bir bit olduğu varsayımı ile) 5.
ve 8. Gen kromozomları arasında tersindiğinde ortaya 011101011 kromozomu
çıkar.
Tersinme genellikle kromozom uzunluğu fazla olan populasyonlara uygulanır.

3. Mutasyon (Mutation)
Amaç,
varolan bir kromozomun genlerinin bir ya da birkaçının yerlerini
değiştirerek yeni kromozom oluşturmaktır. Yeniden ve sürekli yeni nesil
üretimi sonucunda belirli bir süre sonra nesildeki kromozomlar
birbirlerini tekrarlama konumuna gelebilir ve bunun sonucunda farklı
kromozom üretimi durabilir veya çok azalabilir. İşte bu nedenle
nesildeki kromozomlarının çeşitliğini artırmak için kromozomlardan
bazıları mutasyona uğratılır. Açıklandığı gibi mutasyonun birinci
maksadı bir populasyonun içindeki değişimi tanımlamaktır. Mutasyon
populasyonlarda çok önemlidir. Öyle ki burada ilk populasyon mümkün olan
tüm alt çözümlerin küçük bir alt kümesi olabilir ve ilk populasyondaki
tüm kromozomların önemli biti sıfır olabilir. Halbuki o bitin problemin
çözümü için 1 olması gerekebilir ve bunu da çaprazlama düzeltemeyebilir.
Bu durumda o bit için mutasyon kaçınılmazdır. Genellikle önerilen
mutasyon oranı 0.005/bit/generasyondur. Bu işlem çaprazlamadan sonra
gelir. Mutasyonun yapılıp yapılmayacağını bir olasılık testi belirler.
Örneğin yeni neslin ortalama uygunluğu £ Eski neslin ortalama uygunluğu
ise; x. Kromozomun y. Bitini değiştir denilebilir. Bu yeni çocuğu rast
gele değiştirir. İkili kodlama için rast gele seçilmiş bitlerden 0?ları
1, 1?leri 0 yaparız.
Tablo 3. bit katarında hazırlanmış bir mutasyon operatörünü göstermektedir:

GA_tablo3.PNG
Tablo 3. Mutasyon operatörü
Genetik Algoritmaların Çalışma Prensibi

Genetik algoritmanın çalışmasını şöyle özetleyebiliriz:

GA_diyagram.PNG
Şekil 1. Genetik algoritmanın akış diyagramı

GA_adimlari.PNG
Tablo 1. Genetik algoritma adımları

İşlemleri adım adım açıklamak gerekirse:

Adım-1.
Bu
adıma toplumda bulunacak birey sayısını belirleyerek başlanmaktadır.
Kullanılacak sayı için bir standart yoktur. Genel olarak önerilen
100-300 aralığında bir büyüklüktür. Büyüklük seçiminde yapılan
işlemlerin karmaşıklığı ve aramanın derinliği önemlidir. Toplum bu
işlemden sonra rasgele oluşturulur.Kromozomun temsil ettiği çözüm
hakkında bilgiyi herhangi bir yollla içermesi gerekir. En çok kullanılan
kodlama ikili stringtir.

2li_kodlama.PNG
Tablo 2. İkili kodlama

Her
kromozom bir ikili stringe sahiptir. Bu stringteki her bit çözümün
belli karakteristiğini temsil eder, veya tüm string bir sayıyı temsil
eder. Tabiki bir çok kodlama yolu vardır. Bu daha çok çözülen probleme
bağlıdır. Mesela tam sayı veya reel sayı olarak kodlanabilir, bazen de
bazı permutasyonları kodlamak kullanışlı olabilir.

1. Permutasyon kodlama
Düzenleme
problemlerinde kullanılır. Satıcı gezici problemi veya Task Ordering
Probleminde. Burada her kromozom sayıları bir sırada temsil eden bir
sayılar stringidir.
P_kodlama.PNG
Tablo 3. Permutasyon kodlamalı kromozom örnekleri

Permutasyon kodlama sadece ordering problemleri için kullanışlıdır.

2. Değer kodlama
Reel
sayılar gibi komplike değerlerin kullanıldığı problemlerde direk değer
kodlanması kullanılabilir. Bu tip problemler için ikili kodlama işi çok
zordur.

D_kodlama.PNG
Tablo 4. Değer kodlamalı kromozom örnekleri

Bu
bazı özel problemler için çok iyidir. Diğer taraftan bu tip kodlama
için probleme özel yeni bazı mutasyon ve çaprazlamalar geliştirmek
lazımdır.

3. Ağaç kodlama
Bu, gelişen değişen programlar veya
ifadeler için kullanılır (Genetik programlama). Ağaç kodlamada her her
kromozom bazı nesnelerin, mesela fonksiyonlar ya da programlama
dilindeki komutlar gibi, bir ağacıdır şeklinde verilebilir.

A_kodlama.PNG
Şekil 2. Ağaç kodlamalı kromozomlar örneği

LISP programlama dili bunu çok kullanır

Adım-2.
Kromozomların
ne kadar iyi olduğunu bulan fonksiyona uygunlukfonksiyonu denir. Bu
fonksiyon işletilerek kromozomların uygunluklarının bulunmasına ise
hesaplama (evaluation) adı verilir. Bu fonksiyon genetik algoritmanın
beynini oluşturmaktadır. Genetik algoritmada probleme özel çalışan tek
kısım bu fonksiyondur. Uygunluk fonksiyonu kromozomları problemin
parametreleri haline getirerek onların bir bakıma şifresini çözmektedir
(decoding), sonra bu parametrelere göre hesaplamayı yaparak
kromozomların uygunluğunu bulur. Çoğu zaman genetik algoritmanın
başarısı bu fonksiyonun verimli ve hassas olmasına bağlı olmaktadır.

Adım-3.
Kromozomların
eşlenmesi kromozomların uygunluk değerlerine göre yapılır. Bu seçimi
yapmak için rulet tekerleği seçimi (roulette wheel selection) , turnuva
seçimi (Tournament Selection) gibi seçme yöntemleri vardır. Örnek olarak
bu çalışmada kullanılan rulet tekerleği seçimi aşağıda açıklanmıştır:

1- Tüm bireylerin uygunluk değerleri bir tabloya yazılır.
2- Bu değerler toplanır.
3-
Tüm bireylerin uygunluk değerleri toplama bölünerek [0,1] aralığında
sayılar elde edilir. Bu sayılar bireylerin seçilme olasılıklarıdır.
Sayıların hepsi bir tabloda tutulur.
4- Seçilme olasılıklarını
tuttuğumuz tablodaki sayılar birbirine eklenerek rasgele bir sayıya
kadar ilerlenir. Bu sayıya ulaşıldığında yada geçildiğinde son eklenen
sayının ait olduğu çözüm seçilmiş olur.

Bu yönteme rulet
tekerleği seçimi ismi, bir daireyi, çözümlerin uygunluklarına göre
dilimleyip çevirdiğimizde olacakların benzeşimi olduğu için verilmiştir.
Rulet
tekerleği seçimi çözümlerin uygunluk değerlerinin negatif olmamasını
gerektirir. Çünkü olasılıklar negatif olursa bu çözümlerin seçilme şansı
yoktur. Çoğunluğunun uygunluk değeri negatif olan bir toplumda yeni
nesiller belli noktalara takılıp kalabilir.

İkili kodlamada çaprazlama
Gen
takası (crossover) genetik algoritmanın motoru kabul edilir. Basitçe
olay iki ebeveyn kromozomun arasında belirlenen parçaların takasıdır.
Tek noktalı
tek_noktali.PNG
Şekil 3. İkili kodlamada tek noktalı çaprazlama

İki noktalı

2_noktali.PNG
Şekil 4. İkili kodlamada iki noktalı çaprazlama

Düzenli

duzenli.PNG
Şekil 5. İkili kodlamada düzenli çaprazlama

Aritmetik
aritmetik.PNG
Şekil 6. İkili kodlamada aritmetik çaprazlama

İkili kodlamada mutasyon

2li_kodlama_M.PNG
Şekil 7. İkili kodlamada mutasyon

Permutasyon kodlamada çaprazlama
Tek
noktalı çaprazlamada bir nokta seçilir ilk ebeveynden bu permutasyonun
kopyalandığı noktaya kadar,sonra ikinci ebeveyn okunur ve sayı çocukta
hala yoksa o eklenir.

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) => (1 2 3 4 5 6 8 9 7)

Permutasyon kodlamada mutasyon

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Değer kodlamada çaprazlama
İkili kodlamadaki tüm çaprazlamalar kullanılabilir.

Değer kodlamada mutasyon
Reel değer kodlama için seçilen değere küçük bir sayı eklenir ya da çıkarılır.

(1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)

Ağaç kodlamada çaprazlama

A_kodlama_C.PNG
Şekil 8. Ağaç kodlamada çaprazlama

Seçilen
düğümler değiştirilir. Operatorlar sayılar değiştirilir. Gen takası
toplumda çeşitliliği sağlar. İyi özelliklerin bir araya gelmesini
kolaylaştırarak en iyiye yaklaşmayı sağlar. Değiştirme kromozomun bir
parçasının dışarıdan değiştirilmesi şeklinde tanımlanır. Değiştirme
görünüşte genetik algoritmanın dayanak noktasıdır, ancak etkisi bir
çözüm üzerindedir. Bu da yalnız başına başarılı olmasını zorlaştırır.
İkilik dizilerde değiştirme rasgele bir bit?in değiştirilmesiyle
sağlanabilir. Çok düşük bir değiştirme olasılığı toplumda bazı
özelliklerin kaybolmasına neden olabilir. Bu da en iyi sonuçların
bulunmasına engeldir. Ancak yüksek bir değiştirme olasılığı da eldeki
çözümleri bozarak sonuca ulaşmayı zorlaştırır. Gen takası ve
değiştirmenin olasılıkları için kesin bir sayı yoktur. Değiştirme
(mutasyon) olasılığı 0.01-0.001, gen takası (cross-over) olasılığı
0.5-1.0 aralığında tavsiye edilir.

Adım-4.
Eski kromozomlar çıkartılarak sabit büyüklükte bir toplum sağlanır.

Adım-5.
Tüm kromozomlar yeniden hesaplanarak yeni toplumunun başarısı bulunur.

Adım-6.
Genetik algoritma defalarca çalıştırılarak çok sayıda toplum oluşturulup hesaplanır.

Adım-7.
Toplumların
hesaplanması sırasında en iyi bireyler saklandığı için o ana kadar
bulunmuş en iyi çözüm çözümdür. Genetik algoritmanın yaptığı işleri
temelini akış diyagramı olarak Şekil 9’de görebiliriz:

GA_temel.PNG
Şekil 9. Genetik algoritmanın temeli

Basit bir genetik algoritma, L uzunluğundaki homojen bir çubuğun momentinin 0 (sıfır) olduğu noktayı bulmak için kurabiliriz.

L_Moment.PNG
Şekil 10. L uzunluklu çubuğun momenti

L
uzunluğuna bağlı olarak ara uzunluk x1 ve x2 0 ile 255 cm arasında
işaretsiz bir tamsayı alınacaktır. F(x)=x1.m1-x2.m2 minimum değeri, aynı
zamanda uygunluk fonksiyonudur. Dolayısıyla özgül kütleleri aynı
olduğundan, doğrudan uzunluklara bağlı olacaktır. Yani uygunluk
fonksiyonunu daha basit bir şekilde F(x)=x1-x2=0 olarak verebiliriz.
Burada x2=L-x1 olduğundan F(x1)=2.x1-L=0 alınabilir. Örnek basit
seçildiğinden sonucun matematik bilgisine göre 127.5 cm olacağı açıkça
görülmektedir. 0 ile 255 arasındaki sayıları gösterebilmek için 8 bit
uzunluğunda bir bilgiye ihtiyacımız vardır.

0……………. 00000000
255………… 11111111

İlk
olarak başlangıç topluluğu bu sayılar arasından rasgele olarak
seçilebilir. Bunun için 8 birey oluşturulsun (N=8). Bunlar {0, 40, 80,
120, 160, 200, 220, 255} alınırsa:

0……………. 00000000
40………….. 00101000
80………….. 01010000
120………… 01111000
160………… 10100000
200………… 11001000
220………… 11011100
255………….11111111

Değerleri
başlangıç topluluğu olarak belirlenir. Bireylerin uygunluk değerleri,
sayının ondalık karşılığının uygunluk fonksiyonuna verdiği cevapla
bulunabilir. Uygunluk değeri sayının alabileceği değerler ile orantılı
olursa, bunun için max uygunluk değeri olarak 255 ve minimum olarak ta 0
uygunluk değeri alınmalıdır. Eğer elde edilen uygunluk değeri 255 ten
çıkarılırsa max uygunluğa 255 sayısının karşılık düştüğü görülebilir.
Örnek:

x=00000000 için F(x)=255-ABS(255?0)=0
x=00101000 için F(x)=255-ABS(255?80)=80 şeklinde belirlenebilir.

GA_manuel.PNG
Tablo 5. GA’ nın el ile uygulaması I

Bireylerin
uygunluk değerlerinin rulete yansımasından kaç adet kopya
oluşturulacağı veya hiç kopya alınmayacağı belirlenir. Yukarıdaki
tabloya göre 80,120 ve 160 sayılarından 2 şer kopya alınacaktır. 0 ve
255 sayılarından hiç kopya alınmayacak ve diğer sayılardan 1 er kopya
alınacaktır. Buna göre çaprazlama operatörü yardımıyla yeni bireyler
üretmeden önce başlangıç topluluğu tekrar oluşturulmalıdır.

GA_manuel_II.PNG
Tablo 6. GA’ nın el ile uygulaması II

Yukarıdaki
işlemlerde, bir nesilden diğer nesle kromozomlar aktarılırken, uygun
kromozomların iyi özellikleri tekrar üreme adımında kullanılarak en iyi
kromozomlar elde edilebilir. Elle yapılabilecek bu örnekte üç nesil
sonra çözüm olabilecek bireylerin çözüm uzayını yeterince daraltarak
birbirlerine daha çok benzeyecekleri görülecektir.

722e01df 1d42 45f0 9450 b550e9666ca4 444x333 Genetik Algoritmalar

    Makale Yazarı: duslerkulup2

Sizde yorum yazabilirsiniz...

Kameralı Sohbet