Solusi sains dan teknologi -- Cara mendapatkan semut untuk memecahkan masalah catur Oleh Graham Kendall, University of Nottingham Ambil seperangkat catur dan buang semuanya kecuali satu kesatria.Tempatkan ksatria pada salah satu dari 64 kotak papan catur.Dapatkah Anda membuat 63 langkah hukum sehingga Anda mengunjungi setiap alun-alun di papan catur tepat satu kali.Sebagai pengingat, seorang kesatria bisa memindahkan dua kotak dalam garis lurus, diikuti dengan putaran sembilan puluh derajat dan gerakan satu persegi lebih jauh.
Solusi sains dan teknologi -- Ini mungkin tampak seperti tugas yang sulit, tapi rangkaian gerakan ini, yang disebut tur ksatria, dapat dicapai dengan terlalu banyak cara untuk dihitung.Jika Anda dapat membuat gerakan 63 dan berakhir pada sebuah persegi dari mana Anda dapat kembali ke kotak aslinya dengan langkah hukum ke-64, maka ini dikenal sebagai tur tertutup.Wisata lainnya disebut tur terbuka.Matematikawan telah merenungkan berapa banyak tur tertutup yang ada, dan mereka menemukan angka yang menakjubkan: lebih dari 26 triliun.
Solusi sains dan teknologi -- Ada lebih banyak lagi tur terbuka yang kita tidak tahu persis jumlahnya.Baik Philip HingSaya dan saya sangat terpikat oleh masalah wisata ksatria sehingga kami ingin menemukan cara lain untuk menyelesaikannya.Kami menemukan motivasi di alam - khususnya di semut.Semut menggunakan pola, atau algoritma tertentu, untuk mencari makanan.
Solusi sains dan teknologi -- Algoritma ini dapat digunakan untuk mengatasi berbagai jenis masalah termasuk Traveling Salesman Problem dan Vehicle Routing Problems.Philip dan Graham bertanya-tanya apakah mereka bisa menggunakan algoritma pengoptimalan koloni semut untuk menyelesaikan masalah tur ksatria.Beginilah cara kerja algoritma itu: sebuah program komputer digunakan untuk mensimulasikan populasi semut.Semut ini diberi tugas untuk menemukan solusi atas suatu masalah.
Solusi sains dan teknologi -- Karena setiap semut menjalankan tugas mereka, mereka meletakkan jejak feromon - zat bau yang digunakan semut untuk berkomunikasi satu sama lain.Dalam algoritma simulasi, semut yang paling berhasil (yang memecahkan masalah dengan lebih baik), lebih banyak pheromone daripada yang kinerjanya buruk.L.Shyamal Kami mengulangi prosedur ini berkali-kali (mungkin jutaan kali).Melaluipengulangan, jalur feromon pada solusi yang baik meningkat dan mereka menurunkan pada solusi yang lebih buruk karena penguapan, yang juga diprogram dalam algoritma simulasi.
Solusi sains dan teknologi -- Dalam simulasi untuk memecahkan masalah wisata ksatria, semut hanya bisa membuat gerakan ksatria hukum dan dibatasi untuk tetap berada dalam batas-batas papan catur.Jika seekor semut berhasil menyelesaikan tur maka kami memperkuat tur tersebut dengan menyetorkan lebih banyak feromon pada tur tersebut, bila dibandingkan dengan tur yang bukan tur penuh.Semut yang mencoba untuk menemukan kemudian wisata lebih cenderung mengikuti tingkat yang lebih tinggi dari feromon.Ini berarti bahwa mereka lebih cenderung melakukan gerakan yang sama seperti semut yang berhasil sebelumnya.
Solusi sains dan teknologi -- Ada keseimbangan yang harus diserang.Jika semut mengikuti semut yang berhasil terlalu kaku, maka algoritma akan cepat berkumpul untuk satu tur.Jika kita mendorong semut terlalu banyak, tidak mengikuti feromon semut sebelumnya, maka dari itu mereka hanya akan bertindak secara acak.Jadi ini adalah kasus tuning param algoritmaeter untuk mencoba dan menemukan keseimbangan yang baik.
Solusi sains dan teknologi -- Dengan menggunakan algoritma ini, kami dapat menemukan hampir setengah juta tur.Ini adalah peningkatan yang signifikan dari pekerjaan sebelumnya, yang didasarkan pada algoritma Solusi sains dan teknologi Algoritma ini meniru prinsip evolusi alam Charles Darwin - survival of the fittest.Anggota yang lebih baik (orang-orang yang berkinerja baik pada masalah yang dihadapi) dari populasi simulasi bertahan dan anggota yang lebih lemah mati.Tidak mudah untuk mengatakan mengapa algoritma semut dilakukan dengan baik, bila dibandingkan dengan algoritma Solusi sains dan teknologi Mungkin itu adalah untuk menyetel parameter algoritmik, atau mungkin semut benar-benar suka bermain catur.
Solusi sains dan teknologi -- Masalah tur ksatria sedang dikerjakan sejauh 840 M.Sedikit pemecah masalah yang mengetahui bahwa semut, meskipun simulasi, akan mengatasi teka-teki yang sama lebih dari 1.000 tahun di masa depan.Graham Kendall tidak bekerja untuk, berkonsultasi dengan, memiliki saham atau menerima dana dari perusahaan atau organisasi mana pun yang akan mendapatkan keuntungan dari artikel ini,dan tidak memiliki afiliasi yang relevan.Artikel ini awalnya diterbitkan di The Conversation.
Solusi sains dan teknologi -- Baca artikel aslinya.21 -3 .
Tidak ada komentar:
Posting Komentar