METHOD OF ARTIFICIAL FITNESS LEVELS FOR DYNAMICS ANALYSIS OF EVOLUTIONARY ALGORITHMS
Journal: Scientific and Technical Journal of Information Technologies, Mechanics and Optics (Vol.20, No. 5)Publication Date: 2020-10-10
Authors : Buzdalov M.V. Vinokurov D.V.;
Page : 701-707
Keywords : evolutionary algorithms; runtime analysis; fixed-target analysis; fixed-budget analysis; fitness-level method;
Abstract
Subject of Research. Currently, in the theory of evolutionary computation, it becomes relevant to analyze not just the runtime of evolutionary algorithms, but also their dynamics. The two most common methods for dynamics analysis are: fixed-budget analysis, which studies an algorithm reachable fitness in condition of operation time limit, and fixedtarget analysis, which studies the time that an algorithm needs to reach some fixed fitness value. Until now, theoretical studies were systematically carried out only for the first type of analysis. The present work is focused on removal of this disadvantage. Method. We proved the following theorem: if the bounds on optimization time for some evolutionary algorithm on some problem are already proven using artificial fitness levels, than the bounds on this algorithm dynamics on the considered problem derive automatically from the same preconditions. Main Results. Using this theorem, we obtain the upper bounds on fixed-target runtime for the following pairs of algorithms and problems: the family of (1 + 1) evolutionary algorithms on LeadingOnes and OneMax functions, and (μ + 1) evolutionary algorithm on OneMax. These bounds either repeat or refine the existing results, but in a much simpler way. Practical Relevance. The main practical achievement of this paper is that it simplifies the proving of bounds on the dynamics of evolutionary algorithms. In turn, these bounds could be more meaningful for choosing between different evolutionary algorithms for some problem than the time for reaching the optimum, as the latter is mostly infeasible in practice.
Other Latest Articles
- A Note on Different Types of Probabilities of Misclassification
- EFFECT OF CROPPING SYSTEMS ON THE NUTRITIONAL VALUES OF CASHEW IN AGRO-ECOLOGICAL ZONES OF CASHEW TREES IN BENIN
- CMSA/CA PROTOCOL ANALYSIS IN OMNET++ ENVIRONMENT WITH INET FRAMEWORK
- UNDERSTANDING ADOLESCENT RISK PERCEPTIONS ABOUT HIV AND AIDS IN KENYA: ASSESSING THE EFFECTIVENESS OF THE TRUST CONDOM A KUWA TRUEA CAMPAIGN
- Forecasting of COVID-19 Cases in Kurdistan Region Using Some Statistical Models
Last modified: 2020-10-26 20:42:17