分岐による複数の局所最適解の探索） 北山哲士
9
0
0
全文
(2) 一般化ランダム・トンネリング・アルゴリズムによる大域的最適化 ( 第3 報. 分岐による複数の局所最適解の探索） 北山哲士. 山崎光悦. Global Optimization by Generalized Random Tunneling Algorithm (3rd Report: Search of some local minima by branching) Satoshi KITAYAMA and Koetsu YAMAZAKI Department of Human & Mechanical Systems Engineering, Kanazawa University 2-40-20, Kodatsuno, Kanazawa, Ishikawa, 920-8667, Japan This paper presents a method to find some local minima by branching at local minimum, based on the Generalized Random Tunneling Algorithm (GRTA). We call this method as Branching GRTA( BGRTA). BGRTA also consists of three phases, that is, the minimization phase, the tunneling and branching phase, and constraint phase. In the minimization phase, local search technique is used. In the tunneling and branching phase, some local minima can be found by branching at local minimum obtained in the minimization phase. The next branching point is chosen from them. In the constraint phase, the feasibility is examined. We apply BGRTA to the topology optimization problem of truss structure and the traffic road design problem. Through numerical examples, we examine the validity of BGRTA.. Key words: words: Global Optimization, Optimum Design, Branching, Finite Element Method, Topology Optimization, Traffic Road Design B は探索領域外となり，次の出発点となり得ないが，. 1 緒言 側面制約条件と挙動制約条件から構成される連続関. この点を初期点として最適解を探索すれば，点C この点を初期点として最適解を探索すれば，点 C が得 られ，目的関数は改善されていることになる．. 数の大域的最適解，もしくはそれに相当する準最適解. Start point. を求 め る 一 つの 手 法 と して ， 筆 者 ら は一 般 化 ラ ンダ ム・トンネリング・アルゴリズム（以下，G ム・トンネリング・アルゴリズム（以下， G R T A と称. B A. (1). す）を提案した ． GR TA の利点は最適性が保証された 解が得られ，仮に大域的最適解を求めることができな くても，次善の解が得られるといったことが挙げられ. C Local minimum Search region of GRTA. る．さらに入力パラメータも少なく，アルゴリズムも 簡単であるため，容易に実行することができる．. Fig.1 Search region of GRTA. 一方，GRTA 一方， GRTAはいくつかの局所的最適解を見つけるこ はいくつかの局所的最適解を見つけるこ. このため，ランダムに次の出発点を探す場合，一度. とができるが，１点探索法であるため，得られる最適. 得られた点を初期点として，局所的最適解を探索し，. 解は，多点探索を行った場合よりも少なく，より多く. 目的関数の改善を検討する必要があると考えられる．. の解の情報が必要な場合は，Particle の解の情報が必要な場合は， Particle Swarm Optimi‑. さらにGRTA さらに GRTAは一点探索法であったため，より多くの局 は一点探索法であったため，より多くの局. zation や免疫アルゴリズム などの方法のほうが有効. 所的最適解を求めるために，得られた局所的最適解に. であろう．. おいて，分岐させることを考えた．. (2). (3),(4). さらに，GRTA さらに， GRTAは目的関数値のみを用いてランダムに は目的関数値のみを用いてランダムに. そこで本報では，GRTA そこで本報では， GRTAのアルゴリズムをベースにし のアルゴリズムをベースにし. 次の出発点を探していたため，探索領域は例えば図1 次の出発点を探していたため，探索領域は例えば図 1. て，局所的最適解において分岐させ，より多くの局所. のようになっている．図1 のようになっている．図 1 において，局所的最適解 において，局所的最適解A Aが. 的最適解を求めるアルゴリズムを開発する．複数の局. 得られた場合，GRTA 得られた場合， GRTAで次の出発点を見つける場合，点 で次の出発点を見つける場合，点. 所的最適解を見つけることができれば，それだけ多く. ＊. 原稿受付. の情報を提供することができることになり，設計者に. ＊１. 正員，金沢大学工学部（〒920‑8667 正員，金沢大学工学部（〒 920‑8667 金沢市小立野 金沢市小立野2‑40‑20 2‑40‑20） ）.. 平成 ??年 平成?? 年 ?月. 日. とっては，代替案が増えることになり，有効なことで.
(3) あると考える．また得られる複数の局所的最適解の中. と点D と点 D に対してそれぞれ数理計画法を用いて局所的最. にロバスト解が含まれる可能性があること，さらに多. 適解である点C 適解である点 C と点 と点E E を求める．そして点 を求める．そして点C C と点 と点EE の目的. 目的 最 適 化 問題 に お い て， 対 話 的 な 手法 を 用 い る場. 関数値を比較し，目的関数値の良い点E 関数値を比較し，目的関数値の良い点 E が次の分岐点. 合，希求水準の候補になりうるなど，多くの利点を含. となる．分岐点E となる．分岐点 E において，一定の探索回数で，目的. むものと考えられる．さらに目的関数を改善する点を. 関数値を改善する点がみつからなければ，点E 関数値を改善する点がみつからなければ，点 E を最適. ランダムに探しているため，分岐によって生成される. Initial point. 複数の探索点が同じ局所的最適解に陥らないよう，工. B. 夫をする．提案する方法を分岐型一般化ランダム・ト. A Branching point. D. ンネリング・アルゴリズム（Branching ンネリング・アルゴリズム（ Branching GRTA，以下 GRTA ，以下. C. BGRTA）と称する． BGRTA ）と称する．. E Next branching point. はじめに分岐について述べ，B はじめに分岐について述べ， B G R T A のアルゴリズム を示す．そしてB を示す．そして B G R T A を，構造最適化問題と交通路設. Fig.3 Branching at local minimum by BGRTA 解として探索を終了する．. 計問題へ適用する．. ２）ランダムに探索点を見つけているため，一旦，数. 2. 分岐の導入. 理計画法を用いて，局所的最適解を求める．もし，目. 初期点を設定し，数理計画法で局所的最適解 x L が求. 的関数が改善されていれば，その点を次の分岐点の候. まった場合，この局所的最適解 x L において分岐するこ. 補として，保存する．そして，さらに目的関数値を改. とにより，複数の局所的最適解を探索することを考え. 善する点が．最大分岐数 branchmax となるまで，探索を. た．GRTA た． GRTAでは，目的関数値のみを取り扱い，目的関数 では，目的関数値のみを取り扱い，目的関数. 行う．もし同じ最適解が得られた場合は，別の最適解. 値を改善する点が見つかった場合，その点を次の探索. の探索を行う．. 初期点として，逐次最適解を見つけていたが，この方. 最適解が同一であるかどうかを検討するために，探. 法を用いて，つまり目的関数値のみを判断基準として. 索開 始 時 に 次式 を 用 い て， 設 計 変 数 のス ケ ー リ ング. 局所的最適解で分岐させると，図2 局所的最適解で分岐させると，図 2 に示すように，分. （正規化）を行っておく．. 岐した探索点が同じ最適解に陥る可能性が大きく，さ らに複数の最適解は見つかるものの，収束するまでに. Xi =. xi − xi ,min xi ,max − xi ,min. i = 1, 2," , ndv. (1). 非常に多くの時間が必要であることが判った． ここで， xi ,max と xi ,min はそれぞれ，各設計変数の最大 値と最小値であり，これは側面制約条件によって与え られる．また ndv は設計変数の数を表す．最適解の同 一性は，局所的最適解における分岐数 branch が 2 以上 Search region. になったとき，次式によって検討する． Local minimum. X i, j − X i ,branch X i, j. Same local minimum. ≤ε. j = 1, 2," , branch − 1. (2). Fig.2 Branching at local minimum by GRTA 式（2 式（ 2 ）において， X i , j は式（ は式（1 1 ）によってスケーリ そこで，B そこで， B G R T A では，以下の点に注意して，局所的 最適解において分岐させる．. ングされた設計変数であり， j 番目の分岐によって得 られた i 番目の設計変数を表す．また ε は十分小さな. 分岐数 branchmax とする．すなわち，局所的最適解 x L に. 値（例えば ε = 1.0 ×10−3 ）である．分岐によって得られ た最適解のすべての設計変数 i = 1, 2," , ndv に対して，. おける目的関数値を改善する点を最大分岐数だけ見つ. 式（2 式（ 2）が成立した場合，同じ解と見なす．. けるものと仮定する．もし最大分岐数だけ見つからな. ３）分岐する数が無くなった場合は，得られた局所的. い場合は，得られた点の中から目的関数値を最善とす. 最適解の中から目的関数値が最もよいものを最適解と. る探索点を次の分岐点とする．. して，探索を終了する．. １）分岐する数はあらかじめ決めておき，それを最大. 例えば図3 例えば図 3 に示すように，局所的最適解である点 に示すように，局所的最適解である点A Aに. 3. おいて分岐をする場合を考える．最大分岐数を２とす る．点A る．点 A で分岐をし，点 で分岐をし，点B B と点 と点DD が得られたとする．点 が得られたとする．点B B. 3.1. B G R T A のアルゴリズム. アルゴリズム. 本章では，B 本章では， B G R T A のアルゴリ.
(4) it = it + 1. ズムを示す．B ズムを示す． B G R T A で必要となる入力データを以下に 示す．. （ STEP14) STEP14)探索回数の検討を行う． 探索回数の検討を行う．. it ≤ itmax. x0. 1 ）探索初期点 2 ）初期温度. (9). であれば，STEP5 であれば， STEP5へ戻る．そうでなければ へ戻る．そうでなければSTEP15 STEP15へ． へ．. T. 3）一つの温度当りの最大探索回数 4）探索終了のための最小温度. （ 10 10） ）. （ STEP15)温度をコントロールするパラメータ STEP15) 温度をコントロールするパラメータ k を. itmax. k = k +1. Tmin. 5）局所的最適解からの最大分岐数. （ 11 11） ）. として，次式を用いて温度を下げる．. branchmax. T = T /(k + 1). 最小化ステップ （ STEP1) STEP1)適当な初期点 適当な初期点 x0 を取る．. （ 12 12） ）. （ STEP16)温度の検討を行う． STEP16) 温度の検討を行う．. T ≤ Tmin. （ STEP2) STEP2)数理計画法で局所的最適解 数理計画法で局所的最適解 x L を求める． 分岐とトンネル・ステップ. （ 13 13） ）. であれば，STEP17 であれば， STEP17へ．そうでなければ， へ．そうでなければ，. it = out = k = 0. （ STEP3) STEP3)局所的最適解 局所的最適解 x L における分岐数を. branch = 0. (3). （ 14 14） ）. としてSTEP5 として STEP5へ戻る． へ戻る． （ STEP17）分岐数の検討を行う． STEP17 ）分岐数の検討を行う．. とする．. branch = 0. （ STEP4) STEP4)初期温度 初期温度 T を設定する．トンネル・ステップ. （ 15 15） ）. および制約ステップにおける探索回数 it , out をそれぞ. であれば，局所的最適解から分岐する点はないので，. れ初期化する． k = 0 とする．. STEP12（もしくは STEP12 （もしくはSTEP2) STEP2)で得られた点を最適解として で得られた点を最適解として. （ STEP5)各設計変数ごとに STEP5) 各設計変数ごとに[0,1] [0,1]の乱数を発生させ， の乱数を発生させ，. アルゴリズムを終了する．そうでなければ，S アルゴリズムを終了する．そうでなければ， STEP3へ. それを (−π 2, π 2) に変換し， pi とする．. 戻る．. （ STEP6) STEP6)次式を用いて，局所的最適解 次式を用いて，局所的最適解 x L からの増分を. 制約ステップ. 求める．. （ STEP18). x = x L + δx. （4 ）. δ xi = T tan( pi ). （5 ）. *. out = out + 1 として，温度を次式により下げる． T = T /(out + 1). ここで， δx は局所的最適解 x L からの増分である． （ STEP7)すべての制約条件を満足しているかどうかを STEP7) すべての制約条件を満足しているかどうかを. （ 17 17） ）. （ STEP19). T ≤ Tmin. 検討する．もし満足していれば，S 検討する．もし満足していれば， S T E P 8 へ．満足して いなければ制約ステップであるSTEP18 いなければ制約ステップである STEP18へいく． へいく．. （ 16 16） ）. (18). であれば，STEP4 であれば， STEP4へ戻る．そうでなけば， へ戻る．そうでなけば，STEP6 STEP6へ． へ．. （ STEP8) x* を初期点として，数理計画法で局所的最適. 全体のアルゴリズムを図4 全体のアルゴリズムを図 4に示す．. 解 x*L. 3.2. を求める．. B G R T A のアルゴリ. ズムの終了条件は，GRTA ズムの終了条件は， GRTAとは異なり，局所的最適解に とは異なり，局所的最適解に. （ STEP9) STEP9)目的関数値の改善を検討する． 目的関数値の改善を検討する． f (x*L ) ≤ f (x L ). アルゴリズムの終了条件. （6 ）. おける分岐数 branch によって決められる．すなわち，. を満足していれば，STEP10 を満足していれば， STEP10へ進む．そうでなければ， へ進む．そうでなければ，. 局所的最適解における分岐数が無くなった場合，目的. STEP13へ． STEP13 へ．. 関数を改善する点はないと判断し，STEP12 関数を改善する点はないと判断し， STEP12（もしくは （もしくは. （ S T E P 1 0 ) 今までに得られた最適解と同一でなけれ. STEP2)で得られた目的関数値を最小（もしくは最大） STEP2) で得られた目的関数値を最小（もしくは最大）. ば，局所的最適解 x L からの分岐数 branch を. にするものを最適解として，アルゴリズムを終了す. branch = branch + 1. （7 ）. る．. とし，増加させ，STEP11 とし，増加させ， STEP11へ．同一の最適解であれば， へ．同一の最適解であれば，. 4. STEP13へ． STEP13 へ． （ STEP11)局所的最適解 STEP11) 局所的最適解 x L における分岐数が. branch = branchmax. 4.1 （8 ）. 構造最適化問題. トラス構造の位相最適化. 変位制約条件の下. でトラス構造物の体積を最小にするような最適位相を. を満足していれば，SS T E P 1 2 へ．そうでなければ， を満足していれば，. 求める．対象とする問題は図5 求める．対象とする問題は図 5 に示す に示す9 9 節点 節点28 28部材トラ 部材トラ. STEP4へ戻る． STEP4 へ戻る．. ス構造の最適位相を求める問題である．問題の詳細は. （ STEP12 STEP12）得られた局所的最適解 ）得られた局所的最適解 x*L. の中から，目的関. 文献（1 ）を参照されたい．ここでは，シミュレー. 数を最小（もしくは最大）とするものを見つけ，その. テッド・ アニーリ ング（S ング（ S A ) と遺伝的 アルゴリ ズム. 点を新たな分岐点 x L とし， とし，STEP3 STEP3へ戻る． へ戻る．. （ GA)で求めた結果と比較する． GA)で求めた結果と比較する．. （ STEP13) STEP13)探索回数 探索回数 it を増加させる．. B G R T A で必要となる入力データには，以下のものを.
(5) Input initial data Calculation of local minimum x L by mathematical programming Set as branch=0 Setting of initial temperature. k=0 it=0 out=0. Transformation of random number [0,1] into [-π/2,π/2], and put pi. x* = x L + δx No No. g j (x* ) ≤ 0. out=out+1. T=T/(out+1). δ xi = T tan( pi ). Yes * Calculation of local minimum x L by mathematical programming. T < Tmin. Yes. No. Yes. f ( x*L ) ≤ f (x L ) No it=it+1. Same optimum? Yes. branch=branch+1. Yes. it ≤ itmax. No. k=k+1 T=T/(k+1). branch = branchmax. No. T < Tmin. Find the best objective and its design variables. Set as x L. it=0 k=0 out=0. Yes branch=0. No. Yes Global minimum. Fig.4 The algorithm of BGRTA 探索初期点をすべて A0 = 500[mm2 ] とした時， とした時，BB G R T A. 用いた．. T = 1.0. 1)初期温度 1) 初期温度. で得られた最適位相を，SA で得られた最適位相を， SAと と GAで得られた最適位相と GA で得られた最適位相と. 2)一つの温度当りの最大探索回数 2) 一つの温度当りの最大探索回数 itmax = 20 3)探索終了のための最小温度 3) 探索終了のための最小温度 Tmin = 1.0 × 10. 共に表1 共に表 1 に示す．なお，表中の数値は断面積を表す．. −5. SAと SA と GAの結果は， GA の結果は，20 20回計算を行い，目的関数が最善の 回計算を行い，目的関数が最善の. 4)局所的最適解からの最大分岐数 4) 局所的最適解からの最大分岐数 branchmax = 5 P = 1000[ N ] P = 1000[ N ]. ものを示している．なお，S ものを示している．なお， S A では文献（ では文献（5 5 ）の数値を 用いた．またGA 用いた．また GAでは，個体数を では，個体数を100 100，世代を ，世代を2000 2000世代， 世代， 突然変異を0.01 突然変異を 0.01，交差率を ，交差率を0.6 0.6とした． とした． 4.2. a = 100[ mm]. 関数空間. この問題は，数値計算の結果から. 目的関数値が f = 2.40 × 103 [mm3 ] から f = 2.60 × 103 [mm3 ] の間に，少なくとも60 の間に，少なくとも 60以上の局所的最適解が存在し， 以上の局所的最適解が存在し， また，大域的最適解 f = 2.35 × 103[ mm3 ] の付近にも多く. a. a. Fig.5 Analysis model. の局所的最適解が存在することが判り，さらに，文献 E = 210[GPa ]. ( 7) , ( 8) で報告されている局所的最適解を含めると，. Table 1 Comparison of optimum topology BGRTA. SA. 260. 254. 103. GA. 108. 172. 220. 344. 75. 84 115. 102. 55. 515. 48 63 109. 474. f = 2.35 × 10 [mm ] 5. 3. 122. 51. 360. 362. 157 40. 247. 127. 87. 225. 204. 157. 256. f = 2.60 × 105 [ mm3 ]. 20. 169. 557 f = 2.56 × 105 [ mm3 ]. 130.
(6) 非常に多くの最適解が存在する多峰性の強い関数空間. ば，再検討のために要する時間が短縮でき，結果とし. であることが想定される．. て，建設作業の短縮化が期待できる．そこで，複数の. SAの場合，探索初期点にも依存するが，探索点が多 SA の場合，探索初期点にも依存するが，探索点が多. 設計案を得るために，B 設計案を得るために， B G R T A を交通路設計問題へ適用. くのの極大値を乗り越えながら，大域的最適解を探索. する．ここで扱う問題の前提として，交通路設計に対. したが，このため，目的関数値を改悪する点を許容す. する住民の苦情や用地買収，さらには政治問題を取り. る受理確率が低くなり，結果として局所的最適解に. 除き，純粋に利用者の利便性が向上するような複数の. 陥ったと考えらる．つまりSA 陥ったと考えらる．つまり SAの結果より，所々に深い の結果より，所々に深い. 交通路設計案を求めるものとする． 5.1. 谷を持つ関数空間であることが想定される．. 問題設定. 問題を簡略化するために，平面上. 一方，GA 一方， GAでは， では，SA SAよりも深い谷を見つけているが， よりも深い谷を見つけているが，. の点 (ui , vi ) に住宅街が離散的に存在するものとし，そ. やはり大域的最適解を見つけることは出来なかった．. の数を i = 1, 2," , n とする．平面上に存在する住宅街は. 連続変数をあらかじめ決めた適当なビット数で分割す. あらかじめ設定され，また大型ショッピングセンター. るようなGA るような GAの場合は，解の精度が分割するビット数に の場合は，解の精度が分割するビット数に. を目的地とし，その座標を ( x0 , y0 ) とし，これらはすべ. 大きく依存するため，領域適応型G 大きく依存するため，領域適応型 G A のように，最適. て固定されているとする．. (6). 化の状況に適応して，連続変数の精度を改良するよう. y. な方法でなければ，大域的最適解の探索は困難である. Residential block. と考えられる． これらの結果から，関数空間を想定するのであれ Allocation point. ば，例えば図6 ば，例えば図 6 に示すような，所々に深い谷を持ち， さらに大域的最適解は，スパイク状のところに存在す るものと想定される．. Shopping center. x Fig.7 Modeling of traffic road design 住宅街の人々 (ui , vi ) が利用する交通路を設計する場 合 ， こ こ で は 簡 単 の た め ， (ui , vi ) に 対 し て. 割当て. ( x j , y j ) を設け，図 を設け，図7 7 に示すように，住宅街の人々. 点. が直接的に大型ショッピングセンターへ行くことはな く ， 一 度 こ の 割 当 て 点 (x j , y j ) に 行 き ， そ し て 大 型 Global Minimum. ショッピングセンターへ行くものと仮定する．割当て 点は住宅の数と同数とする．すなわち，. Fig.6 Behavior of objective function. (x j , y j ). 一方，GRTA 一方， GRTAや や BGRTAの場合，所々に深い谷を持つ関数 BGRTAの場合，所々に深い谷を持つ関数 であっても，微分可能であれば，ある程度の探索は可. j = 1, 2," , n. (19). である．また，各割当て点 ( x j , y j ) を j = 0,1, 2," , n の順 に直線で結んだものを交通路と見なす．. 能である．また，異なる局所的最適解の目的関数値の. このモデルは，鉄道路線を作る場合に，住宅街から. 差が 微 小 の 場 合 ，G ， G R T A では 探 索 が 難 し いも の の ，. 最もアクセスのしやすい，つまり住宅街の近くに駅. B G R T A では最適解で分岐して，目的関数と制約条件の. ( x j , y j ) を設定し，路線を作るものと同等である．. 感度に基づき，複数の探索点が異なる最適解を見つけ. 目的関数. 住宅街 (ui , vi ) と割当て点 ( x j , y j ) の. 距離 φi , j を. るため，探索が可能であると考えられる．. 5. 5.2. φi, j = ( x j − ui ) 2 + ( y j − vi )2. 交通路設計への適用. i = j = 1, 2," , n (20). とする．各 (ui , vi ) に対して，最も近くにある ( x j , y j ) を. 交通路の設計は公共事業の中でも，莫大な費用がか. ( x*j , y*j ) と す る ． 割 当 て 点 は 少 な く と も １ つ 以 上 の. かるものであり，その設計は非常に重要である．ここ. (ui , vi ) に 割 当 て ら れ る と す る ． そ し て ， (ui , vi ) と. では，既に住宅街があり，そこに住む人々の利便性が. ( x*j , y*j ) の 距 離 を φi*, j と し ， そ の 総 和 を 目 的 関 数 と す. 向上するような交通路を設計することを想定する. る．. (9). ．. 出来上がった交通路の設計案を住民に見せ，仮に問題 が生じた場合は，あらかじめ複数の案を用意しておけ. n. ∑ wiφi*, j → min i =1. (21).
(7) ここで wi は重みであり，例えば住宅街の人口密度な どを表す．この目的関数を最小化することにより，住. Table 2 Coordinates of residential block Residential block Coordinates Weight (Case1)Weight (Case2). 宅街に住む人々全体の交通路に対する利便性が向上す. 1. (1.5, 1.5). 1. 1. るものとする．. 2. (7.5, 2.0). 1. 2. 交通路の建設コストを考え，各割. 3. (3.5, 3.0). 1. 2. 当て点と目的地を結ぶ距離の総和が一定値 L 以下とな. 4. (5.0, 4.0). 1. 1. るよう，挙動制約条件を与える．ただし，各区間の建. 5. (9.0, 4.0). 1. 3. 6. (3.0, 5.0). 1. 2. 7. (8.5, 5.0). 1. 3. 8. (8.0, 6.5). 1. 5. 9. (4.5, 7.0). 1. 4. 10. (8.0, 9.0). 1. 2. 5.3. 制約条件. 設コストを重み Wi として考え， n. ∑Wi i =1. ( xi − xi −1 ) 2 + ( yi − yi −1 ) 2 ≤ L. (22). とする．また，次に示す側面制約条件を与える． とする． また，次に示す側面制約条件を与える． xmin ≤ x ≤ xmax. (23). ymin ≤ y ≤ ymax. (24). 5.4. 各割当て点の座標値である ( x j , y j ). 設計変数. （ j = 1, 2," , n ）を設計変数とする． 5.5. 初期値について. 各割当て点の x 座標の初期. 値については， [ xmin , xmax ] の乱数を発生させて決定す る．一方， y 座標の初期値については， [ ymin , ymax ] の 乱数により初期値を決めた場合，目的地 ( x0 , y0 ) と割当 て点 ( x j , y j ) （ j = 1, 2," , n ）を結ぶ初期交通路が自分自 身に交わる冗長なものになる場合もあるため，. [ ymin , ymax ] の乱数を発生させ，小さいものから順番に 並び替え，決定する．この方法によって得られた初期 交通路の一例を図8 交通路の一例を図 8 に示す．図 に示す． 図 8 において◆は，住宅街 を表し，■は初期点を表す． 10 9. 一方，B 一方， B G R T A で必要となる入力データは，局所的最 適解からの最大分岐数を branchmax = 3 とし，その他は 構造最適化のものと同じ数値を用いた． B G R T A で局所的最適解を求めるために用いた最適化 手法は逐次二次計画法である． 5.7. 重みが一律の場合. 式（2 式（ 2 1 ）の住宅街に対す. る重み wi が一律の場合 が一律の場合(Case1) (Case1)において，得られたい において，得られたい くつかの結果を目的関数値と共に図9(a),(b),(c),(d) くつかの結果を目的関数値と共に図 9(a),(b),(c),(d) に示す．図9 に示す．図 9 ( a ) は，乱数の種を変更して２０回試行 し，最も目的関数値の良かったものを大域的最適解と した．また図9(b),(c),(d) した．また図 9(b),(c),(d)は，探索過程で得られたい は，探索過程で得られたい. が利用する割当て点である．. 7. この結果から，大域的最適解の場合，住宅街 (ui , vi ). 5. 7. であり，式（ であり， 式（22 22）の総長さ ）の総長さ L を L = 15 とした．. 表し，▲は割当て点を表す．また矢印は住宅街の人々. 8. 6. 8. (26). くつかの局所的最適解である．図9 くつかの局所的最適解である．図 9 中の◆は住宅街を. 10. 9. ( x0 , y0 ) = (5.0, 0.0). と割当て点 ( x j , y j ) は，１対１の関係を持っているが，. 6. 目的関数値が悪くなるにつれ，いくつかの住宅街. 5. (ui , vi ) は，同じ割当て点 ( x j , y j ) を利用するような傾向. 4. が見られた．. 4. 10. 3. 3. 2. 9. 2. 1. 1. 0 0. f = 7.44. 8 7. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 6. Fig.8 An example of initial point 5. 5.6. 数値計算例. 住宅街の数を1 住宅街の数を 1 0 とする．住宅街. 3. の座標 (ui , vi ) と重み wi を表 を表22に示す． 各区間の建設コストは一律であると想定し，式 （ 22）の重みを 22）の重みを Wi = 1.0 とした．側面制約条件は. [ xmin , xmax ] = [ ymin , ymax ] = [0.0,10.0]. 4. (25). とした．そしてショッピングセンターの座標は. 2 1 0 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Fig.9(a) Traffic road at global minimum.
(8) 10. しては，他と比べ重みが大きく，必ず交通路が通過し. f = 7.71. 9. ている．. 8. 10. 7. f = 11.72. 9. 6. 8. 5. 7. 4. 6. 3. 5 4. 2. 3. 1. 2. 0 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 1. 10. Fig.9(b) Traffic road at local minimum. 0 0. 10. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Fig.10(a) Traffic road at global minimum. 9 10. f = 9.28. 8. 9. 7. 8. 6. 7. f = 13.17. 6. 5. 5. 4 4. 3 3. 2. 2. 1. 1. 0. 0. 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 0. 10. Fig.9(c) Traffic road at local minimum. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Fig.10(b) Traffic road at local minimum 10. 10. f = 18.38. 9. f = 11.78. 9. 8. 8. 7. 7. 6. 6. 5. 5 4. 4 3. 3 2. 2 1. 1 0 0. 0 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Fig.9(d) Traffic road at local minimum 重みが異なる場合. 式（2 式（ 2 1 ）の住宅街に対す. 7. (c),(d)に示す．図 (c),(d) に示す．図10(a) 10(a)は，乱数の種を変更して２０ は，乱数の種を変更して２０. 6. 回試行し，最も目的関数値の良かったものを大域的最. 5. 適解とした．また図10(b),(c),(d) 適解とした．また図 10(b),(c),(d)は，探索過程で得 は，探索過程で得. 4. られたいくつかの局所的最適解である．この場合，重. 3. みが一律の場合と異なり，いくつかの住宅街 (ui , vi ) が. 2. た交通路自体も，重みの大きい住宅街を通過してお り，外へ湾曲していることがわかる．特に (u8 , v8 ) に関. 3. 4. 5. 6. 7. 8. 9. 10. f = 23.94. 8. る重み wi が異なる場合 が異なる場合(Case2) (Case2)の結果を図 の結果を図10(a),(b), 10(a),(b),. 同じ割当て点 ( x j , y j ) を利用するようになっており，ま. 2. 10 9. 5.8. 1. Fig.10(c) Traffic road at local minimum. 1 0 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Fig.10(d) Traffic road at local minimum.
(9) 5.9. G A との比較. 交通路設計問題に対して，GA 交通路設計問題に対して， GAと と. 多くの計算時間を必要とする場合もある．設計変数が. の比較を行う．GA の比較を行う． GAでは，個体数を では，個体数を100 100，世代を ，世代を5000 5000世 世. 少ない場合は，分岐数を多くすれば，多くの最適解が. 代，突然変異を0 代，突然変異を 0 . 0 1 ，交差率を ，交差率を0 0 . 8 とした．重みが一. 得られるものの，設計変数が多く，局所的最適解にお. 律の場合の結果を図11 律の場合の結果を図 11に，重みが異なる場合の結果を に，重みが異なる場合の結果を. ける分岐数も多くした場合，非常に多くの計算時間が. 図 1 2 に示す．なお図 に示す．なお図1 1 1 および図 および図1 1 2 は，乱数の種を変. 必要となるため，計算時間と設計変数・分岐数の関係. え，20 え， 20回試行し，目的関数値の最良のものである． 回試行し，目的関数値の最良のものである．. はトレードオフの関係が存在するものと考えられる． しかし，設計変数の数と最適な分岐数の関係を言及す. 10. ることは一般には困難であると考えられるので，今後. f = 9.89. 9. の検討課題としたい．. 8. 参考文献. 7 6. （１）北山・山崎，一般化ランダム・トンネリング・. 5. アルゴリズムによる大域的最適化（第１報. 4. アルゴリ. ズムの提示と数値計算例），機論A, ズムの提示と数値計算例），機論 A, 69‑684, (2003),. 3. pp.1250‑1256． pp.1250‑1256 ．. 2. （２）例えば，PARSOPOULOS, （２）例えば， PARSOPOULOS, K.E. and VRAHATIS,. 1. M.N., Recent approaches to global optimization. 0 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Fig.11 Traffic road of Case 1 by GA. problems through Particle Swarm Optimization , Natural Computing, Computing,1 1 ,(2002),pp.235‑306. （３）森・築山・福田，多様性をもつ免疫的アルゴリ. 10. f = 22.74. 9. ズムの提案と負荷割当て問題への応用，電学論C ，. 8. 113‑10，（ 113‑10 ，（1993 1993）， ），pp.827‑878. pp.827‑878.. 7. （４）森・築山・福田，免疫アルゴリズムによる多峰. 6. 性関数最適化，電学論C 性関数最適化，電学論 C ， 117‑5 117‑5，（ ，（1997 1997）， ），pp.593‑ pp.593‑. 5. 598.. 4. （５）北山・山崎，一般化ランダム・トンネリング・. 3. アルゴリズムによる大域的最適化（第２報. 2. とその効率に関する検討），機論A, とその効率に関する検討），機論 A, 70‑689, (2004),. 解の精度. pp.50‑55． pp.50‑55 ．. 1. （６）荒川・萩原，実数領域適応型(ARRange) （６）荒川・萩原，実数領域適応型 (ARRange)遺伝的ア 遺伝的ア. 0 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Fig.12 Traffic road of Case 2 by GA. 6. 結言. ルゴリズムの開発，機論C ルゴリズムの開発，機論 C ， 63‑616 63‑616， ， (1997),pp.4216‑ 4223. （７）坂本・尾田，遺伝的アルゴリズムを利用した最 適トラス形態決定法，機論A 適トラス形態決定法，機論 A ， 59‑562 59‑562， ， pp.1568‑1573.. 本論文では，一般化ランダム・トンネリング・アル. （８）山崎光悦，トンネル法によるトラス構造形態の. ゴリズムを改良し，局所的最適解で分岐することによ. 最適化，機講論，No.940‑10, 最適化，機講論， No.940‑10, Ⅳ（1994 Ⅳ（ 1994）， ），pp.339‑ pp.339‑. り，複数の最適解を求めるためのアルゴリズムを開発. 341.. した．提案した手法は一点探索と多点探索を繰り返し. （９）最適設計ハンドブック，山川宏編，（2003 （９）最適設計ハンドブック，山川宏編，（ 2003）， ），. ながら，複数の最適解を求める方法である．また，分. 朝倉書店,pp.475‑481. 朝倉書店 ,pp.475‑481.. 岐によって生じた複数の探索点が同一の最適解に陥ら ないようにした．数値計算例では，構造最適化問題と 交通路設計問題を扱った．構造最適化問題では，ある 程度の最適解の数を，また交通路設計では，複数の交 通路設計案を示した． しかし，提案した手法は，並列計算に向いているも のの，探索点が感度に基づく探索を行っているため，.
(10)
関連したドキュメント
To determine whether expression of HPV genes had any influence upon HIF-1α activation or levels in normoxia and hypoxia, we first examined whether HIF-1α levels were induced
performed 4 h and 8 h euglycemic (5.5 mmol/l) clamps with 3 different insulin concentrations (basal, medium postprandial and high postprandial, ranging from ~ 35 to ~ 1450 pmol/l)
Provided that the reduction of the time interval leads to incomparableness of normalized bubble-size distributions and does not change the comparable distributions in terms of
The C-minor partial orders determined by the clones gen- erated by a semilattice operation (and possibly the constant operations corresponding to its identity or zero elements)
Department of Orthopedic Surgery Okayama University Medical School Okayama Japan.. in
In this paper, we will apply these methods to the study of the representation theory for quadratic algebras generated by second-order superintegrable systems in 2D and their
In order to demonstrate that the CAB algorithm provides a better performance, it has been compared to other optimization approaches such as metaheuristic algorithms Section 4.2
For performance comparison of PSO-based hybrid search algorithm, that is, PSO and noising-method-based local search, using proposed encoding/decoding technique with those reported
