Mixed Integer-Discrete-Continuous Optimization by

5thInternationalMendelConferenceonSoftComputingMENDEL’99,Brno,CzechRepublic,9–12June1999MixedInteger-Discrete-ContinuousOptimizationbyDifferentialEvolutionJouniLampinenUniversityofVaasaDepartmentofInformationTechnologyandProductionEconomicsP.O.Box700,FIN-65101Vaasa,FinlandE-mail:[e-mail]iversityofBrnoFacultyofTechnology(Zlín),DepartmentofAutomaticControlnám.T.G.M.275,76272Zlín,CzechRepublicE-mail:[e-mail]–IvanZelinkaMixedInteger-Discrete-ContinuousOptimizationbyDifferentialEvolutionJouniLampinen19995thInternationalMendelConferenceonSoftComputingMENDEL’99,Brno,CzechRepublic,9–12June1999DifferentialEvolution:asimple,effective,efficientandrobustfloating-pointencodedevolutionstrategyforoptimizationofcontinuousvariables.Objectiveofthisstudy:ToextendDifferentialEvolutionalgorithmformixed-discrete-continuousnon-linearoptimizationsubjecttomultiplenon-linearconstraintsRequireshandlingtechniquesforall•continuousvariables•integervariables•discretevariables•boundaryconstraints•multiplenon-linearandnon-trivialconstraintfunctionsHere•therequiredtechniqueswillbedescribed•withpracticalexamples•andcomparisonswiththeothermethodsJouniLampinen–IvanZelinkaMixedInteger-Discrete-ContinuousOptimizationbyDifferentialEvolutionJouniLampinen19995thInternationalMendelConferenceonSoftComputingMENDEL’99,Brno,CzechRepublic,9–12June1999DifferentialEvolution(DE)individual1individual2individual3individual4individual5individual6costvalue2.132.862.372.173.462.66parameter10.010.520.050.650.610.01CURRENTparameter20.830.470.590.450.600.70POPULATIONparameter30.140.840.890.390.610.55parameter40.770.730.830.410.670.52parameter50.380.300.010.270.970.88weighteddifferencedifferencevectorvector-0.13-0.100.030.020.440.360.310.250.040.03noisyvector-0.090.720.910.770.91trialvectorcostvalue2.56parameter1-0.09parameter20.83parameter30.14controlvariablesofDEparameter40.77numberofdimensionsD5parameter50.91populationsizeNP6mutationconstantF0.80crossoverconstantCR0.50individual1individual2individual3individual4individual5individual6costvalue2.13parameter10.01POPULATIONparameter20.83FORNEXTparameter30.14GENERATIONparameter40.77parameter50.38+-++1.Choosetargetvector2.Randomchoiceoftwovectors3.Thirdrandomlychosenvector,subjectofmutationsCROSSOVER:WithprobabilityCRselectparametervaluefromnoisyvector,otherwiseselectvaluefromtargetvectorSELECTION:Selecttargetvectorortrialvector,thefittestonesurvivexFMUTATION:AdddifferencevectorweightedwithFtothirdrandomlychosenvectorEVALUATIONOFCOSTFUNCTION:Evaluationofcostfunctionvaluefortrialvectortakesit'splacehereJouniLampinen–IvanZelinkaMixedInteger-Discrete-ContinuousOptimizationbyDifferentialEvolutionJouniLampinen19995thInternationalMendelConferenceonSoftComputingMENDEL’99,Brno,CzechRepublic,9–12June1999Easyimplementation:AnexampleinFORTRAN1do1icount=1,GenMax2do2i=1,NP33A=IDINT(Rndgen()*NP+1)4if(A.EQ.i)goto354B=IDINT(Rndgen()*NP+1)6if((B.EQ.i).OR.(B.EQ.A))goto475C=IDINT(Rndgen()*NP+1)8if((C.EQ.i).OR.(C.EQ.A).OR.(C.EQ.B))goto59do6j=1,iD10trial(j)=P(i,j)+K*(P(C,j)-P(i,j))+F*(P(A,j)-P(B,j))116continue12callCostFunction(score,iD,trial)13if(score.LE.cost(i))then14do7j=1,iD15P(i,j)=trial(j)167continue17cost(i)=score18iBest=i29endif202continue211continueJouniLampinen–IvanZelinkaMixedInteger-Discrete-ContinuousOptimizationbyDifferentialEvolutionJouniLampinen19995thInternationalMendelConferenceonSoftComputingMENDEL’99,Brno,CzechRepublic,9–12June1999Handlingofboundaryconstraints:•byreplacingviolatedvaluewitharandomvaluewithinboundaryconstraints•guaranteesboundaryconstraintsatisfaction•guaranteesdiversityofpopulationJouniLampinen–IvanZelinkaMixedInteger-Discrete-ContinuousOptimizationbyDifferentialEvolutionJouniLampinen19995thInternationalMendelConferenceonSoftComputingMENDEL’99,Brno,CzechRepublic,9–12June1999Handlingofintegervariables:•bytruncatingthechromosomevaluesforcostfunctionevaluation•thepopulationofDEstillworkswithfloating-pointvalues•changestheeffectiveobjectivefunctionlandscapefromDE’spointofview•introducesflatareastothefitnesslandscape•DE’sself-adaptivereproductionschemeiswellabletomoveacrosstothoseflatareasJouniLampinen–IvanZelinkaMixedInteger-Discrete-ContinuousOptimizationbyDifferentialEvolutionJouniLampinen19995thInternationalMendelConferenceonSoftComputingMENDEL’99,Brno,CzechRepublic,9–12June1999Integerhandlingchangestheobjectivefunctionlandscape•ObjectivefunctionlandscapechangeinDE’spointofview•DEstillworkswithacontinuousspaceJouniLampinen–IvanZelinkaMixedInteger-Discrete-ContinuousOptimizationbyDifferentialEvolutionJouniLampinen19995thInternationalMendelConferenceonSoftComputingMENDEL’99,Brno,CzechRepublic,9–12June1999Handlingofdiscretevariables:AdiscretevalueisoptimizedindirectlysothatDEoptimizesanintegervalue(index)thatpointstotheactualdiscretevalue•first,thediscretesetofavailablevaluesisarrangedtoanascendingsequence•thenanindexisassignedtorefereachavailablevalue•DEworkswiththeseindexesbyoptimizingtheindexlikeanyintegervariable•forcostfunctionevaluation,th