著者

榎原 博之 田中 裕也 石川 琢士

雑誌

研究報告数理モデル化と問題解決(MPS)

巻号頁・発行日

vol.2011, no.10, pp.1-6, 2011-05-10

---

自然界には粘菌という単細胞生物が存在する.粘菌は森の土の中などに数多く存在しており,採餌行動の際には自分自身の体で栄養を運ぶネットワークを構築する.本研究では,粘菌の採餌行動のシミュレーションプログラムを元に,巡回セールスパーソン問題 (TSP) を解く粘菌アルゴリズムを提案する.まず,粘菌の作るネットワークをシミュレーションし,そこから巡回路を作成し,TSP に対応させる.最終的には 2-opt 法による局所探索法を用いて,解の改善を行う.ベンチマーク問題 (TSPLIB) を用いて計算機実験を行い,評価を行う.The slime mold is single-celled which exists in the natural world. It exists a lot in the soil of the forest etc. and in the foraging action it constructs the network in which nourishment is carried by own body. In this research, we propose a algorithm which solves the travelling salesperson problem (TSP) based on the simulation program of the foraging action of the slime mold. First,we simulate a network made by the slime mold, and make a TSP tour. Finally, in order to improve the solution, we use 2-opt which is the local search method. We experiment on the computer by using the benchmark problems(TSPLIB), and we evaluate the slime mold algorithm.