Memetiska algoritmer är evolutionära algoritmer som inkluderar lokal sökning för att öka exploateringen. Denna hybridisering har varit fruktbar i otaliga tillämpningar. Teorin om memetiska algoritmer är dock fortfarande i sin linda. Här introducerar vi en enkel memetisk algoritm, den (1+1) Memetic Algorithm ((1+1) MA), som arbetar med en populationsstorlek på 1 och ingen crossover. Vi jämför den med den välkända (1+1) EA och randomiserade lokala sökningen och visar att dessa algoritmer kan överträffa varandra drastiskt. När det gäller problem som t.ex. problem med långa vägar är det viktigt att begränsa den lokala sökningens varaktighet. Vi undersöker (1+1) MA med en fast maximal lokal söktid och definierar en klass av fitnessfunktioner där en liten variation av den lokala söktiden har stor inverkan på prestandan hos (1+1) MA. Alla resultat bevisas rigoröst utan antaganden.
I REF gavs exempel på konstruerade funktioner där (1+1) EA, (1+1) MA och Randomized Local Search (RLS) ömsesidigt kan överträffa varandra.
On the analysis of the (1+1) memetic algorithm
{'venue': "GECCO '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}