Min-Max Çoklu Gezgin Satıcı Problemi için Takviyeli Öğrenme ile Hibrit Yaklaşım
Min-Max Çoklu Gezgin Satıcı Problemi için Takviyeli Öğrenme ile Hibrit Yaklaşım
Takviyeli öğrenme tabanlı hibrit CMSA yöntemi, min-max çoklu gezgin satıcı probleminde en iyi çözümleri sunarak genetik algoritmalara üstünlük sağlıyor.
Önemli Noktalar
- RL-CMSA yöntemi, min-max mTSP’nin en uzun turunu minimize etmeye odaklanıyor.
- Hibrit algoritma, genetik algoritmalara göre daha büyük ve karmaşık örneklerde üstün performans gösteriyor.
- Çözümler, takviyeli öğrenme ile sürekli olarak iyileştiriliyor ve havuzda yaşlanma ile optimize ediliyor.
Yöntemin Temel Özellikleri
Çoklu Gezgin Satıcı Problemi (mTSP), klasik Gezgin Satıcı Probleminden farklı olarak birden fazla satıcının ortak bir depodan başlayıp tüm müşterileri yalnızca bir kez ziyaret etmesini gerektirir. Min-max varyantında ise amaç, en uzun turu minimize ederek iş yükünü dengeli bir şekilde dağıtmaktır.
RL-CMSA (Construct, Merge, Solve & Adapt with Reinforcement Learning) adlı hibrit yaklaşım, simetrik ve tek depo içeren min-max mTSP için önerilmiştir. Yöntem, olasılıksal kümeleme ve öğrenilmiş çift şehir q-değerleriyle çeşitli çözümler oluşturur, rotaları sıkıştırılmış bir havuzda birleştirir, kısıtlı set-covering MILP ile çözer ve rotalar arası çıkarma, kaydırma ve değiştirme adımlarıyla çözümleri rafine eder.
Teknik Detaylar
- Q-değerleri, yüksek kaliteli çözümlerdeki şehir çiftlerinin birlikte görülmesine göre güncellenir.
- Çözüm havuzu, yaşlanma ve budama mekanizmalarıyla sürekli olarak optimize edilir.
- Doğrudan optimizasyon ve takviyeli öğrenme birleşimi sayesinde keşif ve sömürü dengeleniyor.
Performans ve Sonuçlar
RL-CMSA yöntemi, rastgele ve TSPLIB örneklerinde tutarlı şekilde en iyi veya en iyiye yakın çözümler buldu. Karşılaştırılabilir süre sınırlarında, hibrit genetik algoritmaya göre özellikle örnek boyutu ve satıcı sayısı arttıkça daha iyi sonuçlar elde edildi.
Synvalo’da Daha Fazla Teknoloji Haberi
En güncel bilimsel ve teknolojik gelişmeleri takip etmek için Synvalo’nun sosyal medya hesaplarını (@synvalo) ziyaret edebilirsiniz.
Kaynak: arxiv.org