2015/04/23 by Tiago Paixão, Paixão, Tiago, Jorge Pérez Heredia +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Evolution and Genetic Dynamics #Evolutionary Algorithms and Applications #F.2.2 #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE)
paper · pdf · doi:10.48550/arxiv.1504.06260
openalex publication_date 2015/04/23 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired\nby natural evolution. In recent years the field of evolutionary computation has\ndeveloped a rigorous analytical theory to analyse their runtime on many\nillustrative problems. Here we apply this theory to a simple model of natural\nevolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the\ntime between occurrence of new mutations is much longer than the time it takes\nfor a new beneficial mutation to take over the population. In this situation,\nthe population only contains copies of one genotype and evolution can be\nmodelled as a (1+1)-type process where the probability of accepting a new\ngenotype (improvements or worsenings) depends on the change in fitness.\n We present an initial runtime analysis of SSWM, quantifying its performance\nfor various parameters and investigating differences to the (1+1)EA. We show\nthat SSWM can have a moderate advantage over the (1+1)EA at crossing fitness\nvalleys and study an example where SSWM outperforms the (1+1)EA by taking\nadvantage of information on the fitness gradient.\n