(57)【要約】問題を表現する関数の微分可能性及び連続性や空間の連続性を前提条件とせずに区分で定義された関数を含む計画問題を効率的に処理する。このため、非線形計画問題を取得する非線形計画問題入力部と、非線形計画問題のある領域で求めた解を非線形計画問題の暫定解とする暫定解生成部と、暫定解の近傍領域で求めた解を非線形計画問題の解候補とする解候補生成部と、暫定解と解候補との比較結果に応じて、解候補を暫定解として更新する暫定解更新部と、暫定解の改善度合い又は解候補生成回数の少なくとも一方を判断基準として処理の終了を判定する終了判定部と、暫定解を出力する非線形計画問題解出力部と、を備える。
2015186338.tif 000002
【特許請求の範囲】
【請求項１】
制約条件又は目的関数に区分的に定義された関数を含む非線形計画問題処理装置であって、
非線形計画問題を取得する非線形計画問題入力手段と、
前記非線形計画問題のある領域で求めた解を前記非線形計画問題の暫定解とする暫定解生成手段と、
前記暫定解の近傍領域で求めた解を前記非線形計画問題の解候補とする解候補生成手段と、
前記暫定解と前記解候補との比較結果に応じて、前記解候補を暫定解として更新する暫定解更新手段と、
暫定解の改善度合い又は解候補生成回数の少なくとも一方を判断基準として処理の終了を判定する終了判定手段と、
前記暫定解を出力する非線形計画問題解出力手段と、
を備えることを特徴とする非線形計画問題解処理装置。
【請求項２】
請求項１に記載の非線形計画問題処理装置であって、
前記制約条件は、線形関数又は区分線形関数のいずれかであり、
前記目的関数は、線形関数、区分線形関数、二次関数、又は区分二次関数のいずれかである、
ことを特徴とする非線形計画問題処理装置。
【請求項３】
請求項１又は２に記載の非線形計画問題処理装置であって、
前記暫定解生成手段は、前記非線形計画問題のある領域を選択する暫定解領域選択手段と、
前記暫定解領域で計画問題の解を求める解計算手段と、
前記解の良否判定し、否の場合は暫定解生成処理を繰り返し、良の場合は前記解を暫定解として暫定解生成処理を終了する暫定解生成終了判定手段と、
を備えることを特徴とする非線形計画問題処理装置。
【請求項４】
請求項１乃至３のいずれか１項に記載の非線形計画問題処理装置であって、
前記解候補生成手段は、前記暫定解の近傍領域を選択する解候補領域選択手段と、
前記解候補領域で計画問題の解を求める解計算手段と、
前記解の良否判定し、否の場合は解候補生成処理を繰り返し、良の場合は前記解を解候補として解候補生成処理を終了する解候補生成終了判定手段と、
を備えることを特徴とする非線形計画問題処理装置
【請求項５】
請求項１乃至４のいずれか１項に記載の非線形計画問題処理装置であって、
前記暫定解更新手段は、前記暫定解と前記解候補の優劣を比較し、前記解候補が優れていれば常に前記解候補を新たな暫定解とし、前記解候補が優れていなければ、確率的に前記解候補を新たな暫定解とする、
ことを特徴とする非線形計画問題処理装置。
【請求項６】
請求項１乃至５のいずれか１項に記載の非線形計画問題処理装置であって、
前記暫定解生成手段と前記解候補生成手段との少なくとも一方が参照および追加可能な領域・解情報蓄積手段を備える
ことを特徴とする非線形計画問題処理装置
【請求項７】
請求項１乃至６のいずれか１項に記載の非線形計画問題処理装置であって、
前記解候補選択手段は、前記暫定解からの距離、又は前記暫定解を終点とする方向ベクトルを用いて領域を選択する、
ことを特徴とする非線形計画問題処理装置。
【請求項８】
請求項１乃至７のいずれか１項に記載の非線形計画問題処理装置であって、
前記解候補選択手段は、前記暫定解を含む領域の近傍の領域の評価値を用いて領域を選択する、
ことを特徴とする非線形計画問題処理装置。
【請求項９】
制約条件又は目的関数に区分的に定義された関数を含む非線形計画問題を取得し、
前記非線形計画問題のある領域で解を求め、前記解を前記非線形計画問題の暫定解とし、
前記暫定解の近傍領域で解を求め、前記解を前記非線形計画問題の解候補とし、
前記暫定解と前記解候補とを比較して暫定解を更新し、
暫定解の改善度合い又は解候補生成回数の少なくとも一方を判断基準として処理の終了を判定し、
前記暫定解を出力する
ことを特徴とする非線形計画問題解処理方法。
【請求項１０】
請求項９に記載の非線形計画問題解処理方法であって、
前記制約条件は線形関数又は区分線形関数のいずれかであり、
前記目的関数は線形関数、区分線形関数、二次関数、又は区分二次関数のいずれかである、
ことを特徴とする非線形計画問題処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、非線形計画問題処理装置および非線形計画問題処理方法に関する。
【背景技術】
【０００２】
数理計画問題は与えられた制約条件の下で数理計画問題の最適解を求めるための条件を求める問題であり、生産計画問題、資源配分計画問題、輸送問題、エネルギー最小化問題等がある。このような数理計画問題の中で代表的な問題は、線形計画問題と非線形計画問題とがある。【０００３】
線形計画問題は、いくつかの線形不等式や線形等式で表される制約条件の下で、線形の目的関数を最小又は最大にするための条件を求める問題である。この問題の解法として、シンプレックス法（単体法）がよく知られている。また、シンプレックス法以外に内点法を用いることもある。【０００４】
また、非線形計画問題とは、制約条件の等式および不等式と目的関数の少なくとも一つの式が非線形である計画問題である。特に、制約条件が線形不等式や線形等式で、かつ、目的関数が二次式である計画問題は、二次計画問題と呼ばれている。
このような非線形計画問題の解法には、幾つかの提案がなされている。例えば、特許文献１には、非線形計画問題を変形して線形計画問題に変換する方法が開示されている。また、特許文献２には、非線形要素を少なくして解法を簡単化する方法が開示されている。【０００５】
また、非特許文献１には、最急降下法、共役勾配法、ニュートン法、準ニュートン法、逐次二次計画法等の種々の非線形計画問題の解法が記載されている。これらの解法では、連続で微分可能な関数で表現された非線形計画問題を対象としている。【０００６】
一方、微分不可能な連続関数で表現された非線形計画に対しては、滑落シンプレックス法が知られている。このような方法を開示するものとして、特許文献３は、逐次二次計画法を用いたシステムを開示している。【０００７】
また、非特許文献２には、進化的計算手法の一つである差分（微分）進化法（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｅｖｏｌｕｔｉｏｎ）が記載されている。差分進化法は、不連続関数で表現された空間的に連続な非線形計画問題に対して適用可能であり、複数個体で構成される解候補群の世代交代を繰り返して計画問題を解く方法である。【０００８】
さらに、特許文献４には、非線形計画問題の解法の一つとして、小領域に分割して局所解の位置を推定し、推定された位置を出発点として計画問題を解く装置が開示されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２０１３−２５４３２９号公報
【特許文献２】特開２００７−１３３４８３号公報
【特許文献３】特許第５２４２３５５号公報
【特許文献４】特開平２−１７６９０４号公報
【非特許文献】
【００１０】
【非特許文献１】今野浩、山下浩、非線形計画法、日科技連出版、１９７８
【非特許文献２】Ｓｔｏｒｎ，  Ｒ．；  Ｐｒｉｃｅ，  Ｋ．  （１９９７）．  ”Ｄｉｆｆｅｒｅｎｔｉａｌ  ｅｖｏｌｕｔｉｏｎ  −  ａ  ｓｉｍｐｌｅ  ａｎｄ  ｅｆｆｉｃｉｅｎｔ  ｈｅｕｒｉｓｔｉｃ  ｆｏｒ  ｇｌｏｂａｌ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｏｖｅｒ  ｃｏｎｔｉｎｕｏｕｓ  ｓｐａｃｅｓ”．  Ｊｏｕｒｎａｌ  ｏｆ  Ｇｌｏｂａｌ  Ｏｐｔｉｍｉｚａｔｉｏｎ  １１：  ３４１−３５９．
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、特許文献１や又は特許文献２にかかる方法では、非線形問題を線形問題に簡略化して近似をするため、近似誤差が発生するという問題があった。【００１２】
また、特許文献３や又は非特許文献１にかかる方法では、計画問題を表現する関数の微分可能性や連続性が前提条件として要求される問題があった。【００１３】
また、非特許文献２にかかる方法では、計画問題を表現する関数の微分可能性や連続性は、前提条件として要求されないが、空間的に連続であることが要求される問題があった。【００１４】
また、非特許文献２にかかる方法では、複数個体に対して世代交代を繰り返すために計算回数が多くなり、計算に長大な時間を要する問題があった。【００１５】
さらに、特許文献４にかかる方法では、分割された領域をすべて探索するため、探索回数が増加して、計算に長大な時間を要する問題があった。【００１６】
そこで、本発明の主目的は、上記問題を鑑みなされたもので、問題を表現する関数の微分可能性及び連続性や空間の連続性を前提条件とせずに区分で定義された関数を含む計画問題を効率的に処理する非線形計画問題処理装置及び非線形計画問題処理方法を提供することである。
【課題を解決するための手段】
【００１７】
上記課題を解決するため、制約条件又は目的関数に区分的に定義された関数を含む非線形計画問題処理装置にかかる発明は、非線形計画問題を取得する非線形計画問題入力部と、非線形計画問題のある領域で求めた解を非線形計画問題の暫定解とする暫定解生成部と、暫定解の近傍領域で求めた解を非線形計画問題の解候補とする解候補生成部と、暫定解と解候補との比較結果に応じて、解候補を暫定解として更新する暫定解更新部と、暫定解の改善度合い又は解候補生成回数の少なくとも一方を判断基準として処理の終了を判定する終了判定部と、暫定解を出力する非線形計画問題解出力部と、を備えることを特徴とする。【００１８】
また、制約条件又は目的関数に区分的に定義された関数を含む非線形計画問題処理方法にかかる発明は、非線形計画問題を取得する非線形計画問題入力処理をし、非線形計画問題のある領域で解を求め、解を非線形計画問題の暫定解とする暫定解生成処理をし、暫定解の近傍領域で解を求め、解を非線形計画問題の解候補とする解候補生成処理をし、暫定解と解候補とを比較して暫定解を更新する暫定解更新処理をし、暫定解の改善度合い又は解候補生成回数の少なくとも一方を判断基準として処理の終了を判定する処理終了判定処理をし、暫定解を出力する非線形問題解出力処理をすることを特徴とする。
【発明の効果】
【００１９】
本発明に基づけば、計画問題を表現する関数の微分可能性及び連続性と、空間の連続性と、を前提とせず、区分的に定義された関数を含む非線形計画問題を効率的に処理する効果を得ることができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１実施形態にかかる非線形計画問題処理装置のブロック図である。
【図２】定義空間を変数で分割してなる区分を示した図である。
【図３】非線形計画問題処理装置の処理手順を示したフローチャートである。
【図４】暫定解生成部の詳細構成を例示したブロック図である。
【図５】解候補生成部の詳細構成を例示したブロック図である。
【図６】ケース１の場合における解候補生成部の動作を例示した図である。
【図７】ケース２の場合における解候補生成部の動作を例示した図である。
【図８】ケース３の場合における解候補生成部の動作を例示した図である。
【図９】ケース４の場合における解候補生成部の動作を例示した図である。
【図１０】ケース５の場合における解候補生成部の動作を例示した図である。
【図１１】ケース６の場合における解候補生成部の動作を例示した図である。
【図１２】本発明の第２実施形態にかかる処理装置の構成を示すブロック図である。
【発明を実施するための形態】
【００２１】
＜第１実施形態＞
本発明の実施形態を説明する。図１は本発明の第１実施形態にかかる非線形計画問題処理装置２Ａのブロック図である。また、図２は定義空間を変数で分割してなる区分を示した図である。また、図３は、非線形計画問題処理装置２Ａの処理手順を示したフローチャートである。
【００２２】
非線形計画問題処理装置２Ａは、非線形計画問題入力部１０、暫定解生成部２０、解候補生成部３０、暫定解更新部４０、終了判定部５０、及び、非線形計画問題解出力部６０を主要構成としている。
【００２３】
（非線形計画問題入力部１０）
非線形計画問題入力部１０は、区分的に定義された関数を含む非線形計画問題を取得する問題入力処理を行う（ステップＳ１）。この非線形計画問題はユーザが入力した問題である。なお、非線形計画問題とは、等式又は不等式の制約条件と目的関数とを含み、制約条件や目的関数の少なくとも一方の一部が、非線形計画問題に対して、目的関数を最小化又は最大化する解を求める問題である。また、区分的に定義された関数とは、関数の定義域を定める上限値と下限値との少なくとも一方が、有限な値をとる区分（定義域）で定義された関数の集合である。特に、各区分が線形関数となっているものは区分線形関数と呼ばれ、各区分が二次関数となっているものは区分二次関数と呼ばれる。
【００２４】
今、取得された非線形計画問題が、図２に示すように、定義空間Ｋで定義された問題で、制約条件と目的関数のどちらもが区分線形関数であるとする。このとき、一つの変数１は区分Ｒ１＿ａ、Ｒ１＿ｂ、Ｒ１＿ｃで定義され、他の変数２は区分Ｒ２＿ａ、Ｒ２＿ｂで定義されるとする。この場合、定義空間Ｋは、これらの区分の組み合わせで決まる領域Ｋ１、Ｋ２、Ｋ３、Ｋ４に分割されていることになる。そして、そのうちの一つの領域では、制約条件と目的関数とは、線形関数である。
【００２５】
（暫定解生成部２０）
暫定解生成部２０は、ある一つの領域Ｋ１（これを暫定解領域と呼ぶ）で線形計画問題の解を求め、この解を暫定解Ｐａ＿１とする暫定解生成処理（ステップＳ２）を行う。
【００２６】
（解候補生成部３０）
解候補生成部３０は、定義空間Ｋ内で、暫定解領域Ｋ１と異なる別の領域Ｋ２（これを解候補領域と呼ぶ）で線形計画問題の解を求め、この解を解候補Ｐｂ＿１とする解候補生成処理（ステップＳ３）を行う。
【００２７】
（暫定解更新部４０）
暫定解更新部４０は、解候補Ｐｂ＿１と暫定解Ｐａ＿１とが与える目的関数の値を比較する。この比較の結果、解候補Ｐｂ＿１による値が暫定解Ｐａ＿１による値よりも優れていれば、常に解候補Ｐｂ＿１を新たな暫定解とし、解候補領域Ｋ２を新たな暫定解領域としてそれぞれを更新する。一方、解候補Ｐｂ＿１が暫定解Ｐａ＿１よりも優れていなければ、確率的に解候補Ｐｂ＿１を新たな暫定解とし、解候補領域Ｋ２を新たな暫定解領域としてそれぞれを更新する。
【００２８】
なお、解が優れているとは、目的関数の値が最小となる条件を求める問題の場合には、解候補Ｐｂ＿１が暫定解Ｐａ＿１より小さいことであり、目的関数の値が最大となる条件を求める問題の場合には、解候補Ｐｂ＿１が暫定解Ｐａ＿１より大きいことを言う。
【００２９】
また、確率の算出方法には、ｏｂｊｎｅｗを解候補の目的関数の値、ｏｂｊｏｌｄを暫定解の目的関数の値、ａを０より大きな適当な実数としたとき、ｅ−｜ｏｂｊｎｅｗ−ｏｂｊｏｌｄ｜＊ａにより与える方法が例示できる。このとき、更新する確率は、解候補Ｐｂ＿１が暫定解Ｐａ＿１よりも劣っているほど低く、かつ、あるいは解候補生成回数が多いほど低くするように変化させてもよい。
このような、確率的に解を更新することにより、解候補Ｐｂ＿１が暫定解Ｐａ＿１よりも優れていない場合でも、局所的な最適解が求められることが防止できる。即ち、解候補が優れていない場合でも、常に暫定解を更新しないようにすると、局所的な最適解が選択される可能性が高くなる。そこで、解が優れていない場合には、常に更新せずに破棄するのではなく、確率的に更新することで局所的な最適解が選択することを防止している。
【００３０】
（終了判定部５０）
終了判定部５０は、上述したような処理を中止するか否かを判断する（ステップＳ５）。このときの判断は、暫定解の改善度合い（直前の暫定解の目的関数の値と新たに採用した目的関数の値の差）あるいは解候補生成回数の少なくとも一方を判定基準として、改善度合いの絶対値が判定基準以下になった場合、又は、解候補生成回数が判定基準以上になった場合には、処理を終了すると判断する。
【００３１】
この結果、この条件を満たさないと判断した場合には、ステップＳ３に戻り処理を続け、条件を満たす場合にはステップＳ６に進む。
【００３２】
非線形計画問題解出力部６０は、求められた暫定解を出力する。
【００３３】
次に、暫定解生成部２０の詳細構成を説明する。図４は、暫定解生成部２０の詳細構成を例示したブロック図である。暫定解生成部２０は、暫定解領域選択部２１と、解計算部２２と、暫定解生成終了判定部２３と、を含んでいる。
【００３４】
そして、暫定解領域選択部２１は、定義空間Ｋ内にある一つの領域を選択する。選択する方法は、ランダム、定義空間の中での大きさが最大の領域（最大の領域）、定義空間の中心位置（ある変数の定義域の中心の集合）の領域等がある。最大の領域は、定義空間が２次元の場合には面積が最大の領域であり、３次元の場合には体積が最大の領域である。例えば、領域の変数の定義域（区分線形関数に紐づいている）を、［Ｘ＿ｉ＿ｍｉｎ，Ｘ＿ｉ＿ｍａＸ］、Ｘ＿ｉ＿ｒａｎｇｅ＝Ｘ＿ｉ＿ｍａＸ−Ｘ＿ｉ＿ｍｉｎとすると、領域の大きさはＸ＿１＿ｒａｎｇｅ×Ｘ＿２＿ｒａｎｇｅ×．．．×Ｘ＿Ｎ＿ｒａｎｇｅで与える。ただし、Ｎは変数の数である。
【００３５】
解計算部２２は、暫定解領域選択部２１で選択された領域で線形計画問題を解く。このとき、単体法等の線形計画問題の解法を使うことができる。特に、整数解であることが要求されている場合、整数線形計画問題として扱うことができるため、既に知られている分枝限定法等の整数線形計画問題の解法を使うことができる。なお、解法は、問題の性質（整数に限定されているか）等により予め決まっている。従って、解計算部２２には予め問題の性質に適応した解法が格納されている。
【００３６】
暫定解生成終了判定部２３は、解計算部２２で解が求まらなかった場合、再度暫定解領域選択部２１で異なる領域を選択する。解が求まらなかった場合として、例えば、制約条件が、Ｘ＋５＝０かつＸ＞０で、目的関数（最大化）がＦ（Ｘ）＝Ｘのときが例示できる。一方、解が求まった場合、暫定解生成部２０の処理は終了する。
【００３７】
次に、解候補生成部３０の詳細構成について説明する。図５は、解候補生成部３０の詳細構成を例示したブロック図である。解候補生成部３０は、解候補領域選択部３１と、解計算部３２と、解候補生成終了判定部３３とを含んでいる。
【００３８】
解候補領域選択部３１は、定義空間Ｋ内で、暫定解領域Ｋ１とは異なるある一つの領域を選択する。選択の具体例については、後述する。
【００３９】
解計算部３２は、解候補領域選択部３１で選択された領域で、解計算部２２における解法と同様の解法に従い計画問題を解く。
【００４０】
解候補生成終了判定部３３は、解計算部３２で解が求まらなかった場合、再度、解候補領域選択部３１で異なる領域を選択する。一方、解が求まった場合は処理を終了する。
【００４１】
次に、解候補生成部３０において次の区分を選択し、解候補を求める際の例を説明する。
【００４２】
（ケース１）：暫定解領域の近傍にある領域から任意の一つの領域を解候補領域とする場合
図６は、ケース１の場合における解候補生成部３０の動作を例示した図である。この場合、解候補生成部３０に含まれる解候補領域選択部３１は、定義空間Ｑ内で暫定解領域Ｑ１の近傍にある領域から任意の一つの領域（例えば領域Ｑ２）を解候補領域として選択する。そして、解候補生成部３０に含まれる解計算部３２は、解候補領域Ｑ２内で計画問題の解を求める。
【００４３】
（ケース２）：暫定解から所定距離にある任意点を含む領域を解候補領域とする場合
図７は、ケース２の場合における解候補生成部３０の動作を例示した図である。この場合、解候補生成部３０に含まれる解候補領域選択部３１は、定義空間Ｑ内で暫定解領域Ｑ１を除き、暫定解Ｐから所定距離ｒにある任意の一点Ｐｋを含む領域Ｑ２を解候補領域として選択する。なお、距離ｒは例えば、初期パラメータとして設定することができる。
【００４４】
このとき、繰り返し回数の増加につれて距離ｒを減少させてもよい。これは、繰り返し回数が増加することにより、暫定解は最適解に近づいていると考えることができる。このような場合に、距離を変えなかったり、距離を大きくしたりすると、最適解から離れてしまう場合が生じる。そこで、繰り返し回数の増加につれて距離ｒを減少させて、暫定解の近傍を探索することにより、最適解を効率的に探索できるようにする。
【００４５】
そして、解候補生成部３０に含まれる解計算部３２は、解候補領域Ｑ２内で計画問題の解を求める。
【００４６】
（ケース３）：更新直前の暫定解から次の暫定解への延長方向に位置する領域を解候補領域とする場合
図８は、ケース３の場合における解候補生成部３０の動作を例示した図である。この場合、解候補生成部３０に含まれる解候補領域選択部３１は、更新直前の暫定解Ｐｍから暫定解Ｐへの延長方向にあって、暫定解Ｐに最も近い領域Ｑ２を解候補領域として選択する。そして、解候補生成部３０に含まれる解計算部３２は、解候補領域Ｑ２内で計画問題の解を求める。
【００４７】
（ケース４）：更新直前の暫定解領域の重心から暫定解への延長方向に位置する領域を解候補領域とする場合
図９は、ケース４の場合における解候補生成部３０の動作を例示した図である。この場合、解候補生成部３０に含まれる解候補領域選択部３１は、更新直前の暫定解領域Ｑ４の重心Ｇ１から暫定解Ｐへの延長方向にあって、暫定解Ｐに最も近い領域Ｑ２を解候補領域として選択する。そして、解候補生成部３０に含まれる解計算部３２は、解候補領域Ｑ２内で計画問題の解を求める。
【００４８】
（ケース５）：暫定解領域の未選択近傍領域における評価値が最良である領域を解候補領域する場合
図１０は、ケース５の場合における解候補生成部３０の動作を例示した図である。解候補生成部３０に含まれる解候補領域選択部３１は、暫定解領域Ｑ１の近傍で、未だ選択されていない領域（領域Ｑ２、領域Ｑ３）の評価値を以下に述べる方法で求め、評価値が最良である領域（領域Ｑ２）を解候補領域として選択する。
【００４９】
なお、評価値を求める方法は、ある領域の評価値を、その領域の近傍領域であって、既に選択されて解が求まった領域の目的関数の値の平均値とする方法である。即ち、評価値は目標関数の値とする。このとき、評価値が最良である領域とは、最適化問題には目的関数を最大化する場合と最小化する場合がある。最大化する場合は「評価値が高い」、最小化する場合は「評価値が低い」領域をいう。
【００５０】
例えば、領域Ｑ２の評価値は、領域Ｑ２の近傍領域であって、既に選択されて解が求まった領域（領域Ｑ１、領域Ｑ４、領域Ｑ５）のそれぞれの目的関数の値（５、４、３）の平均値４（＝（５＋４＋３）／３）である。なお、最初の評価値は、既に選択されて解が求まった領域が他にないので、未定義とする。
【００５１】
また、領域Ｑ３の評価値は、領域Ｑ３の近傍領域であって、既に選択されて解が求まった領域（領域Ｑ１、領域Ｑ６）のそれぞれの目的関数の値（５、１）の平均値３（＝（５＋１）／２）である。非線形計画問題が目的関数の値が最大となる条件を求める場合には、解候補領域選択部３１は、評価値の最も高い解候補領域Ｑ２を選択し、解計算部３２は、選択された解候補領域Ｑ２内で計画問題の解を求めることになる。
（ケース６）：暫定解領域の近傍で、未選択領域の評価値が最良である領域を解候補領域とする場合
図１１は、ケース６の場合の解候補生成部３０の動作を例示した図である。解候補生成部３０に含まれる解候補領域選択部３１は、暫定解領域Ｑ１の近傍で、未だ選択されていない領域（領域Ｑ２、領域Ｑ３）の評価値を以下に述べる方法で求め、評価値が最良である領域（領域Ｑ２）を解候補領域として選択する。未だ選択されていない領域すべての評価値が未定義であれば、任意の領域を解候補領域として選択する。
【００５２】
なお、評価値が最良である領域は、他の領域に比べてよりよい解（目的関数の値が改善する）を得られる可能性がある領域である。即ち、評価値が最良である領域は、周囲の領域の目的関数の値がよりよい解が存在する領域であり、そのような領域に囲まれている領域には目的関数の値がより良い解が存在すると期待される。
【００５３】
評価値を求める方法は、暫定解領域の目的関数の値と、暫定解領域Ｑ１の近傍で、未だ選択されていない領域の一つ重心から暫定解領域Ｑ１の重心Ｇ２への延長方向であって、暫定解領域Ｑ１の重心Ｇ２に最も近い領域の目的関数の値との差に、暫定解領域Ｑ１の目的関数の値を足した値とする方法である。例えば、Ａ，Ｂ，Ｃの３点が並んでおり、ＡとＢの値が既知で、Ｃの値を推定する場合を想定する。この場合、最も簡単な方法は、（Ｂ−Ａ）＋Ｂである。そこで、上記差を（Ｂ−Ａ）とし、暫定解領域Ｑ１の目的関数の値がＢに相当する。
【００５４】
ただし、暫定解領域Ｑ１の近傍で、未だ選択されていない領域の一つ重心から暫定解領域Ｑ１の重心Ｇ２への延長方向であって、暫定解領域Ｑ１の重心Ｇ２に最も近い領域が未だ選択されていない領域であれば評価値を未定義とする。
【００５５】
例えば、領域Ｑ２の評価値は、暫定解領域Ｑ１の目的関数の値（５）と、領域Ｑ２の重心Ｇ３から暫定解領域Ｑ１の重心Ｇ２への延長方向であって、暫定解領域Ｑ１の重心Ｇ２に最も近い領域Ｑ８の目的関数の値（４）との差１（＝５−４）に、暫定解領域Ｑ１の目的関数（５）の値を足した値６（＝１＋５）である。
【００５６】
また、領域Ｑ３の評価値は、暫定解領域Ｑ１の目的関数の値（５）と、領域Ｑ３の重心Ｇ４から暫定解領域Ｑ１の重心Ｇ２への延長方向であって、暫定解領域Ｑ１の重心Ｇ２に最も近い領域Ｑ９の目的関数の値（６）との差−１（＝５−６）に、暫定解領域Ｑ１の目的関数（５）の値を足した値４（＝−１＋５）である。
【００５７】
目的関数の値を最大化する非線形計画問題であるとすると、解候補領域選択部３１は、評価値の最も高い解候補領域Ｑ２を選択し、解計算部３２は、選択された解候補領域Ｑ２内で計画問題の解を求める。
【００５８】
以上説明したように、非線形計画問題処理装置２Ａは、非線形計画問題を線形近似することがないため、近似誤差が発生しない効果が得られる。即ち、与えられる非線形計画問題は、複数の区分線形関数で表現されていることを前提としているため、区分ごとに考えれば線形式だけで表現されていることになり、線形近似が不要になる。従って、線形近似による誤差の発生が防止できる。
【００５９】
また、非線形計画問題処理装置２Ａは、非線形計画問題が区分の間で不連続、微分不可能であっても、区分の中では連続で微分可能な線形計画問題になるので、解くことができる効果が得られる。即ち、与えられる非線形計画問題は、複数の区分線形関数で表現されていることを前提としているので、非線形計画問題処理装置２Ａで区分を設定する必要がなくなり、区分の中では連続で微分可能な線形計画問題とすることができるようになる。
【００６０】
また、複数個体を生成して世代交代する場合は、生成個体の数をＮ、世代交代の数をＭとするとＮ×Ｍの計算回数が必要になるため、より最適な（目的関数が最良の）解を求めようとするとＮとＭが大きくなり計算回数が多くなる。しかし、非線形計画問題処理装置２Ａは、複数個体を生成して世代交代を繰り返すことがないため、計算回数が多くならない。従って、計算時間を短くすることが可能になる。
【００６１】
さらに、非線形計画問題処理装置２Ａは、選択された領域でのみ計画問題を解き、全領域を探索しないので、計算時間を短くすることが可能になる。即ち、全領域の数をＮ、選択された領域の数をＭとするとＮ＞Ｍが常に成り立ち、計算回数（時間）はＮ又はＭに比例するので、全領域を探索しない方が計算回数（時間）を少なく（短く）できる。
【００６２】
＜第２実施形態＞
次に、本発明の第２実施形態を説明する。なお、第一実施形態と同一構成に関しては同一符号を用いて説明を適宜省略する。
【００６３】
図１２は、本発明の第２実施形態にかかる非線形計画問題処理装置２Ｂのブロック図である。非線形計画問題処理装置２Ｂは、上述した非線形計画問題処理装置２Ａに対して領域・解情報蓄積部７０が追設されている点が相違する。なお、初期状態においては、領域・解情報蓄積部７０は、空になっているものとする。
【００６４】
暫定解領域選択部２１は、領域・解情報蓄積部７０に蓄積された領域情報を参照し、領域・解情報蓄積部７０に蓄積されていない領域を暫定解領域として選択し、選択した領域を領域・解情報蓄積部７０に追加する。
【００６５】
解計算部２２は、解計算部２２で求めた解を領域・解情報蓄積部７０に追加する。解候補領域選択部３１は、領域・解情報蓄積部７０に蓄積された領域情報を参照し、解候補領域を選択する。領域・解情報蓄積部７０に蓄積されていない領域を解候補領域として選択してもよい。解候補領域選択部３１は、選択した領域を領域・解情報蓄積部７０に追加する。
【００６６】
解計算部３２は、領域・解情報蓄積部７０を参照し、解候補領域の解が、領域・解情報蓄積部７０に蓄積されていれば、蓄積されている解を解計算部３２で求めるべき解であると判断する。
【００６７】
一方、解候補領域の解が、領域・解情報蓄積部７０に蓄積されていなければ、解計算部３２は、解候補領域選択部３１で選択された領域で解を求め、求めた解を領域・解情報蓄積部７０に追加する。
【００６８】
なお、終了判定部５０は、終了判定のために領域・解情報蓄積部７０を参照してもよい。参照することによって、解の履歴を参考にした終了判定ができるようになる。例えば、一定の繰り返し回数の間、解の改善がない場合は、繰り返し処理を終了すると判定してもよい。あるいは、解候補領域の選択パターンが一定回数繰り返される場合は、処理を終了すると判定してもよい。
【００６９】
また、非線形計画問題解出力部６０は、領域・解情報蓄積部７０を参照して解を出力してもよい。領域・解情報蓄積部７０を参照することで、優れた解を複数出力することができる。これにより、非線形計画問題処理装置２Ｂは、効率的に解を求めることができるようになる。
【００７０】
以上説明した構成により、暫定解領域選択部２１と解候補領域選択部３１とが領域・解情報蓄積部７０に蓄積された領域、即ち既に解を求めたことのある領域と異なる領域を選択することができるようになる。従って、計算回数を減らせることができるようになる。
【００７１】
また、解計算部３２は、領域・解情報蓄積部７０を参照するため、既に計画問題を解いた解候補領域であれば、再び計画問題を解くことなく解を求めることができるようになる。
【００７２】
そして、これらにより非線形計画問題処理装置２Ｂは、効率的に解を求めることができるようになる。
【００７３】
なお、第１実施形態と第２実施形態とでは、制約条件と目的関数のどちらもが区分線形関数であるとして、解計算部２２、３２では線形計画問題の解法を用いた。しかし、制約条件が区分線形関数で、目的関数が区分二次関数である場合、解計算部２２、３２は二次計画問題の解法を用いることができる。
【００７４】
以上説明した各実施形態により、本発明は限定されるものではなく、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【００７５】
本発明の非線形計画問題処理装置は、設計パラメータの決定、配車・配送計画、列車運行計画、プラント運転パラメータの決定、産業用プロセス装置の運転・メンテナンス計画、電力需要に合わせた発電機運転計画、エネルギー供給計画、建物内の環境制御、農林水産業や畜産業等の環境制御、マニピュレータ、陸上移動体、水上・水中移動体、空中移動体等のアクチュエーションの制御タスク割り当てに適用できる。
以上、実施形態（及び実施例）を参照して本願発明を説明したが、本願発明は上記実施形態（及び実施例）に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
この出願は、２０１４年６月５日に出願された日本出願特願２０１４−１１６６２６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００７６】
１０    非線形計画問題入力部
２０    暫定解生成部
２１    暫定解領域選択部
２２    解計算部
２３    暫定解生成終了判定部
３０    解候補生成部
３１    解候補領域選択部
３２    解計算部
３３    解候補生成終了判定部
４０    暫定解更新部
５０    終了判定部
６０    非線形計画問題解出力部
７０    領域・解情報蓄積部
【図１】
2015186338.tif 000003
【図２】
2015186338.tif 000004
【図３】
2015186338.tif 000005
【図４】
2015186338.tif 000006
【図５】
2015186338.tif 000007
【図６】
2015186338.tif 000008
【図７】
2015186338.tif 000009
【図８】
2015186338.tif 000010
【図９】
2015186338.tif 000011
【図１０】
2015186338.tif 000012
【図１１】
2015186338.tif 000013
【図１２】
2015186338.tif 000014
【国際調査報告】
2015186338.tif 000015
2015186338.tif 000016
2015186338.tif 000017
2015186338.tif 000018