Genetik algoritma ile Gezgin satıcı Problemi (Traveling Salesmen Problem with genetic algorihtm)

Genetik algoritma ile Gezgin satıcı Problemi (Traveling Salesmen Problem with genetic algorihtm)..

Piyasada çok az bir örneği bulunan bir konuda sizlere 2 haftamı, programın yazımı için verdiğim çalışmam hakkında bilgi vermek istiyorum ben en son 370 Şehirle bu uygulamayı denedim. Yakında açık kaynak kodları ile sitemde yayınlayacağım.Bu uygulamada ekranda kullandığım İmagePalet yani noktaları koyduğum  ekranı bir sitede compenet olarak aldım.Ekranın herhangi bir  noktasının pixel olarak kordinatlarını bir fonksiyonun parametresi olarak vermktedir.Sizin yapmanın gereken sadece diğer 2. noktanın kordinatlarını alıp iki pixel arası uzaklığı bulmak.

Sonrası zaten genetik algoritmanın işi. Her bir nokta yeni bir şehir..Ve değişik varyosyonlarla toplam en kısa yolu bulan bir çalışma…Ben çok sevdim sanki bir oyun gibi :=)  Umarım sizde begenirsiniz..

Yapmanız gereken ekranın çeşitli yerlerine nokta koymak mouse ile ve bilgisayarınız iyi bir configrasyona sahip değilse 300-350 şehrin (Ekrana koyulan Nokta adedi )üzerine çıkmanızı tavsiye etmiyorum.Ama sonuçlarını çabuk görmek istiyorsanız yakın , bi kaç tanede uzak yerlere nokta koyun ve başla butonuna basınız. Ekranda Son jenarasyon ve devamlı azalan kısa yol mesafesi gözükmektedir.Durdurmadan temizle butonuna basmayın çünki hata mesajı vermektedir.

NOT : Uygulama C# da yazılmışdır..Sisteminiz de FrameWork Kurulu olması gerekmektedir. Framework 3.5 Önerilen versiyondur.

GEZGİN SATICI PROBLEMİ

Seyyar satıcı problemi, en önemli algoritma problemlerinden biridir. NP-Tam olan problem şu şekildedir:

  • Bir seyyar satıcı var
  • Bu satıcı, mallarını şehirde satmak istiyor
  • Öte yandan, mantıklı bir şekilde, bu satıcı bu şehirleri mümkün olan en kısa şekilde ve her bir sehire maksimum bir kere uğrayarak turlamak istiyor

Problemin amacı, satıcıya bu en kısa yolu sunabilmektir. Basit bir şekilde:

  • İlk şehirde, satıcının değişik şehir arasında seçim hakkı vardır
  • İkinci şehirde, satıcının değişik şehir arasında seçim hakkı vardır
  • vs.

 

Dolayısıyla, sonuç olarak satıcının değişik tur arasından seçim hakkı olacaktır. Bu, 100 şehirlik bir tur için bile değişik tur etmektedir!

Su an itibariyle, bulunabilmiş en güçlü kesin cozum sunan algoritma (Dinamik Programlama)ile zamanda çözülebilmektedir. Mesela, 100 şehirlik bir tur için bu adım etmektedir.Bugüne kadar çözülen en büyük seyyar satıcı problemi 24,978 noktalıdır ve İsveç‘te yerleşimi olan her nokta için çözülmüştür. Bu çözüm, Intel Xeon 2.8 ghz bir işlemcinin 92 yılına denk bir sürede yapılmıştır (öte yandan, 96 bilgisayarlı bir ağ üzerinde çözüldüğünden çözülmesi 3 yıl sürmüştür). Şu anda çözülmeye çalışılan en büyük problem Dünya üzerinde kayıtlı yerleşim olan her nokta için en kısa yolun ne olduğudur. Bu problem 1,904,711 şehir içermektedir.

 

Bu problem, seyyar satıcılardan öte internet üzerinde paketlerin yönlendirilmesi gibi konuların çözümünde de faydalı olacağından önemli bir problemdir.Gezgin satici problemi, do rusal olmayan, kombinatoriyel bir optimizasyon problemidir.

