並列差分進化法を用いた画像処理

卒業研究報告書

題目

並列差分進化法を用いた画像処理

指導教員

石水 隆 講師

報告者

11–1–037–0057

渋谷 俊樹

近畿大学理工学部情報学科

平成

24

1

31

概要

近年

,

PC

PC

.

,

,

CPU

る

.[3].

,

レッドは同時に実行される

.

,

,

.

並列プログラムによる高速化が求められる分野には様々あるが

,

.

,

.

,

.

そこで

,

,

.

(GA : Genetic Algorithm)

,

,

,

,

.

差分進化

(DE : Differential Evolution)

,

たとした進化計算の一種である

.[4] DE

,

,

1

.

,DE

.

,DE

,

,

.

このように進化計算

,

,

.

,

,

.

,

.

本研究では

,

DE

,

(PDE : Parallel Differential Evolution)

.

,

,

.

,

,

DE

.

目次

1

1

1.1

. . . . 1 1.2

. . . . 1 1.3

. . . . 1

2

2

2.1

. . . . 2

3

3

3.1

(DE) . . . . 3 3.2

(PDE) . . . . 4

4

5

4.1

. . . . 6 4.2

. . . . 6

5

6

6

7

7

7

謝辞

8

参考文献

9

付録

A

10

.1 DifferentialEvolution

. . . . 10

.1 LocalDifferentialEvolution

. . . . 22

.1 MonochromePicture

. . . . 28

1

1.1

近年

,

PC

PC

.

,

,

CPU

ある

.[3].

,

レッドは同時に実行される

.

,

,

.

並列プログラムによる高速化が求められる分野には様々あるが

,

.

,

.

最適化問題に対する手法には

,

,

,

,

,

,

,

.

,

,

,

.

,

.

しかしながら，制約条件が多い場合には問題の定式化が困難となる．そこで，これらの問題を解決する手法 として，生物進化をヒントに得た探索手法である進化計算を用いることが近年注目されている．遺伝的アルゴ

リズム

(GA : Genetic Algorithm)

法では高速計算機を用いても数十年かかるような問題や

,

差分進化

(DE : Differential Evolution)

,

たとした進化計算の一種である

[4]

DE

,

1

,DE

,DE

,

,

1.2

前節で述べたように，ように進化計算，取り分け差分進化計算は有用性が極めて高いため，並列化により高 速化することは重要である．しかし，従来の従来の進化計算の並列化手法は

,

本稿では画像の類似性を視覚的に認識することで

,

DE

.

,

,

.

1.3

以下に各章の簡単な構成を示す

.

まず第

2

3

4

5

6

7

2

最適化問題は

,

,

,

1

.

,

.

,GA

DE

.[5]

,

DE

PDE

.

,

,

.

2.1

最適化とは複数の選択肢から最善のものを選ぶことであり

,

,

,

f(x)

x

.

x

,

1

,

.

(1)(2)

.

目的関数

f(x)

(

) (1)

制約条件

x ∈ F (2)

このとき

F

,

(

,

.

)

.

2.1.1

式

(3)

x

∈ F

f (x

) ≤ f (x),

x ∈ F (3)

また実行可能

x

∈ F

U(x

)

,

f (x

) ≤ f (x),

x ∈ F ∩ U (x

) (4)

が成り立つとき、

x

.

??

. U(x

)

,x

.

,U(x

) ∈ F

.

,

.

,

,

.

3

3.1

(DE)

DE

K.price, R.Storn

,

,

う

. DE

,

.

,

,

. DE

,

, [DE/best/1/bin]

[DE/rand/1/exp]

などが代表される

[2].

,

(best)

,

(rand)

2

.

,

,

(bin)

(exp)

2

.

3.1.1 DE

標準的な

DE

.

Step1 : N

,

g=1

.

,

,

.

Step2 :

.

Step3 :

x

(i = 1,2,...N

)

Steo3.1 :

x

(j 6 = i)

Step3.2 : x

v

Step3.3 :

x

v

u

Step3.4 :

x

u

x

. Step6 :

,g=g+1

Step3

.

3.1.2

本節では、交叉について述べる．交叉とは、

2

DE

x

(1 ≤ i ≤ N

)

x

(j 6 = i)

x

best

rand

x

v

v

x

, x

S

v

:= x

+ S

(x

− x, l)

本研究では簡単のために差分定数

S

= 0

v

= x

交叉により差分変異個体

v

x

u

(5)

(6)

v

, x

, u

(1 ≤ m ≤ D)

v

, x

, u

d

, d

1 ≤ d

≤ D

rand[0,1]

[0,1]

二項交叉



 

 



for(d := 1; j ≤ D; ++ d) { if (rand [0, 1] < C

∨ d = d

)

u

:= v

; else u

:= x

; }

(5)

指数交叉



 

 

 

 

 

 



d := d

; do {

u

:= v

; d := (d + 1)%D;

} while (rand [0, 1] < C

∧ d 6 = d

) while (d 6 = d

) {

u

:= x

; d := (d + 1)%D;

}

(6)

3.2

(PDE)

並列差分進化計算

(PDE)

DE

. PDE

DE

1

,

,

,

.[1]

3.2.1

PDE

. (1)

複数のコンピュータあるいは接続機器を

1

LAN

. (2)

階層構造をもったネットワークである

.

,

,

3

,

,

.

(3)

ハイパーキューブは

,n-

,

(

)

,

.

,

.

図

1,2,3

図

1

2

図

3

3.2.2 PDE

本研究では

,

(mix

,rand

,best

)

(mix

,bin

,exp

)

, 5

.

,

5

.

• 1

: [best/exp]

• 2

: [rand/exp]

• 3

: [best/bin]

• 4

: [rand/bin]

• 5

: [mix/mix]

3.2.3 PDE

PDE

,

P

P

(0 ≤ p < P )

,

. PDE

,

P

(0 ≤ p < P )

x

(0 ≤ i < N )

. PDE

2

.

G

.

(1)

DE

(0 ≤ p < P )

x

(0 ≤ i < N)

DE

G

.

(2)

(0 ≤ p < P )

x

)

P

,

P

x

(p − 1)modP )

x

p) (0 ≤ i < N )

.

4

本研究では

PDE

解となる画像については，以下の制限を設ける．

1.

16

16

2

(1

0)

16

16

(0

1)

する．

2.

2.

4.1

本研究で作成した画像処理の手順を以下に述べる

. DE

.

1

20

.

.

手順

2

.

手順

3

2

.

4

2

,

2

.

PDE

.

1

.

手順

2

G

手順

2.1

P

(1 ≤ p ≤ P r)

DE

G

手順

2.2

P

(1 ≤ p ≤ P r)

P

(q = p + 1 mod P r)

手順

2.3

P

(1 ≤ p ≤ P r)

2.2

手順

3.4

,

2

.

4.2

本研究では，

3.2.2

5

,

.

5

本研究では，

5

,

8

100

PDE

1

また，付録に本研究で用いた画像処理の

PDE

また

,5

,

[rand/exp]

100

PDE

.

2

表

1

best rand best rand mix

exp exp bin bin mix

世代数

27 70 506 411 309

11% 70% 14% 16% 24%

表

2

1 2 4 8 16

37 49 59 68 104

21% 41% 54% 76% 69%

6

実験結果より

,

5

,[rand/exp]

.

,PDE

,

,

,

rand

.

逆に

,best

,

は向上するが

,

,

.

7

本研究では

PDE

,

.

,

,

[rand/exp]

,

.

,

,best

mix

,

,

,

.

謝辞

本論文を結ぶにあたり

,

,

.

参考文献

[1]

,

:

,

, Vol.2011-MPS-82 No.23 pp.

1-2 (2011)

[2] Storn, R. and Price, K. : Differential evolution - a simple and efficient heuristic for global optimization over continuous space, Journal of Global Optimization, Vol. 11, no. 4, pp. 341–359 (1997).

[3] Breshears, C.: The Art of Concurrency - A Thread Monkey s Guide to Writing Parallel Applications, O REILLY (2009)

[4] Storn, R. and Price, K.: Differential evolution - a simple and efficient heuristic for global optimization over continuous space, Journal of Global Optimization, Vol. 11, No. 4, pp. 341

359 (1997)

[5]

,

Particle Swarm Optimization

32

(2005)

[6]

(1998)

[7]

(2000) [8]

(1993)

[9] T.Ishimizu and K.Tagawa, Experiment Study of A Structured Differential Evolution with Mixed Strategies, Proc. the World Congress on Nature and Biologically Inspired Computing (NaBIC) , pp.598-603, (2010)

[10] Price,K.V.,Storn,R.M.andLampinen,J.A.:DifferentialEvolution

APractical Approach to Global

Optimization, Springer (2005).

付録

A

本研究で用いた画像処理の

PDE

.

3

.

.1 DifferentialEvolution

p a c k a g e de ; i m p o r t j a v a . io .*;

/**

* 与えられたぼやけた値画像の元画像を進化計算により得る2

*/

p u b l i c c l a s s D i f f e r e n t i a l E v o l u t i o n {

s t a t i c f i n a l int D = 32; // 問題の次元( d i m e n s i o n of p r o b l e m ) s t a t i c f i n a l int NP = 32; // 母集団の大きさ( s i z e of p o p u l a t i o n ) s t a t i c f i n a l d o u b l e F = 0 . 5 ; // 差分定数( d i f f e r e n t i a l c o n s t a n t ) s t a t i c f i n a l d o u b l e CR = 0 . 9 ; // 交叉定数( c r o s s o v e r c o n s t a n t ) s t a t i c f i n a l d o u b l e MT = 0 . 1 ; // 突然変異定数( m u t a t i o n c o n s t a n t ) s t a t i c int L G E N = 8; // 局所世代数( n u m b e r of l o c a l g e n e r a t i o n s ) s t a t i c int S G E N = 1 0 2 4 / L G E N ; // スーパー世代数( n u m b e r of s u p e r g e n e r a t i o n ) s t a t i c M o n o c h r o m e P i c t u r e t a r g e t ; // 目標画像

s t a t i c M o n o c h r o m e P i c t u r e t a r g e t s []; // 目標画像の行列 s t a t i c f i n a l int p i c t u r e S i z e = 16; // 画像のサイズ

s t a t i c f i n a l int CT = -1; // 交叉のタイプ /**

* -1: mix 混在

* 1: bin 二項交叉

* oh : exp 指数交叉

*/

s t a t i c f i n a l int IST = -1; // インデックス選択のタイプ

/**

* -1: mix 混在

* 1: r a n d ランダム

* oh : b e s t 最適値

*/

s t a t i c f i n a l int NWT = 1; // ネットワークのタイプ

/**

* 1: r i n g n e t w o r k

* 2: t o r u s n e t w o r k

* 3: h y p e r c u b e n e t w o r k

* 4: h i e r a r c h i c a l n e t w o r k

* oh : no n e t w o r k

*/

s t a t i c f i n a l int NTH = 4; // 局所計算スレッド数

s t a t i c f i n a l int R O O P N = 8; // ループ回数 s t a t i c f i n a l int GV = 1;

s t a t i c f i n a l d o u b l e E P S I L O N = 0 . 1 ; // 適応値がこれより小さくなると解とみなす

s t a t i c L o c a l D i f f e r e n t i a l E v o l u t i o n de []; // 進化計算スレッドの実装クラスのインスタンス

s t a t i c T h r e a d th []; // 進化計算スレッドのスレッドのインスタンス

s t a t i c F i l e W r i t e r pass , r P a s s ; s t a t i c P r i n t W r i t e r fp , rfp ;

s t a t i c d o u b l e f i t n e s s R e c o r d [ ] [ ] ; // 適応値記録用

s t a t i c M o n o c h r o m e P i c t u r e o p t i m u m R e c o r d []; // 最適値記録用 s t a t i c int r o o p I n d e x = 0;

s t a t i c b o o l e a n i s F i n d O p t i m u m ; // 最適解発見？

s t a t i c int f i n d O p t i m u m []; // 最適解発見時 s t a t i c int sgen , l g e n ;

p u b l i c s t a t i c v o i d m a i n ( S t r i n g [] a r g s ) {

de = new L o c a l D i f f e r e n t i a l E v o l u t i o n [ NTH ];

th = new T h r e a d [ NTH ];

// for ( L G E N =1; LGEN < 1 0 2 4 ; L G E N * = 2 ) { // S G E N = 2 0 4 8 / L G E N ;

l g e n = L G E N ; s g e n = S G E N ; if ( L G E N > GV ) {

l g e n = GV ;

s g e n = S G E N * ( L G E N / GV );

}

f i t n e s s R e c o r d = new d o u b l e [ R O O P N ][ s g e n ];

o p t i m u m R e c o r d = new M o n o c h r o m e P i c t u r e [ R O O P N ];

t a r g e t s = new M o n o c h r o m e P i c t u r e [ R O O P N ];

r o o p I n d e x = 0;

f i n d O p t i m u m = new int [ R O O P N ];

S t r i n g f n a m e = r e c o r d F i l e N a m e ();

try {

// p a s s = new F i l e W r i t e r (" f i t n e s s . txt ");

// fp = new P r i n t W r i t e r ( p a s s );

r P a s s = new F i l e W r i t e r ( f n a m e );

rfp = new P r i n t W r i t e r ( r P a s s );

} c a t c h ( I O E x c e p t i o n e ) { S y s t e m . err . p r i n t l n ( e );

}

for ( r o o p I n d e x = 0; r o o p I n d e x < R O O P N ; ++ r o o p I n d e x ) {

t a r g e t s [ r o o p I n d e x ] = t a r g e t = new M o n o c h r o m e P i c t u r e ( p i c t u r e S i z e );

for ( int i =0; i < NTH ; ++ i ) {

de [ i ] = new L o c a l D i f f e r e n t i a l E v o l u t i o n ( NP , F , CR , MT , lgen , CT , IST , target , i );

}

i s F i n d O p t i m u m = f a l s e ;

f i n d O p t i m u m [ r o o p I n d e x ] = S G E N * L G E N ; // S G E N * L G E N ;

s w i t c h ( NWT ) {

c a s e 1: // リング型ネットワーク

r i n g N e t w o r k ();

b r e a k ;

c a s e 2: // トーラス型ネットワーク

t o r u s N e t w o r k ();

b r e a k ;

c a s e 3: // ハイパーキューブ型ネットワーク

h y p e r c u b e N e t w o r k ();

b r e a k ;

c a s e 4: // 階層型ネットワーク

h i e r a r c h i c a l N e t w o r k ();

b r e a k ;

d e f a u l t : // ネットワーク無し n o N e t w o r k ();

b r e a k ; }

S y s t e m . out . p r i n t l n ( r o o p I n d e x + ": f i n d at " + f i n d O p t i m u m [ r o o p I n d e x ] + ": ");

p r i n t O p t i m u m ();

}

// fp . c l o s e ();

o u t p u t F i t n e s s R e c o r d ();

rfp . c l o s e ();

//}

}

/**

* 局所進化計算

* @ p a r a m sg スーパー世代数

*/

s t a t i c v o i d l o c a l D i f f e r e n t i a l E v o l u t i o n ( int sg ) { for ( int i =0; i < NTH ; ++ i ) {

th [ i ] = new T h r e a d ( de [ i ]);

}

for ( int i =0; i < NTH ; ++ i ) { th [ i ]. s t a r t ();

} try {

for ( int i =0; i < NTH ; ++ i ) { th [ i ]. j o i n ();

}

} c a t c h ( I n t e r r u p t e d E x c e p t i o n e ) { S y s t e m . err . p r i n t l n ( e );

}

// for ( int i =0; i < lg ; ++ i ) { // de [ i ]. p r i n t O p t i m u m ();

//}

// p r i n t F i t n e s s ( sg );

// o u t p u t F i t n e s s ( sg );

}

/**

* 最適解を得る

* @ r e t u r n M o n o c h r o m e P i c t u r e [] : 各プロセッサの最適解画像

*/

s t a t i c M o n o c h r o m e P i c t u r e [] g e t O p t i m u m () {

M o n o c h r o m e P i c t u r e opt [] = new M o n o c h r o m e P i c t u r e [ NTH ];

for ( int i =0; i < NTH ; ++ i ) {

opt [ i ] = de [ i ]. g e t O p t i m u m ();

}

r e t u r n opt ; }

/**

* 適応値を得る

* @ r e t u r n d o u b l e [] : 各プロセッサの適応値

*/

s t a t i c d o u b l e [] g e t F i t n e s s () {

d o u b l e fit [] = new d o u b l e [ NTH ];

for ( int i =0; i < NTH ; ++ i ) {

fit [ i ] = de [ i ]. g e t F i t n e s s ();

}

r e t u r n fit ; }

s t a t i c v o i d r i n g N e t w o r k () {

M o n o c h r o m e P i c t u r e opt [] = new M o n o c h r o m e P i c t u r e [ NTH ];

d o u b l e fit [] = new d o u b l e [ NTH ];

S y s t e m . out . p r i n t l n (" R i n g n e t w o r k ");

// fp . p r i n t l n (" R i n g n e t w o r k ");

// fp . p r i n t ("\ t ");

// for ( int i =0; i < NTH ; ++ i ) // fp . p r i n t ( i + "\ t ");

// fp . p r i n t l n ();

for ( int g =0; g < s g e n ; ++ g ) {

if (! i s F i n d O p t i m u m ) { // 最適値を発見するまで局所を計算するDE l o c a l D i f f e r e n t i a l E v o l u t i o n ( g );

opt = g e t O p t i m u m ();

fit = g e t F i t n e s s ();

int gv = 1;

if ( L G E N > GV ) gv = L G E N / GV ; if (( g % gv ) == ( gv - 1 ) ) {

for ( int i =0; i < NTH ; ++ i ) {

de [( i +1) % NTH ]. r e p l a c e D a t a ( opt [ i ] , fit [ i ]);

// S y s t e m . out . p r i n t ( i + " - >" + (( i +1) % NTH ) + " ");

} }

}

// S y s t e m . out . p r i n t l n ();

r e c o r d F i t n e s s ( g );

} }

s t a t i c v o i d t o r u s N e t w o r k () {

M o n o c h r o m e P i c t u r e opt [] = new M o n o c h r o m e P i c t u r e [ NTH ];

d o u b l e fit [] = new d o u b l e [ NTH ];

int w i d t h =1 , h i g h t =1;

w h i l e ( w i d t h * h i g h t < NTH ) { w i d t h *= 2;

if ( w i d t h * h i g h t == NTH ) b r e a k ; h i g h t *= 2;

}

S y s t e m . out . p r i n t l n (" T o r u s n e t w o r k ");

// fp . p r i n t l n (" T o r u s n e t w o r k ");

// fp . p r i n t ("\ t ");

// for ( int i =0; i < NTH ; ++ i ) // fp . p r i n t ( i + "\ t ");

// fp . p r i n t l n ();

for ( int g =0; g < s g e n ; ++ g ) {

if (! i s F i n d O p t i m u m ) { // 最適値を発見するまで局所を計算するDE l o c a l D i f f e r e n t i a l E v o l u t i o n ( g );

opt = g e t O p t i m u m ();

fit = g e t F i t n e s s ();

int gv = 1;

if ( L G E N > GV ) gv = L G E N / GV ; if (( g % gv ) == ( gv - 1 ) ) {

if (( g + 1 ) % ( 2 * gv ) == 0) { // 横方向のスレッドと通信 // S y s t e m . out . p r i n t l n ( g + " -");

for ( int h =0; h < h i g h t ; ++ h ) {

for ( int w =0; w < w i d t h ; ++ w ) {

de [ h * w i d t h + ( w + 1 ) % w i d t h ]. r e p l a c e D a t a ( opt [ h * w i d t h + w ] , fit [ h * w i d t h + w ]);

// S y s t e m . out . p r i n t (( h * w i d t h + w ) + " - >" + ( h * w i d t h + ( w + 1 ) % w i d t h ) + " ");

} }

} e l s e { // 縦方向のスレッドと通信

// S y s t e m . out . p r i n t l n ( g + " | " ) ; for ( int h =0; h < h i g h t ; ++ h ) {

for ( int w =0; w < w i d t h ; ++ w ) {

de [(( h + 1 ) % h i g h t )* w i d t h + w ]. r e p l a c e D a t a ( opt [ h * w i d t h + w ] , fit [ h * w i d t h + w ]);

// S y s t e m . out . p r i n t (( h * w i d t h + w ) + " - >" + ((( h + 1 ) % h i g h t )* w i d t h + w ) + " ");

} }

}

// S y s t e m . out . p r i n t l n ();

} }

r e c o r d F i t n e s s ( g );

} }

