Analyzing the Simple Ranking and Selection Process for Constrained Evolutionary Optimization

Elfeky EZ, Sarker RA, Essam DL. Analyzing the simple ranking and selection process for constrained evolutionaryoptimization. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 23(1): 19 34 Jan. 2008Analyzing the Simple Ranking and Selection Process for ConstrainedEvolutionary OptimizationEhab Z. Elleky, Ruhul A. Sarker, and Daryl L. EssamSchool of Information Technology and Elctrical Engineering, University of New South Wales, ADFA CampusCanberra 2600, AustraliaE-mail: {elfeky, r.sarker, d.essam }@adfa.edu.auRevised November 20, 2007.Abstract Many optimization problems that involve practical applications have functional constraints, and some ofthese constraints are active, meaning that they prevent any solution from improving the objective function value tothe one that is better than any solution lying beyond the constraint limits. Therefore, the optimal solution usuallylies on the boundary of the feasible region. In order to converge faster when solving such problems, a new rankingand selection scheme is introduced which exploits this feature of constrained problems. In conjunction with selection,a new crossover method is also presented based on three parents. When comparing the results of this new algorithmwith six other evolutionary based methods, using 12 benchmark problems from the literature, it shows very encouragingperformance. T-tests have been applied in this research to show if there is any statistically significance diferencesbetween the algorithms. A study has also been carried out in order to show the effect of each component of the proposedalgorithm.Keywords constrained continuous optimization, evolutionary computation, genetic algorithms, multi-parent crossover1 IntroductionLemongel2), Debl3), Koziel and Michalewicxl4, Far-mani and Wrightl5 and Venkatraman and Yenl6l andMany optimization problems are nonlinear and con-others) attempted to solve constrained problems us-strained. These problems can be represented as fol-ing traditional GAs. Also, Runarsson and Yaol7] delows:veloped an Evolution Strategies (ES) based approachfor solving constrained optimization problems. Theyminf(X)，s.t. g;(X)≤0， i= 1,2...,m,showed that their algorithm outperforms GA based ap-h;(X)≤0，j= 1,2.....proaches for 12 well-known test problems. In this pa-Li≤x;≤U; i= 1,2...n,per, we analyze the different combinations of operators1)and mechanisms, in order to design a new GA basedwhere x∈R" is the vector of solutions x = approach for solving certain casses of constrained op-[x1，2..... The objective function is f(X), mtimization problems. For this purpose, we have de-is the mumber of inequality cnstraints, g(X) is the signed a new ranking and slection method, and a newi-th inequality constraint, p is the number of equalitycrossover method.constraints, and hj(X) is the j-th equality constraint.It is a common situation for many constrained op-Each deision variable has a lower bound L, and an timization problems that some constraints are activeat the global optimum point, thus the optimum pointupper bound U;.Over the last two decades, Evolutionary Algorithmslies on the boundary of the feasible spacel4l. This is(EAs) have proved themselves as global optimizationusually true for business applications with limited re-techniques. Among the evolutionary algorithms, Gsources. In such cases, it seems natural to restrict thenetic Algorithms (GAs) are the most widely usedsearch of the solution to near the boundary of the fea-technique for solving optimization problems. Con-sible space(8l. However, this may not be the situationstrained optimization problems have been consideredfor中国煤化工$ engineering designas dificult problems. Many researchers and practi- andAsYHCNMHGeyelementofGAs.tioners (including Mezura and Coellol1, Barbosa andRegular Paper20J. Comput. Sci & Technol, Jan. 2008, Vol.23, No.1Many studies have been carried out to show how this new offspring. There are three most commonly usedoperator afects the evolutionary process. The most ranking and selection methods. First, fitness propor-widely used crossover methods are k- point, uniform,. tional reproduction, in this scheme individuals are cho-intermediate, global discrete, order-based, and matrix- sen for selection in proportion to their fitness value.based[9]. Most of these crossovers are based on twoIn the second method, rank based selection, the popu-parents. However, Eiben et al.l10l introduced a multi- lation is sorted from best to worst; then the higherparent reproduction process to GAs. They have in- ranked individuals are given higher probabilities todicated that increasing the number of parents in the survivel9. The third method is tournament selection,crossover leads to more reliable offspring. As they re- where a random number of individuals are chosen fromported, performance increased up to a certain num- the population (with or without replacement) and theber of parents and then decreased. They concluded best individual from this group is chosen as a par-that the improvement was at the maximum level when ent for the next generation9. These processes are re-changing the number of parents from2 to3. So it was peated until the mating pool is flled. There are a va-not worthwhile going beyond 3 or 4 parentslo. Note riety of other selection methods, including stochasticthat Eiben et aliol have applied their genetic algo- methodsl7. In this paper, we introduce an algorithmrithm with a binary representation.which uses a tournament selection in some stages ofAs we are dealing with constrained problems, the the evolution process, and uses a new ranking methodfeasibility ratio (the ratio between the number of feasi- in other stages. This will be discussed later in moreble individuals and the total population size) plays an detail.important role in the search process and can thus beThe penalty function is the most widely usedconsidered as an indicator for diversity. Hence, a wider method to deal with constraints in constrained op-range of feasibility ratios would usually help to locate timization. The penalty techniques used are: static,more diverse solutions around the boundary of the fea- dynamic, annealing, adaptive, death penalties, supe-sible space. In this paper, the purpose of designing a riority of feasible points, and faster adaptive meth-three-parent crossover is to generate offspring close to ods. A good comparison and analysis of these meth-:he boundary of the feasible region. For this reason， ods can be found in Sarker and Newton!13). Farmaniwe choose parents from both feasible and infeasible and Wright(5l designed a two-stage dynamic penaltyregions for crossover. Such a multi- parent crossover method which applies a small penalty for slightly in-should speed up convergence when assisted by the se- feasible solutions with reasonable fitness values. Inlection mechanism which will be discussed in a later this way, it permits those infeasible individuals be sur-section.vive and be promoted to a feasible region near theWithout mutation, GAs could become trapped in optimal solution. Venkatraman and Yenl6] proposeda local optimum while solving complex optimization a two-stage approach to solve constrained problemsproblems. Among others, uniform and non-uniform using GA. In the first stage, it deals with the con-mutations are well known in GA applications. Uni- straints simply like a constraint satisfaction problem.form mutation uses uniform random changes to indi- In the second stage, the algorithm handles the explo-viduals, which favors diversity but slows down con- ration and exploitation using non-dominated rankingvergence. Alternatively, Michalewicz 1 proposed a and elitism respectively. In this paper, we have calcu-dynamic non-uniform mutation to reduce the disad- lated the constraint violation without penalizing thevantage of uniform mutation in real-coded GA. Also，individuals, and we have used this information to rankZhao et al.12] reported that a non-uniform mutation and select the individuals as parents as detailed later.operator has the feature of searching the space uni-The developed algorithm was tested using twelveformly during the early stage and very locally in the benchmark problems from the specialized literature,later stage. In other words, that non-uniform muta- and was compared with five other GA-based and onetion has the common merits of a higher probability of ES-based algorithms. From the comparisons, we canmaking long jumps at early stages, and also a much claim that the proposed algorithm performing verybetter local fine-tuning ability in later stagesl2. We well for the twelve constrained optimization problemshave introduced a mutation that uses both uniform tested. Since F 4and non-uniform mutation, to exploit the advantages cal to中国煤化工s betwen the algo-of both of them.rithm!|Y片CNMHGcouldsimplybeanIn GA applications, there are many different ways outlier. ror uns purpose, we nave analyzed the resultsto select good individuals to survive and reproduce using mean and standard deviations, and performed aEhab z. Elfeky et al: Ranking & Selection for Constrained Optimization2series of t-tests. The results of t-tests provide usefuland search process should concentrate on the individ-insight of the stochastic search algorithms. We haveuals in that region. Therefore, the ranking scheme isalso analyzed the contribution of individual compo-designed as follows.nents of the proposed algorithm, which consequently●The feasible individuals are ordered from the bestjustifies the inclusion of these components.to the worst based on their objective function value.This paper is organized as follows, Section 2●Then, those solutions are divided into two groups.presents the proposed algorithrn, experimental studyGroup (a) has a fixed proportion of those with higheris stated in Section 3, analysis of results is provided in quality (smaller objective function), and group (6) hasSection 4, and finally, the conclusion in Section 5.lower quality feasible solutions. As the group (6) in-2 The Proposed Algorithmdividuals are on the worse side of the feasible region.In this section, we present our proposed algorithm.Hence, they should not be considered in the selectionprocess, as they will slow down the algorithm conver-This algorithm uses a floating point representation, genceand the main steps are as follows., The infeasible individuals are arranged in ascend-1) Create random initial population.ing order of the constraint violations. A given pro-2) Check feasibility of all individuals.portion of the individuals with highest violations (of3) Evaluate the population.all constraints) are discarded from the selection pro-4) If the stopping criterion has been met, stop; other-cess (see group (e) in Fig.1), because they are furtherwise continue. .5) If the feasibility ratio is between LR (lower limitaway from the feasible region and will slow down theof ratio) and UR (upper limit of ratio), apply thealgorithm convergence. We are fully aware that theseproposed ranking and selection scheme; otherwise,discarded individuals may diversify the search process,apply the regular tournament selection.but consider that this diversity requires more compu-6) Apply the triangular crossover.tational time.7) Apply the mixed mutation.●The rest of the infeasible individuals are then ar-8) Apply elitism by replacing the worst current indi-ranged in ascending order of their objective; functionvidual with the overall previous generations' bestvalues. All infeasible individuals who have worse ob-individual.jective function values than the best feasible individual9) Go to step 4).are then discarded from the selection (see group (d) inThe details of the components of our algorithm are Fig.1), because they will guide the search process indiscussed below.the wrong direction away from the optimal solution.2.1 Ranking●The remaining individuals are the target of theselection, because they are in the right space near toTo exploit the feature that optimal solutions exist both the optimal and feasible space (see group (c) inon the boundary of the feasible region, the selection Fig.1.Type CriteriaGroupFeaturesAction0(a) <0(b)Search Space着(a)●V(a)=0 .Consider(b)。0(b)>0(a)DiscardFeasible SpaceV(b)=0(0)■O(c) ≈0白(d★0(d)>0(a)V(d)>≈ 0△一 Optimal Solution中国煤化工iscardMHCNMH GFig.1. Ranking scheme in the proposed algorithm. 0(x) is the objective value of individuals in group (x), V(x) is the constraintsviolation of individuals in group (x).22J. Comput. Sci. & Technol, Jan. 2008, Vol.23, No.12.2 Selectionoptimal solution is not on the boundary, group (b) canUp to now, there are two groups of individuals tobe used instead of group (c). The pseudo-code for thestill be considered, group (a) which includes the in-selection process is shown in Fig.2.dividuals on the feasible side of the boundary of thefeasible region, and the other group (c) that includes 2.3 Triangular Crossoverthe individuals on the infeasible side. If there are in-Consider the new mating pool, each successivedividuals in group (c), then in the selection process,two fesible individuals will be selected from the frst group of three individuals are selected as parentsgroup, and one ifieasible individual will be seleted Pl,P2,P3. Next, choose any three random numbersfrom the second group, these three individuals will 12,T7, each of them in the interval (0,， 1!| wherethen undergo the triangular crossover process, other- r1 +r2+r3.=1, the resulted ofspring for the newwise all three individuals are chosen from group (a).generation will be constructed as a linear combinationof the three parents as follows.01 =(r1 xp1)+(r2Xp3)+(r3X P2), .1 if (reasibility ratio is inside the range [LR.. UR) dofor i:= 1 to population. size/3 do02=(r1 Xp2)+(r2Xp1) +(r3X P3), .国←random individual from group (a,03=(r1 Xp3)+(r2 xp2)+(r3Xp1).y←individual from group (a)Selecting two feasible parents and one infeasiblez←individual from group (c)parent gives a higher probability for the offspring tocopy individuals x,y, and z to the new mating poolbe feasible. The resulting offspring from this crossoverodof such selected individuals should ideally be nearer toelse {apply Deb's Methodl21}the boundary of the feasible region than their parentsfor i:= 1 to population. size dowere. The range of feasibility ratios controls the di-10a←random individualversity of the solutions, while the proposed crossover11b←random individualspeeds up the convergence of the search process.| 12if (a is infeasible and b is infeasible) then13if (a cnstr.violation < b cnstr_violation) then14copy individual a to the new mating pool2.4 Mutation1:elseWe have introduced a mixed uniform and non-16copy individual b to the new mating pool17uniform mutation to exploit the advantages of both18else if (a is feasible and b is feasible) thenmutation methods. The probability of mutation (pm)19if (a objective < b objective) thenis fixed during the whole evolution, but the step20size is nonlinearly decreased over time as stated byMichalewicz 川. There is also a low probability of do-ing a uniform mutation (pum) that moves an individ-fual to any part of the search space. In this way, the al-24else if (a is feasible and b is infeasible) thengorithm is converging during most of the evolution u18-25ing the non-uniform mutation, while at the same time26else if (a is infeasible and b is feasible) thenthere is some chance to explore the rest of the feasible27space in later generations using that part of the uni-form mutation. This method helps with sophisticated29multi-modal problems or problems with complicated30feasible fitness landscapes. The pseudo-code for the31 fimutation process is shown in Fig.3.Fig.2. Outline of the selection process.This ranking and selection scheme needs a reason-2.5 Constraints Handlingable amount of both feasible and infeasible individualsDeb3) introduced a method to handle constraints into work; therefore this mechanism is applied only whenan efi中国煤化工l infeasible individ-the feasibility ratio is between [LR, UR]= [0.3, 0.8] in uals wHCNMHG-nfeasible individualthis paper. Otherwise, the regular tournament selec-was as? worst feasible indi-tion is lused to select two individuals from the tourna- vidual. We used this method when the feasibility ratioment set and a third one randomly. In cases where thewas too low. After that, the constraint handling wasEhab Z. Elfeky et al: Ranking & Selection for Constrained Optimization23troducing a new search distribution. They reportedtwo sets of results, the first one is Improved Over-1for i:= 1 to population. size doPenalized approach (IOP), and the second one is Im-2for j:= 1 to chromosome. Jength doproved Stochastic Ranking (ISR). Currently, the re3if (random (0,1) ≤pm) thensults of this method are considered the best amongif (random (0, 1)≤pum) then {uniform}5δ:= 1the existing algorithms.6else {non-uniform}We have solved each test problem 30 times with7δ:= (mandom (0, 1)1一1)different random seeds. We have presented the best8ffitness values over 30 runs in Table 1. In all cases,9if (random(0,1)≤0.5) thenup to 350000 objective function evaluations had been的:= ij - random(0,δX Lj)made before stopping the algorithm, as a similar eval-elseuation budget was used in the other algorithms dis-12到:= xis + random(0,8xUg)cussed above. The population size was set to 30. Theprobability of crossover is 0.8 for using the whole arith-metic triangular crossover discussed earlier. The mu-15 odtation probability (pm) is 0.1 and for the proposedmutation we set the probability of using the uniformwhere random (a, b) is a random number within the rangemutation (pum) to 0.1.of [a,b], δ is the step length within range [0, 1], hence ifThe algorithms SR, I0P, and ISR have solved allit is 0 it will generate the same individual, and ifit is 1it will allow the individual to mutate to the edge of theof the 12 problems considered in this paper. How-domain boundary. t is the current generation number, T isever, KM, SAFF and VY solved 11 problems each.the maximum allowed generation number, b is a parameterKM failed to find any feasible solution for g05, andto control the spcod at which the step length decreases, inthis paper it is 4. Lj is the lower domain bound for theSAFF and VY did not report g12. ACM and DEBdecision variable j, Uj is the upper domain bound for thereported the results for only 4 and 5 test problemsdecision variable j, xij is the value of the decision variablerespectivelyl2,3]. We have not presented ACM andj in individual i.DEB results in this paper. However, interested readersFig.3. Outline of the mixed mutation process.can find them in our earlier paperl15]. We have pre-sented the available results of the six other algorithmsdone implicitly during the ranking and selectionalong with our results in Table 1.scheme, where we exclude high violation individuals;Considering the best results out of 30 indepen-therefore it converges to the feasible space over time.dent runs, we can claim that our proposed algorithmachieved superior results than the five GA-based algo-3 Experimental Resultsrithms (KM, DEB, ACM, SAFF and VY). If we com-In order to measure the performance of our de-pare the solutions of our algorithm with SR, both ofveloped algorithm, we have compared it, denoted asthem achieved the optimal solution in 7 test problemsTC (Triangular Crossover), with eight existing algo-g01, g03, g04, g06, g08, g11, and g12. In g05, the pro-rithms by solving twelve benchmark problems com-posed algorithm achieved the optimal solution whilemonly used by other researchers. The characteristicsSR achieved better than the reported optimal due toof the test problems can be found in Runarsson andconstraints relaxation. Our algorithm achieved bet-Yaol1. The algorithms compared are Barbosa andter solutions for test problem g02, while SR obtainedLemonge2 (denoted as ACM), Deb'sBl GA (DEB),the optimal solution for g09 where also our algorithmKoziel and Michalewicz's4 GA (KM), Farmani andachieved a very close to optimum solution. Moreover,Wright's5) denoted as SAFF and Venkatraman andSR was better for g07. Therefore, we can claim thatYen's(6l denoted as VY. Although these five methodsbased on the best solutions obtained, our algorithm isare GA based, Runarsson and Yaol7l has also intro-competitive to SR. However, I0P and ISR obtainedduced an evolution strategy method which dependsoptimal solutions in most cases.on stochastic ranking (SR). Recently, Runarsson andHowever, since GA and ES are stochastic algo-Yaol14l have revised their stochastic ranking algorithm,rithms中国煤化工- chastic comparisonwhich is now known as“search biases" , in that workinsteacEng the best fitnessthey treated the constraint violation as another ob-value.YHCNMHGcouldbemislead-jective and used the Pareto concept to handle theing as the best fitness value could simply be an outlier.constraints. They also improved the search by in- For this purpose, we have analyzed the mean and stan-24J. Comput. Sci. & Technol, Jan. 2008, Vol.23, No.1dard deviations of 30 independent runs for the seven has slightly better standard deviations in g11 and SRalgorithms discussed earlier. The mean and standard has slightly better standard deviations in g03 and g08.deviations are presented in Table 1. Note that the av-The proposed algorithm has better mean and standarderages for VY are not available as they reported me deviation in g02 and g06. SR has a better mean anddian data only. Also, the standard deviations for KMstandard deviation in g04, g05, and g07. SR has a bet-are not available.ter mean but worse standard deviation in g09. Theseresults emphasize TC and SR competitieness. NoticeAs shown in Table 1, both TC and SR have the that SR, I0P, ISR, and TC get the optimal solutionsame mean for g01, g03, g08, g11, and g12, but TCconstantly in 6, 7, 9 and 6 test problems respectively.Table 1. Resulte Out of 30 Runs of EBach Algorithm (VY=Venkatraman and Yen(6l, SAFF=Farmani and Wrightl5,KM = Koziel and Michalewic, SR-=Stochastic Ranking, I0P=Improved Over Penalized, ISR=Improved StochasticRanking, TC=Proposed Algorithm)fcn/mkBestMedianMeanSt. Dev.Worstg01-15.000VY8.51 x10-1-12.000SAFF- 15.0000.00 x 100KM- 14.786-14.708SR0.00 x100IOP1.30 x10-15ISR5.80 x10~14TCg02-0.803 619-0.803 190-0.755 3323.27 x10-2-0.672 169- -0.802 970-0.790 1001.20 x10-2-0.760 430-0.799 530-0.796 710-0.803 515-0.785 800- -0.781 9752.00 x10-2-0.726 288- 0.803 619-0.780843-0.7762832.30 x10-2-0.712818-0.803619-0.793082-0.782 7152.20 x10-2-0.723 591-0.803615-0.798174-0.796 0368.84 x10-3-0.777 435g03-1.000-0.9854.89 x10-2-0.7867.50 x10-5sR- 1.0001.90 x10-4-0.747-0.21-0.2571.90 x10-1-0.031- 1.001-1.0018.20 x10-9- -1.001一1.0004.02 x10-4g04-30665.539-30665.531- 30663.3643.31 x100- 30 651.960-3065.500- 30665.2004.85 x10-1.-30663.300-30664.500- 30655.300-30 665.539- 30 665.5392.00 x10-5I0P1.10 x10-11 .- 30665.539-30665539.-30665.539.1.10 x10-11- 30 665 539- 30665.302-30 665.5319.16 x10-3-30663.829g055 126.4985 126.5105170.5293.41 x1026112.2235 126.9895 432.0中国煤化工6 089.4305 126.4975127.3725128.8MYHCNMHG5142.4725173.9675 268.6102.00 x1025826.807To be continuedEhab Z. Elfeky et al: Ranking & Selection for Constrained Optimization2Continue from the previous pagefcn/m)BestMedianMeanSt. Dev.WorstISR5 126.4977.20 x10-13TC5 126 4985147.0535 28.1271.56 x1025562.850g06- 6961.814VY-6961.179-6959.5681.27 x10°-6954.319SAFF-6961.8000.00 x100-6952.100-6342.600SR- 6875.9401.60 x102- -6350.262IOP-6961.814-6 961.8141.90 x10-123.70 x10-12gO724.30624.411、26.7362.61 x10035.882 .24.48026.5801.14 x10028.400KM24.62024.82624.30724.3746.60 x10-224.64224. 3061.30 x10-324.3124.306.30 x10-524.74026.09225.9876.63 x10-127.659g08-0.095 825- 0.095 825-0.089 1572.60 x10-17- -0.095 8255.10 x10-172.70 x10-174.23 x10-17680.630680.762681.7067.44 x10-1684.131680.640680.7205.92 x10-2680.870680.910681.160680.641680.6563.40 x10-2680.7631.70 x10-73.20 x10-18680.631680.660680.6632.19 x10- 2680.707g107049.2487060.5537723.1677.97 x10212097.4087061.3407627.8903.73 x1028 288.7907 147.9008 163.6007 054.3167 559.192.5.30 x1028 835.6557 049.2487.50 x10-47049 2527049.2503.20 x10-37049.2707080.2657 703.4907 892.4707.41 x1029847.039g110.7500.7499.30 x10-30.8090.750 .8.00 x10-51.10 x10-160.7540.7566.90 x10-30.774g12-10000000中国煤化工THCNMHG- 0.99900To be continued26J Comput. Sci. & Technol, Jan. 2008, Vol.23, No.1Continue from the previous page_fcn/mkBestMedianMeanSt. Dev.WorstSR-1000000. 1.000 000- 1.000 0000.00 x100-1.000 000IOP-0.999 954-0.999 8891.50 x10-4-0.999 385ISR-1.0000001.20 x10-9- 1.0000004 Analysis of Resultslata. To make the t-test results more readable, weAs discussed in the earlier section, the mean andhave used“_”sign if the t-calculated is less than -2,standard deviation measures .do not provide precisewe have also used“+”sign if the t-calculated is greaterstatistical comparisons; hence we have used t-tests. Inthan +2, and finally we put“≈”sign if t-calculatedaddition, we have analyzed the effecti of the individualis between -2 and +2. As shown in Table 2, for agiven test problem, TC would be considered signif-components of the proposed algorithm.cantly better than any other comparable algorithm ifthere isa“-”sign, significantly worse if there isa“+”4.1 Statistical Testingsign and insignificant if there isa“≈”sign.The t-test is a statistical significance testing whichIt is clear from these results that TC outperformsassesses whether the mean of two groups are statis-SAFF as there is no significance difference in 7 testtically different from each other or not. The t-testproblems; however, TC is significantly better thanresults are meaningful when the distribution of theSAFF for the remaining 5 test problems. TC is quitesample follows normal distribution. The chi-square competitive with both SR and IOP, as they are signifi-goodness of ft test indicates that the sample undercantly better than TC in 3 and 4 test problems respec-the study is coming from normally distributed popu- tively; while at the same time TC is better than themlation. This decision has been made with a confdence in 2 and 3 test problems respectively. Overall, ISRlevel of 95%. The t-test only needs the mean and the is better than TC. However we have indicated“*” in-standard deviation of both groups. We apply it in this stead of“+”for g03 under ISR as their reported meanpaper with confidence level 95%, the t-test when calcu-value is better than the optimal due to the reportinglated at this level of confidence equals 2 at the degree of infeasible solutions which when applying the t-testof freedom level of 60.would naively show a significant difference. Comparedto ISR, TC is significantly better in g02 and g11.Table 2. t-Test Between TC and Each of the OtherIn both g04 and g07, SR, IOP, and ISR are signif-Algorithms at Signifcance Level 95%, i.e., t-Calculatedicantly better than TC. The t-test result shows thatis Greater Than 2TC is significantly better than all the three ES-basedSAFFalgorithms SR, IOP and ISR for g02. Runarsson andg01≈Yao14 stated about g02 that“This benchmark func-g02tion is knoun to have a very rugged fitness landscapeg03and in general the most difficult to solve of these func-g04tions" .g05+It is interesting to report that although TC has ob-g06tained an optimal solution for g04 and g05 (see Table071), SR is significantly better than TC when perform-g08ing the t-test (see Table 2). On the other hand, g06g09is the opposite case, where SR has obtained an opti-g10mal solution but TC is significantly better than SRg11These cases demonstrate that a statistical comparisonlike t-test is useful when comparing two stochastic al-Note:“-” means better significant difference, “+” meansgorithms, such as evolutionary algorithms which areworse significant difference, and“≈” means no significantdifference, * indicates not comparable.affect中国煤化工ed used to start theWe have performed t-tests between TC and each of mandevoluAYH_aim that the perfor-. CN M H Gis statialy bet-SAFF, SR, IOP, and ISP. The t-test between TC and ter compared to the performance of SAFF. To make/Y cannot be performed due to the absence of meanhe comparison more meaningful, we have also ex-Ehab Z. Elfeky et al: Ranking & Selection for Constrained Optimization27cluded the best and the worst of the 30 best solutions●t-calculated when comparing Selection Run withas outliers and have then applied the t-test on the newBase Run (S- B) which is the first column for eachsamples. However, we have not observed any signifi-test problem,cant changes. It is worth noting here that the mean●t-calculated when comparing Crossover Run withand standard deviation (excluding best and worst fit-Selection Run (C-S) which is the second column,ness values) for the later comparison were not avail-●t-calculated when comparing Mutation Run withable from Runarsson and Yao8!. However, we haveSelection Run (M-S) (third),calculated these accurately using a simple analyticalmethod.Crossover Run (M-C) (fourth),●t-calculated when comparing Final Run with4.2 Proposed Components EfectCrossover Run (F-C) (ffth), andIn order to see the effect of each component in the●t-calculated when comparing Final Run with Mu-tation Run (F-M) (sixth).proposed algorithm, we have designed a number of ex-periments as follows.For example, in Fig.4, the first column is represent-●Base Run: with regular tournament selection, twoing the result of the t-test between the Selection Runand the Base Run (S-B) and it has a negative valueparents crossover, and non-uniform mutation.●Selection Run: the same parameters as the baseless than 2, which implies that the ranking and selec-run, except replacing the tournament selection withtion component has an insignificantly BETTER effectthe proposed ranking and selection scheme as dis-on test problem g02. However, for test problem g04,the second column which represents the result of the t-cussed in Section 2.●Crossover Run: similar to the selection run, buttest between the Crossover Run and the Selection Runwith replacing two parents crossover with the triangu-has a negative value less than -2, which implies thatthe triangular crossover component has a significantlylar crossover.●Mutation Run: similar to selection run, exceptBETTER efect on test problem g04. Note that thereplacing the non-uniform mutation with the mixedcrossover effect is on the top of the ranking and selec-mutation (applying both uniform and non-uniform).tion effects.●Final Run: all the previously proposed compo-nents are included in this run.The proposed ranking and selection requires a goodmix of feasible and infeasible individuals in the pop-ulation. Hence, we have experimented with differentfeasibility ratios for when that selection is applied. Inparticular we have reported two sets of experiments inthis paper: (i) for LR= 0.4 and UR = 0.7, and (i)g05LR= 0.3 and UR = 0.8. As previously stated, if theg02feasibility ratio is outside this range, we use a regularg10tournament selection. Figs. 2 and 3 present the effect-6|g07 g09of each component on six test problems for the above_g04.two sets of experiments. We have considered only thetest problems g02, g04, g05, g07, g09, and g10 in thisOS-B ■C-S OM-S ■M-C DFC目F-Manalysis as we obtain optimal solutions easily for therest of the test problems in this paper.For each test problem under investigation in thisFig.4. Effeet of the components when the Proposed Rankingand Selection applied and the feasibility ratio between rangesection, we have run 30 times for each of the above0.4~0.7.runs. To evaluate the added value of each componentwe have performed t-tests (with confidence level 95%).The Base Run for g10 could not find any feasibleFor ease of explanation, we will indicate as BETTER solut中国煤化工e t-test between theif the added component improves the fitness value and SelecCAt the same time theWORSE if it deteriorates. In the fllowing few figures, selectfY片. C N MH Gtions, s0 we cnsiderthe t-test results are presented using six bars for each this as a significantly BETTER effect. As a result, theproblem, these represent:first bar is missing in the figures for g10.28J. Comput. Sci. & Technol, Jan. 2008, VoL.23, No.1In the first experiment, we applied the proposedThe proposed ranking and selection scheme dis-ranking and selection when the feasibility ratio was cards uncessary individuals from the search spacebetween 0.4 and 0.7. The results of this experimentsee Section 2). Apparently, it may seem that suchare presented in Fig.4, in which the proposed selection' an approach would reduce the diversity of the searchhas a BETTER efect, and usually significantly BET-process. In fact, the feasibility ratios, as discussed ear-TER (see S-B column in Fig.4). From the C-S and lier, control the diversity of the solutions of interest inM-S columns we can say that each of the proposedthe search process. The crossover is designed to speedcrossover and mixed mutation techniques do not haveup the convergence. In the next experiment, we in-any signifcantly WORSE individual effect, moreovercreased the probability of using the proposed rankingin most cases it has a significantly BETTER effect.and selection (by widening the feasibility ratio rangeThe column M-C tells us that.the individual effect ofto 0.3~0.8), which would further increase the diver-the proposed mutation is significantly BETTER thanity. The results of this experiment are presented inthe individual effect of the proposedcrossover in prob-Fig.5.lems g02, g04, g07, and g10, which is not the caseBy comparing Figs. 4 and 5, we can notice thatin g09 and g05; notice that g05 has 3 equality con-there are no changes in the efect of the proposed se-straints which is more dificult when the step lengthlection and ranking. On the other hand, the crossoverof mutation is increased. When the columns F-C andeffect is generally worse after increasing the diversity;F-M are compared it is apparent that the combinedhowever g02 is insignificantly better affected. At theeffect of both the proposed crossover and mutationsame time, there are no significant changes in the effectis better than the individual effect of any of them inof the proposed mutation. It means that increasing theg04 and g05. In g02 the WORSE individual efect ofdiversity has a BETTER effect on g02 in the crossoverthe crossover is hampering the combined effect (inalrun, but it has a WORSE efect on the crossover run inrun) from getting better results than the mutation run;g04, where it moved from being a signifcantly BET-hence we can see that the final run is BETTER thanTER effect down to an insignificantly WORSE effect.the crossover run (F-C column). g09 has the same sit-At the same time, it had an insignificant efect on theuation; but this time the WORSE individual effect isrest of the problems. We can argue here that increas-for mutation run. For g07 and g10, the combined ef.ing the diversity had a good effect on the test problemfect of the proposed components is not as good as thewith the largest number of variables, but it had a badindividual effect of these components was.effect on the test problem with the lowest number ofFrom the above analysis, it can be said that nonevariables, while it has an insignificant effect on theof the proposed components (Ranking and Selection,test problems with numbers of variables between theCrossover, and Mutation) has a significant WORSEhighest and the lowest.individual effect on the test problems; indeed in mostIn the experiments carried out so far, the triangularcases they have significant BETTER effect.crossover has been applied to all individuals irrespec-tive of the use of the proposed simple ranking andselection, or the tournament selection. We know thatthe proposed selection would increase diversity whileon the other hand; the proposed crossover will decreasediversity. To make a better balance, we propose to ap-0oply triangular crossover only when the simple rankingg05and selection is in ffect. In other cases, when the fea-:07g09gI0sibility ratio is outside the prescribed range, we willapply two parent crossover with tournament selection.We call this process“synchronization" in this paper.-The experimental results, in terms of t-calculated,with synchronization for feasibility ratios of 0.4~0.7are presented in Fig.6, and for feasibility ratios ofOS-B■C-S OM-S■M-C OFC D F-M0.3~0.8中国煤化工this set of exper-iments,YHCNMHGted using two barsFig.5. Efect of the components when the Proposed Rankingfor eacland Selection are applied and the feasibility ratio is between●t-calculated when comparing Selection Run (syn-range [0.3~0.8].chronized with crossover) with Base Run which is theEhab Z. Elfeky et al: Ranking & Selection for Constrained Optimization29. g10_-2-:--7-口S-BDS-B口M-S-8■M-S」Fig.6. Components effect when both the Proposed Ranking andFig.7. Components effect when both the Proposed Ranking andSelection and the triangular crossover are applied when the fea-sibility ratio is in the range [0.3~0.8].sibility ratio is in the range [0.4~0.7].exploitation for the proposed algorithm.first column for every test problem, and●t-calculated when comparing Mutation Run with4.3 Efect of Population Size :Crossover Run which is the second column for everytest problem.Another set of experiments has been carried outAs of Figs. 6 and 7, when the synchronization hasin order to explore the effect of the population size.been done, the proposed components not only makeWe consider population sizes of 30, 90 and 150. Inconsistently positive contributions but also make a sig-this experiment, we have used four different parame-nificant contribution in most cases. We believe such a ter settings as that in the previous experiments (usingprocess provides a better balance of exploration andtwo feasibility ratios with or without synchronization).Table 3. Aaverage Results of the 4 Combination Runs for Different Population Sizes (30, 90, and 150)fcn/mkBestMedianMeanSt. Dev.Worstg02-0.80361930-0.803610-0.795 520-0.795 6538.19 x10-3-0.77 4105)0- 0.803 585-0.797 112-0.797 1036.77 x10-3-0.77909950-0.803 563-0.802 753- 0.799 5414.90 x10-3-0.787 396g04- -30 665.539- 30665.539- 30 665.536-30 665.5346.16 x10-3-30 665.513- 30665.492- 30665.382-30 665.3271.81 x10-1- 30 664.691150-30665.404-30665.102-30 665.0303.09 x10-1-30664.216g055 126.4985127.1655201.5685291.4832.33 x1025994.2705 126.7235 180.7435242.5581.76 x1025 864.1865127.1185 163.5945 210.7851.17 x1025 556.757g0724.30624.58626.10526.0076.73 x10-127.4419025.13026.16826.1375.50 x10- I27.23425.38026.44526.4285.06 x10-127.436g09680.630680.633680.660680.6632.26 x10-2680.717680.654680.737680.7496.00 x10~2680.904680.673680.790680.973g107049.331中国煤化工7074.4528 133.82683CYTHCNMHG11 602.0797079.4617 455.0757 673.6396.07 x10*9679.8727 068.3037 437.7687 540.0444.13 x1028 640.42230J. Comput. Sci. & Technol, Jan. 2008, Vol.23, No.1For each population size and each parameter set, we space. It is interesting to observe here that the rangesran each test problem (g02, g04, g05, g07, g09 and of feasibility ratios maintained by the algorithm at theg10) for 30 independent runs. We have presented the，later generations are similar for all three test problems.average results of the 4 combinations runs in Table 3. We believe this is a favorable point for our algorithmWe have also performed t-test to see whether therethat would help to avoid traps of local optima.is a significance diference between the results of differ-Table 4. Usage Percentage of the Proposed Rankingnt population sizes. From the results in Table 3 andand Selection for Diferent Runsthe t-tests, we can report that a smaller populationsize (30) is better for g04, g07, and g09, and a largerFcn.RuAsynchronizodSynchronizedpopulation size (150) is better for g10. On the other0.4~0.7 0.3~0.8hand, the efect of population' sizes is insignificant forSelection 5.62% 24.69%g02, and g05. Note that the results. presented in Ta-1.08% 11.01%ble 3 are different from Table 1 as they are based onMutation 8.50% 33.75%6.88% 26.15%diferent numbers of runs.Selection 45.84% 88.95%g04 Crossover38.04% 71.33%43.94% 72.42%Mutation 36.99% 70.88%43.38% 72.00%4.4 Relation Between the Feasibility RatioSelection 47.02% 67.11%and the Proposed Ranking and Selectiong07 Crossover 43.10% 57.25%39.62% 54.40%In order to have a deeper understanding of the newMutation 42.74% 56.83%39.11% 53.96%selection and ranking process, the percentage of use ofSelection 61.43% 90.94%the proposed simple ranking and selection (the numberg09 Crossover 54.47% 80.26%61.43% 81.58%of times the proposed selection was used divided by theMutation 54.12% 78.52%57.60% 79.99%total number of times any type of selection was used)Selection 43.21% 62.91%was calculated and is stated in Table 4. In general10 Crossover 32.56% 44.30%43.21% 29.77%terms, the effects of the components are dependent onMutation 31.79% 44.52%30.67% 43.25%the application of the proposed ranking and selectionscheme. As can be seen in Table 4, the low percentage0.8in g02 is caused by the high percentage of the feasi-0.7ble region in the search space of the problem, which isequal to 99.9973%. Interestingly, it is not more than1.00% in the other test problems, except g04 which is .0.327.0079%. The very high and very low percentages of0.2feasible space are making it harder to have feasibility0.1ratios inside the considered range. It is clear from Ta-0.0ble 4 that the changing of the feasibility ratio rangefrom [0.4~0.7} to [0.3~0.8] gives the algorithm more. Feasibility RatioMoving Averagechances to apply the proposed ranking and selectionscheme.Fig.8. Feasibility ratio and the moving average of each 100 gen-To give an overview of the variations of feasibil- erations for g07 in a single run.ity ratios over different generations in a single run,we have plotted them in Figs. 8, 9, and 10 for threearbitrarily chosen test problems in a single run. Forbetter understanding of the trend of the feasibility ra-0.6元山tios, the moving average of every 100 feasibility ratios0.4has also plotted. From the plots, it is clear that g07and g09 start with lower feasibility ratios and the ra-.2tios increase as the generation progresses. For g02, thesituation is different. The problem has a large feasibleregion a8 compared to its defined search space. As aI 中国煤化工场公美蔡白美result, it starts with a high feasibility ratio (0.6~1.0),loving Averageand as the evolution process advances, the algorithmMHCNMHGconcentrates on the edge of the feasible space which Fig9. Feasibilty ratio and the moving average of each 100 gen-helps to create infeasible individuals closer to feasible erations for g09 in a single run.Ehab Z. Elfeky et al: Ranking & Selection for Constrained OptimizationReferences1.1] Mezura-Montes E, Coello C A C. A simple multimemberedevolution strategy to solve constrained optimization prob-lems. IEEE Trans. Evolutionary Computation, 2005, 9(1):1- 17.业0.22] Barbosa H J C, Lemonge A C C. A new adaptive penaltyscheme for genetic algorithms. Inf. Sci, 2003, 156(3): 215-0.0 ，251[3] Deb K. An eficient constraint handling method for geneticalgorithms. Computer Methods in Applied Mechanics and-Feasbilily Ratio- Moving AverageEngineering, 2000, 186(2-4): 311- 338.[4] Koziel s, Michalewicz z. Evolutionary algorithms, homomor-phous mappings, and constrained parameter optimization.Fig.10. Feasibility ratio and the moving average of each 100Evolutionary Computation, 1999, 7(1): 19- 44.generations for g02 in a single run.[5] Farmani R, Wright J A. Self-adaptive fitness formulation forconstrained optimization. IEEE Transactions on Evolution-In this paper, we have empirically shown that our[6] Venkatraman S, Yen G G. A generic framework for con-ary Computation, 2003, 7(5): 445-455.approach is able to deal with a variety of constrainedstrained optimization using genetic algorithms. IEEEoptimization problems (i.e, with both linear and non-Transactions on Evolutionary Computation, 2005， 9(4):linear constraints and objective functions, and with424-435.equality and inequality constraints). The benchmark [7 Runarsson T P, YaO X. Stochastic ranking for constrainedadopted includes test functions with both small andevolutionary optimization. IEEE Transactions on Evolu-large feasible spaces. We have also argued that our[8] Michalewicz Z. Genetic algorithms, numerical optimization,proposed approach is very simple to implement andand constraints. In Proc. 6th International Conference oncan solve a variety of optimization problems.Genetic Algorithms, San Francisco, CA, 1995, pp.151 -158.Sarker R, Kamruzzaman J, Newton C. Evolutionary opti-mization (EvOpt): A brief review and analysis. Interna-tional Journal of Computational Intelligence and Applica-5 Conclusionstions, 2003, 3(4): 311-330.In this paper, new ranking, selection, and crossover[10] EibenA E, Raue P E, Ruttkay Z. Genetic algorithms withmulti-parent recombination. In Proc. 3rd Conference ormethods were introduced to solve constrained opti-Parallel Problem Soluring frorm Nature, Jerusalerm, 1994,mization problems. The idea behind these new meth-[11] Michalewicz Z. Genetic Algorithms + Data Structures =Pp.78-8ods is the exploitation of some of the features ofEvolution Programs. 3rd Rev. and Extended Ed, Berlin;constrained problems. The performance of the pro-New York: Springer- Verlag, 1996.posed algorithm has been compared with six exist- [12] Zhao X, Gao X S, Hu Z. Evolutionary programming based oning evolutionary algorithms using twelve benchmarknon-uniform mutation.MMRC, AMSS, Chinese Academy ofSciences, Beijing, China, December 2004, No.23, pp.352- 374.test problems. The results of the proposed algorithm13] Sarker R, Newton C. A comparative study of differentare clearly better than the five GA-based approachespenalty function-based GAs for constrained optimization. Inand are competitive with the best known ES- basedProc. the 4th Australia Japan Joint Workshop on Intelligentapproach. In two test problems, we have better re-and Evolutionary Systerns, Japan, 2000.sults than all the other EA-based solutions considered[14] Runarsson T P, Yao X. Search biases in constrained evolu-tionary optimization. IEEE Transactions on Systems, Manin the comparison. The superiority of our algorithm isand Cybernetics, Part C: Applications and Reviews, 2005,the combined efect of our proposed ranking, selection,35(2): 233 -243.crossover and mutation methods.[15] Elfeky E z, Sarker R A, Essam D L. A simple ranking andselection for constrained evolutionary optimization. In Proc.In this paper, a statistical signifcance test has been6th Intermational Conf. Simulated Evolution anLearmning,carried out in order to make a fairer comparison, whichHefei, China, 2006, pp.537- 544.showed that both of the proposed GAs and the best [16] Floudas C A, Pardalos P M. A cllectinn of test problems forEA-based approach are very competitive. Detailedconstrained global optimization algorithms. Lecture Notesanalysis on the efect of the individual componentsin Computer Science, vol. 455. Berlin: Springer-Verlag,1990.of the proposed algorithm has also been done. It is[17] Mich中国煤化工iczM.Anoteonuseclear from this analysis that all the components had afulnes一merical optimizationpositive impact on the algorithmic design.problYHCNMHGence on EvolutionaryProgramming, San Diego, CA, 1996, pp.305 -312.[18] Himmelblau D M. Applied Nonlinear Programming. NewYork: McGraw-Hill, 1972.32J. Comput. Sci. & Technol, Jan. 2008, Vol.23, No.119] Hock W, Schittkowski K. Text Exarmples for Nonlinear Pro-Appendix Test Function Suitegramming Codes. New York: Springer- Verlag, 1981.For more information the original sources are cited withEhab Z. Elfeky received hiseach test function.B.Sc. and Master's degrees by re-A. g01search in 2000 and 2004 respec-Minimizel16]tively from the Cairo University inEgypt. He is an associate lecturer atf(x)=5Sx;-5它不一学Cairo University since 2000. Cur-rently he is a Ph.D. candidate insubject toAustralian Defence Force Acadery.His research interests include evolu-g1(x)=2x1 + 2x2+x10 +$11- 10≤0,tionary computation, applied math-g2(x)=2x1 +2x3 +x10 +x12- 10≤0,ematical modelling and optimization techniques.g3(x)=2x2 +2x3 +:11 +T12- 10≤0,g4(x)=-8x1+x10≤0,Ruhul A. Sarker obtainedis Ph.D. degree in operations re-gs(x)=-8x2 +x11≤0,search (1991) from DalTech (for-ge(x)=-8x3 +x12≤0,mer TUNS), Dalhousie University,gr(x)=-2xs一昭+x10≤0,Halifax, Canada. He is currentlyge(x)=-2x6-卸十:11≤0,a senior lecturer in Operations Research at the School of Informa-g(x)=-2x8- x9+I12≤0,tion Technology and Elctrical En-where the bounds are 0≤xi≤1 (i= ....9),0 ≤gineering, University of New South工i≤100(i= 10,11,12), and0≤113≤1. The global .Wales (UNSW)， ADFA Campus,minimumisatx* =(1,1,1,1,1,1,1, 1,1,3,3,3, 1)Canberra, Australia. Before joining UNSW@ADFA inwhere six constraints are active (91, 92, 93,97, 98，and go)1998, he worked with Monash University and Bangladeshand f(x*)=-15.University of Engineering and Technology. He has pub-lished 150+ refereed technical papers in international jour-B. g02nals. He has edited six reference books and several confer-Maximizel4ence proceedings, and served conference as guest editorsand technical reviewers for a number of international jour-2os*(x2) -2I1 c3<(2)nals. He is the lead author of the book “Optimizationf(x)=:三1=1Modelling: A Practical Approach" published by Taylor andFrancis. His edited book“Evolutionary Optimization" wasEixpublished by Kluwer (now Springer). His research inter-ests include applied mathematical modelling, optimization subject to .and evolutionary computation. Dr. Sarker was a technicalco-chair of IEEE-CEC2003 and served many internationalg1(x)=0.75-1Ix;≤0,conferences in the capacity of chair, co- chair or PC mem-试ber. He is a member of INFORMS, IEEE and ASOR. Dr.Sarker is the editor of ASOR Bulletin, the national publi-g2(x)=2 x- 7.5n≤0,cation of the Australian Society for Operations Research.Daryl Essam received his B.Sc.wheren=20and0≤xe≤10(i=1....n.Theglobal maximum is unknown; the best we found is f(x*) =degree from the University of New 0.803619 (which, to the best of our knowledge, is betterEngland in 1990 and his Ph.D. de-than any reported value), constraint 91 is close to beinggree from the University of Newactive (91=-10-8).South Wales in 2000. He was anC. g03associate lecturer at the Universityof New England from 1991 and hasMaximizel71been with the Australian DefenseForce Academy campus of the Uni-中国煤化工versity of New South Wales sincesubje.MYHCNMHG1994, where he is now a senior lecturer. His research in-terests include genetic algorithms, with a focus on bothhr(x)=>x2-1=0genetic programming and multi-objective optimisation.i=1Ehab Z. Elfeky et al: Ranking & Selection for Constrained Optimization .33wheren= 10 and0≤x≤1 (i= 1....n.. The globalg2()=(x1-6)2+(x2-5)2- 82.81≤0,maximumisatx" =1/vn(i= 1....n where f(x*)= 1.where13≤x1≤100，and0≤x2≤100.Theopti-D. g04mum solution is x* = (14.095, 0.84296) where f(x*) =Minimizel8!- 6961.81388. Both constraints are active.f(x) = 5.3578547x3 + 0.8356891x1xsG. g07+ 37.293239x1 - 40792.141Minimizel19]subject tof(x)=xi+站+x1x2- 14x1- 16x2+(x3- 10)2g1(x) = 85.334407 + 0.0056858x2x5+4(x4-5)2 +(x5-3)2 +2(x6-1)2 + 5x?+ .006262x1x4 - .022053x3x5- 92≤0,+7(28-11)2 +2(xg- 10)2 +(x10-7)2+45g2(x)= - 85.334407 - 0.0056858x2x5- .006262x1xs + 0.0022053x3x5≤0,g3(x) = 80.51249 + 0.0071317x2x5g1(x)=- 105 +4x1 +5x2- 3xr +9x8≤0,+ 0.0029955x1x2 + 0.0021813x3- 110≤0,92(x)=- 10x1- 8x2-17x7 + 2xg≤0,gs(x)= - 80.51249 - 0.0071317x2x5g3(x)=-8x1 +2x2 +5xg +2x10-12≤0,- 0.029955x12 - 0.0021813x3 +90≤0,g(x) =3(x1-2)2 +4(x2-3)2 +2x号-7x4-120≤0,gs(x) = 9.300961 + 0.0047026x3x5gs(x)=5x? +8x2+ (x3-6)2- 2x4-40≤0,+ 0.0012547x1x3 + 0.0019085x3x4- 25≤0,g6(x)=xi+2(x2- 2)2 -2x1x2+ 14x5- 6xe≤0,g6(x)= - 9.300961 - 0.0047026x3x5g7(x) =0.5(x1-8)2 + 2(x2-4)2 +3xζ←∞6-30≤0,- 0.0012547x1x3 - 0.0019085xax4 + 20≤0,ge(x)=- 3x1 +6x2+ 12(x9-8)2- 7x10≤0,where 78≤x1≤102, 33≤x2≤45, and27≤xi≤45.where -10≤出≤10(i= 1...10). The optimum 80-(i = 3,4,5). The optimum solution is x* = (78, 33,lution is x"° = (2.171996, 2.363683, 8.773926, 5.095984,29.995256025682，45, 36.775812905788) where f(x*) =0.9906548，1.430574， 1.321644， 9.828726， 8.280092,30665.539. Two constraints are active (91 and g6).8.375927) where f(x") = 24.3062091. Six constraints areE. g05 .active (91,92, 93, 94,95, and 96).Minimizel19lH. g080.00002.Minimize|4lf(x)= 3x1 + 0000010101 + 2x2 +3x号sin*(2π:1)sin(2rx2)f(x)=对(x1 +x2)g1(x)=一x4+x3-0.55≤0,g2(x)= -x3+x4-0.55≤0,hs(x) = 100sin(-x3 - 0.25) + 100sin(-x4- 0.25)gn(x)=3-x2+1≤0,+ 894.8-出1= 0,g2(x)=1-x1 +(x2-4)°≤0,hs(x) = 1000 sin(x3一0.25) + 1000sin(x3 - x4- 0.25)where0≤T1≤10,and0≤T2≤10.Theoptimumn+ 894.8-x2= 0,solution is x* = (1.2279713, 4.2453733) where f(x") =hs(x) = 100sin(x4- 0.25) + 1000sin(x4-x3 - 0.25)0.095825. The solution lies within the feasible region.+ 1294.8= 0,I. g09 .Minimizel19|where0≤x1≤1200,0≤x2≤1200, -0.55≤x3≤0.55,ind -0.55 ≤x4≤0.55. The best known solution isf(x)=(x1- 10)2 +5(x2- 12)2 +对+3(x4-11)2x° = (679.9453, 1026.067, 0.1188764, -0.3962336) wheref(x*)= 5126.4981.+ 10xg+7x届+x- 4xezτ - 10x6- 8xτF. g06 .Minimizel16)中国煤化工+4n子+5x6≤0,f(x)=(21- 10)3 +(x2- 20)2;YHCNM H Gi+rs-s≤0,g3(x)=- 196 + 23x1 +x路+ 6x名- 8xr≤0,g1(x)=-(x1-5)2-(x2-5)2 + 100≤0,g4(x)=4x? +路-3x1x2 +2x号+5xo- 11xr≤0,34J Comput. Sci. & Technol, Jan. 2008, Vol.23, No.1where -10≤xi≤10 (i = 1,....7).The opti-K. g11mum solution is x° = (2.330499, 1.951372， 0.4775414,Minimize44.365726, 0.6244870, 1.038131, 1.594227) where f(x") =680.6300573. Two constraints are active (91 and ga).f(x)=x +(2-1)2J. g10subject toMinimizel1h(x)=x2-xi=0,f(x)=①1 +2+x;where-1≤x1≤1and-1≤x2≤1.Theoptimumsolutionisx* = (+1/√2,1/2) where f(x*) = 0.75.L. g12Maximizel4g1(x)=-1 + 0.0025(x4 +xo.≤0,g2(x)=-1 + 0.0025(x5 +卸←x≤0,f(x)=(100-(1-5)2-(2-5)2-(03 -512)100g3(x)=-1 +0.01(x8-xa)≤0,g4(x)= - x1x6 + 83.3252x243 + 100x1 - 833.333<0，subject togs(x)= -x2x7 + 1250xs + x2xs- 1250x4≤0,g(x)=(x1-p)2-(x2-q)2 - (x3-r)2 - 0.0625<≤0ge(x)= - x3x8 + 1250000 + x3xs - 2500xs≤0,where0≤0i≤10(i= 1,2,3) and p,q,r = 1,2...,.9.where100≤x1≤1000,1000≤x;≤1000(i=2,3)The feasible region of the search space consists of 93 dis-and 10≤xi≤1000 (i= ....81. The optimum solution jointed spheres. A point (x1,x2, x3) is feasible if and onlyis x" = (579.3167, 1359.943, 5110.071, 182.0174, 295.5985,if there exist (p,q,r) such that the above inequality holds.217.9799, 286.4162, 395.5979) where f(x*) = 7049.3307.The optimum is located at x" = (5,5,5) where f(x*)= 1.Three constraints are active (91, 92 and 93).The solution lies within the feasible region!2).CorrectionThe second author's Chinese name of the paper entitled“Autocorrelation Values of New Generalized Cyclo-tomic Sequences of Order Two and Length pq” , published on No.6, 2007, pp.830 -834, should be陈智雄，butnot陈志雄.中国煤化工MYHCNMHG