静岡理工科大学 総合情報学部 (by 菅沼) 菅沼ホーム 目次 索引

システムの最適化

− 3.組合せ最適化(Combinatorial Optimization) −

  1. 3.1 分枝限定法
    1. 3.1.1 分枝操作と限定操作
    2. 3.1.2 アルゴリズム
    3. 3.1.3 分枝限定法の適用例
  2. 3.2 近似解法
  3. 3.3 人工知能的手法
    1. 3.3.1 状態空間による問題の表現
    2. 3.3.2 探索方法
  組合せ最適化問題 P0 を,定式化すれば以下のようになります.

目的関数: f(x)
制約条件: x ∈ S,ただし,S ⊂ X
   S,X: 有限個,または,可算無限個の要素を持つ離散集合

  組合せ最適化問題における困難さの一つの原因は,非線形計画法のように微分的な情報を利用できない点にあります.そこで,各 x に対して,順にその目的関数の値を調べていかざるを得ないことになります.

  S が有限個の集合であれば,理論的には,すべての組合せを調べることによって解を求めることが可能です.しかし,S の要素の数や x の次元が大きくなるにつれ,その組合せの数は膨大になり,実際にはほとんど不可能になってしまいます.

  組合せ最適化に対する手法では,如何にしてより少ない点(x)だけを調べて,最適解または最適解に近い結果を求めることができるかということ,つまり,探索の範囲を如何にして狭めるかということに重点が置かれます.
3.1 分枝限定法

3.1.1 分枝操作と限定操作

  分枝限定法は,以下の 2 つの操作を繰り返すことによって,最適解(以下の説明では,最小値)を求めようとする方法です.

  1. 分枝操作: 与えられた問題 P0 を,それらを解くことで等価的に P0 が解かれるような,つまり,

       f(P0) = min f(Pi)   f(P0),f(Pi): 問題 P0 及び Pi の最適値

    となるような部分問題 Pi(i = 1,2,・・・)に分解する操作です.ただし,最適化問題 Pi は,以下に示すような問題とします.

       目的関数: f(x)
       制約条件: x ∈ Si, Si ⊂ Xi, Xi ⊂ X, S = S ∩ (∪ Xi), Si = S ∩ Xi

  2. 限定操作: 部分問題 Pi を何らかの方法で終端させます.つまり,それ以上部分問題に分割させないようにします.そのために,部分問題 Pi よりも制約条件が緩く,解きやすい問題を考えて P’i と置きます.このような問題を緩和問題と呼び,問題 Pi の緩和問題 P’i は,以下のように定義されます.

       目的関数: g(x)
       制約条件: x ∈ S’i, Si ⊂ S’i ⊂ Xi

    制約条件を緩めてありますので,一般に,x ∈ Si となる x に対しては,g(x) ≦ f(x) のような結果になるはずです.緩和問題の性質を一般的に述べれば以下のようになり,これらの性質を利用して終端させることになります.

    1. g(P’i) ≦ f(Pi)  g(P’i): P’iの最適値(下界値と呼びます)

    2. P’i が許容解を持たなければ,Pi も持たない.

    3. P’i の目的関数に g(x) = f(x) を用いるとき,P’i の最適解が Pi の許容解であれば,それは Pi の最適解でもある.

    4. それまでに他の部分問題によってもとの問題 P0 の許容解が求められており(その中の最小値を z とする),g(P’i) ≧ z なる関係があるとき,部分問題 Pi,及び,それから生成される部分問題に対する許容解は z 以上の値を持つ.

