Fitness inheritance in multi-objective optimization

Jian-HungChenDavidE.GoldbergShinn-YingHoKumaraSastry

IlliGALReportNo.2002017

June,2002

IllinoisGeneticAlgorithmsLaboratory(IlliGAL)

DepartmentofGeneralEngineeringUniversityofIllinoisatUrbana-Champaign

117TransportationBuilding

104S.MathewsAvenue,Urbana,IL61801http://www-illigal.ge.uiuc.edu

FitnessInheritanceinMulti-ObjectiveOptimization

Jian-HungChen,DavidE.Goldberg,andKumaraSastry

IllinoisGeneticAlgorithmsLaboratory(IlliGAL)

DepartmentofGeneralEngineeringUniversityofIllinoisatUrbana-Champaign104S.MathewsAve,Urbana,IL61801

jh.chen@ieee.org,deg@uiuc.edu,ksastry@uiuc.edu

Shinn-YingHo

DepartmentofInformationEngineering

FengChiaUniversity,Taichung407,Taiwansyho@fcu.edu.tw

Abstract

Inreal-worldmulti-objectiveproblems,theevaluationofobjectivefunctionsusuallyrequiresalargeamountofcomputationtime.Moreover,duetothecurseofdimensionality,solvingmulti-objectiveproblemsoftenrequiresmuchlongercomputationtimethansolvingsingle-objectiveproblems.Therefore,itisessentialtodevelopefficiencyenhancementtechniquesforsolvingmulti-objectiveproblems.Thispaperinvestigatesfitnessinheritanceasawaytospeedupmulti-objectivegeneticandevolutionaryalgorithms.Convergenceandpopulation-sizingmodelsarederivedandcomparedwithexperimentalresultsintwocases:fitnessinheritancewithoutfitnesssharingandfitnessinheritancewithfitnesssharing.Resultsshowthatthenumberoffunctionevaluationscanbereducedwiththeuseoffitnessinheritance.

1Introduction

Formanylarge-scaleandreal-worldproblems,thefitnessevaluationingeneticandevolutionaryalgorithmsmaybeacomplexsimulation,modelorcomputation.Therefore,eventhissubquadraticnumberoffunctionevaluationsisratherhigh.Thisisespeciallythecaseinsolvingmulti-objectiveproblems.Itisnotonlybecausethenumberoftheobjectivestobeevaluatedisincreased,butalsothecurseofdimensionalitymayincreasetheconvergencetimeofgeneticalgorithms(GAs).Asaresult,itisbeneficialtoutilizeefficiencyenhancementtechniques(EETs)inmulti-objectiveGAs.

InpracticeEETshaveimprovedtheperformanceofGAs.Manyreal-worldapplicationsofGAsusuallyuseEETstoimprovethespeed,rangedfromparallelcomputing,dis-tributedcomputing,domain-specificknowledge,orcheaperfitnessfunctions.Recently,Sastry(2002)pro-posedanan-alyticalmodelforanalyzingandpredictingbehaviorofsingle-objectiveGAswithEETs.However,duetothepopularityofmulti-objectiveGAs,thereisaneedtoinvestigatemulti-objectiveGAswithEETs.Inthispaper,oneEETcalledfitnessinheritanceismodeledandoptimizedforgreatestspeedup.Infitnessinheritance,anoffspringsometimesinheritsafitnessvaluefromitsparentsratherthanthroughfunctionevaluations.

Theobjectiveofthispaperistomodelfitnessinheritanceandtoemploythismodelinpredictingtheconvergencetimeandpopulationsizerequiredforthesuccessfuldesignofamulti-objectiveGA.

1

Figure1:Fitnessinheritanceinmulti-objectiveGAs

Thispaperisorganizedinthefollowingmanner.Section2brieflyreviewsthepastworksonEETsandfitnesssharing.Section3describesthebicriteriaOneMaxproblemandfitnessinheritance,andderivesconvergence-timeandpopulation-sizingmodelsformulti-objectiveGAswithEETs,aswellastheoptimalproportionofinheritance,thespeed-up.TheexperimentalresultsonfitnessinheritancewithandwithoutfitnesssharingarepresentedinSection4.ThepaperisconcludedinSection5.

2Background

Asbackgroundinformation,abriefreviewofthefitnessinheritanceliteratureisfirstpresented.Then,abriefsummaryonhowtoincorporatefitnessinheritanceinmulti-objectiveGAsisprovided.Sincefitnessinheritancewithandwithoutfitnesssharingwillbediscussedinthispaper,section2.2presentsabriefsummaryonfitnesssharing.

2.1LiteratureReview

Smith,DikeandStegmann(1995)proposedtwowaysofinheritingfitness,onebytakingtheaveragefitnessofthetwoparentsandtheotherbytakingaweightedaverageofthefitnessofthetwoparents.TheirresultsindicatedthatGAswithfitnessinheritanceoutperformedthosewithoutinheritanceinboththeOneMaxandanaircraftroutingproblem.However,theoreticalanalysisinthispaperwaslimitedtoconsideringaflywheeleffectthatarisesintheschematheorem.Zheng,Julstrom,andCheng(1997)usedfitnessinheritanceforthedesignofvectorquantizationcodebooks.ArecentstudybySastry(2001)developedatheoreticalframeworkforanalyzingfitnessinheritance,anddiscussedhowtodeterminetheoptimalpro-portionoffitnessinheritanceandspeed-upofusingfitnessinheritanceinsingle-objectiveGAs.However,untilnow,thereisnostudyonusingfitnessinheritanceformulti-objectiveGAs.

2

2.2FitnessInheritance

Infitnessinheritance,thefitnessofalltheindividualsintheinitialpopulationareevaluated.Thereafter,thefitnessofsomeproportionofindividualsinthesubsequentpopulationisinherited.Thisproportioniscalledtheinheritanceproportion,pi.Theremainingindividualsreceiveevaluatedfitness.Ifnoneoftheindividualsreceiveinheritedfitness(pi=0),alltheindividualsareevaluatedasusual,thennospeed-upwillbeobtained.Ontheotherhand,ifalltheindividualsreceiveinheritedfitness(pi=1),itmeansthatnoneoftheindividualsareevaluated.Thereafter,thefitnessdiversityinthepopulationwillvanishrapidlyandthepopulationwillprematureconverged,sothatGAswillfailtosearchtheglobaloptimum.Asaresult,itisimportanttochooseanoptimalinheritanceproportion,sothatmaximumspeed-upwillbeyielded.Theflowchartofmulti-objectiveGAswithfitnessinheritanceisshowninfigure1.

Thereareseveraldifferentwaystoinheritfitness(objectivefitnessvalues),suchasweighted-sum.Foramulti-objectiveproblemwithzobjective,fitnessinheritanceinmulti-objectiveGAscanbedefinedas

w1fz,p1+w2fz,p2

fz=,(1)

w1+w2

wherefzisthefitnessvalueinobjectivez,w1,w2aretheweightsforthetwoparentsp1,p2,andf(z,p1),f(z,p2)isthefitnessvaluesofp1,p2inobjectivez,respectively.Inpractice,fitnessinheritancecanbeperformedonalltheobjectivesorjustseveralobjectives.Inthispaper,weassumethatalltheobjectivereceivesinheritedfitnessfromtheparents,andtheinheritedfitness(objectivevalues)istakentobetheaverageofthetwoparents.Therefore,w1andw2aresetto1.

2.3FitnessSharingRevisited

Mostmulti-objectiveproblemshavemultiplePareto-optimalsolutions.Thisusuallycausesdifficul-tiestoanyoptimizationalgorithminfindingtheglobaloptimumsolutions.InpriorGAliterature,therehavebeenmanynichingmethodsonhowtopromoteandmaintainpopulationdiversity.Fit-nesssharing,proposedbyGoldbergandRichardson(1987),maybethemostwidelyusednichingmethodinsolvingmulti-modalandmulti-objectiveproblems.Thebasicideaoffitnesssharingistodegradethefitnessofsimilarsolutionsthatcausespopulationdiversitypressure.Thesharedfitnessofanindividualiisgivenby

Fi

Fsh,i=,(2)

mi

whereFiisthefitnessoftheindividual,andmiisthenichecount,whichdefinestheamountofoverlap(sharing)oftheindividualiwiththerestofthepopulation.Thenichecountiscalculatedbysummingasharingfunctionoverallindividualsofthepopulation:

mi=

n󰀄j=1

sh(di,j).(3)

Thedistancedi,jrepresentsthedistancebetweenindividualiandindividualjinthepopulation,

determinedbyasimilaritymetric.Thesimilaritymetriccanbebasedoneitherphenotypeorgenotypesimilarity.Ifthesharingfunctiondeterminesthatthedistanceiswithinafixedradiusσsh,itreturnsavalue,asequation(4).

