JP2000215193A

JP2000215193A - 最適化問題を解決する処理装置および方法

Info

Publication number: JP2000215193A
Application number: JP11016500A
Authority: JP
Inventors: Ichiro Suzuki; 一郎鈴木; Shigeru Kameda; 繁亀田; Shoichi Masuda; 彰一桝田; Ikuo Fukuda; 育夫福田
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1999-01-26
Filing date: 1999-01-26
Publication date: 2000-08-04
Also published as: US6718289B1

Abstract

(57)【要約】【課題】汎用性に富み、取り扱いの容易な最適化問題
の処理装置および方法を提供することが課題である。【解決手段】処理対象の問題は形状２１に変換されて
探索エンジン１１に入力される。探索エンジン１１は、
探索終了条件１２、１４、変形要素の順序付けアルゴリ
ズム１３、コスト関数１５、および変形パターン１６を
用いて、形状２１を構成する変形要素２３を変化させて
形状２１を変形する。そして、コスト値２２が最小とな
るような形状２１を求め、それを解として出力する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、最適構造問題、最
適配置問題、最適経路問題等のような最適化問題を解決
する処理装置およびその方法に関する。

【０００２】

【従来の技術】近年、様々な産業分野において、最適化
問題を解決することが要求されている。最適化問題と
は、与えられたコスト関数が最大、最小、あるいは局所
最大、局所最小となるような状態を探索する問題であ
る。コスト関数の符号を変えることにより、最大あるい
は局所最大を求める問題は、最小あるいは局所最小を求
める問題に置き換えられる。以下では、主として、最小
あるいは局所最小を求める問題として最適化問題を説明
する。

【０００３】最適化問題には、例えば、最適構造問題、
最適配置問題、最適経路問題、最適ネットワーク問題、
最適フロー問題、最適コスト問題、および最適効率問題
が含まれる。

【０００４】例えば、最適構造問題は、建物、橋、航空
機の翼等の設計において構造を最適化する問題であり、
最適配置問題は、都市設計における施設の配置や化合物
における分子の配置等を最適化する問題であり、最適経
路問題は、車両のナビゲーションや電気回路等において
経路を最適化する問題である。

【０００５】また、例えば、最適ネットワーク問題は、
ガスや水道の配管、電気配線、通信ネットワーク等を最
適化する問題であり、最適フロー問題は、道路上の交通
フローやネットワーク上のデータフロー等を最適化する
問題であり、最適コスト問題および最適効率問題は、科
学、工学、経済、ビジネス等の分野でコストや効率を最
適化する問題である。

【０００６】このような最適化問題を解決するための従
来の代表的アルゴリズムとしては、最急降下法（Steepe
st Descent Method ）、遺伝アルゴリズム（Genetic Al
gorithm ）、焼きなまし法（Simulated Annealing Meth
od）等が挙げられる。

【０００７】

【発明が解決しようとする課題】しかしながら、従来の
最適化問題解決アルゴリズムには、次のような問題があ
る。

【０００８】最適化問題解決のための従来の情報処理装
置は、個々の具体的な問題のみを処理することができる
問題特化装置と種々の問題に対応できる汎用装置の２種
類に大別される。このうち、問題特化装置は、特定の問
題にしか適用することができず、それ以外の問題は解決
できない。

【０００９】これに対して、汎用装置は、上述のような
アルゴリズムを利用していると考えられるが、最急降下
法は、コスト関数が微分可能（滑らか）であることを前
提としており、微分不可能なコスト関数で記述された問
題には適用できない。また、遺伝アルゴリズムは、近傍
探索能力がなく、与えられた問題によっては必ずしも適
切な実装を行うことができない場合がある。また、焼き
なまし法は、温度パラメータの制御が難しく、汎用的な
パラメータ制御を実装することが困難である。

【００１０】本発明の課題は、より汎用性に富み、取り
扱いの容易な最適化問題の処理装置およびその方法を提
供することである。

【００１１】

【課題を解決するための手段】図１は、本発明の処理装
置の原理図である。図１の処理装置は、生成手段１、格
納手段２、変形手段３、および出力手段４を備える。

【００１２】生成手段１は、与えられた問題を表す形状
モデル５を生成し、格納手段２は、形状モデル５のデー
タを格納する。変形手段３は、形状モデル５を変形し、
出力手段４は、変形された形状モデルを視覚的に出力す
る。

【００１３】形状モデル５は、例えば、ｎ次元空間にお
ける点、線、面の集合として生成され、格納手段２は、
それらの点、線、面のデータを格納する。変形手段３
は、形状モデル５に含まれる点、線、面に基づいて形状
モデル５を変形し、出力手段４は、変形された形状モデ
ルをディスプレイ画面等に表示して、変形過程をユーザ
に提示する。

【００１４】このように、最適化問題を形状モデル化し
ておくと、それを多くの問題に対して汎用的に利用する
ことができる。また、形状変形のアルゴリズムはシンプ
ルで理解しやすいという特徴を持つ。最適解は、コスト
値が最良あるいは局所最良となるような形状モデル５か
ら自動的に求めることができ、ユーザが表示された形状
からコスト値を推測できる場合には、適当なタイミング
で解を取り出すこともできる。コスト値が最良あるいは
局所最良とは、コスト値が最小あるいは局所最小の場合
と、コスト値が最大あるいは局所最大の場合の両方を含
んでいる。

【００１５】例えば、図１の生成手段１、格納手段２、
変形手段３、および出力手段４は、後述する図２の探索
エンジン１１に対応し、図１の形状モデル５は、図２の
形状２１に対応する。

【００１６】

【発明の実施の形態】以下、図面を参照しながら、本発
明の実施の形態を詳細に説明する。本発明の処理装置
は、共通部品と個別部品から構成され、個別部品を交換
することにより、他の問題に対応した処理装置を容易に
構成することができる。また、個別部品のチューニング
も容易に行うことができ、与えられた問題に応じて処理
効率を上げることができる。

【００１７】図２は、本実施形態の処理装置の構成図で
ある。図２の処理装置は、探索エンジン１１、変形要素
毎の探索終了条件１２、変形要素毎の順序付けアルゴリ
ズム１３、探索終了条件１４、コスト関数１５、変形パ
ターン１６、およびクリエータ１７を備える。

【００１８】探索エンジン１１は、最適化問題をモデル
化した形状２１のデータと、解の探索過程における最小
コスト値２２を保持し、形状２１は、１つ以上の変形要
素２３のデータを含む。また、クリエータ１７は、生成
部３１、３２、３３、３４、３５、３６を含み、探索エ
ンジン１１からの要求に応じて必要な情報を生成する。

【００１９】探索エンジン１１は共通部品に対応し、変
形要素毎の探索終了条件１２、変形要素毎の順序付けア
ルゴリズム１３、探索終了条件１４、コスト関数１５、
変形パターン１６、形状２１、変形要素２３、および生
成部３１〜３６は、問題に応じて交換可能な個別部品に
対応する。

【００２０】探索エンジン１１は、まず、ユーザからの
指示に従い、開始形状生成部３６を利用して問題を形状
モデル化する。ここでは、最終的に求めたい対象が、向
き付けされた、あるいは向き付けされていない単体的複
体（simplicial complex）のような形状２１（例えば、
多角形や多面体）で表現される。

【００２１】例えば、多角形を表現する空間としては、
平面空間（２次元空間）や立体空間（３次元空間）が挙
げられる。また、形状２１を表現する空間としては、ｎ
次元の多様体（直線、平面、立体、球、トーラス等）だ
けでなく、グラフ（１次元複体）を含む単体的複体も利
用することができる。

【００２２】次に、探索エンジン１１は、コスト関数生
成部３４を利用して、与えられた問題の元のコスト関数
を形状２１に対するコスト関数１５として表現し、元の
制約条件を、形状２１の表現方法に関する制約条件とし
て表現する。そして、決められたアルゴリズムに従って
形状２１を変形させながら解を探索し、コスト関数１５
の値が最小となるような形状を解として出力する。

