Menghasilkan masalah optimisasi kombinasi yang menarik

Saya mengajar kursus tentang meta-heuristik dan perlu membuat contoh menarik dari masalah kombinatorial klasik untuk proyek jangka. Mari kita fokus pada TSP. Kami menangani grafik dimensi dan lebih besar. Saya mencoba tentu saja untuk menghasilkan grafik dengan matriks biaya dengan nilai yang diambil dari U acak ( 0 , 1 ) , dan menemukan bahwa (seperti yang diharapkan) histogram untuk biaya jalur (diambil dengan mengambil sampel banyak jalur acak) memiliki distribusi normal yang sangat sempit ( μ adalah 100 tetapi σ sekitar $200$$U(0,1)$$\mu$$~100$$\sigma$$4$). Ini berarti, menurut saya, masalahnya sangat mudah, karena sebagian besar jalur acak akan berada di bawah rata-rata, dan jalur biaya minimum sangat dekat dengan jalur acak.

Jadi saya mencoba pendekatan berikut: Setelah menghasilkan -matrix, berjalan secara acak di sekitar grafik, dan secara acak (Bernoulli dengan p = 0,5 ) dua kali lipat atau membagi dua nilai tepi. Ini cenderung menurunkan semua nilai, akhirnya mencapai nol, tetapi jika saya mengambil jumlah langkah yang tepat, saya bisa mendapatkan distribusi dengan μ sekitar 2 dan σ sekitar 1 .$U(0,1)$$p=0.5$$\mu$$2$$\sigma$$1$

Pertanyaan saya adalah, pertama, apakah ini bahkan definisi yang bagus untuk masalah yang menarik ? Idealnya saya ingin contoh yang sangat multi-modal (untuk fungsi lingkungan yang paling umum), dan yang memiliki sangat sedikit jalur di dekat nilai minimum, sehingga sebagian besar solusi acak akan sangat jauh dari optimal. Pertanyaan kedua adalah, mengingat uraian ini, bagaimana saya bisa menghasilkan instance dengan karakteristik seperti itu?

Salah satu pendekatan umum untuk menghasilkan instance yang lebih sulit adalah sebagai berikut:

• Mulai dengan contoh masalah acak.
• Sematkan "pintu belakang tersembunyi": pilih secara acak solusi yang baik (solusi yang kemungkinan jauh lebih baik daripada solusi apa pun yang sudah ada) dan modifikasi instance masalah untuk secara paksa menanamkan solusi ini ke instance instance.

$U(0,1)$$U(0,c)$$c<1$; mengurangi berat yang ada; atau memodifikasi edge yang ada dengan probabilitas tetap). Prosedur penyesuaian ini memastikan bahwa solusi optimal akan, dengan probabilitas tinggi, menjadi tur spesial yang Anda pilih. Jika Anda beruntung dan Anda memilih penyematan yang masuk akal, itu juga tidak akan mudah untuk mengenali di mana Anda menyembunyikan solusi khusus.

Pendekatan ini berasal dari ide-ide umum dalam kriptografi, di mana kami ingin membuat masalah pintu satu arah: di mana masalahnya sulit untuk dipecahkan tanpa pengetahuan tentang pintu jebakan rahasia, tetapi dengan pengetahuan tentang pintu jebakan rahasia, masalahnya menjadi sangat mudah. Ada banyak upaya untuk menanamkan pintu jebakan rahasia ke dalam berbagai masalah sulit (sambil tetap mempertahankan kekerasan masalah bahkan setelah pintu jebakan ditambahkan), dengan tingkat keberhasilan yang beragam. Tetapi pendekatan umum ini sepertinya bisa diterapkan, untuk tujuan Anda.

Contoh masalah yang dihasilkan mungkin sulit , tetapi apakah mereka menarik , dari sudut pandang praktis? Saya tidak tahu Mengalahkan saya. Mereka terlihat cukup buatan bagi saya, tetapi apa yang saya tahu?

Jika tujuan utama Anda adalah untuk memilih contoh masalah yang praktis relevan dan mewakili aplikasi TSP dunia nyata, saran saya akan mengambil pendekatan yang sama sekali berbeda. Alih-alih, mulailah dengan mensurvei aplikasi TSP dunia nyata, kemudian mencari contoh representatif dari masalah tersebut, dan mengonversinya menjadi instance masalah TSP yang sesuai - jadi Anda bekerja dengan instance masalah yang berasal dari masalah dunia nyata.

pendekatan yang sering memberi Anda kontrol tinggi atas sifat solusi adalah konversi dari satu masalah lengkap NP ke yang lain. sekarang Anda mendefinisikan "menarik" dalam pertanyaan Anda secara statistik, tetapi pendekatan lain yang rapi adalah menggunakan masalah klasik dari lapangan. favorit saya adalah anjak / SAT. itu sepele untuk menemukan nomor "halus" dengan banyak faktor, atau bilangan prima dengan hanya dua "faktor" (satu dan prima). buat instance SAT untuk menyelesaikan anjak piutang, dan solusinya adalah faktor (sebenarnya permutasi faktor, tetapi juga yang tidak sulit untuk dihitung sebelumnya).

di bawah pendekatan ini, ada definisi alami tentang "menarik" - contoh kasar yang tidak dapat diselesaikan pada waktu P. dan pendekatan ini dijamin untuk menghasilkan contoh-contoh sulit untuk anjak angka-angka tidak mulus kalau tidak akan menyelesaikan pertanyaan terbuka utama dalam teori kompleksitas yaitu kekerasan anjak piutang .

kemudian, mungkin dikonversi ke masalah Anda, dalam hal ini TSP. untuk mengisi jawaban ini akan menyenangkan untuk memiliki SAT langsung ke konversi TSP, berpikir mereka di luar sana, tetapi saya tidak terbiasa dengan mereka. Namun, berikut adalah beberapa rujukan pada factoring-to-SAT dalam pertanyaan ini: mengurangi masalah faktorisasi bilangan bulat menjadi masalah lengkap NP

jika Anda tidak suka anjak piutang, mungkin masih lebih disukai untuk membuat instance di SAT terlebih dahulu karena berbagai alasan. Anda bisa mulai dengan instance SAT acak yang disetel ke pusat di titik transisi mudah-sulit-mudah, dan sebagainya. atau Anda dapat bekerja dari instance keras DIMACS , yang dihasilkan oleh komunitas. atau buat "program" logis lainnya di SAT.