SA 連続最適化問題に対する

連続最適化問題 に対す る コーシー分布型 S A の提案

章 一

泰 太

田 地 ･‑‑ n H = ･･‖り

1. は じ め に

最適化問題 を解 く主 な手法 には,厳密解法 と近似解法がある｡厳密解法はそ の問題の厳密 な最適解 を求める手法であるが,厳密解法は対象 とする問題の大 きさによって計算時間が膨大 にな り実用 的な時間で実行す ることが困難であ る｡一方,近似解法は厳密 な最適解が求 まる保障はないが実用時間内で近似的 な解 を求め ようとする手法であ り,特 に組合せ最適化問題 に対 してメタヒュ‑

リスティクスの種 々の手法が近年研究 されている｡ このメタヒュ‑ リスティク スの代表的 な ものに焼 きなま し法 ( SA: Si mul a t edAnne a l i ng) [ 1 ]があ る｡

SA は ,Me t r o po l i s らが 1 9 5 3 年 に発表 した焼 きなましと呼ばれる加熱炉内の物 質の冷却過程 をシミュ レー トす るアルゴリズム[

2

]に端 を発す る｡ 固体 を洛融 点 を越 えて過熱 し再 び凝固点 まで冷却す るとき,冷却 された物質の構造特性 は 冷却の速度に依存することが知 られている｡ 高温時の物質はエネルギーが高 く, 粒子の運動が激 しく粒子の配列が不規則であるが,徐 々に冷却することで,粒 子の運動が収 ま り粒子の配列が徐 々に規則的で安定 した状態 となる｡例 えば, 硝子の結晶は高温か ら徐 々に冷却 してい くことで成長す るが,水 をかけるなど で急速 に冷却す ると亀裂が生 じ不完全 な もの となることが挙 げ られる 0 Me t ‑ r o po l i s の理論 はこの ような冷却過程 について,ある系が安定状態 まで収束す

るエネルギーの変化 を模擬 している｡後 に Ki r kpa t r i c k らによってこの シミュ レーシ ョンが最適化問題の実行可能解 を探索することに応用で きることが提案 され ,SA は組合せ最適化問題 における代表的な近似解法 として用い られて き

〔67〕

6 8

商 学 討 究 第59巻 第2 ･3号

た｡

本来 ,S A はこの組合せ最適化 問題 に対 して有効 な手法である｡ しか し,逮 続最適化問題 において も目的関数の多峰性が極めて高 く,複雑な挙動 を示す問 題 となる場合 には有効 とされ,連続最適化 問題 に対する多 くの研究がおこなわ れている｡例 えば, タンパ ク質の構造分析

[3

]や画像,音声 などの信号処理 に たいする S A の適用が行われている｡三木 らはこの多峰性の連続最適化問題 に 受理確率 に応 じて近傍の幅 を調整する手法である S A/ AAN を用 いることで, 良好 な解が得 られることを示 している[

4

] ｡三木 らの手法 を用 いてい くつかの ベ ンチマーク問題 を解いた ところ,三木 らが実験対象 としている問題では精度 の高い解 を得 ることがで きたが,ある一部の問題において三木 らの手法では最 適解付近に到達で きない問題 もあることがわかった｡そ こで, この ような難 し い問題 をも解 くことを可能 とし, よ り探索能力の高い手法について検討 してい きたい｡

連続最適化 問題 に対す る手法の一つ に探索の高速化 をはかった手法 として

S z u らが提案 した Fa s t S A ( Fa s tS i mu l a t e dAn n e a l i n g )[ 6 ]がある ｡Fa s t S A

では従来の S A よ りも短時間で探索 を行い,従来の S A と同等の解が得 られる

ことが示 されてお り, この高速化 を実現する要因 として近傍 にコー シー分布が

用い られている｡ この コー シー分布 に着 目してこの ような難 しい問題 を解 くこ

とを試みたい｡ コーシー分布 はその分布の形状か ら,分布の中心 に高い確率で

次状態が提案 されることで解空間を局所的に探索で き, またその裾の広 さか ら

ロングジャンプによる広い探索 をも可能 とす る特徴がある｡ この特徴 は,解の

探索 における集中化 と多様化 を取 り込んだ高い探索能力 を秘めているもの と考

えられる｡そのため, コー シー分布 に従 った近傍 を用いた手法は,高速 な探索

時間 となる他, よ り高い探索能力 を持つ もの となるだろう｡従って,本研究で

は コー シー分布 に従 った近傍 を適用 し ,S A の能力 を活か したアル ゴ リズム

(コー シー分布型 SA) を考察 してい く｡ さらに ,S A は精度の高い解へ の収

束 に膨大 な時間を要す るとい う問題があるため ,powe l l法 [ 7]とい う凸関数 を

最小化す る手法 との組み合 わせ によ り改善 を試みる｡次 に ,S A の能力 を発揮

連続最適化問題に対するコーシー分布型 SAの提案 69 するためには冷却スケジュールを決める適切 なパ ラメー タを設定 しなければな

らない｡ また, コー シー分布型 SA の性能や特徴 を解析す るためにも他の手法 との比較 を行 う必要があるだろう｡そこで,詳細 なパ ラメー タの数値実験 を行 い,適切 なパ ラメー タの提案 を行 う｡そ して ,S A/ AAN や基本的な確率分布 である一様分布や正規分布 に従 った近傍 をもつ SA との比較 を行い, コー シー 分布型 SA の特徴 を明 らかに したい｡最後 に, コー シー分布型 SA と p o we l l

法 を組み合 わせた手法の解の収束性 に対する有効性 を検証する｡

2. 連続最適化問題

最適化問題の一つ として設計変数が連続である連続最適化 問題がある｡連続 最適化問題の最 も単純 なケースは単峰の凸関数の最小化であ り, この ような問 題 にはある解 における勾配情報 などを利用 して最小化 を行 うことがで きる｡ し か し, 現実において直面する問題 はその 日的関数が多峰性で複雑 な場合があ り, 勾配情報だけでは最適解 を得 ることが とて も困難なものである｡本研究で対象

とす るのはこの ような複雑 な問題であ り,この ような問題に対 して多 くの研究 がお こなわれている｡例 えば, タンパ ク質の構造分析

[3

]や画像,音声 などの 信号回復 にたいする S A の適用が行われている｡本研究ではこの連続最適化問 題 に対 して有効 なアルゴリズムの開発 を目標 とし,対象問題 として次に示す

3

つのベ ンチマーク関数の最小化 問題 を扱 うこととす る｡

( 1 )AI p i n e 関数

Al p i n e 関数は以下の式で表 される｡

I,I

fA(I)

‑ Ⅰ

^∑=1lxtsin

xi +

0.1xiJ

また,最適解お よび最適値 は以下の通 りである

｡

l =

連続最適化問題に対するコーシー分布型 S A の提案 7 3

の幅を固定する探索の

2

段階 H,解の受理率が0.

2

となるよう近傍の幅 を調整 する探索の 3 段階 目と,探索 を 3 段階に分けて行い, 目標 とする解の受理率 を 達成する近傍 を生成する｡ また,三木 らは最終的に解の受理率 を

0.2

程度に保 ち探索 を行 うとき,精度の高い解が得 られるとしている｡

この ような受理率 を保つ近傍の調整 を行 うために ,S A/ AAN では近傍 に次 の一様分布 を考え,解の移動を行 う｡

xl/I‑Xi+rm (7)

ここで , Yは [‑1 ,1 ]の一様乱数である｡ また ,m は近傍の幅 を決定す るパ ラメータである｡ このパ ラメー タ 肌 は次式に示 される受理率 ♪によって変化 する関数 ♂

(

♪) により決定 される｡

まず,探索 の一段 階 目で は近傍調整が次の式 に よって行 われ る｡ これ は c o r a na らが提案 した受理率 を 0. 5 となるよう近傍の幅を調整するアルゴリズム である｡探索の序盤では温度が高いため0.

2

という低い受理率 を達成すること は困難である｡そのため,まずは受理率 0. 5 となるよう近傍 を調整 し,温度 を 下げるのである｡

∽′‑∽+♂(♪)

g( ♪) ‑1･C 碧 i f ♪,pl g( p'

‑

l

l

･C 4

^{崇 〕}ー1 1f

P<92 g( ♪) ‑ 1. 0 o t he r u J i s e

(8)

ここで pは,解 の提案 間隔 N 回毎 における,受理 された解 の回数 n か ら ,p

‑n/ N として計算 される｡三木 らは N ‑5 0 としている｡ また,pl , ♪2はそれぞ れ 目標 とする受理率の上限および下限であ り,ここではそれぞれ,0.

6,0

. 4で ある

｡ C

はスケー リングパ ラメー タであ り ,Co r a na と三木はともに 2 として いる｡

次に,受理率が 0. 5 を達成 した後か ら探索の二段階 目が行われる｡二段階 目

7 4

商 学 討 究 第59巻 第2 ･3号

で は,受理率 0. 5 を達成 した近傍 幅 に近傍 を固定 し探索 を行 う ｡SA において は固定 された近傍の まま探索 を続 けることで 自ず と受理率が下が る とい う特徴 があ るため, ここで は固定 された近傍 に よって受理率が 0. 2 と下が るまで探索 を行 うのであ る｡ この 2 段 階 目を終 えた とき,受理率 を 0. 2 に保 ちなが ら探索 を行 える状態 となる｡

そ して,三段 階 日では次の式 に よって,解 の受理率が 0. 2 となるよう近傍 の 調整 を行 う｡

m' ‑m+

9

(

P)

g(

♪)‑Ho

i f ♪>♪1 g( ♪) ‑0. 5 1

f

♪<pZ g( P) ‑ 1. 0

otherwise

(9)

ここで Pは,解 の提 案 間隔 N 回毎 にお け る,受理 され た解 の 回数 n か ら ,9

‑71/N

として計算 される｡三木 らはN ‑5

0

としている｡ また , 九 P Zはそれぞ れ 目標 とす る受理率の上 限お よび下 限である｡ ここではそれぞれ ,0. 25,0. 1 5 としている｡そ して,H o は近傍幅の拡大率であ り,次の ように決め られるo

Ho‑Ho*Hl

( 初期設定

H0‑2.0) H1‑2.0 if

p' >pI

H1‑0.5 if

p' <92

H

1 ‑1. 0

0theruJise

Lltll

ここで,p'は解 の提 案 間隔 L 回毎 にお け る,受理 された解 の 回数 l か ら ,p'

‑

l/L

として計算 される｡三木 らは

L‑200

としている｡

この ように SA/ AAN では解摂動の受理率 を もとに近傍 の幅 を調節 して解摂

動 を行 う｡受理率 少が 目標 とす る受理率 よ りも大 きければ近傍 の幅 を大 きくし,

小 さければ近傍 の帽 を小 さ くす るように調節 される｡ また,近傍の拡大幅 も受

理率 p 'に よって調整す る仕組 み を持 ち, この仕組み に よって問題 に応 じて適

応的に近傍幅 を調整で きる としている｡ この ように,問題 と解 の受理の状況 に

連続最適化問題に対するコーシー分布型 SA の提案 7 5 よって近傍幅 を適応的に自動調節で きること,そ してこれによって精度の高い 解が得 られることに SA/ AAN の大 きな特徴がある｡

本研究では, この SA/ AAN を用いて上述ベ ンチマーク問題 を解 いてみた｡

その結果,三木 らの示 した Ra s t r i g in 関数お よび 2 ' l mi ni ma 関数 において精度 の高い解の値 を得 ることがで き,その解 も最適解付近へ と到達 していた｡ しか

し ,Al pi ne 関数では最適解付近へ全 く到達で きていないことがわかった｡

4. コーシー分布型 SA

SA/ AAN では Al pi ne 関数 において最適解付近へ と全 く到達で きない とい う問題があった｡ また ,SA/ AAN の受理率 を調整す るとい う操作 は,本来の SA の作法,すなわち温度 を下げなが ら探索が進 むにつれて受理率が減少 し, それ と共 に解が最適解‑ と収束す るとい う SA の特徴 とは異 なるものである｡

そ こで ,SA の特徴 的な冷却 スケジュー リングを活か した純粋 な SA でアルゴ リズムを構築 し,かつ近傍構造 を工夫す ることによってこの間題 を解決で きる ようなアルゴリズムの構築 を行いたい｡

まず ,SA では,熱力学 における物質の状態,エネルギー,状態変化,温度, 凝固点 をそれぞれ,最適化問題 における実行可能解, コス ト ( 最小化する目的 関数値),近傍解,制御パ ラメー タ,近似解 に対応 させ て扱 っている ｡SA の アルゴリズムは,十分 に高い温度か ら徐 々に温度 を下げ,各温度 において定め られた回数だけ解移動のプロセスを繰 り返 し,解が安定状態 に至 るまで温度 を 下げることか ら構築 される｡解の移動のプロセスは,現在の解 に微動 を与 えて 解の次状態 を提案 しその コス トの変化 を求め,次の受理基準 に従 って提案 され た次状態へ と更新することで行われる

｡

P(accept)‑

1 ⁽ 』<0 )

e x p( 一号) ^{( A}

^{≧0) (班}

ここで, コス ト差 A‑( 現在の解 コス ト)‑( 次状態の解 コス ト)であ り ,T は

1: x:=

初期解;

Opt:=

初期解;

T :=Tinit;R:=Rinit; 2: while

終了基準

do begin

3: fori:= 1toRdo begin

4: y:=

ランダムに選ばれた解

inN(x) 5: ∆ =f(y)−f(x);

6: if∆≤0then

7: x=:y;

8: iff(y)< f(Opt)thenOpt=y;

9: else

10: ifexp

−^∆_T

≥random[0,1)thenx:=y;

11: end;

12: T :=T∗phi;

13: R:=R∗tau;

14: end;

15: returnOpt;

7 6

商 学 討 究 第59巻 第2 ･3号

現在の温度である｡ この受理基準 は解 コス トが改善 される場合 は必ず次状態へ 移動 し,改悪 される場合で も,温度が高い状態 またはコス ト差が小 さい状態で あれば移動 を許容す ることを示 している｡ この ように SA は解移動 にコス ト差 と温度が深 く関与 した仕組み を持 っている｡その SA のアルゴリズムの全体 を 図 4 に示す ｡SA のアルゴリズムではまず,初期解お よび制御パ ラメー タであ る温度,初期温度における解移動のプロセス数の初期設定 を行 う｡ ここで,ア ルゴリズム

1

行 目の Xが現在の解 ,Opt は探索 における最 も良い解 を保持 した 暫定解 を示 し ,T は現在 の温度 ,R は図の 3 行 目におけるループの反復 回数 す なわち各温度 において定め られた解移動 のプロセスの回数である｡そ こで R 回だけ解

y

を提案す ることを繰 り返 し,解 xを受理基準 に従 って更新する｡

終了基準は温度がある低い温度以下になることや,提案 される解の受理率が小 さ くなることな どを基準 として設定 され るo また, 4 行 目の解

y

は xの近傍

N( I) か らランダムに選ばれた解 の次状態であ り,提案解

y

の コス ト

f(y)

と解 xの コス ト f ( I )か らコス ト差 Aが求め られる. なお,近傍 N( I) とは現在の解

∬にたい して何 らかの微動 を与 えることによって得 られる解 ∬の次状態の集合 である｡R回の反復 を終 えると,温度 T と反復数 R を更新す る｡ これは1 2 行 目

,13

行 目に示 されるようにそれぞれ,温度

Tに減少率

phi を乗 じること,

図 4:SA のアルゴリズム

連続最適化問題に対するコーシー分布型 S A の提案 7 7

反復数 R に増加率

tau

を乗 じることで行 われるo最後 に,終了基準 を満 た し た後, 8 行 目に示 され る探索 において得 られた最 も良い解 を保持 した暫定解 Opt を出力 し探索 を終 える｡ この Opt が S A によって もとめ られた近似解であ る｡

この ように ,S A を適用 したアルゴリズムの構築 において,次状態 を決める 近傍の構造お よび冷却 スケジュールを決める

4

つ ( T i m l ,R " l i t , Phi

,lou)

の パ ラメー タ,終了基準の設定が必要 とな り, これ らの設定が良いアルゴリズム の構築 に重要 なファクター となって くる｡

次に本研究で扱 う近傍 について考察 したい｡ まず近傍の構築に際 して,集中 化 と多様化 とい う二つの概念

[5

]について述べ る ｡S A の ようなメタ戦略の多 くは,｢ 良い解 どうLは似通った構造 を持 っている｣ とい う概念 に基づいて諺 計 されてお り, この概念が成立 しているならば良い解 に似 た解の中によ り良い 解が存在す るとい う考 え方がある｡集中化 とは,この考 えにのっと り良い解 を 得た ときその解 と似た構造の解 を重点的に局所的な探索 を行い,良い解 を得 よ うとす る考 え方である｡ しか し,解空間には最適解 に近い値 をとる局所解が存 在す るため,誤 って局所解の周辺 を積極的に探索 して しまい最適解 を得 ること

とがで きない とい う危険 もある｡ また,同 じ解 を何度 も参照 して しまうとい う 危険 もある｡ これに対 して,探索の中で既 に得 られた解 とは違 う構造の解 を参 照す るなどして,解空間を広 く探索することで局所解 に陥 らない ように しよう とす る考 え方が多様化である｡最適化 におけるアルゴリズムでは,その探索が 集中化 または多様化の どち らにそった もの となるかは次状態 を生成す る近傍の 構造によって左右 される｡そのため,集中化 と多様化 を実現で きる近傍の構造

を構成することが重要 となる｡

本研究で扱 う連続最適化問題の近傍構造 は,一般 に現在の解 に対 して何 らか

の確率分布 に従 った乱数 を発生 させ ることによって次状態 を生成するといった

手法が とられる｡従来の S A が対象 としていた組合せ最適化 問題では,例 えば

巡回セールスマ ン問題 に対す る S A の解の近傍 は,解 を構成す る隣接す る都市

を入れ替えることや,二つの都市の間に別のある都市 を挿入す るといったこと

7 8

商 学 討 究 第59巻 第2 ･3号

で操作的に近傍 を構成することがで きる｡ しか し,連続最適化問題は解の設計 変数が連続 なため隣接する要素 を入れ替 えるといった操作的な近傍構造の構成 を行 うことがで きない｡そのため,近傍の構造 はユーク リッ ド空間内での距離 に関係 した近傍の範囲を設定することによって構成 される｡

は じめに基本的な近傍の構造 として一様分布 と正規分布があげ られる｡まず, 一様分布 は与 え られた範囲 [ α , ∂ ] における値の生起確率がすべ て等 しい分布 である｡この とき,一様分布 に従 った近傍 は現在の解 ∬を中心 とし ,α‑

ズ

ーα,

b‑I+

αと近傍の範 囲 をαで与 え,その範 囲内で一様乱数 を発生 させ ること

で生成 した｡ ここで α を増減 させ ることで近傍 の範囲 を調整で きる もの とし た｡なお,本研究で扱 うベ ンチマーク問題 は

2

変数であるので,解 を

(

r

l,x2)

と表す と,その要素 ∬1

,

g

2

それぞれ を中心 とし,それぞれに対 して独立 に乱 数 を発生 させ

, ∫

l

′, ∬

2 ′を生成 し近傍解

(∫l′,∬2′)

とする｡

次に,正規分布 に基づ く近傍 を考 えたい｡正規分布 は次の確率密度関数 をも つ確率分布である

｡

f( I, ‑去 e r p 〔 ‑ 誓 〕

(12,

ここで pは平均であ り , Uは標準偏差である｡正規分布の形状 は釣 り鐘状 を し

てお り,平均 〃の直線 を境 に左右対称 の形状 を してい る｡ この とき,平均

〃

には現在の解 xを設定 し,標準偏差 Uで近傍 の幅 を与 え,正規分布 に従 った

乱数 を発生することで近傍 を構成 した｡ なお,一様分布同様 に本研究で扱 うベ

ンチマーク問題 は

2

変数であるので,解 を

(

r

l,x2)

と表す と,その要素 x1 ,

g

2

のそれぞれを中心 〃として独立 に乱数 を発生 させ

, ∫l′, ∬2

′を生成 し,近傍

解

(∫l′,∬2′)

とす る｡通常,組合せ最適化 問題の近傍 はこの正規分布の形 をと

るもの と考 えられている｡ しか し,一様分布 を含め,正規分布 は連続最適化問

題では探索能力に限界があると考 える｡そこで より探索能力に優 れた近傍 を考

えてみたい｡高速化 を取 り入れた近傍 としてコーシー分布 を用いることを考 え

た Szu らの Fa s t SA ( Fa s tSi mu l a t e dAnne a l i ng) がある ｡Fa s t SA は SA の

連続最適化問題に対するコーシー分布型 SA の提案 7 9 時間の高速化 を図った手法である｡通常 ,SA の冷却 スケジュールは温度減少 が次の式でなされる とき最適解への収束が保証 されている｡ ここで,T( i ) は 温度の t番 目の温度 ,To は初期温度 を表す

｡

T( i ) ‑ T o

log

( 1+

i)

L

l

. I

ll

しか し,このスケジュー リングでは膨大 な計算時間が必要であ り実用的ではな い｡ これを Fa s t SA では次の式 に示 される温度減少で冷却 を行い,時間の高速 化 を計 っている

｡

･' F ' ‑ 菩 (

1

4 ,

この時間の高速化 を実現 している要因のひとつが コーシー分布 による近傍であ る｡ この コーシー分布 は次の確率密度関数 を持つ ものである｡

f( I; ro ,γ ) ‑

W ,[ 1I 〔 学 ) 2 ] ' 1 5 '

ここで goは分布の最頻値 を与 える位置母数 , γは半値半幅 を与 える尺度母数で ある｡また,コー シー分布 は期待値や分散が定義 されない性質がある｡コー シー 分布の概観 を正規分布の概観 とともに図

5

に示す｡その コーシー分布の形状 は, 分布の頂点が鋭 く, また分布の両裾が正規分布 に比べ長 く広がっている｡すな わち,最頻値 go 付近の値 の生起確率が高 く, また,両裾の値の生起確率が 0 に近づ きに くい とい う特徴がある｡要す るに,分布の中心である最頻値付近 に 高い確率で次状態が提案 されることで解空間を局所的に探索で きるとい う集中 化 に従 った特徴, また,その裾の広 さか らロングジャンプを可能 として大域的

にも探索 しで きるとい う多様化 に従 った特徴 を持つ探索能力が期待で きる

｡

そ して, コーシー分布 に従 った近傍 を構築するには,最頻値 goに現在の解

∬

を設定 し ,γ

‑1

として

,

Jを中心 にコー シー分布 に従 った乱数 を発生 させ るこ

とで生成す ることした｡また,2変数のベ ンチマーク関数に対応 させた近傍 は,

80

045 04 035

03

025 ij 盲 02

015 01 005

商

学

討 究 第 5 9 巻 第

2･3号

‑B ‑

6 ‑l

‑2 0

2 4 6 B

X

図

5:コーシー分布の概観

解 を

(xl,x2)

と表 した時,その要素

xl,

x

2

のそれぞれ を中心 x

o

に設定 し独 立 に乱数 を発 生 させ

, ∫

l

′, ∬

2 ′を生成 し,近傍

(∫l′,gZ′)

とす る｡ また

,∬1,∬2

どち らに対 して も γに同 じ値 を与 えている｡ この場合の乱数の ヒス トグラムを コー シー分布 に従 った近傍 の概観 として図

6に示す｡

この コー シー分布 の特徴が Fa s t SA で示 された時間の高速化 のみ な らず,探 索能力 の向上 を図る戦略 をとる もの として,本研究では近傍 にコー シー分布 を 扱 うこととした｡以降, コー シー分布 を近傍 に適用 した SA をコー シー分布型 SA と呼ぶ こととす る｡ コー シー分布 型 SA は SA の冷却 スケジュー リングに 基づ き, 最適解付近‑ と到達で きる可能性 を持つ アルゴリズム として構築 した｡

さらに,従来か ら SA に よる探索 では近傍の範 囲か らランダムに次状態 を選択 す るために解 の収束 には膨大 な時間を要す ることが知 られているため, この 収 束性 の問題の改善 を考 たい｡本研究で扱 う連続最適化 問題 は多峰性の高い 目的 関数 を対象 としてお り複雑 である｡ しか し,ある範囲 を,例 えば局所解付近や 最適解付近 を, 局所的に見 る とそれは単峰の凸関数 として捉 えることがで きる

｡

その ような点では従来の手法 を用 いてその最小化 を行 うことがで きる｡ この よ

うな考 え方 を基 に した改善手法 として SA と po we l l法のハ イブ リッ ト手法 [ 8 ]

1:

方向集合

ui

を基底ベクトルに初期化。 以下のステップを関数が減少しなくなるまで繰り返す。

2:

出発点を

P0

に設定。

3: i= 1, ..., N

について,P

i−1

を方向

ui

に沿った最小に移動し、その点を

Pi

と置く。

4: i= 1, ..., N

について,u

i

←

ui+1

と置く。

5: uN

←

PN−P0

と置く。

6: PN

を方向

uN

に沿った最小に移動し、その点を

P0

と置く。

連続最適化問題に対するコーシー分布型 S A の提案 8 1

2変数 コーシー分布 mode=00 γ=10

図

6:2 変数のコーシー分布の概観

図7 :

p o wel l 法の基本手続き

が存在す る ｡po we 1 1法 とは n 次の凸関数 を最小化 させ るための手法の一つで

あ り,方向集合 を用いることによって最小化す る方向をさだめ最小化 を行い,

その解か らさらに方向集合 をさだめ最小化 を行 うとい う手順 を最小化で きる方

向が な くなるまで繰 り返 し最小点 を見つ ける とい う手法 に基づ くものである

[ 7]｡その基本手続 きは次の図

7

の とお りである｡ ここで ,P o が現在の解 であ

り , Ⅳ は関数の次数である｡ 2行 目か ら 5行 目で最小化 を行 う方 向を定め,

6

行 目で最小化方向に解 を移動するとい う手続 きを繰 り返 し行 う｡本研究では,

コー シー分布型 SA によって得 られた近似解 に対 して po we l l法 を適用す る と

い う手法で短い時間での解の収束 を可能 とし,かつ,最終的に最適解への収束

8 2

商 学 討 究 第59巻 第2 ･3号

を も可能 とす るような改善 を考 え, コー シー分布型 SA と p o we l l法のハ イブ リッ ト手法 を提案手法 とす る

｡

5. 数 値 実 験

前節ではコー シー分布型 SA による探索能力の向上 をはか り,パ ウエル法で の収束性の強化 をはかる提案手法について述べ た｡本節では, まず S A のパ ラ メータについて妥当なパ ラメー タを求めるための試行実験 を行い,適切 なパ ラ メータを提案す る｡そ して , Al p i n e 関数に対する性能について数値実験 を行い, ア ル ゴ リズ ム の 比 較 を通 して提 案 手 法 の特 徴 を明 らか にす る｡ また,

SA/ AAN で良好 な結果 を得ている事例 について も検証 を行い,提案手法の性 能 を明 らか にす る｡ なお,本節 で行 われ る数値実験 は ,CPU が Pe nt i um4 2. 4 GHz ,メイ ンメモ リが

1

GB の計算機 を使用 し ,OS として Li nu x を採用 し た実験環境で行 った ものである｡なお,アルゴリズムの実装 にはC言語 を用 い ている｡

それでは,パ ラメー タに対する考察 を行いたい oSA では初期温度

Tim/

,堤 度減少率 ♪hi ,初期 ループ数

Rim/

,ループ数増加率 t au ,終了基準 とい う

5

つ のパ ラメー タを調整す る必要があ り,このパ ラメー タによってアルゴリズムの 性 能が左右 される｡ ここではコー シー分布型 SA の Al pi n e 関数 に対す るパ ラ メー タ調整 について述べ る｡まず,初期温度

T"li

fの調整 を行 った｡表

1

はコー シー分布型 S A の Al p i n e 関数に対する 1 0 0 回試行 において,初期温度

T2,,it

を 1 0

度か ら 6 0 度 まで 1 0 ずつ上昇 させた ときに得 られた,最適解付近への到達回数,

コス トの平均値,初期温度における受理率,総ステ ップ数 を示 している｡ ここ

で最適解付近への到達 回数 とは得 られた近似解

(21,32)

の要素 x

l,

x2 がそれ

ぞれの最適解

±1

の範囲に到達 した試行の回数である｡ コス トの平均 とは得 ら

れ た近似解 の値 の平均 で あ る｡ また,初期温度 にお ける受理率 は初期温 度

Ti,Zi

Eにお ける R 回の解提案 において解 の移動が受理 された比率の平均 を表

す｡そ して,総ステ ップ数は探索

1

試行 における解の総提案数 を示 しアルゴリ

連続最適化問題に対するコーシー分布型

SA

の提案

83

ズムの実行時間を示す指標である｡ なお,この試行 においてその他のパ ラメー タは温度減少率 phi

‑0.8

,初期 ループ数 R

"

u / ‑1 0 0 ,ループ数増加率

tau‑1.3

, 終了基準 を温度 T <0. 1 と固定 して設定 した｡また初期解 は ( 1 0

0,100)

である

｡

これは予備実験 により (

‑100,100), (‑100

,

‑100)

, ( 1 0 0,

‑100), (100,0)

,

(‑100,0), (0,100), (0,‑100)

の他 の

7

点で同様の結果が得 られることが 分かってお り,他の関数で も同様であったため,以後の数値実験 において初期 点に

(100,100)

を使用することとした｡

表1:初期温度Tjn

j f の調整

初期温度

T"ll/ 10.0 20.0 30.0 40.0 50.0 60.0

到達回数

62 81 83 86 84 81

コス ト平均値

0.187 0.050 0.030 0.064 0.052 0.032

受理率

0.097 0.229 0.403 0.491 0.561 0.625

総ステップ数

81156 178662 302144 392876 510827 664163

この結果か ら,初期温度

Tim

/が上昇す るにつれて最適解付近への到達回数

が増 えてい くが, この結果の場合40 度 を境 に到達回数が若干減少 してい く傾向

があることがわかった. また, コス トは初期温度

Tm

l lが高い と精度が増す傾

向がみ られ,受理率 は初期温度 Tl , l i t の上昇 につれて高 くなる傾 向があること

がわかる｡初期温度

Tim

lを高 くす ることで精度の高い解が得 られるが,一方

でその総ステ ップ数が増加 して しまい実行時間が長 くなって しまう｡そのため,

ここでは総ステ ップ数 と到達回数 に重点 をおいて考慮 し,初期温度

T"li

fは最

適解付近への到達回数が最 も多い

40.0

に設定す ることとした｡なお,本研究で

は実用的な実行時間を考えた とき総ステ ップ数は400000 ステ ップ前後が妥当で

あると考 えることとした. なお ,Ra s t r i g in 関数 ,2 ' l mi ni ma 関数において も同

様の初期温度

Timl

で到達回数1

00

回を得 ることがで きることを確認 し,また,

この二つの関数では1

0.0

と低い温度か ら始めた場合で も良い結果が得 られてい

る｡

84 商 学 討 究 第59巻 第2･3号

次 に温度減少率 phi につ いて調整 を行 ったo表

2

は コー シー分布型

SA

の

Alpine

関数 に対する1

00

回試行 において,温度減少率 phi を

0.75,0.80,0.85

,

0.90

, とそれぞれ設定 した ときの最適解付近への到達回数, コス トの平均値, 総ステ ップ数 を示 している｡ なお, この試行 においてその他のパ ラメー タは初 期温度

Ti,ZiE‑40.0

,初期 ループ数

RiniE‑100

,ループ数増加率

tau

‑1 .

2

,終 了基準 を温度 T<0. 1と固定 して設定 したoまた初期解 は

(100,100)である^｡

この結果か ら,温度減少率 phi を大 きくす ることによって,到達回数が上昇 し, コス トの精度 も高 くなる傾向があることがわかる｡0.

85,0.90

では

9

割近い到 達率 となっている｡ しか し,総ステ ップ数が大 きなもの となって しまった｡総 ステ ップ数は

SA

のアルゴリズム上,温度減少率

phi

とループ数増加率

tau

の 関係 によ り増減するため, この結果のみで温度減少率 phi を決定せずに,ルー プ数増加率

tauによる変化 も考慮 した上で決定することとし,到達回数は少 な

いが総ステ ップ数が少 ない温度減少率

♪hi‑0.80

と到達 回数は多いが総ステ ッ プ数の多 い温度減少率

phi‑0.85

を候補 として,ループ数増加率 による変化 を 確認 した｡

表

2:温度減少率p

H の調整

温度減少率phi

0.75 0.80 0.85 0.90

到達回数

58 71 87 92

コス ト平均値

0.260 0.149 0.023 0.0001

総ステップ数

21809 65983 410703 15759570

表

3

はコーシー分布型

SA

の

Alpine

関数に対す る1

00

回試行 において,ルー

プ数増加率 t a u を1 .

1

,1 .

2

,1 .

3

,1 .

4

, と設定 した ときに得 られた,最適解付

近への到達回数, コス トの平均値,総ステ ップ数 を示 している｡ この時の温度

減少率 は0.

80

と固定 して設定 している｡ また,表

4

は温度減少率 を0.

85

と固定

して設定 した場合の表

3

と同様の結果である｡ なお,表

3

,表

4

において,釈

方 とも初期温度

Ti,lit‑40.0

,初期 ループ数

Ri,lit‑100

,終了基準 は温度<0.

1

連続最適化問題に対するコーシー分布型 SA の提案 8 5 と同様の固定 したパ ラメー タを用いている｡また初期解 は

(100,100)である｡

ここで,表

4の4

列 目 t au ‑1.

4

の試行 は実行 に膨大 な時間がかかるため,到 達回数は1

0

回試行中の結果 を示 している. この結果,ループ数増加率 t a u が大 きいほ ど到達回数が大 きくなる傾向があることがわか り, この とき温度減少率

♪hi を

0.80

に設定 した ものは,0.

85

に設定 した ものに比べて総ステ ップ数が少 な くて も到達回数で同等の結果が得 られることがわかる｡到達回数が9

0

回を超 えるものは総ステ ップ数が数百万 ステ ップを超 え長い処理時間を必要 となるた め選択 は控 えることとした080 回を超 えるものでは,表

3

の

3

列 目 phi ‑0. 8 , t au ‑1.

3

に設定 した もの と表

4

の

2

列 目 phi

‑0.85

,t au ‑1.

2

に設定 した もの があ り,それぞれ86,87 と同等の到達回数 を得 られている｡ ここではこの二つ の設定か ら到達 回数 を考慮 して,温度減少率 ♪hi ‑0. 8 ,ループ数増加率 t au

‑1.

3

を選択することとした｡

表

3:ループ数増加率tau

の調整 ( phi ‑0. 8 0 ) ループ数増加率 おu

1.1 1.2 1.3 1.4

到達回数

51

コス ト平均値

0.413

総ステップ数

11837

71 86 87 0.148 0.067 0.011 65983 392876 2165978

表

4:ループ数増加率tau

の調整 ( phi ‑0. 8 5 ) ループ数増加率 t a u

1.1 1.2 1.3 1.4

到達回数

60

コス ト平均値

0.379

総ステップ数

32109

87 94 10/10 0.023 0,003 0,001 410703 5419882 62657657

そ して,初期 ループ数

Rim

lの調整 を行 なった｡表

5

は コー シー分布型 SA

の

Alpine

関数に対す る1

00

回試行 において,初期 ループ数

Rini

lを5

0,100,150

,

200

,と設定 した ときに得 られた,最適解付近‑の到達回数,コス トの平均値,

86

商 学 討 究 第59巻 第2･3号

総ステ ップ数 を示 している

O

なお,初期温度 T

im

/

‑40.0

,温度減少率 phi ‑0. 8 , ループ数増加率 t au

‑1.3

,終了基準 は温度<0.

1

と同様の固定 したパ ラメー タ を用 いている｡ また初期解 は

(100,100)である｡ この結果か ら,初期 ループ

数 R

lni

lの増加 に伴 う到達回数の変化 は少 な くどの設定で も

80

回近 くの到達 回 数 を得 られている｡一方, コス トの平均値 は初期 ループ数の増加 に伴い精度が 良 くなっている｡ しか し,良い精度 を得 るためには多 くの総ステ ップ数が必要 で実行時間が長 くなって しまう｡ ここで も到達回数 と総ステ ップ数 を鑑みて, 初期 ループ数 には1

00

を設定す ることで80 回以上の到達回数 と妥 当な実行時間

を保つ こととした｡

表 5

:初期ループ数

R^,n

,

t

の調整

初期ループ数 R

^l,llt 50 100 150 200

到達回数

75 86 84 85

コス ト平均値

0.121 0.067 0.034 0.014

総ステップ数

194279 392876 589407 790658

最 後 に, 終 了基 準 につ い て考 察 を行 い た い｡ これ まで の 数値 実験 で は

S A/ AAN と同等の実行時間で実行 させ るために r<0. 1を終了基準 に用いて きた｡ しか し, コーシー分布型 S A の探索 における挙動 を観察すると,探索の 序盤ですでに最適解付近‑ と到達 しているものが多いことがわかった｡そこで, 終了基準 を適切 に設定することで最適解付近へ と到達す る性能を保 ったまま, 探索時間を短縮す ることを考 えたい｡通常の S A ,す なわち組合せ最適化で用 い られる S A で は解 の収束 に伴 い,解 の受理率 も 0へ と収束 してい く｡ この

S A の特徴 か ら受理率 を終了基準の要素 として考 えることとした｡通常の S A

において,受理率 は収束す る際に緩やかに減少 を続け 0に近づ くとい う挙動 を

とる｡そ こで, コーシー分布型 S A での受理率の挙動 を確認 した ところ,解が

収束 を示す ときの受理率 は 0か ら0.

05

の間で振幅 を続ける傾向が得 られた｡そ

のため,通常の S A で用 い られる受理率が基準値以下 を示す とき探索 を終了す

連続最適化問題に対するコーシー分布型

SAの提案 87

表

6

:受理率0.

05

の記鐸回数による変化

記録回数

100 150 200 250 300 350 400

到達回数

66 68 72 74 80 77 75

コス ト平均値

0.365 0.344 0.169 0,225 0.095 0.123 0,152

平均総ステップ数

23882 31443 38740 46779 56418 65957 71329

るとい うような基準 は使 えないことがわかる｡そこで,本研究では受理率が

0

か ら

0.05

の間で振幅す る状態 を解の収束 した状態 と考 え,受理率0.

05

を一定数 記録することを終了条件 に設定す ることとした｡そ こで,受理率0.

05

の記録回 数が一定数以上 となることを終了基準 とするとき,その記録回数の値が どれ く

らいの値 を設定すれば良いか調べ るため次の ような実験 を行 った｡その結果 を 表

6

に示す｡ これは,記録 回数 を1

00

か ら

400

まで50 ずつ増加 させた ときの到達 回数 と探索 の平均総ステ ップ数 を示す｡ ここでは,初期温度

Ti,ZiE‑40.0

,温 度減少率

phi‑0.8

,初期 ループ数

R"lit‑100

,ループ数増加率 t au ‑

1.3

とパ ラメー タを固定 した｡ この結果か ら,記録回数 を増加 させ ることによ り到達回 数は上昇す るがある点 を境 に減少す るような傾向が見 られ, ここでは記録 回数

300

の とき到達回数,平均 ともに最 も良い結果が得 られた｡終了基準 に ｢ 温度

T <0. 1 ｣と設定 した もの と｢ 受理率0.

05

を

300

回記録 したとき探索 を終了する｣

と設定 した ものを比べ ると,前者の到達回数 よ りは若干少 ないが,後者で も

80

回 と同程度に良い到達回数 を得 ることがで きた｡ よって,受理率0.

05

を一定数 記録 した とき探索 を終了す るとい う終了基準 は十分 に解の収束 を捉 えることが で きる基準であると考 えることがで き,その記録 回数は300 回で 目標 となる到 達回数

8

割 を得 られるo また, この とき探索の総ステ ップ数 も終了基準 を

T

<0.1

とした ときよ りも大 きく減少 させ ることもで きている｡以上 によ り,｢ 受 理率0.

05

を

300

回記録 した とき探索 を終了す る｣ ことをコー シー分布型

SA

の 終了基準 に用いることとした｡

以上の考察によって初期温度

TiniE,

初期 ループ数 Ri n i l ,温度減少率 phi ,ルー

プ数増加率 t a u の

4

つのパ ラメー タの設定 と終了基準の設定 を行 った｡ なお,

ββ 商 学 討 究 第59巻 第2 ･3号

本節では

Alpine

関数 を対象 としてパ ラメー タの設定 を述べたが,Ras

trigin関

数,2

"m inim a

関数で も同様 のパ ラメー タで到達 回数1

00

を記録 し,良い結果 を残す ことがで きている｡

次に,SA/AAN,一様分布型

SA

,正規分布型

SA

との比較 によってコー シー 分布 型

SA

の性 能 を評価 したい｡ ここで は

Alpine関数,Rastrigin関数, 2'〜minima関数の3

つのベ ンチマー ク関数について比較す る｡ まず,Al

pine関

数 についての比較 を行 う｡ この とき

,SA/AAN

の推奨パ ラメー タ設定は三木 らの論文 に示 された

Rastrigin関数 に対す るパ ラメー タ設定 を適用 した もの と

し,初期温度 T" l l / ‑1 0 ,初期 ループ数 R i m

/‑10000

,温度減少率 phi

‑0.8

,ルー プ数増加率 t au ‑ 1. 0 である｡ また,一様分布型,正規分布型 は予備実験 によっ て得 られた最 も良い結果 を残 した設定であ り,一様分布型 は初期温度 Tmi E ‑

100

,初期ループ数 Ri , l i t ‑1 00 ,温度減少率 phi ‑0. 8,ループ数増加率 t au

‑1.2

, 近傍の範囲

α‑20.0

である｡そ して,正規分布型は,ループ増加率 t au ‑ 1 . 3 , 標準偏差

or‑5.0

とし,その他のパ ラメータは一様分布型 と同様である｡なお, コーシー分布型については前節で先述 した とお りである｡表

7

にそれぞれの手 法 による

Alpine関数対す る100

回施行の最適解付近への到達回数, 平均 コス ト, 総ステ ップ数の平均,CPU時間を示す｡結果,SA/AAN は到達回数 0回で, 一度 も最適解付近へ到達で きなかった｡一様分布 は近傍の範囲を

α

‑ 1. 0 とし た ときは到達回数 0回であ り,近傍の範囲を調整 しα‑20 に広 げた上で,40 回 程度の結果であった｡ 同 じく,正規分布 も標準偏差

cr

‑1.

0

とした ときは到達 回数 0回であ り,標準偏差

0,‑5.0

とし近傍の幅 を広 く調整 した上で ( au ‑

1.2

と設定 した時は5

0

回程度 を得 られたo さらに ,l au ‑

1.3

とした時に60 回程度の 結果 を得 られたが,1

00

万ステ ップを超 える多 くのステ ップ数 を費やす もので あった｡Al

pine関数 は広 い近傍 を要求 しているが, コー シー分布型SA

は標 準型

(γ

‑1.

0)

の コー シー分布で80 回程度の到達回数 を得 ることがで きてお り, かつステ ップ数 も5

0000

ステ ップほ どの小 さなステ ップ数である｡ この結果か

ら, コー シー分布型はこの間題での探索能力が優 れてお り,かつ探索時間 も短

く優 れているといえる｡

連続最適化問題に対するコーシー分布型

SAの提案 89

表

7:AIpine

関数についての比較

手 法

SA/AAN

一様分布型 正規分布型 コーシー分布型

到達回数

0 46 66 80

コス ト平均値

0,0006 0,164 0.047 0.095

平均総ステップ数

310000 137273 1122635 56418

CPU 時間( 秒)

0.2868 0.1300 1.1000 0.0473

次 に,Ras

trigin関数 と2nminima

関数 につ いての比較 を行 うo ここで

Ras‑ trigin関数 は三木 らのSA/AANが解 の値 の精度 において よい結果 を残 してい

る問題 であ る｡ この とき推奨パ ラメー タ設定 は,SA/AAN は三木 らの論文 に 示 され た ものであ り,初期 温 度

Timl‑10

,初期 ルー プ数

Rmi^l‑10000

,温 度 減少率

♪hi‑0.8

, ルー プ数増加率

tau

‑ 1. 0である｡ また,一様 分布型,正規 分布型 は

Alpine

関数 と同様 に予備実験 によって得 られた最 も良い結果 を残 し た設定であ り,一様分布型 ･正規分布型 ともに初期温度

Timl‑100

,初期 ルー プ数

Ri,lit‑100

,温度減少率

phi‑0.8

,ループ数増加率

tau

‑

1.2

である｡なお, 一様分布型 は近傍の範囲 α ‑1. 0 とし,正規分布型 は標準偏差 c T ‑ 1. 0 とし, ど ち らも標準型 の近傍 の範囲 とした｡ コー シー分布型

SA

は

Alpine関数 と同 じ

設定 を用 いた｡表

8にそれぞれの手法 に よるRastrigin関数対す る100

回施行 の最適解付 近へ の到達 回数,平均 コス ト,総ステ ップ数の平均 ,CPU 時 間 を 示す｡また,表

9

に2'

lminima関数 に対す る同様 の比較結果 を示す｡この結果,

どの手法 もどち らの問題で も最適解付近‑ と到達 してお り,悪い結果 はでてい

表

8:Rastrigin

関数についての比較

手 法

SA/AAN

一様分布型 正規分布型 コーシー分布型 到達回数

100 100 100 100

コス ト平均値

0.0003 0.0079 0.0029 0.0260

平均総ステップ数

310000 137273 137273 47896

CPU 時間( 秒)

0.2653 0.0700 0.1200 0.0383

90 商 学 討 究 第59巻 第2･3号

表

9:2nminima

関数についての比較

手 法

SA/AAN

一様分布型 正規分布型 コーシー分布型 到達回数

100 97 99 100

コス ト平均値

‑156.664 ‑156.068 ‑156.647 ‑156.662

平均総ステップ数

310000 137273 137273 46561 CPU

時間( 秒)

0.2627 0.1400 0.1100 0.0334

ない｡ この中で もコーシー分布型

SA

は最 も早いステ ップ数で問題 を解 くこと がで きてお り, コー シー分布 による探索時間の短縮が伺 えるものであった｡

以上, 3 つの関数における比較 によって, コー シー分布型

SAが対象問題 に

かかわ らず最適解付近へ到達で きる高い探索性能を持 ち,少 ないステ ップ数で 探索 を行 え,探索時間で も優 れた手法であることが示 された｡特 に,Al

pine

関数では最適解付近‑ と高い頻度で到達で きてお り他 の手法 よ りも優 れてい た｡

さらに,本研究ではよ り早いステ ップ数で コス トの精度の改善 を行いたい｡

ここで,powe l l法 に改善が加 え られた修正

powe

l l法 [ 7]をコー シー分布型

SA

によって得 られた近似解 に適用す るとい う方法で, コス トの精度の改善 を試み ることとした｡この手法 をコ‑ シー +

powe

l l型

SA

と表記する｡SA/

AAN

,コー シー分布型

SA

, コ‑ シー

+powe

l l型

SA

のそれぞれで得 られ る解

(

∬

1,g2)

お よびその コス ト,総ステ ップ数 を比較 し, コ‑ シー

+powe

l lの性能 を確 か めたい｡ 3 つのベ ンチマー ク関数 を対象 としたそれぞれの手法の1

00

回試行 に おいて最 も良い コス トの精度が得 られた試行の結果 を,表1

0

に

Alpine

関数 に ついて,表11には

Rastrigin

関数 について,そ して表1

2

に2

'Zminima

関数 につ いて示す｡ なお, 2 節 において詳述 したが, Al

pine

関数 は最適解 ㌔

‑(0.0

,

0.0)

,最適値 毎( x

*

)

‑0.0

であ り

,Rastrigin

関数 は最適解

x*‑(0.0,0.0)

,最 適値 f R( r* )

‑0.0

で あ る｡ そ して,2

71minima

関数 は最 適解 x*疋(‑2.

90

,‑

2.90)

,最適値

fM(

x* ) だ‑1

56

である｡結果 をみると,すべての関数 においてコ‑

シー

+powe

l l型

SA

は最適解 に収束 した ことが確認で き, これ までの実験 で

連続最適化問題 に対するコーシー分布型SAの提案 91

は最 も良 い コス トの精 度 で あ ったSA/AANよ りも遥 か に良 い精 度 で あ った｡

コ‑ シー +powell型SAの総 ス テ ップ数欄 にお け る括 弧 内 の数 字 は総 ス テ ッ プ数 の 内powell法 の実 行 に費 や した反復 数 で あ る｡ どの 関数 にお い て も費 や され たpowell法 の反復 数 は数 回で あ り, これ はSA

と

powell法 のハ イブ リ ッ

表10:AIpine関数 についてのコス ト精度の比較

手 法

SA/AAN コーシー分布型 コ‑シー +powell塑 xlOf解(xl

, x 2 )

100.4307972

x 2

0f解(xl

, x 2 )

100.4307975 コス ト 0.0000288729 総ステ ップ数 310000

CP U

時間 (秒) 0.2868

ー0.000843162 0.0000000000

‑0.000803642 ‑0.0000000000 0.000163324 0.0000000000

81156 81159(3) 0.1100 0.1100

表11:Rastrigin関数 についてのコス ト精度の比較

手 法

SA/AAN コー シー分布型 コ‑シー +powell型 xlOf解(xl

, x 2 )

0.0000277932

x

20f解(rl

, x2 )

10.0000051192 コス ト 0.000000158449 総ステ ップ数 310000

CP U

時間 (秒) 0.2653

0.001098716 ‑0.000000000000 0.001272003 ‑0.000000000000 0.000560488 0.000000000000

47896 47899(3) 0.0383 0.0383

表12:2nminima関数についてのコス ト精度の比較

手 法

SA/AAN コー シー分布型 コ‑シー +powell型 xlOf解(2

1 , 3

2

)

12.903557744 12.90232112 ‑2.90353402307708

g

20f解(∬

1 , g

2

)

‑2.903552568 ‑2.903284721 ‑2.90353402810204 コス ト ‑156.6646628 ‑156.6646098 ‑156.6646628150857 総ステ ップ数 310000 47896 47897(1)

CP U

時間 (秒) 0.2627 0.0334 0.0334

9 2

商 学 討 究 第59巻 第2 ･3号

ト化 によって早い時間での解の収束が可能 となること, この ようなハ イブリッ ト化 は時間的な負荷の増加が小 さくてすむことを示す結果である｡ コー シー分 布型 SA は最適解付近へ到達す る可能性が高い手法であることは先述の比較で 示 した とお りであ り,コーシー分布型 SA と po we l l法 を組み合 わせたコ‑ シー +po we l l型 SA は最適解付近へ と到達す る高い探索能力 を有 し,対象 問題の 厳密 な最適解 を高い確率で得 られ,かつ,短い時間で探索 を行える手法である

ことが確認で きた｡

6. お わ り に

本研究では,連続最適化問題 におけるコーシー分布型 SA の もつ性能につい て 考 察 を行 っ た｡ まず, 連 続 最 適 化 問 題 に対 す る手 法 で あ る三 木 らの SA/ AAN で Al pi ne 関数 ,Rast ri gi n 関数 ,2 nmi ni ma 関数 を解 い たが, Al pi ne 関数では全 く最適解付近へ と到達す ることがで きなかった｡ また,逮 続最適化問題ではその近傍 に確率分布 を用い られるため,基本的な確率分布 と して一様分布,正規分布 に従 った近傍 を用いて

3

つのベ ンチマーク関数の最小 化 を扱 ったが ,Al pi ne 関数は特 に多峰性が激 しく難 しい問題であ り, 一様分布, 正規分布 を近傍 に用 いた SA で は SA/ AAN 同様 に うま く解 くことがで きな かった｡

そ こで Fas t SA で用 い られていた コー シー分布 に着 日し, コー シー分布 に

従 った近傍 を適用 した SA を構築す ることとした｡ コー シー分布 はその分布の

中心付近に解の次状態が生成 される確率が高 く解探索 における集中化が期待で

き, また,その裾の広 さか らロングジャンプを可能 とし解空間を広 く探索で き

る多様化の実現 を期待で きるものであった｡ さらに ,SA は精度の高い解への

収束 に時間を要す るとい う問題 を po we l l法 とのハ イブ リッ ト手法 を導入す る

ことで改善 に取 り組んだ｡次に ,SA の能力 を活かす ことがで きる SA のアル

ゴリズムに有効 な冷却スケジュールを決めるためにい くつかのパ ラメー タにつ

いて詳細 な実験 を行 い,適切 なパ ラメー タを提案 した｡ また ,SA/ AAN ,‑

連続最適化問題に対するコーシー分布型 S A の提案 9 3

様分布型,正規分布型の他の手法 との比較 を

3

つのベ ンチマーク関数において 行い コー シー分布型 S A の特徴 を解析 した｡その結果, コー シー分布型 S A は

Al p i n e 関数 において 1 0 0 回試行中 8 0 回程度の到達回数 を得 る高い探索能力 を持 ち,かつ,短い時間で探索 を行 えることが示 された｡ さらに, コーシー分布型

S A は Al p i n e 関数 だけではな く他 の関数で も最適解付近へ と到達で きること を確認で き,他の手法 よ りも高い探索能力 と探索時間の速 さの点で優 れている ことが確認で きた｡最後 に, コー シー分布型 S A とパ ウエル法のハ イブ リッ ト 手法 を用いて解の精度の向上 を試みた結果,すべてのベ ンチマーク関数で厳密 な最適解 を得 られ,そのために要する時間 も高々 3 ステ ップほどで非常 に短い ことが示 された｡そ してこれは S A/ AAN で得 られる解の精度 よ りも遥かに良 い精度であった｡以上 によ り,本研究の提案手法であるコー シー分布型 S A と

p o we l l法のハ イブ リッ ト手法 は,最適解付近へ と到達す る高い探索能力 を有 し,かつ早い探索時間で厳密 な最適解 をも得 られる可能性が非常 に高いアルゴ リズムであることを示す ことがで きた｡

ただ し,本研究で扱 った問題 は

3

つのベ ンチマーク関数ついてのみである｡

他の連続最適化問題の実問題など多 くの問題 に対す るコー シー分布型 S A の性

能や特徴 を調査す る必要があるだろう｡ また,今 回は 1 0 0 試行 中の到達回数 8 0

回 と優 れた結果であったが ,9 0 回 ,1 0 0 回 と探索能力 を向上 させ るために,新

たな近傍,アルゴリズムの改善 を考察 してい きたい｡ さらには, コーシー分布

型 S A のパ ラメー タ設定 は実験的に求めるには複雑 さと困難が伴 うものであっ

たため,これ らのパ ラメー タ設定の 自動化‑ も取 り組みたい｡ この ようなこと

を今後の課題 として研究 を進めてい きたい｡

94

商 学 討 究 第59巻 第2･3号 参 考 文 献

[1]S.Kirkpatrick

,

C.D.GelattJ

r

.,M.P.Vecchi:"OptimizationbySimulated Annealing",Science,Vol.220,Num.4598,pp,671‑680(1983)

[2]N.Metropolis

,

A.W.Rosenbluth,M.N.Rosenbluth

,AJ

ITeller,andE.Teller:

"EquationofStateCalculationsbyFastComputingMachines",Journalof ChemicalPhysics21:1087‑1092(1953)

[3]金久実 :｢ゲノム情報への招待｣(共立出版,1996)

[4]三木光範,廉安知之,小野景子 : ｢最適 な受理確率 を 目標 とす る適応的近傍 を 持 つ シ ミュ レー テ ツ ドアニー リング｣,情報処理学会誌 Vo

l , 4 4

No.1pp.1‑6

(2003)

[5]柳浦睦憲 ,茨城俊秀 : ｢組合せ最適化‑ メ タ戦略 を中心 として‑｣

[6]SZUH.,HARTLEYR.:"FastSimulatedAnnealing",PhysicsLettersA Vol.122Num.3,4pp.157‑162(1987)

[7]William H.Press,William T.Vetterling,SaulA.Teukolsky,BrianP.Flan‑

nery,｢NUMERICALRECIPESinC[日本語版]｣ (技 術 評論 社,1993) pp.299‑306

[8]Ya‑ZhongLuo,Guo‑JimTang,Li‑NiZhou:"Simulatedannealingforsolving near‑Optimallow‑thrustorbittransfer"EngineeringOptimization,Volume37,

Number2,March2005,pp.201‑216