Yazarlar:  (1) Ankur Nath, Bilgisayar Bilimi ve Mühendisliği Bölümü, Texas A&M Üniversitesi;  (2) Alan Kuhnle, Bilgisayar Bilimi ve Mühendisliği Bölümü, Texas A&M Üniversitesi.  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:    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. 1. Öğrenilmiş buluşsal yöntemler aşırı parametrelenebilir mi? Kesinlikle.    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. 2. Temel önyargı, öğrenilmiş buluşsal yöntemin üstün performansına atfedilebilir mi?  *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.  Bu makale arxiv'de CC 4.0 DEED lisansı altında mevcuttur.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

HeuristicSearch.TECH

Efficiently exploring and navigating large solution spaces at HeuristicsSearch.Tech

Heuristic Search's blog

Bu ses hikayenin orijinal dilinde üretilmiştir!

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

About Author

YORUMLAR

ETİKETLERİ ASIN

BU YAZI

Related Stories

Kullanıcı Odaklı Kripto Ürünleri Oluşturma: Müşteri Geri Bildiriminin Önemi

HackerNoon Yazma Yarışmasını mı Kazanmak İstiyorsunuz? İşte #crypto-api Yarışması Kazananlarının Önerileri

Başarılı Buluta Geçiş İçin Tam Kılavuz: Stratejiler ve En İyi Uygulamalar

Benzersiz Bir Ekosistemi Güçlendiren Bitcoin UTXO Modeli

Kullanıcı Odaklı Kripto Ürünleri Oluşturma: Müşteri Geri Bildiriminin Önemi

HackerNoon Yazma Yarışmasını mı Kazanmak İstiyorsunuz? İşte #crypto-api Yarışması Kazananlarının Önerileri

Başarılı Buluta Geçiş İçin Tam Kılavuz: Stratejiler ve En İyi Uygulamalar

Benzersiz Bir Ekosistemi Güçlendiren Bitcoin UTXO Modeli

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps