Yldz Ver! ⭐

Probleminizin zmn renmek veya zm balatmak iin bu projeyi beendiyseniz veya kullanyorsanz, ltfen ona bir yldz verin. Teekkrler!

TezRota

Proje Konusu ve Kullanc Etkileimi

Problem seti iinde belirtilen koordinat dzleminde tanml 20 adet noktann balang noktas fark etmeksizin kendi ierisinde en ksa uzunlua sahip olacak ekilde rotalanmas ilemini gerekletirmektir.

• Rotalanmas istenen nokta says 20 olarak belirlenmitir ancak, bu nokta says esnektir. Nokta
  says artrlabilir ya da azaltlabilir.
• Proje konusu aslnda, gezgin satc problem modelidir.
  Rotalama ilemi yaplrken, kyaslama ilemi n plana alnmaya allmtr. Bunu salamak iin
  kullanlan sezgisel yaklamlar birden fazla tutulmutur. Ayrca sezgisel yaklamlarn almas iin
  gereken parametre deerleri sabit tutulmam ve kullancdan alnabilecek ekilde tasarm yoluna
  gidilmitir.
  Kullancya sunulan tek bir ekran vardr. Kullanc bu tek ekrandan parametre ayarlamalarn yaparak
  bir tane zm yntemi seer ve zm srecini balatr. stenen parametreler kullanlacak olan sezgisel
  yaklamn ihtiyalarna gre scaklk, iterasyon says gibi inputlarla ekillenir. Bu parametreler iin
  varsaylan deerler tanmlanmtr.

Kullancdan stenen Parametreler ve Varsaylan Deerleri

a) Scaklk-100 b) terasyon -1000 c) Scaklk Azaltma Oran-0.99 d) Tabu Liste Uzunluu-3 e) Komuluk Says-12

Ekrann sol st kesinde zaman bilgisi gsterimi yaplmtr. Oluturulan rotann toplam mesafesine gre kullancdan alnan hz deeriyle, rotann ne kadar srede tamamlanaca kullancya sunulmutur. rotalama ileminin zm sresi ve rotann sral dizilimi ekranda gsterilmektedir. zm sresi, yalnzca algoritmann zm sresini ifade etmektir.

Gezgin Satc Problemi Hakknda Bilgi

Problem de ama, bir satcnn bulunduu ehirden balayarak her ehre sadece bir kez uradktan sonra balad ehre dnen en ksa turu bulmaktr. ehirler aras gidii ku bak olarak kabul edersek aadaki rnek koordinat gsterimi ile problem tam olarak anlalacaktr.

Kullanlan zm Yntemleri

Rotalama ileminin yaplabilmesi iin iki tane sezgisel yaklamdan yararlanlr. Bunlar: tavlama benzetimi ve yasakl arama yntemleridir. Her iki yntemide kyaslayarak zm sonucunda kalite artrm ve zm sresinin ksalmas hedeflenmitir. Ancak hedeflerin tam olarak gerekleebilmesi iin kullancnn girdi parametrelerini doru ekilde ayarlamas gerekmektedir. rnein 20 noktay rotalamak iin yasakl arama yntemi alrken tabu listesi uzunluunun 40 olmas zm srecine bir fayda salamaz ya da tavlama benzetimi kullanrken scaklk azaltma orannn 1 olmas retilen komuluk saysn azaltacak ve boltzman sabiti ile kurulu rassall olumsuz etkiler ve bir sre sonra lineer arama formuna dnebilir.

Tavlama Benzetimi le zm Yaklam

Tavlama, malzemeyi belirli bir sre (tavlama scaklna kadar) sttktan sonra, yava yava soutmaktr. Tavlama malzemeyi rahatlatmak, yumuatmak ve i yapy daha kullanlabilir hale getirmek iin yaplan sl ilemlerin geneline verilen addr.Tavlama Benzetimi, ni Algoritmasnn (Descent Algorithm) iyiletirilmi halidir.

ni Algoritmas

• Rasgele seilen bir zm ile aramaya balanr.
• Komu zm oluturulur ve ama fonksiyonundaki deiim hesaplanr.
• Eer ama fonksiyonunda azalma sz konusu ise (minimisazyon problemi iin), komu zm mevcut zm olarak kabul edilir.
• Bu sre, ama fonksiyonunda mevcut zmn hibir komusu iyileme salamayana
  kadar devam eder ve algoritma yerel bir eniyi (local minimum/maximum) ile sonlanr.

