Genetik algoritmaların operatörleri ve parametreleri için en iyi ayarları belirleme: Bir metodoloji ve gezgin satıcı probleminde uygulaması

Genetik Algoritmalar (GA'lar), optimizasyon problemlerinin en uygun çözümlerine yaklaşmak için kullanılan sezgisel algoritmalardır. Bir çözüm popülasyonunun nesiller boyunca evrimleştiği ve sonunda sadece en uygun bireylerin hayatta kaldığı doğal evrim teorisinden ilham almıştır. GA'lar çözüm kalitesi ve çalışma süresi açısından birçok optimizasyon probleminde başarılı olarak uygulanmıştır. Bununla birlikte, tipik bir GA'nın mutasyon ve çaprazlama gibi çeşitli operatörleri ve performansını önemli ölçüde etkileyen nüfus büyüklüğü ve üretim sayısı gibi parametreleri vardır. Literatürde, GA'ların operatörleri ve parametreleri belirlenirken genellikle kullanıcıların önceki deneyimleri veya deneme yanılma deneyleri kullanılmaktadır. Bu tezde, GA'ların operatörlerini ve parametrelerini etkili bir şekilde ayarlayan bir metodoloji geliştirilmiştir. Tipik olarak bir GA'nın performansı iki kritere göre değerlendirilir: (1) yaklaşık çözüm kalitesi ve (2) çalışma süresi. Bir algoritmanın yaklaşım kalitesi, algoritma tarafından bulunan çözümün optimal çözüme yakınlığına bağlı olarak belirlenir. Çalışma süresi, algoritmanın çözümü sonlandırmaya kadar kullandığı hesaplama süresiyle ölçülür. Genel olarak, bu iki kriter arasında ödünleşme vardır, daha iyi çözüm kalitesi daha fazla çalışma süresi gerektirir. Bir GA'nın kısa sürede yüksek kaliteye sahip bir çözüm bulması beklenmektedir. Operatörlerin ve parametrelerin ayarları her iki kriteri de etkiler ve farklı ayarlar farklı kriterler açısından avantajlı olabilir. Bu nedenle, etkili ayarların belirlenmesi çok amaçlı bir optimizasyon problemidir. Bu tez kapsamında, GA'ların yaklaşık kalitesi ve çalışma süresi arasındaki dengeleri keşfetmek için çok amaçlı bir evrimsel algoritma (MOEA) kullanılmaktadır. MOEA'lar doğal evrim sürecini taklit eden nüfus tabanlı sezgisel yöntemlerdir ve iyi yakınsamış ve iyi çeşitlendirilmiş baskın olmayan çözümler bulurlar. Yaklaşımımızda, MOEA'nın her bir çözümü, GA'nın operatörleri ve parametreleri için bir ayarı temsil etmektedir. Popülasyondaki bir çözümü değerlendirmek için GA çözümde tanımlanan ayarlar kullanılarak çalıştırılır. Yaklaşık kalite ve çalışma süresi açısından en uygun çözümler nesiller boyunca varlığını sürdürmektedir. Sonunda, her biri başka bir kriterde daha iyi olan bir dizi ayar bulunur. Geliştirilen metodoloji, gezici satıcı probleminde (TSP) denenmiştir. Farklı problem boyutlarına sahip 31 TSP örneği literatürden seçilmiştir. TSP'yi çözmek için kullanılan GA'nın operatörleri ve parametreleri için çeşitli alternatifler dikkate alınmakta ve en iyi ayarlar aranmaktadır. En iyi ayarlar kümesinin belirlenmesi için tanınmış bir MOEA olan NSGA-II kullanılmaktadır. Karar vericilerin tercihlerine göre nihai çözüm kümesinin boyutunu azaltmalarına yardımcı olmak için bir sezgisel tarama da geliştirilmiştir.