SMCB-E-08102005-0551.R2 6 Because FEP [39]and OGA/Q [40]obtained good -93.4804189,which is even much worse than the worst FV performances in solving UCOPs,comparisons are made among (-99.4393027)of OEA.On the other hand.since the NFE of FEP,OGA/Q,and OEA.Since the termination criteria used in OEA and OGA/Q are similar,and the mean running times of [39]and [40]are different significantly,to establish a fair OEA are shorter than those of OGA/Q on all the 6 functions. comparison basis,we implemented FEP and OGA/Q,and ran OGA/Q needs more computational cost than OEA.OGA/Q the three algorithms in the same environment.The parameters of applies orthogonal design to select offspring when each time FEP and OGA/Q are set according to [39]and [40],respectively, performing the orthogonal crossover,which increases the and those of OEA are set as follows:N=150,Maxos-20, computational cost. A.S-0.8,and CS=0.6.Since the number of function evaluations (NFE)of OEA and OGA/Q is different in each generation,FEP, OGA/Q,and OEA are terminated when the NFE is larger than IV.EXPERIMENTAL STUDIES ON CONSTRAINED OPTIMIZATION 300 000.The experimental results of FEP,OGA/Q,and OEA PROBLEMS are obtained over 50 independent trials.All the three algorithms In this section,13 benchmark functions (G01-G13)and 4 are realized by Delphi 5 on a 2.4GHz Pentium PC with 1G well-studied engineering design problems (Welded Beam RAM,and the operating system is Windows XP. Design,Spring Design,Speed Reducer Design,and Three-Bar A.Experimental Results of OEA Truss Design)are used to validate the performance of OEA in Table I summarizes the experimental results of OEA,which solving COPs.These functions are described in [19]and [20]. include the best,the mean,the standard deviation,and the worst The equality constraints have been converted into inequality function value (FV)found.Both the mean running time and the constraints,(x)0,using the degree of violation =104,the mean NFE are given.Table I also shows the global optimum for same with that of [19]. each function.What should be noted is the global optimum for Since RY [19]was a new kind of constraints handling F14 given in [40]is-99.2784,but the Best FV found by OEA is technique and obtained a good performance,we first 99.5643815 implemented RY and made a thorough comparison between RY As can be seen,the best,the mean,and the worst FVs of all and OEA on both G01-G13 and the 4 engineering design functions other than F05 are equal or very close to the global problems.Then,comparisons were made between SMES [18] optima,and the standard deviations are relatively small.The and OEA on G01-G13 and between SCA [20]and OEA on the 4 mean running times of the functions other than F12 and F14 are engineering design problems.The parameters of RY are set between 0.5 and 2 seconds.Especially,those of F01,F02,and according to [19],and those of OEA are set as follows:N=1500, F04-F07 are shorter than one second.Although that of F14 is Maxos,AS,and CS are the same with those of Section IIl.Both 6.570s,it is mainly due to the higher computational cost RY and OEA are terminated when the NFE is larger then required by the function itself. 240000 for G01-G13 and 24000 for the 4 engineer design problems.The experimental results of RY and OEA are B.Comparison between OEA and FEP obtained over 50 independent trials.The running environment is The comparison is shown in Table II.As can be seen,the the same with that of Section III. mean FVs of OEA are better than those of FEP on all functions A.Experimental Results of OEA other than F06.For F06,both OEA and FEP find the exact global optimum.On the other hand,since the NFE of OEA and G01-G13 are solved by OEA with two kinds of constraints FEP are similar,and the mean running times of OEA are handling techniques.The penalty coefficient A in(4)adopted by significantly shorter than those of FEP on all functions,FEP each function is shown in(20),and Table IV summarizes the definitely needs more computational cost than OEA.Although experimental results ofOEA,which include the best,the median, FEP is simple and has no complicated computation,FEP needs the mean,the standard deviation,and the worst FV found.Both to generate normally and Cauchy distributed random numbers, the mean running time and the mean NFE are given.Both OEA which spends lots of computational cost. with CHp and CHe provide 100%feasible solutions for all functions. C.Comparison between OEA and OGA/O Ae01-0.5 402=100 Aeo3=105 A0u=104 The comparison is shown in Table III.Because OGA/Q used 4G05=10 Aeo6-=5000 Am=1000 Aos=1000 the orthogonal design to generate the initial population,when (20) the global optima are at the middle point of the search space, Ae09-500 A10-5×10°Am=10 AG2-100 such as F01-F04,F06,F07,and F09-F11,the global optima 43-0.05 always exist in the initial population of OGA/Q.Therefore,the As described in Table IV,both OEA with CHp and CHc have comparison between OEA and OGA/Q is only made on F05, consistently found the global optima for all trials for G03,G04, F08.andF12-F15. G06,G08,G11,and G12.For GO1,G05,G10,and G13,OEA As can be seen,the mean FVs of OEA are better than those of with CHp outperforms OEA with CHc in terms of all the four OGA/Q on all the 6 functions.Especially for F14,the mean FV criteria.For G02,G09,and G07,OEA with CHc outperforms of OEA is -99.5024042 while that of OGA/Q is only OEA with CHp in terms of some criteria.In the computational
SMCB-E-08102005-0551.R2 6 Because FEP [39] and OGA/Q [40] obtained good performances in solving UCOPs, comparisons are made among FEP, OGA/Q, and OEA. Since the termination criteria used in [39] and [40] are different significantly, to establish a fair comparison basis, we implemented FEP and OGA/Q, and ran the three algorithms in the same environment. The parameters of FEP and OGA/Q are set according to [39] and [40], respectively, and those of OEA are set as follows: No=150, MaxOS=20, AS=0.8, and CS=0.6. Since the number of function evaluations (NFE) of OEA and OGA/Q is different in each generation, FEP, OGA/Q, and OEA are terminated when the NFE is larger than 300 000. The experimental results of FEP, OGA/Q, and OEA are obtained over 50 independent trials. All the three algorithms are realized by Delphi 5 on a 2.4GHz Pentium PC with 1G RAM, and the operating system is Windows XP. A. Experimental Results of OEA Table I summarizes the experimental results of OEA, which include the best, the mean, the standard deviation, and the worst function value (FV) found. Both the mean running time and the mean NFE are given. Table I also shows the global optimum for each function. What should be noted is the global optimum for F14 given in [40] is –99.2784, but the Best FV found by OEA is -99.5643815. As can be seen, the best, the mean, and the worst FVs of all functions other than F05 are equal or very close to the global optima, and the standard deviations are relatively small. The mean running times of the functions other than F12 and F14 are between 0.5 and 2 seconds. Especially, those of F01, F02, and F04-F07 are shorter than one second. Although that of F14 is 6.570s, it is mainly due to the higher computational cost required by the function itself. B. Comparison between OEA and FEP The comparison is shown in Table II. As can be seen, the mean FVs of OEA are better than those of FEP on all functions other than F06. For F06, both OEA and FEP find the exact global optimum. On the other hand, since the NFE of OEA and FEP are similar, and the mean running times of OEA are significantly shorter than those of FEP on all functions, FEP definitely needs more computational cost than OEA. Although FEP is simple and has no complicated computation, FEP needs to generate normally and Cauchy distributed random numbers, which spends lots of computational cost. C. Comparison between OEA and OGA/Q The comparison is shown in Table III. Because OGA/Q used the orthogonal design to generate the initial population, when the global optima are at the middle point of the search space, such as F01-F04, F06, F07, and F09-F11, the global optima always exist in the initial population of OGA/Q. Therefore, the comparison between OEA and OGA/Q is only made on F05, F08, and F12-F15. As can be seen, the mean FVs of OEA are better than those of OGA/Q on all the 6 functions. Especially for F14, the mean FV of OEA is -99.5024042 while that of OGA/Q is only -93.4804189, which is even much worse than the worst FV (-99.4393027) of OEA. On the other hand, since the NFE of OEA and OGA/Q are similar, and the mean running times of OEA are shorter than those of OGA/Q on all the 6 functions, OGA/Q needs more computational cost than OEA. OGA/Q applies orthogonal design to select offspring when each time performing the orthogonal crossover, which increases the computational cost. IV. EXPERIMENTAL STUDIES ON CONSTRAINED OPTIMIZATION PROBLEMS In this section, 13 benchmark functions (G01-G13) and 4 well-studied engineering design problems (Welded Beam Design, Spring Design, Speed Reducer Design, and Three-Bar Truss Design) are used to validate the performance of OEA in solving COPs. These functions are described in [19] and [20]. The equality constraints have been converted into inequality constraints, |h(x)|-δ≤0, using the degree of violation δ=10-4, the same with that of [19]. Since RY [19] was a new kind of constraints handling technique and obtained a good performance, we first implemented RY and made a thorough comparison between RY and OEA on both G01-G13 and the 4 engineering design problems. Then, comparisons were made between SMES [18] and OEA on G01-G13 and between SCA [20] and OEA on the 4 engineering design problems. The parameters of RY are set according to [19], and those of OEA are set as follows: No=1500, MaxOS, AS, and CS are the same with those of Section III. Both RY and OEA are terminated when the NFE is larger then 240000 for G01-G13 and 24000 for the 4 engineer design problems. The experimental results of RY and OEA are obtained over 50 independent trials. The running environment is the same with that of Section III. A. Experimental Results of OEA G01-G13 are solved by OEA with two kinds of constraints handling techniques. The penalty coefficient A in (4) adopted by each function is shown in (20), and Table IV summarizes the experimental results of OEA, which include the best, the median, the mean, the standard deviation, and the worst FV found. Both the mean running time and the mean NFE are given. Both OEA with CHp and CHc provide 100% feasible solutions for all functions. 5 4 G01 G02 G03 G04 G05 G06 G07 G08 6 G09 G10 G11 G12 G13 =0.5 =100 =10 =10 =10 =5000 =1000 =1000 =500 =5 10 =10 =100 =0.05 AAA A AA A A AA A A A × (20) As described in Table IV, both OEA with CHp and CHc have consistently found the global optima for all trials for G03, G04, G06, G08, G11, and G12. For G01, G05, G10, and G13, OEA with CHp outperforms OEA with CHc in terms of all the four criteria. For G02, G09, and G07, OEA with CHc outperforms OEA with CHp in terms of some criteria. In the computational
SMCB-E-08102005-0551.R2 7 cost,the mean running times of all functions other than G02 and the four criteria. G12 are shorter than 0.5 second. The 4 engineering design problems are solved by OEA with CHc only.Table V summarizes the experimental results.OEA V.PARAMETER ANALYSES OF OEA provides 100%feasible solutions for all functions.As described in Table V.the standard deviations of the 4 problems are There are 4 parameters in OEA,namely,No,AS,CS,and Maxos.To study the sensitivity of OEA to these parameters,a relatively small,so the performance of OEA is very stable in series of empirical experiments are carried out on OEA with solving these problems.Moreover,the mean running times of different values of No,AS,CS,and Maxos. all the 4 functions are shorter than 50 milliseconds,which illustrates that the computational cost of OEA is very low. A.Effects of N on the Performance of OEA In the whole,OEA with CHp outperforms OEA with CHc In general,the fitness landscape of COPs is more complicated But the penalty coefficient in OEA with CHp needs to be tuned than that of UCOPs.such that algorithms are of a high for different problems,and this is inconvenient in real probability of trapping into the local optima.Therefore,many applications.On the contrary,although the performance of OEA researchers focus on developing new methods to handle the with CHc is not as good as that of OEA with CHp,the solution constraints.But the results of Tables IV-IX indicate that OEA quality of OEA with CHc is still competitive with that of OEA with a simple penalty term can obtain very good results.We with CHp.Moreover,no parameter needs to be tuned in OEA think this benefits mainly from the large population,that is, with CHc. N=1500,and the search mechanism of OEA.A common B.Comparison between OEA and RY opinion among researchers is that a large population can make The comparison on G01-G13 is shown in Table VI.As can be algorithm have a little chance to get trapped into the local seen,for G03,G04,G08,G11,and G12,both OEA and RY optima,but maybe reduce the convergence rate.Therefore,to have consistently found the global optima for all trials.For G02 study the effects of N.on the performance ofOEA with CHp,N G06,and G09,both OEA with CHp and CHc outperform RY in increases from 150 to 1500 in steps of 450.Here,Maxos=20, AS-0.8.and CS=0.6.Fig.4 shows the evolutionary process of terms of all the four criteria.For the other functions,OEA the mean best solutions over 50 trials for the 4 more difficult outperforms RY in terms of some criteria while is also functions,G01,G05,G06,and G10. outperformed by RY in terms of some criteria.For G05,OEA with CHp and RY find the same best solution,which is even As can be seen,for the 4 functions,N=150'displays a faster convergence rate in the beginning,but it is overtaken by better than the global optimum.This is the consequence of using N。-600',W。=1050',andN。-l500'quickly.As a result, inequalities to approximate equalities,although a very small is N=150'is obvious worse than the 3 others on the whole used.In the computational cost,the mean running times of OEA evolutionary process.In order to compare N.=600',N.=1050', are significantly shorter than those of RY on all functions,so RY definitely needs much more computational cost than OEA. and N=1500'further,we magnify them in the top-right part of each graph. The comparison on the 4 engineer design problems is shown in Table VII.As can be seen,except that the Best FV of RY for On the whole,the evolutionary process of a small population is much easier trapped into the local optima than that of a large Welded Beam Design is better than that of OEA,OEA population,and OEA with a large population can also converge outperforms RY on other functions in terms of all the four fast.We think this benefits mainly from the search mechanism criteria.Moreover,the mean running times of OEA are still of OEA.OEA searches around each leader by the annexing much shorter than those of RY. operator,which is equivalent to performing a hill-climbing To summarize,both OEA with CHp and CHc are competitive operator on the individual.As a result,once a promising with RY,which illustrate that OEA has an effective search ability,and OEA incorporated simple constraints handling individual appears in the population,it can quickly climb to the crest with a high probability. techniques can obtain good performances in solving COPs. B.Effects of AS and CS on the Performance of OEA C.Comparison between OEA and SMES on G01-G13 Benchmark functions,F01-F15,can be divided into four The comparison is shown in Table VIll where the results of groups,that is,unconstrained unimodal functions, SMES are obtained from [18].As can be seen,under the same unconstrained multimodal functions,equality constraints amount of the NFE,the performance of OEA is competitive functions and inequality constraints functions.So two functions with that of SMES are chosen from each group to use in this subsection,and A.S and D.Comparison between OEA and SCA on the 4 Engineering CS are analyzed on the criterion of Average Success Ratio, Design Problems Definition 4:If a trial satisfies (21).then the trial is called The comparison is shown in Table IX where the results of success;otherwise failure, SCA are obtained from [20].The NFE and the solution vector lF'-Fs Ke.IFI F≠0 for the Best FV are also compared.As can be seen,OEA (21) F*=0 significantly outperforms SCA for the 4 problems in terms of all IFkn Ke where Fbes denotes the best solution found by the trial,and F
SMCB-E-08102005-0551.R2 7 cost, the mean running times of all functions other than G02 and G12 are shorter than 0.5 second. The 4 engineering design problems are solved by OEA with CHc only. Table V summarizes the experimental results. OEA provides 100% feasible solutions for all functions. As described in Table V, the standard deviations of the 4 problems are relatively small, so the performance of OEA is very stable in solving these problems. Moreover, the mean running times of all the 4 functions are shorter than 50 milliseconds, which illustrates that the computational cost of OEA is very low. In the whole, OEA with CHp outperforms OEA with CHc. But the penalty coefficient in OEA with CHp needs to be tuned for different problems, and this is inconvenient in real applications. On the contrary, although the performance of OEA with CHc is not as good as that of OEA with CHp, the solution quality of OEA with CHc is still competitive with that of OEA with CHp. Moreover, no parameter needs to be tuned in OEA with CHc. B. Comparison between OEA and RY The comparison on G01-G13 is shown in Table VI. As can be seen, for G03, G04, G08, G11, and G12, both OEA and RY have consistently found the global optima for all trials. For G02, G06, and G09, both OEA with CHp and CHc outperform RY in terms of all the four criteria. For the other functions, OEA outperforms RY in terms of some criteria while is also outperformed by RY in terms of some criteria. For G05, OEA with CHp and RY find the same best solution, which is even better than the global optimum. This is the consequence of using inequalities to approximate equalities, although a very small δ is used. In the computational cost, the mean running times of OEA are significantly shorter than those of RY on all functions, so RY definitely needs much more computational cost than OEA. The comparison on the 4 engineer design problems is shown in Table VII. As can be seen, except that the Best FV of RY for Welded Beam Design is better than that of OEA, OEA outperforms RY on other functions in terms of all the four criteria. Moreover, the mean running times of OEA are still much shorter than those of RY. To summarize, both OEA with CHp and CHc are competitive with RY, which illustrate that OEA has an effective search ability, and OEA incorporated simple constraints handling techniques can obtain good performances in solving COPs. C. Comparison between OEA and SMES on G01-G13 The comparison is shown in Table VIII where the results of SMES are obtained from [18]. As can be seen, under the same amount of the NFE, the performance of OEA is competitive with that of SMES. D. Comparison between OEA and SCA on the 4 Engineering Design Problems The comparison is shown in Table IX where the results of SCA are obtained from [20]. The NFE and the solution vector for the Best FV are also compared. As can be seen, OEA significantly outperforms SCA for the 4 problems in terms of all the four criteria. V. PARAMETER ANALYSES OF OEA There are 4 parameters in OEA, namely, No, AS, CS, and MaxOS. To study the sensitivity of OEA to these parameters, a series of empirical experiments are carried out on OEA with different values of No, AS, CS, and MaxOS. A. Effects of No on the Performance of OEA In general, the fitness landscape of COPs is more complicated than that of UCOPs, such that algorithms are of a high probability of trapping into the local optima. Therefore, many researchers focus on developing new methods to handle the constraints. But the results of Tables IV-IX indicate that OEA with a simple penalty term can obtain very good results. We think this benefits mainly from the large population, that is, No=1500, and the search mechanism of OEA. A common opinion among researchers is that a large population can make algorithm have a little chance to get trapped into the local optima, but maybe reduce the convergence rate. Therefore, to study the effects of No on the performance of OEA with CHp, No increases from 150 to 1500 in steps of 450. Here, MaxOS=20, AS=0.8, and CS=0.6. Fig.4 shows the evolutionary process of the mean best solutions over 50 trials for the 4 more difficult functions, G01, G05, G06, and G10. As can be seen, for the 4 functions, ‘No=150’ displays a faster convergence rate in the beginning, but it is overtaken by ‘No=600’, ‘No=1050’, and ‘No=1500’ quickly. As a result, ‘No=150’ is obvious worse than the 3 others on the whole evolutionary process. In order to compare ‘No=600’, ‘No=1050’, and ‘No=1500’ further, we magnify them in the top-right part of each graph. On the whole, the evolutionary process of a small population is much easier trapped into the local optima than that of a large population, and OEA with a large population can also converge fast. We think this benefits mainly from the search mechanism of OEA. OEA searches around each leader by the annexing operator, which is equivalent to performing a hill-climbing operator on the individual. As a result, once a promising individual appears in the population, it can quickly climb to the crest with a high probability. B. Effects of AS and CS on the Performance of OEA Benchmark functions, F01-F15, can be divided into four groups, that is, unconstrained unimodal functions, unconstrained multimodal functions, equality constraints functions and inequality constraints functions. So two functions are chosen from each group to use in this subsection, and AS and CS are analyzed on the criterion of Average Success Ratio, Definition 4: If a trial satisfies (21), then the trial is called success; otherwise failure, | ||| 0 | | 0 best best FF F F F F ε ε ∗ ∗∗ ∗ − <⋅ ≠ < = (21) where Fbest denotes the best solution found by the trial, and F*