Ideal Evaluation from Coevolution

IdealEvaluationfromCoevolutionAbstractInmanyproblemsofinterest,performancecanbeevaluatedusingtests,suchasex-amplesinconceptlearning,testpointsinfunctionapproximation,andopponentsingame-playing.Evaluationonalltestsisofteninfeasible.Identi?cationofanaccurateevaluationor?tnessfunctionisadif?cultprobleminitself,andapproximationsarelikelytointroducehumanbiasesintothesearchprocess.Coevolutionevolvesthesetoftestsusedforevaluation,buthassofaroftenledtoinaccurateevaluation.Weshowthatforanysetoflearners,aCompleteEvaluationSetcanbedeterminedthatprovidesidealevaluationasspeci?edbyEvolutionaryMulti-ObjectiveOptimization.Thisprovidesaprincipledapproachtoevaluationincoevolution,andtherebybringsautomaticidealevaluationwithinreach.TheCompleteEvaluationSetisofmanageablesize,andprogresstowardsitcanbeaccuratelymeasured.Basedonthisobservation,analgorithmnamedDELPHIisdeveloped.Thealgorithmistestedonproblemslikelytopermitprogressononlyasubsetoftheunderlyingobjectives.Whereallcompari-sonmethodsresultinoverspecialization,theproposedmethodandavariantachievesustainedprogressinallunderlyingobjectives.These?ndingsdemonstratethatidealevaluationmaybeapproximatedbypracticalalgorithms,andthataccurateevaluationfortest-basedproblemsispossibleevenwhentheunderlyingobjectivesofaproblemareunknown.KeywordsCoevolution,Pareto-Coevolution,accurateevaluation,EvolutionaryMulti-ObjectiveOptimization,underlyingobjectives,Pareto-hillclimber,over-specialization.1Introduction1.1EvaluationForsomeofthemostinterestingproblemsthatevolutionarycomputationmightad-dress,testswhoseoutcomesre?ectsomeofthequalitiesofindividualscanreadilybeperformed,whilethepreciseunderlyingobjectivesre?ectedbysuchtestsareun-known.Examplesincludeconceptlearning,functionapproximation,game-playing,aswellasopen-endeddomainssuchastheevolutionofcomplexbehavior.Humandesigned?tnessfunctionsforsuchtest-basedproblemswilltypicallybeinaccurate,andtherebylimitthepotentialofevolutionarycomputationtoaddresstheseproblems.Se-lectinga?xedrepresentativesetoftestsisofteninfeasibleduetothelargenumberofpossibletests.Animportantquestionthereforeis:howmayaccurateevaluationfortest-basedproblemsbeachieved?Coevolution(Barricelli,1962,1963;Axelrod,1987;Hillis,1990)evaluatesindividu-alsonanevolvingsetoftests,andmaytherebyinprincipleprovideaccurateevaluation.E.D.deJongandJ.B.PollackCoevolutionhasalreadyledtoseveralsuccessfulresults(Hillis,1990;Sims,1994;Juill′e&Pollack,1996;Pollack&Blair,1998).Sofarhowever,evaluationincoevolutionhasoftenbeenfarfromaccurate,asindicatedbyproblemssuchasover-specialization,RedQueendynamics,anddisengagement(Cliff&Miller,1995;Watson&Pollack,2021).Inthisarticle,weinvestigatehowcoevolutioncanbeusedtoachieveaccurateevaluation.Thissigni?cantaimisapproachedbyviewingtest-basedproblemsfromtheperspec-tiveofEvolutionaryMulti-ObjectiveOptimization(EMOO)(Deb,2021),andconsider-ingwhattestsarerequiredtodeterminewhodominateswhoinagivenpopulationoflearners.Toillustratethedif?cultyofaccurateevaluation,weconsidertheproblemofse-lectingamoveinachessgame.IftheoptimalMinimax(VonNeumann,1928)valuesforthisproblemwereavailable,itwouldbesuf?cienttocomparethevaluesofthefewtensofboardpositionsreachableviaoneofthecurrentlyavailablemoves.Thisisinsharpcontrastwiththeactualsituation,wherevalueestimatesoftheboardevaluationfunctionmustbere?nedbymeansofextensivelook-aheadsearch.1Thissubstantialamountofrequiredadditionalcomputationsuggeststhatboardevaluationfunctionsusedincurrentmachinechessmustbequitefarremovedfromtheoptimal(Minimax)values.Intest-basedproblems,thequalityofanindividualisdeterminedbyitsperfor-manceonanumberoftests.Typically,thesetofallpossibletestsforproblemsofthiskindisverylarge,makingitinfeasibletoevaluateindividualsonalltests.Astheaboveexampleillustrates,thede?nitionofanaccuratedomain-speci?c?tnessfunc-tionisequallyproblematic,asanaccuratespeci?cationofthequalityofallpossibleindividualsrequireshighlydetailedknowledgeofaproblem.Moreover,theuseofascalar?tnessfunctionpresumesthatindividualscanberankedonasingledimen-sionofperformance.Suchrankingscannotyieldcompleteinformationwhenqualityisgovernedbymultipleobjectives.1.2UnderlyingObjectivesAusefulnotionfortest-basedproblemsisthatoftheunderlyingobjectivesofaproblem.ThetermobjectiveasusedinEvolutionaryMulti-ObjectiveOptimizationreferstoanindicatorofqualityreturninganelementfromanorderedsetofscalarvalues,suchasarealnumber.Foranytest-basedproblem,asetofunderlyingobjectivesexistssuchthatknowledgeoftheobjectivevaluesofanindividualissuf?cienttodeterminetheout-comesofallpossibletests.Theexistenceofasetofunderlyingobjectivesisguaranteed,asthesetofallpossibletestsitselfsatis?esthisproperty.Thenotionofunderlyingobjectivesbecomesmoremeaningfulhoweverwhenalimitedsetofobjectiveswiththispropertycanbeidenti?ed;ifasmallsetofunderlyingobjectivesexists,itrepresentsimportantinformationaboutthestructureofaproblem.Thesmallestpossiblesizeforthesetofunderlyingobjectivescanbeviewedasthein-herentdimensionalityofaproblem,andthenatureofsuchaminimalsetofunderlyingobjectivesmayprovidei