Optimizasyon Tekniklerinde Genetik Algoritmanın kullanımı ile ilgili karşımıza çok çıkan gezgin satıcı problemiyle ilgili okulumuzda bizlere verilen aşağıda gösterilen mesafe matrisiyle ilgili verilen rotaların (kromozomların) maliyetlerini hesaplayacak ve rotaların (kromozomların) rulet tekerleği yöntemiyle açı değerlerini bulacak excel programı yazmamız istendi.
İlk olarak buradaki matrisin aynısını excelde de oluşturdum.
Matrisi excele ekledikten sonra yazacağım programın girilen nodlara göre maliyeti kendisinin oluşturmasını istiyorum bunun için de aşağıdaki gibi bir tablo oluşturdum.
Yukarıda Kromozomlar soldan sağa başlayarak tek tek girilecek, aralarındaki mesafeyi ise sağ taraftaki bölüm kromozomla karşılaştırıp, tablodan veriyi alıp mesafeyi tablonun sağ tarafına yerleştirecek. Daha sonra da mesafeleri toplayıp 1-2-3-4-5 şeklinde sütunda her birisinin yanına yazacak. Son olarak da bu değerlerin açı değerlerini hesaplayıp rulet tekerleği üzerine yerleştireceğiz.
Burada ‘index (indis)’ fonksiyonu ile mesafe matrisini alacağız. Daha sonra ‘;’ işareti ile birlikte başvuru fonksiyonlarından biri olan ‘MATCH (KAÇINCI)’ fonksiyonu ile kromozoma girdiğim değerin aynısını matris içerisinde aramasını istiyorum tabi bu değer satır içerisinde arayacak çünkü A şehrinden B şehrine gidecekse ilk olarak A satırına bakacağız daha sonra sütunlar içerisinden B sütununu arayacağız.
Daha sonra kaçıncı fonksiyonuyla kromozoma yazacağım ilk değeri indis fonksiyonu içerisinde, mesafe matrisinin sütun sayısında arayacağım. Görüldüğü üzere kaçıncı fonksiyonu üç ayrı yapıdan oluşuyor bunlar; aranan değer, aranan dizi ve [eşleştir_tür] şeklinde. Aranan değer seçeneğine 1. kromozomun 1. değerini arayacağım için orayı ekliyorum. Ben bu değeri satır sayıları içerisinde arayacağım için aranan dizi seçeneğine mesafe matrisinin A değerinden J değerine kadar tüm değerlerini dizi olarak ekliyorum. [eşleştir_tür] seçeneği ise bize bulmak istediğimiz değerin, aradığımız diziyle eşleşme durumunu soruyor. Bu seçeneği 0 olarak işaretlememiz bizim tam eşleşme istediğimizi yani aynı değeri aradığımızı gösteriyor.
Burada ikinci değeri sütunlar arasında aramalıyım A şehrinden B şehrine gidecekse ilk nod A ikinci nod B şeklinde girecek ikinci nodu sütunda aradığıma göre aranan değer seçeneğini kromozomun ikinci kutucuğu, aranan dizi seçeneğini de A dan J’ye kadar tüm sütun dizisi şeklinde alacağım. [eşleştir_tür] seçeneği ise birebir eşleşme istediğimden dolayı 0 olarak alıyorum.
Böylece fonksiyonumuzu oluşturmuş olduk. Bu fonksiyon tüm kutular için geçerlidir. Bunu gerçekleştirmek için ise kutunun sağ alt tarafından tutarak kromozomun tamamı için çalışır duruma getirmemiz gerekli daha sonra bunu diğer kromozomlar içinde aşağıya doğru çektirerek yapmalıyız.
Şimdi 5 adet rastgele kromozom oluşturalım ve bu kromozomların rotalarının maliyetlerini hesaplayalım.
Sonunda yine aynı şehre döndüğü için son olarak onu da ekliyoruz.
Burada en kısa rotanın en düşük maliyetli olduğunu bildiğimize göre bunun bir minimizasyon problemi olduğunu, bu problemlerde de rulet tekerleği yöntemindeki açı hesaplamalarında 1/maliyet olarak açı hesaplamalarını yapmamız gerektiğini de bilmeliyiz.
Fonksiyonu =(1/P17) şeklinde yapıp aşağı doğru kaydırdığımızda bütün maliyetlerin hesaplamalarını yapıyor. 1/maliyet verilerini toplayalım
1/maliyet verilerini toplam verisine bölmemiz ve 360 ile çarpmamız gerekli.
Toplam verisini hep aynı yerden aldığım için f4 ile sabitliyorum. Son olarak açı verilerini rulet tekerleğine yerleştirme işlemi kaldı. Sol üstteki sekmelerden ‘ekle’ sekmesi içerisindeki ‘pasta grafik’ seçeneğini işaretleyip karşımıza çıkan yeni sekme içerisindeki ‘veri’ bölümünden ‘veri seç’ butonuna tıklayıp açı verisini dizi olarak eklememiz gerekli.
Verileri grafiğe ekledikten sonra grafik üzerinde tasarımla ilgili değişiklikler yapabilirsiniz. Oluşturduğum excel dosyasını aşağıya bırakıyorum siz de inceleyip geliştirmeler yapabilirsiniz. Rastgele farklı kromozomlar oluşturarak maliyeti en düşük çözüme ulaşmaya çalışabilirsiniz. Gezgin satıcı probleminin genetik algoritma tekniğiyle çözüme yaklaşma uygulaması rulet tekerleği yöntemi kullanarak gerçekleştirilmiştir.