Discrete/Binary Approach - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 155

Table 6.19. Computational Results of DDE algorithm

Instance OPT n opt Δ avg Δ min Δ max I avg I min I max t avg t min t max

11 I 51 174 5 0 0 0 1 1 1 0.04 0.02 0.06

14S 70 316 5 0 0 0 1 1 1 0.04 0.03 0.05

16 I 76 209 5 0 0 0 1 1 1 0.05 0.05 0.06

16PR76 64925 5 0 0 0 1 1 1 0.06 0.05 0.06

20KROA100 9711 5 0 0 0 1 1 1 0.09 0.08 0.09

20KROB100 10328 5 0 0 0 1 1 1 0.09 0.08 0.09

20KROC100 9554 5 0 0 0 1 1 1 0.08 0.08 0.09

20KROD100 9450 5 0 0 0 1 1 1 0.08 0.08 0.09

20KROE100 9523 5 0 0 0 1 1 1 0.09 0.08 0.09

20 99 497 5 0 0 0 1 1 1 0.08 0.08 0.09

20RD100 3650 5 0 0 0 1 1 1 0.09 0.08 0.09

21 I 101 249 5 0 0 0 1 1 1 0.08 0.08 0.09

21LIN105 8213 5 0 0 0 1 1 1 0.1 0.09 0.11

22PR107 27898 5 0 0 0 1 1 1 0.1 0.09 0.11

25PR124 36605 5 0 0 0 1 1 1 0.13 0.13 0.14

26BIER127 72418 5 0 0 0 1 1 1 0.14 0.13 0.14

28PR136 42570 5 0 0 0 1 1 1 0.18 0.16 0.19

29PR144 45886 5 0 0 0 1 1 1 0.18 0.17 0.2

30KROA150 11018 5 0 0 0 1 1 1 0.2 0.19 0.2

30KROB150 12196 5 0 0 0 1 1 1 0.2 0.19 0.2

31PR152 51576 5 0 0 0 1.2 1 2 0.22 0.19 0.28

32U159 22664 5 0 0 0 1 1 1 0.23 0.22 0.24

39 195 854 5 0 0 0 1.4 1 2 0.42 0.36 0.48

40D198 10557 5 0 0 0 1.4 1 2 0.44 0.38 0.52

40KROA200 13406 5 0 0 0 1.2 1 2 0.41 0.38 0.48

40KROB200 13111 5 0 0 0 7 1 22 0.93 0.41 2.03

45TS225 68340 3 0.04 0 0.09 9.8 1 33 1.32 0.47 3.05

46PR226 64007 5 0 0 0 1 1 1 0.42 0.41 0.44

53GIL262 1013 2 0.41 0 0.69 11.4 1 44 2 0.72 5.36

53PR264 29549 5 0 0 0 1.4 1 3 0.79 0.67 1.23

60PR299 22615 2 0.05 0 0.09 11.2 6 19 3.24 2.5 5.36

64LIN318 20765 5 0 0 0 14.2 3 45 4.37 2.13 10.28

80RD400 6361 5 0 0 0 14.8 11 18 8.3 6.86 9.97

84FL417 9651 3 0.01 0 0.02 13.8 8 24 6.86 4.58 10.88

88PR439 60099 5 0 0 0 15.2 8 23 8.54 6.06 11.08

89PCB442 21657 5 0 0 0 19 10 35 11.72 7.86 17.8

Overal Avg 4.72 0.01 0 0.02 4.03 2.11 8.22 1.45 1 2.27

36 problems, the DDE algorithm obtained the optimal solution in every trial. The DDE
algorithm solved all the problems with a 0.01% deviation on average, 0.00% deviation
on minimum and 0.02% deviation on maximum. The overall hit ratio was 4.72, which
indicates that the DDE algorithm was able to find the 95% of the optimal solutions on
overall average. The worst case performance was never more than 0.02% above optimal