Genetik Algoritma

Genetik Algoritma

Genetik algoritmalar canlılarda bulunan DNA yapısındaki Mutasyon’lardan yola çıkarak geliştirişmiş bir problem çözme yaklaşımıdır. Örneğin elimizde bir fotoğraf olduğunu düşünelim ve bu fotoğrafın içerisinde daha önceden belirlediğimiz bir nesne aradığımızı düşünelim.

Bu nesnenin rengi boyutu ve koordinatı standart olmayacaktır. Bu nesneyi bulma fonksiyonunu şöyle düşünebiliriz:

X (X Ekseni koordinatı) Y (Y Ekseni Koordinatı) W (Nesne Piksel Genişliği) H (Nesne Piksel Yüksekliği).

Yani fonksiyon f(X,Y,W,H) gibi 4 boyutlu bir uzayda aranacaktır. İterasyon tek tek arttırılarak yapılırsa problem çözümü çok uzun sürecektir. Bunun yerine genetik algoritma mantığıyla problem daha kolay ve daha hızlı çözülebilir.

Genetik Algoritma Michigan Universitesinde John Holland tarafından 1975 yılında ortaya atılmıştır. Bu algoritmalarda tek bir çözüm üretilmez, farklı çözümlerden oluşan bir vektör kümesi üretilir. Çözüm kümeleri birbirinden bağımsızdır.

Genetik algoritmalarda Evrim mantığı vardır. Çözüm kümeleri Popülasyonlardan oluşur. Popülasyonlar ise kromozom denilen sayı dizileri kümelerinden oluşur. Her birey bir gen’dir.

Genetik fonksiyonlarda mutosyanlarla farklı bireyler yaratılır ve o bireyin problemi çözüp çözmediğine bakılır. Fitnes fonksiyonu yani uygunluk fonksiyonu denilen bu çözüp çözmedi kontrolünün doğru yapılması algoritmanın en önemli adımıdır. Gen’ler random (rasgele) oluşturulmaz. Anne ve Baba gegenlerden çaprazlanmasıyla ve mutasyonlarla ufak değişiklikler yapılarak çocuklar oluşturulur. Problem çözümüne uzak olan çocuklar evlendirilmezler. İyi çocuklardan yeni genler oluşturulur.

Index

Genetik Algoritmada Kullanılan Metodlar

Algoritma oluşturulurken:

• Fitness (Uygunluk Fonksiyonu) Doğru bir şekilde oluşturulmalıdır.
• Bireyler (Genler) Doğru bir şekilde oluşturulmalıdır.
• Mutasyon ve gen değişimleri doğru yapılmaldır.

Genetik algoritmalar problemi tanımlamanın zor olduğu, problem çözümünün çok uzun ve maliyetli olduğu, geneleksel problem çözme yöntemlerinin işe yaramadığı durumlarda kullanılan çoğu zaman başarılı sonuçlar veren bir algoritmadır.

Genetik Algoritma’da Kullanılan Methotlar

Algoritmada, Seçim, Çaprazlama (Crossover) ve Mustasyonlar kullanılır.

Bu algoritmalar Görüntü algılama, Ses algılama, Harita rota oluşturma gibi yapay zeka uygulamalarında kullanılmaktadır.

Bu algoritma popüler olarak Python ve Matlab’de kullanılmaktadır. Python ortamında yapılan algoritma ile resim oluşturma algoritmasını gelin birlikte inceleyelim:

Python’da Genetik Algoritma Örnek Python Kodları

En baştan başlayaım. Bilgisayarımızda bir Pyton çalıştırma ortamı oluşturmalıyız. Bunun bir kaç yolu var fakat en kolayı aşağıdaki linke tıklayarak resmi Anaconda sitesine giderek Anaconda uygulamasını yükleyelim:

Anaconda | The World’s Most Popular Data Science Platform

Kurulum sonrası Jupyter Notebook’u çalıştıralım ve Python’a ulaşalım:

Açılan tarayıcı sayfasında aşağıdaki gibi yeni bir Python çalışma sayfası oluşturalım:

Artık Python çalışma ortamına ulaştık:

Güncel Python Genetik Algoritması Pygad kütüphanesine buraya tıklayarak ulaşabilirsiniz:

Ayrıca resmi Python yayını ise burada.

Örnek Python genetik algoritma uygulaması python kodlarına devam edelim.

Kütüphaneyi yüklemek için aşağıdaki kodu kullanalım:

Kopyaladığınız kodu Shift + Enter ile çalıştırıyoruz.

Önemli Not

!pip install geneticalgorithm

Sonrasında basit bir örnekle başlayalım. Pozitif tüm sayılar kümesinde toplamı minimum eden 4 sayıyı bulmak gibi bir problemimiz olduğunu hayal edelim. Akıllı olduğumuz için, 0 + 0 + 0 + 0 = 0 sonucunu ve problemi biz yarattığımız için zaten biliyoruz. Peki bu problem makine için bu kadar kolay mı? Öğretmezsek hayır. Karmaşık problem çözümlerini genelde makinalara öğretemeyiz. Bu örnek ile algoritma üzerinden Python ile devam edelim: Not: Aşğıdaki kodda göreceğiniz gibi variable_type=’real’ yani tüm sayılar kümesini düşünelim.

Pozitif Tüm Sayılar Algoritması

import numpy as np
from geneticalgorithm import geneticalgorithm as ga
def f(X):
    return np.sum(X)
varbound=np.array([[0,10]]*4)
model=ga(function=f,dimension=4,variable_type='real',variable_boundaries=varbound)
model.run()

