平成８年度第３回KSMAP

日時：　平成８年１０月３日（木）午後３時〜５時半

場所：　住友金属工業株式会社
　　　　大阪市中央区北浜東２ー１６
　　　　日刊工業新聞社ビル　１０Ｆ　会議室

プログラム：

◆［タイトル］    最大安定集合問題の一般化とパーフェクト双向グラフ

  ［発表者］      田村 明久 (電通大)

  ［概要］
    グラフ的な最適化問題としては、最大流問題、巡回セースルマン問題など
    多くの問題が盛んに研究されていますが、ここでは最大安定集合問題とその
    双向グラフ上への一般化された問題の話をします。
    　（無向）グラフの安定集合とは、頂点の集合で任意の要素が辺で結ばれて
    いないものです。最大安定集合問題は要素数最大の安定集合を求めるもので
    すが、一般にはＮＰ困難と呼ばれるクラスに属します。グラフが特殊な構造
    を持っていると、例えばパーフェクト性など、多項式時間解法の存在が知ら
    れています。
    　今回の話は、無向グラフを一般化した双向グラフに対して、最大安定集合
    に対応した問題を考えます。無向グラフのパーフェクトという概念を双向グ
    ラフに拡張し、この問題がパーフェクト双向グラフに対しては、無向グラフ
    のときと同様に多項式時間で解けるというのが話の概要です。



◆［タイトル］    0-1型混合整数計画問題に対する
                                       Hopfield Neural Network の適用

  ［発表者］    向井くみこ (奈良先端大)
  
  ［概要］
      ホップフィールドネットワークを用いて組合せ最適化問題を解く方法が提
    案され、様々な問題に適用されている。今回の発表では、ホップフィールド
    ネットワークを用いた、0-1 型混合整数計画問題に対する新しいアルゴリズ
    ムを提案する。

      対象とする問題は目的関数が凸２次関数、制約条件が１次の不等式で与え
    られる混合整数計画問題であるが、ここではその問題を、0-1 変数を固定し
    て得られる下位レベルの連続型２次計画問題と、その結果生じる非線形 0-1 
    計画問題の２レベルの最適化問題として定式化し、上位レベルの非線形 0-1
    計画問題に対してホップフィールドネットワークを適用する。

      提案するアルゴリズムでは、現在の反復点が与えられた時、上位レベルの
    非線形0-1 計画問題の目的関数をその点において一次近似した部分問題に対
    してホップフィールドネットワークを適用し、得られた解を次の反復点とす
    る。ただし、部分問題はもとの目的関数を近似した関数を最小化しているた
    め、反復点の更新の結果、実際の目的関数値が増加してしまうことがある。

      このため、与えられた反復点と部分問題の解との(ハミング)距離を、近似
    精度がある程度の信頼性を保つように制御する必要がある。提案するアルゴ
    リズムでは現在の反復点との距離を表すペナルティ項を部分問題の目的関数
    に組み込むことにより、そのような制御を行っている。さらに、非線形最適
    化の信頼領域法の考え方を用いて、部分問題の近似精度に応じてペナルティ
    係数を適応的に決定する機能をもたせた。これにより、反復ごとに目的関数
    値の減少性が保証され、局所最適解が安定的に得られることが期待される。

    　なお当日は 今後の課題として考えている、ボルツマンマシンを一部適用
    したアルゴリズムについても簡単にふれる予定である。