s t a t i c v o i d h y p e r c u b e N e t w o r k () {

M o n o c h r o m e P i c t u r e opt [] = new M o n o c h r o m e P i c t u r e [ NTH ];

d o u b l e fit [] = new d o u b l e [ NTH ];

int n e i g h b o r = 1 , p a i r = 2;

S y s t e m . out . p r i n t l n (" H y p e r c u b e n e t w o r k ");

// fp . p r i n t l n (" H y p e r c u b e n e t w o r k ");

// fp . p r i n t ("\ t ");

// for ( int i =0; i < NTH ; ++ i ) // fp . p r i n t ( i + "\ t ");

// fp . p r i n t l n ();

for ( int g =0; g < s g e n ; ++ g ) {

if (! i s F i n d O p t i m u m ) { // 最適値を発見するまで局所を計算するDE l o c a l D i f f e r e n t i a l E v o l u t i o n ( g );

opt = g e t O p t i m u m ();

fit = g e t F i t n e s s ();

int gv = 1;

if ( L G E N > GV ) gv = L G E N / GV ; if (( g % gv ) == ( gv - 1 ) ) {

for ( int i =0; i < NTH ; ++ i ) {

if (( i % p a i r ) < n e i g h b o r ) {

de [( i + n e i g h b o r ) % NTH ]. r e p l a c e D a t a ( opt [ i ] , fit [ i ]);

// S y s t e m . out . p r i n t ( i +" - >"+(( i + n e i g h b o r ) % NTH )+" ");

} e l s e {

de [( i - n e i g h b o r ) % NTH ]. r e p l a c e D a t a ( opt [ i ] , fit [ i ]);

// S y s t e m . out . p r i n t ( i +" - >"+(( i - n e i g h b o r ) % NTH )+" ");

} }

// S y s t e m . out . p r i n t l n ();

n e i g h b o r *= 2;

p a i r * = 2 ;

if ( n e i g h b o r >= NTH ) { n e i g h b o r = 1;

p a i r = 2;

} }

}

r e c o r d F i t n e s s ( g );

} }

s t a t i c v o i d h i e r a r c h i c a l N e t w o r k () {

M o n o c h r o m e P i c t u r e opt [] = new M o n o c h r o m e P i c t u r e [ NTH ];

d o u b l e fit [] = new d o u b l e [ NTH ];

int n e i g h b o r = 1 , p a i r = 2;

S y s t e m . out . p r i n t l n (" H i e r a r c h i c a l n e t w o r k ");

// fp . p r i n t l n (" H i e r a r c h i c a l n e t w o r k ");

// fp . p r i n t ("\ t ");

// for ( int i =0; i < NTH ; ++ i ) // fp . p r i n t ( i + "\ t ");

// fp . p r i n t l n ();

for ( int g =0; g < s g e n ; ++ g ) {

if (! i s F i n d O p t i m u m ) { // 最適値を発見するまで局所を計算するDE l o c a l D i f f e r e n t i a l E v o l u t i o n ( g );

opt = g e t O p t i m u m ();

fit = g e t F i t n e s s ();

int gv = 1;

if ( L G E N > GV ) gv = L G E N / GV ; if (( g % gv ) == ( gv - 1 ) ) {

n e i g h b o r = 1;

p a i r = 2;

w h i l e ( ( ( ( g + 1 ) / gv ) % p a i r ) == 0) { n e i g h b o r *= 2;

p a i r *= 2;

}

w h i l e ( p a i r > NTH ) {

n e i g h b o r = n e i g h b o r * 2/ NTH ; p a i r = p a i r * 2 / NTH ;

}

for ( int i =0; i < NTH ; ++ i ) {

if (( i % p a i r ) < n e i g h b o r ) {

de [( i + n e i g h b o r ) % NTH ]. r e p l a c e D a t a ( opt [ i ] , fit [ i ]);

// S y s t e m . out . p r i n t ( i +" - >"+(( i + n e i g h b o r ) % NTH )+" ");

} e l s e {

de [( i - n e i g h b o r ) % NTH ]. r e p l a c e D a t a ( opt [ i ] , fit [ i ]);

// S y s t e m . out . p r i n t ( i +" - >"+(( i - n e i g h b o r ) % NTH )+" ");

} }

// S y s t e m . out . p r i n t l n ();

} }

r e c o r d F i t n e s s ( g );

} }

/**

* ネットワーク無し

* 局所計算スレッド間の通信を一切しない

*/

s t a t i c v o i d n o N e t w o r k () {

S y s t e m . out . p r i n t l n (" No n e t w o r k ");

// fp . p r i n t l n (" No n e t w o r k ");

// fp . p r i n t ("\ t ");

// for ( int i =0; i < NTH ; ++ i ) // fp . p r i n t ( i + "\ t ");

// fp . p r i n t l n ();

for ( int g =0; g < s g e n ; ++ g ) {

if (! i s F i n d O p t i m u m ) { // 最適値を発見するまで局所を計算するDE l o c a l D i f f e r e n t i a l E v o l u t i o n ( g );

}

r e c o r d F i t n e s s ( g );

} }

/**

* 適合性表示

*/

s t a t i c v o i d p r i n t F i t n e s s () {

S y s t e m . out . p r i n t (" f i t n e s s : ");

for ( int i =0; i < NTH ; ++ i ) {

S y s t e m . out . p r i n t f ( " % 4 . 2 f " , de [ i ]. g e t F i t n e s s ( ) ) ; }

S y s t e m . out . p r i n t l n ();

}

/**

* 適合性表示

* スーパー世代ごとの適合性を表示する

* @ p a r a m sg スーパー世代数

*/

s t a t i c v o i d p r i n t F i t n e s s ( int sg ) {

S y s t e m . out . p r i n t f (" f i t n e s s : %2 d " , sg );

for ( int i =0; i < NTH ; ++ i ) {

S y s t e m . out . p r i n t f ( " % 4 . 2 f " , de [ i ]. g e t F i t n e s s ( ) ) ; }

S y s t e m . out . p r i n t l n ();

}

s t a t i c v o i d p r i n t O p t i m u m () { int i B e s t = 0;

d o u b l e f B e s t = de [ 0 ] . g e t F i t n e s s ();

for ( int i =1; i < NTH ; ++ i ) {

d o u b l e f = de [ i ]. g e t F i t n e s s ();

if ( f < f B e s t ) { i B e s t = i ; f B e s t = f ; }

}

S y s t e m . out . p r i n t l n (" T a r g e t ");

t a r g e t . s h o w P i c t u r e ();

S y s t e m . out . p r i n t l n (" O p t i m u m ");

de [ i B e s t ]. p r i n t O p t i m u m ();

// de [ i B e s t ]. o u t p u t O p t i m u m ( fp );

}

/**

* 適合性出力

* 適合性をファイルに出力する

*/

s t a t i c v o i d o u t p u t F i t n e s s () { fp . p r i n t (" f i t n e s s : ");

for ( int i =0; i < NTH ; ++ i ) {

fp . p r i n t f ( " % 4 . 2 f \ t " , de [ i ]. g e t F i t n e s s ( ) ) ; }

fp . p r i n t l n ();

}

/**

* 適合性出力

* スーパー世代ごとの適合性をファイルに出力する

* @ p a r a m g スーパー世代数

*/

s t a t i c v o i d o u t p u t F i t n e s s ( int sg ) { fp . p r i n t f (" f i t n e s s \ t %2 d \ t " , sg );

for ( int i =0; i < NTH ; ++ i ) {

fp . p r i n t f ( " % 4 . 2 f \ t " , de [ i ]. g e t F i t n e s s ( ) ) ; }

fp . p r i n t l n ();

}

/**

* 全てのの中で最も高い適合性を返すLDE

* @ r e t u r n d o u b l e : 適合性最高値

*/

s t a t i c d o u b l e g e t B e s t F i t n e s s () {

d o u b l e f B e s t = de [ 0 ] . g e t F i t n e s s ();

for ( int i =1; i < NTH ; ++ i ) {

d o u b l e f = de [ i ]. g e t F i t n e s s ();

if ( f < f B e s t ) f B e s t = f ; }

r e t u r n f B e s t ; }

/**

* 全てのの中で最も高い適合性をもつ画像返すLDE

* @ r e t u r n M o n o c h r o m e P i c t u r e : 適合性最高値の画像

*/

s t a t i c M o n o c h r o m e P i c t u r e g e t B e s t O p t i m u m (){

d o u b l e f B e s t = de [ 0 ] . g e t F i t n e s s ();

M o n o c h r o m e P i c t u r e o B e s t = de [ 0 ] . g e t O p t i m u m ();

for ( int i =1; i < NTH ; ++ i ) {

d o u b l e f = de [ i ]. g e t F i t n e s s ();

if ( f < f B e s t ) { f B e s t = f ;

o B e s t = de [ i ]. g e t O p t i m u m ();

} }

r e t u r n o B e s t ; }

/**

* F i t n e s s および O p t i m u m の記録

* @ p a r a m g スーパー世代数

*/

