Genetik Algoritma ile Gezici Satıcı Problemi Çözümü (Travelling Salesman Problem with GA)

Genetik Algoritma Nedir?

Genetik algoritmalar, doğada gözlemlenen evrimsel sürece benzer bir şekilde çalışan arama ve eniyileme yöntemidir. Karmaşık çok boyutlu arama uzayında en iyinin hayatta kalması ilkesine göre bütünsel en iyi çözümü arar[1].

 

Genetik algoritmalar problemlere tek bir çözüm üretmek yerine farklı çözümlerden oluşan bir çözüm kümesi üretir. Böylelikle, arama uzayında aynı anda birçok nokta değerlendirilmekte ve sonuçta bütünsel çözüme ulaşma olasılığı yükselmektedir. Çözüm kümesindeki çözümler birbirinden tamamen bağımsızdır.

 

Genetik algoritmayı daha iyi anlamak için Gezgin satıcı problemi (Travelling Salesman Problem) üzerinde inceleyip açıklayalım.

Gezgin Satıcı Problemi

 

Bu problemde satıcı her şehre sadece bir kez uğrayarak turunu en kısa yoldan tamamlamak zorundadır. Satıcının başladığı şehre geri dönme zorunluluğu yoktur. Yani amaç verilen şehirler arasından en kısa yolu sağlayan turu bulmaktır.

 

Varsayalım satıcımız 8 şehir gezecek. Genetik algoritma kullanmadan en kısa yolu nasıl bulabiliriz?

Her şehre yalnızca bir kere uğrayacak ve bütün şehirleri gezecek ise 8 şehir için 8! farklı rota var demektir. (8! = 40320) Bu da demek oluyor ki biz en kısa rotayı 40320 farklı durumu kontrol ederek bulacağız. Diyelim bu sefer 10 şehir gezecek olsun. Bu seferde 3628800 farklı durumu kontrol etmek zorunda kalacağız. Yani Şehir sayısı arttıkça kontrol edilecek durumlar inanılmaz bir büyüklüğe ulaşacak demektir.

Bu tarz problemler için evrenden yola çıkarak genetik algoritma geliştirilmiştir. Genetik algoritma kesin olarak en kısa mesafeyi bulamayabilir. (Büyük olasılıkla bulamayacak) Fakat en yakın sonucu çok daha az zamanda bulacaktır.

Mesela 8 şehir için GA kullanarak 40320 adım yerine 120 adımda kesin çözüme optimum düzeyde yakın bir çözüm elde edilecektir.

Genetik algoritmasının akış şeması aşağıda verilmiştir.

flow

Genetik Algoritmayı Matlab’da kodladığımız Gezgin satıcı problemi çözümü için değerlendirelim.

 

 

1-KULLANICIDAN 8 ŞEHRİN KOORDİNAT BİLGİSİNİ AL.

Kullanıcıdan aldığımız her şehre 8’e kadar bir sayı ata.

İlk şehir ==>1…Son şehir ==>8

2- 10 ADET RASTGELE ŞEKİLDE SEÇİLMİŞ SIRALAMA BELİRLE

Her bir sıralama GA’da kromozom olarak adlandırılıyor.

Kromozom (1) = [1 4 6 7 2 5 3 8] … Kromozom (8) = [7 2 3 4 1 8 6 5]

 Her bir kromozomun içinde şehir bilgisi ise gen olarak adlandırılıyor.

3- RASTGELE BİR ŞEKİLDE KROMOZOMLARI ÇAPRAZLA

Rastgele seçilmiş iki kromozom çaprazlanıyor.

Çaprazlama için kromozomların son üç genini seçtik.

Çaprazlama sonucu kromozomlarda herhangi bir gen hiç bulunmayabilir ve dolayısıyla bir gen iki kere bulunabilir.

Bu bizim problemimize aykırı olduğu için tekrarlanan geni sırası ile dizilişte bulunmayan gen ile değiştiriyoruz.

dav

4- KROMOZOMLARI MUTASYONA UĞRAT

Çeşitliliği artırmak için yani en iyi sonuca ulaşabilme olasılığını artırmak için rastgele iki genin yerlerini değiştir.

5- İSTENİLEN POPÜLASYON SAYISI KADAR 3. ADIMDAN İTİBAREN TEKRARLA

Matlab Kodu

function z = distance(x,positions)
z =0;
for i=1:7
 
z = sqrt((positions(x(i),1) - positions(x(i+1),1))^2 + (positions(x(i),2) - positions(x(i+1),2))^2) + z;
 
 
end
 
 
end

clc;
clear;
close all;
distanceFunction = @(x,positions) distance(x,positions);
empty.kromozom.gen = [];
empty.best.kromozom = [];
empty.kromozom.distance = [];
empty.kromozom.best.distance = [];
best.distance = Inf;
empty.new.distance = [];
nKrom = 10;
 
%.M DOSYASININ BULUNDUĞU YERE HARİTA.JPG ATILARAK HARİTA ÜZERİNDEN ŞEHİRLER
%SEÇİLEBİLİR.
figure(1)
imshow('harita.jpg');
grid on
title('Detect 8 Cities for Travelling Salesman Problem ')
for i=1:8   % 8 ŞEHRİ HARİTA ÜZERİNDEN İNPUT OLARAK KULLANICIDAN AL.
 
    positions(i,:) = ginput(1);
    hold on
    plot(positions(i, 1), positions(i, 2), 'o','MarkerSize', 10)
    text(positions(i, 1), positions(i, 2), num2str(i),'FontSize', 24)