3.1.2 アルゴリズム

  以上より,分枝限定法のアルゴリズムは以下のようになります.

  1. 初期設定: A = {P0}, z = ∞

  2. A = φ ならば終了.

    • z = ∞: 問題 P0 は解を持たない
    • z < ∞: f(P0) = z

  3. 集合 A の中から,部分問題 Pi を選択(選択方法に関しては後述)

  4. もし,緩和問題 P’i が解を持たなければ,

    1. A = A - {Pi} として,2 へ戻る

    そうでなけでば,

    1. もし,g(P’i) = f(Pi) として,Pi の最適値が得られたら,

      1. z = min {z, f(Pi)}, A = A - {Pi} として,2 へ戻る.

      そうでなければ

      1. もし,g(P’i) ≧ z ならば

        1. A = A - {Pi} として,2 へ戻る.

        そうでなければ

        1. 問題 Pi を,部分問題 Pi1,・・・,Pik に分解し, A = (A - {Pi}) ∪ {Pi1,・・・,Pik} として,2 へ戻る.

  上記のアルゴリズムにおいて,3 番目の部分,つまり,どの部分問題 Pi を選ぶべきかは,計算の挙動に大きな影響を与えます.選び方としては,以下のような方法が考えられます.

  1. 発見的探索: 各部分問題 Pi に対し,f(Pi) の推定値 h(Pi) を何らかの方法で求めておき,h(Pi) が最小の部分問題を選ぶ方法です.良い h が見つかれば,非常に優れた方法です.

  2. 最良下界探索: 発見的探索における h(Pi) として,下界値 g(P’i) を利用する方法です.

  3. 深さ優先探索: 深さが最大のものから,h あるいは g を基準に選択します.ある部分問題が分解されると,その分解された部分問題から選ばれることになります.この操作が,部分問題が終端されるまで繰り返され,終端されるとバックトラック(たどってきた道筋を戻る)します.

  4. 幅優先探索: 深さが最小のものから,h あるいは g を基準に選択します.

3.1.3 分枝限定法の適用例

  ここで,組合わせ最適化の例として,「0-1 ナップザック問題」という簡単な問題を取り上げます.「0-1 ナップザック問題」とは,容量が決まったナップザックに,何を選択して入れるのが最も効用が高いのかを決める問題であり,以下に示すように定式化できます.

[例3.1] 問題 P0
目的関数: f = -2x1 - 5x2 - 4x3 - 3x4
制約条件: x1 + 3x2 + 3x3 + 3x4 ≦ 6

  以下に,上記の問題に対し,分枝限定法を用いて解く過程について説明します.なお,部分問題 Pi の選択方法としては,以下の解法例に示すように,深さ優先探索を使用するものとします.

  1. 節点 0 問題 P0

    目的関数: f = -2x1 - 5x2 - 4x3 - 3x4
    制約条件: x1 + 3x2 + 3x3 + 3x4 ≦ 6

    の緩和問題を,変数の優先度,

    x1 → x2 → x3 → x4

    を利用して解くと,以下のようになります.

    (x1, x2, x3, x4) = (1, 1, 2/3, 0) のとき g(x) = -29/3

    明らかにこの解は,元の問題 P0 の解ではありません(制約条件を満たしていない)ので,z = ∞ とおき,変数 x3 の値により,2 つの部分問題 P1 と P2 (接点 1 と接点 2 )に分解します.

  2. 節点 1 問題 P1 (x3 = 0)

    目的関数: f = -2x1 - 5x2 - 3x4
    制約条件: x1 + 3x2 + 3x4 ≦ 6

    を解くと,以下のようになります.

    (x1, x2, x3, x4) = (1, 1, 0, 2/3) のとき g(x) = -9

    この解も,元の問題 P0 の解ではありませんので,変数 x4 の値により,2 つの部分問題 P3 と P4 (接点 3 と接点 4 )に分解します.

  3. 節点 3 問題 P3 (x3 = 0, x4 = 0)

    目的関数: f = -2x1 - 5x2
    制約条件: x1 + 3x2 ≦ 6

    を解くと,以下のようになります.

    (x1, x2, x3, x4) = (1, 1, 0, 0) のとき g(x) = -7

    この解は,元の問題 P0 の解となりますので,z = -7 とおき,終端とします.

  4. 節点 4 問題 P4 (x3 = 0, x4 = 1)

    目的関数: f = -2x1 - 5x2 - 3
    制約条件: x1 + 3x2 + 3 ≦ 6

    を解くと,以下のようになります.

    (x1, x2, x3, x4) = (1, 2/3, 0, 1) のとき g(x) = -25/3

    この解は,元の問題 P0 の解ではなく,かつ,g(x) < z ですので,変数 x2 の値により,2 つの部分問題 P5 と P6 (接点 5 と接点 6 )に分解します.

  5. 節点 5 問題 P5 (x2 = 0, x3 = 0, x4 = 1)

    目的関数: f = -2x1 - 3
    制約条件: x1 + 3 ≦ 6

    を解くと,以下のようになります.

    (x1, x2, x3, x4) = (1, 0, 0, 1) のとき g(x) = -5

    この解は,元の問題 P0 の解ですが,g(x) ≧ z ですので,終端とします.

  6. 節点 6 問題 P6 (x2 = 1, x3 = 0, x4 = 1)

    目的関数: f = -2x1 - 5 - 3
    制約条件: x1 + 3 + 3 ≦ 6

    を解くと,以下のようになります.

    (x1, x2, x3, x4) = (0, 1, 0, 1) のとき g(x) = -8

    この解は,元の問題 P0 の解となります.さらに,g(x) < z ですので,z = -8 とおき,終端とします.

  7. 節点 2 問題 P2 (x3 = 1)

    目的関数: f = -2x1 - 5x2 - 4 - 3x4
    制約条件: x1 + 3x2 + 3 + 3x4 ≦ 6

    を解くと,以下のようになります.

    (x1, x2, x3, x4) = (1, 2/3, 1, 0) のとき g(x) = -28/3

    この解は,元の問題 P0 の解ではなく,かつ,g(x) < z ですので,変数 x2 の値により,2 つの部分問題 P7 と P8 (接点 7 と接点 8 )に分解します.

  8. 節点 7 問題 P7 (x2 = 0, x3 = 1)

    目的関数: f = -2x1 - 4 - 3x4
    制約条件: x1 + 3 + 3x4 ≦ 6

    を解くと,以下のようになります.

    (x1, x2, x3, x4) = (1, 0, 1, 2/3) のとき g(x) = -8

    この解は,元の問題 P0 の解ではなく,かつ,g(x) ≧ z ですので,終端とします.

  9. 節点 8 問題 P8 (x2 = 1, x3 = 1)

    目的関数: f = -2x1 - 5 - 4 - 3x4
    制約条件: x1 + 3 + 3 + 3x4 ≦ 6

    を解くと,以下のようになります.

    (x1, x2, x3, x4) = (0, 1, 1, 0) のとき g(x) = -9

    この解は,元の問題 P0 の解であり,かつ,g(x) < z ですので,z = -9 とおき,終端とします.

  以上の結果,この問題に対する最適解は -9 となります.上に述べた手続きにおいては,問題 P0 を含め 9 つの問題を解きました.しかし,同じ深さ優先探索を用いたとしても,もし,
	P0 → P2 → P8 → P7 → P1
		
の順に問題を解けば,問題 P8 を解いた段階で z = -9 という結果が得られるため,問題 P1 を分解する必要がなくなります.つまり,問題 P3 〜 P6 を解く必要がないわけです.このように,どの部分問題 Pi を選ぶべきかは,計算の挙動に大きな影響を与え,大規模な問題の場合は,選び方によって解を得られなくなることも珍しくありません.
3.2 近似解法

  いずれの方法を採用するにしろ,組合せ最適化問題の真の最適解を求めることは非常に困難である場合が多く存在します.そこで,以下に示すように,多くの近似解法が提案されています.

  1. 欲張り法  目的関数値の良さを示す局所的評価に基づいて,可能解を直接構成していく方法です.

      たとえば,「 0-1 ナップザック問題」において,cj / aj (目的関数の係数/制約条件の係数)を評価基準として,この値が小さい順に x = 1 と固定していき,制約条件のために xj = 1 とできなくなると,以後,x = 0 とする方法がこれにあたります.

      また,「最小木問題」(無向グラフの各枝の長さ dij が与えられているとき,全節点を連結する木で,枝の長さの和が最小のものを見つける問題)において,長さ最小の枝から始め,選ばれた枝の集合が閉路を形成しないという条件の下で,長さの小さいものから順に N-1 本(N は節点数)選ぶ方法も良く知られた方法です.

  2. ランダム法  解をランダムに何個か選び,発見された可能解の中で目的関数値が最小のものを選ぶ方法です.

  3. 反復改善法(逐次改善法)  何らかの方法で得られた近似最適解に対して,その近傍,つまり少し変更を加えることで得られる他の解を調べ,改善できればそれに置き換えていく方法です.

      例えば,TSP : Traveling Salesman Problem(巡回セールスマン問題:与えられた n 個の都市に対して,各都市を一度だけ訪れ,すべての都市を訪れる経路の内,最小の経路を見つける問題)において,まず,一つの巡回路 t を見つけます.その中の k 本の枝を入れ替えて得られる巡回路が,もとの巡回路より短ければそれに置き換える,という操作を改善が得られなくなるまで繰り返す方法です.下に示す図は,k = 2 の場合であり,枝 AD と CB を入れ替えた例です. → プログラム例

  4. 緩和法  制約条件を緩和することで一つの解を求め,それに修正を加えて可能解を構成する方法です.

  5. 分割法  与えられた問題をいくつかの部分問題に分解し,それぞれの解から,もとの問題の可能解を合成する方法です.

      たとえば,TSP において,与えられた都市を複数のグループに分け,各グループ内の最適経路を見つけた後,全体の最適経路を合成する方法が相当します. → プログラム例