Bir satıcı elemanının, ya da bir aracın belli bir noktadan başlayıp, tüm noktalara ya da

merkezlere uğradıktan sonra yine ayni noktaya, toplam mesafeyi en az kalacak şekilde

dönmesi eklinde tanımlanabilir. Düğüm olarak da adlandırılan noktaların sayısı (n)

problemin boyutunu, diğer bir ifadeyle değişken sayısını göstermektedir. Probleme ait tüm

mümkün çözümlerin sayısı (n-1)!.dir. Konuyla ilgili olarak Taha (2000) ve Timur

(2001).un eserlerine bakılabilir.

 

Düğüm sayısı arttıkça çözüm alternatifi sayısı üssel olarak artmakta ve problem,

deterministik yöntemlerle daha çözümü zor hale gelmektedir. Bu durumda devreye sezgisel yöntemler girmektedir. Geliştirimi birçok sezgisel GSP problemlerinin çözümünde kullanılmıştır. Bunlara örnek olarak genetik algoritma (Potvin, 1996), yapay sinir aglari

(Potvin, 1993), benzetilmi tavlama (Aarts ve di erleri, 1997), karinca kolonisi algoritmasi (Dorigo ve Gambardella, 1997) verilebilir. Bu çali mada popülâsyon temelli gelişim algoritmalarından olan diferansiyel gelişim algoritmasi GSP probleminin çözümünde kullanılmıştır.   

 Bir gezgin satıcı,

 n  s tane salkımlı n düğümlü bir serimde

n  bir başlangıç noktasından başlayıp,

n  her salkımdan bir düğüme sadece bir defa uğrayıp,

n  başladığı yere dönmek durumunda

n  uğrayacağı yerlerin sıralarını belirlerken, kat edeceği toplam mesafenin veya yapacağı harcamanın en küçük olmasını ister.

            Bu tür problemlere Genelleştirilmiş Gezgin Satıcı Problemi denir.

 

Gezgin Satıcı Problemi (Traveling Salesman Problem) veya kısaca GSP (TSP), aralarındaki uzaklıklar bilinen N adet noktanın (şehir, parça veya düğüm gibi) her birisinden yalnız bir kez geçen en kısa veya en az maliyetli turun bulunmasını hedefleyen bir problemdir.

 

UYGULAMA YERLERİ

Ø  GSM operatörlerinin baz istasyonlarının yerleşim yerlerinin belirlenmesi problemi

Ø  GSP bir alt problem olarak birçok ulaşım ve lojistik uygulamalarında ortaya çıkmaktadır.

Ø  Malzeme akış sistem tasarımı

Ø  Posta kutusuna dağıtım problemleri

Ø  Araç Rotalama Problemleri

Ø  Depolardaki vinç güzergâhlarının programlaması

Ø  Stok alanındaki malzeme toplama problemleri

Ø  Uçaklar için havaalanı rotalaması

Ø  Elektronik devre tasarımı

 

GSP ÇÖZÜM YÖNTEMLERİ

Kaba kuvvet arama yöntemi ile doğrudan tüm permütasyonların toplam yol uzunluklarının hesaplanması ve en küçüğünün

bulunması şeklinde çözülebilmekle birlikte, N’in büyük değerleri için permütasyon sayısı N! büyük değerlere ulaşacağından,bu işlem çok uzun zaman almaktadır. 

 Genetik Algoritmalar, Karınca Kolonisi Optimizasyonu, Yerel Arama yöntemleri (2opt, 3opt) gibi sezgisel veya yaklaşıma dayalı çözümler veren yöntemler ise, makul bir sürede en iyi ya da en iyiye yakın sonuçlara ulaşılmasını sağlarlar.

GSP’NİN ÖNEMİ

 

Bilgisayar mühendisliği müfredatında algoritmalar, veri yapıları, ayrık matematik, optimizasyon, yapay zekâ gibi birçok derste bu probleme ve çözüm yöntemlerine değişik bakış açıları ile değinilmektedir.

Çözümü ise, yol planlama (uçak, otobüs, dağıtım kamyonları, bilgisayar ağları, posta taşıyıcılar, vb.), iş planlama, baskı devre kartlarındaki delgi işlemi sırasının belirlenmesi gibi birçok alanda kullanılmaktadır.

 

 UYGULAMA