end
 
for i=1:nKrom % KROMOZOMLARI RASTGELE BİR ŞEKİLDE OLUŞTUR.
 
kromozom(i).gen = randperm(8);
kromozom(i).distance = distanceFunction(kromozom(i).gen,positions);
    if kromozom(i).distance < best.distance
        best.distance = kromozom(i).distance;
        best.kromozom = kromozom(i).gen; 
    end    
end
 
 
for pop=1:120 % POPULASYON SAYISI (TEKRAR SAYISI)
 
x = randperm(nKrom); 
 
for j=1:nKrom/2 % ÇAPRAZLAMA VE DÜZELTME İŞLEMLERİ
        temporary1 = kromozom(x(2*j-1)).gen;
        temporary2 = kromozom(x(2*j)).gen;
        kromozom(x(2*j-1)).gen([6 7 8]) = kromozom(x(2*j)).gen([6 7 8]);
        kromozom(x(2*j)).gen([6 7 8]) = temporary1([6 7 8]);
 
        for i=1:5
           for n=6:8
               u=1;
               v=1;
            if kromozom(x(2*j-1)).gen(i)== kromozom(x(2*j-1)).gen(n)
 
                for a=6:8
                      member = ismember(temporary1(a),kromozom(x(2*j-1)).gen);      
                        if (member == 0) && (u == 1)
 
                           kromozom(x(2*j-1)).gen(i) = temporary1(a);
                                    u = 0;  
                        end
                end
            end
 
            if kromozom(x(2*j)).gen(i)== kromozom(x(2*j)).gen(n)
 
                for a=6:8
                      member = ismember(temporary2(a),kromozom(x(2*j)).gen);      
                        if (member == 0) && (v == 1)
 
                           kromozom(x(2*j)).gen(i) = temporary2(a);
                                    v = 0;  
                        end
                end
            end
 
 
           end
        end      
 
 
end
 
 for i=1:nKrom %YENİ KROZOMLAR İÇİN MESAFE ÖLÇÜMÜ VE EN İYİ SONUÇLARI ATAMA
 
kromozom(i).distance = distanceFunction(kromozom(i).gen,positions);
    if kromozom(i).distance < best.distance
        best.distance = kromozom(i).distance;
        best.kromozom = kromozom(i).gen; 
    end    
 end  
 
 
 
 
 for i=1:nKrom % KROZOMLARI MUTASYONA UĞRATMA İŞLEMİ
 y = randperm(8,2);
 
 temp3 = kromozom(i).gen(y(1));
 temp4 = kromozom(i).gen(y(2));
 kromozom(i).gen(y(1)) = temp4;
 kromozom(i).gen(y(2)) = temp3;
 end
 
 
 for i=1:nKrom %YENİ KROZOMLAR İÇİN MESAFE ÖLÇÜMÜ VE EN İYİ SONUÇLARI ATAMA 
 
kromozom(i).distance = distanceFunction(kromozom(i).gen,positions);
    if kromozom(i).distance < best.distance
        best.distance = kromozom(i).distance;
        best.kromozom = kromozom(i).gen; 
    end    
 end  
 
        for i=1:7 % EN İYİ KROZOMU (ROTAYI) VE İLK KROMOZOMU GRAFİKTE GÖSTERİMİ
 
 
        h(i).graph=plot([positions(best.kromozom(i),1) positions(best.kromozom(i+1),1)], [positions(best.kromozom(i),2) positions(best.kromozom(i+1),2)],'LineWidth',4);
        %f(i).graph=plot([positions(kromozom(1).gen(i),1) positions(kromozom(1).gen(i+1),1)], [positions(kromozom(1).gen(i),2) positions(kromozom(1).gen(i+1),2)],'LineWidth',4);
        end
 
 
 title(['Population = ' num2str(pop) ',    Best Way = [' num2str(best.kromozom) '],    Best Distance = ' num2str(best.distance)])
 %title(['For Kromozom 1 ' 'Population = ' num2str(pop) ',    Actual Way = [' num2str(kromozom(1).gen) '],    Actual Distance = ' num2str(kromozom(1).distance)...
     %',    Best Way = [' num2str(best.kromozom) '],    Best Distance = ' num2str(best.distance)])
 
 ax = gca;
ax.TitleFontSizeMultiplier = 1;
 pause(0.10)
 
    if pop ~= 120
    for i=1:7
    delete(h(i).graph);
    %delete(f(i).graph);
    end
    end
 
 
 
end   
 
% BU KISMI KULLANARAK 8!=40320 AŞAMAYI KONTROL EDEREK GERÇEK EN KISA MESAFE BULUNABİLİR.
%GA SONUCU İLE GERÇEK EN KISA MESAFE SONUCU KARŞILAŞTIRILABİLİR.    
% b = [8 7 6 5 4 3 2 1];
% p = perms(b);
% bestt = Inf;    
% for i=1:40320
% 
% new(i).distance = distanceFunction(p(i,:),positions);
%     if new(i).distance < bestt
%         bestt = new(i).distance;
%         bestpos = p(i,:); 
%     end    
% end     
%

Aşağıdaki videolarda çözümün grafik üzerinde gösterimi bulunmaktadır.

 

Matlab Kodu için ==>

https://drive.google.com/open?id=1DyVmLnEL6rAXOXkVYXibboOcfPYUK_0D

GA hakkında daha detaylı bilgi için ==>

http://www.horozerk.com/wp-content/uploads/genetic.pdf

 

Bir Cevap Yazın

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.