3.3 人工知能的手法

  人工知能分野の問題には,組合せ最適化問題として扱えるものが多く存在します.囲碁,将棋等,ゲームの問題はもちろんですが,有限個の単語の中から,翻訳文として最も適切な単語の組合せを見つける,といった意味から,機械翻訳のようなものも一種の組合せ最適化問題であるといえます.

  そこで,この節では,人工知能における探索の分野に関して簡単に説明します.

3.3.1 状態空間による問題の表現

  まず,問題の表現方法について述べます.問題を解く各段階における対象の有様や条件を状態( State )と呼びます.問題を解くということは,与えられた初期状態に,何らかの作用素( Operator )を適用して,目標状態(問題が解かれた状態)に持っていくこと,つまり,作用素の系列を見つけることに相当します.

  例えば,8 パズルについて考えてみます.8 パズルとは,下の図に示すように,与えられた初期状態(左図)を,できるだけ少ない回数のコマ(数字の書かれたものであり,1 カ所だけコマが置かれていない場所がある)移動によって,目標状態(右図)に持っていくゲームです.この問題における作用素は,コマを移動することに相当します.

  問題を解くことは,コマを移動する順番(作用素系列)を決めることになります.例えば,上の例では,以下に示すものが解になります.

  初期状態からすべての作用素を適用することにより到達可能な状態の集合を状態空間と呼びます.問題を解くためには,状態空間内を探索し,最適解を見つければよいわけですが,膨大な空間であるため全空間を探索することが不可能である場合がほとんどです.そこで,有効な探索方法が問題になってきます.

  状態空間を表現するのに,下に示すようなグラフがしばしば使用されます.グラフの各節点ノード)は状態を表し,また,は作用素を表します.節点には状態( s1 等),また,枝には作用素の種類とその作用素を適用する際のコスト(op1,3 等)を明記します.ただし,すべての作用素に対するコストが同じ場合は,コストの表記を省略します.また,右図のように,閉路のない連結グラフをと呼びます.

