Öğrenilmiş Yerel Arama Buluşsal Yöntemlerinin Sınırlarını Ortaya Çıkarıyoruz: Uysalların En Güçlüsü Siz misiniz?

Bağlantı Tablosu

Özet ve Giriş

Alakalı iş

Max-Cut için değerlendirme

SAT için değerlendirme

Özet ve Görünüm, Referanslar

Ek Malzemeler

Soyut

Son yıllarda sinir ağlarını yerel arama buluşsal yöntemleriyle birleştirmek kombinatoryal optimizasyon alanında popüler hale geldi. Önemli hesaplama gereksinimlerine rağmen, bu yaklaşım minimum düzeyde manuel mühendislikle umut verici sonuçlar ortaya koymuştur. Ancak bu entegrasyon girişimlerinin ampirik değerlendirmesinde üç kritik sınırlama belirledik. İlk olarak, orta derecede karmaşıklığa ve zayıf temellere sahip örnekler, öğrenmeye dayalı yaklaşımların etkililiğinin doğru bir şekilde değerlendirilmesinde zorluk teşkil etmektedir. İkinci olarak, bir ablasyon çalışmasının olmayışı, iyileştirmelerin derin öğrenme mimarisine doğru bir şekilde ölçülmesini ve atfedilmesini zorlaştırıyor. Son olarak, öğrenilmiş buluşsal yöntemlerin farklı dağılımlar arasında genelleştirilmesi henüz yeterince araştırılmamıştır. Bu çalışmada, belirlenen bu sınırlamalara ilişkin kapsamlı bir araştırma yürütüyoruz. Şaşırtıcı bir şekilde, Tabu Aramayı temel alan basit bir öğrenilmiş buluşsal yöntemin, performans ve genelleştirilebilirlik açısından en gelişmiş (SOTA) öğrenilmiş buluşsal yöntemi aştığını gösterdik. Bulgularımız, mevcut varsayımlara meydan okuyor ve kombinatoryal optimizasyonda gelecekteki araştırma ve yenilikler için heyecan verici yollar açıyor.

1. GİRİŞ

NP-zor kombinatoryal optimizasyon (CO) problemleri için etkili buluşsal yöntemler veya yaklaşım algoritmaları tasarlamak, genellikle alan bilgisi ve kapsamlı deneme-yanılma gerektiren zorlu bir iştir. Bu nedenle, bir problemin doğal yapısından yararlanan algoritmaları öğrenmek için bu zorlu ve sıkıcı tasarım sürecini makine öğrenimi yoluyla otomatikleştirme fikri araştırmacılar arasında önemli bir ilgi kazanmıştır (Bello vd., 2016; Khalil vd., 2017; Bengio vd., 2017). ., 2021; Dong ve diğerleri, 2021). Özellikle bu çalışmaların önemli bir kısmı (Khalil vd., 2017; Barrett vd., 2020; Yolcu ve P´oczos, 2019) CO problemleri için Grafik Sinir Ağlarının (GNN) kullanılması üzerine yoğunlaşmıştır. Hesaplamalı taleplere rağmen, bu GNN tabanlı yaklaşımlar, belirli sorunlara göre uyarlanmış SOTA buluşsal yöntemleriyle karşılaştırıldığında rekabetçi bir performans sergilemiştir.

Bu potansiyel ilerlemeler büyük umutlar vaat etse de bazı endişeler devam ediyor. Öğrenilen buluşsal yöntemlerin üstün performansı, belirli örneklerin ve temel çizgilerin seçimine bağlanabilir. Spesifik olarak, eğer taban çizgileri zayıfsa, öğrenilen buluşsal yöntemler kolaylıkla bunlardan daha iyi performans gösterebilir. Zor örnekler ve uygun temel seçimi olmadan öğrenilen buluşsal yöntem, SOTA buluşsal yöntemiyle karşılaştırılabilir performansı kolaylıkla gösterebilir ve bu, öğrenilen buluşsal yöntemin gerçek yeteneklerinin olduğundan fazla tahmin edilmesine yol açabilir. Dahası, derin öğrenme mimarilerindeki ölçeklenebilirlik zorlukları nedeniyle SOTA buluşsal yöntemleriyle karşılaştırmalar zaman zaman göz ardı ediliyor.

Öğrenmeye dayalı yaklaşımların bir alt kümesi (Khalil ve diğerleri, 2017; Yolcu ve P'oczos, 2019; Barrett ve diğerleri, 2020, 2022), geleneksel buluşsal yöntemlerin işlevselliğini veya davranışını içerir ve buluşsal yöntemleri entegre ederek potansiyel olarak iyileştirilmiş veya geliştirilmiş performans sunar. makine öğrenimi bileşenleriyle ilkeler. Entegre buluşsal yöntemlerle kapsamlı bir karşılaştırma ve derin öğrenme mimarisinin ablasyon çalışması eksikse, derin öğrenme mimarisinin spesifik katkısını belirlemek zorlaşır. Sonuç olarak, entegre buluşsal yöntemler sağlamsa, öğrenilen buluşsal yöntemler temel buluşsal yöntemlerden sorunsuz bir şekilde daha iyi performans gösterebilirken, derin öğrenme mimarisi küçük bir rol oynar.

Öğrenilmiş buluşsal yöntemin bir başka büyük başarısı (Khalil ve diğerleri, 2017; Barrett ve diğerleri, 2020; Toenshof ve diğerleri, 2019), başlangıçta belirli bir dağılımdan daha küçük ve spesifik örnekler üzerinde eğitilmiş olup, daha büyük örnekler üzerinde test edildiğinde etkileyici performans sergilemektedir. farklı dağılımlar. Bu başarı, öğrenmeye dayalı yaklaşımları kullanmanın temel hedefiyle uyumlu, önemli bir başarı olarak duruyor: buluşsal yöntemlerin sıklıkla gerektirdiği kapsamlı özelleştirme ve alana özgü bilgi ihtiyacını azaltmak. Her ne kadar hiperparametreli klasik buluşsal yöntemler, belirli bir dağılım için ince ayar yapılırsa zorluklarla karşılaşabilse de, farklı dağılımlara da genellenebilirler. Birincil araştırma, öğrenilmiş buluşsal yöntemlerin gerçekten de klasik buluşsal yöntemlere kıyasla üstün genellenebilirlik gösterip göstermediği etrafında döner. Öğrenilmiş buluşsal yöntemlerin klasik buluşsal yöntemlerle kapsamlı ve anlayışlı bir şekilde karşılaştırılması, öğrenilen buluşsal yöntemlerin genelleştirilebilirliğine ilişkin değerli bilgiler sağlar.

Öğrenilmiş buluşsal yöntemler genellikle teorik garantilerden yoksundur ve ampirik değerlendirmeyi önerilen metodolojilerin güçlü yönlerini ve sınırlamalarını kavramak için tek yöntem haline getirir. Bu çalışmaların ampirik değerlendirmesinde bazı temel ancak önemli soruların henüz keşfedilmemiş kaldığına inanıyoruz. Bu sorular öğrenilen buluşsal yöntemlerin tüm türleri için geçerli olsa da, yerel arama buluşsal yöntemlerini öğrenmeye odaklanan, çok alıntı yapılan ve güncel hakemli yayınları analiz ederek bunları soruyor ve yanıtlıyoruz. Amacımız, çalışmamızda tartışılan CO sorunları için kapsamlı kıyaslamalar sağlamak değil, daha ziyade gelecekteki araştırmacılara araştırmalarını değerlendirmede yardımcı olmaktır.

Somut olarak aşağıdaki soruları sorup cevaplıyoruz:

1. Öğrenilmiş buluşsal yöntemler aşırı parametrelenebilir mi? Kesinlikle. ECO-DQN'deki GNN'yi doğrusal regresyonla değiştirerek ve ECO-DQN'den (Barrett ve diğerleri, 2020) Tabu Search'e (Glover, 1990) bağlanan bir özellik alt kümesi kullanarak, ECO-DQN'nin SoftTabu adı verilen budanmış bir versiyonunu sunuyoruz. . Çalışmamız, SoftTabu'nun NPhard Maksimum Kesim (Max-Cut) problemi için ECO-DQN'ye kıyasla üstün performans ve genellenebilirlik sergilediğini göstermektedir.

2. Temel önyargı, öğrenilmiş buluşsal yöntemin üstün performansına atfedilebilir mi? Evet, öğrenilmiş bir buluşsal yöntem olan SoftTabu'nun, Max-Cut problemi için S2V-DQN'den (Khalil ve diğerleri, 2017) ve Boolean Satisfiability (SAT) için GNNSAT'tan (Yolcu ve P'oczos, 2019) daha iyi performans gösterebileceğini gösteriyoruz.

*3. Öğrenilmiş buluşsal yöntemler, örnek seçimi yanlılığı nedeniyle üstün genelleştirilebilirlik gösterebilir mi?*Evet, ECO-DQN'nin daha zor örneklerde zayıf genelleme gösterdiğini ve arama uzayında kolayca sıkışıp kaldığını gösteriyoruz.