Genetik Algoritma ve Genetik Programlama

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.

shutterstock_107069489-1000x480.jpegHolland,genetik algoritma teoremini ortaya attığında amacı özel problemler için çözüm üretmek değildi.Holland’ın genetik algoritması; kromozomlardan oluşan popülasyonları genetikteki doğal seleksiyon,çaprazlama,mutasyon ve inversion operatörlerini kullanarak yeni popülasyonlara dönüştürme metoduydu.Her kromozom genlerden oluşuyordu.Seleksiyon ile en uygun kromozomları tekrar üretim için seçiyor,çaprazlama ile bu kromozomları belli noktalarından parça değiş tokuşuna tabi tutuyor,mutasyon ile çeşitliliği sağlıyor ve inversion metodu ile de kromozomların sırasını düzenliyordu.Yıllar geçtikçe Holland’ın genetik algoritması değişikliklere uğradı.

İki temel işlemle (çarprazlama ve mutasyon) değişen genler arasından seçim yapılması (selection) ise genetik algoritmalarda kullanılan ve başarı elde etmeyi sağlayan yöntemdir.Seçme işlemi için turnuva seçimi (tournament selection) veya tesadüf değeri içeren rulet seçimi (roulette wheel selection) yöntemleri kullanılabilir.

11jpm

Turnuva seçimi yönteminde popülasyondan rassal olarak belirli sayıda birey seçilir ve kendi aralarında uygunluklarına göre turnuvaya sokulur.Örnek olarak popülasyonumuzdan rastgele iki birey ismi seçelim: 1. birey ve 2. birey olsun.Bu bireyler kendi aralarında turnuvaya sokulduğunda çaprazlanacak bireylerden biri seçilmiş olur.

Kromozomların şifrelenmesi: 

Adım 1: Çevrimleri bul. Adım 2: Değişimli çevrimleri çocuğa kopyala.

  1. a) İkili kodlama

Her bir kromozom 0 ve 1’lerden oluşan bit dizisidir ve ikili dizi ile ifade edilir.

  1. b) Permütasyon kodlama

Bu kodlama gezgin satıcı problemi ve iş sıralama problemleri gibi sıralama problemlerinde kullanılır.

  1. c) Değer Kodlama

Bu kodlama gerçel gibi kompleks sayıların yer aldığı problemlerde kullanılır.

Kromozom A = 10011111

Kromozom B = 11011110

Kromozom A = 3 5 1 2 4 7 6 0

Kromozom B = 5 3 4 2 1 0 6 7

Kromozom A = 3.2 6.5 0.8 9.4

Kromozom B = ABCDE

Kromozom C = (geri),(sağ),(ileri),(sol)

Ağaç kodlama:

Bir Kelime Bir İşlem Programı

Bu ifade sayılardan ve +, -, *, / aritmetik işlemlerden oluşur.

İlk dört giriş sayısı 1 ile 10 arasından ve son iki sayı 25, 50, 75,100 arasından seçilir.

Sınırlama ise yarışmacının her sayıyı bir kez kullanabilmesidir.

Her zaman tam çözüm bulunmaz.
Genetik algoritma,karmaşık çok boyutlu arama uzayında en iyinin hayatta kalması ilkesine göre bütünsel en iyi çözümü arar.Genetik algoritma da tek bir çözüm yerine birden fazla çözüm bulunur ve çözüm kümesi elde edilir,bu kümeye nüfus ismi verilir.Küme sayesinde de en iyi çözüm ortaya çıkarılır.Bu yöntem doğadan bilgisayarlara en iyi çözümlemenin bulunabilmesi için aktarılmıştır.Genetik algoritmalar problemlerin çözümü için evrimsel süreci bilgisayar ortamında taklit ederler.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.

İşlemler:

  • Bilinen bir çözüm kümesi alınması
  • Rastgele bireyler oluşturulur.
  • Belirli kriterleri sağlayan bireyler oluşturulur.
  • Popülasyondaki birey sayısı genellikle 100 ile 300 arasında seçilir.
  • Bireylerin Değerlendirilmesi
  • Kromozomların çözüme uygunluk değerleri belirlenir

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.

Kullanım alanları:

I)Optimizasyon ve arama problemleri,

II)Planlanlama işlemleri,

III)İş dünyasında öne çıkmak için çözüm önerileri

IV)Robot ve yapay zeka uygulamaları

V)Parametre ve sistem tanımlama vs.

 

Yazar: Zehra Demir

Düzenleme: Taha Berk Arslan

Yararlanılan kaynaklar:
https://tr.m.wikipedia.org/wiki/Genetik_algoritma#Kullan.C4.B1m_alanlar.C4.B1

//bilgisayarkavramlari.sadievrenseker.com/2009/02/16/genetik-algoritmalar-genetic-algorithms/

 

You may also like...

3 Responses

  1. Erol dedi ki:

    Karışık güzel bilgi dolu bir yazı elinize sağlık

  2. Taha Berk Arslan dedi ki:

    Teşekkür ederiz

  3. Emir dedi ki:

    Tam da aradığım türden bir yazı teşekkürler

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir