JPH0619951A

JPH0619951A - 組合せ最適化方法及びその装置

Info

Publication number: JPH0619951A
Application number: JP17426492A
Authority: JP
Inventors: Kunio Nakanishi; 邦夫中西; Shigeo Abe; 重夫阿部
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1992-07-01
Filing date: 1992-07-01
Publication date: 1994-01-28

Abstract

(57)【要約】【目的】２つの値のいずれかをとるｎ個の変数の組合
せＸ＝（Ｘ（１），…，Ｘ（ｎ））に対して、ある制約
条件を満足する組合せのうち与えられた目的関数ｆ
（Ｘ）を最小とする組合せを見出す組合せ最適化問題
で、よりよい近似解を得る。【構成】目的関数を修正する目的関数修正手段５２、
制約条件からペナルティ関数を定義するペナルティ関数
定義手段５３、パラメータαを有する補正関数を定義す
る補正関数定義手段５４、パラメータαの初期値及び更
新値を設定するパラメータ設定手段５６を設け、パラメ
ータαを大きな値から徐々に小さくしながら目的関数と
ペナルティ関数と補正関数を加算した補正エネルギ関数
の極小値を追跡し、近似解を求める。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、２つの値をとるｎ個の
変数の組合せに対して、ある制約条件を満足し与えられ
た目的関数を最小にする組合せを見出す組合せ最適化方
法及びその装置に係り、特に、よりよい近似解を得るの
に好適な組合せ最適化方法及びその装置に関する。

【０００２】

【従来の技術】組合せ最適化問題とは、２つの値のいず
れかをとるｎ個の変数の組合せＸ＝（Ｘ（１），…，Ｘ
（ｎ））に対して、ある制約条件を満足する組合せのう
ち与えられた目的関数ｆ（Ｘ）を最小とする組合せを見
出す問題である。合原一幸著「ニューラルコンピュータ
脳と神経に学ぶ」（東京電機大学出版局）９８頁〜１
０５頁には、ある関数が時間とともに減少するようなニ
ューラルネットのモデルを構成し、そのモデルのパラメ
ータを、解くべき組合せ最適化問題に適合するように設
定することによって、解を得る装置が提案されている。

【０００３】

【発明が解決しようとする課題】上記従来技術は、ある
関数が時間とともに減少するというニューラルネットの
性質のみによっているため、近似的にも十分に良い解を
得る保証はなく、解くべき組合せ最適化問題によって
は、制約条件さえ満足しない解や、明らかに近似解とは
言えないような解になることもあるという不具合があ
る。

【０００４】本発明の目的は、近似解としての精度をよ
り向上させた組合せ最適化装置等を提供することにあ
る。

【０００５】

【課題を解決するための手段】上記目的は、制約条件を
満足しない組合せにおける値が、制約条件を満足する組
合せにおける値よりも大きくなるペナルティ関数ｇ
（Ｘ）を定義するペナルティ関数定義手段と、目的関数
ｆ（Ｘ）及びペナルティ関数ｇ（Ｘ）が多項式で表現さ
れている場合に、各変数Ｘ（ｉ）の自乗を（ａ＋ｂ）Ｘ
（ｉ）−ａｂに置換することにより、Ｘの各変数Ｘ
（ｉ）がａ，ｂ間の数となるようなｎ次元の超立方体の
内部に、目的関数ｆ（Ｘ）及びペナルティ関数ｇ（Ｘ）
の極小点が存在しないように修正する手段と、パラメー
タαを有し、各変数Ｘ（１），…，Ｘ（ｎ）が２つの数
ａ，ｂのいずれかとなる組合せＸに対しては互いに等し
い値となり、関数を極小にするｎ次元の超立方体の内部
の点が存在し、その点における値がパラメータαが大き
くなるほど小さくなるような補正関数ｈ（Ｘ，α）を定
義する補正関数定義手段と、補正エネルギ関数Ｆ（Ｘ，
α）＝ｆ（Ｘ）＋ｇ（Ｘ）＋ｈ（Ｘ，α）を極小にする
ｎ次元の超立方体の点Ｘをパラメータαに対応して得る
極小点追跡手段と、パラメータαを初期値に設定、及
び、より小さな値に更新するパラメータ設定手段と、パ
ラメータαを初期値から徐々に小さな値に更新し、補正
エネルギ関数Ｆ（Ｘ，α）を極小にするｎ次元の超立方
体の点Ｘを追跡し、その収束値を求める手段とを設ける
ことにより、達成される。

【０００６】

【作用】各変数が取り得る２つの数ａ，ｂを、０，１と
して説明する。制約条件を満足しない組合せにおける値
が、制約条件を満足する組合せにおける値よりも大きく
なるペナルティ関数ｇ（Ｘ）を定義するペナルティ関数
定義手段は、例えば、変数Ｘ（１），Ｘ（２）のいずれ
か一方のみが１という制約条件に対しては

【０００７】

【数１】

【０００８】と定義すればよい。この関数は、制約条件
を満足するときは０であり、満足しないときはｗとな
る。ここでｗは、ペナルティ関数の具体的な大きさを規
定する正の定数である。

【０００９】目的関数ｆ（Ｘ）及びペナルティ関数ｇ
（Ｘ）が多項式で表現されている場合に、各変数Ｘ
（ｉ）の自乗を（ａ＋ｂ）Ｘ（ｉ）−ａｂに置換するこ
とにより、ｎ次元の超立方体の内部に、目的関数ｆ
（Ｘ）及びペナルティ関数ｇ（Ｘ）の極小点が存在しな
いように修正する手段は、例えば、数１のように多項式
で表現されている場合、展開し、変数Ｘ（ｉ）の自乗を
（ａ＋ｂ）Ｘ（ｉ）−ａｂ＝Ｘ（ｉ）に置き換えると、

【００１０】

【数２】

【００１１】となる。これにより極小点は内部に存在し
なくなる。一般の多項式においても変数の自乗を１乗に
置き換えればよい。なお、この置き換えは、従来技術の
ニューラルネットを適用する場合も同様であり、内部の
極小点に収束しないようにするための手段となってい
る。また、数１のような多項式ではなく、より一般的な
式となっている場合は、各変数Ｘ（１），…，Ｘ（ｎ）
が０，１となる範囲で一致するような多項式を用いれば
よい。そのような多項式が常に存在することは理論的に
保証されている。従って、目的関数ｆ（Ｘ）及びペナル
ティ関数ｇ（Ｘ）は、変数の自乗あるいはより高次の累
乗を含まない多項式として表現できる。

【００１２】パラメータαを有し、各変数Ｘ（１），
…，Ｘ（ｎ）が２つの数０，１のいずれかとなる組合せ
Ｘに対しては互いに等しい値となり、関数を極小にする
ｎ次元の超立方体の内部の点が存在し、その点における
値がパラメータαが大きくなるほど小さくなるような補
正関数ｈ（Ｘ，α）を定義する補正関数定義手段は、例
えば、２次関数

【００１３】

【数３】

【００１４】とすることにより、達成される。数３は、
各変数Ｘ（１），…，Ｘ（ｎ）が２つの数０，１のいず
れかとなる組合せＸに対しては０であり、ｎ次元の超立
方体の中心の点における最小値は−αｎ／８であり、パ
ラメータαが大きくなるほど小さくなっている。

【００１５】補正エネルギ関数Ｆ（Ｘ，α）は次式４で
表される。

【００１６】

【数４】

【００１７】これを極小にするｎ次元の超立方体の点Ｘ
を、パラメータαに対応して得る極小点追跡手段は、Ｘ
の領域が制約された非線形最適化法が適用できる。具体
的な手段としては、最急降下法、共役方向法、共役勾配
法、ニュートン法、準ニュートン法、ニューラルネット
などのいずれかによればよい。

【００１８】パラメータαを初期値に設定、および、よ
り小さな値に更新するパラメータ設定手段は、予め与え
た級数に従って、パラメータαを初期値に設定、及び、
より小さな値に更新すること、または、補正エネルギ関
数の極小点が超立方体の内部に位置するようにパラメー
タαの初期値を十分に大きな数として設定し、極小点の
位置及び履歴などを用いて、より小さな値に更新するこ
とにより達成される。

【００１９】パラメータαの初期値は十分大きく設定し
ており、補正エネルギ関数Ｆ（Ｘ，α）において補正関
数ｈ（Ｘ，α）が支配的になっている。その結果、補正
エネルギ関数Ｆ（Ｘ，α）の極小点Ｘは、ｎ次元の超立
方体の内部になるように定義されている補正関数ｈ
（Ｘ，α）の極小点の近傍に位置している。パラメータ
αを徐々に小さくすると、補正関数ｈ（Ｘ，α）の影響
が小さくなり、補正エネルギ関数Ｆ（Ｘ，α）の極小点
Ｘも徐々に移動することになる。そして、パラメータα
が０に近くなると補正関数ｈ（Ｘ，α）の影響はほとん
どなくなる。従って、目的関数ｆ（Ｘ）及びペナルティ
関数ｇ（Ｘ）が多項式で表現されている場合に、各変数
Ｘ（ｉ）の自乗を（ａ＋ｂ）Ｘ（ｉ）−ａｂに置換する
ことにより、目的関数ｆ（Ｘ）及びペナルティ関数ｇ
（Ｘ）の極小点がｎ次元の超立方体の内部に存在しない
ように修正する手段を備えているので、補正エネルギ関
数Ｆ（Ｘ，α）の極小点は最終的には超立方体の端点に
達し、各変数Ｘ（ｉ）は０または１に収束する。

【００２０】その結果、以上の手段を備えることによ
り、パラメータαを初期値から徐々に小さな値に更新
し、補正エネルギ関数Ｆ（Ｘ，α）を極小にするｎ次元
の超立方体の点Ｘを追跡した収束値は目的関数ｆ（Ｘ）
とペナルティ関数ｇ（Ｘ）の和（エネルギ関数E（Ｘ）
と呼ぶ）を小さくする組合せであり、ペナルティ関数ｇ
（Ｘ）が小さく、制約条件を満足し、目的関数ｆ（Ｘ）
が小さくなり、近似解としての精度をより向上させるこ
とができる。

【００２１】以下、その理論的な根拠を説明する。目的
関数ｆ（Ｘ）及びペナルティ関数ｇ（Ｘ）は、変数の累
乗を含まない多項式であり、その和であるエネルギ関数
E（Ｘ）も変数の累乗を含まない多項式である。

【００２２】パラメータαに対して変数Ｘ（ｉ）が０ま
たは１となる端点となるためには、少なくともその端点
が補正エネルギ関数の極小点でなければならない。その
必要条件を考察するため、まず、端点Ｘに対して、ひと
つのＸ（ｉ）を１−Ｘ（ｉ）に置き換えた点をＸ［ｉ］
とする。このように、ひとつのＸ（ｉ）だけが異なる端
点を、隣接する端点という。また、端点Ｘから隣接する
端点Ｘ［ｉ］に向かって微小量δだけ進んだ点をＸ’と
する。

【００２３】エネルギ関数をＸ（ｉ）について整理し、

【００２４】

【数５】

【００２５】とすると、関数Ｐ（Ｘ），Ｑ（Ｘ）はＸ
（ｉ）には依存しない。従って、点Ｘ，Ｘ［ｉ］，Ｘ’
において同じ値である。

【００２６】ここで、Ｘ（ｉ）＝０と仮定すると、

【００２７】

【数６】

【００２８】

【数７】

【００２９】

【数８】

【００３０】である（δの２乗の項は無視する）。従っ
て、

【００３１】

【数９】

【００３２】となる。端点Ｘが極小点ならばこれは正で
あり、

【００３３】

【数１０】

【００３４】となる。Ｘ（ｉ）＝１と仮定しても同様で
あり、最終的には数１０に達する。

【００３５】端点Ｘが極小点ならば、数１０が全てのｉ
について成立しなければならない。従って、パラメータ
αに対して変数Ｘ（ｉ）が０または１となる端点Ｘとな
るための必要条件は、端点Ｘが隣接する全ての端点より
もα／２以上、エネルギ関数が小さいことである。

【００３６】以上の考察から次のことが明らかである。（１）パラメータαの初期値を十分に大きくすることに
より、全ての端点がこの必要条件を満足しなくなる。（２）パラメータαを徐々に小さくすると、隣接する端
点よりもエネルギ関数がより小さな端点から順次、この
必要条件を満足するようになる。（３）最初にこの必要条件を満足する端点が最適解とは
限らないし、それに収束することも保証されない。しか
しながら、より早く必要条件を満足する端点に収束しや
すく、その結果、最適解に近いことが期待される。