Genetik algoritma hiç bir matematik bilmeden bu problemin sonucunu aşağıdaki gibi yaklaşık 30sn’de buluyor:

Burada sonuç bildiğimiz değer 0 çıkmadı ama 0.0016 çıktı. Yani bu aslında 0 demek. Makina genetik algoritma kullanarak problemimizi doğru şekilde çözdü.

İlerleyen bölümlerde daha karmaşık problem çözümleriyle devam edip algoritmanın daha basit mantığını anlatacağız.

Sorunu şöyle geliştirelim tüm sayılar değil de pozitif tam sayılar yani 1 ,2 ,3,.. gibi bir kümede toplamı en küçük sonuçlanan sayıları düşünelim: Python kodları aşağıdaki gibi olacak:

Problemi optimize ettik ve işlem süresi yaklaşık 2sn sürdü. Makina tam doğru sonucu çok daha kısa sürede bilerek değil ama deneme yanılma ile ve Algoritmayı kullanarak aşağıdaki gibi buldu:

Şimdi problemi Boolean yani evet hayır olarak düşünelim ve zorluğu arttıralım. 100 Tane rastgele 1 ve 0 toplamını minimum değerle donuçlandıran bir problemimiz olduğunu düşünelim ve işi algoritmaya teslim edelim. Bildiğiniz gibi bilgisiayarlar ikili sistemde yani 1 ve 0 ile çalışırlar. Kodlarımız aşağıdaki gibi olacak:

import numpy as np
from geneticalgorithm import geneticalgorithm as ga
def f(X):
return np.sum(X)
model=ga(function=f,dimension=100,variable_type='bool')
model.run()

2’lik olasılıkta 100 ihtimal yazıldığı kadar kolay değildir. Sonuç 1.2676506e+30’dür. Yani bilgisayarın sonuçlandırmada çok zorlanacağı bir işlemdir.

Fakat genetik algoritma sayesinde bu işlem yaklaşık 1dk sürmektedir.

Sıfırın 1’den daha mantıklı olduğunu bilmeseydik (Çoğu problemde bilmiyoruz) Doğru sonucu bulma olasılığımız ise 633.825.300.114.114.700.748.351.602.688 ‘da 1 idi. 30 Basamaklı bir sayı olan bu sayı Milyon, Milyar, Trilyon, Katrilyon, Kentrilyon, Sekstilyon, Septilyon, Oktilyon ve sonra Nonilyon’da 1 ihtinmaldir. Bu problemin çözümü basit bir algoritma sayesinde 1dk’da bulunmuştur.

Şimdi yukarıdakileri birlikte düşünelim ve problemi çok daha zor hale getirelim; 3 değer düşünelim; 1. değer: 0 ile 3 arasında bütün sayılar olsun.

2. Sayı ise 1 ile 300 arasındaki pozitif tüm tam sayılar olsun;

3. olasılık ise boolean yani 1 ve 0 yani mantık sonuçları olsun:

Kodlar aşağıdaki gibi olacak:

import numpy as np
from geneticalgorithm import geneticalgorithm as ga
def f(X):
    return np.sum(X)
varbound=np.array([[0,3],[1,300],[0,1]])
vartype=np.array([['real'],['int'],['int']])
model=ga(function=f,dimension=3,variable_type_mixed=vartype,variable_boundaries=varbound)
model.run()

Bu işlem ise makine için daha kolay oldu ve yaklaşık 10sn sürdü ve sonucu aşağıdaki gibi doğru olarak buldu:

Genetik algoritmalar fitness yani uygunluk fonksiyonun minimum olması üzerine tasarlanmıştır. Peki ya biz fonksiyonun belirli bir değer olmasını istiyorsak ne olacak? Gelin birlikte inceleyelim:

Örneğin 7 değerin toplamının maksimum değerini bulmak istiyorsak kodlar aşağıdaki gibi olacak:

import numpy as np
from geneticalgorithm import geneticalgorithm as ga
def f(X):
return -np.sum(X)
varbound=np.array([[0,10]]*7)
model=ga(function=f,dimension=7,variable_type='real',variable_boundaries=varbound)
model.run()

İşlem süresi yaklaşık 1dk sürmektedir ve sonuç olarak 9,994 olarak çıkmaktadır. Yani sistem en olası rakkamın 10 olduğunu hesaplamaktadır.

Minimum fonksiyona geri dönelim;

Problemi yine değiştirelim; 4 farklı GERÇEK SAYILAR (Çok zordur) kümesinde sonuç hedefimizin minimum olaması gerektiğini düşünelim. Fakat 1. ve 2. sayınının toplamı maksimum minimum yine örneğin 7 olsun.

Python kodlarını aşağıdaki gibi yazalım:

Algoritma yaklaşık 40sn çalışmaktadır ve aşağıdaki sonuçları üretmektedir:

Genetik Algoritma Parametreleri: Varsayılan ayarlar aşağıdaki gibidir. Probleme göre ayarlar değiştirilecektir.

algorithm_param = {'max_num_iteration': None,\
                   'population_size':100,\
                   'mutation_probability':0.1,\
                   'elit_ratio': 0.01,\
                   'crossover_probability': 0.5,\
                   'parents_portion': 0.3,\
                   'crossover_type':'uniform',\
                   'max_iteration_without_improv':None}

Yazımınızın devamında buraya tıklayarak Genetik Algoritma Kullanarak Resim Oluşturma makalemize bakabilirsiniz.