󰀃dαifd)1−(σi,ji,j<σsh,sh(4)sh(di,j)=

0otherwise.Theparameterαisusuallysetto1.σshisoftenconservativelyestimated.

3

3FitnessInheritanceinMulti-ObjectiveOptimization

InthissectionthebicriteriaOneMaxproblemisextendedfromOneMaxproblemforanalyzingmulti-objectiveGAswithfitnessinheritance.Inthissection,abriefsummaryoffitnessinheritanceisalsopresented.

3.1BicriteriaOneMaxProblem

TheOneMaxorbit-countingproblemiswell-knownandwell-studiedinthecontextofGAs.TheOneMaxproblemisabit-countingproblemwherefitnessvalueofeachbinarystringisequaltothenumberofonebitsinit.Accordingly,theoptimumbinarystringisanall1sstring.ThesimplicityoftheOneMaxproblemmakesitaprimecandidatetostudytheeffectoffitnessinheritanceontheperformanceofGAs.Inordertoinvestigatetheperformanceofmulti-objectiveGAswithfitnessinheritance,wedevelopthebicriteriaOneMaxproblemforanalyzingmulti-objectiveGAswithfitnessinheritance.ThebicriteriaOneMaxproblemisdefinedby

󰀃

f(s,x1)=l−d(s,x1)

Maximize,(5)

f(s,x2)=l−d(s,x2)wherestringsisthestringtobeevaluated,x1,andx2aretwofixedstring,thestringlengthisl,andds,xisthehammingdistanceoftwostring.Ifthefixedstringxisall1sstring,thenthecorrespondingobjectivefunctionwillbetheOneMaxproblem.ThenumberofPareto-optimalsolutions,m,inthebicriteriaOneMaxproblemcanbecalculatedby

m=2d(x1,x2).

(6)

Inthispaper,unlessotherwisementioned,x1isall1sstring,andx2isall1sstringexceptthefirstfourbitsofx2is0s.

3.2TimetoConvergence

Inthissectionwederiveconvergence-timemodelforthebicriteriaOneMaxproblemwithfitnessinheritance.ForOneMaxdomain,theconvergencemodelcanbederivedbyusingtheresponsetoselectionequation(M¨uhlenbein&Schlierkamp-Voosen,1993),

󰀄f=ft+1−ft=Iσf.

(7)

Now,wecanproceedtoderivetheconvergencemodelforthebicriteriaOneMaxproblembyex-tendingequation(8).Basedontheconceptoffitnesssharing,assumedthatthepopulationweredividedintoseveralsubpopulations(niches),andeachnicheoptimizesitsownseparateOne-Maxproblem.Therefore,theoptimizingprocessforthebicritieraOneMaxproblemcanberegardedasoptimizingseveralOneMaxproblemssimultaneously.Sincenichesarefromthesamepopulation,eachnichewillreceiveexternalnoisefromotherniches.Asaresult,wecanusetheOneMaxmodelwithnoisyfitnessfunctions(Miller,1997)topredictconvergencetimeinthepresenceofexternal

4

Thisequationwasderivedbycalculatingthedifferenceinmeanfitnessoftwopopulationsusingthe

2attimet.Sastry(2001)extendedthisselectionintensityI,thepopulation’sfitnessvarianceσf

modelforfitnessinheritanceinsingle-objectiveGAs.ThisconvergencemodelderivedbySastryisreproducedbelow:󰀅

󰀄f=ft+1−ft=I1−piσf.(8)

2isthenoisevariancefromotherniches.whereσN

LetMbethenumberofnichesinthepopulation,and

󰀆2+σ2σfN

.ρe=2σf

noisecausedbyniches.Foreachniche,theconvergencemodelforthebicriteriaOneMaxproblem

canbeexpressedas

2󰀅σf

󰀄f=ft+1−ft=I1−pi󰀆,(9)

22σf+σN

AssumedthateachnichehassameproportionofcorrectBBs,letptbetheproportionofcorrect

BBsinthenicheatgenerationt.FortheOneMaxdomain,themeanfitnessatgenerationtequalslpt,thefitnessvariancecanbeapproximatedbylpt(1−pt),andthenoisevariancefromothernichescanbeapproximatedby(M−1)pt(1−pt).Thepopulationisconvergedtooptimalwhenpt=1.Equation(9)nowyields󰀇

I1−pi󰀅

pt+1−pt=pt(1−pt).(10)

ρelApproximatingtheaboveequationwithadifferentialequationandintegratingthisequationusing

theinitialconditionp|t=0=0.5,weget

󰀇󰀁󰀂π1−pIti

pt=sin2.(11)+

42ρel

Thenwecanderiveanequationforconvergencetime,tconv,byequatingpt=1,andinverting

equation(11),󰀈

πl

tconv=ρe.(12)

2I1−piFinally,wecanyield

tconv

π=2I

󰀈l1−pi

󰀇M−1

.l

1+(13)

Ifpiistakenas0,andMistakenas1,thentheaboverelationreducesto

tconv=

π,2I

(14)

whichagreeswithexistingconvergence-timemodelsfortheOneMaxproblem.Generally,McanbesettothenumberofnichesinthepopulationorthenumberofPareto-optimalsolutionsinequation(13).However,itisdifficulttodetermineM,becausenichesareoftenoverlappedinthereal-worldproblems,andthenumberofnichesinthepopulationisalwaysvariedintherealrunsofGAswithfitnesssharing.Theconvergence-timemodelwillbeexaminedandcomparedwithexperimentsinthelatersection.

3.3PopulationSizing

Selectingaconservativepopulationsizereducesthechanceofprematureconvergence,anditalsoinfluencesthequalityofthesolutionobtained.Therefore,itisimportanttoappropriatelysizethe

5

Figure2:Totalnumberoffunctionevaluationspredictedbyequation(17)withafailurerateof0.0001.

populationtoincorporatetheeffectsoffitnessinheritance.FortheOneMaxproblem,theGambler’sRuinpopulation-sizingmodel(Hariketal.,1997)canbeusedtodeterminethepopulation-sizingmodel.Sastry(2001)extendthismodelforfitnessinheritance.Thispopulation-sizingmodelderivedbySastryis√

2k−1ln(ψ)π󰀆2

n=−σf,(15)

1−p3i

2iswherenisthepopulationsize,kisthebuildingblock(BB)length,ψisthefailurerate,andσf

2=25.thevarianceofthenoisyfitnessfunction.ForanOneMaxwithstringlength100,k=1,σf

AssumingthepopulationweredividedintoMniches,andeachnicheoptimizesforitsownsep-arateOneMaxproblem.Similartothepopulation-sizingmodelforthebicriteriaOneMaxproblem,wecanextendthismodelbyusingtheOneMaxmodelwithnoisyfitnessfunctions(Miller,1997)topredictpopulation-sizinginthepresenceofexternalnoisecausedbyniches.ThepopulationmodelforthebicriteriaOneMaxproblemcanbewrittenas

√

2k−1ln(ψ)Mπ󰀆22,σf+σNn=−(16)31−pi2isthenoisevariancefromotherniches,andMisthenumberofniches.whereσN

Thepopulation-sizingmodelwillbeexaminedandcomparedwithexperimentsinthelatersection.

3.4OptimalInheritanceProportionandSpeed-up

Givenaproblemthereshouldbearangeofinheritanceproportionsthataremoreefficientthantheothers.Aninappropriateinheritanceproportionswouldnotreducethenumberoffunctionevalu-ations.Forlargesizedproblems,Sastry’sstudyindicatesthattheoptimalinheritanceproportion,pi,liesbetween0.54-0.558.Thetotalnumberoffunctionevaluationsrequiredcanbecalculatedby

Nfe=n[tconv(1−pi)+pi].(17)Fromtheequation(10)andequation(13),wecanthepredictedthetotalnumberoffunction

evaluationsrequired,asshowninfigure2.

6

Thespeed-upoffitnessinheritanceisdefinedastheratioofnumberoffunctionevaluationswithp1=0tothenumberoffunctionevaluationatoptimalpi.Fromthepracticalview,auserusuallyfixesthepopulationsizeandthenoptimizestheproportionoffitnessinheritance.Therefore,theoptimalproportionoffitnessinheritancewithafixednumberofpopulationsizecanbeobtainedbytheinverseofequation(16).󰀇

κ3

p∗=1−,(18)i

n

󰀆

k−12+σ2).Equation(18)indicatesthatifthepopulationislargerwhereκ=−2ln(ψ)Mπ(σfN

thanκ,thelargerthepopulationsize,thehigherofinheritanceproportioncanbeused.

Figure3:Convergencetimefora100-bitbicriteriaOneMaxproblemfordifferentproportionofinheritancepredictedbyequation(13)comparedtoexperimentalresults.

Figure4:Verificationofthepopulation-sizingmodelforvariousinheritanceproportionswithempir-icalresults.ThecurvesareanalyticalresultsofOnemaxproblemandbicriteriaOneMaxproblem,respectively.Experimentalresultsdepictthepopulationsizerequiredforoptimalconvergencewithfailurerateof0.0001.

7

4ExperimentsAndResults

TheexperimentswereperformedusingselectorecombinativeGAswithbinarytournamentselection,anduniformcrossoverwithcrossoverprobabilityof1.0.Nomutationoperatorisused.Thesharingfactorσshissetto50.ThefitnessassignmentstrategyweusedisproposedbyHo(1999),isdefinedby

F(X)=p−q+c,(19)wherepisthenumberofindividualswhichcanbedominatedbytheindividualX,andqisthe

numberofindividualswhichcandominatetheindividualXintheobjectivespace.Toensureapositivefitnessvalue,aconstantcisadded.Generally,theconstantccanbeassignedusingthenumberofallparticipantindividuals.Allexperimentswereperformed30runsusingthe100-bitbicriteriaOneMaxproblem.

AstoMinequation(13)andequation(16),consideringthebicriteriaOneMaxproblemandassumingperfectniching,Mcanbesetto2.BecausebettermixingofBBsisabletogenerateotherPareto-optimalsolutionsfromx1andx2.Itshouldbeanapproximatedlower-boundforthecomparisonwithexperimentalresults.However,itisnotedthat,intherealrunsofGAswithfitnesssharing,Misvariedinthepopulation.Therefore,equation(13)andequation(17)isalsovaried.

Inordertoinvestigatemulti-objectiveGAswithfitnessinheritance,twokindofexperiments,ftinessinheritancewithoutfitnesssharingandfitnessinheritancewithfitnesssharing,wereper-formedandcomparedwithanalyticalresults.However,sincemulti-objectiveGAswithoutfitnesssharingmayleadtoonlysomeniches.Therefore,forfitnessinheritancewithoutfitnesssharing,thealgorithmusedanexternalnon-dominatedsettostorethenon-dominatedsolutionsduringitssearchprocess.

Figure5:Totalnumberoffunctionevaluationspredictedbyequation(17)comparedtoexperimen-talresults.Thecurvesaretheanalyticalresultsof100-bitOnemaxproblemand100-bitbicriteriaOneMaxproblem,respectively.

4.1FitnessInheritanceWithoutFitnessSharing

Theconvergencetimeobservedexperimentallyiscomparedtotheabovepredictionfora100-bitbicriteriaOneMaxprobleminfigure3.Althoughfitnesssharingwasnotused,theresultsindicate

8

fitnessinheritanceisabletofindallthePareto-optimalsolutionsduringthesearchprocess.Thediscrepancybetweentheempiricalandanalyticalresultsmayduetosomenichesdisappearoutofthepopulation.Therefore,multi-objectiveGAswillfocusthesearchontheremainingniches.Whenthereisonlyonenicheleft,itleadtothatallthepopulationisoptimizinganOneMaxproblem.

Thepopulation-sizingmodeliscomparedtotheresultsof100-bitOneMaxproblemandtheresultsobtainedfora100-bitbicriteriaOneMaxproblemandinfigure4.Fromtheplotitcanbeeasilyseenthatwhentheproportionoffitnessinheritanceissmallerthan0.4,ourpopulation-sizingmodelfitstheexperimentalresultaccurately.However,whentheproportionoffitnessinheritanceisbiggerthan0.4,theexperimentsresultsgetclosertotheanalyticalresultsoftheOneMaxproblem.Itisbecausewhentheproportionofinheritanceishigher,thediversityofpopulationbecomeslesser.Sothatthesearchwasfocusedontheremainingnicheswhensomenichesdisappearedduringthesearchprocess.Asaresult,theconvergencetimeoffitnessinheritancewithoutfitnesssharingisvariedandmaybelowerthentheanalyticalresultspredictedbyequation13.

Byusinganappropriatepopulationsizeandproportionoffitnessinheritanceandfromtheequation(13)andequation(16),wecanthepredictedthetotalnumberoffunctionevaluationsrequiredandcomparedwithexperimentalresults,asshowninfigure5.Theaboveresultsindicatestheoptimalinheritanceproportionliesbetween0.6-0.8forfitnessinheritancewithoutfitnesssharing.Thespeed-upisaround1.4.Inotherwords,thenumberoffunctionevaluationswithinheritanceisaround40%lessthanthatwithoutinheritance.Thisimpliesthatwecangetamoderateadvantagebyusingfitnessinheritance.ThediscrepancybetweenourresultsandSastry’sstudyoccursduetothedisappearanceofniches.

Consideringthefixedpopulationsize,thespeed-upisdifferenttothespeed-upobtainedabove.Fromfigure6,itcanbeseenthatifthepopulationsizeis2000,thenfitnessinheritancecanyieldaspeed-upof3.4.TheresultagreeswiththatobtainedbySastry(2001).

Figure6:Totalnumberoffunctionevaluationsforvariousproportionoffitnessinheritanceatdifferentpopulationsizes.

4.2FitnessInheritanceWithFitnessSharing

Insection4.2,theexperimentswereperformedusingfitnessinheritancewithfitnesssharing.Theexternalnon-dominatedsetwasnotused.

9

Figure7:Convergencetimefordifferentproportionofinheritancepredictedbyequation(13)comparedtoexperimentalresultsusingfitnessinheritancewithfitnesssharing.

Recallingthedefinitionoffitnesssharinginsection2.3,weknowthatfitnesssharingwillde-gradethefitnessofsimilarindividuals,sothattheseindividualswillhavesmalleropportunitytobeselectedintothenextgeneration.However,consideringfitnessinheritancewithfitnessshar-ing,anindividualinheritsfitness(objectivevalue)fromitsparents.Sotheobjectivevaluesareapproximated.Thenthedummyfitnessisassignedaccordingtotheapproximatedobjectiveval-ues.Therefore,thedummyfitnessisalsoapproximated.Apparently,ifsomeindividualsareover-estimatedandreceivebetterfitnessthantheiractualfitness,fitnesssharingwillalsomaintaintheseindividuals.Asaresult,whenfitnessinheritanceisusedwithfitnesssharing,weexpectthatover-estimatedindividualsarelikelytosurviveinthepopulationandaffectothersolutionsastheproportionofinheritanceincreased.

Figure7andfigure8presenttheconvergencemodelandpopulation-sizingmodelobservedfor100-bitbicriteriaOneMaxproblemusingfitnessinheritancewithfitnesssharing.Whentheinheritanceproportionissmallerthan0.7,theexperimentalresultsfitthepredictedconvergencemodelandpopulation-sizingmodel.However,whentheinheritanceproportionisbiggerthan0.8,GAswithfitnessinheritanceandfitnesssharingcannotconvergetoallthePareto-optimalsolutions.

Figure9presentsthedistancetoParetofrontofbothactualandinheritedfitnessfortheexperimentalresultswithinheritanceproportion0.9.Itindicatesthatthesearchprocesswasdividedintotwophases.Inthisfirstphase,fitnessinheritanceproceededwell.Thesecondphasestartedaroundthe40thgeneration.Someindividualswereapproximatedtobetterfitnessandmaintainedbyfitnesssharing.Duetothehighinheritanceproportion,theseinferiorindividualsmixedwithotherindividuals.Finallythepopulationwasfilledwithincorrectindividuals.Thisphenomenonexplainsthediscrepancybetweenempiricalandanalyticalresultsinfigure7.

Thepredictednumberoffunctionevaluationsiscomparedwithexperimentalresultsinfigure10.Thespeed-upisaround1.25.Thediscrepancybetweenourresultsandanalyticalresultsmayduetothenumberofniches,M,isvariedintherealrunsofGAswithfitnesssharing.someinferiorindividualsaremaintainedbyfitnesssharing,andthenmixedwithotherniches.Therefore,morefunctionevaluationtimesarerequired.ThismaybetheoverheadinusingGAswithfitnesssharing.

Insummary,theexperimentalresultsoffitnessinheritancewithfitnesssharingindicatethattheproportionofinheritanceliesbetween0.4-0.5,sothatincorrectnicheswillhavelesserchancetobemaintainedbyfitnesssharing.Theresultisslightlydifferenttotheoptimalproportionof

10

inheritancederivedbySastry.

Figure8:Verificationofthepopulation-sizingmodelforfitnessinheritancewithfitnesssharingcomparedwithempiricalresults.Experimentalresultsdepictthepopulationsizerequiredforoptimalconvergencewithfailurerateof0.0001.

Figure9:ThedistancetotheParetofrontofactualfitnessandinheritedfitnessfortheexperimentalresultswithinheritanceproportion0.9.Theempiricalresultsareaveragedover30runs.

5Conclusions

Inthispaper,wehavedevelopedabicriteriaOneMaxproblemandderivedmodelsforconvergence-timeandpopulation-sizing.Themodelshavebeenanalyzedintwocases:fitnessinheritancewithoutfitnesssharingandfitnessinheritancewithfitnesssharing.Inthefirstcase,fitnessinher-itanceyieldssavingon40%intermsofthenumberoffunctionevaluations.Whileusingafixednumberofpopulationsize,fitnessinheritancecanyieldaspeedupof3.4.Inthesecondcase,fitnessinheritanceyieldssavingto25%.

11

Figure10:Thedistributionoffunctionevaluations.Thecurveisthetotalnumberoffunctionevaluationspredictedbyequation(17)foroptimalconvergenceofa100-bitbicriteriaOneMaxproblemwithafailurerateof0.0001.

Thoughthespeed-upoffitnessinheritanceseemstobemodest,itcanbeincorporatedwithparallelism,timecontinuation,andotherefficiencyenhancementtechniques.Insuchcase,aspeedupof1.25canbeimportant.

Furtherstudiesonusingcomplexinheritancetechniquesandincorporatingfitnessinheritancewithstate-of-the-artmulti-objectivegeneticalgorithmsarestillremainstobedone.

Acknowledgments

TheauthorswouldliketothanktoTian-LiYuandYing-PingChenformanyusefulcomments.

ThefirstauthorwishestothankthethirdauthorforhisencouragementtovisittheIllinoisGeneticAlgorithmsLaboratory(IlliGAL).

Thispaperwasdoneduringthevisit.ThefirstauthorissupportedbyTaiwanGovernmentFundsofMinistryofEducation.ThisworkwaspartiallysponsoredbytheAirForceOfficeofSci-entificResearch,AirForceMaterielCommand,USAF,undergrantsF49620-97-0050ANDF49620-00-0163.ResearchfundingforthisworkwasalsoprovidedbyagrantfromtheNationalScienceFoundationundergrantDMI-9908252.TheUSGovernmentisauthorizedtoreproduceanddis-tributereprintsforGovernmentpurposesnotwithstandinganycopyrightnotationthereon.

Theviewsandconclusionscontainedhereinarethoseoftheauthorsandshouldnotbeinter-pretedasnecessarilyrepresentingtheofficialpoliciesorendorsements,eitherexpressedorimplied,oftheAirForceOfficeofScientificResearch,thatNationalScienceFoundation,ortheU.S.Gov-ernment.

References

Goldberg,D.E.,&Richardson,J.(1987).Geneticalgorithmswithsharingformultimodalfunc-tionoptimization.InProceedingsoftheSecondInternationalConferenceonGeneticAlgo-rithms(pp.41–49).

12

Miller,B.L.(1997).Noise,sampling,andefficientgeneticalgorithms.doctoraldissertation,

UniversityofIllinoisatUrbana-Champaign,Urbana.AlsoIlliGALReportNo.97001.M¨uhlenbein,H.,&Schlierkamp-Voosen,D.(1993).Predictivemodelsforthebreedergenetic

algorithm:I.Continuousparameteroptimization.EvolutionaryComputation,1(1),25–49.Sastry,K.(2002).Evaluation-relaxationschemesforgeneticandevolutionaryalgorithms.Mas-ter’sthesis,UniversityofIllinoisatUrbana-Champaign,Urbana.Sastry,K.,Goldberg,D.E.,&Pelikan,M.(2001,7-11).Don’tevaluate,inherit.InSpector,

L.,Goodman,E.D.,Wu,A.,Langdon,W.B.,Voigt,H.-M.,Gen,M.,Sen,S.,Dorigo,M.,Pezeshk,S.,Garzon,M.H.,&Burke,E.(Eds.),ProceedingsoftheGeneticandEvolution-aryComputationConference(GECCO-2001)(pp.551–558).SanFrancisco,California,USA:MorganKaufmann.Smith,R.E.,&Dike,B.A.(1995).Fitnessinheritanceingeneticalgorithms.InProceedingsof

theACMSymposiumonAppliedComputing(pp.345–350).NewYork,NY:ACM.Zheng,X.,Julstrom,B.A.,&Cheng,W.(1997).Designofvectorquantizationcodebooksusing

ageneticalgorithm.InProceedingsof1997IEEEInternationalConferenceonEvolutionaryComputation(pp.525–530).Piscataway,NJ:IEEE.

13