(57)【要約】【課題】組み合わせ最適化問題を、局所解に陥る確率を低くし、かつ高速に解くことのできる組み合わせ最適化システムを得る。【解決手段】現在の状態から離散変数の値を大きく変動させた隣接状態の集合を第２近傍と定義し、第２近傍生成手段２２、最適解・最良解更新手段２４、タブーリスト更新手段２５および第２近傍探索終了判定手段２６の処理を実行して、第２近傍を隣接状態と見なして最適化する第２近傍探索手段３３と、現在の状態から離散変数を小さく変動させた隣接状態の集合を第１近傍と定義し、第１近傍生成手段２８、最適解・最良解更新手段２４、タブーリスト更新手段２５および第１近傍探索終了判定手段２９の処理を実行して、第１近傍を隣接状態と見なして最適化する第１近傍探索手段３４とを備えている。【選択図】図１
2009048353.tif 000002
【特許請求の範囲】
【請求項１】
組み合わせ最適化問題を解くための組み合わせ最適化システムであって、
最適化条件、全離散変数のリストと最小変動幅・上下限値とで定義される離散変数リスト、および、最適化の過程で変動幅を調整する離散変数のリストとこれら離散変数のリストの各初期変動幅とで定義される変動幅調整変数リスト、を記憶する記憶手段と、
探索の初期では前記変動幅調整変数リストの変動幅を前記初期変動幅で変動させながら最適化を行う第２近傍探索手段と、
前記第２近傍探索手段による第２近傍探索の終了後に、全離散変数の変動幅を前記最小変動幅で変動させながら最適化を行う第１近傍探索手段と、
前記第２近傍探索と前記第１近傍探索手段による第１近傍探索とを実行する制御プログラムと
を備えたことを特徴とする組み合わせ最適化システム。
【請求項２】
前記最適化条件は、最適化の目的、制約条件および設備データを含むことを特徴とする請求項１に記載の組み合わせ最適化システム。
【請求項３】
前記最適化条件、前記離散変数リストおよび前記変動幅調整変数リストを入力する入力手段と、
前記最適化条件、前記離散変数リストおよび前記変動幅調整変数リストの少なくとも一部をファイル・データベースとして記録する記録手段と、
前記記録手段から前記最適化条件、前記離散変数リストおよび前記変動幅調整変数リストを読み出して前記記憶手段に記憶させる記録データ取得手段と、
前記最適化条件、前記離散変数リストおよび前記変動幅調整変数リストのデフォルト値を取得して前記記憶手段に記憶させるデフォルト値取得手段と、
与えられた離散変数値に対する評価関数値を前記最適化条件にしたがって演算する評価関数値演算手段と、
前記最適化の過程で過去最も評価関数値が優れた解である最適解を構成する離散変数値および評価関数値を記憶する最適解記憶手段と、
前記最適化の過程での一時的な解である最良解を構成する離散変数値および評価関数値を記憶する最良解記憶手段と、
前記記憶手段から全離散変数のリストを読み出して、前記記憶手段から読み出した最適化条件を満たすように前記全離散変数の初期値を生成し、前記評価関数値演算手段で演算された評価関数値を前記最適解記憶手段および前記最良解記憶手段に記憶させる初期解生成手段と、
過去の最良解のリストからなるタブーリストを記憶するタブーリスト記憶手段と、
前記タブーリストをクリアして、前記最適解記憶手段から読み出した最適解を追加したタブーリストを前記タブーリスト記憶手段に記憶させるタブーリスト初期化手段と、
前記記憶手段から読み出した最適化条件、変動幅を調整する離散変数のリストおよび変動幅、変動幅を調整しない離散変数のリスト、最小変動幅および全離散変数の上下限値と、前記最良解記憶手段から読み出した現在の最良解を構成する離散変数値および評価関数値とに基づいて、次の最良解候補である隣接状態を複数生成し、前記評価関数値演算手段により全隣接状態の評価関数値を演算し、前記全隣接状態の離散変数値および評価関数値を前記記憶手段に記憶させる第２近傍生成手段と、
前記記憶手段から全隣接状態を読み出し、前記最適解記憶手段および前記最良解記憶手段から現在の最適解および最良解を読み出して、前記全隣接状態と現在の最良解とから次の最良解を選択し、前記次の最良解を構成する離散変数値および評価関数値を前記最良解記憶手段に記憶させ、前記次の最良解の評価関数値が現在の最適解の評価関数値よりも優れている場合には、前記次の最良解を構成する離散変数値および評価関数値を前記最適解記憶手段に記憶させる最適解・最良解更新手段と、
前記最良解記憶手段から最良解を読み出し、前記タブーリスト記憶手段からタブーリストを読み出し、前記タブーリストに保存されている最良解の数が前記タブーリストの長さに達している場合には、前記タブーリスト内の最も古い最良解を破棄して現在の最良解を追加した新しいタブーリストを前記タブーリスト記憶手段に記憶させるタブーリスト更新手段と、
前記記憶手段から読み出した最適化条件に基づいて、前記第２近傍探索の終了条件を満たすか否かを判定し、前記第２近傍探索の終了条件を満たすと判定された場合には前記第１近傍探索に移行し、前記第２近傍探索の終了条件を満たさない場合には、前記第２近傍生成手段の処理に復帰させる第２近傍探索終了判定手段とを備え、
前記第２近傍探索手段は、前記第２近傍生成手段、前記最適解・最良解更新手段、前記タブーリスト更新手段および前記第２近傍探索終了判定手段による一連の処理を実行することを特徴とする請求項１または請求項２に記載の組み合わせ最適化システム。
【請求項４】
前記最適解記憶手段から最適解を読み出して前記最良解記憶手段に記憶させる第１近傍探索初期解生成手段と、
前記記憶手段から読み出した最適化条件、全離散変数に関するリスト、最小変動幅および上下限値と、前記最良解記憶手段から読み出した現在の最良解を構成する離散変数値および評価関数値とに基づいて、次の最良解候補である隣接状態を複数生成し、前記評価関数値演算手段により全隣接状態の評価関数値を演算し、前記全隣接状態の離散変数値および評価関数値を前記隣接状態記憶手段に記憶させる第１近傍生成手段と、
前記記憶手段から読み出した最適化条件に基づいて、前記第１近傍探索の終了条件を満たすか否かを判定し、前記第１近傍探索の終了条件を満たすと判定された場合には前記第１近傍探索を終了し、前記第１近傍探索の終了条件を満たさない場合には、前記第１近傍生成手段の処理に復帰させる第１近傍探索終了判定手段と、
前記最適解を構成する離散変数値および評価関数値を出力する最適化結果出力手段と、
前記最適解を構成する離散変数値および評価関数値をファイル・データベースとして記録する最適化結果記録手段と、
前記第１近傍探索の終了後に、前記最適化結果記録手段に最適化結果を記録するとともに、前記最適化結果出力手段により前記最適化結果を出力させる最適化結果記録・出力処理手段とを備え、
前記第１近傍探索手段は、前記第１近傍生成手段、前記最適解・最良解更新手段、前記タブーリスト更新手段および前記第１近傍探索終了判定手段による一連の処理を実行することを特徴とする請求項３に記載の組み合わせ最適化システム。
【請求項５】
組み合わせ最適化問題を解くための組み合わせ最適化システムであって、
最適化条件、全離散変数のリストと最小変動幅・上下限値とで定義される離散変数リスト、最適化の過程で変動幅を調整する離散変数のリストとこれら離散変数のリストの各初期変動幅とで定義される変動幅調整変数リスト、および、近傍探索の段階を示すカウンタ変数、を記憶する記憶手段と、
前記カウンタ変数が値ｎのときに、前記変動幅調整変数リストの変動幅を前記カウンタ変数の値ｎごとに異なる変動幅Ｗ＿ｎで変動させながら最適化を行う第Ｎ−ｎ近傍探索手段と、
前記カウンタ変数の値ｎを更新するカウンタ変数更新手段と、
前記第Ｎ−ｎ近傍探索手段による第Ｎ−ｎ近傍探索の実行時の変動幅Ｗ＿ｎを更新する変動幅更新手段と、
前記カウンタ変数の値ｎを増加させながら前記第Ｎ−ｎ近傍探索を順次実行する制御プログラムと
を備えたことを特徴とする組み合わせ最適化システム。
【請求項６】
前記最適化条件は、最適化の目的、制約条件および設備データを含むことを特徴とする請求項５に記載の組み合わせ最適化システム。
【請求項７】
前記最適化条件、前記離散変数リストおよび前記変動幅調整変数リストを入力する入力手段と、
前記最適化条件、前記離散変数リストおよび前記変動幅調整変数リストの少なくとも一部をファイル・データベースとして記録する記録手段と、
前記記録手段から前記最適化条件、前記離散変数リストおよび前記変動幅調整変数リストを読み出して前記記憶手段に記憶させる記録データ取得手段と、
前記最適化条件、前記離散変数リストおよび前記変動幅調整変数リストのデフォルト値を取得して前記記憶手段に記憶させるデフォルト値取得手段と、
与えられた離散変数値に対する評価関数値を前記最適化条件にしたがって演算する評価関数値演算手段と、
前記最適化の過程で過去最も評価関数値が優れた解である最適解を構成する離散変数値および評価関数値を記憶する最適解記憶手段と、
前記最適化の過程での一時的な解である最良解を構成する離散変数値および評価関数値を記憶する最良解記憶手段と、
前記記憶手段から全離散変数のリストを読み出して、前記記憶手段から読み出した最適化条件を満たすように前記全離散変数の初期値を生成し、前記評価関数値演算手段で演算された評価関数値を前記最適解記憶手段および前記最良解記憶手段に記憶させる初期解生成手段と、
前記記憶手段から読み出したカウンタ変数の値ｎを「０」に設定して前記カウンタ記憶手段に記憶させるカウンタ初期化手段と、
過去の最良解のリストからなるタブーリストを記憶するタブーリスト記憶手段と、
前記タブーリストをクリアして、前記最適解記憶手段から読み出した最適解を追加したタブーリストを前記タブーリスト記憶手段に記憶させるタブーリスト初期化手段と、
前記記憶手段から読み出した最適化条件、変動幅を調整する離散変数のリストおよび変動幅Ｗ＿ｎ、変動幅を調整しない離散変数のリスト、最小変動幅および全離散変数の上下限値と、前記最良解記憶手段から読み出した現在の最良解を構成する離散変数値および評価関数値とに基づいて、次の最良解候補である隣接状態を複数生成し、前記評価関数値演算手段により全隣接状態の評価関数値を演算し、前記全隣接状態の離散変数値および評価関数値を前記記憶手段に記憶させる第Ｎ−ｎ近傍生成手段と、
前記記憶手段から全隣接状態を読み出し、前記最適解記憶手段および前記最良解記憶手段から現在の最適解および最良解を読み出して、前記全隣接状態と現在の最良解とから次の最良解を選択し、前記次の最良解を構成する離散変数値および評価関数値を前記最良解記憶手段に記憶させ、前記次の最良解の評価関数値が現在の最適解の評価関数値よりも優れている場合には、前記次の最良解を構成する離散変数値および評価関数値を前記最適解記憶手段に記憶させる最適解・最良解更新手段と、
前記最良解記憶手段から最良解を読み出し、前記タブーリスト記憶手段からタブーリストを読み出し、前記タブーリストに保存されている最良解の数が前記タブーリストの長さに達している場合には、前記タブーリスト内の最も古い最良解を破棄して現在の最良解を追加した新しいタブーリストを前記タブーリスト記憶手段に記憶させるタブーリスト更新手段と、
前記記憶手段から読み出した最適化条件に基づいて、前記第Ｎ−ｎ近傍探索の終了条件を満たすか否かを判定し、前記第Ｎ−ｎ近傍探索の終了条件を満たすと判定された場合には前記第Ｎ−ｎ近傍探索を終了し、前記第Ｎ−ｎ近傍探索の終了条件を満たさない場合には、前記第Ｎ−ｎ近傍生成手段の処理に復帰させる第Ｎ−ｎ近傍探索終了判定手段と、
前記カウンタ記憶手段から読み出したカウンタ変数ｎを「ｎ＋１」に設定して前記カウンタ記憶手段に記憶させ、前記変動幅調整変数リスト記憶手段から読み出した変動幅Ｗ＿ｎを更新して前記変動幅調整変数リスト記憶手段に記憶させ、前記最適解記憶手段から読み出した最適解を前記最良解記憶手段に記憶させる第Ｎ−ｎ近傍探索条件更新手段と、
前記記憶手段から読み出した最適化条件に基づいて、全探索の終了条件を満たすか否かを判定し、前記全探索の終了条件を満たすと判定された場合には前記全探索を終了し、前記全探索の終了条件を満たさない場合には前記第Ｎ−ｎ近傍探索条件更新手段の処理に移行する全探索終了判定手段と、
前記最適解を構成する離散変数値および評価関数値を出力する最適化結果出力手段と、
前記最適解を構成する離散変数値および評価関数値をファイル・データベースとして記録する最適化結果記録手段と、
前記全探索の終了後に、前記最適化結果記録手段に最適化結果を記録するとともに、前記最適化結果出力手段により前記最適化結果を出力させる最適化結果記録・出力処理手段とを備え、
前記第Ｎ−ｎ近傍探索手段は、前記第Ｎ−ｎ近傍生成手段、前記最適解・最良解更新手段、前記タブーリスト更新手段および前記第Ｎ−ｎ近傍探索終了判定手段による一連の処理を実行することを特徴とする請求項５または請求項６に記載の組み合わせ最適化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の電源（発電機）の運転計画などに適用可能な、離散値を変数とする組み合わせ最適化問題を解くための組み合わせ最適化システムに関するものである。
【背景技術】
【０００２】
一般に、多くの組み合わせ最適化問題は、厳密な最適解を求めることが極めて困難なことが知られている。実用的な計算時間で十分精度の高い解を求めるシステムとして、近年、局所探索法、タブー探索、シミュレーティッドアニーリングなどの、メタヒューリスティクスに関する研究が盛んに行われている。また、従来から、メタヒューリスティクスの枠組みとは無関係に、効率的に最適解を求める技術も提案されている。
【０００３】
従来の組み合わせ最適化システムとして、高速化を実現するために、離散変数の一部またはすべてを連続変数として扱うことにより、解くべき組み合わせ最適化問題の規模を縮小して、高速化を実現する技術が提案されている（たとえば、特許文献１参照）。
【０００４】
また、他の従来システムとして、局所最適解に陥る確率を小さくするために、制約条件を満たさない状態への遷移を認めるという技術も提案されている（たとえば、特許文献２参照）。
さらに、他の従来システムとして、高速化するとともに、局所最適解に陥る確率を小さくするために、対象を発電機の運転計画に限定して、或る特徴的な時刻の運転状態を固定して問題を解くという技術も提案されている（たとえば、特許文献３参照）。
【０００５】
ここで、メタヒューリスティクスによる組み合わせ最適化問題の解法の一般的枠組みについて、イメージを示した図６の説明図を参照しながら説明する。
一般に、メタヒューリスティクスは、近傍探索を基本とした解法であり、現在の状態に対して、離散変数の一部の値を変更した複数の「隣接状態」（図６の左上部分を例にとると、１点鎖線枠内の白丸および黒丸）を生成し、現在の状態の評価関数値とこれら複数の隣接状態の評価関数値とを比較して、最も評価関数値が優れた点（隣接状態または現在の状態）を、次の現在の状態として更新する。以下、この処理を繰り返し実行することにより、最適解を求める。
【０００６】
ただし、上記のような組み合わせ最適化問題を解くための組み合わせ最適化システムでは、図６内の下段の特性曲線で示すように、一般に評価関数値の収束に時間がかかり、探索がなかなか進まない。すなわち、実用規模の問題では、最適解を得るまでに膨大な処理時間を要するという課題がある。
なお、探索領域を小さく設定すれば、計算時間の短縮を図ることも可能であるが、この場合、初期値に依存した局所解に陥ってしまうという課題が生じる。
【０００７】
たとえば、特許文献１では、第１の課題、すなわち最適解を得るまでに膨大な処理時間がかかるという課題を改善するために、離散変数の一部またはすべてを連続変数として扱うことにより、解くべき組み合わせ最適化問題の規模を縮小して、高速化を実現するシステムが提案されている。しかしながら、このシステムでは、対象とする問題によっては、制約条件の非線形性に起因して、離散変数を連続変数化することが可能とは限らず適用対象が限定されているので、そのような問題を対象とした場合には、依然として、第１の課題を解決することはできない。
【０００８】
また、特許文献２では、第２の課題、すなわち局所解に陥る確率が高いという課題を改善するために、制約を満たさない状態への遷移を認めることにより、より広い領域を探索するシステムが提案されている。しかしながら、このシステムでは、対象とする問題によっては、制約を満たさない領域に遷移しにくく、有効に機能しないので、そのような問題を対象とした場合には、依然として、第２の課題を解決することはできない。
【０００９】
たとえば、具体例として、運転コストを最小化するために、複数台の発電機の起動停止計画問題があげられる。通常、発電機は、起動時にコストがかかるため、１日に何度も起動停止を繰り返すことはなく、起動停止は最大１日１回といった制約条件がある。
いま、組み合わせ最適化途中の或る時点の解が、或る発電機の運転時間が１０：００〜１７：００であるとする。
【００１０】
制約条件を満たさない隣接状態は、たとえば、上記発電機を１０：００〜１２：００と、１３：００〜１７：００との２回に分割して運転する、という状態である。このような２回に分割した状態への遷移を仮に認めたとしても、起動にかかるコストを考えると、明らかに元の状態、すなわち１０：００〜１７：００に１回運転する状態の方が評価関数値は小さく、２回に分割した状態への遷移が発生することはない。
【００１１】
一方、特許文献３では、上記第１および第２の課題の両方を改善するために、対象を発電機の起動停止計画に限定し、特徴的な時刻の起動停止状態を固定して、この条件下で探索を行うというシステムが提案されている。しかしながら、このシステムでは、特徴的な時刻（たとえば、需要の極大値または極小値の発生時刻）の運転状態を固定することから、探索領域が限定されてしまうので、大域的な最適解を取得するのが困難である。
【００１２】
また、特許文献３に記載のシステムでは、特徴的な時刻の運転状態を変更する技術も提案しているが、特徴的な時刻の運転状態を変更した場合、結局、元々の全領域の探索に近づけるのみであり、局所解に陥る確率を低くすることはできるものの、処理時間が増大するので、２つの問題を同時に解決することは困難である。
さらに、特許文献３の記載例で対象としている発電機数は、高々１０台程度であり、最適化対象とする問題の規模が大きくないうえ、適用可能なのは、発電機の起動停止計画のみであり、実用的ではない。
【００１３】
【特許文献１】特開２００３−２０４６２４号公報
【特許文献２】特開平５−１４３５７２号公報
【特許文献３】特開２００１−２５８１５７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
従来の組み合わせ最適化システムは、特許文献１〜３に記載の手法によれば、対象とする問題によっては有効ではあるものの、依然として、実用規模の問題で膨大な処理時間を要するうえ、初期値に依存した局所最適解に陥る傾向が強いという課題があった。
【００１５】
この発明は、上記のような課題を解決するためになされたものであり、組み合わせ最適化問題を、局所解に陥る確率を小さくして、かつ高速に最適解を得ることのできる組み合わせ最適化システムを得ることを目的とする。
【課題を解決するための手段】
【００１６】
この発明による組み合わせ最適化システムは、組み合わせ最適化問題を解くための組み合わせ最適化システムであって、最適化条件、全離散変数のリストと最小変動幅・上下限値とで定義される離散変数リスト、および、最適化の過程で変動幅を調整する離散変数のリストとこれら離散変数のリストの各初期変動幅とで定義される変動幅調整変数リスト、を記憶する記憶手段と、探索の初期では変動幅調整変数リストの変動幅を初期変動幅で変動させながら最適化を行う第２近傍探索手段と、第２近傍探索手段による第２近傍探索の終了後に、全離散変数の変動幅を最小変動幅で変動させながら最適化を行う第１近傍探索手段と、第２近傍探索と第１近傍探索手段による第１近傍探索とを実行する制御プログラムとを備えたものである。
【発明の効果】
【００１７】
この発明によれば、まず、最適解の存在が有望な集中探索領域を高速に特定するために、一部または全離散変数の変動幅を調整（大きく設定）して、第２近傍探索（大域的な探索）を行い、続いて、離散変数の変動幅を小さく設定して、第１近傍探索（有望な集中探索領域の集中探索）を行い、第２近傍探索および第１近傍探索を組み合わせて実行することにより、局所解に陥る確率を小さくするとともに、より大域的な解を高速に到達することができる。
【発明を実施するための最良の形態】
【００１８】
実施の形態１．
以下、具体的な最適化対象として、必要に応じて複数の電源の運転計画に適用する場合を例にとって、この発明の実施の形態１について説明する。
図１はこの発明の実施の形態１に係る組み合わせ最適化システムの全体構成を示すブロック図である。
【００１９】
図１において、組み合わせ最適化システムは、コンピュータシステムからなり、中央処理装置４０と、メインメモリ４１と、ハードディスク４４と、入力装置４５と、出力装置４６と、バス４７とにより構成されている。メインメモリ４１、ハードディスク４４、入力装置４５および出力装置４６は、バス４７を介して、中央処理装置４０に接続されている。
【００２０】
メインメモリ４１は、各種処理を実行する制御プログラム４２と、最適化条件のデフォルト値４３と、最適化条件記憶手段２と、変動幅調整変数リスト記憶手段７と、離散変数リスト記憶手段１２と、最適解記憶手段１８と、最良解記憶手段１９と、タブーリスト記憶手段２１と、隣接状態記憶手段２３とを備えている。
【００２１】
制御プログラム４２は、最適化条件記録データ取得手段４と、最適化条件デフォルト値取得手段５と、変動幅調整変数リスト記録データ取得手段９と、変動幅調整変数リストデフォルト値取得手段１０と、離散変数リスト記録データ取得手段１４と、離散変数リストデフォルト値取得手段１５と、初期解生成手段１６と、評価関数値演算手段１７と、タブーリスト初期化手段２０と、第２近傍生成手段２２と、最良解・最適解更新手段２４と、タブーリスト更新手段２５と、第２近傍探索終了判定手段２６と、第１近傍探索初期解生成手段２７と、第１近傍生成手段２８と、第１近傍探索終了判定手段２９と、最適化結果記録・出力処理手段３０と、第２近傍探索手段３３と、第１近傍探索手段３４とを備えている。
【００２２】
ハードディスク４４は、最適化条件記録手段３と、変動幅調整変数リスト記録手段８と、離散変数リスト記録手段１３と、最適化結果記録手段３２とを備えている。この場合、最適化結果記録手段３２は、ハードディスク４４により構成されている。
入力装置４５は、キーボード（図示せず）などにより構成されており、最適化条件入力手段１と、変動幅調整変数リスト入力手段６と、離散変数リスト入力手段１１とを備えている。出力装置４６は、最適化結果出力手段３１を備えており、最適化結果出力手段３１は、ディスプレイまたはプリンタなど（図示せず）により構成されている。
【００２３】
最適化条件入力手段１は、最適化の目的、制約条件および設備データを含む最適化条件を入力する。
最適化条件記録手段３は、最適化条件入力手段１から入力された最適化条件の少なくとも一部をファイル・データベースとして記録する。
最適化条件記録データ取得手段４は、最適化条件記録手段３から最適化条件を読み出して最適化条件記憶手段２に記憶させる。
最適化条件デフォルト値取得手段５は、制御プログラム４２により設定されている最適化条件のデフォルト値４３を取得して最適化条件記憶手段２に記憶させる。
【００２４】
変動幅調整変数リスト入力手段６は、最適化の過程において変動幅を調整する離散変数のリストと離散変数の各々の初期変動幅とを、変動幅調整変数リストとして入力する。
変動幅調整変数リスト記録手段８は、変動幅調整変数リストの少なくとも一部をファイル・データベースとして記録する。
変動幅調整変数リスト記録データ取得手段９は、変動幅調整変数リスト記録手段８から変動幅調整変数リストを読み出して変動幅調整変数リスト記憶手段７に記憶させる。
変動幅調整変数リストデフォルト値取得手段１０は、制御プログラム４２により設定されている変動幅調整変数リストのデフォルト値４３を取得して変動幅調整変数リスト記憶手段７に記憶させる。
【００２５】
離散変数リスト入力手段１１は、全離散変数に関するリスト、上下限値および最小変動幅を、離散変数リストとして入力する。
離散変数リスト記録手段１３は、離散変数リストの少なくとも一部をファイル・データベースとして記録する。
離散変数リスト記録データ取得手段１４は、離散変数リスト記録手段１３から離散変数リストを読み出して離散変数リスト記憶手段１２に記憶させる。
離散変数リストデフォルト値取得手段１０は、制御プログラム４２により設定されている離散変数リストのデフォルト値４３を取得して離散変数リスト記憶手段１２に記憶させる。
【００２６】
評価関数値演算手段１７は、与えられた離散変数値に対する評価関数値を最適化条件記憶手段２内の最適化条件にしたがって演算する。
最適解記憶手段１８は、最適化の過程で過去最も評価関数値が優れた解である最適解の離散変数値および評価関数値を記憶する。
最良解記憶手段１９は、最適化の過程での一時的な解である最良解の離散変数値および評価関数値を記憶する。
【００２７】
初期解生成手段１６は、離散変数リスト記憶手段１２から全離散変数のリストを読み出して、最適化条件記憶手段２から読み出した最適化条件を満たすように全離散変数の初期値を生成し、評価関数値演算手段１７で演算された評価関数値を最適解記憶手段１８および最良解記憶手段１９に記憶させる。
【００２８】
タブーリスト記憶手段２１は、過去の最良解のリストからなるタブーリストを記憶する。
タブーリスト初期化手段２０は、タブーリストをクリアして、最適解記憶手段１８から読み出した最適解を追加したタブーリストをタブーリスト記憶手段２１に記憶させる。
隣接状態記憶手段２３は、全隣接状態（後述する）の離散変数値および評価関数値を記憶する。
【００２９】
第２近傍生成手段３３は、最適化条件記憶手段２から読み出した最適化条件と、変動幅調整変数リスト記憶手段７から読み出した、変動幅を調整する離散変数のリストおよび変動幅と、離散変数リスト記憶手段１２から読み出した、変動幅を調整しない離散変数のリスト、最小変動幅および全離散変数の上下限値と、最良解記憶手段１９から読み出した現在の最良解を構成する離散変数値および評価関数値とに基づいて、次の最良解候補である隣接状態を複数生成し、評価関数値演算手段１７により全隣接状態の評価関数値を演算し、全隣接状態の離散変数値および評価関数値を、メインメモリ４１上にあらかじめ領域が確保されている隣接状態記憶手段２３に記憶させる。
【００３０】
最適解・最良解更新手段２４は、隣接状態記憶手段２３から全隣接状態を読み出し、最適解記憶手段１８から現在の最適解を読み出し、最良解記憶手段１９から現在の最良解を読み出して、全隣接状態と現在の最良解とから次の最良解を選択し、次の最良解を構成する離散変数値および評価関数値を最良解記憶手段１９に記憶させ、次の最良解の評価関数値が現在の最適解の評価関数値よりも優れている場合には、次の最良解を構成する離散変数値および評価関数値を最適解記憶手段１８に記憶させる。
【００３１】
タブーリスト更新手段２５は、最良解記憶手段１９から最良解を読み出し、タブーリスト記憶手段２１からタブーリストを読み出し、タブーリストに保存されている最良解の数がタブーリストの長さに達している場合には、タブーリスト内の最も古い最良解を破棄して現在の最良解を追加した新しいタブーリストをタブーリスト記憶手段２１に記憶させる。
【００３２】
第２近傍探索終了判定手段２６は、最適化条件記憶手段２から読み出した最適化条件に基づいて、第２近傍探索の終了条件を満たすか否かを判定し、第２近傍探索の終了条件を満たすと判定された場合には第１近傍探索に移行し、第２近傍探索の終了条件を満たさない場合には、第２近傍生成手段２２の処理に復帰させる。
【００３３】
第２近傍探索手段３３は、第２近傍生成手段２２、最適解・最良解更新手段２４、タブーリスト更新手段２５および第２近傍探索終了判定手段２６による一連の処理を実行する。
第１近傍探索初期解生成手段２７は、最適解記憶手段１８から最適解を読み出して最良解記憶手段１９に記憶させる。
【００３４】
第１近傍生成手段２８は、最適化条件記憶手段２から読み出した最適化条件と、離散変数リスト記憶手段１２から読み出した全離散変数に関するリスト、最小変動幅および上下限値と、最良解記憶手段１９から読み出した現在の最良解を構成する離散変数値および評価関数値とに基づいて、次の最良解候補である隣接状態を複数生成し、評価関数値演算手段１７により全隣接状態の評価関数値を演算し、全隣接状態の離散変数値および評価関数値を隣接状態記憶手段２３に記憶させる。
【００３５】
第１近傍探索終了判定手段２９は、最適化条件記憶手段２から読み出した最適化条件に基づいて、第１近傍探索の終了条件を満たすか否かを判定し、第１近傍探索の終了条件を満たすと判定された場合には第１近傍探索を終了し、第１近傍探索の終了条件を満たさない場合には、第１近傍生成手段２８の処理に復帰させる。
第１近傍探索手段３４は、第１近傍生成手段２８、最適解・最良解更新手段２４、タブーリスト更新手段２５および第１近傍探索終了判定手段２９による一連の処理を実行する。
【００３６】
最適化結果出力手段３１は、ディスプレイまたはプリンタなどを含む出力装置４６により構成され、最適解を構成する離散変数値および評価関数値を出力する。
最適化結果記録手段３２は、ハードディスクなどにより構成され、最適解を構成する離散変数値および評価関数値をファイル・データベースとして記録する。
最適化結果記録・出力処理手段３０は、第１近傍探索の終了後に、最適化結果記録手段３２に最適化結果を記録するとともに、最適化結果出力手段３１により最適化結果を出力させる。
【００３７】
次に、図２のフローチャートを参照しながら、図１の組み合わせ最適化システムにより実行される処理手順について説明する。
図２において、まず、最適化条件を入力または読み出して記憶する（ステップＳ１）。
【００３８】
具体的には、入力装置４５内の最適化条件入力手段１（キーボードなど）をオペレータが操作することにより、最適化の目的（ＣＯ２排出量の最小化など）、制約条件（各時刻の電力需要＝電源出力＋買電＋蓄電池充放電など）、設備データ（電源の容量など）が最適化条件として入力される。
以下、中央処理装置４０は、メインメモリ４１内の制御プログラム４２の指令を受けて、入力された最適化条件を、メインメモリ４１上にあらかじめ領域が確保されている最適化条件記憶手段２に記憶させる。
【００３９】
ただし、最適化条件の少なくとも一部が、あらかじめハードディスク４４内の最適化条件記録手段３にファイル・データベースなどとして記録されていて、内容変更が不要な場合には、制御プログラム４２内の最適化条件記録データ取得手段４により、最適化条件記録手段３から最適化条件を読み出して最適化条件記憶手段２に記憶させる。
【００４０】
また、制御プログラム４２によりあらかじめデフォルト値４３が設定されていて、デフォルト値４３の内容変更が不要な最適化条件については、制御プログラム４２内の最適化条件デフォルト値取得手段５により、メインメモリ４１上のデフォルト値４３を取得して最適化条件記憶手段２に記憶させる。
【００４１】
次に、変動幅を調整する離散変数のリストを入力または読み出して記憶する（ステップＳ２）。
具体的には、入力装置４５内の変動幅調整変数リスト入力手段６（キーボードなど）をオペレータが操作することにより、最適化の過程において変動幅を調整する離散変数のリストと、各離散変数の初期変動幅とが入力される。
以下、中央処理装置４０は、メインメモリ４１内の制御プログラム４２の指令を受けて、入力された離散変数情報を、メインメモリ４１上にあらかじめ領域が確保されている変動幅調整変数リスト記憶手段７に記憶させる。
【００４２】
ただし、変動幅を調整する離散変数のリストおよび変動幅の少なくとも一部が、あらかじめハードディスク４４内の変動幅調整変数リスト記録手段８にファイル・データベースなどとして記録されていて、内容変更が不要な離散変数情報については、制御プログラム４２内の変動幅調整変数リスト記録データ取得手段９により、変動幅調整変数リスト記録手段８から離散変数情報を読み出して変動幅調整変数リスト記憶手段７に記憶させる。
【００４３】
また、制御プログラム４２によりデフォルト値４３が設定されていて、内容変更が不要な離散変数情報は、制御プログラム４２内の変動幅調整変数リストデフォルト値取得手段１０により、メインメモリ４１上のデフォルト値４３を取得して変動幅調整変数リスト記憶手段７に記憶させる。
【００４４】
変動幅を調整する離散変数の具体例としては、たとえば、図１の組み合わせ最適化システムを複数の電源の運転計画に適用する場合には、各電源のＯＮ／ＯＦＦ状態を変更する時刻があげられる。この場合、最適化問題が、翌日２４時間の運転計画を立案する問題であって、計画の時間刻みが「３０分間隔」であるとすると、各電源のＯＮ／ＯＦＦ状態を変更する時刻の最小変動幅は「３０分」であるのに対して、初期変動幅は、「６０分」または「９０分」などに設定される。
【００４５】
次に、全離散変数の入力または読み出しを行うために、変動幅を調整しない離散変数のリストを入力または読み出して記憶する（ステップＳ３）。
具体的には、入力装置４５内の離散変数リスト入力手段１１（キーボードなど）をオペレータが操作することにより、変動幅を調整しない離散変数を含む、全離散変数のリストと、全離散変数の上下限値と、全離散変数の最小変動幅とが入力される。
以下、中央処理装置４０は、メインメモリ４１内の制御プログラム４２の指令を受けて、入力された離散変数情報を、メインメモリ４１上にあらかじめ領域が確保されている離散変数リスト記憶手段１２に記憶させる。
【００４６】
ただし、全離散変数情報の少なくとも一部が、ハードディスク４４内の離散変数リスト記録手段１３にあらかじめファイル・データベースなどとして記録されていて、内容変更が不要な場合には、制御プログラム４２内の離散変数リスト記録データ取得手段１４により、離散変数情報を読み出して離散変数リスト記憶手段１２に記憶させる。
【００４７】
また、制御プログラム４２によりデフォルト値４３が設定されていて、内容変更が不要な離散変数については、制御プログラム４２内の離散変数デフォルト値取得手段１５により、メインメモリ４１上のデフォルト値４３を取得して離散変数リスト記憶手段１２に記憶させる。
【００４８】
次に、初期解を生成し、最適解（過去の探索で最も評価関数値が優れた解）、最良解（探索途中の一時的な解）として記憶する（ステップＳ４）。
具体的には、中央処理装置４０は、メインメモリ４１内の制御プログラム４２の指令を受けて、制御プログラム４２内の初期解生成手段１６により、最適化条件記憶手段２から最適化条件を読み出すとともに、離散変数リスト記憶手段１２から全離散変数のリストを読み出す。
【００４９】
また、中央処理装置４０は、最適化条件の一部である制約条件を満たすように全離散変数の初期値を生成し、評価関数値演算手段１７により与えられた離散変数値に対する評価関数値を最適化条件記憶手段２内の最適化条件にしたがって演算し、離散変数値および評価関数値をメインメモリ４１上にあらかじめ領域が確保されている最適解記憶手段１８に記憶させるとともに、離散変数値および評価関数値をメインメモリ４１上にあらかじめ領域が確保されている最良解記憶手段１９に記憶させる。
【００５０】
ここでは、便宜的に、過去の探索で最も評価関数値が優れたものを「最適解」と称し、探索途中の一時的な解を「最良解」と称する。
なお、全離散変数の初期値の与え方は任意であり、たとえば、ランダムに設定してもよいし、対象とする問題において経験的に知られている適当な方法で設定してもよい。
また、評価関数値演算手段１７の具体的な演算内容は、問題ごとにあらかじめ制御プログラム４２にアルゴリズムが記述されている。
【００５１】
たとえば、コージェネ電源の運転計画で、最適化条件として「ＣＯ２排出量最小化」を選択した場合、評価関数値Ｅは、コージェネ電源の燃料消費量Ｆｃと、コージェネ電源用燃料のＣＯ２排出係数Ｋｃと、商用系統からの買電量Ｑｂと、系統電力のＣＯ２排出係数Ｋｑ、不足熱量を供給するための燃料消費量Ｆｐと、不足熱供給用燃料のＣＯ２排出係数Ｋｐとを用いて、以下の式（１）のように演算される。
【００５２】
Ｅ＝Ｆｃ×Ｋｃ＋Ｑｂ×Ｋｑ＋Ｆｐ×Ｋｐ  ・・・（１）
【００５３】
ただし、式（１）において、コージェネ電源の燃料消費量Ｆｃ、商用系統からの買電量Ｑｂおよび不足熱量を供給するための燃料消費量Ｆｐは、離散変数値そのもの、または離散変数値から一意に決定できる値であり、各ＣＯ２排出係数Ｋｃ、Ｋｑ、Ｋｐは、最適化条件の項目である。
【００５４】
次に、最適化の第１段階である第２近傍探索として、制御プログラム４２内の第２近傍探索手段３３により、以下の処理が行われる。
すなわち、組み合わせ最適化システムの基本アルゴリズムがタブー探索を基本としている場合には、まず、制御プログラム４２内のタブーリスト初期化手段２０により、タブーリストを初期化（クリア）し、最適解記憶手段１８から最適解を読み出してタブーリストに追加し、更新後のタブーリストをメインメモリ４１上にあらかじめ領域が確保されているタブーリスト記憶手段２１に記憶させる（ステップＳ５）。
【００５５】
次に、中央処理装置４０は、現在の最良解からやや離れた領域の隣接状態の集合（第２近傍）を生成して評価関数値を演算するために、メインメモリ４１内の制御プログラム４２の指令を受けて、第２近傍生成手段２２により、最適化条件記憶手段２から最適化条件を読み出し、変動幅調整変数リスト記憶手段７から変動幅を調整する離散変数のリストおよび変動幅を読み出し、離散変数リスト記憶手段１２から変動幅を調整しない離散変数のリストおよび最小変動幅と全離散変数の上下限値とを読み出し、最良解記憶手段１９から現在の最良解を構成する離散変数値および評価関数値を読み出す。
【００５６】
以下、中央処理装置４０は、読み出した各情報に基づき、次の最良解候補である隣接状態を複数生成するとともに、評価関数値演算手段１７により全隣接状態の評価関数値を演算し、全隣接状態の離散変数値および評価関数値をメインメモリ４１上にあらかじめ領域が確保されている隣接状態記憶手段２３に記憶させる（ステップＳ６）。
【００５７】
ここで、具体的に述べると、隣接状態は、全離散変数のうちのいずれか１つの離散変数の値を、以下に示す離散変数ごとに異なる幅だけ増加または減少させることによって生成される。この処理を全離散変数に対して行うことにより、現在の最適解の近傍すなわち隣接状態の集合が生成される。
【００５８】
全離散変数のうち、変動幅を調整する離散変数については、調整変数のリストと合わせて取得した変動幅だけ値が変更される。その他の離散変数については、最小変動幅だけ変更される。ただし、変更した離散変数値が上限値よりも大きい場合には上限値に設定し、下限値よりも小さい場合には下限値に設定して、離散変数値を所定範囲内に限定する。
【００５９】
次に、中央処理装置４０は、最適解および最良解と第２近傍の各状態とを比較して、最適解および最良解を更新するために、メインメモリ４１内の制御プログラム４２の指令を受けて、最適解・最良解更新手段２４により、隣接状態記憶手段２３から全隣接状態を読み出し、最適解記憶手段１８から現在の最適解を読み出し、最良解記憶手段１９から現在の最良解を読み出す。
【００６０】
以下、中央処理装置４０は、全隣接状態と現在の最良解とから次の最良解を選択し、次の最良解を構成する離散変数値および評価関数値を最良解記憶手段１８に記憶させ、次の最良解の評価関数値が現在の最適解の評価関数値よりも優れている場合には、次の最良解を構成する離散変数値および評価関数値を、最適解記憶手段１８に更新して記憶させる（ステップＳ７）。
【００６１】
具体的には、次の最良解の選択方法は、適用する組み合わせ最適化システムの基本アルゴリズムにしたがう。たとえば、組み合わせ最適化システムが、局所探索を基本としている場合には、全隣接状態のうち最も評価関数値が優れているものを次の最良解とする。また、組み合わせ最適化システムが、タブー探索を基本としている場合には、全隣接状態のうち、タブーリスト含まれていないもので最も評価関数値が優れているものを次の最良解とする。
【００６２】
次に、組み合わせ最適化システムの基本アルゴリズムが、タブー探索を基本としている場合には、タブーリスト更新手段２５により、最良解記憶手段１９から最良解を読み出し、タブーリスト記憶手段２１からタブーリストを読み出して、タブーリストに保存されている最良解の数がタブーリストの長さに達していれば、タブーリスト内の最も古い最良解を破棄して現在の最良解を追加した新しいタブーリストを、タブーリスト記憶手段２１に更新して記憶させる（ステップＳ８）。
【００６３】
次に、中央処理装置４０は、メインメモリ４１内の制御プログラム４２の指令を受けて、第２近傍探索終了判定手段２６により、最適化条件記憶手段２から最適化条件を読み出し、第２近傍探索を終了する（第２近傍探索の終了条件を満たす）か否かを判定する（ステップＳ９）。
【００６４】
ステップＳ９において、第２近傍探索の終了条件を満たす（すなわち、ＹＥＳ）と判定された場合には、次の第１近傍探索（ステップＳ１０〜Ｓ１５）に移行し、終了条件を満たさない（すなわち、ＮＯ）と判定された場合には第２近傍生成手段２２の処理（ステップＳ６）に復帰する。
上記第２近傍生成手段２２〜第２近傍探索終了判定手段２６の処理（ステップＳ６〜Ｓ９）は、第２近傍探索の１つのループと見なすことができる。
【００６５】
なお、第２近傍探索を終了するか否かの判定は、たとえば、最適化条件で設定されている「第２近傍探索の最大ループ回数」、「第２近傍探索の収束判定回数」または「第２近傍探索の最大探索時間」を用いて行われる。すなわち、第２近傍探索のループ回数が「第２近傍探索の最大ループ回数」を越えた場合、「第２近傍探索の収束判定回数」が連続して最適解が改善されなかった場合、または、第２近傍探索の探索を開始後に「第２近傍探索の最大探索時間」が経過した場合に、第２近傍探索の終了条件が成立したものと判定される。
【００６６】
次に、最適化の第２段階である第１近傍探索として、制御プログラム４２内の第１近傍探索手段３４により、以下の処理が行われる。
まず、中央処理装置４０は、最良解を更新するために、メインメモリ４１内の制御プログラム４２の指令を受けて、第１近傍探索初期解生成手段２７により、最適解記憶手段１８から最適解を読み出して最良解記憶手段１９に記憶させる（ステップＳ１０）。
【００６７】
続いて、組み合わせ最適化システムの基本アルゴリズムが、タブー探索を基本としている場合には、タブーリスト初期化手段２０により、タブーリストを初期化（クリア）し、最適解記憶手段１８から最適解を読み出してタブーリストに追加し、更新後のタブーリストをタブーリスト記憶手段２１に記憶させる（ステップＳ１１）。
【００６８】
次に、中央処理装置４０は、現在の最良解の直近領域の隣接状態の集合（第１近傍）を生成して評価関数値を演算するために、メインメモリ４１内の制御プログラム４２の指令を受けて、第１近傍生成手段２８により、最適化条件記憶手段２から最適化条件を読み出し、離散変数リスト記憶手段１２から全離散変数に関するリスト、最小変動幅および上下限値を読み出し、最良解記憶手段１９から現在の最良解を構成する離散変数値および評価関数値を読み出す。
【００６９】
以下、中央処理装置４０は、読み出した各情報に基づき、次の最良解候補である隣接状態を複数生成し、評価関数値演算手段１７により全隣接状態の評価関数値を演算して、全隣接状態の離散変数値および評価関数値を隣接状態記憶手段２３に記憶させる（ステップＳ１２）。
【００７０】
具体的に述べると、隣接状態は、全離散変数のうちのいずれか１つの離散変数の値を最小変動幅だけ増加または減少させることにより生成される。この処理を全離散変数に対して行うことにより、現在の最適解の近傍すなわち隣接状態の集合が生成される。ただし、変更した離散変数値が上限値よりも大きい場合には上限値に設定し、下限値よりも小さい場合には下限値に設定して、離散変数を所定範囲内に限定する。
【００７１】
次に、中央処理装置４０は、最適解および最良解と第１近傍の各状態とを比較して、最適解および最良解を更新するために、メインメモリ４１内の制御プログラム４２の指令を受けて、最適解・最良解更新手段２４により、隣接状態記憶手段２３から全隣接状態を読み出し、最適解記憶手段１８から現在の最適解を読み出し、最良解記憶手段１９から現在の最良解を読み出す。
【００７２】
以下、中央処理装置４０は、全隣接状態と現在の最良解とから次の最良解を選択し、次の最良解を構成する離散変数値および評価関数値を最良解記憶手段１８に記憶させ、次の最良解の評価関数値が現在の最適解の評価関数値よりも優れている場合には、次の最良解を構成する離散変数値および評価関数値を最適解記憶手段１９に更新して記憶させる（ステップＳ１３）。
次の最良解の具体的な選択方法は、前述の第２近傍探索の場合と同様である。
次に、組み合わせ最適化システムの基本アルゴリズムが、タブー探索を基本としている場合には、タブーリスト更新手段２５により、最良解記憶手段１９から最良解を読み出し、タブーリスト記憶手段２１からタブーリストを読み出して、タブーリストに保存されている最良解の数がタブーリストの長さに達していれば、タブーリスト内の最も古い最良解を破棄して現在の最良解を追加した新しいタブーリストを、タブーリスト記憶手段２１に更新して記憶させる（ステップＳ１４）。
【００７３】
次に、中央処理装置４０は、メインメモリ４１内の制御プログラム４２の指令を受けて、第１近傍探索終了判定手段２９により、最適化条件記憶手段２から最適化条件を読み出し、第１近傍探索を終了する（第１近傍探索の終了条件を満たす）か否かを判定する（ステップＳ１５）。
【００７４】
ステップＳ１５において、第１近傍探索の終了条件を満たす（すなわち、ＹＥＳ）と判定された場合には第１近傍探索を終了し、終了条件を満たさない（すなわち、ＮＯ）と判定された場合には第１近傍生成手段２８の処理（ステップＳ１２）に復帰する。
上記第１近傍生成手段２７〜第１近傍探索終了判定手段２９の処理（ステップＳ１２〜Ｓ１５）は、第１近傍探索の１つのループと見なすことができる。
【００７５】
なお、第１近傍探索を終了するか否かの判定は、たとえば、最適化条件で設定されている「第１近傍探索の最大ループ回数」、「第１近傍探索の収束判定回数」または「第１近傍探索の最大探索時間」を用いて行われる。すなわち、第１近傍探索のループ回数が「第１近傍探索の最大ループ回数」を越えた場合、「第１近傍探索の収束判定回数」が連続して最適解が改善されなかった場合、または、第１近傍探索の探索を開始後に「第１近傍探索の最大探索時間」が経過した場合に、第１近傍探索を終了条件が成立したものと判定される。
【００７６】
最後に、中央処理装置４０は、第１近傍探索の終了後の処理として、メインメモリ４１内の制御プログラム４２の指令を受けて、最適化結果記録・出力処理手段３０により、ハードディスク４４内の最適化結果記録手段３２にファイル・データベースなどとして最適化結果（最適解を構成する離散変数値および評価関数値）を記録するとともに、出力装置４６内の最適化結果出力手段３１（ディスプレイ、プリンタなど）により、最適化結果を出力させて（ステップＳ１６）、図１の処理ルーチンを終了する。
【００７７】
図３はこの発明の実施の形態１に係る組み合わせ最適化システムのイメージを示す説明図である。
図３において、まず、一部の離散変数または全離散変数の変動幅を大きく設定して、現在の状態から離散変数の値を大きく変動させた隣接状態の集合を第２近傍（図３内の破線枠グレー部分）と定義し、第２近傍を隣接状態と見なして最適化する大域的な第２近傍探索を行う。
これにより、最適解が存在することが有望な集中探索する領域を高速に特定することができる。
【００７８】
第２近傍探索により隣接状態の評価関数値が収束したら、続いて、離散変数の変動幅を小さく設定して、現在の状態から離散変数を小さく変動させた隣接状態の集合を第１近傍（図３内の実線枠）と定義し、第１近傍を隣接状態と見なして最適化する第１近傍探索を行う。
これにより、図３内の下段右の特性図に示すように、短時間で有望な領域を集中探索することができる。
【００７９】
以上のように、この発明の実施の形態１に係る組み合わせ最適化問題を解くための組み合わせ最適化システムは、
メインメモリ４１上の制御プログラム４２と、
最適化の目的、制約条件および設備データを含む最適化条件を入力する最適化条件入力手段１と、
最適化条件を記憶する最適化条件記憶手段２と、
最適化条件の少なくとも一部をファイル・データベースとして記録する最適化条件記録手段３と、
最適化条件記録手段３から最適化条件を読み出して最適化条件記憶手段２に記憶させる最適化条件記録データ取得手段４と、
制御プログラム４２により設定されている最適化条件のデフォルト値４３を取得して最適化条件記憶手段２に記憶させる最適化条件デフォルト値取得手段５と、を備えている。
【００８０】
また、最適化の過程において変動幅を調整する離散変数のリストと離散変数の各々の初期変動幅とを変動幅調整変数リストとして入力する変動幅調整変数リスト入力手段６と、
変動幅調整変数リストを記憶する変動幅調整変数リスト記憶手段７と、
変動幅調整変数リストの少なくとも一部をファイル・データベースとして記録する変動幅調整変数リスト記録手段８と、
変動幅調整変数リスト記録手段８から変動幅調整変数リストを読み出して変動幅調整変数リスト記憶手段７に記憶させる変動幅調整変数リスト記録データ取得手段９と、
制御プログラム４２により設定されている変動幅調整変数リストのデフォルト値４３を取得して変動幅調整変数リスト記憶手段７に記憶させる変動幅調整変数リストデフォルト値取得手段１０と、を備えている。
【００８１】
また、全離散変数のリストと上下限値と最小変動幅を入力する離散変数リスト入力手段１１と、
離散変数リストを記憶する離散変数リスト記憶手段１２と、
離散変数リストの少なくとも一部をファイル・データベースとして記録する離散変数リスト記録手段１３と、
離散変数リスト記録手段１３から離散変数リストを読み出して離散変数リスト記憶手１２段に記憶させる離散変数リスト記録データ取得手段１４と、
制御プログラム４２により設定されている離散変数リストのデフォルト値４３を取得して離散変数リスト記憶手段１３に記憶させる離散変数リストデフォルト値取得手段１５と、を備えている。
【００８２】
また、与えられた離散変数値に対する評価関数値を最適化条件記憶手段２内の最適化条件にしたがって演算する評価関数値演算手段１７と、
最適化の過程で過去最も評価関数値が優れた解である最適解の離散変数値と評価関数値を記憶する最適解記憶手段１８と、
最適化の過程で一時的な解である最良解の離散変数値と評価関数値を記憶する最良解記憶手段１９と、
最適化条件記憶手段２から最適化条件を読み出し、離散変数リスト記憶手段１２から全離散変数のリストを読み出し、最適化条件を満たすよう全離散変数の初期値を生成し、評価関数値演算手段１７により評価関数値を演算し、求められた離散変数値および評価関数値を最適解記憶手段１８および最良解記憶手段１９に記憶させる初期解生成手段１６と、を備えている。
【００８３】
また、過去の最良解のリストであるタブーリストを記憶するタブーリスト記憶手段２１と、
タブーリストをクリアし、最適解記憶手段１８から最適解を読み出してタブーリストに追加し、タブーリストをタブーリスト記憶手段２１に記憶させるタブーリスト初期化手段２０と、
全隣接状態の離散変数値および評価関数値を記憶する隣接状態記憶手段２３と、
最適化条件記憶手段２から最適化条件を読み出し、変動幅調整変数リスト記憶手段７から変動幅を調整する離散変数のリストと変動幅を読み出し、離散変数リスト記憶手段１２から変動幅を調整しない離散変数のリストと最小変動幅と全離散変数の上下限値を読み出し、最良解記憶手段１９から現在の最良解を構成する離散変数値および評価関数値を読み出し、次の最良解候補である隣接状態を複数生成し、評価関数値演算手段１７により全隣接状態の評価関数値を演算し、全隣接状態の離散変数値および評価関数値をメインメモリ４１上にあらかじめ領域が確保されている隣接状態記憶手段２３に記憶させる、第２近傍生成手段２２と、を備えている。
【００８４】
また、隣接状態記憶手段２３から全隣接状態を読み出し、最適解記憶手段１８から現在の最適解を読み出し、最良解記憶手段１９から現在の最良解を読み出し、全隣接状態と現在の最良解とから次の最良解を選択し、次の最良解を構成する離散変数値および評価関数値を最良解記憶手段１９に記憶させ、次の最良解の評価関数値が現在の最適解の評価関数値よりも優れている場合には、次の最良解を構成する離散変数値および評価関数値を最適解記憶手段１８に記憶させる、最適解・最良解更新手段２４と、
最良解記憶手段１９から最良解を読み出し、タブーリスト記憶手段２１からタブーリストを読み出し、タブーリストに保存されている最良解の数がタブーリストの長さに達している場合には、タブーリスト内の最も古い最良解を破棄して現在の最良解を追加した新しいタブーリストをタブーリスト記憶手段２１に記憶させる、タブーリスト更新手段２５と、
最適化条件記憶手段２から最適化条件を読み出して、第２近傍探索を終了するか否かを判定し、終了と判定された場合には第１近傍探索に移行し、そうでない場合には第２近傍生成手段２２の処理に復帰させる第２近傍探索終了判定手段２６と、
第２近傍生成手段２２、最適解・最良解更新手段２４、タブーリスト更新手段２５および第２近傍探索終了判定手段２６の一連の処理を実行する第２近傍探索手段３３と、を備えている。
【００８５】
また、最適解記憶手段１８から最適解を読み出して最良解記憶手段１９に記憶させる第１近傍探索初期解生成手段２７と、
最適化条件記憶手段１８から最適化条件を読み出し、離散変数リスト記憶手段１２から全離散変数のリストと最小変動幅と上下限値を読み出し、最良解記憶手段１９から現在の最良解を構成する離散変数値および評価関数値を読み出し、次の最良解候補である隣接状態を複数生成し、評価関数値演算手段１７により全隣接状態の評価関数値を演算し、全隣接状態の離散変数値および評価関数値を隣接状態記憶手段２３に記憶させる第１近傍生成手段２８と、
最適化条件記憶手段２から最適化条件を読み出して、第１近傍探索を終了するか否かを判定し、終了と判定された場合には第１近傍探索を終了し、そうでない場合には第１近傍生成手段２８の処理に復帰させる第１近傍探索終了判定手段２９と、
第１近傍生成手段２８、最適解・最良解更新手段２４、タブーリスト更新手段２５および第１近傍探索終了判定手段の一連の処理を実行する第１近傍探索手段３４と、を備えている。
【００８６】
さらに、最適解を構成する離散変数値および評価関数値を出力するディスプレイ、プリンタなどの出力装置４６からなる最適化結果出力手段３１と、
ファイル・データベースなどとして最適解を構成する離散変数値および評価関数値を記録するハードディスク４４などからなる最適化結果記録手段３２と、
第１近傍探索の終了後に、最適化結果記録手段３２に最適化結果を記録するとともに、最適化結果出力手段３１により最適化結果を出力させる最適化結果記録・出力処理手段３０と、を備えている。
【００８７】
このように、第２近傍探索（第１段階の最適化）と第１近傍探索（第２段階の最適化）とを組み合わせることにより、局所解に陥る確率を小さくするとともに、より大域的な解を高速に到達することができる。
【００８８】
実施の形態２．
なお、上記実施の形態１では、２段階の最適化処理を実行したが、より優れた解を得るために３段階以上の任意段階の最適化処理を実行してもよい。
図４は任意段階の最適化を可能にしたこの発明の実施の形態２に係る組み合わせ最適化システムの全体構成を示すブロック図である。
【００８９】
図４において、前述（図１参照）と同様のものについては、前述と同一符号を付して、または符号の後に「Ａ」を付して詳述を省略する。
この場合、メインメモリ４１Ａは、前述の構成に加えて、第ｎ近傍を探索するかを表すカウンタ変数ｎを記憶するカウンタ記憶手段５２を備えている。
【００９０】
制御プログラム４２Ａは、前述の第２近傍生成手段２２に代えて、カウンタ初期化手段５１と、第Ｎ−ｎ近傍生成手段５３とを備えている。
また、制御プログラム４２Ａは、前述の第２近傍探索終了判定手段２６〜第１近傍探索終了判定手段２９に代えて、第Ｎ−ｎ近傍探索終了判定手段５４と、全探索終了判定手段５５と、第Ｎ−ｎ近傍探索条件更新手段５６とを備えている。
さらに、制御プログラム４２Ａは、前述の第２近傍探索手段３３および第１近傍探索手段３４に代えて、第Ｎ−ｎ近傍探索手段５７を備えている。
【００９１】
カウンタ初期化手段５１は、カウンタ記憶手段５２から読み出したカウンタ変数ｎを「０」に設定してカウンタ記憶手段５２に記憶させる。
第Ｎ−ｎ近傍生成手段５３は、最適化条件記憶手段２から読み出した最適化条件と、変動幅調整変数リスト記憶手段７から読み出した、変動幅を調整する離散変数のリストおよび変動幅Ｗ＿ｎと、離散変数リスト記憶手段１２から読み出した、変動幅を調整しない離散変数のリスト、最小変動幅および全離散変数の上下限値と、最良解記憶手段１９から読み出した現在の最良解を構成する離散変数値および評価関数値とに基づいて、次の最良解候補である隣接状態を複数生成し、評価関数値演算手段１７により全隣接状態の評価関数値を演算し、全隣接状態の離散変数値および評価関数値を、メインメモリ４１Ａ上にあらかじめ領域が確保されている隣接状態記憶手段２３に記憶させる。
【００９２】
第Ｎ−ｎ近傍探索終了判定手段５４は、最適化条件記憶手段２から読み出した最適化条件に基づいて、第Ｎ−ｎ近傍探索の終了条件を満たすか否かを判定し、第Ｎ−ｎ近傍探索の終了条件を満たすと判定された場合には第Ｎ−ｎ近傍探索を終了し、第Ｎ−ｎ近傍探索の終了条件を満たさない場合には、第Ｎ−ｎ近傍生成手段５３の処理に復帰させる。
第Ｎ−ｎ近傍探索手段５７は、第Ｎ−ｎ近傍生成手段５３、最適解・最良解更新手段２４、タブーリスト更新手段２５および第Ｎ−ｎ近傍探索終了判定手段５４による一連の処理を実行する。
【００９３】
第Ｎ−ｎ近傍探索条件更新手段５６は、カウンタ記憶手段５２から読み出したカウンタ変数ｎを「ｎ＋１」に設定（インクリメント）して、カウンタ記憶手段５２に記憶させ、変動幅調整変数リスト記憶手段７から読み出した変動幅Ｗ＿ｎを更新して変動幅調整変数リスト記憶手段７に記憶させ、最適解記憶手段１８から読み出した最適解を最良解記憶手段１９に記憶させる。
【００９４】
全探索終了判定手段５５は、最適化条件記憶手段２から読み出した最適化条件に基づいて、全探索の終了条件を満たすか否かを判定し、全探索の終了条件を満たすと判定された場合には全探索を終了し、全探索の終了条件を満たさない場合には第Ｎ−ｎ近傍探索条件更新手段の処理に移行する。
【００９５】
次に、図５のフローチャートを参照しながら、図４の組み合わせ最適化システムにより実行される処理手順について説明する。
図５において、ステップＳ１〜Ｓ４およびＳ１６については、前述（図２参照）と同様の処理なので、ここでは詳述を省略する。
【００９６】
この場合、ステップＳ４とステップＳ１６との間に、前述のステップＳ５〜Ｓ１５に代えて、ステップＳ２４〜Ｓ３３が挿入されている。
図５内のステップＳ２５〜Ｓ２９は、前述（図２）のステップＳ５〜Ｓ９（Ｓ１１〜Ｓ１５）に対応し、ステップＳ３３は、前述のステップＳ１０に対応する。
【００９７】
まず、前述と同様に、最適化条件を入力または読み出して記憶し（ステップＳ１）、変動幅を調整する変数を入力または読み出して記憶し（ステップＳ２）、全離散変数（変動幅を調整しない変数）を入力または読み出して記憶し（ステップＳ３）、初期解を生成する（ステップＳ４）。なお、コージェネ電源の運転計画における評価関数値は、前述の式（１）のように演算される。
【００９８】
次に、カウンタ初期化手段５１により、第ｎ近傍を探索するかを表すカウンタ変数ｎを「０」に設定し、この設定値（ｎ＝０）を、メインメモリ４１Ａ上にあらかじめ領域が確保されているカウンタ記憶手段５２に記憶させる（ステップＳ２４）。
ただし、以下の説明においては、カウンタ値の最大値を「Ｎ」とする。
【００９９】
次に、第Ｎ−ｎ近傍探索手段５７により、以下のように、最適化の第ｎ段階で第Ｎ−ｎ近傍探索の処理を行う。
まず、組み合わせ最適化システムの基本アルゴリズムが、タブー探索を基本としている場合には、タブーリスト初期化手段２０により、タブーリストをクリアし、最適解記憶手段１８から最適解を読み出してタブーリストに追加し、タブーリストをメインメモリ４１Ａ上にあらかじめ領域が確保されているタブーリスト記憶手段２１に記憶させる（ステップＳ２５）。
【０１００】
次に、中央処理装置４０は、現在の最良解から変動幅Ｗ＿ｎだけ離れた領域の隣接状態の集合（第Ｎ−ｎ近傍）を生成して評価関数値を演算するために、メインメモリ４１Ａ内の制御プログラム４２Ａの指令を受けて、第Ｎ−ｎ近傍生成手段５３により、最適化条件記憶手段２から最適化条件を読み出し、変動幅調整変数リスト記憶手段７から変動幅を調整する離散変数のリストと第Ｎ−ｎ近傍探索時の変動幅を読み出し、離散変数リスト記憶手段１２から変動幅を調整しない離散変数のリストと最小変動幅と全離散変数の上下限値を読み出し、最良解記憶手段１９から現在の最良解を構成する離散変数値および評価関数値を読み出す。
【０１０１】
以下、中央処理装置４０は、読み出した各情報に基づき、次の最良解候補である隣接状態を複数生成し、評価関数値演算手段１７により全隣接状態の評価関数値を演算し、全隣接状態の離散変数値および評価関数値を、メインメモリ４１Ａ上にあらかじめ領域が確保されている隣接状態記憶手段２３に記憶させる（ステップＳ２６）。
【０１０２】
具体的に述べると、隣接状態は、全離散変数のうちいずれか１つの離散変数の値を以下に示す離散変数ごとに異なる幅だけ増加または減少させることによって生成される。この処理を全離散変数に対して行うことにより、現在の最適解の近傍すなわち隣接状態の集合が生成される。
【０１０３】
全離散変数のうち、変動幅を調整する離散変数については、調整変数のリストと合わせて取得した変動幅Ｗ＿ｎだけ値を変更する。その他の離散変数については、最小変動幅だけ変更される。
ただし、変更した離散変数値が上限値よりも大きい場合には上限値に設定し、下限値よりも小さい場合には下限値に設定して、離散変数を所定範囲内に限定する。
【０１０４】
次に、中央処理装置４０は、最適解および最良解と第Ｎ−ｎ近傍の各状態とを比較して、最適解および最良解を更新するために、メインメモリ４１Ａ内の制御プログラム４２Ａの指令を受けて、最適解・最良解更新手段２４により、隣接状態記憶手段２３から全隣接状態を読み出し、最適解記憶手段１８から現在の最適解を読み出し、最良解記憶手段１９から現在の最良解を読み出す。
【０１０５】
以下、中央処理装置４０は、全隣接状態と現在の最良解とから次の最良解を選択し、次の最良解を構成する離散変数値および評価関数値を最良解記憶手段１８に記憶させ、次の最良解の評価関数値が現在の最適解の評価関数値よりも優れている場合には、次の最良解を構成する離散変数値および評価関数値を最適解記憶手段１８に更新して記憶させる（ステップＳ２７）。
【０１０６】
次の最良解の具体的な選択方法は、前述と同様に、適用する組み合わせ最適化システムの基本アルゴリズムにしたがう。たとえば、組み合わせ最適化システムが、局所探索を基本としている場合には、全隣接状態のうち最も評価関数値が優れているものを次の最良解とする。また、組み合わせ最適化システムが、タブー探索を基本としている場合には、全隣接状態のうちタブーリスト含まれていないもので最も評価関数値が優れているものを次の最良解とする。
【０１０７】
次に、組み合わせ最適化システムの基本アルゴリズムが、タブー探索を基本としている場合には、タブーリスト更新手段２５により、最良解記憶手段１９から最良解を読み出し、タブーリスト記憶手段２１からタブーリストを読み出して、タブーリストに保存されている最良解の数がタブーリストの長さに達している場合には、タブーリスト内の最も古い最良解を破棄して現在の最良解を追加した新しいタブーリストを、タブーリスト記憶手段２１に更新して記憶させる（ステップＳ２８）。
【０１０８】
次に、中央処理装置４０は、メインメモリ４１Ａ内の制御プログラム４２Ａの指令を受けて、第Ｎ−ｎ近傍探索終了判定手段５４により、最適化条件記憶手段２から最適化条件を読み出し、第Ｎ−ｎ近傍探索を終了する（終了条件を満たす）か否かを判定する（ステップＳ２９）。
【０１０９】
ステップＳ２９において、第Ｎ−ｎ近傍探索の終了条件を満たす（すなわち、ＹＥＳ）と判定された場合には全探索終了判定手段５５の処理（ステップＳ３０）に移行し、終了条件を満たさない（すなわち、ＮＯ）と判定された場合には、第Ｎ−ｎ近傍生成手段５３の処理（ステップＳ２６）に復帰させる。
上記第Ｎ−ｎ近傍生成手段５３〜第Ｎ−ｎ近傍探索終了判定手段５４の処理（ステップＳ２６〜Ｓ２９）は、第Ｎ−ｎ近傍探索の１つのループと見なすことができる。
【０１１０】
なお、ステップＳ２９における終了するか否かの判定は、たとえば、最適化条件で設定されている「第Ｎ−ｎ近傍探索の最大ループ回数」、「第Ｎ−ｎ近傍探索の収束判定回数」または「第Ｎ−ｎ近傍探索の最大探索時間」を用いて行われる。
すなわち、第Ｎ−ｎ近傍探索のループ回数が「第Ｎ−ｎ近傍探索の最大ループ回数」を越えた場合、「第Ｎ−ｎ近傍探索の収束判定回数」が連続して最適解が改善されなかった場合、または、第Ｎ−ｎ近傍探索の探索を開始後に「第Ｎ−ｎ近傍探索の最大探索時間」が経過した場合に、第Ｎ−ｎ近傍探索を終了条件が成立したものと判定される。
【０１１１】
次に、全探索終了判定手段５５は、最適化条件記憶手段２から最適化条件を読み出して、全探索を終了する（終了条件を満たす）か否かを判定する（ステップＳ３０）。
ステップＳ３０において、全探索の終了条件を満たす（すなわち、ＹＥＳ）と判定された場合には、最適化結果記録・出力処理手段３０の最終処理（ステップＳ１６）に移行し、終了条件を満たさない（すなわち、ＮＯ）と判定された場合には、第Ｎ−ｎ近傍探索条件更新手段５６の処理（ステップＳ３１）に移行する。
【０１１２】
次に、第Ｎ−ｎ近傍探索条件更新手段５６は、カウンタ記憶手段５２からカウンタ変数ｎを読み出して「ｎ＋１」に設定（インクリメント）し、カウンタ記憶手段５２に記憶させる（ステップＳ３１）。
また、変動幅調整変数リスト記憶手段７から変動幅Ｗ＿ｎを読み出して、更新後の変動幅Ｗ＿ｎを変動幅調整変数リスト記憶手段７に記憶させ（ステップＳ３２）、最適解記憶手段１８から最適解を読み出して最良解記憶手段１９に記憶させることにより、最良解を初期化する（ステップＳ３３）。
【０１１３】
以下、タブーリスト初期化手段２０の処理（ステップＳ２５）に復帰して、第Ｎ−ｎ近傍探索（カウンタ変数ｎは、ステップＳ３１で更新済）を繰り返し実行する。
【０１１４】
なお、変動幅Ｗ＿ｎの更新方法としては、順次に小さい値に設定するために、たとえば、前回の探索での変動幅Ｗ＿ｎを１／２にすることなどが考えられる。
たとえば、前述の電源運転計画においては、電源のＯＮ／ＯＦＦ状態を変更する時間幅Ｗ＿ｎは、「１２０分」→「６０分」→「３０分」などと順次に更新される。変動幅Ｗ＿ｎの値が最小変動幅に達した場合には、それ以上の更新は行われない。
【０１１５】
また、ステップＳ３０での全探索の終了判定は、たとえば、最適化条件で設定されている「全探索の最大探索時間」を用いて行われる。すなわち、最初の探索を開始後に「全探索の最大探索時間」が経過した場合、または、全離散変数の変動幅Ｗ＿ｎが最小変動幅での近傍探索が終了した場合に、全探索の終了条件が成立したものと判定される。
【０１１６】
最後に、全近傍探索の終了後に、中央処理装置４０は、メインメモリ４１Ａ内の制御プログラム４２Ａの指令を受けて、前述と同様に、最適化結果記録・出力処理手段３０により、最適解を構成する離散変数値および評価関数値を、ハードディスク４４からなる最適化結果記録手段３２にファイル・データベースなどとして記録するとともに、出力装置４６からなる最適化結果出力手段３１（ディスプレイ、プリンタなど）に、最適解を構成する離散変数値および評価関数値を出力させる。
【０１１７】
以上のように、この発明の実施の形態２に係る組み合わせ最適化システムは、前述と同様の構成として、最適化条件入力手段１と、最適化条件記憶手段２と、最適化条件記録手段３と、最適化条件記録データ取得手段４と、最適化条件デフォルト値取得手段５と、変動幅調整変数リスト入力手段６と、変動幅調整変数リスト記憶手段７と、変動幅調整変数リスト記録手段８と、変動幅調整変数リスト記録データ取得手段９と、変動幅調整変数リストデフォルト値取得手段１０と、離散変数リスト入力手段１１と、離散変数リスト記憶手段１２と、離散変数リスト記録手段１３と、離散変数リスト記録データ取得手段１４と、離散変数リストデフォルト値取得手段１５と、評価関数値演算手段１７と、最適解記憶手段１８と、最良解記憶手段１９と、初期解生成手段１６と、タブーリスト記憶手段２１と、タブーリスト初期化手段２０と、隣接状態記憶手段２３と、最適解・最良解更新手段２４と、タブーリスト更新手段２５と、最適化結果出力手段３１と、最適化結果記録手段３２と、最適化結果記録・出力処理手段３０とを備えている。
【０１１８】
また、前述とは異なる構成として、第ｎ近傍を探索するかを表すカウンタ変数ｎを記憶するカウンタ記憶手段５２と、カウンタ記憶手段５２から第ｎ近傍を探索するかを表すカウンタ変数ｎを「０」に設定し、カウンタ記憶手段に記憶させるカウンタ初期化手段５１と、第Ｎ−ｎ近傍生成手段５３と、第Ｎ−ｎ近傍探索手段５７と、第Ｎ−ｎ近傍探索条件更新手段５６と、全探索終了判定手段５５とを備えている。
【０１１９】
第Ｎ−ｎ近傍生成手段５３は、最適化条件記憶手段２から最適化条件を読み出し、変動幅調整変数リスト記憶手段７から、変動幅を調整する離散変数のリストおよび変動幅Ｗ＿ｎを読み出し、離散変数リスト記憶手段１２から、変動幅を調整しない離散変数のリスト、最小変動幅および全離散変数の上下限値を読み出し、最良解記憶手段１９から現在の最良解を構成する離散変数値および評価関数値を読み出して、次の最良解候補である隣接状態を複数生成し、評価関数値演算手段１７により全隣接状態の評価関数値を演算し、全隣接状態の離散変数値および評価関数値を隣接状態記憶手段２３に記憶させる。
【０１２０】
第Ｎ−ｎ近傍探索終了判定手段５４は、最適化条件記憶手段２から最適化条件を読み出して、第Ｎ−ｎ近傍探索を終了するか否かを判定し、終了と判定された場合には第Ｎ−ｎ近傍探索を終了し、そうでない場合には第Ｎ−ｎ近傍生成手段５３の処理に復帰させる。
第Ｎ−ｎ近傍探索手段５７は、第Ｎ−ｎ近傍生成手段５３、最適解・最良解更新手段２４、タブーリスト更新手段２５および第Ｎ−ｎ近傍探索終了判定手段５６の一連の処理を実行する。
【０１２１】
第Ｎ−ｎ近傍探索条件更新手段５６は、カウンタ記憶手段５２からカウンタ変数ｎを読み出し、「ｎ＋１」に設定（インクリメント）してカウンタ記憶手段５２に記憶させ、変動幅調整変数リスト記憶手段７から変動幅Ｗ＿ｎを読み出して更新後の変動幅Ｗ＿ｎを変動幅調整変数リスト記憶手段７に更新記憶させ、最適解記憶手段１８から最適解を読み出して最良解記憶手段１９に記憶させる。
全探索終了判定手段５５は、最適化条件記憶手段２から最適化条件を読み出して、全探索を終了するか否かを判定し、終了と判定された場合には全探索を終了し、そうでない場合には第Ｎ−ｎ近傍探索条件更新手段５６の処理に移行する。
【０１２２】
このように、一部または全離散変数の変動幅を大きいものから、段階的に小さく設定して大域的な探索を行い、最適解が存在することが有望な集中探索する領域を高速に特定し、最終的に、離散変数の変動幅を最小変動幅に設定して、有望な領域を集中探索する近傍探索を組み合わせることにより、前述と同様に、局所解に陥る確率を小さくするとともに、より大域的な解を高速に到達することができる。
また、前述の実施の形態１と比べて、長い時間を要するものの、最適解の信頼性をさらに向上させることができる。
【図面の簡単な説明】
【０１２３】
【図１】この発明の実施の形態１に係る組み合わせ最適化システムの全体構成を示すブロック図である。
【図２】この発明の実施の形態１に係る組み合わせ最適化システムの動作を示すフローチャートである。
【図３】この発明の実施の形態１に係る組み合わせ最適化システムのイメージを示す説明図である。
【図４】この発明の実施の形態２に係る組み合わせ最適化システムの全体構成を示すブロック図である。
【図５】この発明の実施の形態２に係る組み合わせ最適化システムの動作を示すフローチャートである。
【図６】従来の組み合わせ最適化システムのイメージを示す説明図である。
【符号の説明】
【０１２４】
１  最適化条件入力手段、２  最適化条件記憶手段、３  最適化条件記録手段、４  最適化条件記録データ取得手段、５  最適化条件デフォルト値取得手段、６  変動幅調整変数リスト入力手段、７  変動幅調整変数リスト記憶手段、８  変動幅調整変数リスト記録手段、９  変動幅調整変数リスト記録データ取得手段、１０  変動幅調整変数リストデフォルト値取得手段、１１  離散変数リスト入力手段、１２  離散変数リスト記憶手段、１３  離散変数リスト記録手段、１４  離散変数リスト記録データ取得手段、１５  離散変数リストデフォルト値取得手段、１６  初期解生成手段、１７  評価関数値演算手段、１８  最適解記憶手段、１９  最良解記憶手段、２０  タブーリスト初期化手段、２１  タブーリスト記憶手段、２２  第２近傍生成手段、２３  隣接状態記憶手段、２４  最良解・最適解更新手段、２５  タブーリスト更新手段、２６  第２近傍探索終了判定手段、２７  第１近傍探索初期解生成手段、２８  第１近傍生成手段、２９  第１近傍探索終了判定手段、３０  最適化結果記録・出力処理手段、３１  最適化結果出力手段、３２  最適化結果記録手段、３３  第２近傍探索手段、３４  第１近傍探索手段、４０  中央処理装置、４１、４１Ａ  メインメモリ、４２、４２Ａ  制御プログラム、４３  デフォルト値、４４  ハードディスク、４５  入力装置、４６  出力装置、４７  バス、５１  カウンタ初期化手段、５２  カウンタ記憶手段、５３  第Ｎ−ｎ近傍生成手段、５４  第Ｎ−ｎ近傍探索終了判定手段、５５  全探索終了判定手段、５６  第Ｎ−ｎ近傍探索条件更新手段、５７  第Ｎ−ｎ近傍探索手段。
【図１】
2009048353.tif 000003
【図２】
2009048353.tif 000004
【図３】
2009048353.tif 000005
【図４】
2009048353.tif 000006
【図５】
2009048353.tif 000007
【図６】
2009048353.tif 000008