Jaringan saraf dengan amuba memecahkan masalah salesman keliling untuk 8 kota

Solusi dari masalah salesman keliling yang diperoleh oleh sistem komputasi berbasis amuba. Contoh tur penjual di empat, lima, enam, tujuh dan delapan kota, diperoleh dalam percobaan, di mana setiap tur diwarnai merah pada saluran yang sesuai dari gambar kanan. Panel kiri menunjukkan gambar cahaya yang ditransmisikan dari keadaan awal (

Sekelompok peneliti Jepang dari Universitas Keio di Tokyo menunjukkan bahwa amuba mampu menghasilkan solusi perkiraan untuk masalah matematika yang sangat kompleks yang dikenal sebagai masalah salesman keliling .

Tugas wiraniaga adalah salah satu tugas optimisasi kombinatorial yang paling terkenal, yang terdiri dari menemukan rute yang paling menguntungkan melewati kota-kota ini setidaknya sekali dan kemudian kembali ke kota asli.

Pernyataan optimisasi masalah termasuk dalam kelas masalah NP-hard, seperti kebanyakan kasus khusus. Versi "masalah keputusan" (yaitu, di mana pertanyaan dimunculkan apakah rute ada tidak lebih dari nilai k yang diberikan) milik kelas masalah NP-lengkap.

Kesulitan menghitung solusi yang tepat meningkat secara eksponensial karena lebih banyak kota ditambahkan ke tugas. Misalnya, untuk empat kota ada tiga solusi, dan untuk enam kota - 360. Di masa depan, pertumbuhan eksponensial terus berlanjut.

Terlepas dari kerumitan komputasinya yang besar, ada sejumlah besar algoritma heuristik dan akurat yang dapat sepenuhnya menyelesaikan beberapa kasus dengan puluhan ribu kota, dan bahkan masalah dengan jutaan kota dapat diperkirakan sekitar 0,05% . Tautan yang diindikasikan berisi upaya untuk menyelesaikan contoh 1.904.711 kota di Bumi dari dasar National Geographical Society.


Pangkalan Perhimpunan Geografis Nasional 1.904.711 kota

Saat ini, catatan untuk jarak minimum untuk kota-kota di Bumi adalah 7 515 772 107 km, ditetapkan pada 13 Maret 2018 menggunakan algoritma LKH heuristik.

Masalah salesman klasik dalam ilmu komputer digunakan sebagai tolok ukur untuk algoritma optimasi.

Amuba adalah organisme uniseluler yang tidak tahu tentang kompleksitas optimasi kombinatorial. Mereka tidak memiliki apa-apa bahkan menyerupai sistem saraf pusat, yang membuat mereka menjadi kandidat yang kurang cocok untuk memecahkan masalah kompleksitas seperti itu. Namun, peneliti Jepang telah menemukan bahwa jenis amuba tertentu dapat digunakan untuk menghitung solusi yang hampir optimal untuk masalah salesman keliling untuk delapan kota.


Menurut sebuah artikel ilmiah , amuba yang disebut Physarum polycephalum , yang sebelumnya telah digunakan sebagai komputer biologis dalam beberapa percobaan lain, berpartisipasi dalam percobaan. Makhluk ini dianggap sangat berguna dalam komputasi biologis karena dapat memperluas berbagai area tubuhnya untuk mencari cara yang lebih efisien untuk mendapatkan makanan, dan membenci cahaya.

Untuk mengubah mekanisme nutrisi alami ini menjadi komputer, peneliti Jepang menempatkan amuba di piring khusus dengan 64 saluran, ke arah mana hewan itu dapat meregangkan tubuh. Amoeba terus-menerus berusaha memperluas tubuh untuk menutupi area yang paling besar dari lempeng nutrisi. Namun demikian, setiap saluran di piring dapat menyala, yang menyebabkan amuba keluar dari saluran ini dari perasaan benci ke cahaya.

Untuk mensimulasikan masalah pramuniaga keliling, masing-masing 64 saluran di piringan diberi kode kota antara A dan H, di samping angka dari 1 hingga 8, yang menunjukkan urutan kota (urutan kota sesuai dengan urutan kunjungan mereka oleh pramuniaga).

Untuk memprogram amuba, para peneliti menggunakan jaringan saraf yang mencakup data tentang posisi amuba saat ini dan jarak antara kota untuk menerangi saluran tertentu. Jaringan saraf lebih memungkinkan untuk menerangi kota (saluran) dengan jarak yang lebih besar di antara mereka.

Ketika algoritma dan amuba berinteraksi, yang terakhir mengambil bentuk yang mewakili solusi perkiraan untuk masalah salesman keliling. Yang paling menarik, jumlah waktu yang dibutuhkan amuba untuk mendapatkan solusi yang hampir optimal ini tumbuh secara linear , walaupun jumlah opsi solusi meningkat secara eksponensial . Dalam waktu dekat, para peneliti akan membuat chip dengan puluhan ribu saluran sehingga amuba dapat mencoba memecahkan masalah salesman keliling di ratusan kota.

Artikel ilmiah ini diterbitkan pada 19 Desember 2018 dalam jurnal Royal Society Open Science (doi: 10.1098 / rsos.180396).