Sekiz vezir Problemi ve Genetik Algoritmalar

İnternette genetik algoritmaların ne olduğuna dair yeterince kaynak var. Bundan dolayı ben işin sadece uygulama kısmına değineceğim. Genetik algoritmalarla ilgili bilgilere kod ve us‘ tan , learnartificialneuralnetworks‘ den ve obitko‘ dan ulaşabilirsiniz.

Sekiz vezir problemi içinde yeterince kaynak var. Bu bilgilere Türkçe wikipedia‘dan, ekşisözlük‘ten ulaşabilirsiniz. Ve bu applet de hediyemiz olsun :).

Şimdi asıl işe gelelim. Ben bu aralar bir genetik algoritmalar kütüphanesi üzerinde çalışıyorum. Bu arada da sekiz vezir problemini çözeyim, böylece kütüphaneyi de test etmiş olurum diye düşündüm. . Burada ben sadece bu problemi çözerken kullandığım sınıfları yazacağım…

İlk olarak genetik kütüphanesinden gelen sınıfları yazayım:

//Tüm Gen sınıfları bu sınıftan türetilir.
public abstract class SoyutGen implements Cloneable{

protected boolean _genSecildi;

public boolean genSecildiMi() {
return _genSecildi==true;
}

public void genSecildi() {
_genSecildi=true;
}

public void genSecilmedi(){
_genSecildi=false;
}

public Object clone(){
// TODO Auto-generated method stub
try {
return super.clone();
} catch (CloneNotSupportedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

return null;

}
}

//IntGen sınıfı…
//Sekiz vezir probleminde her bir vezirin temsili bu sınıfın nesneleri ile yapılır.

public class IntGen extends SoyutGen {

private int _deger;

public IntGen(){
}

public IntGen(int deger){
_deger=deger;
}

public void degerVer(int deger) {
_deger=deger;
}

public int  degerNe() {
return _deger;
}

public Object clone(){
IntGen gen=new IntGen();
gen.degerVer(this.degerNe());
return gen;
}

public String toString() {
return _deger+” “;
}
}

// Bu da SoyutKromozom sınıfıdır. Diger kromozom sınıfları bu sınıftan türetilir.
public abstract class SoyutKromozom {

protected double _uygunlukDegeri;
protected int _kromozomBoyut;
protected SoyutGen[] _genler;

public double uygunlukDegeriNe() {
return _uygunlukDegeri;
}

public void uygunlukDegeriniVer(double deger) {
_uygunlukDegeri=deger;
}

public SoyutGen[] genleriGetir() {
return _genler;
}

public SoyutGen lokustakiGeniGetir(int lokus) {
return _genler[lokus];
}

public int genSayisiniGetir() {
return _kromozomBoyut;
}
}

//Kromozom sınıfı. Sekiz vezir problemindeki her bir aday cevap bir kromozomdur.
//Sekiz tane gen içerecektir.

public class Kromozom extends SoyutKromozom {

public Kromozom(SoyutGen[] genler){

_kromozomBoyut=genler.length;
_genler=new SoyutGen[_kromozomBoyut];
_genler=genler;
}

public String toString() {
String s=””;
for(int i=0;i<_kromozomBoyut;i++)
s+=_genler[i].toString();
return s;
}

public SoyutGen[] genleriGetir() {
// TODO Auto-generated method stub
return _genler;
}

public SoyutGen lokustakiGeniGetir(int lokus) {
return _genler[lokus];
}
}

//KromozomFactory sinif

public class KromozomFactory {

private static KromozomFactory fabrika = new KromozomFactory();

private KromozomFactory() {

}

public static KromozomFactory fabrikayiGetir() {
return fabrika;
}

public Kromozom genleriTekilOlmayanKromozomUret(String genTur, int genSay,
int minDeger, int maxDeger) {
Kromozom kromozom = null;

if (genTur.equals(“int”)) {
IntGen[] genler = TekilOmayanRasgele.fabrikayiGetir()
.intGenleriUret(genSay, minDeger, maxDeger);
kromozom = new Kromozom(genler);
}

else if (genTur.equals(“double”)){
DoubleGen[] genler=TekilOmayanRasgele.fabrikayiGetir()
.doubleGenleriUret(genSay);
kromozom=new Kromozom(genler);
}

return kromozom;
}

public Kromozom genleriTekilOlanKromozomUret(String genTur) {
Kromozom kromozom = null;

if (genTur.equals(“int”)) {
IntGen[] genler = TekilRasgele.fabrikayiGetir().intGenleriUret();
kromozom = new Kromozom(genler);
}
return kromozom;
}
}

//Bu sınıf kromozomun rasgele değerlerle ilklenmesini sağlar.
//Biz sekiz vezir probleinde permütasyon kodlama yapacağız. Yani kromozomdaki her bir gen değeri diğerinde farklı olmalı, satranc tahtasında bir konum belirtmelidir.
//Bir örnek:0-5-3-2-6-1-7-4
//Bunun anlamı ilk vezir tahtanın ilk sutununda sıfırıncı satıra, ikinci vezir tahtanın ikinci sutununda beşinci satıra yerleşti //demektir.

public class TekilRasgele {

private static TekilRasgele _rasgele=new TekilRasgele();
private SoyutGen[] _temelGenler;
private  int genSay;

private TekilRasgele(){

}

public static TekilRasgele fabrikayiGetir() {
return _rasgele;
}

public void temelGenleriAyarla(SoyutGen[] genler) {
_temelGenler=genler;
genSay=_temelGenler.length;
}

public IntGen[] intGenleriUret() {

IntGen[] genler = null;
genler = new IntGen[genSay];

Random ran=new Random();
for (int i = 0; i < genSay; i++) {
genler[i]=(IntGen) _temelGenler[i].clone();
}

for(int i=0;i<genSay;i++){
int konum=ran.nextInt(genSay);
IntGen gecici=genler[i];
genler[i]=genler[konum];
genler[konum]=gecici;
}

return (IntGen[]) genler;
}
}

//Secim fonksiyonu
public abstract class AbstractSecimFonksiyonu {

protected int _popBoyut;
protected SoyutKromozom[] _kromozomlar=null;

public void kromozomlariVer(SoyutKromozom[] kromozomlar) {
_kromozomlar=kromozomlar;
_popBoyut=_kromozomlar.length;
}

public SoyutKromozom[] kromozomlariGetir() {
return _kromozomlar;
}
public abstract int enKotuKromozomunYeriniGetir();
public abstract void fonksiyonuCalistir() ;
public abstract SoyutKromozom enIyiKromozomuGetir();
public abstract SoyutKromozom enKotuKromozomuGetir() ;

}

//Sabit durum secimi:
public class SabitDurumSecimi extends AbstractSecimFonksiyonu{

private int _bas;
private int _son=1;

public SoyutKromozom enIyiKromozomuGetir() {
if (_bas>=_popBoyut)
_bas=0;
return _kromozomlar[_bas++];
}

public SoyutKromozom enKotuKromozomuGetir() {
if ((_popBoyut-_son)<0)
_son=1;
return _kromozomlar[_popBoyut-_son++];
}

public int enKotuKromozomunYeriniGetir(){
int son=_popBoyut-_son;
return ++son;
}

public void fonksiyonuCalistir() {
_son=1;
_bas=0;
for(int i=0;i<_popBoyut-1;i++){
for(int j=i;j<_popBoyut;j++){
if (_kromozomlar[i].uygunlukDegeriNe()>_kromozomlar[j].uygunlukDegeriNe()){
SoyutKromozom gecici=_kromozomlar[i];
_kromozomlar[i]=_kromozomlar[j];
_kromozomlar[j]=gecici;
}
}
}
}
}

//Caprazlama fonksiyonu arayüzü
public interface ICaprazlamaFonksiyonu {

public SoyutKromozom caprazla(SoyutKromozom anne,SoyutKromozom baba);
}
//Uygunluk fonksiyonu arayüzü
public interface IUygunlukFonksiyonu {

public void uygunlukDegeriHesapla(SoyutKromozom kromozom);
}


//Havuz sınıfı.
public class Havuz {

private int _popBoyut;
private int _nesilSay;
private String _kromozomYapi;
private String _genTur;
private int _genSay;
private int _minDeger;
private int _maxDeger;
private double _mutasyonOlasiligi;
private double _caprazlamaOlasiligi;
private int _mutasyonSayac;
private int _caprazlamaSayac;

private static int MUTASYONTOHUM=4;
private static int CAPRAZLAMATOHUM=5;

private IUygunlukFonksiyonu _uygunlukFonksiyonu;
private AbstractSecimFonksiyonu _secimFonksiyonu;
private ICaprazlamaFonksiyonu _caprazlamaFonksiyonu;
private IKromozomMutasyon _mutasyonFonksiyonu;

private SoyutKromozom[] _kromozomlar;
private Random ran = new Random();

/**
*
* @param popBoyut
* @param nesilSay
* @param kromozomTur
* @param kromozomYapi
* @param genTur
*/
public Havuz(int popBoyut, int nesilSay, String kromozomTur,
String kromozomYapi, String genTur) {
_popBoyut = popBoyut;
_nesilSay = nesilSay;
_genTur = genTur;
_kromozomYapi = kromozomYapi;

kromozomTurBelirle(kromozomTur);
}

public void genAyarla(int genSay, int minDeger, int maxDeger) {
_genSay = genSay;
_minDeger = minDeger;
_maxDeger = maxDeger;
}

private void kromozomTurBelirle(String kromozomTur) {
if (kromozomTur.equals(“agac”)) {
_kromozomlar = new AgacKromozom[_popBoyut];
}

else if (kromozomTur.equals(“kromozom”))
{
_kromozomlar = new Kromozom[_popBoyut];

if (_kromozomYapi.equals(“tekilOlmayan”))
for (int i = 0; i < _popBoyut; i++)
_kromozomlar[i] = KromozomFactory.fabrikayiGetir()
.genleriTekilOlmayanKromozomUret(_genTur, _genSay,
_minDeger, _maxDeger);
else if (_kromozomYapi.equals(“tekil”))
for(int i=0;i<_popBoyut;i++)
_kromozomlar[i]=KromozomFactory.fabrikayiGetir()
.genleriTekilOlanKromozomUret(_genTur);

}
}

public void parametreAyarla(double caprazlamaOlasiligi,
double mutasyonOlasiligi) {
_mutasyonOlasiligi = mutasyonOlasiligi;
_caprazlamaOlasiligi = caprazlamaOlasiligi;
}

public void fonksiyonlariAyarla(IUygunlukFonksiyonu uFonk,
AbstractSecimFonksiyonu sFonk,ICaprazlamaFonksiyonu cFonk,IKromozomMutasyon mFonk) {
_uygunlukFonksiyonu = uFonk;
_secimFonksiyonu = sFonk;
_caprazlamaFonksiyonu=cFonk;
_mutasyonFonksiyonu=mFonk;

_secimFonksiyonu.kromozomlariVer(_kromozomlar);

}

private void kromozomlarinUygunlukDegerleriniHesapla(){
for(int i=0;i<_popBoyut;i++){
_uygunlukFonksiyonu.uygunlukDegeriHesapla(_kromozomlar[i]);
//System.out.println(_kromozomlar[i].uygunlukDegeriNe());

}
}

public void genetigiCalistir() {
SoyutKromozom anne=null;
SoyutKromozom baba=null;
SoyutKromozom cocuk=null;

kromozomlarinUygunlukDegerleriniHesapla();
_secimFonksiyonu.fonksiyonuCalistir();

for (int i = 0; i < _nesilSay; i++) {
int konum=0;
for(int j=0;j<(_popBoyut*_caprazlamaOlasiligi);j++){

//int konum=0;
if (caprazlamaVarMi()){
anne= _secimFonksiyonu.enIyiKromozomuGetir();
baba= _secimFonksiyonu.enIyiKromozomuGetir();
cocuk=_secimFonksiyonu.enKotuKromozomuGetir();
cocuk=_caprazlamaFonksiyonu.caprazla(anne, baba);
konum=_secimFonksiyonu.enKotuKromozomunYeriniGetir();
//  System.out.println(“cc=>”+konum);
_kromozomlar[konum]=cocuk;
}
if (mutasyonVarMi()){
_mutasyonFonksiyonu.mutasyon(_kromozomlar[konum]);
}
}
kromozomlarinUygunlukDegerleriniHesapla();
_secimFonksiyonu.fonksiyonuCalistir();
}
}

public void enIyiSonucuYazdir() {
System.out.println(“——————————“);
_secimFonksiyonu.fonksiyonuCalistir();
_kromozomlar=_secimFonksiyonu.kromozomlariGetir();
for(int i=0;i<_popBoyut;i++)
if (_kromozomlar[i].uygunlukDegeriNe()==0){
Kromozom enIyi=(Kromozom) _kromozomlar[i];
System.out.println(“En iyi Sonuc=>”+enIyi.toString()+” “+”Uygunluk Degeri=>”+enIyi.uygunlukDegeriNe());

}
}

private boolean mutasyonVarMi() {
//int x=(int) (_mutasyonOlasiligi*1000);
if (ran.nextInt(MUTASYONTOHUM) == MUTASYONTOHUM/2) {
if ((_mutasyonOlasiligi*1000)>_mutasyonSayac++);
return true;
}
_mutasyonSayac=0;
return false;
}

private boolean caprazlamaVarMi() {
if (ran.nextInt(CAPRAZLAMATOHUM) != CAPRAZLAMATOHUM/2) {
if ((_caprazlamaOlasiligi*100)>_caprazlamaSayac++);
return true;
}
_caprazlamaSayac=0;
return false;
}
}

//Mutasyon Fonksiyonu
public interface IKromozomMutasyon {

public void mutasyon(SoyutKromozom kromzom);
}

Buraya kadar olan tüm sınıflar şu an üzerinde çalıştığın genetik kütüphanesinde olan sınıflardır. Şimdi
sekiz vezir problemini çözmek için gerekli olan bir kaç sınıf daha yazacağız.

SekizVezir kütüphanesi:

//Mutasyon fonksiyonudur.
//İlgili kromozomdaki genlerin yerini rasgele değiştirerek mutasyon gerçekleştirilir.

public class GenlerinYeriniRasgeleDegistir implements IKromozomMutasyon{

private Random _ran=new Random();
public void mutasyon(SoyutKromozom kromzom) {
Kromozom kr=(Kromozom)kromzom;
int konum=_ran.nextInt(8);
int konum1=_ran.nextInt(8);

int gecDeger=((IntGen)kr.lokustakiGeniGetir(konum)).degerNe();
int gecDeger1=((IntGen)kr.lokustakiGeniGetir(konum1)).degerNe();

((IntGen)kr.lokustakiGeniGetir(konum)).degerVer(gecDeger1);
((IntGen)kr.lokustakiGeniGetir(konum1)).degerVer(gecDeger);
}
}

//Çaprazlama fonksiyonudur.
public class RasgeleNoktaCaprazla implements ICaprazlamaFonksiyonu{

private Random _ran=new Random();
private int[] _dizi;
private SoyutGen[] _cocukGenler;
private SekizVezirUygunlukFonksiyonu _uf=new SekizVezirUygunlukFonksiyonu();
private static int BOYUT=8;
private SoyutKromozom _kromozom;

public SoyutKromozom caprazla(SoyutKromozom anne, SoyutKromozom baba) {
//int boyut=anne.genSayisiniGetir();
caprazlamaDizisiniOlustur();

for(int i=0;i<BOYUT;i++){
if (_dizi[i]==0){
_cocukGenler[i]=(SoyutGen) anne.lokustakiGeniGetir(i).clone();
}else{
_cocukGenler[i]=(SoyutGen) baba.lokustakiGeniGetir(i).clone();
}
}
_kromozom=new Kromozom(_cocukGenler);
_uf.uygunlukDegeriHesapla(_kromozom);
kromozomKontrol();
return _kromozom;
}

private void caprazlamaDizisiniOlustur(){
_dizi=new int[BOYUT];
_cocukGenler=new IntGen[BOYUT];

for(int i=0;i<BOYUT;i++)
_dizi[i]=_ran.nextInt(2);
}

private void kromozomKontrol(){
IntGen[] genler= genDizisiGetir();
//SoyutKromozom kr=new Kromozom(genler);
int[] knt1=new int[BOYUT];
int[] knt2=new int[BOYUT];

for(int i=0;i<BOYUT;i++){
for(int j=0;j<BOYUT;j++){
if (genler[i].degerNe()==((IntGen)_kromozom.lokustakiGeniGetir(j)).degerNe()){
knt1[i]=1;
knt2[j]=1;
break;
}
}
}

for(int i=0;i<BOYUT;i++){
if (knt1[i]==0){
for(int j=0;j<BOYUT;j++){
if (knt2[j]==0){
int yeniDeger=genler[i].degerNe();
((IntGen)_kromozom.lokustakiGeniGetir(j)).degerVer(yeniDeger);
knt2[j]=1;
break;
}
}
}
}

}

private IntGen[] genDizisiGetir() {
SoyutGen[] genler=new IntGen[BOYUT];
for(int i=0;i<BOYUT;i++){
genler[i]=new IntGen(i);
}
return (IntGen[]) genler;
}
}


//Sekiz vezir problemi için uygunluk fonksiyonudur.

public class SekizVezirUygunlukFonksiyonu implements IUygunlukFonksiyonu{

private double _puan;
private int[] _referansDizi=new int[8];

public  void uygunlukDegeriHesapla(SoyutKromozom kromozom) {
_puan=0;

for(int i=0;i<8;i++){
diziyiIlkle();
referansOlustur(i);
//IntGen[] genler=new IntGen[8];
//genler=(IntGen[]) kromozom.genleriGetir();
for(int j=i+1;j<8;j++){/*
if ((genler[j].degerNe()==genler[i].degerNe()+_referansDizi[j])
&& ((7-genler[i].degerNe())>=_referansDizi[j]))
_puan+=1;

else if ((genler[j].degerNe()==genler[i].degerNe()-_referansDizi[j])
&& ((genler[i].degerNe())>=_referansDizi[j]))
_puan+=1;*/
//System.out.println(“********”+i+” “+j);
if ((((IntGen)kromozom.lokustakiGeniGetir(j)).degerNe()==((IntGen)kromozom.lokustakiGeniGetir(i)).degerNe()+_referansDizi[j])
&& ((7-((IntGen)kromozom.lokustakiGeniGetir(i)).degerNe())>=_referansDizi[j]))
_puan+=1;

else if ((((IntGen)kromozom.lokustakiGeniGetir(j)).degerNe()==((IntGen)kromozom.lokustakiGeniGetir(i)).degerNe()-_referansDizi[j])
&& ((((IntGen)kromozom.lokustakiGeniGetir(i)).degerNe())>=_referansDizi[j]))
_puan+=1;

else _puan+=0;
}
}
kromozom.uygunlukDegeriniVer(_puan);
}

private void referansOlustur(int referansNoktasi) {
for (int i = 0; i < _referansDizi.length; i++) {
_referansDizi[i]-=referansNoktasi;
}
}

private void diziyiIlkle() {
for (int i = 0; i < _referansDizi.length; i++) {
_referansDizi[i]=i;
}
}
}

//Çaprazlama fonksiyonudur.
public class UniformTakasCaprazlama implements ICaprazlamaFonksiyonu{

private SoyutGen[] _yeniGenler=new IntGen[8];
private Random ran=new Random();
private int[] _kontrol={1,0,1,0,1,0,1,0};

public SoyutKromozom caprazla(SoyutKromozom anne, SoyutKromozom baba) {
int genSay=8;//anne.genSayisiniGetir();
for(int i=0;i<genSay;i++){
//int kontrol=ran.nextInt(2);
if (_kontrol[i]==1){
_yeniGenler[i]=(IntGen) anne.lokustakiGeniGetir(i).clone();
}
else
_yeniGenler[i]=(IntGen) baba.lokustakiGeniGetir(i);
}

SoyutKromozom kr=new Kromozom(_yeniGenler);
if (ran.nextInt(5)>2){
IKromozomMutasyon mF=new GenlerinYeriniRasgeleDegistir();
mF.mutasyon(kr);
}
return kr;
}
}

//Şimdi çalıştırma zamanı geldi.
public class SekizVezirMain {

/**
* @param args
*/
public static void main(String[] args) {
IntGen[] genler=new IntGen[8];
for(int i=0;i<8;i++){
genler[i]=new IntGen(i);
}
TekilRasgele.fabrikayiGetir().temelGenleriAyarla(genler);
//    Kromozom[] k=new Kromozom[3];
//    k[0]=KromozomFactory.fabrikayiGetir().genleriTekilOlanKromozomUret(“int”);
//    System.out.println(k[0].toString());
//    k[1]=KromozomFactory.fabrikayiGetir().genleriTekilOlanKromozomUret(“int”);
//    k[2]=KromozomFactory.fabrikayiGetir().genleriTekilOlanKromozomUret(“int”);

IUygunlukFonksiyonu uF=new SekizVezirUygunlukFonksiyonu();
/*    for(int i=0;i<3;i++){
uF.uygunlukDegeriHesapla(k[i]);
System.out.println(k[i].toString());*/
//    System.out.println(k[i].uygunlukDegeriNe());
//}
//System.out.println(“——-çaprazla———-“);
RasgeleNoktaCaprazla rF=new RasgeleNoktaCaprazla();
//SoyutKromozom kr=rF.caprazla(k[0], k[1]);
//System.out.println(kr.toString());
AbstractSecimFonksiyonu sF=new SabitDurumSecimi();
//sF.kromozomlariVer(k);
//sF.fonksiyonuCalistir();
//System.out.println(sF.enIyiKromozomuGetir().uygunlukDegeriNe()+” “+sF.enIyiKromozomuGetir().uygunlukDegeriNe());
IKromozomMutasyon mF=new GenlerinYeriniRasgeleDegistir();

Havuz havuz=new Havuz(5000,6,”kromozom”,”tekil”,”int”);
havuz.fonksiyonlariAyarla(uF, sF, rF, mF);
havuz.parametreAyarla(0.6, 0.1);
havuz.genetigiCalistir();
havuz.enIyiSonucuYazdir();
//System.out.println(k.uygunlukDegeriNe());
}

}

Advertisements

Tags: , ,

2 Responses to “Sekiz vezir Problemi ve Genetik Algoritmalar”

  1. aylin Says:

    Merhaba ,

    Kodunuzu inceledim ve TekilOmayanRasgele classı eksik olduğu için hata veriyor.Yardımcı olursanız çok sevinirim.İyi Günler.

    • mytkn Says:

      merhaba,
      kodları bulmam artık mümkün değil maalesef.
      en kısa zamanda yenisini yazacağım..
      isterseniz başka bir problem (diophantine denklemi) için yazdığım genetik kodlarını gönderebilirim..

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: