GENETİK ALGORİTMALAR (ÖRNEK SORU VE EXCEL UYGULAMASI)

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.

İndis fonksiyonuna Mesafe Matrisini ekliyorum.
Mesafe Matrisi Tüm Kutular İçinde Aynı Olup Değişmeyeceği İçin f4 ile sabitliyorum.

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.

Satır için hep aynı diziden arama gerçekleştireceğim için satırı da tüm kutular için f4 ile sabitliyorum.

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.

Sütun için hep aynı diziden arama gerçekleştireceğim için sütunu da tüm kutular için f4 ile sabitliyorum.
Fonksiyonun son hali bu şekilde.

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.

Rastgele oluşturduğumuz kromozomlar.
Sonunda yine aynı şehre döndüğü için son olarak onu da ekliyoruz.
Kromozomların her biri arasındaki mesafeyi ve bu mesafelerin toplamını maliyet olarak görebiliyoruz.
Burada maliyetler dizisinin P17- P18- P19- P20-P21 konumlarındaki sayıardan oluştuğunu görüyoruz.

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.

Bir cevap yazın

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