平成８年度第１回KSMAP

日時：　平成９年５月３０日（木）午後３時〜５時
場所：　住友金属工業株式会社 　　　　大阪市中央区北浜東２ー１６
　　　　日刊工業新聞社ビル　１０Ｆ　Ｃ会議室

帰納的学習によるスケジューリング・ルールの自動獲得

• 諏訪 晴彦 (神戸大学大学院 自然科学研究科)
  ［概要］ 近年，生産の場でのスケジューリングの自動化を目指して，インテリジェント・ スケジューリングシステムの構築が研究され始めている．このようなシステム の構築においては，効率的なルールの獲得方法の確立が重要である．本研究で は，多数発生させたスケジュール上の仕事対の入換え操作から得られる事例か ら，スケジューリング・ルールを帰納的に獲得することを考えている．ルール の獲得は，帰納的学習法にC4.5学習アルゴリズムを利用し，仕事の属性データ とスケジュール上での局所的な位置情報に基づく事例を入力データとして行わ れる．これまでに対象としてきた１機械問題およびフローショップ問題を取り 上げ，本手法によるスケジューリング・ルールの獲得を紹介する．

距離付き２進符号について

• 毛利 進太郎 (大阪大学大学院工学研究科 応用物理学専攻数理情報工学講座)
  ［概要］ 従来,符号理論では通信を行い際に誤りが発生する可能性があるということを前 提として,その誤りを検出,訂正する符号化についての研究は多く行われてきた. 距離付き2進符号では,それら誤り訂正,誤り検出などの従来の研究とは異なり,誤 りが起こり得る符号系が通信される対象である情報にどのような違いを起こしう るかということを考える.
  距離付き２進符号は符号語の誤りに対し情報の違いの大きさを表す誤り距離とい う概念を導入する.そして誤り距離の性質を考察することによって通信によって符 号語に誤りが生じたとき,なるべく元の符号語の情報に近い情報の符号語へ復号さ れるということを考える.
  人間が情報を交信する際には,多少の情報の誤りがあっても人間がそれを経験に よって補い,正確な情報の伝達を可能としている.例えば画像データなどを送信す る場合,受信データが必ずしも送信データと厳密に同じでなくてもその画像がなに を表しているのかを判別することが出来る.距離付2進符号はそのように受信デー タが必ずしも送信データと厳密に同じでなくても差し支えないような場合に有効 である.
  距離付2進符号においては誤り距離がなるべく小さい方が望ましいと考えられる. 本研究における最も重要な目的の一つはnビット長の2進符号に対し,誤り距離の 総和が最小となる2進符号がどのようなものであるかを調べることにある.

ＣＳＰ(制約充足問題)による汎用組合せアルゴリズムの研究

• 野々部　宏司　　(京都大学大学院工学研究科数理工学専攻)
  ［概要］ 現実社会に現れる問題は、数学的に記述し直してみると組合せ問題がその中心 となっていることが少なくない。そこで、様々な組合せ問題を一括して解くこ とができる汎用アルゴリズムが存在すれば、実用上非常に意義のあるものとな る。しかし、組合せ問題を厳密の解くことの困難さは理論的にも明らかにされ ており、現実社会における大規模な問題例に対して厳密解を求めることは実用 上不可能と考えられる。このことから、応用上、良質の近似解を効率良く求め ることができる近似アルゴリズムが有用であると考えられる。 このような、組合せ問題に対する汎用近似アルゴリズムを目指して、CSP(制約 充足問題)に対するタブー探索の適用を行った。CSPは、与えられた制約を全て 満たすような、各変数への値の割当てを求める問題であり、様々な組合せ問題 を定式化することができる。また、タブー探索はメタ・ヒューリスティックス と呼ばれる手法の 1つであり、多くの組合せ最適化問題に対して有効であると いう報告がなされている。
  タブー探索を用いた CSPアルゴリズムの、汎用アルゴリズムとしての有用性を 調べるため、グラフの彩色問題、ブロック計画、集合カバー問題、一般化割当 て問題、時間割問題、スケジューリング問題等、多くの組合せ問題に対して数 値実験を行った結果、ほとんどの場合、計算時間は多少かかるものの、個々の 問題に対する専用アルゴリズムと同等の解を求めることができた。しかし、問 題例によってはこのアルゴリズムが有効でない場合もあり、この問題点の解消 を試みていくと共に、このようなCSP とタブー探索 (メタ・ヒューリスティッ クス) を基本的な枠組みとしたアプローチの、汎用アルゴリズムとしての可能 性を調べる。