Nästan alla analyser av tid komplexiteten hos evolutionära algoritmer (EAs) har genomförts endast för (1+1) EAs. Teoretiska resultat av den genomsnittliga beräkningstiden för populationsbaserade EA är få. De allra flesta tillämpningar av EAs använder dock en populationsstorlek som är större än en. Användningen av befolkningen har betraktats som ett av de viktigaste inslagen i EA. Det är viktigt att på djupet förstå vad befolkningens verkliga nytta är när det gäller EA:s tids komplexitet, när EA:er tillämpas på kombinatoriska optimeringsproblem. Detta dokument jämför (1 + 1) EA och (N + N ) EA teoretiskt genom att härleda sin första träfftid på samma problem. Det visas att en befolkning kan ha en drastisk inverkan på en EA:s genomsnittliga beräkningstid, vilket i vissa fall ändrar en exponentiell tid till en polynomtid (i indatastorleken). Det visas också att den första träffsannolikheten kan förbättras genom att införa en befolkning. De resultat som presenteras i detta dokument innebär dock inte att befolkningsbaserade EA alltid kommer att vara bättre än (1 + 1) EA för alla möjliga problem. [9], som gör det svårt att göra en teoretisk jämförelse mellan EAS och andra optimeringsalgoritmer. Det är nödvändigt att få en djupare förståelse för EA:s tidsmässiga komplexitet för att förstå om en EA förväntas skalas väl med insatsstorleken och när en EA förväntas ge de största fördelarna med ett visst problem. Det har gjorts en del arbete på analysen av tids komplexitet (1 + 1) [8]. Eftersom (1 + 1) EA inte omfattar återkombination och populationsbaserat urval, kan resultaten på (1 + 1) EA inte generaliseras till EA med en populationsstorlek som är större än en. Det är viktigt att förstå vilken inverkan en befolkning kan ha på en EA:s genomsnittliga beräkningstid. En sådan förståelse förväntas sprida lite ljus över den verkliga nyttan av populationsbaserade EAs i kombinatorisk optimering [1], [2]. I den här artikeln jämför vi (1 + 1) och (N + N ) EA teoretiskt på två familjer av problem. Vi får den första träfftiden för (1 + 1) och (N + N ) EA, respektive. Sådana resultat gör det möjligt för oss att observera när tiden skulle vara polynom eller exponentiellt i indatastorlek. De matematiska tekniker som används i detta dokument följer dem i den analytiska metoden för passagetiden för Markovkedjor [18]. Till skillnad från driftanalys [8], som uppskattar den första slå tid från drift av en Markov kedja, dessa tekniker beräkna den första slå tiden av en Markov kedja direkt från övergångsmatrisen. Fördelen med driftanalysen är att ett exakt uttryck för den första slagtiden kan erhållas för vissa EAS. Nackdelen är att sådana exakta uttryck är svåra, om inte omöjliga, att härleda från övergångsmatriser om de är alltför komplexa. Resten av detta dokument är organiserat enligt följande. I avsnitt II introduceras några noteringar, definitioner och teorem om den första träfftiden i en Markovkedja. Avsnitt III innehåller våra huvudsakliga resultat. Med tanke på typiska problem, vi härleda den första slå tid (1 + 1) och (N + N ) EAs, respektive, och försöka svara på följande frågor. 1) Kommer en (N + N ) EA ändra tids komplexiteten hos en (1 + 1) EA för ett givet problem, t.ex. från exponentiellt till polynom tid eller vice versa? 2) Hur mycket kommer en (N + N ) EA att ändra den genomsnittliga sannolikheten för en (1 + 1) EA för ett givet problem? 3) Hur mycket kommer en (N + N ) EA att ändra den genomsnittliga första träfftiden för en (1 + 1) EA för ett givet problem? Även partiella svar på ovanstående frågor kommer att fördjupa vår förståelse av befolkningens roll i EA. Slutligen avslutar avsnitt IV dokumentet med en kort sammanfattning av dokumentet och några kommentarer.
Som en av de tidigaste noggranna analyserna undersökte han och Yao Ref hur den förväntade träfftiden för EA varierar i takt med att befolkningsstorleken ökar.
From an individual to a population: An analysis of the first hitting time of population-based evolutionary algorithms
{'venue': 'IEEE Transactions on Evolutionary Computation', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}