モダンヒューリスティックスによる組み合わせ最適化問題の解法
| 965086 | 富田 紘司 |
| 965099 | 長谷川 渉 |
| 965150 | 吉田 一貴 |
概要
ナップサック問題や巡回セールスマン問題は、最適解を求めるためにすべての組み合 わせを列挙して調べなければならないという本質的な困難さを含んでいる。このため 計算規模が大きくなり、列挙法や分枝限定法といった厳密解法が今日の優れた計算機 環境でも適用できない場合が多い。したがって局所解、あるいはかなり満足できる実行可能解を少ない計算量で求める近似解法を利用することが一般的になっている。モダンヒューリスティックスは、生物進化のシミュレーションや、金属の焼きなましのシミュレーションなどから組み合わせ最適化問題の解法へ適用する技法の総称であり、人工生命とタブーサーチは、近似解法を利用するヒューリスティック手法の一つである。本研究では、人工生命及びタブーサーチをナップサック問題と巡回セールスマン問題 に適用し、その有用性を検討する。