gezgin-sataca-problemi (Programı Bu link’ en indirebilirsiniz )

 4 

Şekil Programın İlk açılışı…

 

Bu ekranda ilk açılan sayfa boş gelir ve son jenerasyonumuzun sayısı, Son turun uzunluğu ve kaç adet şehirler bu değerler ve yol bulundu bu gibi bilgiler yer almaktadır. Ekranın beyaz kısımlar üzerinde Mouse yardımı ile basılarak şehirler oluşturulur.

  

Oluşturulan bu şehirlerin adedi ekranda gözükmektedir. Bu işlemden sonra başla butonuna basarak program çalıştılırılır ve yukarda anlattığımız TSP çözüm yöntemleri ile ilk yol çizilir. Daha sonra en kısa yol bulunana kadar.Bu işlem devam eder.

  

  İlk sonuçlar.. 

 

 

 

2
2

   Daha kısa bir yol..

Artificial İntelligent, Dersler, Genetik Algoritma, TSP-Gezgin Satıcı | 23.02.2009 15:01 | 22 Comments

22 Comments on “Genetik algoritma ile Gezgin satıcı Problemi (Traveling Salesmen Problem with genetic algorihtm)”

comments rss | trackback url

Ethem YAPAR

Merhaba,
Bilgisayar tek. bilişim sistemleri 3. sınıf öğrencisiyim. Tatile gitmek siteyen birisi için en kısa yolu bularak gideceği yere en kısa yolla gitmesini sağlayacak bir C# Uygulması yazmaya çalışıyorum.
Ama hangi algoritmayı kullanacağımı bulamadım, zorlandım :)
Makalenizi çok beğendim emeğinize sağlık.
Nasıl yapabilirim? hangi algoritmayı kullanabilirim?
Şehirler arası mesafeleri databaseye aktardım bun verileri nasıl kullanabilirim?
yardımcı olursanız çok sevinirim.
İyi calışmalar.

13.08.2009 1:03

Mevlüt ALTUNTERİM

Merhaba.. Kusura bakmayın.. Şehir dışında olduğum için şimdi vakit buldum sorunuzu cevaplamaya…Algoritma olarak TSP algoritmalarından birini kullanabilirsiniz.Databasedeki verilerinizi nokta kriteri olarak belirleyip her biri için bir puanlama sistemi ile en yüksek puanlı nokta, ilk tercih olucak şekilde TSP yi çalıştırabilirsin.. Bu konulara bakarsan soruna cevap bulabilirsin..

21.08.2009 4:46

gulsah muslubas

merhaba mevlüt bey
yapmış olduğunuz projenin UML diagramı varmı sizde.
iyi çalışmalar…

9.03.2010 12:09

ali

hocam elinize saglik . kodlari da vereceginizi yazmissiniz . buna benzer bir projem var da . cok yardimci olursunuz kodlari verebilirseniz.

23.03.2010 15:37

burak arslan

hocam eline koluna sağlık çok iyi bir program olmuş ben karabük üniversitesinde pc sis öğr okuyorum hocamız bizden proje olarak bir tüpçü programı istedi ve genetik algoritma kullanmamızı istedi fakat küçük bir sorun var adam hiç bu konuyu anlatmadı senden ricam bu programın kodlarını yada başka bir programın genetik algoritma programı paylaşabilirsen çok mutlu olurum kalıp geçmem bu projeye bağlı

1.06.2010 1:36

burcu

merhaba Mevlüt Bey;
Birinci sınıf öğrencisiyim. Hocamızda buna benzer bize bir ödev verdi. Sizde bu dinamik gezgin satıcı probleminin kodları varsa benim e-mail adresime en kısa zamanda yollayabilirmisiniz.
İyi Çalışmalar.

1.06.2010 3:10

laz53

slm mevlüt bey..Sizin gezgin satıcı programınıza baktım.Ya bende bunun aynısına benzer bi proje yapıyorum..Ama bi türlü genetik algoritmayı çözemedim. Ya bana bu programın kodlarından yardımcı olurmusun şimdiden çok saolun.

1.06.2010 11:16

Mevlüt ALTUNTERİM

