制約違反の十分条件を用いた組合せ制約充足／最適化

• Item type: Journal(1)
• 公開日: 1992-04-15
• タイトル: 制約違反の十分条件を用いた組合せ制約充足／最適化
• タイトル / 言語: en
• タイトル: Constraint Satisfaction and Optimization Using Sufficient Conditions for Constraint Violation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 最適化手法
• 著者所属: （株）富士通研究所人工知能研究部
• 著者所属: （株）富士通研究所人工知能研究部
• 著者所属: （株）富士通研究所人工知能研究部
• 著者所属: （株）富士通研究所人工知能研究部
• 著者所属: （株）富士通研究所人工知能研究部
• 著者所属(英): en
• 著者所属(英): Artificial Intelligence Laboratory, Fujitsu Laboratoring Ltd
• 著者所属(英): en
• 著者所属(英): Artificial Intelligence Laboratory, Fujitsu Laboratoring Ltd
• 著者所属(英): en
• 著者所属(英): Artificial Intelligence Laboratory, Fujitsu Laboratoring Ltd
• 著者所属(英): en
• 著者所属(英): Artificial Intelligence Laboratory, Fujitsu Laboratoring Ltd
• 著者所属(英): en
• 著者所属(英): Artificial Intelligence Laboratory, Fujitsu Laboratoring Ltd
• 著者名: 丸山, 文宏; 箕田, 依子; 澤田, 秀穂; 滝沢, ユカ; 川戸, 信明
• 著者名(英): Fumihiro, Maruyama; Yoriko, Minoda; Shuho, Sawada; Yuka, Takizawa; Nobuaki, Kawato
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 組合せ的な制約充足や最適化は 理論的にその困難さがわかっている(NP困難)問題であるが 工学やORの様々な局面に現れる重要な問題である本研究の目的は これらのうち制約条件が不等式および等式で表現できる問題に対して できるだけ効率のよい解法を開発することである本論文では このような問題に対する厳密解法を考察し 新しい制約充足アルゴリズムおよびこれに基づく最適化手法を提案する本手法では 制約充足処理の失敗情報として 違反の根拠を示す 制約違反の十分条件を論理式(不等式またはその論理積)で表現した制約違反条件を導入し これを最大限に利用して制約充足/最適化を行うその特徴は (1)制約違反を検出すると制約違反条件を生成・蓄積して制約を伝播し これにより未探査の解空間を削り (2)制約充足を繰り返すことにより最適化を行い (3)制約条件や評価関数が非線形の場合にも適用できる ことである実験システムを実装し例題で評価した結果 制約違反条件が解空間の絞り込みに有効であること 他の手法と比べて10倍以上高速に最適化できること 例題に関して十分実用になる性能を持つこと を確認したさらに規模の大きな問題に対しても この手法が近似解法を開発するベースになりうる
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 33, 号 5, p. 585-594, 発行日 1992-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764