Real-Coded Genetic Algorithms-UNDX and SPX

86



2006



06

 

Real-Coded Genetic Algorithms-UNDX and SPX

  

1

!#"$&% ')(*,+-,.,/10,2

(Genetic Algorithm:GA)

3465 7)8 *69):;)<>=@?).BAC)D)E&/1;>:;)<>=@?).F6G)HBI CD)E /1;,:;)<,=)?.F,AJ)KL 3MNO AP

0

QR

1

3,ST6U FVW X1Y,HI6Z[,ZP)CDE /1;,:;<,= ?). 3\] A^_6`a,b6X1Y,H)96c 3)def `)G,ghP@i j6kl 4)mn6de63o)p6q CD)E&/1;,:;)<6=B?).)rs t 3 Auv qw Zx6I>Z R `yzLPB{ l)| :;)<,=B?).

r{)}&ZL)} t I~{ l| :;<6=B?.F6A

M)N)O A{ l ,€ U -FVW XY,HI { l)|

GA

3 +z->>/h062BA Rƒ‚ Xz„BGBHBI†…>‡zFBP1ˆ ‰BŠ F>Az{ lB|

GA

3~‹ V)*>9zŒB)ŽB q

SPX(Simplex

Crossover: SPX )

1)



UNDX(Unimodal Normal

Dis-tribution Crossover: UNDX)

2)

q@‘

x’L^’_“’”,r• – J6HI

2

SPX

—

UNDX

˜ ™ š ˆ ‰Š F6AP@›)œ&X1Y R)ž)O63 tŸ )¡ ‹6q¢ H ž O r@£¤’J¥H@Ž’¥A

MGG(Minimal Generation Gap)

r¦)x,HI

MGG

 A

1

§¨ª©

2

‘,3«žO  ›)œ žO l¬ 3žO­63® [,¯

,

4,°

1

žO ± ?²?.-; ³ T6U £¤ q´ g£,µY R

1

žO r  ¡ ‹,q¢ J>I

2.1

¶·¸,¹º»¼½¾

(SPX)

¿À Á ?> ³ T €Bà Œ’

(Simplex Crossover: SPX)

A@P Ä)Å6Æ [6¯Ç l 3ž)O rÈ,É6Z1P@È6É,Z R)žO63 ¬)Ê [ ¯ 7Ë’Ì l r@͒›ÎX~ϒРZ~x ž’O r@›’œ’J,H@Œ’’F¥G HI

SPX

3 +-,,/10,2AÑÒ 3´ t q 9HI

1.

ÄÅ,Æ [,¯

(n+1)

ž,3«ž)O

−

→

P

0

,

−

P

→

n

r ± ?Ó2 q £Ô,I

2. (1-1)

Õ,q Z R y`L «žO,3Ö×

−

→

_G

rØ,ÙHI

~

G = (

n+1

X

i=1

~

P

i

)/(n + 1)

(1-1)

3.

Õ

(1-2)



(1-3)



(1-4)

[,¯P

−

→

x

k

,

−

C

→

k

r

k=0,

Ú

,n

q‘ x)L)Ø6Ù)HI

e

AÛ 3Ü ±)Ý ;6ÞF)ß)à)á

(Ex-pansion Rate)

 ´ Ô¥I

e

3â’ã | A

√

n + 2

F,G g

,

… 3)®)3

n

A kl 3)ä l F6G)H)I

−

→

x

k

A)å)æ

[0,1]

3 7)Ë ¬)Ê Ì l

u(0,1)

r

(1-3)

Õ F)ç)è&Z1Lé&¯1Y H Ì l F,GHI

~

x

k

= ~

G + e( ~

P

k

− ~

G), (k = 0, 1, ...n)

(1-2)

r

k

= u(0, 1)

1

k+1

_{, (k = 0, 1...n − 1)}

_(1-3)

~

C

k

=

(

0, (k = 0)

r

_k−1

(~x

_k−1

− ~

x

k

+ ~

C

k−1

), (k = 1, ...n)

(1-4)

4.

Õ

(1-5)

q Z R y`L žO r›œJ,HI

~

C = ~

x

n

+ ~

C

n

(1-5)

QR P

Fig.1

q

SPX

q´ H )žO ›œê,ërìJ>I

2

2

2

)



e

GP 

Fig. 1 SPX(

Éí#îðïñòó

1

´ g ä ¦

)

2.2

ôõö÷ø)ùú½¾

-UNDX

¿À

UNDX

A Ä)Å>Æ [>¯

3

‘)«)žBO63zž)O r ± ?BÓ)2 q È É,ZP

Fig.2

q ìJ ´ t q,û‘«žO rü,„ýþÿ 3® ×

,q Û
 ¬)Ê q Z R `yzL)P ± ?Ó)2 q ˆ)* û1‘ 3O r›œ)J,HI žO

−

→

C

1

,

−

C

→

2

AÑ)Ò 3´ t q 9HI

~

C

1

= ~

m + z

1

e

~

1

+

P

n

_k=2

z

k

e

~

k

~

C

2

= ~

m − z

1

e

~

1

−

P

n

k=2

z

k

e

~

k

(2-1)

~

m = ( ~

P

1

+ ~

P

2

)/2

(2-2)

z

1

: N (0, σ

2

1

); z

2

: N (0, σ

2

2

)

(2-3)

σ

1

= αd

1

; σ

2

= βd

2

/

√

n

(2-4)

~

e

1

= ( ~

P

2

− ~

P

1

)/| ~

P

2

− ~

P

1

|

~

e

i

⊥ ~

e

j

(i, j = 1, ...n)

(2-5)

z

1



z

2

AÛ
 ¬)Ê 3 ± ?)Ó)2 l F6G)H)I

d

1

A

P

1

[ ¯

P

2

Q F 3 P

d

2

A  3«’žO

P

3

[,¯

P

1



P

2

 « rüÔ Q F 3 F,GHI QR P

Fig.2

q

UNDX

q´ H )žO ›œê,ërìJ>I

1

Y

X

P1

P2

P3

d1

d2

Fig. 2 UNDX(

Éí#îðïñòó

2

´ g ä ¦ ­

×

UNDX

SPX

Function

Benchmark function

Initial Population Size

300

300

Dimension of Function

10

10

Parents Size

3

11

α

0.5

×

β

0.35

×

Children Size

100

100

Threshold

10e-7

10e-7

Termination of evaluation

6e+6

6e+6

Trials

5

5

Table 1

Ü ±Ý ;,Þ;

3

SPX

—

UNDX

˜



 ˜



3.1

  { Ü ±Ý ;,Þ;,A

Table 1

F,GH

.

Ñ)Ò 3q A. ± 3 ,A l

,

 ,A k l| rì ZLx,H

.

3.2

SPX

 !

1. E- 08

1. E- 06

1. E- 04

1. E- 02

1. E+00

1. E+02

1. E+04

1. E+06

1. E+08

0 1E+06 2E+06 3E+06 4E+06 5E+06 6E+06 7E+06

Ros enbr ock

Scal ed_Ros enbr oc

Rot at ed_r as t r i gi

Ras t r i

i n

g

Fig. 3 SPX

3 {ü"

(

Éí î$#&%

)

Fig.4

q A…)Y')Y 3 kl q)( J6H{)ü"6rì)J

.

{  3 ü"

,

c 3 kzl F 5

,SPX

A 465)°)* 9)+>r^)_)F-, R

.

X)¯ q

,Scaled Rosenbrock



Rotated rastrigin

r¦ xL

,

./0 rç1 ZL 54,5)°* 9+,rØ,ÙH‡  ` F,H

.Rastrigin



Rotated rastrigin

q •K’L

Rosen-brock



Scaled Rosenbrock

A2 ‚°)* 9)+Ø,Ù)H‡ 

.

3.3

UNDX

 !

1. E- 08

1. E- 06

1. E- 04

1. E- 02

1. E+00

1. E+02

1. E+04

1. E+06

1. E+08

0. E+00 2. E+05 4. E+05 6. E+05 8. E+05 1. E+06 1. E+06

Rot at ed_r as t r i gin

Ras t r i gi n

Ros enbr ock

Scal ed Ros enbr ock

Fig. 4 UNDX

3 {ü"

(

Éí î$#3%

)

{4’ü4" q’´ yL>P

UNDX

A k@l 3  45’l `

10

3 6

,Rosenbrock

kl A ° x+)Ø,Ù)H‡  `F, R ‡  ` 7 [)H

.

ZP

Rastrigin

kl A89 3 kl 3R ÙP 4 5°* 9+,rØ,ÙH‡  `F,9[y R

.

3.4

UNDX

¿

SPX

:;

1. E- 08

1. E- 06

1. E- 04

1. E- 02

1. E+00

1. E+02

1. E+04

1. E+06

1. E+08

0

0.5E+06 1E+06

2E+06

2E+06

3E+06

3E+06

4E+06

UNDX-Rosenbrock

UNDX-Scal ed_Ros enbr ock

SPX - Ros enbr ock

SPX-Scal ed_Ros enbr ock

Fig. 5

• – ü"

(

Éí î$#3%

)

UNDX



SPX

r

Rosenbrock



Scaled-Rosenbrock

q k ZL’• – Z R

.UNDX



SPX

5 c Ÿ ¯ 54¥5°<* 9+,rØ,ÙH‡  `F-,H

.

=
>
?
@

1) Takahide Higuchi,Shigeyoshi Tsutsui,Masayuki

Ya-mamura.Simplex Crossover for Real-Coded Genetic

Algorithms.

AIC Vol.16, No.1 ,p146-155 (2001).

2) Isao Ono, Shigenobu Kobayashi

I

A Real-coded

Ge-netic Algorithm for Function Optimization Using

Unimodal Normal Distribution Crossover

ICGA’97

No.1249 (1997)