Merhaba tabiki yardımcı olabilceğim birşey varsa elbette…Bana mail adreslerimden ulaşabilirsiniz..

8.06.2010 9:47

seda

merhaba hocam birinci sınıf öğrencisiyim. Hocamızda buna benzer bize bir ödev verdi. Sizde bu dinamik gezgin satıcı probleminin kodları varsa benim e-mail adresime en kısa zamanda yollayabilirmisiniz.

18.06.2010 4:32

Ahmet Ozer

Merhaba Mevlüt Bey,

Bu genetik algoritma ile ilgili bir proje üzerinde çalışmalarım var. Ancak çok fazla c# deneyimim yok. Sizin çalışmanızı referans olarak almak için source code u benimle paylaşmanızı istesem uygun olur mu?

Teşekkürler,
Iyi gunler…

7.07.2010 10:43

eylül yıldız

Merhaba Mevlüt Bey,
Ödevimin konusu olan GSP de başarılı çalışmanızdan yararlanmak istiyorum yanlız kodlar ve paralel algoritması gerekiyor hiç bir yerde bulamıyorum yardımcı olabilir misiniz?

20.11.2010 20:07

ezgi

Bu makeleyi çok önceden yazmışsınız fakat internetteki en iyi uygulamalardan diyebilirim.Rica etsem kodlarını mailime gönderebilir misiniz?

20.12.2010 6:03

mehmet evcan

hocam ben bilgisyarlı matematik 4.sınıf öğrencisiyim bu bizim profe konumuzu projeler geçti sınavlar başlayacak hoca dinamik dizi soracağım dedi bunun gelme ihtimali olabilir bu programın dinamik dizi ile oluşturulmuş kodları varsa bana mail ile yollayabilirmisiniz?

29.12.2010 17:59

Ceylan

Merhaba Mevlüt Bey. Çok güzel bir çalışma. Bu çalışmayı referans alarak bu konuda kendimi geliştirmek istiyorum. Acaba kaynak kodlarını göndermeniz mümkün mü? Yardımcı olabilirseniz sevinirim. Teş. Edr.
ceylan_akde@yahoo.com

26.02.2011 14:38

Hasan Güney

Merhaba Mevlüt Hocam,

Hocamız bu konuda ödev verdi.İnternetten 15 gündür araştırıyorum.Ancak sizinki kadar açık bir uygulama bulamadım.Kaynak kodları göndermeniz mümkünmüdür?Saygılarımla

31.03.2011 9:57

cigdem

merhaba hocam
bu konuyla ılglı bir ödev üzerinde calışıyorum eger mümkünse bu calısmanızın kodlarını yollayabılırmısınız.kendime calısmanızı referans almak istiyorum

27.11.2011 15:50

Deniz

İnanılmaz beğendiğim bir çalışma olmuş.Hocamız yapay zeka dersinde anlattı kodlarını yazın dedi.Kodları denedim bazı mantıksal hatalarla karşılaşıyorum rica etsem kodları mail adresime gönderebilir misiniz?

14.03.2012 19:03

Berk

İyi günler ben de bu konu hakkında çalışma yapıyorum ama yazdığım kodda her halde belirli hatalar var ki sizin programınız kadar iyi çalışmıyor rica etsem kaynak kodlarınızı gönderebilir misiniz?

20.04.2012 8:17

semih

hocam merhabalar.
herkes gibi bende sizden genetik algoritma ödevim için kodu isteyecektim yardımcı olursanız sevinirim. teşekkürler…

5.08.2012 1:31

ali

Merhabalar, bu konuyla ilgili bir ödev üzerinde çalışıyorum. Yazdığınız kodları mail adresime gönderebilirmisiniz

21.11.2012 12:51

Ahmet

Hocam merhaba, bir ödevim için yazmış olduğunuz kodlara ihtiyacım var. Gönderebilirmisiniz? Şimdiden teşekkürler.

24.12.2012 14:20

seren

selam bna yaptıgınız calısmaların kodları gerek kendm yapamıyorm programa uyarlayamıyorum teslım etmem gerekıyor pazartesı yardımcı olur musunuz.

2.03.2013 9:58

Leave a Reply