著者北山哲士, 山崎光悦

(1)

一般化ランダム・トンネリング・アルゴリズムによる大域的最適化（第２報解の精度とその効率に関する検討）

著者北山哲士, 山崎光悦

雑誌名日本機械学会論文集Ａ編

巻 70

号 689

ページ 50‑55

発行年 2004‑01‑01

URL http://hdl.handle.net/2297/2267

(2)

＊

＊原稿受付平成？？年？？月日原稿受付平成？？年？？月日

＊１

＊１正員，金沢大学工学部（〒正員，金沢大学工学部（〒920‑8667 920‑8667 金沢市小立野金沢市小立野2‑40‑202‑40‑20））..

In constrained optimization problems, many heuristic methods treat constraint functions as penalty In constrained optimization problems, many heuristic methods treat constraint functions as penalty function, and it is well known that penalty parameters depend on the problems. Generalized Random function, and it is well known that penalty parameters depend on the problems. Generalized Random Tunneling Algorithm(GRTA) for global optimization has been proposed in the first report. GRTA does Tunneling Algorithm(GRTA) for global optimization has been proposed in the first report. GRTA does not need penalty parameters, and is a simple method. In this paper

not need penalty parameters, and is a simple method. In this paper t the accuracy of solutions and thehe accuracy of solutions and the efficiency between GRTA and heuristic methods are discussed through numerical examples. In numeri- efficiency between GRTA and heuristic methods are discussed through numerical examples. In numerical examples, some mathematical problems and structural optimization problem are treated. In case of cal examples, some mathematical problems and structural optimization problem are treated. In case of mathematical problems, there are little differences of the accuracy of solution and the results between mathematical problems, there are little differences of the accuracy of solution and the results between GRTA and heuristic methods. However, the efficiency of GRTA is excelent to find global minimum.

GRTA and heuristic methods. However, the efficiency of GRTA is excelent to find global minimum.

Moreover there is big difference of the result in case of structural optimization problem. As a result, the Moreover there is big difference of the result in case of structural optimization problem. As a result, the validity and efficiency of GRTA are confirmed.

validity and efficiency of GRTA are confirmed.

Satoshi KITAYAMA and Koetsu YAMAZAKI Satoshi KITAYAMA and Koetsu YAMAZAKI

Department of Human & Mechanical Systems Engineering, Kanazawa University Department of Human & Mechanical Systems Engineering, Kanazawa University

2-40-20, Kodatsuno, Kanazawa, Ishikawa, 920-8667, Japan 2-40-20, Kodatsuno, Kanazawa, Ishikawa, 920-8667, Japan

Global Optimization by Generalized Random Tunneling Algorithm Global Optimization by Generalized Random Tunneling Algorithm

(2nd Report: Examination on the accuracy of solution and its efficiency) (2nd Report: Examination on the accuracy of solution and its efficiency)

北山哲士

北山哲士山崎光悦山崎光悦

一般化ランダム・トンネリング・アルゴリズムによる大域的最適化一般化ランダム・トンネリング・アルゴリズムによる大域的最適化一般化ランダム・トンネリング・アルゴリズムによる大域的最適化一般化ランダム・トンネリング・アルゴリズムによる大域的最適化一般化ランダム・トンネリング・アルゴリズムによる大域的最適化一般化ランダム・トンネリング・アルゴリズムによる大域的最適化一般化ランダム・トンネリング・アルゴリズムによる大域的最適化一般化ランダム・トンネリング・アルゴリズムによる大域的最適化

（第２報解の精度とその効率に関する検討）

（第２報解の精度とその効率に関する検討）（第２報解の精度とその効率に関する検討）

（第２報解の精度とその効率に関する検討）

Key Words

Key Words : : Optimum Design, Structural Analysis, Numerical Analysis, Global Optimization, TunnelingOptimum Design, Structural Analysis, Numerical Analysis, Global Optimization, Tunneling Algorithm.

Algorithm.

1 1 1 1 1 1 1 1 緒言緒言緒言緒言緒言緒言緒言緒言

側面制約条件の下で目的関数の大域的最適解を求め側面制約条件の下で目的関数の大域的最適解を求める手法は古くから提案されている．しかし多くの提案る手法は古くから提案されている．しかし多くの提案されている手法で解かれた問題は，簡単な側面制約条されている手法で解かれた問題は，簡単な側面制約条件のみで実行可能領域が構成されており，また設計変件のみで実行可能領域が構成されており，また設計変数も２〜５ぐらいまでの比較的小規模な問題が多い．

数も２〜５ぐらいまでの比較的小規模な問題が多い．

さらに，非線形性の強い不等式制約条件が存在する場さらに，非線形性の強い不等式制約条件が存在する場合，ペナルティ関数を作成することにより，事実上の合，ペナルティ関数を作成することにより，事実上の無制約最適化問題に変換し，大域的最適解を求めてい無制約最適化問題に変換し，大域的最適解を求めていた．しかしペナルティ係数は対象とする問題に大きくた．しかしペナルティ係数は対象とする問題に大きく依存すること，制約条件上の解を厳密には求められな依存すること，制約条件上の解を厳密には求められな

(1) (1)

いなど，問題点も存在する．いなど，問題点も存在する．

そこで筆者らは目的関数と側面制約条件

そこで筆者らは目的関数と側面制約条件,, および不および不等式制約条件から構成される連続変数の最適化問題に等式制約条件から構成される連続変数の最適化問題における大域的最適解を求める手法の一つとして，一般おける大域的最適解を求める手法の一つとして，一般化ランダム・トンネリング・アルゴリズム（以下，化ランダム・トンネリング・アルゴリズム（以下，

(2) (2)

GRTA

GRTAと称する．）を提案した．と称する．）を提案した．GRTAGRTAは数理計画法とは数理計画法とヒューリスティックな方法の特徴を組み合せた方法でヒューリスティックな方法の特徴を組み合せた方法であり，下記の３つのステップから構成されている．

あり，下記の３つのステップから構成されている．

（

（1 . 11 . 1 ）最小化ステップ・・・局所的最適解を数理計）最小化ステップ・・・局所的最適解を数理計

画法を用いて求めるステップ．

（

（1 . 21 . 2 ）トンネル・ステップ・・・最小化ステップで）トンネル・ステップ・・・最小化ステップで求まった局所的最適解における目的関数値よりも，目求まった局所的最適解における目的関数値よりも，目的関数を改善する設計点を求めるステップ．

的関数を改善する設計点を求めるステップ．

（

（1 . 31 . 3 ）制約ステップ・・・トンネルステップで得ら）制約ステップ・・・トンネルステップで得られた設計点が制約条件を満足しているかどうかを検討れた設計点が制約条件を満足しているかどうかを検討するためのステップ．

するためのステップ．

G R T AG R T A は，この３つのステップを繰り返すことによは，この３つのステップを繰り返すことにより，大域的最適解，もしくはそれに相当する準最適解り，大域的最適解，もしくはそれに相当する準最適解を求めることができる手法である．トンネル・ステッを求めることができる手法である．トンネル・ステッ

(3) (3)

プでは，

プでは，CauthyCauthy分布に基づくタンジェント関数と温分布に基づくタンジェント関数と温度の積を，局所的最適解からの増分として用いること度の積を，局所的最適解からの増分として用いることにより，局所的最適解からの脱出を図った．ある一定により，局所的最適解からの脱出を図った．ある一定回数の探索により，目的関数を改善する新たな設計点回数の探索により，目的関数を改善する新たな設計点が求まらない場合，温度を下げ探索領域を絞り込むこが求まらない場合，温度を下げ探索領域を絞り込むことにより，再び探索を繰り返した．探索の終了条件ととにより，再び探索を繰り返した．探索の終了条件として，最小温度を設定し，その最小温度以下になったして，最小温度を設定し，その最小温度以下になった場合に，探索を終了とした．

場合に，探索を終了とした．GRTAGRTAの特徴は，最終的にの特徴は，最終的に得られる解が常に，最小化ステップで得られた解であ得られる解が常に，最小化ステップで得られた解であるため，

るため，Kuhn‑TuckerKuhn‑Tucker条件で探索が終了し，最適性が条件で探索が終了し，最適性が保証された点が得られることである．さらに最小化ス保証された点が得られることである．さらに最小化ステップで数理計画法，特に制約条件を陽に扱う方法をテップで数理計画法，特に制約条件を陽に扱う方法を用いているため，ペナルティ法に比べる制約条件上の用いているため，ペナルティ法に比べる制約条件上の

(3)

最適解が容易に見つかりやすい．つまり，

最適解が容易に見つかりやすい．つまり，GRTAGRTAではペではペナルティ係数の設定は必要ない．また初期に必要となナルティ係数の設定は必要ない．また初期に必要となるデータは，設計変数の初期値，初期温度，トンネルるデータは，設計変数の初期値，初期温度，トンネルステップにおける最大探索回数，そして探索終了のたステップにおける最大探索回数，そして探索終了のための最小温度と，入力データが非常に少ないことであめの最小温度と，入力データが非常に少ないことである．

る．

一方，離散変数および連続変数の最適化問題に対し一方，離散変数および連続変数の最適化問題に対しては，遺伝的アルゴリズム（

ては，遺伝的アルゴリズム（ G A )G A ) やシミュレーテッやシミュレーテッ

(4) (4)

ド・アニーリング（

ド・アニーリング（SASA）など，大域的最適解，もし）など，大域的最適解，もしくはそれに相当する準最適解を求める手法がいくつかくはそれに相当する準最適解を求める手法がいくつか存在し，その有効性は広く知られている．しかし，探存在し，その有効性は広く知られている．しかし，探索終了条件としては，一定の探索回数で探索を終了し索終了条件としては，一定の探索回数で探索を終了したり，設定した最小温度以下となった場合に探索を終たり，設定した最小温度以下となった場合に探索を終了したり，または目的関数の改善が一定期間なくなっ了したり，または目的関数の改善が一定期間なくなった場合に終了する，といったものが主であり，得られた場合に終了する，といったものが主であり，得られた解の最適性までは保証されていない．

た解の最適性までは保証されていない．

GAGAは初期点を設計空間内にランダムに発生させ，多は初期点を設計空間内にランダムに発生させ，多点同時探索を行うことにより，個体間の解の多様性を点同時探索を行うことにより，個体間の解の多様性を維持しつつ，大域的最適解，もしくは準最適解を求め維持しつつ，大域的最適解，もしくは準最適解を求める手法である．一方

る手法である．一方SASAは設計空間内に１つの初期点をは設計空間内に１つの初期点を設定する．探索点は確率的に目的関数を改悪する点を設定する．探索点は確率的に目的関数を改悪する点を許容しながら大域的最適解，もしくは準最適解を求め許容しながら大域的最適解，もしくは準最適解を求める方法であるが，局所的最適解からの脱出には確率的る方法であるが，局所的最適解からの脱出には確率的な方法を用いることなど，比較的

な方法を用いることなど，比較的G R T AG R T A と共通点も多と共通点も多い．

い．

そこで本報では，

そこで本報では，G R T AG R T A により得られた解と，により得られた解と，S AS A にによって得られた解やその効率，探索過程などについてよって得られた解やその効率，探索過程などについて検討し，

検討し，GRTAGRTAの有効性を検討する．の有効性を検討する．

2 2 2 2 2 2 2

2 一般化ランダム・トンネリング・一般化ランダム・トンネリング・一般化ランダム・トンネリング・一般化ランダム・トンネリング・一般化ランダム・トンネリング・一般化ランダム・トンネリング・一般化ランダム・トンネリング・一般化ランダム・トンネリング・

アルゴリズム（

アルゴリズム（アルゴリズム（

アルゴリズム（G R T A ) G R T A ) G R T A ) G R T A ) G R T A ) G R T A ) G R T A ) G R T A )

連続変数の最適化問題は一般に次のように書くこと連続変数の最適化問題は一般に次のように書くことができる．

ができる．

Find x=(x x1, 2,",x_n)^T (1)(1)

Such as ^f( )^x ^→^min ⁽²⁾⁽²⁾

Subject to

L≤ ≤ U

x x x (3)(3)

( ) ⁰

gj x ≤ j=1,",m (4)(4)

ここで

ここでx は設計変数ベクトルであり，は設計変数ベクトルであり，x^U ，，x^Lは設計は設計変数ベクトルの上下限値であり，側面制約と呼ばれ変数ベクトルの上下限値であり，側面制約と呼ばれる．また

る．また^f( )^x は多峰性を許容する目的関数である．は多峰性を許容する目的関数である．

( )

gj x は不等式制約条件を表し，は不等式制約条件を表し，mは不等式制約条件は不等式制約条件の数である．前報で提案した

の数である．前報で提案したGRTAGRTAの流れを要約するとの流れを要約すると

(2) (2)

次のようである．次のようである．最小化ステップ最小化ステップ最小化ステップ最小化ステップ最小化ステップ最小化ステップ最小化ステップ最小化ステップ (Step1)

(Step1)実行可能領域に適当な初期点実行可能領域に適当な初期点x₀を取る．を取る．

(Step2)

(Step2)数理計画法を用いて，局所的最適点数理計画法を用いて，局所的最適点x_L^*を求めを求める．

る．

トンネルステップトンネルステップトンネルステップトンネルステップトンネルステップトンネルステップトンネルステップトンネルステップ ( St ep 3)

( St ep 3) 初期温度初期温度T₀を設定する．トンネル・ステップを設定する．トンネル・ステップおよび制約ステップにおける探索回数

および制約ステップにおける探索回数it out, をそれぞをそれぞれ初期化する．

れ初期化する．k=0とする．とする．

(Step4)

(Step4)各設計変数ごとに各設計変数ごとに[0,1][0,1]の乱数を発生させ，その乱数を発生させ，それを

れを(−π π^2, ²)に変換し，に変換し，P_iとする．とする．

(Step5) (Step5)

( )

^*^L

f x ≤ f x (5)(5)

となる点を次式を用いて探索する．

*

x = x +L δx (6)(6)

i tan i

x T P

δ = (7)(7)

ここで

ここでδxは局所的最適解は局所的最適解x_L^*からの増分である．からの増分である．

(Step6)

(Step6)式式(5)(5)を満足する場合，局所的最適解よりも深を満足する場合，局所的最適解よりも深い谷が見つかったことになるので，制約条件をチェッい谷が見つかったことになるので，制約条件をチェックするために，制約ステップへいく．そうでなければクするために，制約ステップへいく．そうでなければ Step7

Step7へいく．へいく．

( S t e p 7 )

( S t e p 7 ) トンネルステップにおける探索回数が，あらトンネルステップにおける探索回数が，あらかじめ決められた最大探索回数（

かじめ決められた最大探索回数（it_max）を超えた場合）を超えた場合は

は，， S t e p 8S t e p 8 へ行く．最大探索回数以下の場合は，へ行く．最大探索回数以下の場合は， 1

it= +it としてとしてStep4Step4へ戻る．へ戻る．

(Step8)

(Step8)k= +k 1として，次の式で定めるスケジューリとして，次の式で定めるスケジューリングにより，温度を下げる．

ングにより，温度を下げる．

( 1)

T =T k+ (8)(8)

(Step9)

(Step9)温度があらかじめ決められた最小温度温度があらかじめ決められた最小温度T_minよりよりも大きい場合は，

も大きい場合は，Step8Step8で得られた温度のまま，で得られた温度のまま，Step4Step4 へ行く．小さい場合は，最小化ステップで得られた解へ行く．小さい場合は，最小化ステップで得られた解を大域的最適解として終了する．

を大域的最適解として終了する．

制約ステップ制約ステップ制約ステップ制約ステップ制約ステップ制約ステップ制約ステップ制約ステップ (Step10)

(Step10)すべての制約条件を満足したかどうかを検討すべての制約条件を満足したかどうかを検討する．すべての制約条件を満足している場合は，得らする．すべての制約条件を満足している場合は，得られた点を初期点として最小化ステップへ戻り，再び数れた点を初期点として最小化ステップへ戻り，再び数理計画法によって局所的最適解を求める．制約条件を理計画法によって局所的最適解を求める．制約条件を満足していなければ，

満足していなければ，Step11Step11へ行く．へ行く．

(Step11)

(Step11)式（式（55）を満足する）を満足するxは制約条件の外にあるとは制約条件の外にあると考えられるため，

考えられるため，

1

out=out+ (9)(9)

として，

として，Step12Step12へいく．へいく．

(Step12)

(Step12)次の式で定めるスケジューリングにより，温次の式で定めるスケジューリングにより，温度を下げ，

度を下げ，Step13Step13へいく．へいく．

( 1)

T =T out+ （（1010））

(Step13)

(Step13)温度があらかじめ決められた最小温度温度があらかじめ決められた最小温度T_minよよりも大きい場合は

りも大きい場合はS t e p 6S t e p 6 へ行く．そうでなければ，へ行く．そうでなければ，

Step3

Step3へ行く．へ行く．

(4)

GRTAGRTAは上記の最小化ステップ，トンネルステップ，は上記の最小化ステップ，トンネルステップ，

制約ステップを繰り返すことにより大域的最適解，も制約ステップを繰り返すことにより大域的最適解，もしくはそれに相当する準最適解を見つける方法であしくはそれに相当する準最適解を見つける方法である．

る．

3 33 33 33

3 比較する方法と問題設定比較する方法と問題設定比較する方法と問題設定比較する方法と問題設定比較する方法と問題設定比較する方法と問題設定比較する方法と問題設定比較する方法と問題設定

GRTAGRTAととSASAによって得られた解やその効率について比によって得られた解やその効率について比較，検討する．局所的最適解からの脱出に確率的な方較，検討する．局所的最適解からの脱出に確率的な方法を用いているため，１回で効率の優劣を言及するこ法を用いているため，１回で効率の優劣を言及することは難しいと考え，２０回の計算を実行する．また異とは難しいと考え，２０回の計算を実行する．また異なる初期値から大域的最適解を探索して結果を評価すなる初期値から大域的最適解を探索して結果を評価する．

る．

3 . 13 . 13 . 13 . 13 . 1 比較する方法 3 . 13 . 13 . 1 比較する方法比較する方法比較する方法比較する方法比較する方法比較する方法比較する方法比較，検討する方法としては比較，検討する方法としては様々な方法が考えられるが，本研究では下記の３つの様々な方法が考えられるが，本研究では下記の３つの項目について比較，検討する．

項目について比較，検討する．

（

（3 . 13 . 1 ））2 02 0 回計算を実行し，大域的最適解に到達した回計算を実行し，大域的最適解に到達した割合．

割合．

（

（3 . 23 . 2 ）目的関数の改善がなくなるまでに必要とした）目的関数の改善がなくなるまでに必要とした探索回数の平均値．

探索回数の平均値．

（

（3 . 33 . 3 ）目的関数の改善がなくなるまでに必要とした）目的関数の改善がなくなるまでに必要とした関数の呼び出し回数の平均値．

関数の呼び出し回数の平均値．

（

（3 . 13 . 1 ）項は解の精度，（）項は解の精度，（3 . 23 . 2 ）と（）と（3 . 33 . 3 ）項に関して）項に関しては，アルゴリズムの効率を検討する主要な項目であるは，アルゴリズムの効率を検討する主要な項目であると考えた．

と考えた．

3 . 23 . 23 . 23 . 23 . 2 比較する問題3 . 23 . 23 . 2 比較する問題比較する問題比較する問題比較する問題比較する問題としては多峰性比較する問題比較する問題比較する問題比較する問題としては多峰性を有する数学問題および構造最適設計問題を考える．

を有する数学問題および構造最適設計問題を考える．

数学問題としては，１〜２変数から構成される簡単な数学問題としては，１〜２変数から構成される簡単な無制約最適化問題と有制約最適化問題を考える．一無制約最適化問題と有制約最適化問題を考える．一方，構造最適化問題としては，前報で示した変位制約方，構造最適化問題としては，前報で示した変位制約条件の下で，体積を最小にするようなトラス構造の最条件の下で，体積を最小にするようなトラス構造の最適位相問題を考えることにする．

適位相問題を考えることにする．

4 44 44 44

4 数値計算結果数値計算結果数値計算結果数値計算結果数値計算結果数値計算結果数値計算結果数値計算結果

4 . 14 . 14 . 14 . 14 . 1 数学問題4 . 14 . 14 . 1 数学問題数学問題数学問題数学問題数学問題数学問題数学問題 GR TAGR TA ととSASA で共通に必要となる初期で共通に必要となる初期入力データとして下記のものを用いた．

入力データとして下記のものを用いた．

(a)

(a)初期温度初期温度 T₀=1.00 (b)

(b)探索終了のための最小温度探索終了のための最小温度 T_min=1.00 10× ⁻⁵ また

またGRTAGRTAにおいて必要となるトンネル・ステップににおいて必要となるトンネル・ステップにおける最大探索回数を

おける最大探索回数をit_max=20とした．一方，とした．一方，SASAにおにおいて一つの温度当たりの最大探索回数を，無制約最適いて一つの温度当たりの最大探索回数を，無制約最適化問題においては

化問題においては2020回とし，有制約最適化問題におい回とし，有制約最適化問題においては

ては100100回とした．さらに温度スケジューリングには回とした．さらに温度スケジューリングには

T=cT (11)(11)

を用い，式（

を用い，式（1111）の係数）の係数c^を^をc=0.85とした．またとした．またGRTAGRTA では最小化ステップにおいて，無制約最適化問題の場では最小化ステップにおいて，無制約最適化問題の場合では，準ニュートン法を，有制約最適化問題の場合合では，準ニュートン法を，有制約最適化問題の場合

では，最小化ステップで逐次二次計画法を用いた．

なお表中の

なお表中のGRTAGRTAは一般化ランダム・トンネリング・は一般化ランダム・トンネリング・

アルゴリズムの結果を示し，

アルゴリズムの結果を示し，SASAはシミュレーテッド・はシミュレーテッド・

アニーリングを適用した結果を示す．また

アニーリングを適用した結果を示す．またS I AS I A は目的は目的関数の改善がなくなるまでに必要とした探索回数の平関数の改善がなくなるまでに必要とした探索回数の平均値，

均値，F C AF C A は目的関数の改善がなくなるまでに必要とは目的関数の改善がなくなるまでに必要とした関数の呼び出し回数の平均値を示す．さらにした関数の呼び出し回数の平均値を示す．さらにn回回目の目的関数値

目の目的関数値 f_nととn+1回目の目的関数値回目の目的関数値 f_n₊₁の相対の相対誤差

誤差eをを

1

n n

n

f f

e f

+ −

=

とし，相対誤差が１％以下となる探索回数が

とし，相対誤差が１％以下となる探索回数が4040回以上回以上続いた場合，目的関数の更新がないと判断し，得られ続いた場合，目的関数の更新がないと判断し，得られた解を最適解とした．

た解を最適解とした．

テスト問題１テスト問題１テスト問題１テスト問題１テスト問題１次に示す１変数から成る無制約最適テスト問題１テスト問題１テスト問題１次に示す１変数から成る無制約最適

(5) (5)

化問題の大域的最適解を求める．化問題の大域的最適解を求める．

( ) ¹⁰ ⁵

(

² ²

)

^x² ^min

f x = x × x − e⁻ → (12)(12)

4 x 3

− ≤ ≤ (13)(13)

この関数と大域的最適解を図１に示す．大域的最適解この関数と大域的最適解を図１に示す．大域的最適解は

はx= −2.085 でその時の目的関数値はでその時の目的関数値は f = −11.970 であである．初期点及び比較項目（

る．初期点及び比較項目（3.13.1）〜（）〜（3.33.3）までを表１）までを表１に示す．

に示す．

テスト問題テスト問題テスト問題テスト問題テスト問題テスト問題テスト問題テスト問題 22222222 次に示す１変数から成る無制約最適次に示す１変数から成る無制約最適

(6) (6)

化問題の大域的最適解を求める．化問題の大域的最適解を求める．

5 ( )

1

( ) cos 1 min

i

f x i i x i

=

∑

 + + → ⁽¹⁴⁾⁽¹⁴⁾

0≤ ≤x 7.5 (15)(15)

この関数と大域的最適解を図

この関数と大域的最適解を図22 に示す．大域的最適解に示す．大域的最適解は

はx=4.858 でその時の目的関数値はでその時の目的関数値は f = −12.871 であである．また初期点及び比較項目（

る．また初期点及び比較項目（3.13.1）〜（）〜（3.33.3）までを）までを表

表22に示す．に示す．

2.25 62.5

2 34

186 371

330 660

1.50

2.50

Initial point Ratio of achievement SIA FCA GRTA

SA GRTA

SA

100%

Table 1 Comparison between GRTA and SA of example 1 Table 1 Comparison between GRTA and SA of example 1 Fig.1 Function and global minimum of example 1 Fig.1 Function and global minimum of example 1

-4 -3 -2 -1 1 2 3

-10 -5 5 10

Global minimum

-4 -3 -2 -1 1 2 3

-10 -5 5 10

-4 -3 -2 -1 1 2 3

-10 -5 5 10

Global minimum

(5)

テスト問題テスト問題テスト問題テスト問題テスト問題 3テスト問題テスト問題テスト問題3333333 次に示す２変数１制約条件から成る次に示す２変数１制約条件から成る

(7) (7)

有制約最適化問題の大域的最適解を求める．有制約最適化問題の大域的最適解を求める．

( ) ²

(

⁴ ²

)

1

1 16 5 min

2_i ⁱ ⁱ ⁱ

f x x x

=

∑

− + →

x （（1616））

( ) ² ²

1 1 2 9 0

g x =x +x − ≤ （（1717））

この関数と大域的最適解を図

この関数と大域的最適解を図33 に示す．制約条件が存に示す．制約条件が存在するため，

在するため，SASAにおいては，制約条件上の最適解を比においては，制約条件上の最適解を比

(8) (8)

較的見つけやすい精密ペナルティ法を用い，そのと較的見つけやすい精密ペナルティ法を用い，そのときのペナルティ係数を

きのペナルティ係数をr=1000r=1000とした．大域的最適解はとした．大域的最適解は

(x x1, 2) (^T= −2.121, 2.121− )^Tであり，その時の目的関数値であり，その時の目的関数値は

はf = −62.355である．比較項目（である．比較項目（3.13.1）〜（）〜（3.33.3）を表）を表 3

3に示す．に示す．

テスト問題テスト問題テスト問題テスト問題テスト問題 4テスト問題テスト問題テスト問題4444444 次に示す２変数２制約条件から成る次に示す２変数２制約条件から成る有制約最適化問題の大域的最適解を求める．

有制約最適化問題の大域的最適解を求める．

( ) 1 2 min

f x = − − →x x （（1818））

( ) ⁴ ³ ²

1 2 2 1 8 1 8 1 2 0

g x = − − x + x − x +x ≤ （（1919））

( ) ⁴ ³ ²

2 36 4 1 32 1 88 1 96 1 2 0

g x = − − x + x − x + x +x ≤ (20)(20) 0≤ ≤x1 3, , 0≤x₂≤4 (21)(21) この関数と局所的最適解および大域的最適解を図この関数と局所的最適解および大域的最適解を図44 にに示す．大域的最適解は

示す．大域的最適解は(x x1, 2) (^T = 2.329,3.178)^Tであり，であり，

その時の目的関数値は

その時の目的関数値は f = −5.508 である．また比較項である．また比較項目（

目（3.13.1）〜（）〜（3.33.3）を表）を表44に示す．に示す．

(9) (9)

4 . 34 . 34 . 34 . 34 . 3 構造最適化問題4 . 34 . 34 . 3 構造最適化問題構造最適化問題構造最適化問題構造最適化問題変位制約条件の下でトラ構造最適化問題構造最適化問題構造最適化問題変位制約条件の下でトラス構造物の体積を最小にするような最適位相を求めス構造物の体積を最小にするような最適位相を求める．問題の詳細は文献（

る．問題の詳細は文献（22）を参照されたい．）を参照されたい．

GRTAGRTAととSASAで共通に必要となる初期入力データは数学で共通に必要となる初期入力データは数学問題と同じ値を用いた．また

問題と同じ値を用いた．またSASAにおいて一つの温度当において一つの温度当たりの最大探索回数を

たりの最大探索回数を10001000回，回，1000010000回の二つとした．回の二つとした．

さらに精密ペナルティ法を用い，ペナルティパラメーさらに精密ペナルティ法を用い，ペナルティパラメータは

タはr=1.00 10× ⁷とした．とした．

探索初期値をすべ

探索初期値をすべA₀=5.00 10 [× ² mm²]として，として，G R T AG R T A で得られたトラス構造の最適位相と，

で得られたトラス構造の最適位相と，SASAで得られた最で得られた最適位相を目的関数である体積値とともに表

適位相を目的関数である体積値とともに表55 に示す．に示す．

なお

なおSASAの結果は乱数の種を変え，それぞれ２０回計算の結果は乱数の種を変え，それぞれ２０回計算を行った結果得られた最良のものを示している．

を行った結果得られた最良のものを示している．

6 6 6 6 6 探索過程に関する検討 6 6 6 探索過程に関する検討探索過程に関する検討探索過程に関する検討探索過程に関する検討探索過程に関する検討探索過程に関する検討探索過程に関する検討

第

第 55 章において，いくつかの数値計算例を通じて章において，いくつかの数値計算例を通じて G R T A

G R T A ととS AS A の探索効率に関して検討を行った．本章での探索効率に関して検討を行った．本章では，

は，GRTAGRTAととSASAの探索点の移動戦略と探索過程に関しての探索点の移動戦略と探索過程に関して考察を行う．

考察を行う．

Table 4 Comparison between GRTA and SA of example 4 Table 4 Comparison between GRTA and SA of example 4

(x x1, 2) (^T = 0.50,1.00)^T (x x1, 2) (^T = 1.65, 2.00)^T

66.1 1104.6

29.3 483.9 6574 13518

6345 13075 Initial point Ratio of achievement SIA FCA GRTA

SA GRTA

SA

100%

Fig.2 Function and global minimum of example 2 Fig.2 Function and global minimum of example 2

1 2 3 4 5 6 7

-10 -5 5 10 15

Global Minimum

1 2 3 4 5 6 7

-10 -5 5 10 15

Global Minimum

480 54.5

51.6 242

257 513

3.16

2.33

6.00 2.00

SA GRTA

SA

100%

( )

1 0

g x ≤

-4 -2 0 2 4

x1 x2

Global minimum

-4 -2 0 2 4

x1 x2

Global minimum

Fig.3 Contour of functions and Fig.3 Contour of functions and global minimum of example 3 global minimum of example 3

24.1 532.3

17.0 371.4 2670 5410

2946 5925

1 2

( ,x x )^T =(1.00, 0.50)^T

1 2

( ,x x )^T = −( 1.00,1.50)^T

SA GRTA

SA

100%

Fig.4 Contour of functions and Fig.4 Contour of functions and global minimum of example 4 global minimum of example 4

0 0.5 1 1.5 2 2.5 3

0.5 1 1.5 2 2.5 3 3.5

4 Global minimum

Local minimum

Local minimum A

B C

( )

1 0

g x <

( )

2 0

g x <

( )

1 0

g x <

( )

2 0

g x <

x1

x2

Search Regions

0 0.5 1 1.5 2 2.5 3

0.5 1 1.5 2 2.5 3 3.5

4 Global minimum

Local minimum

Local minimum A

B C

( )

1 0

g x <

( )

2 0

g x <

( )

1 0

g x <

( )

2 0

g x <

x1

x2

Search Regions

(6)

6 . 1 6 . 1 6 . 1 6 . 1 6 . 1 6 . 1 6 . 1

6 . 1 移動戦略移動戦略移動戦略移動戦略移動戦略移動戦略移動戦略移動戦略 S AS A などのメタ・ヒューリスティッなどのメタ・ヒューリスティックスと呼ばれる方法は，

クスと呼ばれる方法は，POPPOP（（Proximate OptimalityProximate Optimality Principle

Principle）の概念に基づき，局所的最適解の近傍を探）の概念に基づき，局所的最適解の近傍を探索を行いながら，大域的最適解，もしくはそれに相当索を行いながら，大域的最適解，もしくはそれに相当する準最適解を見つける方法である．一方，

する準最適解を見つける方法である．一方，GRTAGRTAはは目目的関数値を改善する点をランダムに選び，探索を行的関数値を改善する点をランダムに選び，探索を行う．つまり局所的最適解の近傍や離れた領域をランダう．つまり局所的最適解の近傍や離れた領域をランダムに探索し，目的関数値を改善する点を見つける．ムに探索し，目的関数値を改善する点を見つける． GRTA

GRTAととSASAを比較すれば，を比較すれば，GRTAGRTAの移動戦略は以下の点にの移動戦略は以下の点に特徴がある．

特徴がある．

１）局所的最適解からジャンプする．つまり実行可能１）局所的最適解からジャンプする．つまり実行可能領域が離れていてもある程度の探索は可能．

領域が離れていてもある程度の探索は可能．

２）目的関数値を改悪する点は考慮しない．

３）ランダムに探索点を選ぶため，局所的最適解の近３）ランダムに探索点を選ぶため，局所的最適解の近傍の探索も可能．

傍の探索も可能．

特に上記１）の実行可能領域が離れている場合，

特に上記１）の実行可能領域が離れている場合，SASA でも最適解の探索は可能である．しかし

でも最適解の探索は可能である．しかしSASA で探索するで探索する場合，離れた領域ごとに適したペナルティパラメータ場合，離れた領域ごとに適したペナルティパラメータが必要となるが，このペナルティパラメータの決定はが必要となるが，このペナルティパラメータの決定は

一般に難しく，ペナルティパラメータを必要としない一般に難しく，ペナルティパラメータを必要としない GRTA

GRTAのほうが有利であると考える．のほうが有利であると考える．

6 . 2 6 . 2 6 . 2 6 . 2 6 . 2 6 . 2 6 . 2

6 . 2 探索過程探索過程探索過程探索過程探索過程探索過程探索過程探索過程 G R T AG R T A ととS AS A の探索過程を模擬的に示の探索過程を模擬的に示すならば，例えば図

すならば，例えば図55のようになる．のようになる．

テスト問題

テスト問題11 に関しては，少なくとも極大値を１つに関しては，少なくとも極大値を１つ乗り越えれば大域的最適解に到達することが可能であ乗り越えれば大域的最適解に到達することが可能であるが，テスト問題２では，初期点に依存するものの，

るが，テスト問題２では，初期点に依存するものの，

いくつかの極大値を乗り越えなければ大域的最適解がいくつかの極大値を乗り越えなければ大域的最適解が得られず，近傍探索という

得られず，近傍探索というSASA の移動戦略を考えれば，の移動戦略を考えれば，

テスト問題

テスト問題22はテスト問題はテスト問題11に比べ，に比べ，SASAでは大域的最適では大域的最適解を見つけるまでには多くの探索回数を必要とするこ解を見つけるまでには多くの探索回数を必要とすることを意味する．一方，

とを意味する．一方，G R T AG R T A では，局所的最適解からでは，局所的最適解からジャンプすることにより目的関数を改善する点を見つジャンプすることにより目的関数を改善する点を見つけるため，

けるため，SASAほど多くの探索回数を必要とせず，数値ほど多くの探索回数を必要とせず，数値計算の結果からも

計算の結果からもGRTAGRTAの特徴が出ている．の特徴が出ている．

テスト問題

テスト問題3 , 43 , 4 では制約条件をペナルティ関数としでは制約条件をペナルティ関数とし Search process of GRTA

Search process of SA

Search process of GRTA Search process of SA

Fig.5 Difference of search process Fig.5 Difference of search process Optimum topology

Optimum topology ^Iteration^Iteration F C F C

GRTA GRTA

SA SA (1000) (1000)

SA SA (10000) (10000)

5

2144

70929

142801

709929

1420912 260

103

515 362

102

87

360

254

5 3

2.35 10 [ ] f = × mm

Table 5 Comparison of optimum topologies Table 5 Comparison of optimum topologies

280

83 131 155

99

165 ¹⁵⁴ ⁷¹

413

58 381 211

5 3

2.47 10 [ ] f = × mm

127 225 172

84

115

55 474

75

247

109 157

108 256

5 3

2.60 10 [ ] f = × mm

Fig.6 Search process of SA (example 3) Fig.6 Search process of SA (example 3)

-4 -2 0 2 4

Initial point

Global minimum

-4 -2 0 2 4

Initial point

Global minimum

Fig.7 Search process of SA (example 4) Fig.7 Search process of SA (example 4)

0 0.5 1 1.5 2 2.5 3

0 1 2 3 4

Initial Point A

B

C

0 0.5 1 1.5 2 2.5 3

0 1 2 3 4

Initial Point A

0 0.5 1 1.5 2 2.5 3

0 1 2 3 4

0 0.5 1 1.5 2 2.5 3

0 1 2 3 4

0 0.5 1 1.5 2 2.5 3

0 1 2 3 4

0 0.5 1 1.5 2 2.5 3

0 1 2 3 4

Initial Point A

B

C

(7)

て拡大目的関数を作成して最適解を求めている．図て拡大目的関数を作成して最適解を求めている．図66 にテスト問題

にテスト問題33 の等高線と探索過程を，図の等高線と探索過程を，図77 にテスト問にテスト問題

題44の等高線と探索過程を示す．の等高線と探索過程を示す．

テスト問題

テスト問題33 において，において，S AS A では探索点が実行可能領では探索点が実行可能領域にあれば逐次目的関数を改善する点を探しながら，

域にあれば逐次目的関数を改善する点を探しながら，

探索を行うが，実行可能領域外に探索点が行った場探索を行うが，実行可能領域外に探索点が行った場合，非常に大きなペナルティが課せられ，探索点は図合，非常に大きなペナルティが課せられ，探索点は図 6

6 に示すように制約条件上を這うように探索を続け，に示すように制約条件上を這うように探索を続け，

大域的最適解を見つける．探索点が近傍を逐次探索す大域的最適解を見つける．探索点が近傍を逐次探索するため，多くの探索回数が必要となる．一方，

るため，多くの探索回数が必要となる．一方，GRTAGRTAででは探索点が局所的最適解からジャンプして，実行可能は探索点が局所的最適解からジャンプして，実行可能領域内の次の出発点を見つけるため，少ない探索回数領域内の次の出発点を見つけるため，少ない探索回数で大域的最適解に到達している．

で大域的最適解に到達している．

テスト問題

テスト問題44 では，では，x=(1.0, 0.0)^Tにおいて実行可能領において実行可能領域が分離している．また，テスト問題

域が分離している．また，テスト問題22 と同様にと同様にS AS A のの探索過程は制約条件上をたどりながら大域的最適解に探索過程は制約条件上をたどりながら大域的最適解に到達しているが，

到達しているが，x=(1.0, 0.0)^T において実行可能領域において実行可能領域が分離しているため，この付近まで探索点が移動しなが分離しているため，この付近まで探索点が移動しなければ，大域的最適解を見つけられない．一方ければ，大域的最適解を見つけられない．一方GRTAGRTAででは局所的最適解である点

は局所的最適解である点AA に探索点が陥った場合，図に探索点が陥った場合，図44 の灰色部分が探索領域となり，局所的最適解である点の灰色部分が探索領域となり，局所的最適解である点 A

A から実行不可能な領域を大きくジャンプして，実行から実行不可能な領域を大きくジャンプして，実行可能領域内の目的関数値を改善する点を見つけ，大域可能領域内の目的関数値を改善する点を見つけ，大域的最適解に到達している．

的最適解に到達している．

挙動制約条件をペナルティ関数として扱う場合，ペ挙動制約条件をペナルティ関数として扱う場合，ペナルティ係数が拡大目的関数に大きく影響するが，多ナルティ係数が拡大目的関数に大きく影響するが，多点探索の場合，目的関数値からペナルティ係数を決定点探索の場合，目的関数値からペナルティ係数を決定

(10) (10)

する方法はあるものの

する方法はあるものの，，S AS A などの一点探索法の場などの一点探索法の場合，多点探索法と比べれば得られる情報は限られ，ペ合，多点探索法と比べれば得られる情報は限られ，ペナルティ係数を探索初期段階で決定するのは困難であナルティ係数を探索初期段階で決定するのは困難である．探索を行う前にペナルティ係数を決定することはる．探索を行う前にペナルティ係数を決定することは難しく，ペナルティ係数を必要としない

難しく，ペナルティ係数を必要としないGRTAGRTAのほうがのほうが有利であると考える．またテスト問題４のような実行有利であると考える．またテスト問題４のような実行可能領域が分離している問題でも，

可能領域が分離している問題でも，GRTAGRTAは少ない探索は少ない探索回数で，大域的最適解もしくはそれに相当する準最適回数で，大域的最適解もしくはそれに相当する準最適解の探索が行えることがわかる．

解の探索が行えることがわかる．

構造最適化問題では，目的関数は線形であるが，制構造最適化問題では，目的関数は線形であるが，制約条件が非線形であるため，設計空間が多峰性の激し約条件が非線形であるため，設計空間が多峰性の激しい問題となり，テスト問題

い問題となり，テスト問題44 のような制約条件の曲面のような制約条件の曲面が凹凸となる設計空間で，探索が行われている．結果が凹凸となる設計空間で，探索が行われている．結果として，

として，SASA では大域的最適解を見つけられなかったとでは大域的最適解を見つけられなかったと考えられる．

考えられる．

7 77 77 77

7 結言結言結言結言結言結言結言結言

提案する手法と

提案する手法とSASAは，ともに局所的最適解からの脱は，ともに局所的最適解からの脱出には確率的な方法を用いているため，簡単にどちら出には確率的な方法を用いているため，簡単にどちら

がよいかを言及することは難しいが，３章で挙げた比がよいかを言及することは難しいが，３章で挙げた比較項目，及び取り上げたいくつかの数値計算例に関し較項目，及び取り上げたいくつかの数値計算例に関しては

てはG R T AG R T A のほうがのほうがS AS A よりも優れていることがわかっよりも優れていることがわかった．

た．GRTAGRTAは初期入力パラメータも少なく，アルゴリズは初期入力パラメータも少なく，アルゴリズム自体も簡単なため，容易に実行できる．

ム自体も簡単なため，容易に実行できる．GRTAGRTAで得らで得られた解の精度やその探索効率に関して数値計算を通じれた解の精度やその探索効率に関して数値計算を通じて検討を行った．数値計算の結果から，

て検討を行った．数値計算の結果から，GRTAGRTAの効率はの効率は SA

SAよりもよく，大域的最適解を得られる．さらによりもよく，大域的最適解を得られる．さらにGRTAGRTA の探索過程は

の探索過程はSASAのように近傍を逐次探索するのではなのように近傍を逐次探索するのではなく，実行可能領域内をジャンプしながら探索するたく，実行可能領域内をジャンプしながら探索するため，実行可能領域が離れていても少ない探索回数で大め，実行可能領域が離れていても少ない探索回数で大域的最適解，もしくはそれに相当する準最適解の探索域的最適解，もしくはそれに相当する準最適解の探索が可能である．

が可能である．

参考文献参考文献参考文献参考文献参考文献参考文献参考文献参考文献

（１）遺伝的アルゴリズム，坂和・田中，（

（１）遺伝的アルゴリズム，坂和・田中，（19971997），），

朝倉書店．

（２）北山・山崎，一般化ランダム・トンネリング・

アルゴリズムによる大域的最適化，（第１報アルゴアルゴリズムによる大域的最適化，（第１報アルゴリズムの提示と数値計算例），機論

リズムの提示と数値計算例），機論AA，，6969696969‑684,(2003)696969‑684,(2003) ,pp.1250‑1256

,pp.1250‑1256．．

（３）

（３）Szu,H. and Hartley,R., Szu,H. and Hartley,R., Fast Simulate An‑Fast Simulate An‑

n e a l i n g

n e a l i n g, P h y s i c s L e t t e r s A , , P h y s i c s L e t t e r s A , V o l . 1 2 2V o l . 1 2 2V o l . 1 2 2V o l . 1 2 2V o l . 1 2 2V o l . 1 2 2V o l . 1 2 2V o l . 1 2 2 ‑ 3 , 4 ,‑ 3 , 4 ,

（

（19871987），）， pp.157‑162. pp.157‑162.

（４）

（４）Kirkpatrick,S.,Gellat,C.D, and Vecchi,M.P.,Kirkpatrick,S.,Gellat,C.D, and Vecchi,M.P., Optimization by Simulated Annealing

Optimization by Simulated Annealing, Science,, Science, 220

220 220 220 220 220 220

220,(1983), pp.671‑680.,(1983), pp.671‑680.

（５）施・萩原・高島，応答曲面法による多峰性問題

（５）施・萩原・高島，応答曲面法による多峰性問題の最適設計法の開発，機論

の最適設計法の開発，機論AA ，，6 56 56 56 56 56 56 56 5 ‑ 6 3 0‑ 6 3 0 ，（，（1 9 9 91 9 9 9 ），），

pp.232‑239.

（６）

（６）Levy,A.V. and Gomez,S., Levy,A.V. and Gomez,S., Numerical Optimi‑Numerical Optimi‑

zation 1984

zation 1984, (1985),pp.213‑244, SIAM., (1985),pp.213‑244, SIAM.

（７）茂中・藤田ほか

（７）茂中・藤田ほか22 名，ダイナミック・トンネリ名，ダイナミック・トンネリング・アルゴリズムの有制約大域的最適化問題への適ング・アルゴリズムの有制約大域的最適化問題への適用，電学論

用，電学論CC，，118118118118118118118118‑11‑11，（，（19981998），），pp.1674‑1675pp.1674‑1675．．

（８）相吉・志水，数理計画法演習，（

（８）相吉・志水，数理計画法演習，（19851985），朝倉），朝倉書店．

書店．

（９）山崎光悦，トンネル法によるトラス構造形態の

（９）山崎光悦，トンネル法によるトラス構造形態の最適化，機講論，

最適化，機講論，No.940‑10, No.940‑10, Ⅳ（Ⅳ（19941994），），pp.339‑pp.339‑

341.

（１０）荒川・萩原，領域遺伝的アルゴリズムの開発

（精度および求解性の向上のためのオペレータの提

（精度および求解性の向上のためのオペレータの提案），機論

案），機論CC，，65‑63865‑638，，(1999), pp.4156‑4163.(1999), pp.4156‑4163.

著者 北山 哲士, 山崎 光悦

一般化ランダム・トンネリング・アルゴリズムによ る大域的最適化（第２報 解の精度とその効率に関 する検討）