差分進化演算法 Differential evolution - 4|APTDE, EPSDE, MPEDE比較結果


 (二)目標函數 (Objective functions)



三、實驗結果

(一)實驗設定


Basic DE


APTDE


EPSDE


MPEDE

Population size

50

popSize

50

popSize

50

popSize

50

Genration

10000

Gen

10000

Gen

10000

Gen

10000

Dimension

30

Dim

30

Dim

30

Dim

30

Scaling factor (F)

0.8

F

0.8

F

[0.4, 0.9]

F

[0.4, 0.9]

Crossover rate (CR)

0.9

CR

0.9

CR

[0.1, 0.9]

CR

[0.1, 0.9]

Repeat times

10

Repeat

10

Repeat

10

Repeat

10

Mutation

Rand/1


Rand/1


rand/1
best/2
current-to-best/1


rand/1
current-to-best/1
current-to-rand/1

Crossover

bin


bin


bin


bin



uPopSize

1.5x

probSuceess

0.9

ng

20



lPopSize

0.5x



subPopRate

0.2



UDelta

5



C

0.5



LDelta

1



meanF

0.5



k1

4



meanCR

0.5



k2

4







C1

0.5







C2

0.01







P

3







Ω

0.8





(二)目標函數值比較

A. Ackley

        在Ackley中,收斂程度:(快)EPSDE = MPEDE > APTDE > Basic DE(慢),表現上:(優)EPSDE = MPEDE > APTDE > Basic DE(差),對EPSDE、MPEDE、APTDE來說,10e-15是個瓶頸。演算法優化程度:(優)自適應參數 > 自適應群體數(差)。

B. Griewank

        在Griewank中,收斂程度:(快)EPSDE = MPEDE > APTDE > Basic DE(慢),表現上:(優)EPSDE > MPEDE > APTDE > Basic DE(差)。演算法優化程度:(優)自適應參數 > 自適應群體數(差)。

C. Michalewicz

        在Michalewicz中,收斂程度:(快)APTDE > MPEDE > Basic DE > EPSDE (慢)。100,000 eva前,APTDE表現最好,但之後就掉入-24瓶頸中。130,000 eva後,MPEDE表現最好,且有在進步的趨勢。前期演算法優化程度:(優)自適應群體數 > 多群+自適應參數 > 自適應參數(差);後期演算法優化程度:(優)多群+自適應參數 > 自適應參數 > 自適應群體數(差)。

D. Powell

        在Powell中,收斂程度:(快)MPEDE > EPSDE > APTDE > Basic DE(慢)。190,000 eva前,MPEDE表現較好,但之後就被APTDE超越。整體表現上:(優)APTDE > MPEDE > Basic DE > EPSDE(差)。演算法優化程度:(優)自適應群體數 > 多群+自適應參數 > 自適應參數(差)。

E. Rastrigin

        在Rastrigin中,收斂程度:(快)APTDE > MPEDE > EPSDE > Basic DE(慢),70,000 eva前,APTDE表現較好,但之後就分別被MPEDE、EPSDE 和Basic DE超越。APTDE被困在43、Basic DE被困在20,而EPSDE和MPEDE都有在進步的趨勢。演算法優化程度:(優)自適應參數>自適應群體數(差)。

F. Rosenbrock

        在Rosenbrock中,表現上:(優)MPEDE > EPSDE > APTDE  > Basic DE(差)。演算法優化程度:(優)多群+自適應參數  > 自適應參數 > 自適應群體數(差)。

G. Schwefel

        在Schwefel中,收斂程度:(快)APTDE > EPSDE > MPEDE > Basic DE(慢),表現上:(優)EPSDE > MPEDE > APTDE > Basic DE(差),不過在150,000 eva後,APTDE就被Basic DE超越。演算法優化程度:(優)自適應參數 > 自適應群體數(差)。

H. Sphere

        在Sphere中,收斂程度:(快)EPSDE > MPEDE > APTDE > Basic DE(慢),表現上:(優)EPSDE > MPEDE > APTDE > Basic DE(差)。演算法優化程度:(優)自適應參數 > 群體+自適應參數 > 自適應群體數(差)。

I. Sum Squares

        在Sum Squares中,收斂程度:(快)EPSDE > MPEDE > APTDE > Basic DE(慢),表現上:(優)EPSDE > MPEDE > APTDE > Basic DE(差)。演算法優化程度:(優)自適應參數 > 群體+自適應參數 > 自適應群體數(差)。

J. Zakharov

        在Zakharov中,收斂程度:(快)EPSDE > MPEDE > APTDE > Basic DE(慢),表現上:(優)EPSDE > MPEDE > APTDE > Basic DE(差)。演算法優化程度:(優)自適應參數 > 群體+自適應參數 > 自適應群體數(差)。

(三)500,000 eva表現總表



Eva

Mean

Min

Max

S.D.

Ackley

Basic DE

500000

2.354804E-08

4.579800E-09

9.821780E-08

2.698304E-08

APTDE

499094

6.750158E-15

3.552710E-15

7.105430E-15

1.123469E-15

EPSDE

500000

3.552710E-15

3.552710E-15

3.552710E-15

0.000000E+00

MPEDE

500000

3.552710E-15

3.552710E-15

3.552710E-15

0.000000E+00

Griewank

Basic DE

500000

7.396040E-04

3.368260E-16

7.396040E-03

2.338833E-03

APTDE

497917

4.436640E-03

2.891300E-42

1.232100E-02

4.901695E-03

EPSDE

500000

3.468092E-138

9.787360E-144

3.466260E-137

1.096063E-137

MPEDE

500000

2.738750E-129

1.867230E-140

1.784920E-128

6.097034E-129

Michalewicz

Basic DE

500000

-2.692153E+01

-2.726490E+01

-2.606700E+01

3.709719E-01

APTDE

505546

-2.477436E+01

-2.615750E+01

-2.376400E+01

7.198696E-01

EPSDE

500000

-2.749729E+01

-2.776910E+01

-2.733360E+01

1.323328E-01

MPEDE

500000

-2.774761E+01

-2.863080E+01

-2.725100E+01

3.865567E-01

Powell

Basic DE

500000

1.119716E-05

4.814050E-06

2.376540E-05

6.252576E-06

APTDE

496933

6.970059E-08

1.313430E-08

1.631210E-07

4.516522E-08

EPSDE

500000

1.558664E-05

8.721640E-06

2.659800E-05

5.175205E-06

MPEDE

500000

4.246294E-07

7.101690E-09

2.738400E-06

9.080742E-07

Rastrigin

Basic DE

500000

2.067441E+01

1.151790E+01

2.923210E+01

5.684803E+00

APTDE

503081

4.808441E+01

3.172620E+01

6.122870E+01

9.071356E+00

EPSDE

500000

4.965759E-34

2.126690E-51

4.965430E-33

1.570195E-33

MPEDE

500000

4.875614E-31

1.315100E-99

4.864630E-30

1.537949E-30

Rosenbrock

Basic DE

500000

8.934412E+01

8.620260E-07

3.807220E+02

1.376412E+02

APTDE

496569

2.176789E+01

3.693260E-06

1.636100E+02

5.112147E+01

EPSDE

500000

6.150362E+00

1.166070E-04

3.167340E+01

1.297102E+01

MPEDE

500000

9.228357E-06

1.360320E-15

5.799930E-05

1.753119E-05

Schwefel

Basic DE

500000

2.501517E+03

1.700290E+03

3.430150E+03

5.694504E+02

APTDE

500898

3.433173E+03

2.897010E+03

4.082660E+03

4.594089E+02

EPSDE

500000

2.938839E+01

-2.985190E+01

8.862330E+01

6.243661E+01

MPEDE

500000

4.349335E+02

-2.985220E+01

7.257650E+02

2.973437E+02

Sphere

Basic DE

500000

5.532226E-18

5.750920E-19

2.584260E-17

8.112919E-18

APTDE

495758

8.644462E-42

1.686590E-43

3.090780E-41

1.118238E-41

EPSDE

500000

4.288293E-144

2.274480E-146

3.403970E-143

1.053232E-143

MPEDE

500000

3.586470E-131

6.178550E-142

3.417780E-130

1.076170E-130

Sum Squares

Basic DE

500000

7.041131E-17

4.513710E-18

2.871010E-16

1.047409E-16

APTDE

495702

2.234219E-41

3.652560E-43

5.352010E-41

1.722906E-41

EPSDE

500000

1.020780E-147

8.298780E-150

5.654060E-147

1.738346E-147

MPEDE

500000

1.480164E-132

9.370330E-145

1.430980E-131

4.510516E-132

Zakharov

Basic DE

500000

2.306313E-15

2.317090E-16

7.135630E-15

2.023552E-15

APTDE

495430

1.143136E-38

1.140410E-40

4.531670E-38

1.790051E-38

EPSDE

500000

3.253845E-141

3.568260E-144

1.498130E-140

5.553144E-141

MPEDE

500000

2.620850E-126

1.734330E-136

2.614760E-125

8.266469E-126


四、結論

Basic DE

APTDE

EPSDE

MPEDE

Ackley

4

3

1

1

Griewank

4

3

1

2

Michalewicz

3

4

2

1

Powell

3

1

4

2

Rastrigin

3

4

1

2

Rosenbrock

4

2

3

1

Schwefel

3

4

2

1

Sphere

4

3

1

2

Sum Squares

4

3

1

2

Zakharov

4

3

1

2

36

30

17

16

整體表現中,(優)MPEDE > EPSDE > APTDE > Basic DE(差),故自適應參數的優化,比自適應群體數來得好。自適應參數加上多群機制,可以使DE在多峰型解空間表現得更好。

特別的是在Powell的表現上,APTDE是最優的,反而EPSDE最差。而APTDE並沒有全贏Basic DE,MPEDE則全贏Basic DE。總體而言,這三個DE變形表現有比Basic DE好。

參考文獻

  1. Mallipeddi, R., Suganthan, P. N., Pan, Q. K., & Tasgetiren, M. F. (2011). Differential evolution algorithm with ensemble of parameters and mutation strategies. Applied Soft Computing, 11(2), 1679-1696. https://doi.org/10.1016/j.asoc.2010.04.024 
  2. Storn, R., & Price, K. (1997). Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341-359. https://doi.org/Doi 10.1023/A:1008202821328 
  3. Surjanovic, S., & Bingham, D. (2013a). ACKLEY FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/ackley.html
  4. Surjanovic, S., & Bingham, D. (2013b). GRIEWANK FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/griewank.html
  5. Surjanovic, S., & Bingham, D. (2013c). MICHALEWICZ FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/michal.html
  6. Surjanovic, S., & Bingham, D. (2013d). POWELL FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/powell.html
  7. Surjanovic, S., & Bingham, D. (2013e). RASTRIGIN FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/rastr.html
  8. Surjanovic, S., & Bingham, D. (2013f). ROSENBROCK FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/rosen.html
  9. Surjanovic, S., & Bingham, D. (2013g). SCHWEFEL FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/schwef.html
  10. Surjanovic, S., & Bingham, D. (2013h). SPHERE FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/spheref.html
  11. Surjanovic, S., & Bingham, D. (2013i). SUM SQUARES FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/sumsqu.html
  12. Surjanovic, S., & Bingham, D. (2013j). ZAKHAROV FUNCTION. Simon Fraser University. Retrieved Jun. 19 from http://www.sfu.ca/~ssurjano/zakharov.html
  13. Wu, G., Mallipeddi, R., Suganthan, P. N., Wang, R., & Chen, H. (2016). Differential evolution with multi-population based ensemble of mutation strategies. Information Sciences, 329, 329-345. https://doi.org/10.1016/j.ins.2015.09.009 
  14. Zhu, W., Tang, Y., Fang, J.-a., & Zhang, W. (2013). Adaptive population tuning scheme for differential evolution. Information Sciences, 223, 164-191. https://doi.org/10.1016/j.ins.2012.09.019 

留言