適応型確率探索による制約充足問題の解法

機関リポジトリ 情報処理学会 HANDLE Web Site 被引用文献3件 参考文献15件 オープンアクセス

書誌事項

タイトル別名
  • Solving Constraint Satisfaction Problems by an Adaptive Stochastic Search Method
  • テキオウガタ カクリツ タンサク ニ ヨル セイヤク ジュウソク モンダイ ノ

この論文をさがす

説明

近年，大規模な制約充足問題に対して，確率的探索アルゴリズムにおける局所最適解からの脱出のためのメタ戦略に関する研究が注目されている．代表者なメタ戦略としてシミュレーテッド・アニーリング（SA）法があげられるが，状態遷移確率を決めるパラメータ（温度）のスケジューリングが難しい．そこで本論文では，このスケジュールを与えられた問題に応じて自動的に決定する手法を提案する．本手法は，まず，異なる温度を持つ集団を複数個生成し，各集団に均等に解候補を割り振る．次に，解に収束するまで探索を行う処理と集団を再編成する処理を繰り返す．探索を行う処理では，確率的山登り法による探索を一定回数行う．集団を再編成する処理では，各集団の評価値を求め，評価値の低い集団から評価値の高い集団へ解候補を移動する処理を行う．本手法は，SAにおける温度の時間的な進移を，空間的な分布に置き換えたものである．本手法を大規模，かつ制約密度の低いグラフ色塗り問題に適用して，ランダムな初期値からSAを繰り返す方法より有効であることを詳細な実験で確認した．

A meta-heuristics for escaping from local optima to solve large constraint satisfaction problems is proposed,which gives a method of automatic temperature control in simulated annealing(SA)approach.First,in our method,several groups with different temperatures are created,in each of which the same number of candidate solutions are stored.Then,the main process is repeated until the system comes to a certain convergence.The main process is composed of two phases:searching,or an ordinal stochastic hill-climbing,and population tuning,or temperature adjustment.As to the latter phase,after evaluating the average adaptation value per each group,migration operations of some number of candidate solutions from groups with lower values to groups with higher values are induced.This method represents a temporal change of the temperature in SA,sa spatial distribution of the temperature.The method is applied to large scale graph-coloring problems of sparsely-connected,whose experimental simulations prove our meta-heuristics to be more efficient than ramdomly restarting SA.

収録刊行物

被引用文献 (3)*注記

もっと見る

参考文献 (15)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