Profile and Contacts�   Author: Fei Zhao�   Student ID: 085739E�   Email: [email protected]�   PDF Download: http://bit.ly/semi3-fei�   Date: 2011/05/13 (FRI)� 1 目次 4.3.1 問題の定義と定式化 ------------------------------------ 131 4.3.2 近傍 ---------------------------------------------------------- 133 4.3.3 補助メモリによる高速化 -------------------------------- 137 4.3.4 禁断探索法 ------------------------------------------------ 138 4.3.5 遺伝的アルゴリズムと禁断探索法の融合 --------- 138 4.3.6 Python による実装 -------------------------------------- 141 2 4.3.1 問題の定義と定式化グラフ彩色問題とは: 与えられた無向グラフ G = (V ,E) に対して, 最小の K (彩色数) を導く K 彩色Υ = {V1 ,...,Vk } を求める問題. ただし, € K 個の部分集合への分割 Υ€= {V1 ,...,Vk } で点集合 V の €は: € Vi ∩V j = ∅,∀i≠ j K Vj = V € j=1  € € € を満たす 3 4.3.1 問題の定義と定式化グラフ彩色問題の例: Υ = {V1 ,V2 ,V3 } K =3 V1 = {B,E,D} € € V2 = {F} € V3 = {A,C} € € 4 4.3.1 問題の定義と定式化グラフ彩色問題の最適解: 3 (色クラスの数). 5 4.3.1 問題の定義と定式化グラフ彩色問題の定式化: minimize K max ∑ yk k=1 K max subject to ∑ xik k=1 € =1 ∀i ∈ V xik + x jk ≤ yk ∀(i, j) ∈ E,k = 1,...,K max xik ∈€{0,1} ∀i ∈ V ,k = 1,...,K max € yk ∈ € {0,1} ∀k = 1,...,K max € € € 6 4.3.1 問題の定義と定式化グラフ彩色問題の定式化: 最適な K 彩色は, 1 ≤ る € y k K max ∑ yk k=1 K ≤ K max (仮定) の整数から選択す yk ∈ {0,1} € ∀k = 1,...,K max 色クラス Vk に含まれる点の数が ≥ 1 のとき otherwise € € 0 € € € € 1 € 7 4.3.1 問題の定義と定式化グラフ彩色問題の定式化: xik ∈ {0,1} ∀i ∈ V ,k = 1,...,K max xik k =1 点 i に塗られた色が € € otherwise k の時 1 € 0 € € € k =2 € € k=3 k = K max € € 8 4.3.1 問題の定義と定式化グラフ彩色問題の定式化: K max ∑ xik k=1 k =1 = 1 ∀i ∈ V k =2 € € 各点 i に必ず一つの色が塗られること € € k=3 k =n € € € k = K max € 9 4.3.1 問題の定義と定式化グラフ彩色問題の定式化: xik + x jk ≤ yk ∀(i, j) ∈ E,k = 1,...,K max € € € xik ∈ {0,1} ∀i ∈ V ,k = 1,...,K max xik + x jk ≤ yk = 1 ( yk = 1 のときのみ色 k で彩色可能) € € 枝(i, j)両端点の点 i と点 j が,同じ色クラスに割り当てられることを禁止する € € € € 10 € 4.3.1 問題の定義と定式化グラフ彩色問題の定式化: xik + x jk ≤ yk = 1 0 0 =0 0 1 =1 1 0 =1 1 1 = 2 (同じ色クラスに割り当てられる) 11 4.3.1 問題の定義と定式化応用: 1. 時間割作成 2. スケジューリング 3. 周波数割当 4. レジスタ配分 5. プリント基板テスト 6. パターンマッチング 7. 数独 (81 個の頂点を持つグラフの 9 – 彩色問題) 12 4.3.2 近傍 move 近傍: (一つの点の色を別の色に変える) 13 4.3.2 近傍 move 近傍の定義: ʹ′ } | conditions} N move (Υ) = {Υʹ′ = {V1ʹ′,...,VKʹ′ ,VK+1 conditions : Vcʹ′(i) = Vc (i) \ {i} Vkʹ′ = VkU {i} V jʹ′ = V j (∀j ≠ k,c(i)) k ≠ c(i) k ∈ {1,...,K,K +1} i∈V 14 4.3.2 近傍 move 近傍のペナルティ関数: f (Υ) = K 2 − ∑ Vi i=1 K + 2 ∑ Vi i=1 ⋅ E(Vi ) € 15 4.3.2 近傍 move 近傍おいては, 彩色数 K を小さくするために, 各色クラスに含まれる点の数をなるべく偏ったものにすること. 9 個の点を三つ分割するとき: € (3,3,3) 2 2 2 (0,0,9) 2 2 2 = 3 + 3 + 3 = 27 = 0 + 0 + 9 = 81 K =3 K =1 € € € € 16 4.3.2 近傍 move 近傍 (制限付き) の定義: N˜ move (Υ) = {Υʹ′ = {V1ʹ′,...,VKʹ′ } | conditions} conditions : Vcʹ′(i) = Vc (i) \ {i} Vkʹ′ = VkU {i} V jʹ′ = V j (∀j ≠ k,c(i)) k ≠ c(i) k ∈ {1,...,K} i∈V B(i) > 0 17 4.3.2 近傍 Kempe chain 近傍の定義: K 彩色 Υ = {V1 ,...,VK } から２つのクラス Vi ,V j を選び, k を Vi ,V j から導かれた部分グラフ上での連結成分とする. k ≠ (Vi ∪V j ) のとき, Vi = Vi Δk € € € V j = V j Δk € で置き換えた彩色の集合が, Υ の Kempe 近傍である. € € € 18 4.3.2 近傍 Kempe chain 近傍の例: Vi = {A, B} V j = {C,D,E} € € € € k = {A, B,D} Vi ∪V j = {A, B,C,D,E} 19 4.3.2 近傍 Kempe chain 近傍の例:  k ≠ Vi ∪V j ∴ Vi = Vi Δk = (Vi \ k) ∪ (k \ Vi ) = {∅} ∪ {D} = {D} € € V j = VΔk = (V j \ k) ∪ (k \ V j ) = {C,E} ∪ {A, B} = {A, B,C,E} 20 € 4.3.2 近傍 Kempe Chain 近傍の例: 21 4.3.2 近傍 Kempe Chain 近傍は 4 色問題の証明に用いられた. 4 色問題とは: 境界で接するどの２つの国も同じ色で塗らないように, 地図の全ての国を 4 色で塗り分けることができる. 22 4.3.2 近傍 Kempe Chain 近傍においては, move 近傍で用いたペナルティ関数と同様に, 色クラス Vk の位数をなるべく偏ったものすることによって, 彩色数 K を減少させる. 下記の目的関数を最大化すれば良い. € € € f (Υ) = K 2 ∑ Vi i=1 23 4.3.2 近傍近傍の比較: move 近傍  実行不可能解を許可. move 近傍 (制限付き)  実行不可能解を許可. Kempe Chain 近傍  実行可能解上で定義される. 24 4.3.3 補助メモリによる高速化補助メモリを用いて目的関数値の差の計算を効率的に計算できる. 補助メモリ BD(i,k) は: 点 i に色 k を塗ったときの点 i に接続する悪い枝の数を保管する配列である. 補助メモリ BD(i,k) を使うことによって, 点 i の色を k ≠ c(i) に変更したときの目的関数の差は, 下記の式によって O(1) € € € €時間で評価できる. BD(i,k) − BD(i,c(i)) € € € € € 25 4.3.4 禁断探索法禁断リスト Tabu には, 点と色のペアを保管する. 26 4.3.5 遺伝的アルゴリズムと禁断探索法の融合 1 初期解 ( K 分割) の集合 P をランダムに生成 2 3 € € € while 終了判定基準が満たされていない 1 ２つの親 Υ , do Υ 2 , を P から選択 € 2 4 親 Υ , Υ に対する交叉によって子 Υ を生成 € 5 Υ を禁断探索法によって改善 € € € 6 改善された解を P にいれて, 最も悪い解を除去 € € € 7 return P 1 € 27 END� ご清聴, ありがとうございました. 28