メタヒューリスティクスの数理 サポートページ

久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ 著
共立出版 2009年

 

メタヒューリスティクス(metaheurisitcs, modern heuristics)は,困難な組合せ最適化問題を解くための比較的新しいフレームワークである.本書のポリシーは,以下の通り.

  1. 実際に動くプログラムを示し,それを使って解説する.
  2. 抽象論(哲学)ではなく,具体的なアルゴリズムを設計する.
  3. 実際に役に立つ工夫を紹介する.
  4. 自分で一から効率的なメタヒューリスティクスを設計できるようなコツを伝授する.
  5. 応用例を多く示す.とりあげる問題は,グラフ分割,最大安定集合,グラフ彩色,巡回セールスマン,2次割当,多制約ナップサック,数分割である.
  6. 実際に動くプログラムをソースレベルで解説する.コンパクトに記述するために,用いるプログラミング言語はPythonを選択した.

Pythonのプログラム (Programs in Python)

download all files
for Python 2.x zip file
for Python 3.x zip file

  1. graph tools (used in common in the following programs)
  2. Graph partitioning problem o tabu search o simulated annealing
  3. Maximum stable set problem o tabu search o plateau search
  4. Graph coloring problem o construction heuristics (including SEQ, DSATUR, RLF) o tabu search o hybrid of genetic algorithm and tabu search
  5. Traveling salesman problem o basic local search o with GUI (using networkX)
  6. Quadratic assignment problem o tabu search
  7. Multi-constrained knapsack problem o tabu search o MIP based approach
  8. Number partitioning o differencing method for bipartition o differencing method for multi partition o Longest Processing Time (LPT) heuristics (by solving multiprocessor scheduling)

誤植等(数式等はLaTeXフォーマットで記述)

  1. p.70 3行目:divide and conqer -> divide and conquer
  2. p.203 13行目: $5L$ -> $5${\tt L}
  3. p.227 左段 21行目(索引): divide and conqer -> divide and conquer
  4. 背表紙 著者紹介 4行目: 准教授 -> 教授