制約充足問題に対する ACO の動的パラメータ調整有効性の検討

制約充足問題に対する ACO の動的パラメータ調整の有効性

の検討

Dynamic parameter tuning for ACO solving CSPs

戸谷 太亮

1

_{水野 一徳}

1

_{増金 拓弥}

1

Takaaki.T

1

_{, Kazunori. M}

1

_{, and Takuya. M}

1 1

_{拓殖大学工学部情報工学科}

1

_{Department of Computer Science, Takushoku University}

Abstract: Ant colony optimization, ACO, has been effective meta-heuristics to solve large-scale constraint

satisfaction problems, CSPs. In ACO based algorithms, we need to set the parameters, how pheromone is important and how constraint violations are important, respectively. In this paper, we apply the PSOACO, which is the ACO based algorithm for combinatorial optimization problems, to CSPs to tune such the parameters dynamically. We also have demonstrated how effective the PSOACO can be to solve hard instances of graph coloring problems that is one of CSPs.

1 はじめに

制約充足問題(Constraint Satisfaction Problem: CSP) とは，離散値をとるいくつかの変数に割当て可能な 値の組合せのうち，与えられた全ての制約を満たす ものを，探索によって発見する問題である．CSP は， 設計や計画問題をはじめ，人工知能分野やパターン 処理などの広い分野にわたって応用されている基盤 的技術である． 大規模なCSP を効率よく解くための手法として近 年では，解候補を反復改良していく確率的探索アル ゴリズムの研究が盛んに行なわれている．確率的探 索アルゴリズムは，アルゴリズムの完全性が保証さ れていないものの，実用的な時間内に高い確率で問 題の解を発見しようというものである．しかし，確 率的探索アルゴリズムには，局所最適解に捕捉され てしまう可能性があるという欠点がある．そのよう な局所最適解に陥らないようにする，あるいは局所 最適解に陥ってしまった際に効率よく抜け出すため のメタヒューリスティクスに関する研究が盛んに行 なわれている．

蟻コロニー最適化(Ant Colony Optimization: ACO)

は，蟻の採餌行動におけるフェロモンコミュニケー ションから着想を得たメタヒューリスティクスであ

り ， 巡 回 セ ー ル ス マ ン 問 題(Traveling Salesman

Problem: TSP)のような組合せ最適化問題や，グラフ 彩色問題(Graph Coloring Problem: COL)のような CSP

に有効な手法として研究されている[1][2][3][4][5]． ACO に基づくアルゴリズムでは，各世代で得られた， 最も評価が高い解候補を用いて，フェロモングラフ の更新が行なわれる．また，フェロモングラフと制 約違反数をもとに，解候補の構築が行なわれる． ACO に基づくアルゴリズムでは，フェロモンと制約 違反数を重視する重み係数をそれぞれ設定する必要 があるが，最適な重み係数の値はインスタンス毎に 異なる．これらの重み係数の値を動的に調整するア ルゴリズムとして，PSOACO が提案されている．

PSOACO で は ， 粒 子 群 最 適 化 (Particle Swarm Optimization: PSO)[6]を用いて，重み係数の値の最適 化が行なわれる．文献[1]では，組合せ最適化問題で ある TSP を対象に，PSOACO の有効性を示してい る． 本研究では，PSOACO を CSP に適用する．また， CSP の 1 つである COL を対象に，PSO による重み 係数の値の調整がCSP を効率よく解くのに有効であ るかを，実験的に評価する．

2 研究分野の概要

2.1 グラフ彩色問題

本稿ではCSP を，(X, D, C)の 3 つ組で定義する． X (= {𝑥1, …, 𝑥𝑛})は，n 個の変数の有限集合を表す． 𝐷𝑖∈ 𝐷は，変数𝑥𝑖に割当て可能な値の有限集合を表 す．C (= {𝑐1, …, 𝑐𝑚})は，変数間に割当てに関する m 個の制約の有限集合を表す． グラフ彩色問題(COL)とは，無向グラフの各頂点 人工知能学会研究会資料 SIG-FPAI-B901-06

begin while (問題が解ける or 世代数の上限に達するまで) do while (全ての蟻が解候補を生成するまで) do 解候補の生成 end while フェロモンの蒸発 while (全ての蟻がフェロモンを蓄積するまで) do 各蟻によるフェロモンの蓄積 end while while (全ての蟻が Pbest を更新するまで) do Pbest の更新 end while Gbest の更新 while (全ての蟻がパラメータを更新するまで) do 各蟻のパラメータの更新 end while end while end Fig. 1 提案するアルゴリズム に，隣接する頂点の色が同じにならないように彩色 する問題である．上述したCSP の定義に対応させる と，無向グラフの頂点の集合が X，割当てる色の集 合がD，無向グラフの辺の集合が C を表す．特に 3 色で彩色を行なう3COL は，組合せ探索アルゴリズ ムの性能を評価するためのベンチマークとしてしば しば用いられる[2][5]．|X| = n，|C| = m を用いて，制 約密度d = m / n を定義する．先行研究から，d = 2.3 ~ 2.4 の領域には解くのに非常にコストがかかる，難 しい問題が集中していることがわかっている[2][5]． 本研究では，このような難しい問題が集中している 領域を含む，d = 2.0 ~ 3.0 の領域の 3COL を対象に， 提案する組合せ探索アルゴリズムの評価を行なう．

2.2 PSOACO

ACO は，蟻の採餌行動におけるフェロモンコミュ ニケーションをモデル化したメタヒューリスティク スである[4]．ACO に基づくアルゴリズムでは，各世 代で得られた評価が高い解候補を用いて，フェロモ ングラフを更新する．また，このフェロモングラフ と制約違反数に基づいて，解候補を確率的に構築し ていくことで探索を行なう． ACO アルゴリズムを用いて探索を行なう際，パラ メータとして，フェロモンを重視する重み係数の値 𝛼と，制約違反を重視する重み係数の値𝛽を設定する 必要がある．しかし，最適なパラメータの値はイン スタンス毎に異なる．PSOACO は，それらのパラメ ータを動的に調整するために，組合せ最適化問題に 有効である PSO[4]というメタヒューリスティクス を用いる ACO アルゴリズムである．文献[1]では， 組合せ最適化問題であるTSP を対象に，PSO を用い てパラメータを調整することの有効性を実験的に示 している．

2.3 PSOACO の問題点

組合せ最適化問題のみならず，CSP を対象とした ACO アルゴリズムにおいても，フェロモンを重視す る重み係数の値と，制約違反を重視する重み係数の 値を設定する必要がある．しかし，PSOACO は組合 せ最適化問題にのみ適用されているため，PSOACO をCSP に適用させる必要がある． また，文献[1]で提案される PSOACO では，調整さ れるパラメータ𝛼，𝛽の値に上限が設けられていない． そのため，𝛼と𝛽の値が大きく離れてしまうことで探 索が発散してしまう可能性が考えられる．

3 提案手法

3.1 概要

CSP を対象とする ACO アルゴリズムにおいても， 2.2 節で述べた𝛼と𝛽の値をそれぞれ設定する必要が ある．そこで本研究では，文献[1]で提案された組合 せ最適化アルゴリズムであるPSOACO を，CSP の 1 つである 3COL に適用する．また，2.3 節で述べた PSOACO の欠点を改善するために，本研究で提案す るPSOACO では，𝛼と𝛽の値に上限を設け，探索の効 率化を図る．本提案アルゴリズムの基本方針は，以 下の2 点である． ⚫ 蟻ごとに，異なる𝛼と𝛽の値を設定する． ⚫ 各世代の最後に PSO を用いて，各蟻の𝛼と𝛽の 値を更新する．

3.2 アルゴリズム

本研究で提案するアルゴリズムをFig. 1 に示す． 各蟻は，1 つの解候補と，蟻ごとに値が異なるパラメ ータ𝛼と𝛽を持つ．各蟻は，変数をランダムに 1 つ選 択し，蓄積しているフェロモンの量と制約違反数か ら確率的に値の割当てを行なう．以下に，解候補 A の変数𝑥𝑗に値 v を割当てる際の確率𝑝𝐴(< 𝑥𝑗, 𝑣 >)を 以下に示す． 𝑝𝐴(< 𝑥𝑗, 𝑣 >) = [𝜏𝐴(<𝑥𝑗,𝑣>)]𝛼[𝜂𝐴(<𝑥𝑗,𝑣>)]𝛽 ∑_𝑤∈𝐷[𝜏_𝐴(<𝑥_𝑗,𝑤>)]𝛼[𝜂_𝐴(<𝑥_𝑗,𝑤>)]𝛽 ,

𝜏𝐴(< 𝑥𝑗, 𝑣 >) = ∑<𝑥𝑘,𝑢>∈𝐴𝜏(< 𝑥𝑘, 𝑢 >, < 𝑥𝑗, 𝑣 >) , 𝜂𝐴(< 𝑥𝑗, 𝑣 >) = 1 1 + 𝑐𝑜𝑛𝑓({< 𝑥𝑗, 𝑣 >∪ 𝐴}) − 𝑐𝑜𝑛𝑓(𝐴) ただし，𝜏(< 𝑥𝑘, 𝑢 >, < 𝑥𝑗, 𝑣 >)はフェロモングラフ上 の辺(< 𝑥𝑘, 𝑢 >, < 𝑥𝑗, 𝑣 >)に蓄積しているフェロモン 量を，𝑐𝑜𝑛𝑓(𝐴)は解候補 A の制約違反数をそれぞれ 表す．全ての蟻が解候補を構築し終わると，各蟻が 生成した解候補に基づいて，フェロモングラフが更 新される．その後，各蟻が持つパラメータ𝛼と𝛽が更 新される．これらの処理を1 つの世代とし，制約違 反のない解が発見されるか，与えられた世代数の上 限まで探索を行なう．

3.3 フェロモングラフの更新

本研究ではフェロモングラフの構造を，以下に示 すグラフ構造G = (V, E)で定義する． 𝑉 = {< 𝑥𝑖, 𝑣 >|𝑥𝑖∈ 𝑋 𝑎𝑛𝑑 𝑣 ∈ 𝐷} 𝐸 = {(< 𝑥𝑖, 𝑣 >, < 𝑥𝑗, 𝑤 >) ∈ 𝑉2|𝑥𝑖≠ 𝑥𝑗} フェロモングラフの更新は，フェロモンの蒸発と 蓄積からなる．以下にフェロモンの蒸発の式を示す． 𝜏(𝑖, 𝑗) = (1 − 𝜌) × 𝜏(𝑖, 𝑗) ただし，𝜌はフェロモンの蒸発率を表す．フェロモン の蒸発により，フェロモングラフの各辺に蓄積して いるフェロモンの量を減少させる．その後，各蟻が 持つ解候補に基づいて，フェロモンの蓄積が行なわ れる．以下にフェロモンの蓄積の式を示す． 𝜏(𝑖, 𝑗) = { 1 𝑐𝑜𝑛𝑓(𝐴), (𝑖, 𝑗) ∈ 𝐴 0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 フェロモンの蓄積では，多くの解候補に(i, j)が含ま れているほど，(i, j)を含む解候補の制約違反数が少 ないほど，フェロモングラフの辺(i, j)に蓄積される フェロモンの量は多くなる．

3.4 パラメータの調整

PSOACO では，各世代の最後に，メタヒューリス ティクスである PSO を用いて，パラメータ𝛼と𝛽の 調整を行なう．パラメータ更新のための式を以下に 示す 𝑉𝛼𝑘𝑡+1= 𝑉𝛼𝑘𝑡+ 𝑟1 𝑐1(𝛼𝑃𝑏𝑒𝑠𝑡_𝑘− 𝛼𝑘𝑡) +𝑟2 𝑐2(𝛼𝐺𝑏𝑒𝑠𝑡− 𝛼𝑘𝑡); 𝑉𝛽𝑘𝑡+1= 𝑉𝛽𝑘𝑡+ 𝑟1 𝑐1(𝛽𝑃𝑏𝑒𝑠𝑡_𝑘− 𝛽𝑘𝑡) +𝑟2 𝑐2(𝛽𝐺𝑏𝑒𝑠𝑡− 𝛽𝑘𝑡); 𝛼𝑘𝑡+1= 𝛼𝑘𝑡+ 𝑉𝛼𝑘𝑡+1; 𝛽𝑘𝑡+1= 𝛽𝑘𝑡+ 𝑉𝛽𝑘𝑡+1; 𝛼𝑘𝑡, 𝛽𝑘𝑡, 𝑉𝛼𝑘𝑡，𝑉𝛽𝑘𝑡はそれぞれ，世代t の k 番目の蟻 の持つ𝛼，𝛽，𝛼成分の速度，𝛽成分の速度である．r1， r2は乱数である．c1とc2は，それぞれPbest，Gbest の重み係数である．𝛼𝑃𝑏𝑒𝑠𝑡𝑘，𝛽𝑃𝑏𝑒𝑠𝑡𝑘,，𝛼𝐺𝑏𝑒𝑠𝑡，𝛽𝐺𝑏𝑒𝑠𝑡 はそれぞれ，k 番目の蟻の持つ Pbest の𝛼，𝛽，Gbest の持つ𝛼，𝛽である． Pbestkは，k 番目の蟻に割り当てられたパラメータ 𝛼と𝛽の値の組み合わせの内，もっとも評価の高いも のである．Gbest は，すべての蟻において，いままで 割り当てられたパラメータの値の組み合わせの内， 最も評価の高い組み合わせである． また，パラメータの値の組み合わせの評価は，そ のパラメータを割り当てられているときに発見した 解候補の，最も高い評価値である．今回は，発見し た解候補の制約違反数が，パラメータの評価となる．

4 評価実験

4.1 実験条件

3 章で提案したアルゴリズムの性能を評価するた め，実験を行なった．ここでは，次の4 つの条件を 適用した4 つのアルゴリズムで実験を行った． ⚫ 条件 1: 𝛼と β の値を，PSO を用いて調整する． ⚫ 条件 2: 𝛼の値を固定し，β の値のみを，PSO を用いて調整する． ⚫ 条件 3: α と β の値を，ランダムに変更する． ⚫ 条件 4: 𝛼の値を固定し，β の値のみをラ ンダムに変更する． 条件1 と 3，条件 2 と 4 をそれぞれ比較し，PSO を 用いてパラメータを調整することの有効性を調査す る．また，条件1 と 2，条件 3 と 4 をそれぞれ比較 し，2 変数の最適化を行なう場合と１変数の最適化 を行なう場合における，探索結果の違いについて調 査する． 実験には，頂点数100 の 3COL を用いる．制約密 度が2.0～3.0 の範囲で，0.1 ごとに制約密度が異なる 問題を，10 問ずつランダムに生成した．ここで生成 した問題は全て，解が存在するものである．また， 各アルゴリズムは1 つの問題に対して 10 回の探索 を試行する．よって，各アルゴリズムは，各制約密 度の問題を合計100 回試行する．表 1 と表 2 に，本 実験におけるアルゴリズムのパラメータを示す．

表1: 条件 1～4 において共通する実験条件 蟻の数 20 匹 世代数の上限 1000 初期フェロモン蓄積量 1.0 蒸発率 0.2 𝛼の初期値の範囲 0 ≤ 𝛼 ≤ 20 𝛽の初期値の範囲 0 ≤ 𝛽 ≤ 20 𝛼の上限，下限 0 ≤ 𝛼 ≤ 20 𝛽の上限，下限 0 ≤ 𝛽 ≤ 20 𝛼成分の速度の上限 なし 𝛽成分の速度の上限 なし 𝑐1 1.0 𝑐2 1.0 𝑟1 0 ≤ 𝑟1≤ 1.0 𝑟2 0 ≤ 𝑟2≤ 1.0 パラメータ変更の間隔 毎世代ごと 表2: 条件 2，4 に追加される実験条件 𝛼の値 1.0 (常に固定) 本実験で評価する項目は，次の3 点である． 1． 探索成功率(%): 探索を行なった全ての試行の うち，探索に成功した(解を発見できた)試行の 割合 2． 探索コスト: 解を発見するまでに生成した解 候補の数(ただし，解を発見できなかった試行 については，探索コストを蟻の数 × 世代数 = 20,000 とする) 3． 探索時間(ms): 探索に成功した試行を対象に した，試行1 回あたりの平均実行時間

4.2 実験結果

Fig. 1，2，3 にそれぞれ，探索成功率，探索コスト， 探索時間の実験結果を示す．ただし，Fig. 3 において， 1 つの制約密度における試行で 1 度も解を発見でき なかった場合，探索時間を0 とした． Fig. 2 より，条件 1 と 3 を適用したアルゴリズム では，解をほとんど発見できていないことがわかる． 特に，条件3 のアルゴリズムは，制約密度が 2.0 と 2.6 以外の領域では，探索に成功した試行は 1 度もな い．一方で，条件2 と 4 を適用したアルゴリズムは， 比較的高い確率で解を発見できている．また，全て の制約密度で，条件2 のアルゴリズムの探索成功率 が，条件4 のアルゴリズムの探索成功率を上回って いる．これらの結果から，パラメータをランダムに 変更するよりPSO を用いて調整する方が，また，𝛼 と𝛽を調整するより𝛽のみを調整する方が，高い確率 で解を発見できると考えられる． 次に，Fig. 3 より，条件 2 と 4 のアルゴリズムの 方が，条件1 と 3 のアルゴリズムより少ない探索コ Fig. 2 探索成功率の実験結果 Fig. 3 探索コストの実験結果 ストで解を発見できている．さらに，条件4 より条 件2 の方が，条件 3 より条件 1 の方が少ない探索コ ストで解を発見できている．この探索コストの違い は，探索成功率の違いによるものである．探索に失 敗し，解が発見できなかった場合，20,000 の探索コ ストがかかってしまう．逆に，探索に成功した場合， 20,000 より少ないコストで探索を終えることができ る．そのため，探索成功率が高いアルゴリズムの方 が，探索に必要なコストも少なく抑えられると考え られる． 最後に，Fig. 4 より，条件 2 と 4 のアルゴリズムの 方が，条件1 のアルゴリズムよりも少ない実行時間 で解を発見できていることがわかる．この結果から， 𝛼と𝛽の両方を調整するよりも，𝛽のみを調整する方 が，実行時間が少なく済むことがわかる． 以上のことから，𝛼の値を固定し，𝛽の値のみを調 整するほうが，解の発見率が高く，必要な探索コス トと探索に必要な実行時間が少なく済むことがわか る．

Fig. 4 探索時間の実験結果 Fig. 5 条件 4 での各蟻の𝛽の推移

4.3 考察

本節では，パラメータ𝛽の値の調整を行なったこ とが，探索成功率の向上につながった原因について 考察する．Fig. 5 ~ 7 は，解を発見した，異なる 3 つ の試行において，全ての蟻の𝛽の値を世代毎に示し たものである．そのため，各世代で蟻の数 = 20 個分 のプロットがなされている．また，各グラフの右端 は，解を発見した世代数となっている．Fig. 5 は𝛼の 値を固定し，𝛽の値をランダムに変更するもの(4.1 節 における条件4)であり，Fig. 6 と 7 は，𝛼の値を固定 し，𝛽の値を PSO によって調整するもの(4.1 節にお ける条件2)である．Fig. 5 と比較して，Fig. 6 と 7 は 探索が進むにつれて，各蟻の𝛽の値が収束している のがわかる．このことから，Fig. 6 と 7 の試行では， 探索に適した𝛽が存在し，PSOACO を用いることで 適した𝛽の値へ蟻の集団全体が収束しているのでは ないかと考える．また，Fig. 6 と 7 のどちらも，𝛽が 上限値である 20 に収束しており，𝛽に適した値が， 実際は20 より大きいことが考えられる．そのため， 𝛽の上限値をより大きくすることで，探索成功率の 上昇や探索コストの削減などの，更なる探索性能の 向上が期待される． Fig. 6 条件 2 での各蟻の𝛽の推移の一例(1) Fig. 7 条件 2 での各蟻の𝛽の推移の一例(2)

5 おわりに

本研究では，ACO アルゴリズムにおけるパラメー タである，フェロモンを重視する重み係数𝛼と制約 違反を重視する重み係数𝛽の値を動的に設定するア ルゴリズムを提案した．本アルゴリズムは，𝛼と𝛽の 値を，PSO を用いて最適化するアルゴリズムである． CSP の 1 つである 3COL を対象に，本アルゴリズム の有効性を実験的に示した．また，𝛼と𝛽の値の両方 を最適化するよりも，𝛼の値を固定し，𝛽の値のみを 最適化する方が，より効率的な探索が行なわれるこ とを示した． 本研究の今後の課題として，他の探索アルゴリズ ムとの性能の比較や，𝛽の上限値に応じた探索性能 の調査が挙げられる．

参考文献

[１] Mahi, Mostafa, Ömer Kaan Baykan, and Halife Kodaz. "A

new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem." Applied Soft Computing 30 (2015): 484-490.

[２] 増金拓弥, 水野一徳. “複数種類のフェロモンを用 いた cAS による制約充足問題の解法.” 人工知能 学会全国大会論文集 第 32 回全国大会 (2018). 一 般社団法人 人工知能学会, 2018. [３] 筒井茂義. "ACO: アントコロニー最適化 (< 特集> 進化計算の新展開)." システム/制御/情報 52.10 (2008): 390-398.

[４] Dorigo, Marco., Vittorio. Maniezzo, and Alberto. Colorni.

“Ant system: optimization by a colony of cooperating agents.” IEEE Transactions on Systems, Man, and

Cybernetics, Part B (Cybernetics) 26.1 (1996): 29-41.

[５] Mizuno, Kazunori, et al. "Solving constraint satisfaction

problems by ACO with cunning ants." 2011 International

Conference on Technologies and Applications of Artificial Intelligence. IEEE, 2011

[６] J. Kennedy, R. Eberhart, Particle swarm optimization, in: 1995 IEEE International Conference on Neural Networks Proceedings, vols. 1–6, 1995, pp. 1942–1948.