s t a t i c v o i d r e c o r d F i t n e s s ( int g ) {

d o u b l e b e s t F i t n e s s = g e t B e s t F i t n e s s ();

f i t n e s s R e c o r d [ r o o p I n d e x ][ g ] = b e s t F i t n e s s ; if (! i s F i n d O p t i m u m && b e s t F i t n e s s < E P S I L O N ) {

i s F i n d O p t i m u m = t r u e ;

f i n d O p t i m u m [ r o o p I n d e x ] = g * l g e n ; // g * L G E N ; }

o p t i m u m R e c o r d [ r o o p I n d e x ] = g e t B e s t O p t i m u m ();

}

/**

* @ r e t u r n データ記録用ファイル名

*/

s t a t i c S t r i n g r e c o r d F i l e N a m e () { S t r i n g f n a m e = " d a t a /";

if ( CT == -1) {

f n a m e += " mix -";

} e l s e if ( CT == 1) { f n a m e += " bin -";

} e l s e {

f n a m e += " exp -";

}

if ( IST == -1) {

f n a m e += " mix -";

} e l s e if ( IST == 1) { f n a m e += " rand -";

} e l s e {

f n a m e += " best -";

}

s w i t c h ( NWT ) { c a s e 1:

f n a m e += " r i n g ";

b r e a k ; c a s e 2:

f n a m e += " t o r u s ";

b r e a k ; c a s e 3:

f n a m e += " h y p e r c u b e ";

b r e a k ; c a s e 4:

f n a m e += " h i e r a r c h i c a l ";

b r e a k ; d e f a u l t :

f n a m e += " no ";

b r e a k ; }

if ( L G E N < 10) {

f n a m e += ( " 0 0 " + L G E N );

} e l s e if ( L G E N < 1 0 0 ) { f n a m e += ( " 0 " + L G E N );

} e l s e {

f n a m e += L G E N ; }

f n a m e += ". txt ";

r e t u r n f n a m e ; }

s t a t i c v o i d o u t p u t F i t n e s s R e c o r d () {

if ( CT == -1) {

rfp . p r i n t (" Mix \ t ");

} e l s e if ( CT == 1) {

rfp . p r i n t (" Bin \ t ");

} e l s e {

rfp . p r i n t (" Exp \ t ");

}

if ( IST == -1) {

rfp . p r i n t (" Mix \ t ");

} e l s e if ( IST == 1) {

rfp . p r i n t (" R a n d \ t ");

} e l s e {

rfp . p r i n t (" B e s t \ t ");

}

s w i t c h ( NWT ) { c a s e 1:

rfp . p r i n t (" R i n g n e t w o r k \ t ");

b r e a k ; c a s e 2:

rfp . p r i n t (" T o r u s n e t w o r k \ t ");

b r e a k ; c a s e 3:

rfp . p r i n t (" H y p e r c u b e n e t w o r k \ t ");

b r e a k ; c a s e 4:

rfp . p r i n t (" H i e r a r c h i c a l n e t w o r k \ t ");

b r e a k ; d e f a u l t :

rfp . p r i n t (" No n e t w o r k \ t ");

b r e a k ; }

rfp . p r i n t l n ( L G E N );

rfp . p r i n t ("\ t ");

int g m a x = s g e n * l g e n / GV ; if ( g m a x > 2 5 0 ) g m a x = 2 5 0 ; for ( int g =0; g < g m a x ; ++ g )

rfp . p r i n t f ( " % 2 d \ t " , g * GV );

rfp . p r i n t l n (" f i n d A t ");

int c o u n t = 0;

int sum = 0;

int s q s u m = 0;

int c o u n t T a b l e [] = new int [ 8 ] ;

for ( int i =0; i < c o u n t T a b l e . l e n g t h ; ++ i ) c o u n t T a b l e [ i ] = 0;

d o u b l e f i t n e s s S u m [] = new d o u b l e [ g m a x ];

for ( int i =0; i < f i t n e s s S u m . l e n g t h ; ++ i ) { f i t n e s s S u m [ i ] = 0;

}

int ct [] = new int [ L G E N * S G E N ];

for ( int i =0; i < ct . l e n g t h ; ++ i ) { ct [ i ] = 0;

}

for ( int r =0; r < R O O P N ; ++ r ) { rfp . p r i n t f ( " % 2 d \ t " , r );

if ( LGEN < GV ) {

for ( int g =0; g < g m a x ; ++ g ) {

rfp . p r i n t f ( " % 4 . 3 f \ t " , f i t n e s s R e c o r d [ r ][ g * GV / L G E N ]);

f i t n e s s S u m [ g ] += f i t n e s s R e c o r d [ r ][ g * GV / L G E N ];

} } e l s e {

for ( int g =0; g < g m a x ; ++ g ) {

rfp . p r i n t f ( " % 4 . 3 f \ t " , f i t n e s s R e c o r d [ r ][ g ]);

f i t n e s s S u m [ g ] += f i t n e s s R e c o r d [ r ][ g ];

} }

if ( f i n d O p t i m u m [ r ] < l g e n * s g e n ) { rfp . p r i n t l n ( f i n d O p t i m u m [ r ]);

c o u n t ++;

sum += f i n d O p t i m u m [ r ];

s q s u m += f i n d O p t i m u m [ r ] * f i n d O p t i m u m [ r ];

if ( f i n d O p t i m u m [ r ] < 16) { ++ c o u n t T a b l e [ 0 ] ;

} e l s e if ( f i n d O p t i m u m [ r ] < 32) { ++ c o u n t T a b l e [ 1 ] ;

} e l s e if ( f i n d O p t i m u m [ r ] < 64) { ++ c o u n t T a b l e [ 2 ] ;

} e l s e if ( f i n d O p t i m u m [ r ] < 1 2 8 ) { ++ c o u n t T a b l e [ 3 ] ;

} e l s e if ( f i n d O p t i m u m [ r ] < 2 5 6 ) { ++ c o u n t T a b l e [ 4 ] ;

} e l s e if ( f i n d O p t i m u m [ r ] < 5 1 2 ) { ++ c o u n t T a b l e [ 5 ] ;

} e l s e if ( f i n d O p t i m u m [ r ] < 1 0 2 4 ) { ++ c o u n t T a b l e [ 6 ] ;

} e l s e if ( f i n d O p t i m u m [ r ] < 2 0 4 8 ) { ++ c o u n t T a b l e [ 7 ] ;

}

++ ct [ f i n d O p t i m u m [ r ]];

} e l s e {

rfp . p r i n t l n (" not yet ");

} }

rfp . p r i n t (" av \ t ");

for ( int g =0; g < g m a x ; ++ g ) {

rfp . p r i n t f ( " % 4 . 3 f \ t " , ( f i t n e s s S u m [ g ] / R O O P N ));

}

rfp . p r i n t l n ();

for ( int i =1; i < c o u n t T a b l e . l e n g t h ; ++ i ) { c o u n t T a b l e [ i ] += c o u n t T a b l e [ i - 1 ] ; }

if ( c o u n t > 0) {

d o u b l e av = ( d o u b l e ) sum / c o u n t ; if ( c o u n t > 1) {

d o u b l e s t d e v = M a t h . s q r t (( d o u b l e ) ( s q s u m - av * av * c o u n t ) / ( count - 1 ) ) ; rfp . p r i n t ( c o u n t + "\ t " + av + "\ t " + s t d e v );

S y s t e m . out . p r i n t l n ( c o u n t + " av :" + av + " s t d e v :" + s t d e v );

} e l s e {

rfp . p r i n t ( c o u n t + "\ t " + av + "\ t n o n ");

S y s t e m . out . p r i n t l n ( c o u n t + " av :" + av + " s t d e v : non ");

} } e l s e {

rfp . p r i n t ( " 0 \ t n o n \ t n o n ");

S y s t e m . out . p r i n t l n ("0 av : non s t d e v : non ");

}

for ( int i =0; i < c o u n t T a b l e . l e n g t h ; ++ i ) { rfp . p r i n t ("\ t " + c o u n t T a b l e [ i ]);

}

rfp . p r i n t l n ();

for ( int r =0; r < R O O P N ; ++ r ) {

rfp . p r i n t l n (" L o o p : " + r );

rfp . p r i n t l n (" T a r g e t ");

t a r g e t s [ r ]. p r i n t P i c t u r e ( rfp );

rfp . p r i n t l n (" O p t i m u m ");

o p t i m u m R e c o r d [ r ]. p r i n t P i c t u r e ( rfp );

rfp . p r i n t f ( " % 4 . 3 f " , f i t n e s s R e c o r d [ r ][ SGEN - 1 ] ) ; rfp . p r i n t l n ();

}

for ( int i =1; i < ct . l e n g t h ; ++ i ) { ct [ i ] += ct [ i - 1 ] ;

}

for ( int i =0; i < 5 1 2 ; i + = 4 ) { rfp . p r i n t ( i + "\ t ");

}

rfp . p r i n t l n ();

for ( int i =0; i < 5 1 2 ; i + = 4 ) { rfp . p r i n t ( ct [ i ] + "\ t ");

}

rfp . p r i n t l n ();

} }

.1 LocalDifferentialEvolution

p a c k a g e de ;

i m p o r t j a v a . u t i l . R a n d o m ; i m p o r t j a v a . io .*;

/**

* 与えられたぼやけた値画像の元画像を進化計算により得る2

*/

p u b l i c c l a s s L o c a l D i f f e r e n t i a l E v o l u t i o n i m p l e m e n t s R u n n a b l e { M o n o c h r o m e P i c t u r e pop []; // 母集団( p o p u l a t i o n )

d o u b l e fit []; // 母集団の適合性( f i t n e s s of the p o p u l a t i o n ) int s i z e P o p ; // 母集団の大きさ( s i z e of p o p u l a t i o n )

d o u b l e d i f f C o n s ; // 差分定数( d i f f e r e n t i a l c o n s t a n t ) 現在は未使用拡張用(:) d o u b l e c r o s s C o n s ; // 交叉定数( c r o s s o v e r c o n s t a n t )

d o u b l e m u t a t i o n C o n s ; // 突然変異定数( m u t a t i o n c o n s t a n t ) int g e n e r a t i o n ; // 世代数( n u m b e r of g e n e r a t i o n s )

int i B e s t ; // 最適解のインデックス

R a n d o m rd ; // 乱数発生用クラスのインスタンス

M o n o c h r o m e P i c t u r e t a r g e t ; // 目標となる値画像2

int p i c t u r e S i z e ; // 画像のサイズ

int c r o s s T y p e ; // 交叉のタイプ

/**

* 1: bin

* oh : exp

*/

int i n d e x S e l e c t T y p e ; // インデックス選択のタイプ /**

* 1: r a n d

* ot : b e s t

*/

int t h N u m ; // スレッド番号

/**

* コンストラクタ

* @ p a r a m int s 母集団のサイズ

* @ p a r a m d o u b l e dc 差分定数

* @ p a r a m d o u b l e cc 交叉定数

* @ p a r a m d o u b l e mc 突然変異定数

* @ p a r a m int gen 世代数

* @ p a r a m int ct 交叉のタイプ

* @ p a r a m int ist : インデックスの選択タイプランダム (ベストor )

* @ p a r a m M o n o c h r o m e P i c t u r e mp : 目標画像

* @ r a m a m int tn スレッド番号

*/

L o c a l D i f f e r e n t i a l E v o l u t i o n ( int s , d o u b l e dc , d o u b l e cc , d o u b l e mc , int gen , int ct , int ist , M o n o c h r o m e P i c t u r e mp , int tn ) { s i z e P o p = s ;

d i f f C o n s = dc ; c r o s s C o n s = cc ; m u t a t i o n C o n s = mc ; g e n e r a t i o n = gen ; if ( ct == -1) {

if ( tn % 2 == 0) { c r o s s T y p e = 0;

} e l s e {

c r o s s T y p e = 1;

} } e l s e {

c r o s s T y p e = ct ; }

if ( ist == -1) {

if ( tn % 4 < 2) {

i n d e x S e l e c t T y p e = 0;

} e l s e {

i n d e x S e l e c t T y p e = 1;

} } e l s e {

i n d e x S e l e c t T y p e = ist ; }

rd = new R a n d o m ();

t a r g e t = mp ;

p i c t u r e S i z e = mp . s i z e ;

pop = m a k e P o p u l a t i o n (); // 解の母集団設定

fit = new d o u b l e [ s i z e P o p ];

s e t I n i t i a l F i t n e s s (); // 適合性の初期値設定

t h N u m = tn ; }

/**

* 解の母集団表示関数

*/

p u b l i c v o i d p r i n t P o p u l a t i o n () {

for ( int i =0; i < s i z e P o p ; ++ i ) { if ( i == i B e s t ) {

S y s t e m . out . p r i n t l n (" b e s t ");

} e l s e {

S y s t e m . out . p r i n t l n ();

}

pop [ i ]. s h o w P i c t u r e ();

} }

/**

* 最適解表示

*/

p u b l i c v o i d p r i n t O p t i m u m () { pop [ i B e s t ]. s h o w P i c t u r e ();

S y s t e m . out . p r i n t l n (" f i t n e s s : " + pop [ i B e s t ]. g e t V a l u e ( ) ) ; }

/**

* 最適解出力

* @ p a r a m p r i n t W r i t e r fp : 出力ファイルへのポインタ

*/

p u b l i c v o i d o u t p u t O p t i m u m ( P r i n t W r i t e r fp ) { pop [ i B e s t ]. p r i n t P i c t u r e ( fp );

fp . p r i n t l n (" f i t n e s s \ t " + pop [ i B e s t ]. g e t V a l u e ( ) ) ; }

/**

* 最適解出力

* @ r e t u r n M o n o c h r o m e P i c t u r e : 最適解

*/

p u b l i c M o n o c h r o m e P i c t u r e g e t O p t i m u m () { r e t u r n pop [ i B e s t ];

}

/**

* 適合性出力

* @ r e t u r n d o u l b e 適合性