Pointer Networks Kombinatoryal Optimizasyonda Ne Kadar İyi?

Bir araştırmacı, seyaç satıcısı problemini (TSP) çözmek için Pointer Networks'ü REINFORCE ile eğitti ve sonuçlar ilginç: ağ çözümleri milisaniyeler içinde buluyor ama problem büyüdükçe kalite düşüyor.

Kısa özet: 20 şehir için iyi sonuçlar alıyor, 200 şehire çıkınca ağ çöküyor. Google'ın OR-Tools'u (10 saniyelik zaman aşımıyla) daha dengeli kalıyor. Araştırmacı sorunu buldu: LSTM encoder koordinatları sırayla işliyor ve son gördüğü veriye daha fazla ağırlık veriyor. Oysa TSP'de şehirlerin sırası önemli değil, sadece onlar arasındaki mesafeler önemli.

Bu yapay bir sıralama önyargısı yaratıyor. Ağ, "son şehir daha yakın" gibi yanlış desenleri öğreniyor. Büyük problemlerde bu bias çok kötü çıkıyor.

Praktik olarak: Pointer Networks hızlı, ama NP-hard problemlerde gerçek kullanım için başka mimariler (Transformer, Graph Neural Networks) daha umut verici görünüyor. Bu yazı, makine öğrenmesi ile kombinatoryal optimizasyon arasındaki boşluğu gösteriyor, hız kolay, kalite zor.