Diophantine ve Genetik Algoritmalar

Genetik algoritmaları öğrenmek için çözdüğüm ilk problem “diophantine denklemleri”dir. O zamanlar Java’da bu uygulamayı gerçekleştirmiştim.

Bu aralar Python’a merak sardım. Bari şu diophantine’yi bir de GA ile Python’da çözeyim dedim. Çok basit bir çözüm ama GA’nın da mantığını yansıtan bir örnek oldu.

Problemimiz: a+2*b+3*c+4*d=30 denklemini sağlayan a,b,c,d doğal sayılar nelerdir?

Tasarımız ise şu şekilde oldu: Her bir kromozom aday bir çözümdür. O halde kromozomumuz 4 tane gen içerir ve her bir gen, denklemde bir bilinmeyene karşılık gelir. Uygunluk fonksiyonumuz zaten denklemin kendisidir. Çaprazlama fonksiyonumuz anneden ilk iki gen, babadan ise son iki geni alıp yavru bir kromozom oluşturur. Seçme fonksiyonu ise son derece ilkeldir. Populasyondaki tüm kromozomları uygunluk değerine göre sıralar ve belli aralıktaki kromozomlardan anne ve baba kromozomu seçer. Mutasyon işleminde ise sadece bie kromozomun ilk genine yeniden değer ataması yapılır.

Afiyet olsun.





import random

#kromozom uretilir.
#her kromozom 4 genden olusur.
#ve her gen bir bilinmeyeni temsil eder.
def kromozomUret(): 
    kromozom=[random.randint(0,(30/x)) for x in range(1,5)]
    return kromozom

#populasyon uretilir.
#bu populasyon popSay kadar kromozom icerir.
def populasyonUret(popSay):
    populasyon=[]
    while popSay>0:
        kromozom=kromozomUret()
        uygunlukHesap(kromozom)
        populasyon.append(kromozom)      
        popSay-=1
    return populasyon

#populasyondaki kromzomlar uygunluk degerine gore siralanir.
#ilk iki siradaki kromozomlar ata kromozomlar olarak secilir
def anneVebabaKromozomlariGetir(populasyon):
    popBoyut=len(populasyon)
    for i in range(0,popBoyut-1):
        if (populasyon[i][4]>populasyon[i+1][4]):
            geciciKr=populasyon[i+1]
            populasyon[i+1]=populasyon[i]
            populasyon[i]=geciciKr

    anneIndex=random.randint(0,popBoyut/4)
    babaIndex=random.randint(0,popBoyut/4)      
    return populasyon[anneIndex],populasyon[babaIndex]

def sonuclariYazdir(populasyon):
    for kr in populasyon:
        if kr[4]==0:
            print "1*",kr[0],"+ 2*",kr[1]," + 3*",kr[2]," + 4*",kr[3]," =30"

#iterasyon sayisi, ilgili populasyonun ne kadar evrilecegini belirler.
#populasyon sayisi, kac tane kromozom olacagini belirler.
#caprazlama sayisi, her bir iterasyonda kac defa caprazlama olacagini belirler.
#mutasyon olasiligi ise caprazlama dongusunde ne kadar sayida mutasyon olacagini belirler.      
def havuz(iterasyonSay,populasyonSay,caprazlamaOlasilik,mutasyonOlasilik):
    populasyon=populasyonUret(populasyonSay)   
    while iterasyonSay>0:
        caprazlamaSay=caprazlamaOlasilik
        mutasyonSay=mutasyonOlasilik
        cocukIndex=populasyonSay-1
        while caprazlamaSay>0:    
            anneKr,babaKr= anneVebabaKromozomlariGetir(populasyon)           
            cocuk=caprazlamaYap(anneKr, babaKr)
            populasyon[cocukIndex]=cocuk
            caprazlamaSay-=1
            if mutasyonSay>0:
                mutasyon(populasyon[cocukIndex])
                mutasyonSay-=1
            cocukIndex-=1
        iterasyonSay-=1
    sonuclariYazdir(populasyon)    

#kromzom denklemi ne derecede sagliyor, bunu hesaplar.
#kromozoma uygunluk degeri olarak, 30'a olan uzakligi atanir.
#bu durumda cozumu saglayan kromozom 0 degerini alir.    
def uygunlukHesap(liste):
    uygunlukDeger=liste[0]+liste[1]*2+liste[2]*3+liste[3]*4
    liste.append(uygunlukDeger-30)

#anne kromozomun ilk 2 geni,
#   baba kromozomun ise son 2 geni alinarak yavru birey olusturulur. 
def caprazlamaYap(krAnne,krBaba):
    cocuk=[0,0,0,0]
    cocuk[0:2],cocuk[2:]=krAnne[0:2],krBaba[2:]
    uygunlukHesap(cocuk)  
    return cocuk

#mutasyon olarak kromozomun ilk genine yeniden deger atamasi yapilir
def mutasyon(kromozom):
    kromozom[0]=random.randint(0,20)
    uygunlukHesap(kromozom)

#main
havuz(100, 2000, 50, 5)
Advertisements

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: