最適化処理プログラム、方法及び装置
【課題】２以上の目的関数に対する最適化問題の解を数式で高速に得る。
【解決手段】本方法は、複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の多項式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより第１の式の射影因子である第２の式を生成させ、当該第２の式のデータをＣＡＤ処理部から取得する工程と、複数の目的関数の変数の値を複数生成して、複数の目的関数に代入することによって複数の目的関数の値セットを複数算出し、当該複数の値セットから複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出する工程と、第２の式の各々について、当該第２の式と仮最適点の各々との距離の評価値を算出する工程と、評価値が最も小さい第２の式を特定する工程とを含む。
【解決手段】本方法は、複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の多項式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより第１の式の射影因子である第２の式を生成させ、当該第２の式のデータをＣＡＤ処理部から取得する工程と、複数の目的関数の変数の値を複数生成して、複数の目的関数に代入することによって複数の目的関数の値セットを複数算出し、当該複数の値セットから複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出する工程と、第２の式の各々について、当該第２の式と仮最適点の各々との距離の評価値を算出する工程と、評価値が最も小さい第２の式を特定する工程とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、コンピュータを用いた演算処理に関する。
【背景技術】
【０００２】
２以上の目的関数の値を同時に最小化するといった問題は多目的最適化問題として知られている。このような多目的最適化問題は、例えばものづくりにおける設計段階で用いられており、ＳＲＡＭ（Static Random Access Memory）やハードディスクのスライダの設計に適用された従来例が存在している。
【０００３】
例えばＳＲＡＭの設計の例では、電力についての目的関数ｆ1（ｘ1，ｘ2）とサイズについての目的関数ｆ2（ｘ1，ｘ2）とを、変数ｘ1及びｘ2のそれぞれの値域において同時に最小化するという問題を解くことになる。
【０００４】
このような多目的最適化問題を、数値解析にて高速に解こうとする技術は多数存在している。
【０００５】
一方、多目的最適化問題を、数式処理により解く方法も存在している。この方法では、様々な設計パラメータの値について、計算機シミュレーションを実施し、各々のケースについて出力評価指標を算出する。そして、設計パラメータと出力評価指標との関係を近似するモデル式を計算し、このモデル式に基づいて数式処理による最適化を行う。この最適化のための処理として、得られた近似式及び制約条件からコストと性能との関係を表す数式を算出する場合がある。
【０００６】
なお、数式処理については、限定子除去法（ＱＥ：Quantifier Elimination）という技術が知られている。この技術は、例えば∃ｘ（ｘ2＋ｂｘ＋ｃ＝０）という数式を、限定子（∃及び∀）を除去した等価な式ｂ2−４ｃ≧０に変形する技術である。
【０００７】
具体的には、以下の文献を参照のこと。但し、ＱＥについての文献は多数存在しているので、以下の文献以外でも有用な文献は存在している。
【０００８】
数学セミナー 穴井宏和・横山和弘「計算実代数幾何入門」 日本評論社出版。第１回 ＣＡＤ（Cylindrical Algebraic Decomposition）とＱＥの概要（2007年11月号）、第２回 ＱＥによる最適化とその応用（2007年12月号）、第３回 ＣＡＤアルゴリズム(前半)（2008年1月号）、第４回 ＣＡＤアルゴリズム(後半)（2008年3月号）、第５回 ＣＡＤによるＱＥ（2008年4月号）。
【０００９】
雑誌FUJITSU2009-9月号，穴井 宏和, 金児 純司, 屋並 仁史, 岩根 秀直，「数式処理を用いた設計技術」（http://img.jp.fujitsu.com/downloads/jp/jmag/vol60-5/paper24.pdfから２００９年１０月取得可能）
【００１０】
Mats Jirstrand: Cylindrical Algebraic Decomposition - an Introduction，１９９５−１０−１８（http://www.control.isy.liu.se/research/reports/1995/1807.ps.Zから２００９年１０月取得可能）
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特表２００８−５０７０３８号公報
【特許文献２】特表２００８−５０２０３３号公報
【特許文献３】特開２０１０−１４６１６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上で述べた限定子除去法によって上で述べたような多目的最適化問題の解を数式で得ることができる。しかしながら、上で述べた多目的最適化問題を限定子除去法で全て解くのは計算効率が悪く、処理時間がかかる。
【００１３】
従って、本技術の目的は、一側面において、２以上の目的関数に対する最適化問題の解を数式で高速に得るための技術を提供することである。
【課題を解決するための手段】
【００１４】
本最適化処理方法は、（Ａ）複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の多項式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより第１の式の射影因子である第２の式を生成させ、当該第２の式のデータをＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、（Ｂ）複数の目的関数の変数の値を複数生成して、複数の目的関数に代入することによって複数の目的関数の値セットを複数算出し、当該複数の値セットから複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、（Ｃ）第１データ格納部に格納されている第２の式の各々について、当該第２の式と第２データ格納部に格納されている仮最適点の各々との距離の評価値を算出し、第３データ格納部に第２の式と対応付けて格納する評価ステップと、（Ｄ）第３データ格納部に格納されている評価値が最も小さい第２の式を特定するステップとを含む。
【発明の効果】
【００１５】
２以上の目的関数に対する最適化問題の解を数式で高速に得ることができるようになる。
【図面の簡単な説明】
【００１６】
【図１】図１は、最適化処理装置の機能ブロック図である。
【図２】図２は、射影処理を説明するための図である。
【図３】図３は、メインの処理フローを示す図である。
【図４】図４は、多目的最適化問題の一例を示す図である。
【図５】図５は、射影因子集合生成処理の処理フローを示す図である。
【図６】図６は、ＱＥ問題の一例を示す図である。
【図７】図７は、パレート生成処理の処理フローを示す図である。
【図８】図８は、目的関数平面の一例を示す図である。
【図９】図９は、仮最適点集合を説明するための図である。
【図１０】図１０は、パレート式選択処理の処理フローを示す図である。
【図１１】図１１は、区間分割処理の処理フローを示す図である。
【図１２】図１２は、パレートデータ格納部に格納されるデータの一例を示す図である。
【図１３】図１３は、出力データ格納部に格納されるデータの一例を示す図である。
【図１４】図１４は、出力データ格納部に格納されるデータの一例を示す図である。
【図１５】図１５は、出力データの一例を示す図である。
【図１６】図１６は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１７】
図１に、本実施の形態に係る最適化処理装置の構成を示す。最適化処理装置は、（Ａ）ユーザなどからデータを受け付ける入力部１と、（Ｂ）入力部１からのデータを格納する入力データ格納部３と、（Ｃ）入力データ格納部３に格納されているデータ等を用いて処理を行いＱＥツール１００に処理を行わせるＱＥ（Quantifier Elimination）ツール制御部５と、（Ｄ）入力データ格納部３に格納されているデータ等を用いて処理を行うパレート生成部９と、（Ｅ）ＱＥツール制御部５の処理結果等を格納する多項式格納部７と、（Ｆ）パレート生成部９の処理結果等を格納するパレートデータ格納部１１と、（Ｇ）入力データ格納部３と多項式格納部７とパレートデータ格納部１１とに格納されているデータを用いて処理を行うパレート式選択部１３と、（Ｈ）パレート式選択部１３の処理結果等を格納する出力データ格納部１５と、（Ｉ）出力データ格納部１５に格納されているデータを出力装置（印刷装置、表示装置等）に出力する出力部１７とを有する。
【００１８】
ＱＥツール１００は、背景技術の欄で述べたＱＥ処理を実施するモジュール又は装置であり、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部１１０と、式構築部１２０とを有する。ＣＡＤ処理部１１０は、射影部１１１と、ベース部１１２と、リフティング部１１３とを有する。なお、ＱＥツール１００は、最適化処理装置の一部である場合もあれば、他の装置又は他の装置に含まれる機能である場合もある。
【００１９】
典型的には、背景技術の欄で述べたように、ＱＥツール１００に対して限定子付きの式を投入して、その式と等価な、限定子なしの式をＱＥツール１００の出力として得る。すなわち、限定子付きの式を、射影部１１１で処理し、射影部１１１の出力をベース部１１２で処理し、ベース部１１２の出力をリフティング部１１３で処理し、リフティング部１１３の出力を式構築部１２０で処理することで、限定子なしの式を出力する。
【００２０】
本実施の形態では、射影部１１１の処理結果のみを使用するので、射影部１１１の処理内容についてのみ多少説明しておく。図２に示すように、ｘ1からｘrの変数を含む多項式集合Ｆrが与えられた場合に、この多項式集合Ｆrに対して変数ｘrを除去するように第１回目の射影処理を実施する。なお、Ｑは、括弧内に含まれる変数を含む実数係数の全多項式の集合を表している。第１回目の射影処理を実施すると、変数ｘ1からｘr-1を含む多項式集合Ｆr-1が得られる。さらに、この多項式集合Ｆr-1に対して変数ｘr-1を除去するように第２回目の射影処理を実施する。そうすると、変数ｘ1からｘr-2を含む多項式集合Ｆr-2が得られる。
【００２１】
このような処理を繰り返して、多項式集合Ｆ2に対して変数ｘ2を除去するように第ｒ−１回目の射影処理を実施する。そうすると、変数ｘ1のみを含む多項式集合Ｆ1が得られる。射影部１１１は、変数が１個になると、多項式集合Ｆr乃至Ｆ1の全てを出力する。
【００２２】
多項式集合Ｆrについて変数ｘrを除去する射影処理は、（Ａ）多項式集合Ｆrに含まれる各多項式ｆにおける変数ｘrの係数、（Ｂ）多項式集合Ｆrに含まれる各多項式ｆの判別式と、（Ｃ）多項式集合Ｆrに含まれる各多項式ｆ及びｇ（ｆ≠ｇ）の終結式とを生成する処理である。
【００２３】
例えば、以下に述べるような多項式集合Ｆ4に対して射影処理を実施する場合を考える。
Ｆ4＝｛ｆ1−４ｘ1，ｆ2−ｘ1＋ｘ1ｘ2−５，ｘ1−５，ｘ1−１，ｘ1−４，ｘ2−２，ｘ2−１｝
【００２４】
まず、多項式集合Ｆ4に対して変数ｘ2を除去する第１回目の射影処理を実施すると、以下に述べる多項式集合Ｆ3が得られる。
Ｆ3＝｛ｘ1−４，ｘ1，４ｘ1＋（−ｆ12），ｘ1，ｘ1＋（−ｆ2−５），ｘ1＋（ｆ2＋５）｝
【００２５】
さらに、多項式集合Ｆ3に対して変数ｘ1を除去する第２回目の射影処理を実施すると、以下に述べる多項式集合Ｆ2が得られる。
Ｆ2＝｛ｆ2＋１，ｆ2＋４、ｆ2＋５，ｆ2＋６，ｆ2＋９，４ｆ2＋（−ｆ12＋２０），４ｆ2＋（ｆ12＋２０）｝
【００２６】
最後に、多項式集合Ｆ2に対して変数ｆ2を除去する第３回目の射影処理を実施すると、以下に述べる多項式集合Ｆ1が得られる。
Ｆ1＝｛ｆ1−４，ｆ1−２，ｆ1，ｆ1＋２，ｆ1＋４，ｆ12＋４，ｆ12＋１６｝
【００２７】
次に、図１に示した最適化処理装置の動作について図３乃至図１５を用いて説明する。
【００２８】
まず、ユーザは、最適化処理装置の入力部１に対して今回解くべき多目的最適化問題を入力する。入力部１は、ユーザから、多目的最適化問題の入力を受け付け、当該多目的最適化問題のデータを入力データ格納部３に格納する（ステップＳ１）。なお、入力するデータは、このほかに、以下の処理で用いるパラメータも含まれる。具体的にはサンプリング数上限、判定基準の距離δを含む。場合によっては、変数値を生成するアルゴリズム種別を含む場合もある。
【００２９】
例えば、２つの目的関数ｆ1及びｆ2を、制約条件の下で同時に最小化するという多目的最適化問題を検討するものとする。具体的には、図４に示すような多目的最適化問題のデータが入力されたものとする。図４から分かるように、目的関数ｆ1は変数ｘ1を含み、目的関数ｆ2は変数ｘ1及びｘ2を含む。そして、変数ｘ1及びｘ2についての制約条件（ｘ1−１≧０，４−ｘ1≧０，ｘ2−１≧０，２−ｘ2≧０）も規定されている。
【００３０】
次に、ＱＥツール制御部５は、入力データ格納部３に格納されているデータを用いて、射影因子集合生成処理を実施する（ステップＳ３）。この射影因子集合生成処理については、図５及び図６を用いて説明する。
【００３１】
ＱＥツール制御部５は、入力データ格納部３に格納されている、多目的最適化問題のデータから等価なＱＥ問題を生成し、例えばメインメモリなどの記憶装置に格納する（図５：ステップＳ１１）。図４に示したような多目的最適化問題の場合、図６に示すような等価なＱＥ問題が生成される。図６から分かるように、目的関数の式及び制約条件の式を連結して、目的関数の変数ｘ1及びｘ2に存在を示す限定子∃を付加している。多目的最適化問題ではなく、このようなＱＥ問題を入力部１から入力するようにしても良い。
【００３２】
そして、ＱＥツール制御部５は、ＱＥ問題で出現する多項式（場合によっては単項式を含む。以下同じ。）を抽出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ１３）。ＱＥ問題の多項式を単純化した上で、抽出する。図６の場合には、上で述べた多項式集合Ｆ4に含まれる多項式が得られる。
【００３３】
そして、ＱＥツール制御部５は、ＱＥツール１００のＣＡＤ処理部１１０内における射影部１１１に対して、抽出された多項式（実際的には多項式集合）のデータを出力して射影処理を実施させることで、当該抽出された多項式に対する射影因子となる他の多項式（実際的には多項式集合）を生成させ、当該射影因子となる他の多項式のデータを、ＱＥツール１００から取得し、多項式格納部７に格納する（ステップＳ１５）。上で述べた例では、多項式集合Ｆ4乃至Ｆ1が射影因子となる他の多項式として取得され、多項式格納部７に格納される。そして元の処理に戻る。
【００３４】
このように射影部１１１以外のベース部１１２及びリフティング部１１３の処理及び式構築部１２０の処理を省略しているので、それだけ短い処理時間で処理結果を得ることができる。
【００３５】
図３の処理の説明に戻って、パレート生成部９は、入力データ格納部３に格納されているデータを用いてパレート生成処理を実施する（ステップＳ５）。このパレート生成処理については、図７乃至図９を用いて説明する。なお、ステップＳ３及びＳ５は独立した処理なので、処理順番を入れ替えたり、並列に実行することが可能である。
【００３６】
まず、パレート生成部９は、入力データ格納部３に格納されている最適化問題のデータに含まれる目的関数に含まれる各変数の値域に従って、変数の値を１組生成し、例えばメインメモリなどの記憶装置に格納する（ステップＳ２１）。そして、パレート生成部９は、生成された変数の値を各目的関数に代入することで、各目的関数の値を算出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ２３）。図４から明らかなように、制約条件には変数の値域ｘ1−１≧０，４−ｘ1≧０，ｘ2−１≧０，２−ｘ2≧０が規定されているので、この中で適切な変数値を生成し、目的関数に代入する。変数値の生成については、値域内においてランダムに生成するようにしても良いし、遺伝的アルゴリズム（Genetic Algorithm）、ＰＳＯ（Particle Swarm Optimization）、ＬＨＣ（Latin Hyper-cubic method）といったアルゴリズムを用いて生成するようにしても良い。このようなアルゴリズムについては、設計者がステップＳ１で指定するようにしても良い。
【００３７】
そして、パレート生成部９は、目的関数空間において、算出した目的関数値のセット（空間における点に相当）がパレート（すなわち非劣解）であるかを判断し、パレートであればパレート集合を更新する（ステップＳ２５）。
【００３８】
例えばパレート集合に含まれる点が登録されているパレートリストを、パレートデータ格納部１１に格納しておく。また、パレート集合に含まれない点が登録されている非パレートリストも、パレートデータ格納部１１に格納しておく。そして、今回算出した目的関数値のセットに対応する新規の点が、既にパレートリストに登録されている点のいずれかに支配されている場合には、非パレートリストに登録する。支配は、目的関数値のいずれもが優れていること、本例では小さい値であることを意味している。
【００３９】
一方、新規の点が、既にパレートリストに登録されている点のいずれにも支配されていない場合には、パレートリストに登録すると共に、逆にパレートリストに登録されている点の方が新規の点に支配されている場合には、この点をパレートリストから除去して、非最適点リストに登録する。
【００４０】
そして、パレート生成部９は、ステップＳ２３で生成された目的関数値のセット数がサンプリング数上限に達したか判断する（ステップＳ２７）。生成された目的関数値のセット数がサンプリング数上限に達していない場合には、ステップＳ２１に戻る。
【００４１】
図４の例では、例えば図８に示すような点群が、目的関数空間に配置される。すなわち、図８の例では、横軸は目的関数ｆ1を表し、縦軸は目的関数ｆ2を表している。ステップＳ２３を実行することによって、図８に示すような点の各々が生成される。このうち、左下の原点に近い非劣解となる点が、パレート集合に含まれることになる。
【００４２】
ステップＳ２７で、生成された目的関数値のセット数がサンプリング数上限に達した場合には、パレート生成部９は、入力データ格納部３に格納されている距離δ＝０が設定されているか又は全く距離δが設定されていないかを判断する（ステップＳ２９）。本実施の形態では、パレート集合の数が少ない場合などに備えるために、補助的にパレート集合に含まれる点から距離δ以内であれば、パレート集合に追加登録する。但し、距離δ＝０又は全く距離δが設定されていない場合には、パレート生成部９は、パレート集合の点を仮最適点集合に登録する（ステップＳ３０）。仮最適点集合のリストを、パレートデータ格納部１１に格納する。そして元の処理に戻る。
【００４３】
一方、距離δ≠０が設定されている場合には、パレート生成部９は、パレート集合に含まれない、すなわち非パレート集合に含まれる目的関数値セット毎に、最も近いパレートとの距離がδ以内か確認し、δ以内であれば仮最適点集合に登録する（ステップＳ３１）。仮最適点集合のリストを、パレートデータ格納部１１に用意して、初期的にパレートリストに登録されている点を登録しておく。そして、ステップＳ３１でδ以内と判定された点については追加登録する。その後元の処理に戻る。
【００４４】
ステップＳ３１を実施した場合には、例えば図９に示すように、点線で囲まれた部分が、仮最適点集合に含まれるようになる。
【００４５】
図３の処理の説明に戻って、パレート式選択部１３は、入力データ格納部３とパレートデータ格納部１１と多項式格納部７とに格納されているデータを用いて、パレート式選択処理を実施する（ステップＳ７）。パレート式選択処理については、図１０乃至図１５を用いて処理を説明する。
【００４６】
まず、パレート式選択部１３は、区間分割処理を実施する（図１０：ステップＳ４１）。図９に示したような目的関数平面（一般的には空間）における最適解は、必ずしも１つの曲線で表されるわけではない。区間毎に異なる曲線が最適解となる場合もあるので、適切に区間分割して、区間毎に最適解となる曲線を特定するものである。区間分割処理については、図１１及び図１２を用いて説明する。
【００４７】
パレート式選択部１３は、基準となる目的関数の値域を、入力データ格納部３に格納されている最適化問題のデータから特定する（図１１：ステップＳ６１）。例えば、目的関数ｆ1を基準となる目的関数とする。そして、制約条件に含まれる変数ｘ1及びｘ2の値域から、目的関数ｆ1の値域が算出できる。具体的には、この例ではｘ1の上限値及び下限値から、［２，４］であることが分かる。
【００４８】
次に、パレート式選択部１３は、多項式格納部７に格納されている、射影因子の多項式のうち基準となる目的関数についての多項式について実数根を算出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ６３）。上で述べた例で目的関数ｆ1について実数根を算出できる多項式は、多項式集合Ｆ1に含まれている。多項式集合Ｆ1に含まれている各多項式についての実数根は、−４，−２，０，２，４である。
【００４９】
そして、パレート式選択部１３は、ステップＳ６３で算出された実数根から、基準となる目的関数の値域に含まれる実数根を抽出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ６５）。本例では、値域が［２，４］であるので、実数根２及び４が抽出される。但し、抽出されない場合もある。
【００５０】
従って、値域に含まれる実数根が抽出されなかった場合（ステップＳ６７：Ｎｏルート）には、パレート式選択部１３は、基準となる目的関数の値域そのものを区間に設定し、当該区間のデータを出力データ格納部１５に格納する（ステップＳ６９）。そして、ステップＳ７３に移行する。
【００５１】
一方、値域に含まれる実数根が抽出された場合（ステップＳ６７：Ｙｅｓルート）には、パレート式選択部１３は、基準となる目的関数の値域を、抽出された実数根で分割して区間を生成し、区間のデータを出力データ格納部１５に格納する（ステップＳ７１）。本例では、値域が［２，４］で、抽出された実数根が２及び４であるから、結果的には区間は［２，４］となる。一般的には、値域が［ｌ，ｒ］であり、ステップＳ６５で実数根ｑ1，ｑ2，．．．ｑjが抽出されると、区間［ｌ，ｑ1］［ｑ1，ｑ2］［ｑ2，ｑ3］．．．［ｑj，ｒ］に分割される。
【００５２】
そして、パレート式選択部１３は、パレートデータ格納部１１に格納されている仮最適点集合に含まれている点を、出力データ格納部１５に格納されている区間のデータに従って分類し、分類結果をパレートデータ格納部１１に格納する（ステップＳ７３）。例えば、図１２に示すようなデータが、パレートデータ格納部１１に格納される。図１２の例では、目的関数ｆ1の値と、目的関数ｆ2の値と、区間の番号とが登録されている。例えば、区間の値が小さい順番に区間番号を付与して、該当する区間の番号が登録される。そして元の処理に戻る。
【００５３】
図１０の処理の説明に戻って、パレート式選択部１３は、出力データ格納部１５に登録されている区間のうち未処理の区間を１つ特定する（ステップＳ４３）。そして、パレート式選択部１３は、多項式格納部７において、未処理の多項式を１つ特定する（ステップＳ４５）。その後、パレート式選択部１３は、特定された多項式と、特定された区間内の仮最適点との距離の自乗和を評価値として算出し、多項式に対応付けて出力データ格納部１５に格納する（ステップＳ４７）。
【００５４】
例えば、区間ｋの仮最適点集合ＯＰkに属する仮最適点をＰj,kと表し、多項式格納部７に格納されている多項式をＧiとすると、評価値Ｄi,kは、以下のように表される。
【００５５】
【数１】
distance（Ａ，Ｂ）は、式Ｂと点Ａとの距離を表す。曲線と点の距離はよく知られているのでここでは述べない。この式（１）は一例であって、例えば距離の自乗和の平方根を採用しても良いし、該当する仮最適点の数で除することによって平均値を算出するようにしても良い。
【００５６】
そして、パレート式選択部１３は、多項式格納部７において、未処理の多項式が存在するか判断する（ステップＳ４９）。未処理の多項式が存在する場合にはステップＳ４５に戻る。このような処理を繰り返すと、例えば図１３に示すようなデータが得られる。図１３の例では、多項式に対応付けて評価値が格納されるようになっている。
【００５７】
一方、未処理の多項式が存在しない場合には、パレート式選択部１３は、評価値が最小となる多項式を特定し、ステップＳ４３で特定された区間のデータに対応付けて出力データ格納部１５に格納する（ステップＳ５１）。例えば図１３に示されるようなデータのうち評価値が最小となる行を特定し、当該行の多項式を特定する。
【００５８】
そして、パレート式選択部１３は、出力データ格納部１５に格納されている区間のうち未処理の区間が存在するか判断する（ステップＳ５３）。未処理の区間が存在していればステップＳ４３に戻る。一方、未処理の区間が存在していなければ、元の処理に戻る。
【００５９】
このような処理を実施すれば、例えば図１４に示すようなデータが出力データ格納部１５に格納される。図１４の例では、各区間について、最も評価値が小さくなる多項式のデータが登録されている。なお、上で述べた例では、区間［２，４］について、「４ｆ2＋ｆ12−２０」が特定される。
【００６０】
図３の処理の説明に戻って、出力部１７は、出力データ格納部１５に格納されている区間及び多項式のデータを用いて、多項式を表すグラフを出力装置（例えば表示装置又は印刷装置）に出力する（ステップＳ９）。例えば、「４ｆ2＋ｆ12−２０」の場合には４ｆ2＋ｆ12−２０＝０を表示装置に表示する。
【００６１】
例えば図１５のようなグラフが表示される。図１５の例では、横軸は目的関数ｆ1を表し、縦軸は目的関数ｆ2を表す。曲線ａが、上記の多項式を表している。なお、ハッチングが付された領域Ａは、実行可能領域としてＱＥツール１００によって全て数式処理で解いた場合に特定される領域である。具体的には、以下の式が数式処理で得られる。
［ｆ1−２≧０∨ｆ1＋２≦０］∧ｆ1＋４≧０∧ｆ1−４≦０∧ｆ2−５≦０∧４ｆ2＋ｆ12−２０≧０
【００６２】
このような数式処理であれば、上でも述べたような時間のかかる処理を行うことになるが、本実施の形態であれば、簡単な処理で短時間で同じ処理結果を得ることができるようになる。
【００６３】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、図１の機能ブロック図は一例であって必ずしも実際のプログラムモジュール構成と一致しない場合もある。また、処理フローについても処理結果が変わらない限りにおいて、処理順番を入れ替えたり、並列実行するようにしても良い。
【００６４】
さらに上で述べた例では、１台のコンピュータで実行する例を示しているが、複数台のコンピュータで処理を分担して実施するようにしても良い。
【００６５】
また、２つの目的関数についての処理を一例として説明したが、３以上の目的関数についても、同様に処理することができる。
【００６６】
なお、上で述べた最適化処理装置は、コンピュータ装置であって、図１６に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００６７】
以上述べた本実施の形態をまとめると、以下のようになる。
【００６８】
本実施の形態に係る最適化処理方法は、（Ａ）複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の多項式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより第１の式の射影因子である第２の式を生成させ、当該第２の式のデータをＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、（Ｂ）複数の目的関数の変数の値を複数生成して、複数の目的関数に代入することによって複数の目的関数の値セットを複数算出し、当該複数の値セットから複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、（Ｃ）第１データ格納部に格納されている第２の式の各々について、当該第２の式と第２データ格納部に格納されている仮最適点の各々との距離の評価値を算出し、第３データ格納部に第２の式と対応付けて格納する評価ステップと、（Ｄ）第３データ格納部に格納されている評価値が最も小さい第２の多項式を特定するステップとを含む。
【００６９】
通常ＣＡＤ処理部で行われる射影処理より後の処理よりも、上で述べた処理の方が簡単な処理で短時間で行うことができる。従って、２以上の目的関数に対する最適化問題の解を数式で高速に得ることができるようになる。
【００７０】
なお、本最適化処理方法は、複数の値セットのうち非劣解との距離が所定値以下の値セットを抽出し、仮最適点のデータとして第２データ格納部に格納するステップを更に含むようにしてもよい。例えば、非劣解の数が少ない場合などは有効である。
【００７１】
さらに、上で述べた評価ステップが、複数の目的関数のうち特定の目的関数の値域を、最適化問題から特定するステップと、第１データ格納部に格納されている第２の式のうち特定の目的関数のみを変数として含む第３の式を抽出するステップと、抽出された第３の式の実数根を算出し、当該第３の式の実数根から特定の目的関数の値域に含まれる実数根を抽出するステップと、特定の目的関数の値域を、抽出された実数根で区分することによって、特定の目的関数の区間を生成するステップと、上記仮最適点を、特定の目的関数の区間に従って分類するステップとを含むようにしてもよい。その際、距離の評価値の算出を、特定の目的関数の区間毎に、当該特定の目的関数の区間に対応する分類に係る仮最適点について実施するようにしてもよい。このようにすれば、区間毎に適切な式を特定することができるようになる。
【００７２】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【００７３】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７４】
（付記１）
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納する評価ステップと、
前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するステップと、
を、コンピュータに実行させるための最適化処理プログラム。
【００７５】
（付記２）
前記複数の値セットのうち前記非劣解との距離が所定値以下の値セットを抽出し、前記仮最適点のデータとして前記第２データ格納部に格納するステップ
を更に前記コンピュータに実行させるための付記１記載の最適化処理プログラム。
【００７６】
（付記３）
前記評価ステップが、
前記複数の目的関数のうち特定の目的関数の値域を、前記最適化問題から特定するステップと、
前記第１データ格納部に格納されている前記第２の式のうち前記特定の目的関数のみを変数として含む第３の式を抽出するステップと、
抽出された前記第３の式の実数根を算出し、当該第３の式の実数根から前記特定の目的関数の値域に含まれる実数根を抽出するステップと、
前記特定の目的関数の値域を、抽出された前記実数根で区分することによって、前記特定の目的関数の区間を生成するステップと、
前記仮最適点を、前記特定の目的関数の区間に従って分類するステップと、
を含み、
前記距離の評価値の算出を、前記特定の目的関数の区間毎に、当該特定の目的関数の区間に対応する分類に係る前記仮最適点について実施する
付記１又は２記載の最適化処理プログラム。
【００７７】
（付記４）
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納する評価ステップと、
前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するステップと、
を含み、コンピュータに実行される最適化処理方法。
【００７８】
（付記５）
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納する制御部と、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するパレート生成部と、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納し、前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するパレート式選択部と、
を有する最適化処理装置。
【符号の説明】
【００７９】
１ 入力部 ３ 入力データ格納部
５ ＱＥツール制御部 ７ 多項式格納部
９ パレート生成部 １１ パレートデータ格納部
１３ パレート式選択部 １５ 出力データ格納部
１７ 出力部
１００ ＱＥツール
１１０ ＣＡＤ処理部 １１１ 射影部
１１２ ベース部 １１３ リフティング部
１２０ 式構築部
【技術分野】
【０００１】
本技術は、コンピュータを用いた演算処理に関する。
【背景技術】
【０００２】
２以上の目的関数の値を同時に最小化するといった問題は多目的最適化問題として知られている。このような多目的最適化問題は、例えばものづくりにおける設計段階で用いられており、ＳＲＡＭ（Static Random Access Memory）やハードディスクのスライダの設計に適用された従来例が存在している。
【０００３】
例えばＳＲＡＭの設計の例では、電力についての目的関数ｆ1（ｘ1，ｘ2）とサイズについての目的関数ｆ2（ｘ1，ｘ2）とを、変数ｘ1及びｘ2のそれぞれの値域において同時に最小化するという問題を解くことになる。
【０００４】
このような多目的最適化問題を、数値解析にて高速に解こうとする技術は多数存在している。
【０００５】
一方、多目的最適化問題を、数式処理により解く方法も存在している。この方法では、様々な設計パラメータの値について、計算機シミュレーションを実施し、各々のケースについて出力評価指標を算出する。そして、設計パラメータと出力評価指標との関係を近似するモデル式を計算し、このモデル式に基づいて数式処理による最適化を行う。この最適化のための処理として、得られた近似式及び制約条件からコストと性能との関係を表す数式を算出する場合がある。
【０００６】
なお、数式処理については、限定子除去法（ＱＥ：Quantifier Elimination）という技術が知られている。この技術は、例えば∃ｘ（ｘ2＋ｂｘ＋ｃ＝０）という数式を、限定子（∃及び∀）を除去した等価な式ｂ2−４ｃ≧０に変形する技術である。
【０００７】
具体的には、以下の文献を参照のこと。但し、ＱＥについての文献は多数存在しているので、以下の文献以外でも有用な文献は存在している。
【０００８】
数学セミナー 穴井宏和・横山和弘「計算実代数幾何入門」 日本評論社出版。第１回 ＣＡＤ（Cylindrical Algebraic Decomposition）とＱＥの概要（2007年11月号）、第２回 ＱＥによる最適化とその応用（2007年12月号）、第３回 ＣＡＤアルゴリズム(前半)（2008年1月号）、第４回 ＣＡＤアルゴリズム(後半)（2008年3月号）、第５回 ＣＡＤによるＱＥ（2008年4月号）。
【０００９】
雑誌FUJITSU2009-9月号，穴井 宏和, 金児 純司, 屋並 仁史, 岩根 秀直，「数式処理を用いた設計技術」（http://img.jp.fujitsu.com/downloads/jp/jmag/vol60-5/paper24.pdfから２００９年１０月取得可能）
【００１０】
Mats Jirstrand: Cylindrical Algebraic Decomposition - an Introduction，１９９５−１０−１８（http://www.control.isy.liu.se/research/reports/1995/1807.ps.Zから２００９年１０月取得可能）
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特表２００８−５０７０３８号公報
【特許文献２】特表２００８−５０２０３３号公報
【特許文献３】特開２０１０−１４６１６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上で述べた限定子除去法によって上で述べたような多目的最適化問題の解を数式で得ることができる。しかしながら、上で述べた多目的最適化問題を限定子除去法で全て解くのは計算効率が悪く、処理時間がかかる。
【００１３】
従って、本技術の目的は、一側面において、２以上の目的関数に対する最適化問題の解を数式で高速に得るための技術を提供することである。
【課題を解決するための手段】
【００１４】
本最適化処理方法は、（Ａ）複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の多項式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより第１の式の射影因子である第２の式を生成させ、当該第２の式のデータをＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、（Ｂ）複数の目的関数の変数の値を複数生成して、複数の目的関数に代入することによって複数の目的関数の値セットを複数算出し、当該複数の値セットから複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、（Ｃ）第１データ格納部に格納されている第２の式の各々について、当該第２の式と第２データ格納部に格納されている仮最適点の各々との距離の評価値を算出し、第３データ格納部に第２の式と対応付けて格納する評価ステップと、（Ｄ）第３データ格納部に格納されている評価値が最も小さい第２の式を特定するステップとを含む。
【発明の効果】
【００１５】
２以上の目的関数に対する最適化問題の解を数式で高速に得ることができるようになる。
【図面の簡単な説明】
【００１６】
【図１】図１は、最適化処理装置の機能ブロック図である。
【図２】図２は、射影処理を説明するための図である。
【図３】図３は、メインの処理フローを示す図である。
【図４】図４は、多目的最適化問題の一例を示す図である。
【図５】図５は、射影因子集合生成処理の処理フローを示す図である。
【図６】図６は、ＱＥ問題の一例を示す図である。
【図７】図７は、パレート生成処理の処理フローを示す図である。
【図８】図８は、目的関数平面の一例を示す図である。
【図９】図９は、仮最適点集合を説明するための図である。
【図１０】図１０は、パレート式選択処理の処理フローを示す図である。
【図１１】図１１は、区間分割処理の処理フローを示す図である。
【図１２】図１２は、パレートデータ格納部に格納されるデータの一例を示す図である。
【図１３】図１３は、出力データ格納部に格納されるデータの一例を示す図である。
【図１４】図１４は、出力データ格納部に格納されるデータの一例を示す図である。
【図１５】図１５は、出力データの一例を示す図である。
【図１６】図１６は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１７】
図１に、本実施の形態に係る最適化処理装置の構成を示す。最適化処理装置は、（Ａ）ユーザなどからデータを受け付ける入力部１と、（Ｂ）入力部１からのデータを格納する入力データ格納部３と、（Ｃ）入力データ格納部３に格納されているデータ等を用いて処理を行いＱＥツール１００に処理を行わせるＱＥ（Quantifier Elimination）ツール制御部５と、（Ｄ）入力データ格納部３に格納されているデータ等を用いて処理を行うパレート生成部９と、（Ｅ）ＱＥツール制御部５の処理結果等を格納する多項式格納部７と、（Ｆ）パレート生成部９の処理結果等を格納するパレートデータ格納部１１と、（Ｇ）入力データ格納部３と多項式格納部７とパレートデータ格納部１１とに格納されているデータを用いて処理を行うパレート式選択部１３と、（Ｈ）パレート式選択部１３の処理結果等を格納する出力データ格納部１５と、（Ｉ）出力データ格納部１５に格納されているデータを出力装置（印刷装置、表示装置等）に出力する出力部１７とを有する。
【００１８】
ＱＥツール１００は、背景技術の欄で述べたＱＥ処理を実施するモジュール又は装置であり、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部１１０と、式構築部１２０とを有する。ＣＡＤ処理部１１０は、射影部１１１と、ベース部１１２と、リフティング部１１３とを有する。なお、ＱＥツール１００は、最適化処理装置の一部である場合もあれば、他の装置又は他の装置に含まれる機能である場合もある。
【００１９】
典型的には、背景技術の欄で述べたように、ＱＥツール１００に対して限定子付きの式を投入して、その式と等価な、限定子なしの式をＱＥツール１００の出力として得る。すなわち、限定子付きの式を、射影部１１１で処理し、射影部１１１の出力をベース部１１２で処理し、ベース部１１２の出力をリフティング部１１３で処理し、リフティング部１１３の出力を式構築部１２０で処理することで、限定子なしの式を出力する。
【００２０】
本実施の形態では、射影部１１１の処理結果のみを使用するので、射影部１１１の処理内容についてのみ多少説明しておく。図２に示すように、ｘ1からｘrの変数を含む多項式集合Ｆrが与えられた場合に、この多項式集合Ｆrに対して変数ｘrを除去するように第１回目の射影処理を実施する。なお、Ｑは、括弧内に含まれる変数を含む実数係数の全多項式の集合を表している。第１回目の射影処理を実施すると、変数ｘ1からｘr-1を含む多項式集合Ｆr-1が得られる。さらに、この多項式集合Ｆr-1に対して変数ｘr-1を除去するように第２回目の射影処理を実施する。そうすると、変数ｘ1からｘr-2を含む多項式集合Ｆr-2が得られる。
【００２１】
このような処理を繰り返して、多項式集合Ｆ2に対して変数ｘ2を除去するように第ｒ−１回目の射影処理を実施する。そうすると、変数ｘ1のみを含む多項式集合Ｆ1が得られる。射影部１１１は、変数が１個になると、多項式集合Ｆr乃至Ｆ1の全てを出力する。
【００２２】
多項式集合Ｆrについて変数ｘrを除去する射影処理は、（Ａ）多項式集合Ｆrに含まれる各多項式ｆにおける変数ｘrの係数、（Ｂ）多項式集合Ｆrに含まれる各多項式ｆの判別式と、（Ｃ）多項式集合Ｆrに含まれる各多項式ｆ及びｇ（ｆ≠ｇ）の終結式とを生成する処理である。
【００２３】
例えば、以下に述べるような多項式集合Ｆ4に対して射影処理を実施する場合を考える。
Ｆ4＝｛ｆ1−４ｘ1，ｆ2−ｘ1＋ｘ1ｘ2−５，ｘ1−５，ｘ1−１，ｘ1−４，ｘ2−２，ｘ2−１｝
【００２４】
まず、多項式集合Ｆ4に対して変数ｘ2を除去する第１回目の射影処理を実施すると、以下に述べる多項式集合Ｆ3が得られる。
Ｆ3＝｛ｘ1−４，ｘ1，４ｘ1＋（−ｆ12），ｘ1，ｘ1＋（−ｆ2−５），ｘ1＋（ｆ2＋５）｝
【００２５】
さらに、多項式集合Ｆ3に対して変数ｘ1を除去する第２回目の射影処理を実施すると、以下に述べる多項式集合Ｆ2が得られる。
Ｆ2＝｛ｆ2＋１，ｆ2＋４、ｆ2＋５，ｆ2＋６，ｆ2＋９，４ｆ2＋（−ｆ12＋２０），４ｆ2＋（ｆ12＋２０）｝
【００２６】
最後に、多項式集合Ｆ2に対して変数ｆ2を除去する第３回目の射影処理を実施すると、以下に述べる多項式集合Ｆ1が得られる。
Ｆ1＝｛ｆ1−４，ｆ1−２，ｆ1，ｆ1＋２，ｆ1＋４，ｆ12＋４，ｆ12＋１６｝
【００２７】
次に、図１に示した最適化処理装置の動作について図３乃至図１５を用いて説明する。
【００２８】
まず、ユーザは、最適化処理装置の入力部１に対して今回解くべき多目的最適化問題を入力する。入力部１は、ユーザから、多目的最適化問題の入力を受け付け、当該多目的最適化問題のデータを入力データ格納部３に格納する（ステップＳ１）。なお、入力するデータは、このほかに、以下の処理で用いるパラメータも含まれる。具体的にはサンプリング数上限、判定基準の距離δを含む。場合によっては、変数値を生成するアルゴリズム種別を含む場合もある。
【００２９】
例えば、２つの目的関数ｆ1及びｆ2を、制約条件の下で同時に最小化するという多目的最適化問題を検討するものとする。具体的には、図４に示すような多目的最適化問題のデータが入力されたものとする。図４から分かるように、目的関数ｆ1は変数ｘ1を含み、目的関数ｆ2は変数ｘ1及びｘ2を含む。そして、変数ｘ1及びｘ2についての制約条件（ｘ1−１≧０，４−ｘ1≧０，ｘ2−１≧０，２−ｘ2≧０）も規定されている。
【００３０】
次に、ＱＥツール制御部５は、入力データ格納部３に格納されているデータを用いて、射影因子集合生成処理を実施する（ステップＳ３）。この射影因子集合生成処理については、図５及び図６を用いて説明する。
【００３１】
ＱＥツール制御部５は、入力データ格納部３に格納されている、多目的最適化問題のデータから等価なＱＥ問題を生成し、例えばメインメモリなどの記憶装置に格納する（図５：ステップＳ１１）。図４に示したような多目的最適化問題の場合、図６に示すような等価なＱＥ問題が生成される。図６から分かるように、目的関数の式及び制約条件の式を連結して、目的関数の変数ｘ1及びｘ2に存在を示す限定子∃を付加している。多目的最適化問題ではなく、このようなＱＥ問題を入力部１から入力するようにしても良い。
【００３２】
そして、ＱＥツール制御部５は、ＱＥ問題で出現する多項式（場合によっては単項式を含む。以下同じ。）を抽出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ１３）。ＱＥ問題の多項式を単純化した上で、抽出する。図６の場合には、上で述べた多項式集合Ｆ4に含まれる多項式が得られる。
【００３３】
そして、ＱＥツール制御部５は、ＱＥツール１００のＣＡＤ処理部１１０内における射影部１１１に対して、抽出された多項式（実際的には多項式集合）のデータを出力して射影処理を実施させることで、当該抽出された多項式に対する射影因子となる他の多項式（実際的には多項式集合）を生成させ、当該射影因子となる他の多項式のデータを、ＱＥツール１００から取得し、多項式格納部７に格納する（ステップＳ１５）。上で述べた例では、多項式集合Ｆ4乃至Ｆ1が射影因子となる他の多項式として取得され、多項式格納部７に格納される。そして元の処理に戻る。
【００３４】
このように射影部１１１以外のベース部１１２及びリフティング部１１３の処理及び式構築部１２０の処理を省略しているので、それだけ短い処理時間で処理結果を得ることができる。
【００３５】
図３の処理の説明に戻って、パレート生成部９は、入力データ格納部３に格納されているデータを用いてパレート生成処理を実施する（ステップＳ５）。このパレート生成処理については、図７乃至図９を用いて説明する。なお、ステップＳ３及びＳ５は独立した処理なので、処理順番を入れ替えたり、並列に実行することが可能である。
【００３６】
まず、パレート生成部９は、入力データ格納部３に格納されている最適化問題のデータに含まれる目的関数に含まれる各変数の値域に従って、変数の値を１組生成し、例えばメインメモリなどの記憶装置に格納する（ステップＳ２１）。そして、パレート生成部９は、生成された変数の値を各目的関数に代入することで、各目的関数の値を算出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ２３）。図４から明らかなように、制約条件には変数の値域ｘ1−１≧０，４−ｘ1≧０，ｘ2−１≧０，２−ｘ2≧０が規定されているので、この中で適切な変数値を生成し、目的関数に代入する。変数値の生成については、値域内においてランダムに生成するようにしても良いし、遺伝的アルゴリズム（Genetic Algorithm）、ＰＳＯ（Particle Swarm Optimization）、ＬＨＣ（Latin Hyper-cubic method）といったアルゴリズムを用いて生成するようにしても良い。このようなアルゴリズムについては、設計者がステップＳ１で指定するようにしても良い。
【００３７】
そして、パレート生成部９は、目的関数空間において、算出した目的関数値のセット（空間における点に相当）がパレート（すなわち非劣解）であるかを判断し、パレートであればパレート集合を更新する（ステップＳ２５）。
【００３８】
例えばパレート集合に含まれる点が登録されているパレートリストを、パレートデータ格納部１１に格納しておく。また、パレート集合に含まれない点が登録されている非パレートリストも、パレートデータ格納部１１に格納しておく。そして、今回算出した目的関数値のセットに対応する新規の点が、既にパレートリストに登録されている点のいずれかに支配されている場合には、非パレートリストに登録する。支配は、目的関数値のいずれもが優れていること、本例では小さい値であることを意味している。
【００３９】
一方、新規の点が、既にパレートリストに登録されている点のいずれにも支配されていない場合には、パレートリストに登録すると共に、逆にパレートリストに登録されている点の方が新規の点に支配されている場合には、この点をパレートリストから除去して、非最適点リストに登録する。
【００４０】
そして、パレート生成部９は、ステップＳ２３で生成された目的関数値のセット数がサンプリング数上限に達したか判断する（ステップＳ２７）。生成された目的関数値のセット数がサンプリング数上限に達していない場合には、ステップＳ２１に戻る。
【００４１】
図４の例では、例えば図８に示すような点群が、目的関数空間に配置される。すなわち、図８の例では、横軸は目的関数ｆ1を表し、縦軸は目的関数ｆ2を表している。ステップＳ２３を実行することによって、図８に示すような点の各々が生成される。このうち、左下の原点に近い非劣解となる点が、パレート集合に含まれることになる。
【００４２】
ステップＳ２７で、生成された目的関数値のセット数がサンプリング数上限に達した場合には、パレート生成部９は、入力データ格納部３に格納されている距離δ＝０が設定されているか又は全く距離δが設定されていないかを判断する（ステップＳ２９）。本実施の形態では、パレート集合の数が少ない場合などに備えるために、補助的にパレート集合に含まれる点から距離δ以内であれば、パレート集合に追加登録する。但し、距離δ＝０又は全く距離δが設定されていない場合には、パレート生成部９は、パレート集合の点を仮最適点集合に登録する（ステップＳ３０）。仮最適点集合のリストを、パレートデータ格納部１１に格納する。そして元の処理に戻る。
【００４３】
一方、距離δ≠０が設定されている場合には、パレート生成部９は、パレート集合に含まれない、すなわち非パレート集合に含まれる目的関数値セット毎に、最も近いパレートとの距離がδ以内か確認し、δ以内であれば仮最適点集合に登録する（ステップＳ３１）。仮最適点集合のリストを、パレートデータ格納部１１に用意して、初期的にパレートリストに登録されている点を登録しておく。そして、ステップＳ３１でδ以内と判定された点については追加登録する。その後元の処理に戻る。
【００４４】
ステップＳ３１を実施した場合には、例えば図９に示すように、点線で囲まれた部分が、仮最適点集合に含まれるようになる。
【００４５】
図３の処理の説明に戻って、パレート式選択部１３は、入力データ格納部３とパレートデータ格納部１１と多項式格納部７とに格納されているデータを用いて、パレート式選択処理を実施する（ステップＳ７）。パレート式選択処理については、図１０乃至図１５を用いて処理を説明する。
【００４６】
まず、パレート式選択部１３は、区間分割処理を実施する（図１０：ステップＳ４１）。図９に示したような目的関数平面（一般的には空間）における最適解は、必ずしも１つの曲線で表されるわけではない。区間毎に異なる曲線が最適解となる場合もあるので、適切に区間分割して、区間毎に最適解となる曲線を特定するものである。区間分割処理については、図１１及び図１２を用いて説明する。
【００４７】
パレート式選択部１３は、基準となる目的関数の値域を、入力データ格納部３に格納されている最適化問題のデータから特定する（図１１：ステップＳ６１）。例えば、目的関数ｆ1を基準となる目的関数とする。そして、制約条件に含まれる変数ｘ1及びｘ2の値域から、目的関数ｆ1の値域が算出できる。具体的には、この例ではｘ1の上限値及び下限値から、［２，４］であることが分かる。
【００４８】
次に、パレート式選択部１３は、多項式格納部７に格納されている、射影因子の多項式のうち基準となる目的関数についての多項式について実数根を算出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ６３）。上で述べた例で目的関数ｆ1について実数根を算出できる多項式は、多項式集合Ｆ1に含まれている。多項式集合Ｆ1に含まれている各多項式についての実数根は、−４，−２，０，２，４である。
【００４９】
そして、パレート式選択部１３は、ステップＳ６３で算出された実数根から、基準となる目的関数の値域に含まれる実数根を抽出し、例えばメインメモリなどの記憶装置に格納する（ステップＳ６５）。本例では、値域が［２，４］であるので、実数根２及び４が抽出される。但し、抽出されない場合もある。
【００５０】
従って、値域に含まれる実数根が抽出されなかった場合（ステップＳ６７：Ｎｏルート）には、パレート式選択部１３は、基準となる目的関数の値域そのものを区間に設定し、当該区間のデータを出力データ格納部１５に格納する（ステップＳ６９）。そして、ステップＳ７３に移行する。
【００５１】
一方、値域に含まれる実数根が抽出された場合（ステップＳ６７：Ｙｅｓルート）には、パレート式選択部１３は、基準となる目的関数の値域を、抽出された実数根で分割して区間を生成し、区間のデータを出力データ格納部１５に格納する（ステップＳ７１）。本例では、値域が［２，４］で、抽出された実数根が２及び４であるから、結果的には区間は［２，４］となる。一般的には、値域が［ｌ，ｒ］であり、ステップＳ６５で実数根ｑ1，ｑ2，．．．ｑjが抽出されると、区間［ｌ，ｑ1］［ｑ1，ｑ2］［ｑ2，ｑ3］．．．［ｑj，ｒ］に分割される。
【００５２】
そして、パレート式選択部１３は、パレートデータ格納部１１に格納されている仮最適点集合に含まれている点を、出力データ格納部１５に格納されている区間のデータに従って分類し、分類結果をパレートデータ格納部１１に格納する（ステップＳ７３）。例えば、図１２に示すようなデータが、パレートデータ格納部１１に格納される。図１２の例では、目的関数ｆ1の値と、目的関数ｆ2の値と、区間の番号とが登録されている。例えば、区間の値が小さい順番に区間番号を付与して、該当する区間の番号が登録される。そして元の処理に戻る。
【００５３】
図１０の処理の説明に戻って、パレート式選択部１３は、出力データ格納部１５に登録されている区間のうち未処理の区間を１つ特定する（ステップＳ４３）。そして、パレート式選択部１３は、多項式格納部７において、未処理の多項式を１つ特定する（ステップＳ４５）。その後、パレート式選択部１３は、特定された多項式と、特定された区間内の仮最適点との距離の自乗和を評価値として算出し、多項式に対応付けて出力データ格納部１５に格納する（ステップＳ４７）。
【００５４】
例えば、区間ｋの仮最適点集合ＯＰkに属する仮最適点をＰj,kと表し、多項式格納部７に格納されている多項式をＧiとすると、評価値Ｄi,kは、以下のように表される。
【００５５】
【数１】
distance（Ａ，Ｂ）は、式Ｂと点Ａとの距離を表す。曲線と点の距離はよく知られているのでここでは述べない。この式（１）は一例であって、例えば距離の自乗和の平方根を採用しても良いし、該当する仮最適点の数で除することによって平均値を算出するようにしても良い。
【００５６】
そして、パレート式選択部１３は、多項式格納部７において、未処理の多項式が存在するか判断する（ステップＳ４９）。未処理の多項式が存在する場合にはステップＳ４５に戻る。このような処理を繰り返すと、例えば図１３に示すようなデータが得られる。図１３の例では、多項式に対応付けて評価値が格納されるようになっている。
【００５７】
一方、未処理の多項式が存在しない場合には、パレート式選択部１３は、評価値が最小となる多項式を特定し、ステップＳ４３で特定された区間のデータに対応付けて出力データ格納部１５に格納する（ステップＳ５１）。例えば図１３に示されるようなデータのうち評価値が最小となる行を特定し、当該行の多項式を特定する。
【００５８】
そして、パレート式選択部１３は、出力データ格納部１５に格納されている区間のうち未処理の区間が存在するか判断する（ステップＳ５３）。未処理の区間が存在していればステップＳ４３に戻る。一方、未処理の区間が存在していなければ、元の処理に戻る。
【００５９】
このような処理を実施すれば、例えば図１４に示すようなデータが出力データ格納部１５に格納される。図１４の例では、各区間について、最も評価値が小さくなる多項式のデータが登録されている。なお、上で述べた例では、区間［２，４］について、「４ｆ2＋ｆ12−２０」が特定される。
【００６０】
図３の処理の説明に戻って、出力部１７は、出力データ格納部１５に格納されている区間及び多項式のデータを用いて、多項式を表すグラフを出力装置（例えば表示装置又は印刷装置）に出力する（ステップＳ９）。例えば、「４ｆ2＋ｆ12−２０」の場合には４ｆ2＋ｆ12−２０＝０を表示装置に表示する。
【００６１】
例えば図１５のようなグラフが表示される。図１５の例では、横軸は目的関数ｆ1を表し、縦軸は目的関数ｆ2を表す。曲線ａが、上記の多項式を表している。なお、ハッチングが付された領域Ａは、実行可能領域としてＱＥツール１００によって全て数式処理で解いた場合に特定される領域である。具体的には、以下の式が数式処理で得られる。
［ｆ1−２≧０∨ｆ1＋２≦０］∧ｆ1＋４≧０∧ｆ1−４≦０∧ｆ2−５≦０∧４ｆ2＋ｆ12−２０≧０
【００６２】
このような数式処理であれば、上でも述べたような時間のかかる処理を行うことになるが、本実施の形態であれば、簡単な処理で短時間で同じ処理結果を得ることができるようになる。
【００６３】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、図１の機能ブロック図は一例であって必ずしも実際のプログラムモジュール構成と一致しない場合もある。また、処理フローについても処理結果が変わらない限りにおいて、処理順番を入れ替えたり、並列実行するようにしても良い。
【００６４】
さらに上で述べた例では、１台のコンピュータで実行する例を示しているが、複数台のコンピュータで処理を分担して実施するようにしても良い。
【００６５】
また、２つの目的関数についての処理を一例として説明したが、３以上の目的関数についても、同様に処理することができる。
【００６６】
なお、上で述べた最適化処理装置は、コンピュータ装置であって、図１６に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００６７】
以上述べた本実施の形態をまとめると、以下のようになる。
【００６８】
本実施の形態に係る最適化処理方法は、（Ａ）複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の多項式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより第１の式の射影因子である第２の式を生成させ、当該第２の式のデータをＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、（Ｂ）複数の目的関数の変数の値を複数生成して、複数の目的関数に代入することによって複数の目的関数の値セットを複数算出し、当該複数の値セットから複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、（Ｃ）第１データ格納部に格納されている第２の式の各々について、当該第２の式と第２データ格納部に格納されている仮最適点の各々との距離の評価値を算出し、第３データ格納部に第２の式と対応付けて格納する評価ステップと、（Ｄ）第３データ格納部に格納されている評価値が最も小さい第２の多項式を特定するステップとを含む。
【００６９】
通常ＣＡＤ処理部で行われる射影処理より後の処理よりも、上で述べた処理の方が簡単な処理で短時間で行うことができる。従って、２以上の目的関数に対する最適化問題の解を数式で高速に得ることができるようになる。
【００７０】
なお、本最適化処理方法は、複数の値セットのうち非劣解との距離が所定値以下の値セットを抽出し、仮最適点のデータとして第２データ格納部に格納するステップを更に含むようにしてもよい。例えば、非劣解の数が少ない場合などは有効である。
【００７１】
さらに、上で述べた評価ステップが、複数の目的関数のうち特定の目的関数の値域を、最適化問題から特定するステップと、第１データ格納部に格納されている第２の式のうち特定の目的関数のみを変数として含む第３の式を抽出するステップと、抽出された第３の式の実数根を算出し、当該第３の式の実数根から特定の目的関数の値域に含まれる実数根を抽出するステップと、特定の目的関数の値域を、抽出された実数根で区分することによって、特定の目的関数の区間を生成するステップと、上記仮最適点を、特定の目的関数の区間に従って分類するステップとを含むようにしてもよい。その際、距離の評価値の算出を、特定の目的関数の区間毎に、当該特定の目的関数の区間に対応する分類に係る仮最適点について実施するようにしてもよい。このようにすれば、区間毎に適切な式を特定することができるようになる。
【００７２】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【００７３】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７４】
（付記１）
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納する評価ステップと、
前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するステップと、
を、コンピュータに実行させるための最適化処理プログラム。
【００７５】
（付記２）
前記複数の値セットのうち前記非劣解との距離が所定値以下の値セットを抽出し、前記仮最適点のデータとして前記第２データ格納部に格納するステップ
を更に前記コンピュータに実行させるための付記１記載の最適化処理プログラム。
【００７６】
（付記３）
前記評価ステップが、
前記複数の目的関数のうち特定の目的関数の値域を、前記最適化問題から特定するステップと、
前記第１データ格納部に格納されている前記第２の式のうち前記特定の目的関数のみを変数として含む第３の式を抽出するステップと、
抽出された前記第３の式の実数根を算出し、当該第３の式の実数根から前記特定の目的関数の値域に含まれる実数根を抽出するステップと、
前記特定の目的関数の値域を、抽出された前記実数根で区分することによって、前記特定の目的関数の区間を生成するステップと、
前記仮最適点を、前記特定の目的関数の区間に従って分類するステップと、
を含み、
前記距離の評価値の算出を、前記特定の目的関数の区間毎に、当該特定の目的関数の区間に対応する分類に係る前記仮最適点について実施する
付記１又は２記載の最適化処理プログラム。
【００７７】
（付記４）
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納する評価ステップと、
前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するステップと、
を含み、コンピュータに実行される最適化処理方法。
【００７８】
（付記５）
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納する制御部と、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するパレート生成部と、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納し、前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するパレート式選択部と、
を有する最適化処理装置。
【符号の説明】
【００７９】
１ 入力部 ３ 入力データ格納部
５ ＱＥツール制御部 ７ 多項式格納部
９ パレート生成部 １１ パレートデータ格納部
１３ パレート式選択部 １５ 出力データ格納部
１７ 出力部
１００ ＱＥツール
１１０ ＣＡＤ処理部 １１１ 射影部
１１２ ベース部 １１３ リフティング部
１２０ 式構築部
【特許請求の範囲】
【請求項１】
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納する評価ステップと、
前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するステップと、
を、コンピュータに実行させるための最適化処理プログラム。
【請求項２】
前記複数の値セットのうち前記非劣解との距離が所定値以下の値セットを抽出し、前記仮最適点のデータとして前記第２データ格納部に格納するステップ
を更に前記コンピュータに実行させるための請求項１記載の最適化処理プログラム。
【請求項３】
前記評価ステップが、
前記複数の目的関数のうち特定の目的関数の値域を、前記最適化問題から特定するステップと、
前記第１データ格納部に格納されている前記第２の式のうち前記特定の目的関数のみを変数として含む第３の式を抽出するステップと、
抽出された前記第３の式の実数根を算出し、当該第３の式の実数根から前記特定の目的関数の値域に含まれる実数根を抽出するステップと、
前記特定の目的関数の値域を、抽出された前記実数根で区分することによって、前記特定の目的関数の区間を生成するステップと、
前記仮最適点を、前記特定の目的関数の区間に従って分類するステップと、
を含み、
前記距離の評価値の算出を、前記特定の目的関数の区間毎に、当該特定の目的関数の区間に対応する分類に係る前記仮最適点について実施する
請求項１又は２記載の最適化処理プログラム。
【請求項４】
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納する評価ステップと、
前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するステップと、
を含み、コンピュータに実行される最適化処理方法。
【請求項５】
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納する制御部と、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するパレート生成部と、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納し、前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するパレート式選択部と、
を有する最適化処理装置。
【請求項１】
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納する評価ステップと、
前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するステップと、
を、コンピュータに実行させるための最適化処理プログラム。
【請求項２】
前記複数の値セットのうち前記非劣解との距離が所定値以下の値セットを抽出し、前記仮最適点のデータとして前記第２データ格納部に格納するステップ
を更に前記コンピュータに実行させるための請求項１記載の最適化処理プログラム。
【請求項３】
前記評価ステップが、
前記複数の目的関数のうち特定の目的関数の値域を、前記最適化問題から特定するステップと、
前記第１データ格納部に格納されている前記第２の式のうち前記特定の目的関数のみを変数として含む第３の式を抽出するステップと、
抽出された前記第３の式の実数根を算出し、当該第３の式の実数根から前記特定の目的関数の値域に含まれる実数根を抽出するステップと、
前記特定の目的関数の値域を、抽出された前記実数根で区分することによって、前記特定の目的関数の区間を生成するステップと、
前記仮最適点を、前記特定の目的関数の区間に従って分類するステップと、
を含み、
前記距離の評価値の算出を、前記特定の目的関数の区間毎に、当該特定の目的関数の区間に対応する分類に係る前記仮最適点について実施する
請求項１又は２記載の最適化処理プログラム。
【請求項４】
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納するステップと、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するステップと、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納する評価ステップと、
前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するステップと、
を含み、コンピュータに実行される最適化処理方法。
【請求項５】
複数の目的関数を含む最適化問題と等価な限定子除去問題に出現する第１の式に対して、ＣＡＤ（Cylindrical Algebraic Decomposition）処理部に射影処理を実施させることにより前記第１の式の射影因子である第２の式を生成させ、当該第２の式のデータを前記ＣＡＤ処理部から取得して、第１データ格納部に格納する制御部と、
前記複数の目的関数の変数の値を複数生成して、前記複数の目的関数に代入することによって前記複数の目的関数の値セットを複数算出し、当該複数の値セットから前記複数の目的関数の値で張られる空間における非劣解である仮最適点を抽出し、第２データ格納部に格納するパレート生成部と、
前記第１データ格納部に格納されている前記第２の式の各々について、当該第２の式と前記第２データ格納部に格納されている前記仮最適点の各々との距離の評価値を算出し、第３データ格納部に前記第２の式と対応付けて格納し、前記第３データ格納部に格納されている前記評価値が最も小さい第２の式を特定するパレート式選択部と、
を有する最適化処理装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１２−６８８７０（Ｐ２０１２−６８８７０Ａ）
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【出願番号】特願２０１０−２１２６８６（Ｐ２０１０−２１２６８６）
【出願日】平成２２年９月２２日（２０１０．９．２２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【出願日】平成２２年９月２２日（２０１０．９．２２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]