3.3.2 探索方法

  1. 縦型(深さ優先)探索  最も最近に生成された,すなわち,最も深い節点を最初に展開(その節点から一つの作用素で移動可能な状態を羅列する)します.発見される経路は必ずしも最短ではありません.解が存在しない部分を無意味に探索することを避けるため,一般には,深さ限界を設け,ある深さになると後戻り( back tracking )するように設定します.アルゴリズムは以下のようになります.

    1. A = {S00} とします   S00: 初期状態,
    2. A の中から,深さ d が最も深い状態 Sdi を選択し,
      • A = A - {Sdi}
      • d = Sdi の深さ
      とします.
    3. 状態 Sdi が目標状態であれば終了します.さもなければ,
      1. 深さ d が,深さ限界であれば,b へ戻ります(後戻り).さもなければ,
        • 状態 Sdi を展開
        • d = d + 1
        • 展開された状態 Sdj, ・・・ を A に追加,つまり,A = A + {Sdj, ・・・}
        とし,b へ戻ります.

      深さ制限を 3 とした場合は,下図の左図に示した順番で探索されることになります(この例では,同じ深さの場合は,図の左の節点から探索するものとする).

  2. 横型(幅優先)探索  深さが最も浅い節点から順に展開します.もし,解があるならば,最短の解系列を見つけます.そのアルゴリズムは以下のようになります.

    1. A = {S00} とします   S00: 初期状態,
    2. A の中から,深さ d が最も浅い状態 Sdi を選択し,
      • A = A - {Sdi}
      • d = Sdi の深さ
      とします.
    3. 状態 Sdi が目標状態であれば終了します.さもなければ,
      • 状態 Sdi を展開
      • d = d + 1
      • 展開された状態 Sdj, ・・・ を A に追加,つまり,A = A + {Sdj, ・・・}
      とし,b へ戻ります.

      例えば,上図の右図に示した順番で探索されることになります(この例では,同じ深さの場合は,図の左の節点から探索するものとする).

  3. 知識を用いた探索  今まで述べてきた方法は,基本的に,すべての状態を虱潰しに調べようとするものです.したがって,非常に簡単な問題を除いて,解が得られることはほとんど無いと思われます.

      人間の場合であれば,何らかの知識を使用し,調べる必要のない状態を積極的に除いた空間で探索を行っています.そこで,この知識に対応する部分を,評価関数という関数で表現し,より効率的に解を求めようとするのが知識を用いた探索方法です.知識を用いた探索方法では,1 や 2 で述べたアルゴリズムの b において,最も評価関数の値が小さなものを選択することになります.

      評価関数としては,例えば,以下のようなものが使用されます.

    f(n) = e(n) + h(n)
    f(n): 節点 n を通る最適な経路のコストの推定値
    e(n): 初期節点から節点 n までの最適な経路のコストの推定値
    h(n): 節点 n から目標節点に至る最適な経路のコストの推定値

    上記の評価関数を使用した探索において,

    h(n) ≦ h*(n)
    h*(n): 節点 n から目標節点に至る最適な経路のコストの真の値

    という関係が成立するとき,そのアルゴリズムを,A* アルゴリズムと呼びます.A*アルゴリズムでは,解経路が存在する場合,必ず最小コスト経路解を発見します.A*アルゴリズムにおいて,

    h1(n) > h2(n)

    なる関係があるとき,「アルゴリズム A1 は A2 よりも,より知識がある」といいます.

      また,すべての枝が均一のコストを持つとき,知識を用いた探索と,縦型探索及び横型探索とは,以下のような関係があります.

    • h(n) = 0, e(n) = 深さ → 横型探索
    • h(n) = 0, e(n) = -深さ → 縦型探索

[探索の例: 8 パズル]  以下,上記で述べた探索方法を,下に示す 2 つの 8 パズルの問題に適用した例について述べていきます.なお,得られた結果は,私の作成したプログラムによって得られたものであり,結果の数値に絶対的な意味はありません.

  1. 横型探索  左側の問題(最適解: 5 回のコマの移動)に対しては,45 個の節点を展開することによって,最適解を得ることができましたが,右側の問題(最適解: 18 回のコマの移動)に対しては,2000 個以下の節点の展開では不可能でした.

  2. 縦型探索  左側の問題に対しては,深さ限界を 5 とし,30 個の節点を展開することによって,最適解を得ることができましたが,右側の問題に対しては,2000 個以下の節点の展開では不可能でした.

  3. 評価関数を利用した探索  ここでは,2 つの評価関数を使用して,探索を行ってみます.

    1. 評価関数は,以下の通りとします.

      f(n) = g(n) + h(n)
      g(n): 節点 n の深さ
      h(n): 節点 n の状態で,誤って置かれているコマの数

      明らかに,これは,A* アルゴリズムとなっています.左側の問題に対しては,6 個の節点を展開することによって,最適解を得ることができました.また,右側の問題に対しても,1858 個の節点を展開することによって,最適解を得ることができました.

    2. 評価関数は,以下の通りとします.

      f(n) = g(n) + h(n)
      g(n): 節点 n の深さ
      h(n) = p(n) + 3s(n)
      p(n): 各コマの正しい位置からの距離を加えた値
      s(n): 中心以外のコマに対し,その次のコマが正しい順序になっていなければ 2,そうでなければ 0,中心の駒には 1 を与える事によって得られる得点

      これは,A* アルゴリズムとはなっていません.しかし,8 パズルに対しては,非常に高速に解を求めることができます(得られた結果は,必ずしも最適解ではない).上の例の場合,左側の問題に対しては,5 個の節点を展開することによって,最適解を得ることができました.また,右側の問題に対しても,32 個の節点を展開することによって,最適解を得ることができました.

静岡理工科大学 総合情報学部 (by 菅沼) 菅沼ホーム 目次 索引