本日読了。
良書だが絶版？かなり昔の本なので、用語の日本語訳が微妙であるが、ヒューリスティクスの手法を網羅的に解説しており、価値が高い。
なお、筆者がWebにもっといろいろまとめている。
Python言語による実務で使える100+の最適化問題 | opt100
基本戦略
- 近傍探索法と構築法（今風に言うと生成法？）
- 部品の利用
- 複数の解の保持と相互の情報交換
- 問題の変形（スケーリング、微細データの除去、平準化、集約、目的関数の変形）
- 探索履歴の活用（同じ探索を繰り返さない等）
代表的な手法
- hill clibming method
- multiple start
- iterated local search（hill clibming + kick）
- simulated annealing method
- tabu search（近傍内の最良解で、禁断リストにないものを探索）
- guided local search
- ant colony method（探索したところにフェロモンが残る）
- evolutionary algorithm（交叉や突然変異で子孫をつくり、自然淘汰させる）
具体的な問題
- グラフ分割問題（制約条件とペナルティ付きのグループ分割）
- 最大安定集合問題（制約条件とペナルティ付きの最大部分集合抽出）
- グラフ彩色問題（制約条件とペナルティ付きの彩色問題）
- 巡回セールスマン問題
- 2次割当問題（総移動距離を最小にする配置）
- 多制約ナップザック問題
- 数分割問題（数の組み合わせを分割して合計差を最小にする）