【００２３】ところで、このような処理装置を利用する
にあたって、ユーザは、以下の６つの項目を決定する必
要がある。（１）変形要素２３形状２１を変形させるに際して、形状２１のどのような
要素（単体）に基づく変形を考えるかを決定する。例え
ば、形状２１に含まれる点、線、面、立体等が、変形要
素２３として採用される。ここで、要素に基づく変形と
は、要素をパラメータとして持つ変形操作であり、例え
ば、次のようなものが考えられる。・形状２１を多角形
とし、その頂点を要素としたとき、要素の位置を変化さ
せて形状２１を変形させる。・形状２１を平面上の木と
し、その木のノード（点）を要素としたとき、その木の
適当な位置に新たなノードを付け加えて、元の要素と新
たなノードを接続することにより得られる木を、元の木
の変形形状とみなす。（２）変形パターン１６変形パターン生成部３５を利用して、変形要素２３に基
づく変形操作の中から具体的な操作を複数個選び、それ
らを順序付ける。例えば、形状２１がｘｙ平面上の多角
形として実現されており、変形要素２３がその多角形の
頂点である場合、適当な長さｈを用いて次のような変形
パターン１６を定義することが可能である。［変形１］頂点を長さｈだけｘ軸の正の方向に動かすこ
とによる形状変形［変形２］頂点を長さｈだけｙ軸の正の方向に動かすこ
とによる形状変形［変形３］頂点を長さｈだけｘ軸の負の方向に動かすこ
とによる形状変形［変形４］頂点を長さｈだけｙ軸の負の方向に動かすこ
とによる形状変形ここでは、頂点をキーとし、順序付けられた［変形１］
〜［変形４］の４つの変形操作が、１つの変形パターン
を表している。（３）探索開始形状開始形状生成部３６を利用して、形状２１の初期形状を
決定する。例えば、形状２１が平面上の５角形である場
合、平面上に５個の点を適当に配置し、それら点を適当
な順番で結んで得られる５角形を、開始形状とする。（４）探索終了条件１４探索終了条件生成部３３を利用して、探索終了条件１４
を決定する。探索終了条件１４としては、例えば、次の
ようなものが考えられる。・形状２１の最小コスト値２２があらかじめ決められた
値より小さくなったとき、探索を終了する。・形状のコスト関数１５の値の減衰率があらかじめ決め
られた値より小さくなったとき、探索を終了する。・探索回数があらかじめ決められた値を越えたら、探索
を終了する。・コスト関数１５の値の降下回数があらかじめ決められ
た値を越えたら、探索を終了する。・探索時間があらかじめ決められた値を越えたら、探索
を終了する。・ユーザからの終了指示があったとき、探索を終了す
る。（５）変形要素の順序付けアルゴリズム１３変形要素の順序付けアルゴリズム生成部３２を利用し
て、形状２１の変形要素２３を順序付けるアルゴリズム
を決定する。例えば、乱数発生器を利用して、変形要素
２３を順序付けるというアルゴリズムが考えられる。（６）変形要素毎の探索終了条件１２変形要素毎の探索終了条件生成部３１を利用して、変形
要素毎の探索終了条件１２を決定する。この探索終了条
件１２としては、例えば、次のようなものが考えられ
る。・変形パターン１６が有限個の変形操作からなる場合、
それらの変形操作をすべて行ってから、探索を終了す
る。・探索回数があらかじめ決められた値を越えるか、また
は変形パターン１６の変形操作が終了したら、探索を終
了する。・コスト関数１５の値の降下回数があらかじめ決められ
た値を越えるか、または変形パターン１６の変形操作が
終了したら、探索を終了する。・ユーザからの終了指示があるか、または変形パターン
１６の変形操作が終了したら、探索を終了する。

【００２４】図２の処理装置は、最急降下法のようにコ
スト関数の微分可能性を前提としておらず、遺伝アルゴ
リズムにはない近傍探索能力を持っている。また、焼き
なまし法のようなパラメータ制御を必要としない。した
がって、汎用性に富み、操作性の高い構成となってい
る。

【００２５】この処理装置は、任意のハードウェアまた
はソフトウェアにより実現することができるが、ここで
は、一例として、オブジェクト指向プログラミングを利
用した場合の構成について説明する。本実施形態におけ
るオブジェクトは、共通オブジェクト、インタフェース
共通オブジェクト、コスト関数オブジェクト、およびオ
ブジェクトファクトリに分類される。オブジェクトは、
通常、データとそのデータに対する手続き（メソッド）
を所持しており、他のオブジェクトとのリンク関係を所
持することもできる。

【００２６】共通オブジェクトは、個別の問題から独立
しており、すべての問題に共通して利用されるオブジェ
クトである。共通オブジェクトは、共通のメソッドイン
タフェースのみを意識して設計され、メソッドの動作ロ
ジックは特に意識していない。共通オブジェクトとして
は、次のようなものが用いられる。（１）探索エンジンオブジェクト（２）起動ボタンオブジェクト（３）停止ボタンオブジェクトインタフェース共通オブジェクトは、個別の問題から独
立した共通のメソッドインタフェースを持つが、メソッ
ドの動作ロジックは、個別の問題に依存している。共通
オブジェクトとしては、次のようなものが用いられる。（４）コスト関数オブジェクト（５）開始形状生成オブジェクト（６）形状オブジェクト（７）変形要素オブジェクト（８）変形アルゴリズム管理オブジェクト（９）変形アルゴリズム群オブジェクト（１０）変形アルゴリズムオブジェクト（１１）形状表示オブジェクトオブジェクトファクトリは、インタフェース共通オブジ
ェクトを生成するためのオブジェクトである。オブジェ
クトファクトリのオブジェクト群をカストマイズするこ
とによって、処理装置を個別の問題に適合させることが
できる。オブジェクトファクトリとしては、次のような
ものが用いられる。（１２）コスト関数オブジェクト生成オブジェクト（１３）開始形状生成オブジェクト生成オブジェクト（１４）形状オブジェクト生成オブジェクト（１５）変形要素オブジェクト生成オブジェクト（１６）変形アルゴリズム管理オブジェクト生成オブジ
ェクト（１７）変形アルゴリズム群オブジェクト（１８）変形アルゴリズムオブジェクト（１９）形状表示オブジェクト生成オブジェクト次に、図３から図２４までを参照しながら、各オブジェ
クトが所持するデータとメソッドについて説明する。図
３は、探索エンジンオブジェクトの構成を示している。
図３の探索エンジンオブジェクト４１は、図２の探索エ
ンジン１１に対応し、形状オブジェクト４２、コスト値
オブジェクト４３、および探索メソッド４４を所持す
る。

【００２７】形状オブジェクト４２とコスト値オブジェ
クト４３は、それぞれ、図２の形状２１と最小コスト値
２２に対応し、探索エンジンオブジェクト４１が使用す
るデータを所持する。変形要素オブジェクト４５は、図
２の変形要素２３に対応し、形状オブジェクト４２にリ
ンクされる。また、探索メソッド４４は、探索エンジン
１１に対応する処理を起動する。

【００２８】図４は、起動ボタンオブジェクトの構成を
示している。図４の起動ボタンオブジェクト５１は、タ
イミングフラグオブジェクト５２と起動メソッド５３を
所持し、ディスプレイ画面に表示された探索エンジン起
動ボタンの操作を検出する。タイミングフラグオブジェ
クト５２は、形状オブジェクト４２のデータを表示する
タイミングを表すフラグを所持しており、起動メソッド
５３は、ボタン押下のイベントに基づいて、探索エンジ
ンオブジェクト４１を起動する。

【００２９】図５は、停止ボタンオブジェクトの構成を
示している。図５の停止ボタンオブジェクト６１は、終
了フラグオブジェクト６２と停止メソッド６３を所持
し、ディスプレイ画面に表示された探索エンジン停止ボ
タンの操作を検出する。終了フラグオブジェクト６２
は、探索エンジンオブジェクト４１による探索処理の終
了タイミングを表すフラグを所持しており、停止メソッ
ド６３は、ボタン押下のイベントに基づいて、探索エン
ジンオブジェクト４１を停止する。

【００３０】図６は、コスト関数オブジェクトの構成を
示している。図６のコスト関数オブジェクト７１は、図
２のコスト関数１５に対応し、与えられた形状のコスト
値を返すコスト値メソッド７２を所持する。また、図７
は、開始形状生成オブジェクトの構成を示している。図
７の開始形状生成オブジェクト８１は、開始形状メソッ
ド８２を所持し、ディスプレイ画面に表示された開始形
状生成ボタンの操作を検出する。開始形状メソッド８２
は、ボタン押下のイベントに基づいて開始形状を生成す
る。

【００３１】図８は、変形アルゴリズム管理オブジェク
トの構成を示している。図８の変形アルゴリズム管理オ
ブジェクト９１は、図２の変形要素の順序付けアルゴリ
ズム１３に対応し、初期化メソッド９２、変形要素メソ
ッド９３、および通知メソッド９４を所持する。初期化
メソッド９２は、変形アルゴリズム管理オブジェクト９
１を初期化し、変形要素メソッド９３は、次に処理すべ
き変形要素オブジェクト４５を求める。また、通知メソ
ッド９４は、次の変形要素オブジェクト４５が存在する
か否かを通知する。

【００３２】図９は、変形アルゴリズム群オブジェクト
の構成を示している。図９の変形アルゴリズム群オブジ
ェクト１０１は、図２の変形パターン１６に対応し、更
新フラグオブジェクト１０２、初期化メソッド１０３、
変形アルゴリズムメソッド１０４、および通知メソッド
１０５を所持する。初期化メソッド１０３は、変形アル
ゴリズム群オブジェクト１０１を変形要素オブジェクト
４５毎に初期化し、変形アルゴリズムメソッド１０４
は、次に適用すべき変形アルゴリズムオブジェクトを求
める。また、通知メソッド１０５は、次の変形アルゴリ
ズムオブジェクトが存在するか否かを通知する。

【００３３】図１０は、変形アルゴリズムオブジェクト
の構成を示している。図１０の変形アルゴリズムオブジ
ェクト１１１は、与えられた形状に対して、それを変形
した後の形状を返す変形メソッド１１２を所持する。ま
た、図１１は、形状表示オブジェクトの構成を示してい
る。図１１の形状表示オブジェクト１２１は、図４のタ
イミングフラグオブジェクト５２、状態フラグオブジェ
クト１２２、および表示メソッド１２３を所持する。表
示メソッド１２３は、与えられた形状をディスプレイ画
面に表示する。

【００３４】図１２は、コスト関数オブジェクト生成オ
ブジェクトの構成を示している。図１２のコスト関数オ
ブジェクト生成オブジェクト１３１は、図２のコスト関
数生成部３４に対応し、与えられた問題に対応するコス
ト関数オブジェクト７１を生成する生成メソッド１３２
を所持する。

【００３５】図１３は、開始形状生成オブジェクト生成
オブジェクトの構成を示している。図１３の開始形状生
成オブジェクト生成オブジェクト１４１は、図２の開始
形状生成部３６に対応し、与えられた問題に対応する開
始形状生成オブジェクト８１を生成する生成メソッド１
４２を所持する。

【００３６】図１４は、形状オブジェクト生成オブジェ
クトの構成を示している。図１４の形状オブジェクト生
成オブジェクト１５１は、与えられた問題に対応する形
状オブジェクト４２を生成する生成メソッド１５２を所
持する。また、図１５は、変形要素オブジェクト生成オ
ブジェクトの構成を示している。図１５の変形要素オブ
ジェクト生成オブジェクト１６１は、与えられた問題に
対応する変形要素オブジェクト４５を生成する生成メソ
ッド１６２を所持する。

【００３７】図１６は、変形アルゴリズム管理オブジェ
クト生成オブジェクトの構成を示している。図１６の変
形アルゴリズム管理オブジェクト生成オブジェクト１７
１は、図２の変形要素の順序付けアルゴリズム生成部３
２に対応し、与えられた問題に対応する変形アルゴリズ
ム管理オブジェクト９１を生成する生成メソッド１７２
を所持する。

【００３８】図１７は、変形アルゴリズム群オブジェク
ト生成オブジェクトの構成を示している。図１７の変形
アルゴリズム群オブジェクト生成オブジェクト１８１
は、図２の変形パターン生成部３５に対応し、与えられ
た問題に対応する変形アルゴリズム群オブジェクト１０
１を生成する生成メソッド１８２を所持する。また、図
１８は、変形アルゴリズムオブジェクト生成オブジェク
トの構成を示している。図１８の変形アルゴリズムオブ
ジェクト生成オブジェクト１９１は、与えられた問題に
対応する変形アルゴリズムオブジェクト１１１を生成す
る生成メソッド１９２を所持する。

【００３９】図１９は、形状表示オブジェクト生成オブ
ジェクトの構成を示している。図１９の形状表示オブジ
ェクト生成オブジェクト２０１は、与えられた問題に対
応する形状表示オブジェクト１２１を生成する生成メソ
ッド２０２を所持する。

【００４０】以上説明したオブジェクトの他に、図２の
変形要素毎の探索終了条件１２、探索終了条件１４、変
形要素毎の探索終了条件生成部３１、および探索終了条
件生成部３３の各々に対応するオブジェクトを設けて、
これらの探索終了条件を制御することもできる。

【００４１】次に、共通オブジェクトが行う処理につい
て、より詳細に説明する。ここでは、変形アルゴリズム
群オブジェクト１０１が管理する変形アルゴリズムによ
る変形操作がすべて終了したとき、１つの変形要素に関
する探索が終了し、ユーザがマウス等を用いて画面上の
停止ボタンを押す操作を行ったとき、すべての探索が終
了する。

【００４２】図２０は、システムを起動する起動プログ
ラムの処理のフローチャートである。起動プログラム
は、まず、コスト関数オブジェクト生成オブジェクト１
３１を起動して、コスト関数オブジェクト７１を生成し
（ステップＳ１）、開始形状生成オブジェクト生成オブ
ジェクト１４１を起動して、開始形状生成オブジェクト
８１を生成し（ステップＳ２）、変形アルゴリズム管理
オブジェクト生成オブジェクト１７１を起動して、変形
アルゴリズム管理オブジェクト９１を生成する（ステッ
プＳ３）。

【００４３】次に、探索エンジンオブジェクト４１を生
成し（ステップＳ４）、形状表示オブジェクト１２１を
生成する（ステップＳ５）。そして、起動ボタンオブジ
ェクト５１を生成し（ステップＳ６）、停止ボタンオブ
ジェクト６１を生成する（ステップＳ７）。

【００４４】次に、形状表示オブジェクト１２１に対応
する表示領域を表示し（ステップＳ８）、起動ボタンオ
ブジェクト５１に対応する起動ボタンを表示し（ステッ
プＳ９）、停止ボタンオブジェクト６１に対応する停止
ボタンを表示して（ステップＳ１０）、処理を終了す
る。

【００４５】図２１および図２２は、図３の探索エンジ
ンオブジェクト４１が所持する探索メソッド４４の処理
のフローチャートである。探索メソッド４４は、まず、
探索形状を表す形状オブジェクト４２が存在するかどう
かをチェックし（図２１のステップＳ２１）、それが存
在しなければ処理を終了する。形状オブジェクト４２が
存在すれば、図５の停止ボタンオブジェクト６１が所持
する終了フラグオブジェクト６２の終了フラグを伏せる
（オフにする）（ステップＳ２２）。

【００４６】次に、探索形状のコスト値が求まっている
かどうかをチェックし（ステップＳ２３）、コスト値が
求まっていなければ、図６のコスト関数オブジェクト７
１に探索形状のコスト値を問い合せ、得られたコスト値
をコスト値オブジェクト４３のコスト値に格納する（ス
テップＳ２４）。

【００４７】次に、終了フラグオブジェクト６２の終了
フラグが立っているかどうか（オンかどうか）を停止ボ
タンオブジェクト６１に問い合せ、終了フラグが立って
いれば処理を終了する（ステップＳ２５）。

【００４８】次に、図８の変形アルゴリズム管理オブジ
ェクト９１に次の変形要素が存在するかどうかを問い合
せる（ステップＳ２６、Ｓ２７）。次の変形要素が存在
しなければ、図１１の形状表示オブジェクト１２１が所
持する状態フラグオブジェクト１２２の状態フラグを立
てて、探索形状の表示を依頼し（ステップＳ２８）、変
形アルゴリズム管理オブジェクト９１に初期化メソッド
９２の実行を依頼する（ステップＳ２９）。

【００４９】次に、変形アルゴリズム管理オブジェクト
９１に次の変形要素を問い合せ（ステップＳ３０）、図
９の変形アルゴリズム群オブジェクト１０１に対して、
得られた変形要素に基づいて初期化メソッド９２を実行
するように依頼する（ステップＳ３１）。

【００５０】次に、変形アルゴリズム群オブジェクト１
０１に次の変形アルゴリズムが存在するかどうかを問い
合せる（図２２のステップＳ３２、Ｓ３３）。次の変形
アルゴリズムが存在すれば、その変形アルゴリズムを表
す図１０の変形アルゴリズムオブジェクト１１１を取得
し（ステップＳ３４）、得られた変形アルゴリズムオブ
ジェクト１１１に対して、探索形状の変形形状を問い合
せる（ステップＳ３５）。

【００５１】次に、得られた変形形状のコスト値をコス
ト関数オブジェクト７１に問い合せ、得られたコスト値
をコスト値オブジェクト４３が所持する探索形状のコス
ト値と比較する（ステップＳ３６）。変形形状のコスト
値が探索形状のコスト値以上であれば、ステップＳ３２
以降の処理を繰り返し、変形形状のコスト値が探索形状
のコスト値より小さければ、変形形状を探索形状として
採用し、形状オブジェクト４２と変形された変形要素オ
ブジェクト４５を更新する（ステップＳ３７）。

【００５２】そして、変形形状のコスト値をコスト値オ
ブジェクト４３のコスト値に代入し（ステップＳ３
８）、変形アルゴリズム群オブジェクト１０１が所持す
る更新フラグオブジェクト１０２の更新フラグを立てて
（ステップＳ３８）、ステップＳ３２以降の処理を繰り
返す。

【００５３】ステップＳ３３において次の変形アルゴリ
ズムが存在しなければ、形状表示オブジェクト１２１が
所持する状態フラグオブジェクト１２２の状態フラグを
伏せて、探索形状の表示を依頼し（ステップＳ４０）、
図２１のステップＳ２５以降の処理を繰り返す。これに
より、次の変形要素に関する処理が行われる。

【００５４】図２３は、図４の起動ボタンオブジェクト
５１が所持する起動メソッド５３の処理のフローチャー
トである。起動メソッド５３は、まず、起動ボタンが押
されたかどうかを定期的にチェックする（ステップＳ４
１）。起動ボタンが押されたら、タイミングフラグオブ
ジェクト５２のタイミングフラグを設定し（ステップＳ
４２）、探索エンジンオブジェクト４１に探索の開始を
依頼して（ステップＳ４３）、処理を終了する。

【００５５】ステップＳ４２においては、タイミングフ
ラグを立てる処理と伏せる処理の２通りの処理が考えら
れる。探索形状を画面に表示するかどうかは、後述する
ように、タイミングフラグと状態フラグの関係に基づい
て決定されるため、タイミングフラグを立てるか伏せる
かに応じて異なる表示タイミングを指定することができ
る。

【００５６】図２４は、図５の停止ボタンオブジェクト
６１が所持する停止メソッド６３の処理のフローチャー
トである。停止メソッド６３は、まず、起動ボタンが押
されたかどうかを定期的にチェックする（ステップＳ５
１）。停止ボタンが押されたら、終了フラグオブジェク
ト６２の終了フラグを立てて（ステップＳ５２）、処理
を終了する。

【００５７】次に、具体的な最適化問題としてばね吊り
問題とＮ体問題を用いて、個別問題に応じたオブジェク
トの構成と動作について説明する。ばね吊り問題は、ば
ねの両端を固定して吊り下げ、最終的に静止したときの
形状を求める問題である。この問題では、図３の形状オ
ブジェクト４２は、ばね形状（ｘｙ平面上のＮ＋２個の
点を結んだ折れ線）、ばね質量、ばね定数、およびばね
の自然の長さをデータとして所持する。Ｎ＋２個の点の
うち両端の２点は固定されており、ばねの変形は残るＮ
個の点の移動によって生じる。このとき、この形状オブ
ジェクト４２に含まれるＮ＋２個の点のうち、両端の点
を除いたＮ個の点が、それぞれ、変形要素オブジェクト
４５となる。

【００５８】図６のコスト関数オブジェクト７１は、一
定重力下における形状オブジェクト４２のポテンシャル
エネルギーをコスト値とする。例えば、形状オブジェク
ト４２のＮ＋２個の点をｐ₀，ｐ₁，ｐ₂，．．．，ｐ
_N，ｐ_N+1とし、点ｐ_iの座標を（ｘ，ｙ）＝（ｘ_i，
ｙ_i）（ｉ＝０，１，．．．，Ｎ，Ｎ＋１）とし、（ｘ
₀，ｙ₀）＝（０，０）、（ｘ_N+1，ｙ_N+1）＝（Ｌ，
０）とする。また、ばねの質量をＭとし、ばね定数をｋ
とし、ばねの自然の長さをＬ₀とすると、形状オブジェ
クト４２のコスト値は、次式により計算される。

【００５９】

【数１】ただし、簡単のため重力加速度を１としており、｜ｐ_i
−ｐ_i+1｜はｐ_iとｐ_i+ ₁の間の距離を表している。

【００６０】また、図７の開始形状生成オブジェクト８
１は、画面上に表示される以下のようなＧＵＩ（graphi
c user interface）コンポーネントを含む。（１）開始形状のばね質量Ｍを設定するための入力フィ
ールド（２）開始形状のばね定数ｋを設定するための入力フィ
ールド（３）開始形状のばねの自然の長さＬ₀を設定するため
の入力フィールド（４）開始形状のばねの固定端間の距離Ｌを設定するた
めの入力フィールド（５）開始形状のばね形状を表わす点の個数Ｎを設定す
るための入力フィールド（６）開始形状の生成を行うための初期化ボタン図２５は、開始形状生成オブジェクト８１が所持する開
始形状メソッド８２の処理のフローチャートである。開
始形状メソッド８２は、まず、初期化ボタンが押された
かどうかを定期的にチェックし（ステップＳ６１）、初
期化ボタンが押されたら、次に、上述の入力フィールド
に設定されたパラメータが適切かどうかをチェックする
（ステップＳ６２）。

【００６１】すべてのパラメータが適切であれば、それ
らを形状オブジェクト４２に記憶させ（ステップＳ６
３）、端点ｐ₀とｐ_N+1の間の距離Ｌに基づき、ｐ₀の
座標（ｘ₀，ｙ₀）を（０，０）に設定し、ｐ_N+1の座
標（ｘ_N+1，ｙ_N+1）を（Ｌ，０）に設定する（ステッ
プＳ６４）。

【００６２】次に、座標（０，Ｌ／２）と（Ｌ，−Ｌ／
２）を対角頂点として生成される正方形内に、ランダム
にＮ個の点を生成して、それらの点の列をｐ₁，
ｐ₂，．．．，ｐ_Nとして形状オブジェクト４２に記憶
させる（ステップＳ６５）。そして、得られた形状オブ
ジェクト４２を開始形状として探索エンジンオブジェク
ト４１に記憶させ（ステップＳ６６）、処理を終了す
る。

【００６３】また、ステップＳ６２において、いずれか
のパラメータが適切でなければ、エラー処理を行ってエ
ラーメッセージ等を表示し（ステップＳ６７）、処理を
終了する。

【００６４】また、図８の変形アルゴリズム管理オブジ
ェクト９１は、上述したメソッドの他に、ポインタ（整
数）を格納するポインタオブジェクトを所持し、以下の
ような処理を行う。

【００６５】図２６は、変形アルゴリズム管理オブジェ
クト９１が所持する初期化メソッド９２の処理のフロー
チャートである。初期化メソッド９２は、ポインタオブ
ジェクトのポインタに１を代入して（ステップＳ７
１）、処理を終了する。

【００６６】図２７は、変形アルゴリズム管理オブジェ
クト９１が所持する変形要素メソッド９３の処理のフロ
ーチャートである。変形要素メソッド９３は、まず、ポ
インタの番号に対応する点が形状オブジェクト４２に存
在するかどうかをチェックし（ステップＳ８１）、その
点が存在すれば、対応する変形要素オブジェクト４５の
情報を取り出す（ステップＳ８２）。そして、ポインタ
に１を加算し（ステップＳ８３）、取り出した情報を返
して（ステップＳ８４）、処理を終了する。

【００６７】また、ステップＳ８１において、ポインタ
の番号に対応する点が存在しなければ、エラー処理を行
って（ステップＳ８５）、処理を終了する。図２８は、
変形アルゴリズム管理オブジェクト９１が所持する通知
メソッド９４の処理のフローチャートである。通知メソ
ッド９４は、まず、ポインタの番号に対応する点が形状
オブジェクト４２に存在するかどうかをチェックし（ス
テップＳ９１）、その点が存在すれば、“Ｙｅｓ”を返
して（ステップＳ９２）、処理を終了する。その点が存
在しなければ、“Ｎｏ”を返して（ステップＳ９３）、
処理を終了する。

【００６８】また、図９の変形アルゴリズム群オブジェ
クト１０１は、上述した更新フラグオブジェクト１０２
の他に、変形要素オブジェクト４５、カウンタオブジェ
クト、移動量オブジェクト、および移動方向オブジェク
トを所持する。カウンタオブジェクトは、カウンタ（整
数）を格納し、移動量オブジェクトは、移動量（実数）
を格納し、移動方向オブジェクトは、移動方向（２次元
ベクトル）を格納する。

【００６９】図２９は、変形アルゴリズム群オブジェク
ト１０１が所持する初期化メソッド１０３の処理のフロ
ーチャートである。初期化メソッド１０３は、まず、与
えられた変形要素オブジェクト４５の情報を記憶し（ス
テップＳ１０１）、更新フラグオブジェクト１０２の更
新フラグを伏せて（ステップＳ１０２）、カウンタオブ
ジェクトのカウンタに０を代入する（ステップＳ１０
３）。そして、移動量オブジェクトの移動量を初期化し
（ステップＳ１０４）、移動方向オブジェクトの移動方
向を初期化して（ステップＳ１０５）、処理を終了す
る。

【００７０】ステップＳ１０４において、移動量Δｐ
は、例えば、次式により初期化される。

【００７１】

【数２】また、ステップＳ１０１において記憶された変形要素オ
ブジェクト４５が点ｐ _iであるとすると、ステップＳ１
０５では、移動方向を表す２次元ベクトルのｘ成分ｄ_x
とｙ成分ｄ_yが、例えば、次式により初期化される。ｄ_x＝ｋ（α_i（ｘ_i−ｘ_i-1）−α_i+1（ｘ_i+1−ｘ_i））ｄ_y＝Ｍ／Ｎ＋ｋ（α_i（ｙ_i−ｙ_i-1）−α_i+1（ｙ_i+1−ｙ_i）） α_i＝Ｎ−Ｌ₀／｜ｐ_i−ｐ_i-1｜［３］図３０は、変形アルゴリズム群オブジェクト１０１が所
持する変形アルゴリズムメソッド１０４の処理のフロー
チャートである。変形アルゴリズムメソッド１０４は、
まず、移動方向の２次元ベクトル（ｄ_x，ｄ_y）が
（０，０）かどうかをチェックする（ステップＳ１１
１）。（ｄ_x，ｄ_y）＝（０，０）でなければ、ベクト
ル（ｄ_x，ｄ_y）と移動量Δｐを元にして移動ベクトル
を作成し、それを所持する移動ベクトルオブジェクトを
生成する（ステップＳ１１２）。ここでは、ベクトル
（ｄ_x，ｄ_y）をスカラー倍して、長さがΔｐのベクト
ルを作成し、それを移動ベクトルとする。

【００７２】次に、変形要素オブジェクト４５と移動ベ
クトルオブジェクトを元にして、図１０の変形アルゴリ
ズムオブジェクト１１１を作成する（ステップＳ１１
３）。そして、移動量Δｐを半分の値に設定し（ステッ
プＳ１１４）、カウンタに１を加算し（ステップＳ１１
５）、作成された変形アルゴリズムオブジェクト１１１
の情報を返して（ステップＳ１１６）、処理を終了す
る。

【００７３】また、ステップＳ１１１において、
（ｄ_x，ｄ_y）＝（０，０）であれば、エラー処理を行
って（ステップＳ１１７）、処理を終了する。図３１
は、変形アルゴリズム群オブジェクト１０１が所持する
通知メソッド１０５の処理のフローチャートである。通
知メソッド１０５は、まず、（ｄ_x，ｄ _y）＝（０，
０）であるかどうかをチェックし（ステップＳ１２
１）、（ｄ_x，ｄ_y）＝（０，０）であれば、“Ｎｏ”
を返して（ステップＳ１２２）、処理を終了する。

【００７４】（ｄ_x，ｄ_y）＝（０，０）でなければ、
次に、カウンタをチェックし（ステップＳ１２３）、カ
ウンタが１５以上であれば、“Ｎｏ”を返して（ステッ
プＳ１２２）、処理を終了する。カウンタが１５未満で
あれば、次に、更新フラグをチェックし（ステップＳ１
２４）、更新フラグが立っていれば、“Ｎｏ”を返して
（ステップＳ１２２）、処理を終了する。更新フラグが
立っていなければ、“Ｙｅｓ”を返して（ステップＳ１
２５）、処理を終了する。

【００７５】図３０のステップＳ１１３で作成された変
形アルゴリズムオブジェクト１１１は、変形要素オブジ
ェクト４５と移動ベクトルオブジェクトを所持し、図３
２に示すような処理を行う。

【００７６】図３２は、変形アルゴリズムオブジェクト
１１１が所持する変形メソッド１１２の処理のフローチ
ャートである。変形メソッド１１２は、まず、与えられ
た形状オブジェクト４２のコピーを作成し（ステップＳ
１３１）、コピーに含まれる与えられた変形要素オブジ
ェクト４５を移動ベクトルに従って移動する（ステップ
Ｓ１３２）。そして、得られた形状オブジェクトを返し
て（ステップＳ１３３）、処理を終了する。

【００７７】また、図３３は、図１１の形状表示オブジ
ェクト１２１が所持する表示メソッド１２３の処理のフ
ローチャートである。表示メソッド１２３は、まず、タ
イミングフラグオブジェクト５２のタイミングフラグと
状態フラグオブジェクト１２２の状態フラグが一致する
かどうかをチェックする（ステップＳ１４１）。それら
が一致すれば、形状オブジェクト４２が表す探索形状を
画面に表示して（ステップＳ１４２）、処理を終了す
る。また、２つのフラグが一致しなければ、探索形状を
表示せずに、処理を終了する。

【００７８】タイミングフラグおよび状態フラグは、論
理“０”のとき、伏せた状態に対応し、論理“１”のと
き、立った状態に対応する。また、状態フラグは、論理
“０”のとき、１つの変形要素に関する探索が終了した
状態を表し、論理“１”のとき、形状の変形要素毎の探
索を一巡した状態を表す。

【００７９】したがって、起動ボタンが押されたときに
タイミングフラグが論理“０”に設定されていれば、１
つの変形要素に関する探索が終了する度に、探索形状が
画面に表示される。また、起動ボタンが押されたときに
タイミングフラグが論理“１”に設定されていれば、変
形要素毎の探索を一巡する度に、探索形状が画面に表示
される。

【００８０】図３４から図３６までは、ばね吊り問題の
シミュレーションにおける表示画面の例を示している。
図３４の表示画面において、ボタン２０８、２０９は起
動ボタンに対応し、ボタン２１０は停止ボタンに対応す
る。例えば、起動ボタン２０８が押された場合は、タイ
ミングフラグは論理“０”に設定され、起動ボタン２０
９が押された場合は、タイミングフラグは論理“１”に
設定される。

【００８１】また、フィールド２１１、２１２、２１
３、２１４、２１５は、それぞれ、ばねの自然の長さＬ
₀、質量Ｍ、ばね定数ｋ、両端間の距離Ｌ、移動可能な
点（質点）の数Ｎの入力フィールドに対応する。

【００８２】例えば、ユーザが、Ｌ₀＝１０、Ｍ＝１０
０、ｋ＝１、Ｌ＝１５、Ｎ＝２１と入力して初期化ボタ
ン２１６を押すと、開始形状２１７、２１８が表示され
る。形状２１７、２１８は、同一の開始形状を２つの方
法で表示した結果を表し、形状２１７は、縦横が同一の
スケーリングで表示されており、形状２１８は、縦横が
異なるスケーリングで表示されている。また、放物線２
１９、２２０は、ばねが最終的に到達する形状に対応
し、探索の開始時にあらかじめ表示されている。

【００８３】図３４の形状を開始形状として探索を行う
と、ばねの形状は、図３５に示すように、Ｖ字型の形状
２２１、２２２に変化する。そして、探索が十分に進む
と、図３６に示すように、放物線２１９、２２０にほと
んど重なるような形状に収束する。

【００８４】このように、ばね吊り問題においては、ば
ねの形状を複数の点の集合で表し、各点を移動させるこ
とで、形状を変化させながら安定な状態を求めることが
できる。ユーザは、あらかじめ決められたパラメータを
入力するだけで、自動的に吊り下げられたばねの静止状
態を得ることができる。

【００８５】次に、Ｎ体問題は、Ｎ個の星（天体）の周
期運行の軌道を求める問題である。この問題では、図３
の形状オブジェクト４２は、図３７に示すように、周期
Ｔのデータ２３１、各星の運行軌道を閉折れ線グラフで
表現したときの頂点数Ｍのデータ２３２、およびＮ個の
星オブジェクト２３３（Ｏ１〜ＯＮ）の集約オブジェク
トを所持する。

【００８６】各星オブジェクト２３３は、星の運行軌道
の形状オブジェクト２３４（要素数Ｍの３次元ベクトル
の配列）と星の質量のデータ２３５を所持し、形状オブ
ジェクト２３４は、Ｍ個の頂点の３次元空間における位
置を表す位置ベクトル２３６（Ｖ１〜ＶＭ）を所持す
る。

【００８７】この形状オブジェクト４２には、Ｎ個の星
の情報が含まれており、各星の軌道は、Ｍ個の頂点から
なる折れ線で表されている。したがって、形状オブジェ
クト４２には、ＮＭ個の折れ線軌道の頂点の情報が含ま
れており、各頂点が変形要素オブジェクト４５となる。
この場合、変形要素オブジェクト４５には、Ｎ個の星の
うちの１つを指す星ポインタ、Ｍ個の頂点のうちの１つ
を指す頂点ポインタ、およびその頂点の位置を表す位置
ベクトルの情報が含まれる。

【００８８】図６のコスト関数オブジェクト７１は、形
状オブジェクト４２が表すＮ個の星がNewtonの万有引力
で引き合うことによって生じる力学系の作用（ラグラン
ジアンの時間積分）を、コスト値とする。

【００８９】例えば、形状オブジェクト４２に属するａ
番目の星オブジェクトＯａのｉ番目の頂点の位置ベクト
ルＶｉを、ｐ_a,i（１≦ａ≦Ｎ，１≦ｉ≦Ｍ）とし、形
状オブジェクト４２に属する星オブジェクトＯａの質量
をＭ_aとする。また、３次元ベクトルの列ｐ_a,b,iとｖ
_a,b,i（１≦ａ，ｂ≦Ｎ，１≦ｉ≦Ｍ）を次式により定
義する。ｐ_a,b,i≡ｐ_a,i−ｐ_b,i ｖ_a,b,i≡ｐ_{a,b,(i+1)modM}−ｐ_a,b,i ［４］このとき、形状オブジェクト４２のコスト値は、次式に
より計算される。

【００９０】

【数３】ただし、簡単のため重力加速度を１としており、（ｉ＋
１）ｍｏｄＭは、Ｍによる剰余演算を表している。

【００９１】また、図７の開始形状生成オブジェクト８
１は、画面上に表示される以下のようなＧＵＩコンポー
ネントを含む。（１）開始形状の星の個数Ｎを設定するための入力フィ
ールド（２）開始形状の星の運行軌道を折れ線グラフで表した
ときの頂点数Ｍを設定するための入力フィールド（３）開始形状の生成を行うための円軌道ボタン図３８は、開始形状生成オブジェクト８１が所持する開
始形状メソッド８２の処理のフローチャートである。開
始形状メソッド８２は、まず、円軌道ボタンが押された
かどうかを定期的にチェックし（ステップＳ１５１）、
円軌道ボタンが押されたら、次に、上述の入力フィール
ドに設定されたパラメータＭ、Ｎが適切かどうかをチェ
ックする（ステップＳ１５２）。

【００９２】すべてのパラメータが適切であれば、頂点
数Ｍを形状オブジェクト４２に記憶させ（ステップＳ１
５３）、個数Ｎを形状オブジェクト４２に記憶させる
（ステップＳ１５４）。また、周期Ｔ＝１を形状オブジ
ェクト４２に記憶させる（ステップＳ１５５）。

【００９３】次に、変数ｉに１を代入し（ステップＳ１
５６）、ｉとＮ＋１を比較する（ステップＳ１５７）。
ｉ＜Ｎ＋１であれば、０．００１以上１００以下の実数
をランダムに選択し、それをｉ番目の星オブジェクトＯ
ｉに質量として記憶させる（ステップＳ１５８）。

【００９４】次に、０．１以上１．１以下の実数をラン
ダムに選択し、変数ｒに代入する（ステップＳ１５
９）。次に、ｘｙｚ空間の原点（ｘ，ｙ，ｚ）＝（０，
０，０）を中心とし、ｒを半径とする円に内接する正Ｍ
角形であって、１つの頂点の座標が（ｒ，０，０）であ
るようなものを求める（ステップＳ１６０）。そして、
その正Ｍ角形のＭ個の頂点の位置ベクトルの配列を、星
オブジェクトＯｉに折れ線軌道として記憶させる（ステ
ップＳ１６１）。

【００９５】次に、変数ｉに１を加算し（ステップＳ１
６２）、ステップＳ１５７以降の処理を繰り返し、ｉが
Ｎ＋１に達すると、処理を終了する。また、ステップＳ
１５２において、いずれかのパラメータが適切でなけれ
ば、エラー処理を行って（ステップＳ１６３）、処理を
終了する。

【００９６】また、図８の変形アルゴリズム管理オブジ
ェクト９１は、星ポインタ（整数）を格納する星ポイン
タオブジェクトと、頂点ポインタ（整数）を格納する頂
点ポインタオブジェクトとを所持し、以下のような処理
を行う。

【００９７】図３９は、変形アルゴリズム管理オブジェ
クト９１が所持する初期化メソッド９２の処理のフロー
チャートである。初期化メソッド９２は、星ポインタオ
ブジェクトの星ポインタに１を代入し（ステップＳ１７
１）、頂点ポインタオブジェクトの頂点ポインタに１を
代入して（ステップＳ１７２）、処理を終了する。

【００９８】図４０は、変形アルゴリズム管理オブジェ
クト９１が所持する変形要素メソッド９３の処理のフロ
ーチャートである。変形要素メソッド９３は、まず、頂
点ポインタの値を形状オブジェクト４２が所持するＭと
比較する（ステップＳ１８１）。頂点ポインタの値がＭ
以下であれば、次に、星ポインタの値を形状オブジェク
ト４２が所持する星オブジェクト２３３の数Ｎと比較す
る（ステップＳ１８２）。

【００９９】星ポインタの値がＮ以下であれば、星ポイ
ンタに対応する星オブジェクト２３３の情報を形状オブ
ジェクト４２から取り出し（ステップＳ１８３）、その
星オブジェクト２３３から頂点ポインタに対応する頂点
の位置ベクトル２３６を取り出す（ステップＳ１８
４）。そして、星ポインタに１を加算し（ステップＳ１
８５）、取り出した頂点の情報を変形要素として返して
（ステップＳ１８６）、処理を終了する。

【０１００】ステップＳ１８２において、星ポインタの
値がＮを越えていれば、頂点ポインタに１を加算し（ス
テップＳ１８７）、星ポインタに１を代入して（ステッ
プＳ１８８）、ステップＳ１８１以降の処理を繰り返
す。また、ステップＳ１８１において、頂点ポインタの
値がＭを越えていれば、エラー処理を行って（ステップ
Ｓ１８９）、処理を終了する。

【０１０１】図４１は、変形アルゴリズム管理オブジェ
クト９１が所持する通知メソッド９４の処理のフローチ
ャートである。通知メソッド９４は、まず、星ポインタ
に対応する星オブジェクト２３３が形状オブジェクト４
２に存在するかどうかをチェックする（ステップＳ１９
１）。その星オブジェクト２３３が存在しなければ、
“Ｎｏ”を返して（ステップＳ１９２）、処理を終了す
る。

【０１０２】星ポインタに対応する星オブジェクト２３
３が存在すれば、次に、頂点ポインタの値をチェックす
る（ステップＳ１９３）。頂点ポインタの値が１以上Ｍ
以下であれば、“Ｙｅｓ”を返して（ステップＳ１９
４）、処理を終了する。頂点ポインタの値が１より小さ
いかまたはＭより大きければ、“Ｎｏ”を返して（ステ
ップＳ１９２）、処理を終了する。

【０１０３】また、図９の変形アルゴリズム群オブジェ
クト１０１は、更新フラグオブジェクト１０２の他に、
星ポインタオブジェクト、頂点ポインタオブジェクト、
移動量カウンタオブジェクト、移動量オブジェクト、移
動方向テーブルオブジェクト、および移動方向テーブル
カウンタオブジェクトを所持する。

【０１０４】移動量カウンタオブジェクトは、移動量カ
ウンタ（整数）を格納し、移動量オブジェクトは、移動
量（実数）を格納し、移動方向テーブルオブジェクト
は、移動方向テーブル（３次元ベクトルの配列）を格納
し、移動方向テーブルカウンタオブジェクトは、移動方
向テーブルカウンタ（整数）を格納する。

【０１０５】図４２は、変形アルゴリズム群オブジェク
ト１０１が所持する初期化メソッド１０３の処理のフロ
ーチャートである。初期化メソッド１０３は、まず、与
えられた変形要素オブジェクト４５の情報を星ポインタ
オブジェクトと頂点ポインタオブジェクトに記憶させ
（ステップＳ２０１）、更新フラグオブジェクト１０２
の更新フラグを伏せて（ステップＳ２０２）、移動量カ
ウンタオブジェクトの移動量カウンタに１を代入する
（ステップＳ２０３）。

【０１０６】次に、移動量オブジェクトの移動量を初期
化し（ステップＳ２０４）、移動方向テーブルカウンタ
オブジェクトの移動方向テーブルカウンタに１を代入し
（ステップＳ２０５）、移動方向テーブルオブジェクト
の移動方向テーブルが初期化されているかどうかをチェ
ックする（ステップＳ２０６）。

【０１０７】移動方向テーブルが初期化されていれば処
理を終了し、それが初期化されていなければ、移動方向
テーブルを初期化して（ステップＳ２０７）、処理を終
了する。

【０１０８】今、ステップＳ２０１において記憶された
星ポインタおよび頂点ポインタの値を、それぞれａおよ
びｉとすると、ステップＳ２０４において、移動量Δｐ
は、例えば、次式により初期化される。 Δｐ＝（１／４）（｜ｐ_a,i-1−ｐ_a,i｜＋｜ｐ_a,i−ｐ_a,i+1｜）［６］ここで、ｐ_a,i-1、ｐ_a,i、ｐ_a,i+1は、それぞれ、星
ポインタに対応する星オブジェクトＯａのｉ−１番目、
ｉ番目、ｉ＋１番目の頂点の位置ベクトルを表す。

【０１０９】また、ステップＳ２０７において、移動方
向テーブルは、例えば、次のようにして初期化される。
まず、３次元ベクトルｅ₁、ｅ₂、ｅ₃を次式のように
選ぶ。ｅ₁＝（１，０，０）ｅ₂＝（０，１，０）［７］ｅ₃＝（０，０，１）次に、要素数６の３次元ベクトルの配列を作成し、その
配列の１番目の要素にｅ₁を代入し、２番目の要素に−
ｅ₁を代入し、３番目の要素にｅ₂を代入し、４番目の
要素に−ｅ₂を代入し、５番目の要素にｅ₃を代入し、
６番目の要素に−ｅ₃を代入する。そして、この３次元
ベクトルの配列を移動方向テーブルとする。

【０１１０】図４３は、変形アルゴリズム群オブジェク
ト１０１が所持する変形アルゴリズムメソッド１０４の
処理のフローチャートである。変形アルゴリズムメソッ
ド１０４は、まず、移動方向テーブルカウンタの値をチ
ェックする（ステップＳ２１１）。

【０１１１】カウンタの値が６以下であれば、カウンタ
に対応する配列要素を移動方向テーブルから取り出し
（ステップＳ２１２）、その配列要素と移動量Δｐを元
にして移動ベクトルを作成し、それを所持する移動ベク
トルオブジェクトを生成する（ステップＳ２１３）。こ
こでは、取り出された３次元ベクトルをスカラー倍し
て、長さがΔｐのベクトルを作成し、それを移動ベクト
ルとする。

【０１１２】次に、星ポインタオブジェクト、頂点ポイ
ンタオブジェクト、および移動ベクトルオブジェクトを
元にして、図１０の変形アルゴリズムオブジェクト１１
１を作成する（ステップＳ２１４）。そして、移動方向
テーブルカウンタに１を加算し（ステップＳ２１５）、
作成された変形アルゴリズムオブジェクト１１１の情報
を返して（ステップＳ２１６）、処理を終了する。

【０１１３】また、ステップＳ２１１において、カウン
タの値が６を越えていれば、移動量Δｐを半分の値に設
定し（ステップＳ２１７）、移動量カウンタに１を加算
し（ステップＳ２１８）、移動方向テーブルカウンタに
１を代入して（ステップＳ２１９）、ステップＳ２１２
以降の処理を行う。

【０１１４】図４４は、変形アルゴリズム群オブジェク
ト１０１が所持する通知メソッド１０５の処理のフロー
チャートである。通知メソッド１０５は、まず、移動量
カウンタの値をチェックし（ステップＳ２２１）、カウ
ンタの値が１０以上であれば、“Ｎｏ”を返して（ステ
ップＳ２２２）、処理を終了する。

【０１１５】カウンタの値が１０未満であれば、次に、
更新フラグをチェックし（ステップＳ２２３）、更新フ
ラグが立っていれば、“Ｎｏ”を返して（ステップＳ２
２２）、処理を終了する。更新フラグが立っていなけれ
ば、“Ｙｅｓ”を返して（ステップＳ２２４）、処理を
終了する。

【０１１６】図４３のステップＳ２１４で作成された変
形アルゴリズムオブジェクト１１１は、星ポインタオブ
ジェクト、頂点ポインタオブジェクト、および移動ベク
トルオブジェクトを所持し、図４５に示すような処理を
行う。

【０１１７】図４５は、変形アルゴリズムオブジェクト
１１１が所持する変形メソッド１１２の処理のフローチ
ャートである。変形メソッド１１２は、まず、与えられ
た形状オブジェクト４２のコピーを作成する（ステップ
Ｓ１３１）。次に、コピーに含まれる与えられた星ポイ
ンタに対応する星オブジェクト２３３の与えられた頂点
ポインタに対応する頂点の位置を移動ベクトルに従って
移動する（ステップＳ２３２）。そして、得られた形状
オブジェクトを返して（ステップＳ２３３）、処理を終
了する。

【０１１８】また、この問題において、図１１の形状表
示オブジェクト１２１が所持する表示メソッド１２３
は、図３３と同様の処理を行い、タイミングフラグと状
態フラグが一致したときに探索形状を表示する。

【０１１９】図４６および図４７は、Ｎ体問題のシミュ
レーションにおける表示画面の例を示している。図４６
の表示画面において、ボタン２４１、２４２は起動ボタ
ンに対応し、ボタン２４３は停止ボタンに対応する。例
えば、起動ボタン２４１が押された場合は、タイミング
フラグは論理“０”に設定され、起動ボタン２４２が押
された場合は、タイミングフラグは論理“１”に設定さ
れる。

【０１２０】また、フィールド２４４、２４５は、それ
ぞれ、頂点の数Ｍ、星の数Ｎの入力フィールドに対応す
る。例えば、ユーザが、Ｍ＝６０、Ｎ＝３と入力して円
軌道ボタン２４６を押すと、３つの星２４７、２４８、
２４９を含む開始形状が表示される。この開始形状で
は、星２４７、２４８は、楕円状の軌道に沿って運行し
ており、星２４９は、これらの軌道の中央に静止してい
る。また、点２５０は、３つの星の重心の位置を表わし
ている。

【０１２１】図４６の形状を開始形状として探索を行う
と、各星の軌道は、図４７に示すように変化する。図４
７では、星２４７の軌道が最も内側に入り込み、静止し
ていた星２４９が、星２４７と星２４８の間の軌道に沿
って運行していることが分かる。

【０１２２】このように、Ｎ体問題においては、Ｎ個の
星の軌道を複数の点の集合で表し、各点を移動させるこ
とで、全体の形状を変化させながら安定な軌道を求める
ことができる。ユーザは、あらかじめ決められたパラメ
ータを入力するだけで、自動的に星の安定な軌道を得る
ことができる。

【０１２３】以上説明した具体例では、形状オブジェク
ト４２が表す形状モデルが与えられた問題に含まれる物
理的な物体の形状や軌跡に対応しているが、一般には、
形状オブジェクト４２は必ずしも物理的な物体に対応す
るとは限らない。例えば、経済、ビジネス等の分野にお
ける最適コスト問題の場合、日時、金額、人数等のパラ
メータを組合せて形状モデルが生成される。この場合
も、形状の変形過程を画面に表示することが可能であ
る。

【０１２４】ところで、上述した図２の処理装置は、図
４８に示すような情報処理装置（コンピュータ）を用い
て構成することができる。図４８の情報処理装置は、Ｃ
ＰＵ（中央処理装置）２５１、メモリ２５２、入力装置
２５３、出力装置２５４、外部記憶装置２５５、媒体駆
動装置２５６、およびネットワーク接続装置２５７を備
え、それらはバス２５８により互いに接続されている。

【０１２５】メモリ２５２は、例えば、ＲＯＭ（read o
nly memory）、ＲＡＭ（random access memory）等を含
み、処理に用いられるプログラムとデータを格納する。
ＣＰＵ２５１は、メモリ２５２を利用してプログラムを
実行することにより、必要な処理を行う。

【０１２６】図２の探索エンジン１１、変形要素毎の探
索終了条件１２、変形要素毎の順序付けアルゴリズム１
３、探索終了条件１４、コスト関数１５、変形パターン
１６、形状２１、変形要素２３、および生成部３１〜３
６は、メモリ２５２の特定のプログラムコードセグメン
トに格納されたソフトウェアコンポーネントに対応し、
１つ以上のインストラクションからなるプログラムによ
り実現される。

【０１２７】入力装置２５３は、例えば、キーボード、
ポインティングデバイス、タッチパネル等であり、ユー
ザからの指示や情報の入力に用いられる。出力装置２５
４は、例えば、ディスプレイ、プリンタ、スピーカ等で
あり、ユーザへの問い合わせや処理結果の出力に用いら
れる。

【０１２８】外部記憶装置２５５は、例えば、磁気ディ
スク装置、光ディスク装置、光磁気ディスク（magneto-
optical disk）装置等である。この外部記憶装置２５５
に、上述のプログラムとデータを保存しておき、必要に
応じて、それらをメモリ２５２にロードして使用するこ
ともできる。また、外部記憶装置２５５は、図２の共通
部品や個別部品を格納するデータベースとしても用いら
れる。

