Author: emrahgumus

Elimizde bir labirent var, A noktasında B noktasına kendi yazacağımız Q-learning algoritması ile nasıl ilerleyeceğimizi ve hedefe varmak için en kısa yolu nasıl bulacağımızı bu ilk blog yazımda sizlerle paylaşacağım.

Q-Learning: Bir görevi en yüksek kazançla tamamlayabilmek için hangi eylemleri gerçekleştirmeleri gerektiğiyle ilgilenen bir makine öğrenme tekniğidir. Yani bir labirentte A noktasında B noktasına gitmek için birden fazla yol olabilir. Q-learning algoritması bize gidilebilecek en kısa yolu kazanç prensibine göre buluyor. 

Örnek olarak bu labirenti ele alalım. Bu labirentte başlangıç adresi 0,0 hedef adres 1,1 olsun burada bilinmesi gereken bu labirentin komşuluk matrisidir. Komşuluk matrisini de bizim çıkartmamız gerekiyor. Labirentin komşuluk matrisi de şu şekilde olacaktır:

Burada düğüm isimleri soldan sağa artacak şekilde ayarlanmıştır. örneğin 2. düğüm 2×2 lik matrisimizde 1,0 alanına denk gelmektedir. Buda resimde açıkça belirtilmiştir. Komşuluk matrisinde kaynak 0. düğümden hedef olarak seçtiğimiz 1. ve 2. düğüme geçiş olduğunu belirtmek için komşuluk matrisinde 0,1 ile 0,2 alanının değerini 0 yapacağız. Diğer bir yola bakacak olursak 1,0 dan 1,1 e geçiş olmadığı için komşuluk matrisinde kaynak 2 den hedef hedef 3 e geçişin olmadığını belirmek için komşuluk matrisinde değeri -1 dir. Programda bu alanları aşağıdaki gibi tanımlayacağız.

int[][] RMatrisi;
double[][] QMatrisi;
int baslangicDugumu = 0;
int bitisDugumu = 3;
int diziBoyutu = 0;
String dosyaYolu = "labirent2x2.txt";
int maxIteration = 0;

R matrisi iki boyutlu bir dizi olarak tanımladık. Fakat kaça kaçlık bir labirent üzerinde çalışacağımızı bu aşamada bilmediğimiz için sadece iki boyutlu dizi oluşturacağımızı belirtiyoruz. diziBoyutu değişkeni de toplamda kaça kaçlık bir labirent olacağını tutacak. Bu tanımlanmış değişkenleri global olarak tanımlamamız gerekiyor. Aksi taktirde sürekli fonksiyonlara bu değerleri gönderip geri almak zorunda kalacağız ki bu pek tavsiye edilen bir durum değil. En kolay yolu global olarak tanımlayıp istediğimiz zaman istediğimiz yerden erişebilmeyi mümkün kılmaktır. Komşuluk matrisini belirledik ama bu tek başına yeterli olmadığı için birde Q matrisine ihtiyacımız var bu matris bizim kazanç matrisimiz yani başlangıç adresimizden hedef adrese gidilen yolları tutacak. Şimdilik bu matrisle ilgili detaya girmiyorum yazının ilerleyen kısımlarında onu da anlatacağım. Şu an sadece gideceğimiz yolu tutacağını bilmemiz yeterli.

R matrisini, başlangıç ve bitiş düğümleri tanımladık şimdi ikinci adım olarak bu değişkenlerin içini doldurmaya geçelim. Komşuluk matrisini belirlemek için bir txt dosyasından faydalanacağız. Bu txt dosyasının içeriği şu şekilde:

1,2
0,3
1

Program içerisinden satır satır okumaya başladığımızda toplamda 4 satır okuduğumuzu anlayacağız. Bunu anladıktan sonra Math.sqrt() fonksiyonuyla satır sayısının karekökünü aldığımızda 2×2 lik bir matris olacağını anlayacağız. Bunu belirtmeliyim ki ele alacağımız labirentler daima kare olacaktır. Bu txt dosyasını okuyalım ve toplamda kaç satır olduğunu bulalım:

FileReader fileReader;
BufferedReader br;
fileReader = new FileReader(dosyaYolu);
br = new BufferedReader(fileReader);
while((br.readLine()) != null){
    diziBoyutu++;
}
br.close();

Kodun çalışması sonucunda diziBoyutu değişkeninin değeri 4 olacaktır. Dizi boyutunu öğrendikten sonra artık RMatrisi ve QMatrisi dizimizi tanımlayıp içlerini doldurabiliriz.

RMatrisi = new int[diziBoyutu][diziBoyutu];
QMatrisi = new int[diziBoyutu][diziBoyutu];
for (int i = 0; i < diziBoyutu; i++) {
    for (int j = 0; j < diziBoyutu; j++) {
        RMatrisi[i][j] = -1;
        QMatrisi[i][j] = 0;
    }
}

R matrisinin elemanlarını -1, Q matrisinin elemanlarını 0 yaptıktan sonra bitiş düğümünün belirlememiz gerekiyor. Bitiş düğümün değeri 100 olarak belirleyeceğiz.

RMatrisi[bitisDugumu][bitisDugumu] = 100;

Problemin ilk kısmını bitirdik ve tüm bu yaptıklarımız sonucunda artık kaça kaçlık bir labirentte ilerleyeceğimizi, başlangıç ve bitiş düğümlerimizin neler olduğunu biliyoruz. Tüm bunları parça parça ele aldık, şöyle bir toparlayacak olursak elimizde şöyle bir kod blogu olacaktır:

FileReader fileReader;
BufferedReader br;
try {
    fileReader = new FileReader(dosyaYolu);
    br = new BufferedReader(fileReader);
    while((br.readLine()) != null){
        diziBoyutu++;
    }
    br.close();
} catch (FileNotFoundException ex) {
    Logger.getLogger(MainForm.class.getName()).log(Level.SEVERE, null, ex);
} catch (IOException ex) {
    Logger.getLogger(MainForm.class.getName()).log(Level.SEVERE, null, ex);
}
RMatrisi = new int[diziBoyutu][diziBoyutu];
QMatrisi = new int[diziBoyutu][diziBoyutu];
for (int i = 0; i < diziBoyutu; i++) {
    for (int j = 0; j < diziBoyutu; j++) {
        RMatrisi[i][j] = -1;
        QMatrisi[i][j] = 0;
    }
}
RMatrisi[bitisDugumu][bitisDugumu] = 100;

Labirentin komşuluk matrisini oluşturmak için öncelikle komşuluk matrisinin olduğu dosyayı okuyup matris içerisinde yolları belirleyelim. Dosyadan okuma ve matrisi oluşturmak için YollariBelirle isminde bir fonksiyon tanımlayacağız.  Bu fonksiyon aşağıdaki resimde gördüğümüz komşuluk matrisindeki 1 lerin nerelerde olacağını belirleyecektir. Komşuluk matrisimiz ve fonksiyon içeriğimiz şu şekilde olacaktır:

public void YolariBelirle(){
    FileReader fileReader;
    BufferedReader br;
    try {
        fileReader = new FileReader(dosyaYolu);
        String line;
        br = new BufferedReader(fileReader);
        int x = 0;
        while((line = br.readLine()) != null){
            String[] parts = line.split(",");
            for(int n = 0; n < parts.length; n++) {
                int y = Integer.parseInt(parts[n]);
                if(y == bitisDugumu )
                    RMatrisi[x][y] = 100;
                if (x == bitisDugumu )
                    RMatrisi[x][x] = 100;
                if(x == bitisDugumu && y != bitisDugumu)
                    RMatrisi[x][y] = 0;
                if(x != bitisDugumu && y != bitisDugumu)
                    RMatrisi[x][y] = 0;
            }
            x++;
        }
        br.close();
    } catch (FileNotFoundException ex) {
        Logger.getLogger(MainForm.class.getName()).log(Level.SEVERE, null, ex);
    } catch (IOException ex) {
        Logger.getLogger(MainForm.class.getName()).log(Level.SEVERE, null, ex);
    }
}

Matriste yolları da belirledikten sonra en can alıcı noktasına ulaşmış bulunmaktayız. Bu matrisi bir fonksiyona sokacağız ve sonucunda bize Q (kazanç) matrisini oluşturacak.

public void yolBul(){
    int[] komsular = new int[diziBoyutu];
    for(int k = 0; k < maxIteration; ++k){
        Random rand = new Random();
        int start = (rand.nextInt(diziBoyutu) + 1) % diziBoyutu;
        int komsuSayisi;
        double max = 0;
        do{
            for(int t=0; t < diziBoyutu; ++t)
                komsular[t] = -2;
            int m = 0;
            for(int l = 0; l < diziBoyutu; ++l){
                if(RMatrisi[start][l] != -1){
                    komsular[m] = l;
                    ++m;
                }
            }
            komsuSayisi = m;
            int j = (rand.nextInt(diziBoyutu) + 1) % komsuSayisi;
            int index = komsular[j];
            m = 0;
            for(int t=0; t < diziBoyutu; ++t)
                komsular[t] = -2;
            for(int l=0; l < diziBoyutu; ++l){
                if(RMatrisi[index][l] != -1){
                    komsular[m] = l;
                    ++m;
                }
            }
            komsuSayisi = m;
            max = QMatrisi[index][komsular[0]];
            for(int y = 0; y < komsuSayisi; ++y){
                if(QMatrisi[index][komsular[y]] > max)
                    max = QMatrisi[index][komsular[y]];
            }
            QMatrisi[start][index] = (RMatrisi[start][index] + ( 0.8 * max ));
            start = index;
       }while(start != bitisDugumu);
    }
}

yolBul fonksiyonu çalıştığında başlangıçta rasgele bir düğüm belirliyoruz. Ardından bu düğümün komşularını belirleyip hangi komşuya gideceğimizi rasgele bir şekilde seçip o düğüme geçiş yapıyoruz. Bu her yeni düğüme geçildiğinde tekrarlanıyor ve hedef düğüm bulunduğunda 1 iterasyon tamamlanmış oluyor. Bu en dıştaki for döngüsünde k değeri maxIteration degerine ulaşana kadar devam ediyor. yolBul fonksiyonu çalıştıktan sonra Q matrisimiz aşağıdaki gibi olacaktır.

Algoritmayı yazıp çalıştırdık birde kullanıcı dostu olması açısından biraz da görsel birşeyler yapmamız gerekiyor. Ben en basitinden labirentin başlangıç ve bitiş düğümünü iterasyon sayısını alıp gidilen yolu ekranda çizen bir tasarım yaptım. Son olarak 6×6 bir matriste projeyi test edecek olursak ekran çıktıları aşağıdaki gibi olacaktır.

---

Uygulamayı düzenlediğim zaman yazıyı da güncelleyeceğim. Projenin GitHub adresini aşağıda paylaştım. Umarım faydalı olmuştur.

https://github.com/emrahgumus/java-q-learning-labirent.git