| 第1章 序論 1 |
| 1.1 組合せ最適化 1 |
| 1.1.1 アルゴリズムの複雑度 4 |
| 1.1.2 困難な問題 対 容易な問題 6 |
| 1.2 最適化手法 9 |
| 1.3 状態、遷移、および、最適性 10 |
| 1.4 局所的探索 12 |
| 1.4.1 決定的アルゴリズムと確率的アルゴリズム 13 |
| 1.5 最適解 対 最終解 15 |
| 1.6 単一制約最適化と複数制約最適化 16 |
| 1.7 繰り返しアルゴリズムの収束性の解析 18 |
| 1.7.1 構成グラフ 18 |
| 1.8 マルコフ連鎖 20 |
| 1.8.1 斉時的マルコフ連鎖 20 |
| 1.8.2 摂動確率 21 |
| 1.8.3 エルゴード的マルコフ連鎖 21 |
| 1.8.4 採択確率 25 |
| 1.8.5 推移確率 26 |
| 1.9 並列処理 27 |
| 1.10 概要と本書の構成 31 |
| 文献 33 |
| 演習問題 34 |
| 第2章 シミュレーティド・アニーリング手法(SA) 43 |
| 2.1 序論 43 |
| 2.1.1 背景 44 |
| 2.2 SAアルゴリズム 46 |
| 2.3 SAの収束性 52 |
| 2.4 SAアルゴリズムのパラメータ 60 |
| 2.4.1 単純な冷却スケジュール 61 |
| 2.4.2 統計的な多項式時間冷却スケジュール 62 |
| 2.4.3 効率的な汎用冷却スケジュール 66 |
| 2.5 SAへの要求 67 |
| 2.6 SAの適用例 69 |
| 2.6.1 VLSIの配置処理とTimberWolf3.2 69 |
| 2.6.2 他の適用例に関する概要 74 |
| 2.7 SAの並列化 74 |
| 2.7.1 並列アニーリング手法 75 |
| 2.7.2 多重試行並列化 77 |
| 2.8 結論と最近の研究 83 |
| 文献 86 |
| 演習問題 88 |
| 第3章 遺伝的アルゴリズム(GAs) 95 |
| 3.1 序論 95 |
| 3.1.1 GAsの基本的な考えかた 96 |
| 3.1.2 GAsの用語 97 |
| 3.2 GAs 104 |
| 3.3 スキーマ定理と内在的並列性 105 |
| 3.3.1 スキーマ定理 107 |
| 3.3.2 内在的並列性 110 |
| 3.4 GAsの収束性 111 |
| 3.4.1 突然変異、あるいは逆位をもたないGAs 112 |
| 3.4.2 交叉と突然変異をもつGAs 113 |
| 3.5 実用上のGAs 116 |
| 3.5.1 遺伝的オペレータ 117 |
| 3.5.2 適応度関数 123 |
| 3.5.3 スケーリング 124 |
| 3.5.4 両親の選択 125 |
| 3.6 GAsのパラメータ 128 |
| 3.6.1 集団 128 |
| 3.6.2 世代間ギャップ 129 |
| 3.6.3 オペレータの確率 130 |
| 3.6.4 その他の課題 131 |
| 3.7 GAsの適用例 132 |
| 3.7.1 巡回セールスマン問題 133 |
| 3.7.2 部品配置問題 138 |
| 3.7.3 GAsの他の問題への適用 140 |
| 3.8 GAsの並列化 143 |
| 3.8.1 島モデル 143 |
| 3.8.2 踏み石モデル 143 |
| 3.8.3 近傍、または、細胞モデル 144 |
| 3.9 他の問題と最近の研究 145 |
| 3.9.1 性能評価尺度 145 |
| 3.9.2 グレイコード化 対 2進コード化 146 |
| 3.9.3 生態学的地位、混雑度、および、種形成 146 |
| 3.9.4 一定集団、対、動的減少集団 148 |
| 3.9.5 GAsによる多目的最適化 149 |
| 3.9.6 その他の関連する話題 150 |
| 3.10 結論 151 |
| 文献 151 |
| 演習問題 156 |
| 第4章 タブー・サーチ手法(TS) 163 |
| 4.1 序論 163 |
| 4.2 TSアルゴリズム 166 |
| 4.3 プログラム化に関する問題 173 |
| 4.3.1 遷移の属性 173 |
| 4.3.2 タブーリストとタブー制約 174 |
| 4.3.3 タブーリストを取り扱うためのデータ構造 176 |
| 4.3.4 その他の願望水準 183 |
| 4.4 短期記憶の限界 185 |
| 4.4.1 中期記憶(探索の強化) 187 |
| 4.4.2 長期記憶(探索の多様化) 188 |
| 4.5 多様化した探索の例 190 |
| 4.5.1 2次割り当て問題における多様化 191 |
| 4.5.2 多重プロセッサスケジューリングにおける多様化 193 |
| 4.6 TSの収束性 195 |
| 4.7 TSの適用例 197 |
| 4.7.1 2次割り当て問題 197 |
| 4.7.2 バンド幅圧縮問題(BWP:Bandwidth Packing Problem) 200 |
| 4.8 TSの並列化 202 |
| 4.9 その他の課題と関連する研究 207 |
| 4.9.1 近傍、評価関数、停止基準 207 |
| 4.9.2 目標解析(TA:Target Analysis) 209 |
| 4.9.3 候補リスト戦略 213 |
| 4.9.4 戦略的振動 215 |
| 4.10 結論 219 |
| 文献 220 |
| 演習問題 224 |
| 第5章 シミュレーティド.エボリューション手法(SimE) 227 |
| 5.1 序論 |
| 5.2 歴史的背景 228 |
| 5.3 SimEアルゴリズム 228 |
| 5.3.1 評価処理 231 |
| 5.3.2 選択処理 235 |
| 5.3.3 ソート処理 235 |
| 5.3.4 割り当て処理 236 |
| 5.3.5 初期化処理 237 |
| 5.4 SimEのオペレータとパラメータ 238 |
| 5.4.1 選択の効果 239 |
| 5.4.2 割り当ての効果 239 |
| 5.4.3 集団サイズの効果 240 |
| 5.4.4 繰り返し回数の効果 240 |
| 5.5 SimE、SA、および、GAsの比較 240 |
| 5.6 SimEの収束性に関する一面 241 |
| 5.7 SimEの適用例 245 |
| 5.7.1 標準セル設計方式 246 |
| 5.7.2 SimEのその他の適用例 255 |
| 5.8 SimEの並列化 256 |
| 5.8.1 ベクトルプロセッサ上でのSimEのプログラム化 256 |
| 5.8.2 MISDおよびMIMDマシン上でのSimEのプログラム化 258 |
| 5.9 結論と最近の研究 260 |
| 文献 261 |
| 演習問題 262 |
| 第6章 確率的進化手法(StocE) 267 |
| 6.1 序論 267 |
| 6.2 歴史的背景 268 |
| 6.3 StocEアルゴリズム 269 |
| 6.3.1 StocEアルゴリズム 272 |
| 6.3.2 StocE 対 SA 275 |
| 6.3.3 StocE対SimE 275 |
| 6.4 StocEの収束性に関する一面 277 |
| 6.5 StocEの適用例 279 |
| 6.5.1 ネットワーク2分割問題 280 |
| 6.5.2 頂点被覆問題 280 |
| 6.5.3 ハミルトン閉路問題 282 |
| 6.5.4 巡回セールスマン問題 286 |
| 6.5.5 StocEにもとづいたFPGAのテクノロジー・マッピング 287 |
| 6.6 StocEの並列化 298 |
| 6.7 結論と最近の研究 303 |
| 文献 304 |
| 演習問題 306 |
| 第7章 ハイブリッド手法とその他の課題 309 |
| 7.1 序論 309 |
| 7.2 アルゴリズムの概要 310 |
| 7.3 ハイブリッド化 312 |
| 7.3.1 SA/TSハイブリッド 312 |
| 7.3.2 GA/SAハイブリッド 313 |
| 7.3.3 その他のハイブリッド 315 |
| 7.4 GAsと多目的最適化 316 |
| 7.4.1 パレート最適化 317 |
| 7.4.2 VEGA 318 |
| 7.4.3 MOGA 319 |
| 7.5 多目的最適化のためのファジー論理 320 |
| 7.5.1 ファジー集合理論 321 |
| 7.5.2 ファジー演算 323 |
| 7.5.3 ファジー・ルール 323 |
| 7.5.4 ファジー多目的最適化の例 323 |
| 7.5.5 ファジー目標指向最適化 326 |
| 7.6 人工ニューラルネットワーク 327 |
| 7.7 解の質 332 |
| 7.8 結論 335 |
| 文献 337 |
| 演習問題 339 |
| 索引 343 |
| 人名索引 347 |
