探索領域適応アルゴリズムと進化アルゴリズムの組 合せ

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

探索領域適応アルゴリズムと進化アルゴリズムの組 合せ

大西, 圭

九州芸術工科大学

高木, 英行

九州芸術工科大学芸術工学部

http://hdl.handle.net/2324/4482120

出版情報：ファジィシステムシンポジウム講演論文集. 18, pp.449-452, 2002-08. 日本ファジィ学会 バージョン：

権利関係：

探索領域適応アルゴリズムと進化アルゴリズムの組合せ

Co m b i n i n g  A d a p t i v e  A l go r i t h m f o r  S e a r c h i n g  A r e a s  a n d  Evo l u t i ona r y  A l g o r i t hm 

大西圭 高 木 英 行

K e i  Ohn i sh i  Hi dey u k i  T akag i 

九州芸術工科大学

Ky u s hu I n s t i t u t e  o f  Design 

A b s t r a c t ‑We  pr o p o s e  a  new o p t i m i z a t i o n  method t h a t  c o m b i n e s  a l g o r i t h m  t h a t  a d a p t s   s e a r c h i ng a r e a s  (ASA)  and  evo l u t i o n a r y  a l g o r i t h m  ( E A ) .  ASA  i s  m a i n   s e a r c h i n g  e n g i n e  and  EA  exp l o i t s  w i t h i n   th e  s e a r c h i ng a r e a s  t h a t  a r e  d i s c o v e r d   and adapted by  ASA. We  e x p e r i m e n t a l l y  e v a l u a t e  t h e   p r o p o s e d  a l g o r i t h m  w i t h   s e v e r a l  be n chmark  f u n c t i o n s  and  d i s c u s s   i t s  s e a r c h i n g  c h a r a c t e r i s t i c s .  

ー はじめに

進化アルゴリズム

[ 2 ] (

以下

E A)

は，(

1 )

探索点をそれ らの持つ適応度に基づき競争させ，(

2 )

その競争に勝ち 残った探索点に確率的演算を適用して探索点を進化させ る．探索点に対する演算により新たな探索点を生成する ことの利点は，局所的な適応度ランドスケープ構造を考 慮した探索点生成を行えることである．一方，局所的な

2 

ランドスケープ構造を考慮した演算を有効に働かすため には，有望な探索領域に探索点を保持し，その数を解探 索の進行に伴って増やしていく必要がある．

従来の

E Aが抱える問題点は，探索点の分布の制御が

探索性能を決める大きな要素であるにも関らず，一般に は適応度に応じて保持する探索点を決定することや確率 的演算のために保持しておくべき探索点が消失してしま

う可能性を持つことである．

以上の一般的な

EA

の問題点に対して，過去の探索点 の分布を明示的な構造として学習し，学習で得た構造を 探索点生成に利用するアプローチが考えられる．学習に 用いられる構造として現在活発に研究が行われているも のは確率モデルである

[ 6 ] .

これは，現探索点の分布を ある確率モデルに従った標本化の結果と考え，実際に現 探索点の分布を説明可能な確率モデルを構築し，次の探 索点を構築された確率モデルに従い生成する．明示的な 構造として探索すべき領域情報を持つことにより，偶発 的な探索点の消失による探索性能の低下を防ぐことがで きる．このアプローチの探索性能は，構造学習能力に依 存する．

我々はこれまでに

EA

と構造学習を用いる方法の持つ 考え方を含む最適化の考え方を提案してきた

[ 4 ] . EA

と 構造学習を用いる方法の持つ考え方を含む最適化

[ 4 ]

と は，描造学習を用いる方法から探索領域を明示的な構造 として保持するという考え方を得て，

EA

から競争・進 化主体の持つを情報を利用して新たな競争進化主体を形 成するという考え方を得たものであり，これらの考え方 を合わせて探索領域情報を明示的な構造として持つ探索 点生成メカニズム（それが持つ探索領域内にそれ自身で 探索点を生成可能なメカニズム）を競争進化主体とする ものである． 探索点生成メカニズム自体を進化させる従 来の方法として

EA

の一つである(μ,入）ー進化戦略

( 1 ]

が ある．

以上の最適化の考え方に基づき実現したアルゴリズム

[ 4 ]

は，探索点生成メカニズムとして超直方体内にランダ ムサンプリングを行うものを用いた．このアルゴリズム

はサンプリング法を固定しなければ探索領域を超直方体 として適応させるアルゴリズムと捉えることができる．

本論文では探索領域を適応させるアルゴリズムにサン プリング法として

EA

を組み合わせたアルゴリズムを実 現し，ベンチマーク関数に適用して評価する．

2 . 1 

探索領域適応アルゴリズムと進化 アルゴリズムの組合せ

探索点生成メカニズムの競争進化に基づ く最適化

この最適化方法

[ 4 ]

は，探索点生成領域とその領域内 に探索点を生成する方法とを持つ様々な探索点生成メカ ニズムの問に競争進化を生み，その結果として探索すべ き領域とその領域内でのサンブリング法を獲得する，と いうものである．

この最適化方法における競争進化主体は，従来の

EA

や確率モデルを用いる方法が一般に探索点を競争進化主 体とするのに比べるとメタレベルのものである．しかし，

基本的には競争進化の原理として

EA

のような演算が利 用できる．また，メタレベルな競争進化主体であるがゆ えに確率モデルを用いる方法のように探索領域を明示的 に保持することができる．

探索点生成メカニズムの持つ探索点生成領域とその領 域内に探索点を生成する方法とを決めるバラメータを以 下では構成要素と呼ぶ．探索点生成メカニズムと構成要 素の関係は，

EA

における個体と迫伝子の関係，あるい は確率モデルを用いる方法における確率モデルとモデル パラメータの関係に類似するものである．例えば，

N

実 変数最適化問題のとき，各変数の値を乱数生成ルーチン により生成しようとすれば，乱数発生区間を決めるバラ メータと乱数生成ルーチンの種類が構成要素と呼べるも のになる．そして，探索点生成メカニズムは，各変数の 値を決める乱数生成ルーチンを組み合わせて

N

変数全 ての値（探索点）を決めることができるものである．

この最適化方法の基本的な流れ（図

l ( a ) )

は以下のよ うである．

(1)構成要素の集合を決定する．

( 2 )

構成要素を組合わせて様々な探索点生成メカニズム を構成する．

( 3 )

構成した探索点生成メカニズムで複数の探索点を決 定してそれらの適応度を計算する．

( 4 )

各適応度を当該探索点を生成した探索点生成メカニ ズムの描成要素に分配する．

( 5 )

分配された適応度に基づいて探索点生成メカニズム の構成要素を淘汰生成して新しい探索点生成メカニズム を再構成する．

( 6 )  ( 1 )( 5 )

を繰り返す．

さらに，以上の

( 1 )( 6 )

の手続きを一つの単位として 階陪的に適用する（図

l ( b ) ) .

最初はデフォルトの探索空 問に対して以上の

( 1 )( 6 )

の手続を適用する．ある段階 で探索点生成メカニズムの持つ探索点生成領域（デフォ ルトの探索空問よりも縮小した空問）を次の探索空間と

して同様の手続きを適用する．またさらにある段階で探 索点生成メカニズムの持つ探索点生成領域（さらに縮小 した空間）を次の探索空間として同様の手続きを適用す る，というように同手続を縮小していく探索空問に対し て適用していくことで精度の高い解が順次得られていく

ことを期待する．

( a )  O u t l i n e  o f  t h e  o p t i m i z a t i on p r o c e d u r e .  

<Initials● arching space > 

／ ／ こ 三

‑ 0   ‑ 0   ‑ 0 …  歴之三~¾ニフ乙~ _{o o     . . , o o   . . .  oo,    . .} … 

戸"~ デ .' . . デ デ . . _~~ .  .  … 

( b )  H i e r a r c h i c a l  s e a r c h i n g .  

図

1 : Opt i m i z a t i o n  b a s e d  on  c o m p e t i t i o n  a n d  e v o l u t i o n  amo n g  m e c h a n i s m s  t h a t   g e n e r a t e  s e a r c h i n g   p o i n t s . 

2.2  探索領域適応ア ルゴ リ ズム

第

2 . 1

節に示した最適化の考え方に基づいた数値最適 化問題のためのアルゴリズムの流れ（図

2 )

を以下に説明 する．このアルゴリズムは，探索点生成メカニズムが持 つ探索点生成領域内でのサンプリング法は固定しないも のであり，サンプリング法を任意のものにすることがで きる．ここに示すアルゴリズムは探索領域を適応させる ものと捉えることもでき，以下ではこれを探索領域適応 アルゴリズム

(ASA)とよぶ．文献 [ 4 ]

で提案したアル ゴリズムは，サンブリング法としてランダムサンプリン グ法を用いたものである．

以下の説明では

N

変数最適化問題を想定する．説明に 出てくる

N c,Nm,Ns,N p , L , l ( , Rmaz 且 min,Rrc,Rrs,Pm

はアルゴリズムの持つバラメータである．

( 1 )

構成要素の初期化

構成要素は第

2

節の定義ではサンプリング法を含む探

索点生成メカニズムを構成するものであったが,

ASA

は サンプリング法を固定しないものであるので，ここに示 す構成要素は探索点生成領域情報しか持たない．

各変数の値を生成する区問を決めるバラメータ（区 問の中心となる座標と区問の大きさ）が構成要素であ る．構成要素の数は各変数につき

Ne

個である．区問 の大きさは，まず各変数

( x , , i  =  1 ,  2 ,  ・  ・  ・ ,  N)

の定義 域の大きさ

(S 這 = 1 , 2 , ・ ・・,N)

に対する比の最大と 最小

(Rmax E  ( 0 ,   1 ) ,   凡 n i nE  ( 0 ,  1 ) )

を用いてその範囲

([RminSi, Rmax

ふ］）が定められ，次にその範囲内でラン ダムに値が生成される．区問の中心は各変数の定義域内 にランダムに生成される．

( 2 )

探索点生成メカニズム構成

探索点生成メカニズムは，探索点である

N

変数の値 を同時に決定できる仕組みである．ここでは構成要素を 変数毎に一つずつ無作為に選びだし組み合わせて

1

個の 探索点生成メカニズムとする．探索点生成メカニズムの 持つ探索点生成領域は超直方体内部となり，その領域内 に任意のサンプリング法が利用できる．構成される探索 点生成メカニズムの数を

N m

個とする．

( 3 )

探索点生成・適応度計算

N m

個の探索点生成メカニズムそれぞれが凡個の探 索点を生成し，それらの適応度を計算する．

( 4 )

探索点生成メカニズムに適応度を付与

各探索点生成メカニズムで生成した探索点の適応度か らそのメカニズムの適応度を算出する．ここでは各メカ ニズムが生成した探索点の適応度のうち最良のものをそ のメカニズムの適応度とする．さらにそのメカニズムを 構成する構成要素の区問の中心を最良適応度を持つ探索 点座標に合わせる．

( 5 )

定めた数の探索点を生成したかを判定

予め定めた探索点数

Np

が生成されたかを判定する． その数に達していなければ次の

( 6 )

の手続きに進む．そ の数に達していれば，それまでに得られている適応度上 位

L

個の探索点生成メカニズムがカパーする探索領域を それぞれ次の探索空間として，手続き (1)から同じよう に手続きを実行する最初の探索空間での探索を第

1

階 屈とすると

,L

個の探索空問での探索は第

2

階層となる．

L

個の探索空問に対して同様な手続きを実行し，そのそ れぞれにおいて，最良探索点生成メカニズムがカバーす る探索領域を次の探索空間とする．これが第

3

階恩とな る．このような手続きを第

k

階屈まで繰り返す（図

3 ) . ( 6 )

構成要素に適応度分配

探索点生成メカニズムに与えられた適応度をその構成 要素にも直接与える．

( 7 )

構成要素の選択

各変数について適応度上位

N e

個の構成要素を選択 する．

( 8 )

構成要素の変形

現在の区間の中心と大きさをそれぞれ

c ,s ,  

変形後 の中心と大きさをそれぞれ

c ' , s '

とすると，等式

c'=

c  +  ^{u(‑r c ,   r e ) ,   s}  =  s  +  ^{u(‑rs,  r s )}

により確率

Pm

で 変形が行われる．ただし，

u ( a , b )

は，区問

[ a , b ]

内の一 様乱数である．等式中の

rc,rs

は，手続

( 1 )

において 構成要素である区問の大きさを決めるのと同じように 各変数（叩，

i =  1 ,  2 ,  ・  ・  ・ ,  N)

の定義域の大きさ

( S i , i  = 

1 ,2 ・ , ・ ‑,N)

に対する比

(RrcE  [ 0 , 1 ] ,  

尼

E [ O ,  l ] )

を用

いて

re=

凡ふ，

TS=

凡 ふ と 決 め ら れ る．

( 9 ) ( 2 )

に戻る

(1)  (2) 

弓:‑:.ヰ．一

I  !  : 

.  i

「 ―

I . i .    

Ii 

.. 

！

：  

1 1 ~

••••••••••

••

• •

‑

r 

•

••

． , 1 

~...L

.. •

, L 

••

~

•3[

ii

—

-

. .  

5‑

竺

i

‑

••

~i

ai2g

igi•

~i

き i -

_.

. . .  ‑ i‑

‑﹃9

‑ ‑ f ii

‑

﹃5i

i

竺

~)-

一世 ︶ 立

・・

1 2 .

‑ t

.

・

‑

．

．

． ︳ ． ．． 

ー

・

・1

‑

．1

..

. ̀ 

． ．  

︑ . ̀

︑ ̀

.••

︑．

9[ 

•.  ..•

t , ．

‑

． ．  

, ．

 

~~-·_iii・

••

••••

••••••••••••••

． •••

．  

・

・ 一

."~

． ．  

•Y.

.・・・・・・・・・・........   .・

; (2・1).... .,. 叩 呪,.,... ,,.,.  : 

： 四

' ' " ° " ' , ̲ , , . , . , . , . " " o n :

＇

 

^: ',,.,.,.,,_,._,,,.m«>匹•^._ヽ・(2•2)YM<f<ng.,,.., .‑・_.・_. 一^" "_.一^"_...^"一•一^"• ^"..^一•"一•• ^"一• .^"一.一・

．  _．  ． 

・^"‑.・^"・一.^"一•^'..・^'•  ・

,,"o •

一‑^"・.・一.^""一・^"・・・‑^"‑・、^"

 

 

＇

: (2·K)U"""'O"""'""'P><• •

,  . , . ,  .  . . , ̲ , . . , , , .   ・ ・

 _＇

‑・・‑・・ 一..一..一..一..ー・•一•• 一・・‑

み合わせたアルゴリズム（以下

ASA+RS)[4], ( 3 )

実 数値

GA(

以下

RG A ) (

世代交代モデルに

Mi n i m a l Gen ‑ e r a t i on  G a p [ 7 ]  

(以下

MGG),

交叉演算に

B LX‑ a [ 5 ]と S i m p l e x [ 3 ] ,  

突然変異に一様乱数，を用いるもの），の

3

つである

．

提案アルゴリズムのサンプリンゲ法として用いられる

EA

は実数値

GA(MGG, BLX

心交叉，一様乱数突然変 異）とする．

ここで用いられる全てのアルゴリズムは各ベンチマー ク関数に対して初期乱数値を変えて

5 0

回適用される.

1 

回の実行は適応度を

2 . 5

X 106回計算したところで終了 する

．各アルゴリズムの持つパラメータの値を表 2

に 示す．

Rnn_!<_• ^of vndnble● 

図

2 :

The flow of the adaptive algorithm for searching areas. 

1st 

~~ 匹 四 心 坪 ン

／ 弓 三

³ 

之こニプ乙二ニァ．．．之ニ

I  I 

3<d hle<archy 

I  I 

‑::::::=;7  L二':::;? ‑::::::=;7  L二＝プ

I  I  I  I 

:  :  :  ： 

I  I 

^Kth h如a向

I I 

, C 7 ~ ア ‑ ‑ = ァ <

図

3 :

The procedure (5) in the algorithm flow. Parallelogram m  the figure represents a searching space. Arrows in the figure mean  that a searching space 1・lims  ited after the number of searching points  generated within current searching space reaches to given number. 

2 . 3  提案アルゴ リ ズム

第

2 . 2

節に示した

ASA

は，探索点生成メカニズムの 持つ探索点生成領域（超直方体）内でのサンプリング法

（手続き

( 3 )

の部分）として任意のものを用いることがで きるものであり，提案アルゴリズムは

ASA

のサンプリ ング法として実数値

G A

や進化戦略などの

EA

を用いる ものである．

サンプリング法としての

EA

は全ての探索点生成メカ ニズムに用いられるわけではなく，確率Peaで用いられ る.

EA

がサンプリング法として用いられない場合，ラ ンダムサンプリング法が用いられる.

EA

が用いられた 場合，個体数は

P

とし，適応度を

S

回計算したところで 終了する• ^Pea, 

P, S

はアルゴリズムパラメータである．

ー ． 

3 3  

ベンチマーク関数を用いた評価

実験条件

評価に用いるベンチマーク関数は，表

1

に示す

4

つ

( F l F 4 )

である．変数の数

N

は

2 0

とする

．

評価に用いるアルゴリズムは，

( 1 )

提案アルゴリズ ム（以下

PA), (2)ASA

にランダムサンプリング法を組

z;  E {‑600, 600) 

召 E{‑2.048, 2.048)  z; E {‑6.12, 5.12) 

町 E{‑500, 500) 

表

2 :

Values of the algorithms parameters for experiments.  parameter  used value 

Common parameters for PA and ASA+RS. 

Ne  lOOOO(F(Fl)l , 200(F2(F),2  200(F3J;‑(F3 10訓F4(F)4  N m   10 ), 1000  }, 500  }, 500 ) 

N,  5 

ダ

P

5 X 105  2 

K  3 

Rma.z, Rm,n   （(O.l, 0.02)  R

… ,  

^{Rr.,  0.2, 0.02)} 

Pm  0.01 

Parameters for PA. 

P•• 0.01 

p  40 

s  ¹⁰⁰⁰ 

Parameters for RGA. 

Pop. size  500 

O<  0.36 (parameter of BLX‑cr crossover)  Mut. rate  0.01 

3 . 2   実験結果と考察

実験の結果を表

3

に示す．比較対象の

RGA

は

2 種類

の交叉演算を用いているが，表3には最終的な最良適応 度の平均値の良い方を用いた交又演算とともに示した．

表

3

に示した実験結果から以下では，(

1 )

探索点生成 領域決定法と探索性能の関係，

( 2 )PA

と

ASA+RS

のサ ンプリング法と探索性能の関係，について考える．

( 1 )

探索点生成領域決定法と探索性能の関係

PA

と

ASA+RS

は探索点生成領域は探索点生成メカ ニズムが明示的に持つ．これらの方法は最適解を含む近 傍を全ての階屈で探索点生成メカニズムが保持しなくて はならない．これに失敗すると局所解を得ることになる．

RGA

は探索点を引数として探索領域が決定する．この 方法は探索点が最適解近傍に集まってきたとき，探索点 がさらに最適解に近い領域へ高い確率でシフトするよう な交叉演算が必要となる．以上のことを踏まえて個々の ベンチマ

ーク関数に対する結果を考える．

F l

は大局的に見ると変数間に依存関係のない単峰性

表 3: Results of the experiments. This shows the average of the best fitness values (Mean) and the standard deviations of those (SD) at  , 10, 

5 x 10  1.5 x 106, 2 x 106, and 2.5 x 10  iterations. The average of calculation times for one implementation (Time) is also shown. 

F¥inc. I Al,o.  I  lot(5 X 10°)  I 2nd(l.0 X 10")  I 3^『d(l5 x 10")  I 2nd(2.0 x 106)  I 3^『d(2.5X l  Time!•]

I  L‑1  I  L‑2  I 

PA  Mc~n 1 8160 X 10‑L  2.4623 X 10‑a  1 3811 X 10‑S  11.1883 X 10 ゴ l 4864 X 10 ~4 60  SD  ² 9992 X 10‑S  1.3795 X 10‑5  1 0243 X 10‑S  2.5436 X 10‑6  1.0723 X 10‑6  Fl  ASA+RS  Mean  1.0760  1 1926 X 10‑2  1 0469 X 10‑3  l 4990 X to‑3  5.5076 X 10‑6  52 

SD  1. 1469 X 10‑4  7.4330 X 10‑5  2 3087 X 10‑5  1 0075 X 10‑S  2 5478 X 10ー11 RGA  Mco.n  1.1336 X 10‑S  1. 1338 X 10‑S  1.1336 X 10 ‑s  1.1336 X 10 ‑3  1.1336 X 10 ‑3  62  (BLX‑a)  SD  1 0010 X 10‑5  1 0010 X 10‑5  l 0010 X 10‑6  1 0010 X 10‑S  1.0010 X 10‑5 

PA  Mca.n  3.4181 X 10‑i  1.9411 X 10‑l  1.8696 X 10‑1  1.7632 X 10‑1  1 . 7 3 4 0 X 1 0 ー

一

⁴¹ 

SD  9.5317 X 10‑2  2 6740 X 10 ‑2  2.5244 X 10 ‑2  2.4204 X 10‑2  2.3461 X 10‑2  F2  ASA+RS  Mea.n  1.7670  1.1377 X 10ー1 4.0896 X 10 ‑I  3.9239 X 10ー1 3 9055 X 10‑l  36 

SD  ⁵ 3804 X 10‑2  4 8452 X 10‑2  1. 7980 X 10 ‑2  4.8066 X 10‑2  4.8047 X 10‑2  RGA  Mean  2.7754  1.6606  1.1491  ⁶ 6096 X 10‑I  6.6892 X 10‑l  286  (Simplex)  SD  1.2391 X 10‑t  4 11596 X 10-~ 1.8881 X 10 ‑2  1.0857 X 10‑2  7 6419 X 10‑3 

PA  Meci.n  4.6009  4.3181  4.3181  4.3181  4.3181  54  SD  2.8663  2.8366  2 8366  2.8355  2.8365 

F3  ASA+RS  Menn  6 4971  1.2604 X 10‑l  1.2268 X 10‑l  6.2049 X 10 ‑2  6.1777 X 10 ‑2  42  SD  ⁶ 0063 X 10‑l  1 0380 X 10‑l  1.0399 X 10‑I  6.6767 X 10 ‑2  5.6796 X 10 ‑2  RGA  Mean  le^●● Lhon 10 ー18 le●● lhn.n 10 ー18 le●● lhnn 10 ー18 le●● t.hAn 10‑18  le●● than 10‑18  53  (BLX‑a)  SD  le■‑thn.n 10 ー18 Jc●● tha.n  10 ー18 le^●● than 10 ー18 le●● thn.n 10 ー18 le●● thn.n 10 ー18

PA  Menn  ⁶ 2098 X 10‑,  7.7818 X 10-~ 6.1288 X 10‑ 6.0398 X 10 ~ 5 9837 X 10―  58  SD  7 9855 X 10‑4  2 7202 X 10‑9  1 412 X 10 ー15 8.16 X 10 ー16 6.70 X 10‑16  F4  ASA+RS  Mco.n  27 1536  1.2115 X 10‑2  1 0169 X 10‑5  1.0169 X 10‑S  4.9315 X 10‑6  so 

SD  13.0297  4 0692 X 10‑6  1.0018 X 10 ‑0  1.0048 X 10 ‑9  4 9254 >< 10ー13 RGA  Mean  5.6132 X 10‑7  ts.5132 X 10 ‑7  6,6132 X 10― 7  !5.!5132 X 10― 7  6.5132 X 10‑T  57  (BLX‑a)  SO  Je^●● thn.n 10 ー18 le^●● thnn 10 ー18 le^●● thnn 10 ー18 le^●● thnn 10‑18  le^●● tho.n 10 ー18

状であるが，局所的に見ると振幅の小さな激しい振動が

4 

ある.R G Aは，BL X‑a交叉が大局的ランドスケープに

まとめ

適合しているため初期の収束は速いが，局所的なランド スケープに交叉演算が適合していないため最終的な解の 精度は他の手法より低い．一方， P AやA S Aは階層的 に最適解近傍をメカニズムが捉え続けたことで解の改善 が行なわれたと考えられる．

F 2は変数問に強い依存関係のある単峰性関数である．

Simplex交叉はこのランドスケープに適合したものであ るが，有効に働くかどうかは演算を施す探索点の選ばれ 方に依存する．この依存関係が今回はP AやA S A + P A

の持つ最適解近傍をメカニズムが捉える難しさよりも強 く働いたと考えられる．

F3とF4は局所解の分布は異なるものの最適解近傍は 変数間に依存関係のない単峰性状であり，R G AのBLX‑

a

交叉が有効に働いている．これらの関数に対しては

R G Aのサンプリング法に無駄が少なく収束の速さや解

の精度ともに他の手法より優れていると思われる.F 3  

に対しては， P AとASA+RSの最適解近傍の保持の失 敗が観察されている．

以上の考察には競争進化主体の多様性維持についての 観点が抜けている．特にP AやASA+RSは多様性維持 に関連したアルゴリズムバラメータを多く持ち

，そのバ

ラメータ値に探索性能が依存することを今後考える必要 がある．

(2)P AとASA+RSのサンプリング法と探索性能の関係 全体的に見てP Aはサンプリング法にE Aを達入した ことで初期の収束特性がASA+RSに比べて良い．一方 で最適解近傍を含まない探索領域をE Aによって探索し，

その領域を高く評価してしまった結果，早い段階で局所 解に陥ってしまうケース(F3)があった．ある探索領域 の有望さ（最適解を含む領域であるかどうか）を見積も るのに適したサンプリング法は実際のところ適応度ラン ドスケープに依存すると考えられる．

本論文では，探索領域適応アルゴリズムと進化アルゴ リズムを組み合わせた数値最適化アルゴリズムを提案し，

ベンチマーク関数に適用して評価した．また評価実験の 結果から最適化の方法論と探索性能の関係を考察した

．

参考文献

[ l ]  

T. B批k and H.‑P. Schwefel, "Evolution Strategies 1:  Vari‑ ants and their computational implementation", G. Winter,  J. Prieaux, M. Gal and P. Cuesta, editors:  Genetic Algo‑ rithms in Engineering and Computer Science, pp.127‑140,  Wiley, Chichester, 1995. 

[2]  T. Back and H.‑P. Schwefel, "Evolutionary Computation: An  Overview", in Proc. of the Third IEEE Conf. on Evolutionary  Computation (ICEC'96), pp. 20‑29, 1996. 

[3)樋口陥英，筒井茂義，山村雅幸，"実数値G Aにおけるシンプレッ クス交叉の提案",人工知能学会誌， Vol.16,No.l, pp.146‑155,  2001. 

[ 4 )

大西圭，商木英行， 探索点生成メカニズムの進化に基づく最適 化",MPSシンポジウム（進化的計窮シンポジウム2001)論文集，

pp.187‑192, 2001. 

(5)小野功，山村雅幸，喜多ー， 実数値G Aとその応用＂，人工知能学 会誌，Vol.15,No. 2, pp.259‑266, 2000. 

[6]  M. Pelikan, D. E. Goldberg, and F. Lobo, "A Survey of Op‑

timization by Building and Using Probabilistic Models", II‑ IiGAL Report No.99018, Illinois Genetic Algorithms Lab.,  Univ. of Illinois at Urbana‑Champaign, Urbana, IL, 1999. 

[ 7 ]

阻附告，収野功，小林重信， 遺伝的アルゴリズムにおける世代交代モ デルの捉案と評価＂，人工知能学会 誌，Vol.12,No.5, pp.734‑744,  1997. 

問い合わせ先

〒

815‑8540 福岡市南区塩原4‑9‑1

九 州 芸 術 工 科 大 学 芸 術 梢 報設計 学 科 高木 英 行

Tel&FAX  092‑553‑4555 

E‑mail  takagi◎ kyushu‑id.ac.jp