cıwann

1.1. GENETİK ALGORİTMANIN TARİHÇESİ
Michigan Üniversitesinde psikoloji ve bilgisayar bilimi uzmanı olan John Holland bu konuda ilk çalışmaları yapan kişidir. Mekanik öğrenme ( machine learning ) konusunda çalışan Holland, Darwin’in evrim kuramında etkilenerek canlılarda yaşanan genetik süreci bilgisayar ortamında gerçekleştirmeyi düşündü. Tek bir mekanik yapının öğrenme yeteneğini geliştirmek yerine böyle yapılarda oluşan bir topluluğun çoğalma, çiftleşme, mutasyon, vb. genetik süreçlerden geçerek başarılı ( öğrenebilen) yeni bireyler oluşturabildiğini gördü. Çalışmalarının sonucunu açıkladığını kitabının 1975’te yayınlanmasından sonra geliştirdiği yöntemin adı Genetik Algoritmalar ( ya da kısaca GA ) olarak yerleşti. Ancak 1985 yılında Holland’ın öğrencisi olarak doktorasını veren David E. Goldberg adlı inşaat mühendisi 1989 da konusunda bir klasik sayılan kitabını yayınlayana dek genetik algoritmaların pek pratik yararı olmayan bir araştırma konusu olduğu düşünülüyordu. Halbuki Goldberg’in gaz boru hatlarının denetimi üzerine yaptığı doktora tezi ona sadece 1985 National Science Foundation Genç Araştırmacı ödülünü kazandırmakla kalmadı, genetik algoritmaların pratik kullanımının da olabilirliğini kanıtladı. Ayrıca kitabında genetik algoritmalara dayalı tam 83 uygulamaya yer vererek GA’nın dünyanın her yerinde çeşitli konularda kullanılmakta olduğunu gösterdi.
1.2. KURAMSAL TEMELLER
1.2.1. 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 kopyalama (recombination), değ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 :
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 :
Eski nesildeki her bir bireyin uygunluk değerini hesaplama.
Bireyleri , uygunluk değerini göz önüne alarak (uygunluk fonksiyonu ) kullanılarak seçme.
Ş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 local 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 genelikle, 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
Objektif fonksiyonu(Değerlendirme fonksiyonu) her bir kromozomun durumunu değerlendirmek için mekanızmayı 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 züdende planlanır. Bu planlamayı sağlayan ve uygunluk teknikleri olarak bilinen birçok yöntem vardır. Çoğu ortak kullanılan by yöntemler aşağıda verilmiştir.
Pencereleme
Populasyonda en ktü 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.
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 :
Kulanılan genetil operatörler , varolan nesil (population) üzerine uygulanan işlemlerdir . Bu işlamlerin 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 ) :
*RULET TEKERLEĞİ SEÇİMİ
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.
Sonra bir bilye atılır ve kromozomu seçer.Daha fazla uygunluğu olan kromozomalr daha çok seçilecektir.Bu aşağıdaki algoritmayla simule edilebilir.
[Sum] Populasyondaki tüm kromozom uygunlukları toplamını hesapla - toplam S.
[Select] (0,S) – r aralığından rastgele bir sayı üret.
[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 dönder.
Tabii ki 1. basamak her populasyon için bir kez performe edilir.
*RANK SEÇİMİ
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 resimde görebilirsiniz.
Rankingden önceki durum(Uygunluk grafiği)
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.
*STEADY-STATE SEÇİMİ(KARARLı HAL)
Bunlar 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 terkeder.
*ELİTİZM
bu da yerine geçme metodu olarak bilinir. Elitizm fikriyle zaten daha önce tanışılmıştı.Mutasyon ve krossing-over’la 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.
Ç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. Çarprazlamadan elde edilecek çocuk kromozomların uygunluk değeri bir önceki ana kromozomlardan daha yüksek olmayabilir.
Üretim : Parents Child ( offspring) .
Örnek :
parents : A = 101010 B = 010100
çaprazlama noktası rastgele seçilir : 4
Çaprazlama sonucunda elde edilen yeni çocuk kromozomlar :
a = 101000 b = 010110
şeklinde olacaktır.
Çarprazlamadan başka tersinme denilen bir üreme yöntemi daha vardır. Hollan bunu tanımlayarak kromozom uzunluğu çok olan bireylerde çarprazlama 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 yerdeğ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.
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 çarprazlama düzeltemeyebilir.Bu durumda o bit için mutasyon kaçınılmazdır. Genelikle önerilen mutasyon oranı 0.005/bit/generasyondur.Bu işlem crossing-overdan sonra gelir.Mutasyonun yapılıp yapılmayacağını bir olasılık testi belirler.Örneğin Yeni neslin oratalama uygunluğu
Eski neslin ortalama uygunluğu ise; x. Kromozomun y. Bitini değiştir denilebilir. Bu yeni çocuğu rastgele değiştirir. İkili encodelama için rastgele seçilmiş bitlerden 0’ları 1, 1’leri 0 yaparız.
Orjinal çocuk 1 1101111000011110
Orjinal çocuk 2 1101100100110110
Mutasyonlu çocuk 1 1100111000011110
Mutasyonlu çocuk 2 1101101100110100
1.2.2. Genetik Algoritmaların Çalışma Prensibi
Genetik algoritmanın çalışmasını aşağıdaki gibi özetleyebiliriz;
Adım 1
Olası çözümlerin kodlandığı bir çözüm grubu oluşturulur (çözüm grubu, biyolojideki benzerliği nedeniyle, toplum (population), çözümlerin kodları (string) da kromozom olarak adlandırılır).
Adım 2
Her kromozomun ne kadar iyi olduğu bulunur (fitness function).
Adım 3
Bu kromozomlar eşlenerek (mating), yeniden kopyalama (recombination) ve değiştirme (crossover) operatörleri uygulanır. Bu sayede yeni bir toplum oluşturulur.
Adım 4
Yeni kromozomlara yer açmak için eski kromozomlar ortadan kaldırılır.
Adım 5
Tüm kromozomların uygunlukları tekrar hesaplanır.
Adım 6
Eğer jenerasyon süresi dolmamışsa 3. adıma gidilir.
Adım 7
O ana kadar bulunmuş en iyi kromozom sonuçtur.
İş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 encodelama ikili stringtir.
İkili encodelama
Kromozom 1 1101100100110110
Kromozom 2 1101111000011110
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 encodelama yolu vardır. Bu daha çok çözülen probleme bağlıdır. Mesela tam sayı veya reel sayı olarak encodelanabilir, bazen de bazı permutasyonları encodelamak kullanışlı olabilir.
Permutasyon encodelama
Düzenleme problermlerinde kullanılır.Satıcı gezici problemi veya Task Ordering Problem da. Burada her kromozom sayıları bir sırada temsil eden bir sayılar stringidir.
Kromozom A 1 5 3 2 6 4 7 9 8
Kromozom B 8 5 6 7 2 3 1 4 9
Permutasyon encodelamalı kromozom örnekleri
Permutasyon encodelama sadece ordering problemleri için kullanışlıdır.
Değer encodelama
Reel sayılar gibi komplike değerlerin kullanıldığı problemlerde direk değer encodelanması kullanılabilir.Bu tip problemler için ikili encodelama işi çok zordur.
Chromosome A1.2324 5.3243 0.4556 2.3293 2.4545
Chromosome B ABDJEIFJDHDIERJFDLDFLFEGT
Chromosome C (back), (back), (right), (forward), (left)
Değer encodelamalı kromozom örnekleri
Bu bazı özel problemler için çok iyidir.Diğer taraftan bu tip encodelama için probleme özel yeni bazı mutasyon ve krossing-overler geliştirmek lazımdır.
Ağaç encodelama
Bu, gelişen değişen programlar veya ifadeler için kullanılır.(Genetik programlama)Ağaç encodelamada her her kromozom bazı nesnelerin, mesela fonksiyonlar ya da programlama dilindeki komutlar gibi, bir ağacıdır
Kromozom A Kromozom B
( + x ( / 5 y ) ) ( do_until step wall )
Ağaç encodelamalı kromozomlar örneği
LISP programlama dili bunu çok kullanır
Adım-2. Kromozomların ne kadar iyi olduğunu bulan fonksiyona uygunluk fonksiyonu 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. şeklinde verilebilir.
Binary encodingde krossing-over
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ı:
11001011+11011111 = 11001111
İki noktalı:
11001011 + 11011111 = 11011111
Düzenli:
11001011 + 11011101 = 11011111
Aritmetik:
11001011 + 11011111 = 11001001 (AND)
Binary encodingde mutasyon:
11001001 => 10001001
Permutasyon encodingde krossing-over
Tek noktalı krossing overda bir nokta seçilir ilk ebeveynden bu permutayonun 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 encodingde mutasyon
(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)
Değer encodelamada krossing-over
İkili encodelamadaki tüm krossoverlar kulanılabilir.
Değer encodelamada mutasyon
Reel değer encodelama 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ç encodelamada krosing-over
Ağaç encodelamada mutasyon
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-2 de görebiliriz.
ŞEKİL- 2.Genetik Algoritmanın Temeli
1.2.3. Genetik Algoritmaların Kullanılma Nedenleri
Öncelikle niye diğer yöntemlerin kullanılmadığı belirtilmelidir. Denklem en iyilemesinde (optimization) ;
1. Türev-İntegral hesabına (calculus) dayananlar,
2. Numaralamaya (enumeration) dayananlar,
3. Rastgele aramalar (random searches) olmak üzere üç tip çözümden bahsedilir. Genetik algoritmaların yeri Şekil-4 de görülebilir.
Türev-İntegral hesaplamalarına dayanan hesaplama yöntemleri çok derinlemesine çalışılmıştır. Bu yöntemler fonksiyonun türevinin köklerinin fonksiyonun en küçük ve en büyük değer veren noktaları olmasından yararlanır. Gerçek problemler için sıfır veren noktaları bulmak da ayrı bir problemdir.
Diğer bir yöntem ise alınan bir noktadan sadece yukarı ilerleyerek en iyi sonucu bulmayı hedefler. Tepe tırmanma (hill climbing) denen bu yöntem fonksiyon grafiğinin tepelerini tırmanır. Ancak çok sayıda dönme noktası içeren bir fonksiyonda çok sayıda tepe oluşur. Hangi tepenin en iyi çözüm olduğunu bilenemez. Numaralama yöntemleri ise oldukça alışılagelmiştir. Sürekli olan gerçel sayı aralıkları belli sayıda parçaya ayrılarak parçalar denenir. Ancak problemler böyle çözmek için büyük olabilir. Bu yöntemin biraz daha geliştirilmiş şekli Dinamik Programlamayla (dynamic programming) oluşturulur. Parçalar arasından iyi görünenler seçilir. Bu parçalar parçalara ayrılarak işlem tekrarlanır. Bu yöntem de tepe tırmanma yöntemi gibi yanlış tepeleri araştırabilir. Dinamik Programlama tepelerin olmadığı aralıklarda başarılı ve hızlıdır.
En iyilemenin
bir işin daha iyi yapılması,
en doğru şekilde yapılması
olmak üzere iki amacı vardır.
Günümüzde rasgele aramaların kullanımı artmaktadır. Bu tip aramalar en iyilemenin daha iyi yapma amacını sağlamakta daha başarılıdırlar. İnsanların bilgisayarlardan genel beklentisi mükemmellik olduğu için bu tip aramalar başarısız görünebilir. Genetik algoritmalar klasik yöntemlerin çok uzun zamanda yapacakları işlemleri kısa bir zamanda çok net olmasa da yeterli bir doğrulukla yapabilir.
1.2.4. Genetik Algoritmaların Farkları
Genetik algoritma parametrelerin kodlarıyla uğraşır. Parametreler kodlanabildiği sürece fark etmez.
Genetik algoritma bir tek yerden değil, bir grup çözüm içinden arama yapar.
Genetik algoritma ne yaptığı konusunda bilgi içermez, nasıl yaptığını bilir. Bu nedenle bir kör arama (blind search) metodudur.
Genetik algoritmalar olasılık kurallarına göre çalışır. Programın ne kadar iyi çalışacağı önceden kesin olarak belirlenemez. Ama olasılıkla hesaplanabilir.
1.2.5. Şema teorisi (Schemata theorem)
Genetik algoritmalarda oluşan başarılı bireyler incelenirse, bu bireyler arasındaki benzerlikler bulunabilir. Bu benzerliklerden yola çıkarak şemalar oluşturulabilir. İkilik dizi kodlaması için aşağıdaki yöntem önerilebilir.
0,1 ve # (‘#’ o konumda 0 veya 1 olmasının önemsiz olduğunu gösterir)
Örnek olarak ikinci ve dördüncü bitleri 1, altıncı biti 0 olan çözümlerin başarılı olduğu bir toplumda şu şema oluşturulabilir:
#1#1#0
Bu şemaya uygun aşağıdaki ikilik diziler yazılabilir:
010100, 010110, 011100, 011110, 110100, 110110, 111100, 111110.
Görüldüğü gibi şemaların katılması ikilik dizilerle gösterilen arama aralığını büyütmektedir. Arama aralığının büyümesinin sonucun bulunmasını zorlaştırması beklenir ancak durum böyle değildir. Seçilim ve yeniden kopyalama ile iyi özellikler daha çok bir araya gelerek daha iyi değerlere sahip şemalara uygun çözümler elde edilir.
Genetik algoritma kendi içinde sanal olarak şemaları oluşturur. Toplumun bireyleri incelenerek bu şemalar ortaya çıkarılabilir. Genetik algoritmalar şemaları oluşturmak için toplum üyelerinin kodları dışında bir bilgi tutmaz. Genetik algoritmaların bu özelliğine içsel paralellik (implicit parallelism) denir. Her nesilde, iyiyi belirleyen şemalardaki belirsiz yada önemsiz elemanlar azalır. Böylece genetik algoritmalar sonuca doğru belli kalıplar içinde ilerler.
1.2.6. Ga’nın Performansını Etkileyen Nedenler
Kromozom sayısı: Kromozom sayısını arttırmak çalışma zamanını arttırırken azaltmak da kromozom çeşitliliğini yok eder.
Mutasyon Oranı: Kromozomlar birbirine benzemeye başladığında hala çözüm noktalarının uzağında bulunuyorsa mutasyon işlemi GA’nın sıkıştığı yerden kurtulmak için tek yoludur. Ancak yüksek bir değer vermek GA’yı kararlı bir noktaya ulaşmaktan alıkoyacaktır.
Kaç Noktalı Çaprazlama Yapılacağı: Normal olarak çaprazlama tek noktada gerçekleştirilmekle beraber yapılan araştırmalar bazı problemlerde çok noktalı çaprazlamanın çok yararlı olduğunu göstermiştir.
Çaprazlamanın sonucu elde edilen bireylerin nasıl değerlendirileceği: Elde edilen iki bireyin birden kullanılıp kullanılamayacağı bazen önemli olmaktadır.
Nesillerin birbirinden ayrık olup olmadığı: Normal olarak her nesil tümüyle bir önceki nesle bağlı olarak yaratılır. Bazı durumlarda yeni nesli eski nesille birlikte yeni neslin o ana kadar elde edilen bireyleri ile yaratmak yararlı olabilir.
Parametre kodlanmasının nasıl yapıldığı: Kodlananın nasıl yapıldığı en önemli noktalardan biridir. Örnek vermek gerekirse kimi zaman bir parametrenin doğrusal yada logaritmik kodlanması GA’nın performansında önemli bir farka yol açabilir.
Kodlama gösteriminin nasıl yapıldığı: Bu da nasıl olduğu yeterince açık olmamakla beraber GA’nın performansını etkileyen bir noktadır. İkilik düzen, kayan nokta aritmetiği ya da gray kodu ile gösterim en yaygın yöntemlerdir.
Başarı değerlendirmesinin nasıl yapıldığı: akıllıca yazılmamış bir değerlendirme işlevi çalışma zamanını uzatabileceği gibi çözüme hiçbir zaman ulaşmamasına neden olabilir.
Genetik Algoritmanın Matematiksel Modeli :
1.2.7.1Şema Modeli :
Şema modeli , ikili düzen kullanıldığında , { 0,1,* } alfabesi üzerinde tanımlı bir desen olarak da tanımlanabilir.
Şema , birey deği bireyin özelliklerini kodlayan bir yapıdır.
Örnek : ***01**1 bireyin taşıdığı bir özelliği temsil eder.
GA’ da bireyler , ikilik düzende sabit uzunluklu katarlar olarak ifade edilirler.
Desende , 0 ve 1 ler tanımlayıcı bitler (defining bits)olarak adlandırılır.
1.2.7.2 Şema Mertebesi :
Şema Mertebesi tanımlayıcı bitlerin sayısıdır ve - order o(H) - olarak ifade edilir.
Örnek :
**0*11**1 ile ifade edilen H şemasının mertebesi : order o(H) = 4
1.2.7.3 Tanımlayan Uzunluğu :
En sol ve en sağ tanımlayıcı bitler arasındaki uzaklık olarak ifade edilir.
Örnek1 : 011*1** ile ifade edilen H şemasının mertebesi 4 ,
Tanımlayan Uzunluğu defining length d(H) = 4 dır Çünkü ,
ilk tanımlayıcı bit olan 0 ın pozisyonu 1 , son tanımlayıcı bit olan 1 in katardaki pozisyonu 5 ve d(H) = 5-1=4.
Örnek2 : 0****** ile ifade edilen H şeması için tanımlayan uzunluğu ;
d(H) = 1-1 = 0 dır.
Eğer bir X katarının bit değerleri ve katardaki yerleri H şemasının tanımlayıcı bitleri ile aynı konumda ise , X katarı S şemasının bir örneğidir.
Örnek : 00011 ve 00110 katarları 00*1* şemasının örnekleridir.
1.2.8 Genetik Operatörlerin Şema Üzerine Etkileri :
1.2.8.1 Çoğalmanın Etkisi :
Verilen bir t zamanında ( adımında) ;
A ( t ) : nesil ( population ) ,
m( H ,t ) : t adımında nesilde H şemasına ait örneklerin sayısı ,
f : uygunluk kodu ( değerlendirme - evaluation ) ,
f ( H ) : t. adımda H şemasına ait katarların uygunluk değerlerinin ortalaması ,
fort : tüm nesilin ortalama uygunluk değeri .
t + 1 adımda ( çoğalmada ) , A( t+1 ) nesilinde H şemasının m ( H,t+1) kopyası bulunması beklenir.
Çoğalma sırasında Aj katarının seçilme olasılığı ;
pi = fi / åfj olmak üzere ,
m( H,t+1) = m (H,t).n.f(H) / åfj ve fort = åfj / n
m(H,t+1) = m(H,t).f(H) / fort olacaktır.
H şemasının uygunluk değeri , ortalama uygunluk değerinden ( c sabit olmak üzere ) c. fort kadar fazla ise ;
m(H,t+1) = m(H,t).( fort + c. fort) / fort = (1+c).m(H,t) ,
t = 0 dan başlayarak , m(H,t) = m(H,0).(1+c)t şeklinde geomaetrik bir fonksiyon elde edilir.
1.2.8.2. Çaprazlamanın Etkisi :
Çaprazlama , katarlar arasında yapısal ama aynı zamanda raslantısal bir bilgi değiş tokuşudur.
A = 0 1
1000 ( Birey )
H1 = *1*
***0
H2 = ***
10** ( Hj bireyinin özellikleri )
Bir şemanın çaprazlamayı bozulmadan atlatabilmesi için , kesim noktasının tanımlayan uzunluğun dışında klaması gerekmektedir.
l : katar uzunluğu ,
: şemanın tanımlayan uzunluğu .
Şemanın çaprazlamayı bozulmadan atlatabilmesi olasılığı :
ps = 1 - (d(H) / ( l -1 ) )
Şemanın çaprazlanmaya girme olasılığı pc , ps alt sınırı ;
ps > 1 - pc (d(H) / ( l -1 ) ) olacaktır.
Çaprazlama ve çoğalma operatörlerinin bağımsızlığı kabul edilecek olursa , şemanın bir sonraki nesildeki beklenen ( bozulmadan aktarılan ) temsilci sayısı :
m( H,t+1) > m(H,t).f(H). / fort . (1 - pc (d(H) / ( l -1 ) )) olacaktır.
Hem çoğalma hem çaprazlama operatorleri uygulandığında şemanın bir sonraki nesilde beklenen temsilci sayısı ( m(H,t+1)) iki olaya dayanır :
Şemanın uygunluk değerinin nesil ortalamasından yüksek ya da alçak olması ,
Şemanın , kısa ya da uzun tanımlayan uzunluğa sahip olması .
Eğer ,
Şemanın uygunluk değeri nesil ortalamasında yüksekse ,
Şemanın tanımlayan uzunluğu kısaysa
özellik artarak diğer nesillere aktarılır.
Mutasyonun Etkisi :
Mutasyon , bir basamağın pm olasılıkla değişmesidir.
Bir şemanın mutasyonu bozulmadan atlatabilmesi için ;
tüm allele’rinin ( genlerin alabileceği sayılar ) korunması gerekmektedir.
Her allele’nin kurtulma olasılığı : 1 - pm
o(H) mertebesindeki bir şemanın kurtulma olasılığı : (1 - pm )o(H)
pm ‘in çok küçük değerleri için (pm << 1) şemanın kurtulma olasılığı :
o(H). pm olarak ifade edilebilir.
Çoğullama (reproduction) , çaprazlama ( crossover ) ve mutasyon (mutation) etkileri toplandığında Şema Teoremine , diğer adıyla Genetik Algoritmalar Teoremi ‘ne ulaşılır :
m( H,t+1) > m(H,t).f(H). / fort . (1 - pc (d(H) / ( l -1 ) )-o(H). pm )
Sonuç olarak , kısa tanımlayıcı uzunluklu ,düşük mertebeli ve yüksek uygunluk değerine sahip olan şemalar örneklenir ,birleştirilir ve potansiyel olarak daha yüksek uygunluk değerine sahip katarlar oluşturmak üzere yeniden örneklenir ( çoğaltılır) .
Her akla yatkın kombinasyonu deneyerek yüksek performanslı katarlar yaratmaya çalışmak yerine geçmiş örneklemelerin en iyi kısmi sonuçlarından gitgide daha iyi nesiller oluşturulur.
1.2.9. Uygulama Alanları
Genetik algoritmaların en uygun olduğu problemler geleneksel yöntemler ile çözümü mümkün olamayan ya da çözüm süresi problemin büyüklüğü ile üstel orantılı olarak artanlardır. Bugüne kadar GA ile çözümüne çalışılan konulardan bazıları şunlardır.
Optimizasyon: GA, sayısal optimizasyon ve kombinetoral optimizasyon problemleri olan devre tasarımı, doğrusal olmayan denklem sistemlerinin çözümünde ve fabrika-üretim planlamasında kullanılır.
Otomatik Programlama (automatic programming): GA, bilgisayar programları yardımıyla network sıralamasında (sorting),sınav/ders programı hazırlanmasında kullanılır.
Makine öğrenmesi (machine learning): GA, robot sensorlerinde, neural networklerde,VLSI yonga tasarımı ve protein yapısal analizinde kullanır.
Ekonomi (economics): GA, ekonomik modellerin geliştirilmesinde ve işlemesinde kullanılır. Mesela Seralarda salatalık yetiştirilmesinde iklim kontrolünü yapabilmek ve optimal sıcaklığın nasıl yayılmasını belirlemek için GA yöntemin kullanılmıştır. Yöntem optimal kontrol teorisinde kullanılan dinamik optimumlaştırmaya bir alternatif olarak ele alınmıştır
İmmün sistemler (Immune systems): GA, çok-gen’li ailelerin evrimi esnasında ve doğal immün sistem modellerinde kullanılır.
Popülasyon genetiği (population genetics): GA, evrim ile ilgili sorulara cevap bulmada kullanılır.
Evrim ve öğrenme (evolution and learning): GA, fertlerin öğrenmesini ve türlerin evrilmesinde kullanılır.
Sosyal sistemler (social systems): GA, sosyal sistemlerin analizinde kullanılır.
Müzik. Stokastik müzik üretecinin çıktısından elde edilen materyali sınırlayan bir takım veri filtreleri ile müzik oluşturma Genetik algoritmaların bir uygulamasıdır. Bunun için algoritmik düzenin yapısındaki değişiklikler tanımlanır ve bunların çıktıları müzikal örnekler verirler.
1.3. GA NASIL ÇALIŞIYOR?
Gördüğümüz gibi GA’nın işleyişi çok basittir fakat bu kadar basit olan yöntemin, en zor problemleri nasıl çözdüğünün anlaşılması da o kadar zordur. Bu da GA’nın en karmaşık ve bilim adamlarının yıllardır çözmeye çalıştıkları en önemli sorulardan biridir.
GA’nın bu yönünü biraz açıklayalım; GA, çözüm(ler) bulmak için taranması gereken parametre uzayının çok büyük olduğu durumlarda bu arama işlemi, için en akılcı yöntemdir. Evrimin her sürecinde edinilen bilgi sonra ki nesillere aktarılarak taramanın daha uygun bölgelerde gezmesi sağlandığı gibi değişim işlemi yardımıyla yerel çözüm noktalarına sıkışıp kalma olasılığı da azaltılıyor. Ayrıca GA’nın paralel işlem yapılan bilgisayarlarda kullanılmaya elverişli yapısı da zaman alıcı problemlerin çözümü için çekici bir seçenek olmasını sağlamaktadır.
1.3.1 Örnek: Fonksiyon Maksimizasyonu
Amacımız genetik algoritmanın bilgisayarda nasıl çalışacağını kağıt üzerinde açıklayıcı şekilde anlatmaktır.
Amaç: f(x)=x² , xÎ[0,31] şeklinde verilen bir fonksiyonun, verilen aralıkta maksimizasyonu yapılması istenmektedir.
Adım 1: İlk olarak x sayısının kodlanması işlemi yapılmalıdır. x’in 0 ve 1′lerden oluşan 2 tabanındaki gösterilimi kullanılacaktır. Dolayısıyla x, 5 bit uzunluğunda bir kodla (string) temsil edilecektir. Öyle ki 0: “00000” ve 31: “11111” olacaktır.
Adım 2: Toplumun birey sayısı n:4 olarak seçilmiştir. Toplumu oluşturan dört birey, her biri 5 bit uzunluğunda birer kromozomla temsil edildiği için toplam 20 kere yazı tura atmak suretiyle belirlenmiştir. Elde edilen birey kromozomları aşağıdadır.
Birey 1: 01101, x = 13 , x² = 169
Birey 2: 11000, x = 24 , x² = 576
Birey 3: 01000, x = 8 , x² = 64
Birey 4: 10011, x = 19 , x² = 361
Adım 3: Yukarıda belirlenen bireyler için f(x)=x², bireylerin uygunluk değerlerini verir. Dört bireyin toplam uygunluk değerleri “169+576+64+361=1170” dir. Dolayısıyla her bir bireyin rulet tekerleğinde kaplayacağı alan şu şekilde hesaplanır.
Birey 1: 169/1170=0.14 : %14
Birey 2: 576/1170=0.49 : %49
Birey 3: 64/1170=0.06 : %6
Birey 4: 361/1170=0.31 : %31
Bu değerler, rulet tekerleğinin her çevrilişinde hangi olasılıkla hangi bireyin seçileceğini belirtir, yani 0.14 olasılıkla 1 numaralı birey seçilecektir. Rulet tekerleği ve bireylerin tekerlek üzerindeki dağılımları Şekil-3 de gösterilmiştir
. Şekil-3. Rulet Tekerleği Dağılımı
Adım 4: toplumda ki birey sayısının sabit kaldığı varsayıldığından dolayı, rulet tekerleği 4 kere çevrilerek çiftleşme havuzu oluşturulacaktır. Rulet tekerleği döndürülmüş ve şu sonuçlar elde edilmiştir.
Birey 1 : 1 kere
Birey 2 : 2 kere
Birey 3 : 0 kere
Birey 4 : 1 kere
Bunun sonucunda elde edilen çiftleşme havuzunda şu şekildedir;
Aday 1 : 01101 (Birey 1)
Aday 2 : 11000 (Birey 2)
Aday 3 : 11000 (Birey 2)
Aday 4 : 10011 (Birey 4)
Adım 5: çiftleşme havuzu belirlendikten sonra iki aşamalı çaprazlama uygulanır. İlk aşamada adaylar çiftleşmek üzere rasgele olarak eşlenirler. Her ikili grup için bir kere zar atılarak çaprazlaşmanın oluşacağı nokta belirlenir. rasgele eşleştirme yapılmış ve bunun sonucunca ( Aday 1, Aday 2) ve (Aday 3, Aday 4) ikili grupları oluşmuştur. Çaprazlaşma noktalarıca zar atılarak 1. Grup için k=4 ve 2. Grup içinde k=2 olarak belirlenmiştir. Bu aşamadan sonra çaprazlaşma gerçekleştirilmiş ve şu sonuçlar oluşmuştur; ( çaprazlaşma noktaları “/” ile belirtilmiştir.)
Çiftleşme grubu 1: (k=4)
Aday 1 : 0110/1 oluşan Birey 1 : 01100
Aday 2 : 1100/0 oluşan Birey 2 : 11001
Çiftleşme grubu 2 : (k=2)
Aday 3 : 11/000 oluşan Birey 3 : 11011
Aday 4 : 10/011 oluşan Birey 4 : 10000
Adım 6: Son aşama olan mutasyon bitler düzeyinde uygulanır. Bu örnekte her bir bit için (toplam 20 bit var) mutasyon olma olasılığı 0.01 olarak seçilmiştir. Dolayısıyla her bir bit için ağırlıklı yazı/tura (mutasyon olasılığına göre) atılarak hangi bitlerin mutasyona uğrayacağı belirlenir. Bu işlem yapılmış ve sonuçta oluşan birey 3’ün 2 numaralı bitinde mutasyon olacağı ortaya çıkmıştır.
Oluşan Birey 3 : 11011
Mutasyon sonucu oluşan Birey 3 : 10011
Bu adımın tamamlanmasıyla bir sonraki kuşağı oluşturacak toplumun bireyleri belirlenmiş olur. Yeni toplum şu
şekildedir;
Birey 1 : 01100, x=12, x²=144
Birey 2 : 11001, x=25, x²=625
Birey 3 : 10011, x=19, x²=361
Birey 4 : 10000, x=16, x²=256
3 temel operatörden oluşan genetik algoritma her aşamada yeni oluşan kuşağa uygulanarak bir sonraki kuşak elde edilecektir. Yukarıdaki örnekte tek bir iterasyon yapılmış ve başlangıç toplumundan bir sonraki kuşak oluşturulmuştur ancak genetik algoritmanın çalışmasının tam olarak gözlenebilmesi için tek bir iterasyon yeterli değildir. Yukarıdaki işlemlerde her şey çok fazla rasgele gibi görünse de, uygunluk değeri yüksek olan bireylerin seçilme ve çiftleşme olasılıkları yüksek olduğu için kuşaklar ilerledikçe toplumu oluşturan bireylerin uygunluk değerlerinin ortalamasının da arttığı gözlenecektir. Bunun için ise tek bir iterasyon yeterli değildir.
1.4. SONUÇLAR
Frekanslarının değişim hızlarının basamakların değerlerine bağlı bir sıra izlemesi var olan kuramlarla uyuşmaktadır. Şema kuramı, genetik algoritmaların çalışması sırasında, öncelikle kısa ve az tanımlı şemaların seçilerek toplumdaki frekanslarını arttırmalarını öngörür. En kısa anlamlı şemalar, bir tek belirli elemanı olan şemalardır. Bu tip şemalar içinde, seçim işleminden en çok en anlamlı basamağı tanımlı olan şemalar etkilenir. Çünkü bu tip şemaların örneklerinin başarımları arasında önemli farklar vardır.
Genetik algoritma çalışmaya başladıktan bir süre sonra en anlamlı basamaklarda bir değer baskın gelir. Bir basamakta bir değerin baskın gelmesi ilgili noktanın genetik algoritmanın araştırma işleminde yer almaması anlamına gelir. Örneğin, toplumun %95’i çözümün bir bit pozisyonunda 0 taşıyorsa bu pozisyonda bulunan değer çözümler arasında farklılık yaratmaz; bu noktanın değeri hemen hemen hepsinde aynıdır. Sonuç olarak, o noktada ki değerin araştırması bitmiş sayılabilir. Genetik algoritma bu aşamadan sonra o nokta hiç yokmuş gibi diğer noktalarla işleme devam eder. Tüm pozisyonlar için bir değer baskın hale geçtiğinde arama bitmiştir. Bu aşamadan sonra genetik algoritmanın daha başarılı bir değer bulması daha zordur. Benzerlikler fazla olduğu için arama uzayının değişik bölgelerine ulaşılamaz. Toplum bu duruma ulaştığında en genel olan çözüm en iyi çözüm olmak zorunda değildir. Genetik algoritma, bu genel çözüme ulaşırken daha iyi çözümler bulmuş olabilir.
Bit pozisyonlarının frekansları yukarıda belirtilen olaya bağlı olarak sırayla baskın hale geçer. Genetik algoritmada gözlemlenen bu durumun bazı istisnaları vardır.
Bazı basamaklar normalden daha erken baskın duruma geçer.
Bazı basamaklar baskın değerlerini değiştirirler.
Bazı basamaklar hiçbir zaman baskın hale geçmez.
Birinci durumda sözü geçen pozisyondaki çeşitliliğin kaybedilmesi olarak açıklanabilir. Bu kaybın nedeni, büyük bir olasılıkla o parçaların başarılı bir parça ile birlikte kopyalanmasıdır. Başarılı şemanın örnek sayısı artarken bu şemayı içeren ancak daha çok elemanı belirli olan bir şemanın da örnekleri artmaktadır. Bu ikinci şema en iyileme işleminde bazı pozisyonların sıradan bağımsız olarak baskın hale geçmesine neden olur. İkinci şema genelde başarısız parçalar içerir. Bu parçalar ‘cross over’ işlemi sırasında başarılı parçalardan ayrılmayabilir yada bu ayrılma yeterince olmaz. Böylece bazı noktalarda beklenenden erken bir tekilleşme ve çeşitlilikte azalma oluşur.
İkinci durum genetik algoritmanın ilerlemesi sırasında yeni değerlerin bulunmasıyla ortaya çıkar. Bu tip bir değişimin ortaya çıkması yakınındaki değerlerin değişmesiyle gerçekleşir. Örneğin (1#####) şeması başarısız, (0#####) ve (100000) şemaları başarılı olsun. Böyle bir problemde genetik algoritmanın çalışması sırasında öncelikle (0#####) şeması baskın hale gelir. Daha sonra (100000) keşfedilir. (100000) toplumda çoğaldıkça 1. pozisyondaki frekans değişir.
Programın çalışmasını bitiren iki etken vardır. İlk etken en fazla tekrar sayısına ulaşılmasıdır. İkincisi ise en fazla başarısız tekrar sayısına ulaşılmasıdır. En fazla başarısız tekrar sayısına ulaşıldığına toplumda değişkenlerin son rakamları için çeşitlilik korunmuş olabilir.
Aramanın yapılmasında izlenen sıra yaklaşık değerlere bağlıdır. Genetik algoritma çalışırken mutasyon işlemcisi sayesinde her aşamada değişik parçalar oluşur. Bu parçaların bir kısmı bir süre daha toplumda kalır ve daha iyi parçaların toplumda çoğalmasını yavaşlatır. Bu etki en anlamsız bitlerde en fazladır; çünkü bu bitlere doğru ilerlendikçe çözümün kesinliği azalır. Çözümün arama aralığının solunda mı sağında mı olduğunu ortaya koymak genetik algoritma için oldukça kolaydır. Seçilen parçalar yakalaşık olarak iki bölgeye de eşit dağılmıştır. Zaman ilerledikçe bir tarafta kalan parçaların sayısı artar. Genetik algortima böylece çözümün yerini kabaca tahmin etmiş olur. Parçalar küçüldükçe iş güçleşir çünkü bu küçük aralıklarda eşit değerli noktaların sayısı daha fazladır. Parçaların küçülmesinin bir diğer sonucu da hata payını arttırmasıdır. Arama derinliği arttıkça hata payı da paralel olarak artar.
Genetik algoritmanın başarısı kısaca problemi parçalayarak çalışmasıyla açıklanabilir. Bu aşamada bir dinamik programla yöntemi gibi çalışmaktadır. Genetik algoritmanın bu yöntemlere göre daha başarılı olmasının en önemli nedeni problemin boyutundan bağımsız olmasıdır. Değişken sayısı ve bu değişkenlerin değerlerinin sonuçlara etkisi araştırma yöntemini değiştirmez. Araştırma arama uzayını dinamik olarak parçalar. Algoritmanın çalışması sırasında çevre etkenlerine (biçim dosyasında belirtilen özellikler, rasgele sayı üreticinin ilk değeri) bağlı olarak arama uzayı farklı şekilde taranır. En alt düzeyde işlemler oldukça karmaşık ve değişkendir; ancak üst düzey bir bakışla değişik yollarla da olsa genetik algoritma sonuca ulaşır.
Genetik algoritmalar ayrıca bazı geri dönüşler içerir. Bu geri dönüşler sayesinde daha karmaşık problemler çözülebilir ve genetik algoritma yerel maksimum noktalara takılmaktan kurtulur. Bu geri dönüşlere, genetik algoritmanın içinde bulunan çeşitlilik neden olur. Baskın değerin yanında bazı farklı değerler de denenmeye devam eder. Kimi durumlarda bu farklı değerler baskın değerden daha başarılı olur. Bu olay genetik algoritmanın frekans grafiklerinde baskın değerini değiştiren noktalar olarak kendini gösterir.
PASCAL ÖRNEĞİ
{ initial.sga: initdata, initpop, initreport, initialize’ı içerir }
procedure initdata;
{ Interaktif data araştırmave setup }
var ch, dummy:char; j:integer;
begin
{ assign( rep_file, ‘report.txt’ ); }
rewrite(rep_file, ‘NAME = report.txt’ ); { Liste aygıtları için setup }
clrscr; { Clear screen }
skip(output,9);
repchar(output,’ ‘,25); writeln(’——————————–’);
repchar(output,’ ‘,25); writeln(’Basit bir Genetik Algoritma- SGA’);
repchar(output,’ ‘,25); writeln(’ (c) Bilal ALATAS’);
repchar(output,’ ‘,25); writeln(’ Tum Haklari Saklidir ‘);
repchar(output,’ ‘,25); writeln(’——————————–’);
writeln(’******** SGA Data Girişi ve Başlangici************’);
writeln;
write(’Populasyon boyutunu girin ——- > ‘); readln(popsize);
write(’Kromozom uzunlugunu girin —– > ‘); readln(lchrom);
write(’Max. Generasyonu girin —— > ‘); readln(maxgen);
write(’Crossover olasiligini girin - > ‘); readln(pcross);
write(’Mutasyon olasiligini girin– > ‘); readln(pmutation);
pause(5); clrscr;
{ Rastgele sayı üretecini Initialize et }
randomize;
pause(2); clrscr;
{ Sayaçları Initialize et }
nmutation := 0;
ncross := 0;
end;
procedure initreport;
{ İlk raporu }
begin
writeln(rep_file,’—————————————————-’);
writeln(rep_file,’
Basit bir Genetik Algoritma - SGA - v1.0
‘);
writeln(rep_file,’
(c) Bilal ALATAS
‘);
writeln(rep_file,’
Tun Hakki saklidir
‘);
writeln(rep_file,’—————————————————-’);
skip(rep_file,5);
writeln(rep_file,’ SGA Parametreleri’);
writeln(rep_file,’ ————–’);
writeln(rep_file);
writeln(rep_file,’ Population size (popsize) = ‘,popsize);
writeln(rep_file,’ Chromosome length (lchrom) = ‘,lchrom);
writeln(rep_file,’ Maximum # of generation (maxgen) = ‘,maxgen);
writeln(rep_file,’ Crossover probability (pcross) = ‘,pcross);
writeln(rep_file,’ Mutation probability (pmutation) = ‘,pmutation);
skip(rep_file,8);
writeln(rep_file,’ İlk Nesil İstatistiği’);
writeln(rep_file,’ —————————–’);
writeln(rep_file);
writeln(rep_file,’ Initial population maximum fitness = ‘,max);
writeln(rep_file,’ Initial population average fitness = ‘,avg);
writeln(rep_file,’ Initial population minimum fitness = ‘,min);
writeln(rep_file,’ Initial population sum of fitness = ‘,sumfitness);
page(rep_file); { Yeni sayfa }
end;
procedure initpop;
{ Rastgele bir populasyon initialize et}
var j, j1:integer;
begin
for j := 1 to popsize do with oldpop[j] do begin
for j1 := 1 to lchrom do chrom[j1] := flip(0.5); { Doğru bir yazi tura }
x := decode(chrom,lchrom); { String decode et }
fitness := objfunc(x); { İlk uygunluğu değerlendir }
parent1 := 0; parent2 := 0; xsite := 0; { Çıktı değişkenlerini Initialize Et }
end;
end;
procedure initialize;
{ Başlangıç Koordinatorü }
begin
initdata;
initpop;
statistics(popsize, max, avg, min, sumfitness, oldpop);
initreport;
end;
{ interfac.sga: objfunc, decode’u içerir }
{ Bunlar farklı problemler için değiştirilir. }
function objfunc(x:real):real;
{ Fitness function - f(x) = x**n }
const
{coef = 1073741823.0;} { Domaini normalize etmek için katsayı }
n = 10; { x in kuvveti}
var coef: real;
begin
coef := power( 2, lchrom ) - 1;
objfunc := power( x/coef, n )
end;
function decode(chrom:chromosome; lbits:integer):real;
{ Stringi işaretsiz ikili integer olarak kodlar- true=1, false=0 }
var j:integer;
accum, powerof2:real;
begin
accum := 0.0; powerof2 := 1;
for j := 1 to lbits do begin
if chrom[j] then accum := accum + powerof2;
powerof2 := powerof2 * 2;
end;
decode := accum;
end;
{ random.apb: random number generator ve related utilities i
(advance_random, warmup_random, random, randomize,
flip, rnd ) içerir}
{ Global değişkenler – Bu isimleri başka kodda kullanmayınız}
var oldrand:array[1..55] of real; { Rastgele 55 sayının dizisi}
jrand:integer; { Şuanki rastgele}
procedure advance_random;
{ 55 rastgele sayının bir sonraki kümesini oluştur }
var j1:integer;
new_random:real;
begin
for j1:= 1 to 24 do
begin
new_random := oldrand[j1] - oldrand[j1+31];
if (new_random < 0.0) then new_random := new_random + 1.0;
oldrand[j1] := new_random;
end;
for j1:= 25 to 55 do
begin
new_random := oldrand[j1] - oldrand[j1-24];
if (new_random < 0.0) then new_random := new_random + 1.0;
oldrand[j1] := new_random;
end;
end;
procedure warmup_random(random_seed:real);
{ Get random off and runnin }
var j1,ii:integer;
new_random,prev_random:real;
begin
oldrand[55] := random_seed;
new_random := 1.0e-9;
prev_random := random_seed;
for j1:=1 to 54 do
begin
ii := 21*j1 mod 55;
oldrand[ii] := new_random;
new_random := prev_random - new_random;
if (new_random < 0.0) then new_random:=new_random+1.0;
prev_random:=oldrand[ii]
end;
advance_random; advance_random; advance_random;
jrand:=0;
end;
function random:real;
{ 0.0 ve 1.0 arasında rastgele bir sayı al- Subtractive Method }
{ Detaylar için Knuth, D. (1969), v. 2 ‘ye bakınız }
begin
jrand := jrand + 1;
if (jrand > 55) then
begin jrand:=1; advance_random end;
random := oldrand[jrand];
end;
function flip(probability:real):boolean;
{ Flip a biased coin - true if heads }
begin
if probability = 1.0 then flip := true
else flip := (random <= probability);
end;
function rnd(low,high:integer):integer;
{ Pick a random integer between low ve high arasında rastgele bir sayı seç}
var i:integer;
begin
if low >= high then i := low
else begin
i := trunc( random * (high-low+1) + low);
if i > high then i := high;
end;
rnd := i;
end;
procedure randomize;
{ Rastgele için bir kaynak sayı al ve başlat }
var randomseed:real;
begin
repeat
write(’Seed random sayıyı gir (0.0..1.0) > ‘); readln(randomseed);
until (randomseed>0) and (randomseed<1.0);
warmup_random(randomseed);
end;
{ generate.sga }
procedure generation;
{ select, crossover, ve mutation boyunca yeni nesil üret}
{ Not: Nesil Çift sayılı populasyon boyutuna sahip }
var j, mate1, mate2, jcross:integer;
begin
j := 1;
repeat { select, crossover, ve mutation newpop dolana kadar }
mate1 := select(popsize, sumfitness, oldpop); { Eş çiftlerini al }
mate2 := select(popsize, sumfitness, oldpop);
{ Crossover ve mutation - mutation crossover çine gömülü}
crossover(oldpop[mate1].chrom, oldpop[mate2].chrom,
newpop[j ].chrom, newpop[j + 1].chrom,
lchrom, ncross, nmutation, jcross, pcross, pmutation);
{ Stringi çöz, fitness’ı değerlendir, her iki çocuktaki nesil tarihini kaydet }
with newpop[j ] do begin
x := decode(chrom, lchrom);
fitness := objfunc(x);
parent1 := mate1;
parent2 := mate2;
xsite := jcross;
end;
with newpop[j+1] do begin
x := decode(chrom, lchrom);
fitness := objfunc(x);
parent1 := mate1;
parent2 := mate2;
xsite := jcross;
end;
{ Populasyon indexini arttır }
j := j + 2;
until j>popsize
end;
{ report.sga: writechrom, report’u içerir }
procedure writechrom(var out:text; chrom:chromosome; lchrom:integer);
{ Bir Kromozom yaz : 1′ler (true’lar) ve 0′lar (false’lar) }
var j:integer;
begin
for j := lchrom downto 1 do
if chrom[j] then write(out,’1′)
else write(out,’0′);
end;
procedure report(gen:integer);
{Populasyon reportunu yaz }
const linelength = 132;
var j:integer;
begin
repchar(rep_file,’-',linelength); writeln(rep_file);
repchar(rep_file,’ ‘,50); writeln(rep_file,’Population Report’);
repchar(rep_file,’ ‘,23); write(rep_file,’Generation ‘,gen-1:2);
repchar(rep_file,’ ‘,57); writeln(rep_file,’Generation ‘,gen:2);
writeln(rep_file);
write(rep_file,’ # string x fitness’);
write(rep_file,’ # parents xsite’);
writeln(rep_file, ‘ string x fitness’);
repchar(rep_file,’-',linelength); writeln(rep_file);
for j := 1 to popsize do begin
write(rep_file,j:2, ‘) ‘);
{ Eski string }
with oldpop[j] do begin
writechrom(rep_file,chrom,lchrom);
write(rep_file,’ ‘, x:10, ‘ ‘, fitness:6:4, ‘
‘);
end;
{ Yeni string }
with newpop[j] do begin
write(rep_file,’ ‘, j:2, ‘) (’, parent1:2, ‘,’, parent2:2, ‘) ‘,
xsite:2,’ ‘);
writechrom(rep_file,chrom,lchrom);
writeln(rep_file, ‘ ‘,x:10,’ ‘, fitness:6:4);
end;
end;
repchar(rep_file,’-',linelength); writeln(rep_file);
{ Nesil istatistiği ve toplanan değerler }
writeln(rep_file,’ Note: Generation ‘, gen:2, ‘ & Accumulated Statistics: ‘
,’ max=’, max:6:4,’, min=’, min:6:4, ‘, avg=’, avg:6:4, ‘, sum=’
,sumfitness:6:4, ‘, nmutation=’, nmutation:1, ‘, ncross= ‘, ncross:1);
repchar(rep_file,’-',linelength); writeln(rep_file);
page(rep_file);
end;
{ stats.sga }
procedure statistics(popsize:integer;
var max,avg,min,sumfitness:real;
var popopulation);
{ populasyon istatistiğini hesapla }
var j:integer;
begin
{ Initialize }
sumfitness := pop[1].fitness;
min := pop[1].fitness;
max := pop[1].fitness;
{ max, min, sumfitness için döngü}
for j := 2 to popsize do with pop[j] do begin
sumfitness := sumfitness + fitness; { Uygunluk toplamını biriktir}
if fitness>max then max := fitness; { Yeni max }
if fitness
end;
{ Oratalamayı hesapla}
avg := sumfitness/popsize;
end;
{ triops.sga }
{ 3-operators: Reproduction (select), Crossover (crossover),
& Mutation (mutation) }
function select(popsize:integer; sumfitness:real;
var popopulation):integer;
{Roulette tekerleği seçimi iletek bir birey seç }
var rand, partsum:real; { Tekerlekte rastgele nokta, kısmi toplam }
j:integer; { populasyon indexi }
begin
partsum := 0.0; j := 0; { Zero out sayıcı ve akümülator }
rand := random * sumfitness; { [0,1] arasında rastgele sayıyı kullanan tekerlek noktası }
repeat { tekerlek deliğini bul }
j := j + 1;
partsum := partsum + pop[j].fitness;
until (partsum >= rand) or (j = popsize);
{ Birey sayısını geri gönder }
select := j;
end;
function mutation(alleleval:allele; pmutation:real;
var nmutation:integer):allele;
{ Bir alleli mutasyona uğrat w/ pmutation, Mutasyonların sayı numarası }
var mutate:boolean;
begin
mutate := flip(pmutation); { biaslı parayı döndür }
if mutate then begin
nmutation := nmutation + 1;
mutation := not alleleval; { Bit değerini değiştir }
end else
mutation := alleleval; { Değişiklik yok }
end;
procedure crossover(var parent1, parent2, child1, child2:chromosome;
var lchrom, ncross, nmutation, jcross:integer;
var pcross, pmutation:real);
{ İki ana stringi cross yap, yerine iki çocuk string yerleştir }
var j:integer;
begin
if flip(pcross) then begin { p(cross) ile cross-pver yap}
jcross := rnd(1,lchrom-1); { 1 ve l-1 arasında Cross}
ncross := ncross + 1; { crossover sayacını arttır }
end else { Diğer halde cross cross site’ını mutasyona zorla }
jcross := lchrom;
{ 1. yerdeğişim, 1 1 e ve 2 , 2’ye }
for j := 1 to jcross do begin
child1[j] := mutation(parent1[j], pmutation, nmutation);
child2[j] := mutation(parent2[j], pmutation, nmutation);
end;
{ 2. yerdeğişim, 1 2 ‘ye ve 2 , 1’e ]
if jcross<>lchrom then { cross site is lchrom ise atla—crossover yok }
for j := jcross+1 to lchrom do begin
child1[j] := mutation(parent2[j], pmutation, nmutation);
child2[j] := mutation(parent1[j], pmutation, nmutation);
end;
end;
{ utility.sga: pause, page, repchar, skip, power’ı içerir }
procedure pause(pauselength:integer);
{ Bir süre bekleme }
const maxpause = 2500;
var j,j1:integer;
x:real;
begin
for j := 1 to pauselength do
for j1 := 1 to maxpause do x := 0.0 + 1.0;
end;
procedure page(var out:text);
{ Dosyaya ya da alete form kaynağını yayımla }
begin {write(out,chr(12))} end;
procedure repchar(var out:text; ch:char; repcount:integer);
{ Tekrar ederekl çıkış cihazına bir karakter yaz }
var j:integer;
begin for j := 1 to repcount do write(out,ch) end;
procedure skip(var out:text; skipcount:integer);
{ Alet çıkışında skipcount satırlarını atla }
var j:integer;
begin for j := 1 to skipcount do writeln(out) end;
function power(x,y:real):real;
{ X i y nin kuvvetine büyüt }
begin power := exp( y*ln(x) ) end;
procedure clrscr;
begin
end;
program sga;
{ Basit bir Genetik Algoritma - SGA - v1.0 }
{ (c) Bilal ALATAS }
{ Tum Hakki saklidir }
{uses crt;}
const maxpop = 100;
maxstring = 30;
type allele = boolean; { Allele = bit pozisyonu }
chromosome = array[1..maxstring] of allele; { Bitlerin stringi }
individual = record
chrom:chromosome; { Genotype = bit stringi }
x:real; { Phenotype = unsigned integer }
fitness:real; { Objective fonksiyon değeri }
parent1, parent2, xsite:integer; { parents & cross pt }
end;
population = array[1..maxpop] of individual;
var oldpop, newpopopulation; { Çakışmayan iki populasyon }
popsize, lchrom, gen, maxgen:integer; { Integer global değişkenler }
pcross, pmutation, sumfitness:real; { Real global değişkenler }
nmutation, ncross:integer; { Integer istatistikler }
avg, max, min:real; { Real istatistikler }
rep_file: text; {report file}
{ Utility procedureleri ve fonksiyonları içerir}
{$I utility.sga }
%INCLUDE ./utility.sga
{ pseudo-random number generator ve random utilities’leri içerir }
{$I random.apb }
%INCLUDE ./random.apb
{ ınterface routineleri içerir: decode ve objfunc }
{$I interfac.sga }
%INCLUDE ./interfac.sga
{ İstatistics hesaplamalarını içerir: statistics }
{$I stats.sga }
%INCLUDE ./stats.sga
{ Init. Routinelerini içerir: initialize, initdata, initpop, initreport }
{$I initial.sga }
%INCLUDE ./initial.sga
{ Report routinelerini içerir: report, writechrom }
{$I report.sga }
%INCLUDE ./report.sga
{ 3 operatorleri içerir: select (reproduction), crossover, mutation }
{$I triops.sga }
%INCLUDE ./triops.sga
{ Yeni populasyon üretim rutinini içerir : generation }
{$I generate.sga }
%INCLUDE ./generate.sga
begin { Ana program}
gen := 0; { Set }
initialize;
repeat { Ana iteratif döngü }
gen := gen + 1;
generation;
statistics(popsize, max, avg, min, sumfitness, newpop);
report(gen);
oldpop := newpop; { nesli(üretimi) ilerlet }
until (gen >= maxgen)
end. { Ana program sonu}


alıntı..

__________________