Genetik Algoritma

Genetik Algoritmalar 

Genetik algoritmalar (GA) günlük hayatta karşılaştığımız çözümü imkansız ya da çok zor olan karmaşık problemlerin hesaplanmasında kullanılmaktadır. GA 1970’li yıllarda Michigan Üniversitesinde öğretim üyeliği yapan John Holland ve onun çalışma arkadaşları ile öğrencileri tarafından geliştirilerek bilgisayar ortamına taşınmıştır. Daha sonra John Holland’ın öğrencisi David Goldberg’in “Gaz Borularının Genetik Algoritma İle Optimizasyonu” adlı doktora tezi ile birlikte genetik algoritmaların teorik olmaktan öteye piyasalarda uygulanabilirliği ispatlanmıştır. 1989 yılında David Goldberg’in bu konuda klasik sayılabilecek kitabı yayınlanmıştır (Goldberg, 1989).

Genetik Algoritmalar mühendislik problemlerinde optimizasyon amacıyla  kullanılmaktadır. GA’ları kör bir arama motoruna benzetebiliriz. GA’lar problemin yapısına bakmaksızın çok karmaşık optimizasyon problemleri için bile çözüm bulabilirler. Problemin karmaşıklığı GA’lar için hiç önemli değildir. GA’ların ihtiyaç duyduğu şey problemin karar değişkenlerinin uygun bir yöntemle kodlanması ve neyin iyi olduğunu GA’ya belirtmek üzere tasarlanan bir uygunluk (amaç) fonksiyonudur. GA’lar çözüm uzayını taramaya bir topluluk ile başladıkları için global optimum çözüme yaklaşmak diğer yöntemlere göre daha kolay olmaktadır. Genel olarak global optimum çözümü bulmayı garanti etmezlerse de buna yakın bir sonucu bulduğu bir çok araştırmayla ispatlanmıştır. GA’lar bir topluluk (başlangıçta bu topluluk genelde rastgele oluşturulur) ile başlar ve bu topluluk üzerinde çaprazlama, seçme ve mutasyon gibi yöntemlerin uygulanmasıyla problemin her aşamasında en iyiye doğru gidiş sağlanır.

 

Genetik Algoritma Aşamaları

Başlangıç: Problemin karar değişkenlerinin şifrelendiği (n) adet kromozom içeren bireylerle başlangıç topluluğunun oluşturulması.

Uyumluluk: Her kromozom için fonksiyonun uygunluk (amaç) değerlerinin bulunması.

Seçim: İki bireyin uygunluk değerlerine göre turnuva, rulet tekerleği gibi seçme operatörlerinden problemin yapısına uygun olanının seçilmesi işlemi.

Çaprazlama: Uygunluk değeri iyi olan bireyler eşleştirilerek  bu bireylerden yeni bireyler oluşturulması.

Mutasyon: Mutasyon olma olasılığına göre seçilen herhangibir bireyin kromozomlarındaki bir bitin değiştirilmesi işlemi.

Elitizm: Mevcut toplulukdaki uygunluk değeri en iyi olan bireyin olduğu gibi yeni topluluk havuzuna aktarılması.

Yeni topluluk havuzu: Yeni oluşan bireylerin bir havuza alınması, eski bireylerin (ebeveynler) öldürülerek havuzdan atılması.

Sonuç: Topluluktaki bireylerden birisi istenilen sonucu veriyorsa algoritmanın sona erdirilmesi.

Döngü: 2. adıma geri dönülmesi. 

 

Görüldüğü üzere genetik algoritmaların yapısı oldukça basittir ve bir probleme kolaylıkla uygulanabilir. Neyin iyi olduğunu GA’ya bildirmek için bir uygunluk (amaç) fonksiyonu oluşturulması ve problemin değişkenlerinin kodlanmasıyla her çeşit karmaşık problem GA’lar sayesinde çözüme ulaşabilir (Goldberg, 1989). Topluluktaki bireyler kromozomların birleşmesiyle oluşur. Birey çözümü ifade eder ve sürekli iyiye doğru giden topluluklar arasındaki en iyi birey sonuç olarak alınır. Kromozomlar ikili kodlama, reel sayı kodlama, tam sayı kodlama vb çeşitlerinden uygun birisi kullanılarak kodlanır. İkili kodlamada bitler (genler) kullanılır; bitler 1 ya da 0 olmak üzere iki değer alabilirler. Kromozomların uzunluğu da problemin yapısına göre değişir. Örneğin 32 farklı karar değişkeni olan bir problem için kromozomun 2n=32; n=5 bit değeri vardır. 00010 11001 10101 şeklinde kromozomlar birleşerek bireyi oluşturur. Genetik algoritma operatörlerinin detaylı anlatımı için yukarıdaki butonları kullanınız.