” 辅导720 IEEE编程、 写作Python720 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 22, NO. 5, OCTOBER 2018Standard Steady State Genetic Algorithms CanHillclimb Faster Than Mutation-OnlyEvolutionary AlgorithmsDogan Corus, Member, IEEE, and Pietro S. Oliveto , Senior Member, IEEEAbstractExplaining to what extent the real power of geneticalgorithms (GAs) lies in the ability of crossover to recombine indi-viduals into higher quality solutions is an important problem inevolutionary computation. In this paper we show how the inter-play between mutation and crossover can make GAs hillclimbfaster than their mutation-only counterparts. We devise a Markovchain framework that Allows to rigorously prove an upper boundon the runtime of standard steady state GAs to hillclimb theONEMAX function. The bound establishes that the steady-stateGAs are 25% faster than all standard bit mutation-only evolu-tionary algorithms with static mutation rate up to lower orderterms for moderate population sizes. The analysis also suggeststhat larger populations may be faster than populations of size 2.We present a lower bound for a greedy (2 + 1) GA that matchesthe upper bound for populations larger than 2, rigorously provingthat two individuals cannot outperform larger population sizesunder greedy selection and greedy crossover up to lower orderterms. In complementary experiments the best population sizeis greater than 2 and the greedy GAs are faster than standardones, further suggesting that the derived lower bound also holdsfor the standard steady state (2 + 1) GA.Index TermsAlgorithms design and analysis, genetic algo-rithms (GAs), Markov processes, stochastic processes.I. INTRODUCTIONGENETIC algorithms (GAs) rely on a population of indi-viduals that simultaneously explore the search space.The main distinguishing features of GAs from other random-ized search heuristics is their use of a population and crossoverto generate new solutions. Rather than slightly modifying thecurrent best solution as in more traditional heuristics, the ideabehind GAs is that new solutions are generated by recom-bining individuals of the current population (i.e., crossover).Such individuals are selected to reproduce probabilisticallyaccording to their fitness (i.e., reproduction). Occasionally,Manuscript received November 15, 2016; revised April 13, 2017,July 7, 2017, and August 3, 2017; accepted August 5, 2017. Date of publi-cation September 26, 2017; date of current version September 28, 2018. Thiswork was supported by EPSRC under Grant EP/M004252/1. (Correspondingauthor: Pietro S. Oliveto.)The authors are with the Rigorous Research Team, Algorithms Group,Department of Computer Science, University of Sheffield, Sheffield S1 4DP,U.K. (e-mail: d.corus@sheffield.ac.uk; p.oliveto@sheffield.ac.uk).This paper has supplementary downloadable multimedia material availableat https://ieeexplore.ieee.org provided by the authors.Color versions of One or more of the figures in this paper are availableonline at https://ieeexplore.ieee.org.Digital Object Identifier 10.1109/TEVC.2017.2745715random mutations may slightly modify the offspring producedby crossover. The original motivation behind these mutationsis to avoid that some genetic material may be lost forever, thusallowing to avoid premature convergence [16], [18]. For thesereasons the GA community traditionally regards crossover asthe main search operator while mutation is considered a back-ground operator [1], [16], [19] or a secondary mechanismof genetic adaptation [18].Explaining when and why GAs are effective has proved tobe a nontrivial task. Schema theory and its resulting buildingblock hypothesis [18] were devised to explain such workingprinciples. However, these theories did not allow to rigor-ously characterize the behavior and performance of GAs.The hypothesis Was disputed when a class of functions (i.e.,Royal Road), thought to be ideal for GAs, was designed andexperiments revealed that the simple (1+1) EA was moreefficient [20], [27].Runtime analysis approaches have provided rigorous proofsthat crossover may indeed speed up the evolutionary processof GAs in ideal conditions (i.e., if sufficient diversity is avail-able in the population). The JUMP function was introduced byJansen and Wegener [22] as a first example, where crossoverconsiderably improves the expected runtime compared tomutation-only evolutionary algorithms (EAs). The proofrequired an unrealistically small crossover probability to allowmutation alone to create the necessary population diversityfor the crossover operator to then escape the local optimum.Dang et al. [6] recently showed that the sufficient diversity,and even faster Upper bounds on the runtime for not too largejump gaps, can be achieved also for realistic crossover proba-bilities by using diversity mechanisms. Further examples thatshow the effectiveness of crossover have been given for bothartificially constructed functions and standard combinatorialoptimization problems (see the next section for an overview).Excellent hillclimbing performance of crossover-based GAshas been also proved. Doerr et al. [8], [9] proposed a请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