【００３７】なお、以上では各変数が取り得る２つの数
ａ，ｂを０，１として説明したが、数式を若干訂正すれ
ば一般の数ａ，ｂにも適用できることは明らかである。

【００３８】上記の理論的根拠が成り立つのは、超立方
体の内部に極小点が存在しないように目的関数ｆ（Ｘ）
及びペナルティ関数ｇ（Ｘ）を修正し、補正関数ｈ
（Ｘ，α）を数３により定義した場合に限られる。従っ
て、それ以外の場合については上記の理論的根拠が成り
立たなくなる。そのため、０または１に収束しない変数
Ｘ（ｉ）が存在する可能性があり、求められる解が満た
すべき必要条件が数１０のように明確には示せなくなる
が、組合せ最適化装置の動作そのものは適用可能であ
る。

【００３９】また、上記においてはパラメータαを徐々
に小さくするとしたが、適当な値のパラメータαを用い
て、補正エネルギ関数Ｆ（Ｘ，α）を極小にする変数の
組合せＸを求めるとしてもよく、ニューラルネットのエ
ネルギ関数を補正エネルギ関数Ｆ（Ｘ，α）に替えるこ
ともできる。この場合、隣接する全ての端点よりもα／
２以上エネルギ関数が小さい端点Ｘに限定されるため、
エネルギ関数が小さく比較的よい解となる。

【００４０】

【実施例】以下、本発明の一実施例を図面を参照して説
明する。図１において、５１は解くべき組合せ最適化問
題に関して、その目的関数と制約条件を記述する問題記
述手段である。５２は問題記述手段５１に記述されてい
る目的関数ｆ（Ｘ）が多項式で表現されている場合に、
各変数Ｘ（ｉ）の自乗を（ａ＋ｂ）Ｘ（ｉ）−ａｂ＝Ｘ
（ｉ）に置換することにより、ｎ次元の超立方体の内部
に、目的関数ｆ（Ｘ）の極小点が存在しないように修正
する目的関数修正手段である。目的関数ｆ（Ｘ）が多項
式で表現されていない場合には、ｎ次元の超立方体の端
点で同じ値となる多項式に修正する。

【００４１】５３は問題記述手段５１に記述されている
制約条件からペナルティ関数ｇ（Ｘ）を定義するペナル
ティ関数定義手段であり、これにはペナルティ関数ｇ
（Ｘ）が多項式で表現されている場合に、各変数Ｘ
（ｉ）の自乗を（ａ＋ｂ）Ｘ（ｉ）−ａｂ＝Ｘ（ｉ）に
置換することにより、ｎ次元の超立方体の内部に、ペナ
ルティ関数ｇ（Ｘ）の極小点が存在しないように修正す
ることも含まれる。ペナルティ関数ｇ（Ｘ）が多項式で
表現されていない場合は、ｎ次元の超立方体の端点で同
じ値となる多項式に修正する。

【００４２】５４は補正関数を数３により定義する補正
関数定義手段である。５５は補正エネルギ関数Ｆ（Ｘ，
α）＝ｆ（Ｘ）＋ｇ（Ｘ）＋ｈ（Ｘ，α）を極小にする
ｎ次元の超立方体の点Ｘをパラメータαに対応して得る
極小点追跡手段であり、Ｘの領域が制約された非線形最
適化法により実現する。本実施例では、勾配を用いて互
いに共役な方向を生成する方法で、Ｘがｎ次元の超立方
体の外部に出ないという制約を付けた共役勾配法を採用
する。

【００４３】５６はパラメータαを初期値に設定、およ
び、より小さな値に更新するパラメータ設定手段であ
り、初期値は十分に大きな数とし、より小さな値に更新
する手段である。本実施例においては、十分に大きな初
期値とし、１未満の公比をもつ等比級数に従って設定す
る手段を用いる。５７はパラメータ設定手段５６により
設定されたパラメータαに対して極小点追跡手段５５に
より極小点を追跡し、終了判定を行う実行制御手段であ
る。５８は実行制御手段５７により得られた結果などを
表示する表示手段である。

【００４４】図２は実行制御手段５７の処理手順を示す
フローチャートである。図２において、ステップ６１は
極小点Ｘを初期値に設定するステップであり、超立方体
の内部ならば任意の点でよい。ステップ６２はパラメー
タ設定手段５６によりパラメータαを初期値に設定する
ステップである。ステップ６３は極小点追跡手段５５に
より補正エネルギ関数Ｆ（Ｘ，α）の極小点を追跡する
ステップである。

【００４５】ステップ６４は極小点Ｘが端点に達する
か、前回のパラメータαに対する極小点との差がほとん
どなくなれば終了すべきと判定するステップである。極
小点Ｘが端点に達した場合はその結果が解であるが、前
回のパラメータαに対する極小点との差がほとんどなっ
たことにより終了すべきと判定された場合は解が得られ
なかった場合に相当する。しかしながら、目的関数ｆ
（Ｘ）とペナルティ関数ｇ（Ｘ）には超立方体の内部に
極小点がないため、後者の場合はごく稀であると考えら
れる。

【００４６】ステップ６５はステップ６４で終了すべき
でないと判定されたときに実行するステップであり、パ
ラメータ設定手段５６によりパラメータαをより小さな
値に更新し、ステップ６３に戻る。

【００４７】ステップ６６はステップ６４で終了すべき
であると判定されたときに実行するステップであり、得
られた結果などを表示手段５８により表示し、終了す
る。

【００４８】本実施例によれば、パラメータαを初期値
から徐々に小さな値に更新し、補正エネルギ関数Ｆ
（Ｘ，α）を極小にするｎ次元の超立方体の点Ｘを追跡
し、その収束値を求めることにより、近似解としての精
度をより向上させることができるという効果がある。

【００４９】ここで具体的な例題として道路網の最短経
路探索問題を考える。この問題は、図３に示したような
道路網で、与えられた２地点Ｓ，Ｇ間の最短経路を探索
する問題であり、以下の定式化により、０または１の値
をとる変数の組合せ最適化問題として取り扱うことがで
きる。

【００５０】すなわち、記号をＳ：スタート地点Ｇ：ゴール地点Ｌ：地点の集合Ｌ’：ＬからＳ，Ｇを除いた集合ａ（ｉ，ｊ）：地点ｉ，ｊ間に道路があるときは１、な
いときは０ｄ（ｉ，ｊ）：地点ｉ，ｊ間の道路の長さＸ（ｉ）：地点ｉを通るときは１、通らないときは０と
なる変数ただし、Ｘ（Ｓ），Ｘ（Ｇ）は常に１の定数と定義す
る。

【００５１】このとき、目的関数ｆ（Ｘ）は経路の長さ
であり、

【００５２】

【数１１】

【００５３】である。この関数には自乗は含まれないた
め修正する必要はない（ａ（ｊ，ｊ）は０である）。

【００５４】次に、制約条件は枝分かれなく地点Ｓから
地点Ｇまで結ばれることであり、地点ｉを通るならばそ
の前後の２地点を通る、ただし、地点ＳとＧについては
前後いずれかの１地点であると考えることができる。す
なわち、

【００５５】

【数１２】

【００５６】

【数１３】

【００５７】である。従って、ペナルティ関数ｇ（Ｘ）
は、

【００５８】

【数１４】

【００５９】とすればよい。この関数には変数の自乗が
含まれるているので、さらに、

【００６０】

【数１５】

【００６１】と修正する。ここで、ｗはペナルティ関数
の大きさを決める正の定数であり、大きいほど制約条件
を重視することになる。

【００６２】以上から、補正関数ｈ（Ｘ，α）を数３に
より定義すれば、補正エネルギ関数Ｆ（Ｘ，α）は、

【００６３】

【数１６】

【００６４】となる。

【００６５】図３の道路網に対して、定数ｗを“２０”
とし、パラメータαを初期値が“１００”、公比が
“０．９”の等比級数により設定した。その結果、長さ
“２９．６”の経路（Ｓ−３−８−９−１０−１１−１
２−１７−２２−Ｇ）が得られた。この結果は、最短経
路（Ｓ−１−２−７−１３−１８−Ｇ、長さ“２８．
１）との差は僅かであり、５番目によい解である。な
お、この問題に従来技術を適用すると、全ての変数が０
となり、制約条件さえ満足しない結果となり、定数ｗを
非常に大きくしてはじめて長さ“３６．４”の経路（Ｓ
−３−８−９−５−６−７−１３−１８−Ｇ）が得られ
るにすぎない。

【００６６】第２の具体例として巡回セールスマン問題
に適用した場合を説明する。巡回セールスマン問題と
は、与えられたＮ地点を全て１回ずつ通り元の地点に戻
る最小コストの巡回路を探索する問題である。

【００６７】変数Ｘ（ｉ，ｐ）をｉ番目に地点ｐを通る
とき１、その他を０とする（ただし、ｉ及びｐは０から
Ｎ−１とする）。地点ｐ，ｑ間のコストをｄ（ｐ，ｑ）
とすると、目的関数ｆ（Ｘ）は

【００６８】

【数１７】

【００６９】とすればよい。制約条件は、各時刻ｉには
いずれか１地点に限ること、各地点ｐは１回だけである
ことと考えると、各時刻ｉに対して

【００７０】

【数１８】

【００７１】及び各地点ｐに対して

【００７２】

【数１９】

【００７３】であり、ペナルティ関数ｇ（Ｘ）は、

【００７４】

【数２０】

【００７５】とすればよい（最後の項は前の２項を展開
したときに現れるＸ（ｉ，ｐ）²をＸ（ｉ，ｐ）に置換
するための項であり、ｗは適当な正の定数である）。以
下の処理は最短経路探索問題と同じである。

【００７６】また、ＬＳＩなどの最適な配置を決定する
ＣＡＤシステムのための最適配置問題は、配置を０また
は１の値をとる変数の組合せで表し、配線の長さ、全体
の面積など最適にしたい評価基準を目的関数とすること
によって、組合せ最適化問題として同様に取り扱うこと
ができる。

【００７７】さらに、複数の工程の最適な順序などを決
定するスケジューリング問題は、工程の順序を０または
１の値をとる変数の組合せで表し、全体の所要時間や各
工程の遅延時間などから最適にしたい評価基準を目的関
数として定義することによって、組合せ最適化問題とし
て同様に取り扱うことができる。

【００７８】その他の組合せ最適化問題に対しても同様
の手順によればよく、本発明が適用できることは明らか
であり、同様の効果が得られる。

【００７９】上記の実施例においては、パラメータαを
等比級数により設定するとしているが、その他の級数に
従って、初期値を設定し、より小さな値に更新してもよ
い。採用する級数により処理速度などに差はあるが、効
果としては変わらないと考えてよい。

【００８０】また、パラメータ設定手段において、補正
エネルギ関数の極小点が超立方体の内部に位置するよう
にパラメータαの初期値を設定し、極小点の位置及び履
歴などを用いて、より小さな値に更新してもよい。更新
値は、極小点がなめらかに移動するように、極小点が急
激に移動した場合は余り変化させず、極小点がほとんど
移動しない場合は大きく変化させるという決定方法が適
している。これにより、パラメータαをより的確に変え
ることができ、上述の効果に加えて高速化が達成される
という効果も発生する。

【００８１】また、上記実施例では補正関数ｈ（Ｘ，
α）を２次関数としているが、パラメータαを有し、各
変数Ｘ（１），…，Ｘ（ｎ）が２つの数ａ，ｂのいずれ
かとなる組合せＸに対しては互いに等しい値となり、関
数を極小にするｎ次元の超立方体の内部の点が存在し、
その点における値がパラメータαが大きくなるほど小さ
くなるような関数であれば任意でよい。

【００８２】さらに、目的関数ｆ（Ｘ）とペナルティ関
数ｇ（Ｘ）は変数Ｘ（ｉ）の累乗を含まない多項式とし
ているが、一般の関数でもよい。この場合、理論的な根
拠はそのまま適用できないが、組合せ最適化装置の方式
は同様に適用できる。これにより、目的関数ｆ（Ｘ）と
ペナルティ関数ｇ（Ｘ）を修正する必要がなくなり、容
易に適用できるようになるという効果がある。

【００８３】また、以上の実施例においてはパラメータ
αを徐々に小さくするとしたが、適当な値のパラメータ
αを用いて、補正エネルギ関数Ｆ（Ｘ，α）を極小にす
る変数の組合せＸを求めるとしてもよく、ニューラルネ
ットのエネルギ関数を補正エネルギ関数Ｆ（Ｘ，α）に
替えることもできる。この場合、隣接する全ての端点よ
りもα／２以上エネルギ関数が小さい端点Ｘに限定され
るため、パラメータαの値によって解を絞り込むことが
でき、エネルギ関数が小さく比較的よい解となるという
効果がある。なお、パラメータαの値は、例えば、制約
条件を満足する端点Ｘとその点に隣接する端点とのエネ
ルギ関数の差によって決定すればよい。

【００８４】

【発明の効果】本発明によれば、２つの値のいずれかを
とるｎ個の変数の組合せＸ＝（Ｘ（１），…，Ｘ
（ｎ））に対して、ある制約条件を満足する組合せのう
ち与えられた目的関数ｆ（Ｘ）を最小とする組合せを見
出す組合せ最適化問題に対して、近似解としての精度を
より向上させることができる。

【図面の簡単な説明】

【図１】本発明の一実施例に係る組合せ最適化装置の構
成図である。

【図２】図１に示す実行制御手段の処理手順を示すフロ
ーチャートである。

【図３】最短経路探索問題の道路網の例を示す図であ
る。

【符号の説明】

５１…問題記述手段、５２…目的関数修正手段、５３…
ペナルティ関数定義手段、５４…補正関数定義手段、５
５…極小点追跡手段、５６…パラメータ設定手段、５７
…実行制御手段、５８…表示手段。

Claims

【特許請求の範囲】

【請求項１】２つの数ａ，ｂのいずれかの値をとるｎ
個の変数の組合せＸ＝（Ｘ（１），…，Ｘ（ｎ））に対
して、ある制約条件を満足する組合せのうち与えられた
目的関数ｆ（Ｘ）を最小とする組合せを見出す組合せ最
適化装置において、制約条件を満足しない組合せにおける値が、制約条件を
満足する組合せにおける値よりも大きくなるペナルティ
関数ｇ（Ｘ）を定義するペナルティ関数定義手段と、パラメータαを有し、目的関数ｆ（Ｘ）とペナルティ関
数ｇ（Ｘ）が小さいほど小さくなる補正エネルギ関数Ｆ
（Ｘ，α）を定義する手段と、前記補正エネルギ関数Ｆ（Ｘ，α）を極小にする変数の
組合せＸを求める手段とを備えることを特徴とする組合
せ最適化装置。
【請求項２】２つの数ａ，ｂのいずれかの値をとるｎ
個の変数の組合せＸ＝（Ｘ（１），…，Ｘ（ｎ））に対
して、ある制約条件を満足する組合せのうち与えられた
目的関数ｆ（Ｘ）を最小とする組合せを見出す組合せ最
適化装置において、制約条件を満足しない組合せにおける値が、制約条件を
満足する組合せにおける値よりも大きくなるペナルティ
関数ｇ（Ｘ）を定義するペナルティ関数定義手段と、パラメータαを有し、各変数Ｘ（１），…，Ｘ（ｎ）が
前記２つの数ａ，ｂのいずれかとなる組合せＸに対して
は互いに等しい値となり、ｎ次元の超立方体の内部の点
において極小となり、その点における値がパラメータα
が大きくなるほど小さくなるような補正関数ｈ（Ｘ，
α）を定義する補正関数定義手段と、目的関数ｆ（Ｘ）とペナルティ関数ｇ（Ｘ）と補正関数
ｈ（Ｘ，α）の総和である補正エネルギ関数Ｆ（Ｘ，
α）を極小にする前記ｎ次元の超立方体の点Ｘをパラメ
ータαに対応して得る極小点追跡手段と、前記パラメータαを初期値に設定、及び、より小さな値
に更新するパラメータ設定手段と、前記パラメータαを初期値から徐々に小さな値に更新
し、前記補正エネルギ関数Ｆ（Ｘ，α）を極小にする前
記ｎ次元の超立方体の点Ｘを追跡し、その収束値を求め
る手段とを備えることを特徴とする組合せ最適化装置。
【請求項３】請求項２において、前記目的関数ｆ
（Ｘ）及びペナルティ関数ｇ（Ｘ）が多項式で表現され
ている場合に、各変数Ｘ（ｉ）の自乗を（ａ＋ｂ）Ｘ
（ｉ）−ａｂに置換することにより、前記目的関数ｆ
（Ｘ）及びペナルティ関数ｇ（Ｘ）の極小点がｎ次元の
超立方体の内部に存在しないように修正する手段を備え
ることを特徴とする組合せ最適化装置。
【請求項４】請求項２において、補正関数定義手段
は、補正関数ｈ（Ｘ，α）を、各変数Ｘ（１），…，Ｘ
（ｎ）が２つの数ａ，ｂのいずれかとなる組合せＸに対
しては０であり、ｎ次元の超立方体の中心の点で最小値
をとる２次関数とすることを特徴とする組合せ最適化装
置。
【請求項５】請求項２において、パラメータ設定手段
は、予め与えた級数に従って、前記パラメータαを初期
値に設定、及び、より小さな値に更新することを特徴と
する組合せ最適化装置。
【請求項６】請求項２において、パラメータ設定手段
は、補正エネルギ関数の極小点が前記超立方体の内部に
位置するように前記パラメータαの初期値を設定し、極
小点の位置及び履歴などを用いて、より小さな値に更新
することを特徴とする組合せ最適化装置。
【請求項７】与えられた道路網の与えられた２地点間
を結ぶ最短経路を探索する最短経路探索問題、あるい
は、与えられた複数の地点を全て１回ずつ通り元の地点
に戻る最小コストの巡回路を探索する巡回セールスマン
問題、あるいは、ＬＳＩなどの最適な配置を決定するＣ
ＡＤシステムのための最適配置問題、あるいは、複数の
工程の最適な順序などを決定するスケジューリング問題
のいずれかを組合せ最適化問題として解く解法装置にお
いて、請求項１乃至請求項６のいずれかに記載の組合せ
最適化装置を備えることを特徴とする解法装置。
【請求項８】２つの数ａ，ｂのいずれかの値をとるｎ
個の変数の組合せＸ＝（Ｘ（１），…，Ｘ（ｎ））に対
して、ある制約条件を満足する組合せのうち与えられた
目的関数ｆ（Ｘ）を最小とする組合せを見出す組合せ最
適化方法において、制約条件を満足しない組合せにおける値が、制約条件を
満足する組合せにおける値よりも大きくなるペナルティ
関数ｇ（Ｘ）を定義し、パラメータαを有し、目的関数ｆ（Ｘ）とペナルティ関
数ｇ（Ｘ）が小さいほど小さくなる補正エネルギ関数Ｆ
（Ｘ，α）を定義し、前記補正エネルギ関数Ｆ（Ｘ，α）を極小にする変数の
組合せＸを求めることを特徴とする組合せ最適化方法。
【請求項９】２つの数ａ，ｂのいずれかの値をとるｎ
個の変数の組合せＸ＝（Ｘ（１），…，Ｘ（ｎ））に対
して、ある制約条件を満足する組合せのうち与えられた
目的関数ｆ（Ｘ）を最小とする組合せを見出す組合せ最
適化方法において、制約条件を満足しない組合せにおける値が、制約条件を
満足する組合せにおける値よりも大きくなるペナルティ
関数ｇ（Ｘ）を定義し、パラメータαを有し、各変数Ｘ（１），…，Ｘ（ｎ）が
前記２つの数ａ，ｂのいずれかとなる組合せＸに対して
は互いに等しい値となり、ｎ次元の超立方体の内部の点
において極小となり、その点における値がパラメータα
が大きくなるほど小さくなるような補正関数ｈ（Ｘ，
α）を定義し、目的関数ｆ（Ｘ）とペナルティ関数ｇ（Ｘ）と補正関数
ｈ（Ｘ，α）の総和である補正エネルギ関数Ｆ（Ｘ，
α）を極小にする前記ｎ次元の超立方体の点Ｘをパラメ
ータαに対応してとり、前記パラメータαを初期値に設定、及び、より小さな値
に更新するパラメータを設定し、前記パラメータαを初期値から徐々に小さな値に更新
し、前記補正エネルギ関数Ｆ（Ｘ，α）を極小にする前
記ｎ次元の超立方体の点Ｘを追跡し、その収束値を求め
ることを特徴とする組合せ最適化方法。
【請求項１０】請求項９において、前記目的関数ｆ
（Ｘ）及びペナルティ関数ｇ（Ｘ）が多項式で表現され
ている場合に、各変数Ｘ（ｉ）の自乗を（ａ＋ｂ）Ｘ
（ｉ）−ａｂに置換することにより、前記目的関数ｆ
（Ｘ）及びペナルティ関数ｇ（Ｘ）の極小点がｎ次元の
超立方体の内部に存在しないように修正することを特徴
とする組合せ最適化方法。