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

スポンサーリンク

概要

• 論文の詳細を見る

• 組合せ的な制約充足や最適化は,理論的にその困難さがわかっている(NP困難)問題であるが,工学やORの様々な局面に現れる重要な問題である.本研究の目的は,これらのうち制約条件が不等式および等式で表現できる問題に対して,できるだけ効率のよい解法を開発することである本論文では,このような問題に対する厳密解法を考察し,新しい制約充足アルゴリズムおよびこれに基づく最適化手法を提案する.本手法では,制約充足処理の失敗情報として,違反の根拠を示す,制約違反の十分条件を論理式(不等式またはその論理積)で表現した制約違反条件を導入し,これを最大限に利用して制約充足/最適化を行う.その特徴は,(1)制約違反を検出すると制約違反条件を生成・蓄積して制約を伝播し,これにより未探査の解空間を削り,(2)制約充足を繰り返すことにより最適化を行い,(3)制約条件や評価関数が非線形の場合にも適用できる,ことである実験システムを実装し例題で評価した結果,制約違反条件が解空間の絞り込みに有効であること,他の手法と比べて10倍以上高速に最適化できること,例題に関して十分実用になる性能を持つこと,を確認した.さらに規模の大きな問題に対しても,この手法が近似解法を開発するベースになりうる.

• 一般社団法人情報処理学会の論文
• 1992-05-15

著者

• 丸山 文宏

  (株)富士通研究所

• 川戸 信明

  (株)富士通研究所ソフトウェア研究部

• 丸山 文宏

  欧州富士通研究所

• 澤田 秀穂

  (株)富士通研究所人工知能研究部

• 箕田 依子

  (株)富士通研究所人工知能研究部

• 滝沢 ユカ

  (株)富士通研究所人工知能研究部

• 箕田 依子

  (株)富士通研究所

関連論文

• 知的エージェント環境SAGEの企業間ECへの応用 : 仮想カタログの概念に基づくSAGE : Francis(ソフトウェアエージェントとその応用論文特集)
• SAGE : 仮想カタログ データベースのエージェント化
• SAGE : 仮想カタログ ユーザエージェント
• SAGE : 仮想カタログ システムデザイン
• SAGE (Smart AGent Environment) : 仮想カタログ
• 5. 最近のCADシステムの話題 5.5 論理装置のCAD における知識工学の応用 (論理装置CADの最近の動向)
• ハードウェア設計言語DDLによる計算機設計支援システム
• 連載「計画問題と人工知能」にあたって
• 4. オブジェクト指向データベースの応用 4.3 エンジニアリング業務支援とオブジェクト指向データベース (オブジェクト指向データベースシステム)
• 第2回 最近の英国事情(欧州駐在員便り)
• エージェントによるアプリケーション
• 情報工学科の学生に望むこと
• 小特集「数理計画法と人工知能技術の融合」にあたって
• 論理に基づく論理設計支援 (「VLSI-CADと人工知能」)
• 特集「VLSI-CADと人工知能」にあたって
• 5.オフィスと人工知能技術(人工知能技術と産業応用)
• ソフトウェアエージェントのECへの応用
• ECにおける商品情報検索のためのエージェント技術
• 2. 方式・機能・論理設計におけるCAD 2.5 方式・機能・論理設計の検証 (論理装置CADの最近の動向)
• ハードウェアの機能設計段階における検証
• 分権コンピューティングと仲介エージェント (「創造的ネットワーク化情報環境に向けて」)
• VLSI CADへの知識工学の応用
• VLSI CADへのエキスパートシステム技術の適用(エキスパートシステム)
• 小特集「論理型言語とその処理系」の編集にあたって
• 論理回路設計環境の構想
• 制約違反の十分条件を用いた組合せ制約充足/最適化
• 協調型論理設計エキスパートシステムco-LODEX : 試作
• 協調型論理設計エキスパートシステムco-LODEX : 概要
• 疎結合マルチプロセッサ上での論理回路遅延時間計算の並列化
• 藤代一成 著, "CAD/CAM", マルゼンアドバンストテクノロジー 電子・情報・通信編, 丸善, A5判, 274p., \4,738, 1990
• ビジネスモデルの記述に関する一考察(インタプライスモデル化技術,一般)
• ビジネスモデル実現のための構成要素に関する一考察(インタプライズモデル化,一般)

もっと見る 閉じる

スポンサーリンク