Tavlama Benzetiminde, ama fonksiyonunda arta neden olabilecek komu hareketler bazen kabul edilerek yerel en iyi noktalarndan kurtulmak mmkndr. Ama fonksiyonunda arta neden olabilecek bu komu hareketin kabul edilip edilmemesi, rassal olarak belirlenmektedir.[1]

Yasakl Arama Yntemi le zm Yaklam

Tabu Arama Algoritmas, optimizasyon problemlerinin zm iin F.Glover tarafndan gelitirilmi iteratif bir aratrma algoritmasdr. Temel yaklam, son zme gtren admn dairesel hareketler yapmasn nlemek iin bir sonraki dngde tekrarn yasaklanmas veya cezalandrlmasdr. Bylece yeni zmlerin incelenmesiyle Tabu Arama algoritmas, blgesel en iyi zmn daha ilerisinde bulunan zmlerin aratrlabilmesi iin blgesel-sezgisel aratrmaya klavuzluk etmektedir. Tabu Arama algoritmasnn blgesel optimallii amak amacyla kulland temel prensip, deerlendirme fonksiyonu tarafndan her iterasyonda en yksek deerlendirme deerine sahip hareketin bir sonraki zm oluturmak amacyla seilmesine dayanmaktadr. Bunu salamak amacyla bir tabu listesi oluturulur, tabu listesinin orijinal amac nceden yaplm bir hareketin tekrarndan ok tersine dnmesini nlemektir. Tabu listesi kronolojik bir yapya sahiptir ve esnek bir hafza yaps kullanr. Tabu arama algoritmas her ne kadar istenmeyen noktalarn iaretlenmesi olarak aklanm olsa da daha cazip noktalarn iaretlenmesi olarak ta kullanlr. Yasakl armay aklamak iin aadaki gibi bir gsterimden yararlanlabilir:

Yukardaki ifadeyi aklarsak; ama fonksiyonu c(x) maliyet veya kar fonksiyonun en kk veya en byk deerin aranmaktadr fakat bu aramada x vektr ile belirtilen kstlamalara uyularak zme ulalacaktr. Baka bir ifade ile her x eleman bir hareketi temsil eder ve tm hareketler X ile gsterilmektedir. Ancak daha doru bir varsaym x vektrlerinin TA bellek yaps olarak kullanlddr. Bylece vektrde tutulan bellek deerine bal olarak zm aramada baz hareketler tabu olarak kabul edilip engellenecek, bazlarna ise daha fazla odaklanacaktr. X vektrndeki her bir hareket ise mevcut zmn bir komusunun seimini temsil eder.

zm Yntemlerinin Projede Kullanm

Tm zm yntemlerinin kullanm srecinde, kullanc varsaylan deerleri deitirerek zm srecine yn verebilir. Kullancya uygulama ilk kez altrldnda, rastgele oluturulmu bir balang zm verilir. Bu zm zerinde rota aratrmas yaplr. Tavlama benzetimi iin varsaylan deerler: Scaklk azaltma oran 0.99, scaklk 100 ve iterasyon deeri 1000 olarak belirlenmitir. Kullanc ilk zm isteini gerekletirdiinde, rastgele olarak retilmi olan balang zm zerinden aratrma yaplmaya, komuluk retimine balanr. Ancak kullanc, uygulamay kapatmadan, birinci zmden elde ettii sonucun akabinde yeniden bir tavlama benzetimi yntemiyle zm aratrma istei verirse uygulamaya, uygulama balang olarak ilk istein rettii sonucu balang zm olarak kabul eder ve aratrmasn bu zm zerinden devam ettirir. Her istein ardndan retilen zmde oranna dikkat edilmeksizin iyiye gitme olduu gz nne alnrsa, tavlama benzetimi kullanlarak yaplan ard arda isteklerin merdiven etkisiyle daha da iyi sonulara gidecei sylenebilir.

Yasakl arama ynteminde, balang zm her zm istei alndnda rastgele olarak yeniden oluturulmutur bu sebeple yukarda bahsi geem merdiven etkisini yasakl arama yntemi kullanlan isteklerin zm sonularnda grmek mmkn deildir.

Yasakl arama yntemi kullanrken dikkat edilen en nemli nokta tabu listesinin uzunluudur. Rotalama iin kullanlan nokta says varsaylan olarak 20 adettir ancak bu boyut artrlabilir ya da azaltlabilir. Bu sebeple 4 adet nokta iin 5 adet tabu liste boyutu vermek doru bir yaklam deildir. Belli bir zm sresinden ya da iterasyon saysndan sonra uygulamann srarla ayn sonucu en iyi zm kabul etmesi durumu gz nnde bulundurularak, 10 000 iterasyonda bir tabu listesinden bir eleman karlmtr.

Nokta Tanmlamas

Uygulama rotalama ilemini yapabilmek iin temelde nokta tanmlamasna ihtiya duyar. Nokta tanmlamasnda dzlem, x y koordinat sistemi eklinde modellenmitir ve noktalar bu dzlemde konumlandrlmtr.

Her noktann konum bilgisi ondalkl saylar olarak, 15.6 inclik bir bilgisayarn ekran boyutlar gz nne alnarak statik olarak verilmitir. Ancak nokta tanmlamas yaplrken yalnzca koordinat bilgisi kayt altna alnmamtr. Her nokta iin aada belirtilen deerler tanmlanmtr.

• sim

• znitelik numaras

• Koordinat bilgisi

• Gei yapabilecei noktalar kmesi bilgileri tutulur.

Gei yaplabilecek noktalar kmesinin zm sresi boyunca noktann yannda tanmasnn sebebi, programlama asndan okuma yazma ileminin ok maliyetli olmas sebebiyledir. Her noktann koordinat deerleri bir kez okunur ve hafzada tutulur.

Kromozom ve Komuluk Tanmlamas

zm srecinin en nemli aamasndan biri de kromozom yapsdr. Kromozom noktalardan oluan sral bir kme olarak modellenmitir. Noktalarn kromozom zerindeki sralamas, soldan saa doru gei ynn ifade eder.

a) Kromozom noktalar kmesinden olutuu iin, kromozom kendi iinde her noktann koordinat, isim, numara ve gei yaplabilecek noktalar kmesi deerlerini yannda tar. Dolaysyla bir kromozom retildikten sonra yaplmas gereken tek ey o kromozom zerinde toplam mesafe maliyetinin hesaplanmasdr.

b) Tavlama benzetiminde her iterasyonda bir adet komuluk retilmitir.

c) Yasakl arama yaklamnda her iterasyonda komuluk says parametresi kadar komuluk retilmitir.

d) Aslnda her bir kromozom linked list yapdadr. Kromozomu oluturan noktalar rota sral tanmland gibi fiziksel hafzada sral ekillerde tutulurlar. Bu yntem programlama asndan fayda salamtr.

e) Her komuluk bilgisi rota ve mesafe maliyeti bilgisini tar.

Yasakl arama ynteminde komuluk kmesi kullanlmtr. Bu kme kromozomlardan olumaktadr. Kromozomlar zerinde rastgele takas ilemi yaplarak komuluklarn retilmesi salanr. Komuluk yaps list veri yaps eklindedir. Bu yapy dz bir liste yapmak gibi dnebiliriz. Ancak komuluk kmesinde hesaplama ilemi yaparken rastgele bir yaklam deil sral bir seim ilemi yaplmtr. Komuluk kmesinde bulunan kromozomlarn mesafe maliyeti, kmede bulunduu sraya gre hesaplama ilemine tabi olmutur.

Balang zmnn Oluturulmas

Toplam mesafesi hesaplanmak istenen noktalarn belirlenmesinin ardndan balang zmnn oluturulmas aamasna geilir. Hesaplanmak istenen btn noktalar bir torbaya atlm gibi dnlr ve torbadan rastgele olarak srasyla seim yaparak kromozom yapsna nokta eklemesi yaplr

Rotann Mesafe Maliyetinin Hesaplanmas

Her iki zm yntemi iin ortak olan aama, oluturulan rotann mesafe maliyetinin hesaplanmas ilemidir. Rotay oluturan nokta tanmlar xy koordinat dzlemin esas alnarak modellenmitir. Bu sebeple klit forml kullanlarak iki nokta arasndaki mesafe hesaplanmtr. Sonrasnda rota iinde bulunan tm mesafeler toplanarak, toplam mesafe maliyeti elde edilmitir.

• klit formlnn proje ierisinde C# programlama dili kullanlarak uygulanmas

Yasakl Hareketin Kontrol

Yasakl arama algoritmasnn alma mekanizmasnda esas ama baz hareketlerin tekrarlanmasn nlemektir. Tabu listesinin boyutu ald durumda FIFO kural uygulanr. Tabu listesine giren ilk hareket tabu listesinden karlr ve yasakl olmaktan kurtulur. Programlama aamasnda fark edilmitir ki A noktasnn B noktasyla yer deitirmesi demek ayn zamanda B noktasnn A noktasyla yer deitirmesi anlamna gelmektedir. Bu sebeple yalnzca A-B yer deitirmesi durumu deil ayn anda B-A yer deitirmesi olayda kontrol edilmitir.

• Tabu hareket kontrolnn C# programlama dili kullanlarak kontrol edilmesi

Programn alma Admlar

Programn almas sral ilemlerin uygulanmas eklinde tanmlanmtr. Kullancnn mdahalesi yanzca sezgisel yntemin seilmesi ve seim yaplan bu ynteme ilikin parametre ayarlarnn yapld ksmdr. Kullanc parametre ayarn yapmasa dahi seilen aratrma yntemi varsaylan parametrelerle alacaktr. Programn alma admlar srasyla aadaki gibidir.

a) Program ierisinde hard-code olarak tanml 20 nokta kullanlarak problem denen noktalar kmesi tanmlanr. Bu tanmlama noktalarn isim, numara ve koordinat bilgilerinin belirtilen CityPoint snf ierisinde kurall ekilde yazlmas ilemidir.

Nokta bilgilerinin nesnelerle temsil edilmesinin ardndan, rastgele olarak balang zm oluturulur.

c) Oluturulan balang zm kullancya grafiksel arayzle ve string sral gsterimiyle sunulur.

d) Kullanc, arayz araclyla parametre deiimi yapmaz ise seim yapt sezgisel yntem, program ierisinde yine hard-code olarak tanmlanm olan varsaylan deerlerle zm arama srecini balatlr. Parametreleri deitirmesinin ardndan yine bir sezgisel arama yntemi seerek, kullanc zm arama srecini balatr.

e) zm arama srecinin tamamlanmasnn ardndan, bulunan iyiletirilmi rota kullancya grafiksel arayzle ve string sral gsterimle sunulur. Ayrca kullancya zm sresinin ne kadar olduu ile ilgili anlalr formatta bilgilendirme yaplr.

Programn alma Performansn Artran lemler

Programn, nokta tanmlamas, rota belirlenmesi ve kabul edilebilir bir rota dzenlemesinin gerekletirimi yaparken alma sresinin katlanlabilir olmas gerekmektedir. Ayrca bulunan zmn kullancya anlalr ekilde sunulmas da nemli bir durumdur. Bu amalar iin yaplan ilemleri aadaki gibi sralanmtr.

a) Her iki sezgisel aratrma yntemi iin ortak olan fonksiyonlar statik snflarda tanmlanmlardr. rnein, zm sresi her iki yntem iin kullancya belli bir formatta sunulmutur. Bu formatn tanmlamasnn yapld method statik olarak tanmlanmtr.

b) Bir noktann dier noktalara olan gei matris bilgisinin her hesaplama ileminde okunmas tercih edilmemitir yalnzca bir kez okuma ilemi yaplmtr.

c) Her iki sezgisel aratrma yntemi ayn problemin noktalarndan bir rota hazrlamaya alt iin, problemin oluturulduu blm statik snf ierisinde tanmlanmtr.

d) Kullancnn bulunan rotay doru ekilde anlayabilmesi iin, noktalar aras geiler oklarla gsterilmitir. Bu ekilde bir string format hazrlanm ve kullancya sunulmutur.

e) Rotann kullanc tarafnda net gzlemlenebilmesi iin, noktalar arasndaki mesafeye sadk kalarak, kltme leklemesiyle rota izilerek gsterim yaplmtr.

f) Srdrlebilirlik asndan esnektir. zm iin kullanlan noktalar kmesi artrlabilir ya da azaltlabililir.

Program Kstlar

Programn gelitirme aamasnda akla n grlemeyen, zm srecinin kontrol ve zm kalitesini artrmaya ynelik baz durumlar olumutur. Bunlar aada sralanmtr.

a) Her bir komuluk rotas ve komuluun mesafe maliyeti, kullanlan sezgisel yntem ile bu ynteme ait parametrelerle kaydnn tutulmas yaplmamtr. rnein tavlama method iin bu yntem uygulanabilseydi, scaklk dne bal olarak zm kalitesi gzlemlenebilirdi.

b) Balang zmnn ardndan yaplan iyiletirilmi zm, ikinci istee balang zm verilerek aratrma verilebilmesi(daha nce bahsedilen merdiven etkisi) yalnzca tavlama benzetimi iin kodlanabilmitir.

c) Her zm istei, zm isteinin hangi yntem ve parametrelerle yaplmak istendii, elde edilen sonu ve zm sresi gibi bilgiler kaydedilmemitir. Dolaysyla kyaslama ilemi program alrken kullancnn gzlem yeteneine braklmtr.

Programn Uygulama Sonular

Programn amac verilen 20 adet noktann, toplamda en ksa mesafeyi bulacak ekilde rotalanmasdr. Bu ilemi yaparken en hzl ekilde yapmas hedeflenmitir. Bu sebeple de iki sezgisel arama yaklamnn kyaslanmas yoluna gitmitir. Sonular deerlendirilirken adaletli bir kyaslama yaplmaya gayret edilmitir. Her iki yaklam iin aada belirtilen durumlar gz nne alnarak sonular deerlendirilmitir.

a) Kontrol edilen komuluk saysnn her iki sezgisel yaklam iinde ayn olmasna gayret edilmitir.

b) terasyon deeri 1000 saysyla balanm nce 1000er 1000er artrlm ardndan 10000er 10000er artrm yoluna gidilmitir.

c) Yasakl arama ynteminde tabu listesi boyutu 3 olarak balatlm srasyla 7 ve 9 deerleri denenmitir.

d) Tavlama benzetimi iin scaklk 100 olarak belirlenmi bunun dnda bir deer iin kontrol yaplmamtr.

e) Yasakl arama ynteminde komuluk deeri 12 olarak belirlenmi ve bunun dnda bir deer iin kontrol yaplmamtr.

• Bulunan sonular deerlendirildiinde, her iki ynteminde balang zm zerinde iyiletirme
  yapt gzle grlr ekilde ortadadr.
• Yntemler kendi arasnda kyaslanacak olursa, tavlama benzetiminin yasakl arama yntemine gre
  daha iyi sonular verdii gzlemlenmitir.

deal zm Gsterimi

Program altrlarak pek ok sonu elde edilmitir. Elde edilen sonular ierisinde en ksa mesafe uzunluu 3690,06 km bulunmutur. Ancak bu sonucun en iyi sonu olduu halan bilinmemektedir. Pek ok kez daha durumun test edilmesi gerekmektedir. Ancak bu deerden daha iyi bir sonu elde edilemedii gibi, balang zmlerine gre en az %50 oranda iyileme olan bir sonutur. Rotann balang noktasnn hangi nokta olduunun bir nemi yoktur. nk hangi noktadan balanrsa balansn yine ayn noktaya varlaca iin ember etkisi vardr ve toplam mesafe uzunluu fark etmeyecektir. Bu sebeple birden fazla ayn sonuca sahip zmler olduu sylenebilir. Dolaysyla aada verilen zm grseli, 3690,06 mesafe deerine sahip zmlerden herhangi biridir denilebilir.

• zm Sonu:3690,06 km
• Rota:R => J => D => O => C => M => F => H => P => N => T => S => A => U => I => E => B
  => G => L => K => R

Proje Gelitirme Srecini Gsteren TFS Adresi

Projenin gelitirme aamas balangtan bitimine kadar TFS zerinden kontrol edilmitir. Link : https://nisanurb.visualstudio.com/TSP/_git/TSP

Kaynaka

1. http://web.firat.edu.tr/iaydin/bmu579/bmu_579_bolum7.pdf