【０１２９】媒体駆動装置２５６は、可搬記録媒体２５
９を駆動し、その記録内容にアクセスする。可搬記録媒
体２５９としては、メモリカード、フロッピーディス
ク、ＣＤ−ＲＯＭ（compact disk read only memory
）、光ディスク、光磁気ディスク等、任意のコンピュ
ータ読み取り可能な記録媒体が用いられる。この可搬記
録媒体２５９に上述のプログラムとデータを格納してお
き、必要に応じて、それらをメモリ２５２にロードして
使用することもできる。

【０１３０】ネットワーク接続装置２５７は、ＬＡＮ
（local area network）等の任意のネットワーク（回
線）を介して外部の装置と通信し、通信に伴うデータ変
換を行う。また、必要に応じて、上述のプログラムとデ
ータを外部の装置から受け取り、それらをメモリ２５２
にロードして使用することもできる。

【０１３１】図４９は、図４８の情報処理装置にプログ
ラムとデータを供給することのできるコンピュータ読み
取り可能な記録媒体を示している。可搬記録媒体２５９
や外部のデータベース２６０に保存されたプログラムと
データは、メモリ２５２にロードされる。そして、ＣＰ
Ｕ２５１は、そのデータを用いてそのプログラムを実行
し、必要な処理を行う。

【０１３２】

【発明の効果】本発明によれば、処理対象の最適化問題
を形状モデル化することで、汎用性の高いアルゴリズム
が実現される。また、形状モデルが変形する過程を表示
することで、問題解決の過程をユーザに提示することが
でき、ユーザは、提示された過程を視覚的に理解するこ
とができる。

【図面の簡単な説明】

【図１】本発明の処理装置の原理図である。

【図２】処理装置の構成図である。

【図３】探索エンジンオブジェクトを示す図である。

【図４】起動ボタンオブジェクトを示す図である。

【図５】停止ボタンオブジェクトを示す図である。

【図６】コスト関数オブジェクトを示す図である。

【図７】開始形状生成オブジェクトを示す図である。

【図８】変形アルゴリズム管理オブジェクトを示す図で
ある。

【図９】変形アルゴリズム群オブジェクトを示す図であ
る。

【図１０】変形アルゴリズムオブジェクトを示す図であ
る。

【図１１】形状表示オブジェクトを示す図である。

【図１２】コスト関数オブジェクト生成オブジェクトを
示す図である。

【図１３】開始形状生成オブジェクト生成オブジェクト
を示す図である。

【図１４】形状オブジェクト生成オブジェクトを示す図
である。

【図１５】変形要素オブジェクト生成オブジェクトを示
す図である。

【図１６】変形アルゴリズム管理オブジェクト生成オブ
ジェクトを示す図である。

【図１７】変形アルゴリズム群オブジェクト生成オブジ
ェクトを示す図である。

【図１８】変形アルゴリズムオブジェクト生成オブジェ
クトを示す図である。

【図１９】形状表示オブジェクト生成オブジェクトを示
す図である。

【図２０】起動プログラムのフローチャートである。

【図２１】探索メソッドのフローチャート（その１）で
ある。

【図２２】探索メソッドのフローチャート（その２）で
ある。

【図２３】起動メソッドのフローチャートである。

【図２４】停止メソッドのフローチャートである。

【図２５】第１の開始形状メソッドのフローチャートで
ある。

【図２６】第１の初期化メソッドのフローチャートであ
る。

【図２７】第１の変形要素メソッドのフローチャートで
ある。

【図２８】第１の通知メソッドのフローチャートであ
る。

【図２９】第２の初期化メソッドのフローチャートであ
る。

【図３０】第１の変形アルゴリズムメソッドのフローチ
ャートである。

【図３１】第２の通知メソッドのフローチャートであ
る。

【図３２】第１の変形メソッドのフローチャートであ
る。

【図３３】表示メソッドのフローチャートである。

【図３４】第１の表示画面を示す図である。

【図３５】第２の表示画面を示す図である。

【図３６】第３の表示画面を示す図である。

【図３７】Ｎ体問題の形状オブジェクトを示す図であ
る。

【図３８】第２の開始形状メソッドのフローチャートで
ある。

【図３９】第３の初期化メソッドのフローチャートであ
る。

【図４０】第２の変形要素メソッドのフローチャートで
ある。

【図４１】第３の通知メソッドのフローチャートであ
る。

【図４２】第４の初期化メソッドのフローチャートであ
る。

【図４３】第２の変形アルゴリズムメソッドのフローチ
ャートである。

【図４４】第４の通知メソッドのフローチャートであ
る。

【図４５】第２の変形メソッドのフローチャートであ
る。

【図４６】第４の表示画面を示す図である。

【図４７】第５の表示画面を示す図である。

【図４８】情報処理装置の構成図である。

【図４９】記録媒体を示す図である。

【符号の説明】

１生成手段２格納手段３変形手段４出力手段５形状モデル１１探索エンジン１２変形要素毎の探索終了条件１３変形要素毎の順序付けアルゴリズム１４探索終了条件１５コスト関数１６変形パターン１７クリエータ２１形状２２最小コスト値２３変形要素３１、３２、３３、３４、３５、３６生成部４１、４２、４３、４５、５１、５２、６１、６２、７
１、８１、９１、１０１、１０２、１１１、１２１、１
２２、１３１、１４１、１５１、１６１、１７１、１８
１、１９１、２０１、２３３オブジェクト４４、５３、６３、７２、８２、９２、９３、９４、１
０３、１０４、１０５、１１２、１２３、１３２、１４
２、１５２、１６２、１７２、１８２、１９２、２０２
メソッド２０８、２０９、２１０、２１６、２４１、２４２、２
４３、２４６ボタン２１１、２１２、２１３、２１４、２１５、２４４、２
４５入力フィールド２１７、２１８、２２１、２２２表示形状２１９、２２０放物線２３１周期２３２頂点数２３４ベクトルの配列２３５質量２３６ベクトル２４７、２４８、２４９星２５０重心２５１ＣＰＵ２５２メモリ２５３入力装置２５４出力装置２５５外部記憶装置２５６媒体駆動装置２５７ネットワーク接続装置２５８バス２５９可搬記録媒体２６０データベース ^//

───────────────────────────────────────────────────── フロントページの続き (72)発明者桝田彰一神奈川県川崎市中原区上小田中４丁目１番１号富士通株式会社内 (72)発明者福田育夫神奈川県川崎市中原区上小田中４丁目１番１号富士通株式会社内Ｆターム(参考） 5B046 DA02 FA04 GA01 JA04

Claims

【特許請求の範囲】

【請求項１】与えられた問題を表す形状モデルを生成
する生成手段と、前記形状モデルのデータを格納する格納手段と、前記形状モデルを変形する変形手段と、変形された形状モデルを視覚的に出力する出力手段とを
備えることを特徴とする処理装置。
【請求項２】前記生成手段は、１つ以上の変形要素を
含む形状モデルを生成し、前記変形手段は、該変形要素
に基づいて該形状モデルを変形することを特徴とする請
求項１記載の処理装置。
【請求項３】前記生成手段、格納手段、変形手段、お
よび出力手段のうち少なくとも１つは、前記与えられた
問題に依存しない共通部品手段を含むことを特徴とする
請求項１記載の処理装置。
【請求項４】前記生成手段、格納手段、変形手段、お
よび出力手段のうち少なくとも１つは、前記与えられた
問題に応じて交換可能な個別部品手段を含むことを特徴
とする請求項１記載の処理装置。
【請求項５】与えられた問題を表す形状モデルを１つ
以上の変形要素を用いて生成し、該変形要素を変化させ
ながら該形状モデルを変形して、該形状モデルのコスト
値が良くなるような解を探索する探索手段と、変形要素毎の探索終了条件、全体の探索終了条件、変形
要素の処理順序、コスト関数、および変形要素の変形ア
ルゴリズムを指定する指定手段と、変形された形状モデルを視覚的に出力する出力手段とを
備えることを特徴とする処理装置。
【請求項６】コンピュータのためのプログラムを記録
した記録媒体であって、与えられた問題を表す形状モデルを生成するステップ
と、前記形状モデルを変形するステップと、変形された形状モデルを視覚的に出力するステップとを
含む処理を前記コンピュータに実行させるためのプログ
ラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項７】与えられた問題を形状モデルに変換し、前記形状モデルを変形して、コスト値の良好な形状モデ
ルを求め、変形された形状モデルを視覚的に表現することを特徴と
する処理方法。