適応型確率探索による制約充足問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
近年、大規模な制約充足問題に対して、確率的探索アルゴリズムにおける局所最適解からの脱出のためのメタ戦略に関する研究が注目されている。代表的なメタ戦略としてシミュレーテッド・アニーリング(SA法が挙げられるが、確率パラメータ(温度)のスケジュール管理が難しい。そこで本論文では、このスケジュールを問題に応じて自動的に決定する手法を提案する。本手法は、複数個の解候補を異なる確率パラメータを持つ集団に均等に割り振り、確率的山登り法による探索を行うものである。また、探索の途中で、集団の評価値を求め、評価値の低い集団から高い集団へ解候補を移動する処理を行う。本手法を大規模、かつ制約密度の低いグラフ色塗り問題に適用して、ランダムな初期値からSAを繰り返す方法より探索成功率が高いことを詳細な実験で確認した。
- 1997-05-26
著者
関連論文
- 知識ベースに基づく点字翻訳のための日本語文節区切り手法
- 知識べースに基づく点字翻訳のための日本語文書分かち書き手法
- 1K-1 ビルボードを用いた都市空間の高速表示
- 5C-4 セルオートマトンによる仮想都市空間内の土地利用変化シミュレーション(複雑系,一般セッション,人工知能と認知科学)
- 5S-5 Binary CSPのための制約違反最小化戦略に基づくハイブリッド型Ant Systemの提案(認知・推論・探索,学生セッション,人工知能と認知科学)
- 5S-4 極小非可解構造の埋め込み操作による3COLインスタンスの組織的生成(認知・推論・探索,学生セッション,人工知能と認知科学)
- 極小非可解構造の埋め込みによる難しい3-COLインスタンスの組織的生成 (特集 「機械学習の諸科学への応用」および一般)
- 1ZE-4 制約充足に基づく図面理解システムのGUI開発(CG:モデリング,探索,学生セッション,インターフェース)
- 3V-1 マルチエージェント型交通シミュレータと歩行者エージェントの導入(マルチエージェント(1),学生セッション,人工知能と認知科学)
- 1V-5 蟻の集団を用いたBinaryCSPの解法(学習・推論,学生セッション,人工知能と認知科学)
- 6C-7 仮想都市における交通シミュレーションによる動的経路選択の有用性の検証(ニューラルネット・マルチエージェント,一般セッション,人工知能と認知科学)
- 資源割当てを伴う複数経路探索における対話的制約充足
- 極小非可解構造に基づく3COLインスタンスの組織的生成(人工知能,認知科学)
- 時間変化する仮想都市における道路網の自動生成
- 事例知識を用いた日本語点字翻訳とエラー修正支援
- 事例ベース推論と制約充足に基づく室内レイアウト変更計画(自動推論 : 演繹, 帰納, モデル検査/生成, 仮説推論アブダクション, 論理プログラム, プランニング, 時相論理, etc.)
- 確率的制約充足アルゴリズムにおける局所最適構造
- 1N-3 制約充足問題における制約構造に注目した計算複雑さの考察
- 極小非可解構造に基づく連結度を考慮した3COLインスタンスの組織的生成 (特集 「知識発見の生命科学への応用」および一般)
- 点連結度に注目した難しい3COLインスタンスの組織的生成 (特集 「ベイジアン・ネットワークと応用」および一般)
- 併合法による制約充足の並列化効果について
- 表層解析に基づく点字用日本語分かち書きへの事例ベースの適用
- 角運動量変化を利用した力覚提示デバイス
- 制約グラフの局所性を用いた併合法の並列化について
- バックトラック無しアルゴリズムの実験評価
- あいまいな三面図の概略理解手法
- ウイルス感染を用いた遺伝的アルゴリズムによるニューラルネットワークの学習(進化的計算)
- 知識の集団を用いたGAによる不特定な立ち寄り地を含む経路探索
- 制約に基づく対話型室内レイアウトシステム
- 三面図解釈における組合せ探索法の効率改善
- ウイルス進化論に基づく制約充足問題の解法
- ウイルス進化論に基づく制約充足問題の解法
- オブジェクト指向を用いた計算機使用支援のための知識ベースシステム
- 1W-3 連結度に注目した難しい3彩色インスタンスの組織的生成(最適化,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 遺伝的アルゴリズムを用いたバーチャルワールドの生成
- Lシステムを用いた道路網の生成
- F-023 制約充足問題のためのランク付け機能を有するACOの局所探索による解候補育成(F分野:人工知能・ゲーム,一般論文)
- 1W-2 制約充足に基づく勤務シフトスケジューリング(最適化,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- F-017 Binary CSPのための制約違反最小化戦略のハイブリッド型Ant Systemの効果(人工知能・ゲーム,一般論文)
- 地形を考慮したLシステムに基づく仮想都市のための道路網の生成
- ニューラルネットワークの集団を用いた制約充足問題の解法
- 交通信号制御のための分散制約充足方式の提案 (テーマ:知能・適応と社会,ネットワーク) -- (マルチエージェントシステム)
- 適応型確率探索による制約充足問題の解法
- 対話的図形描画のための幾何制約ソルバ
- 特徴的幾何形状マッチングによる不完全三面図からの3次元モデル復元
- 事例を用いたオンライン点字翻訳支援システム
- 制約充足に基づく三面図理解システム
- 板金物体を対象とした省略のある三面図の復元手法
- ウイルス進化論に基づくGAによるカーナビのための実時間経路探索
- 概整合ラベリング問題の並列解法と効率評価
- 許容度を有する整合ラベリング問題解法の効率化とシステムについて
- 適応型確率探索による制約充足問題の解法
- 適応型確率探索による制約充足問題の解法
- Swarmを用いたデマンドバスのシミュレーション環境の構築
- エッシャー風タイリング画像作成支援システム
- F-034 グラフ彩色インスタンス生成のためのGAに基づく極小非可解構造の導出(知能システム,F分野:人工知能・ゲーム)