METHOD OF ARTIFICIAL FITNESS LEVELS FOR DYNAMICS ANALYSIS OF EVOLUTIONARY ALGORITHMS
Annotation
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 fixed- target 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.
Keywords
Постоянный URL
Articles in current issue
- PRODUCIBILITY ANALYSIS OF LENS SYSTEM DURING OPTICAL DESIGN STAGE(in English)
- EFFECT OF LASER PROCESSING PARAMETERS ON SPECTRAL CHARACTERISTICS OF SILVER-IMPREGNATED TITANIUM DIOXIDE THIN FILMS
- OPTICAL MODULE DESIGN FOR AUGMENTED REALITY GLASSES
- SEARCH QUALITY METHODOLOGY AND PARTICULAR FINDINGS FOR KEY POINTS BASED ON MATERIALS OF OPTICAL-ELECTRONIC AERIAL SURVEY
- ROUGHNESS STUDY OF PAPER MADE FROM SECONDARY RAW MATERIALS BY ATOMIC FORCE MICROSCOPY
- METHOD FOR HYPERPARAMETER TUNING IN MACHINE LEARNING TASKS FOR STOCHASTIC OBJECTS CLASSIFICATION
- HIERARCHICAL DIAGNOSTIC MODEL SYNTHESIS FOR DATAFLOW REAL-TIME COMPUTING SYSTEM
- COMPARATIVE ANALYSIS OF METHODS FOR IMBALANCE ELIMINATION OF EMOTION CLASSES IN VIDEO DATA OF FACIAL EXPRESSIONS
- CMSA/CA PROTOCOL ANALYSIS IN OMNET++ ENVIRONMENT WITH INET FRAMEWORK
- DETERMINATION OF PACKED AND ENCRYPTED DATA IN EMBEDDED SOFTWARE
- SEARCH OF CLONES IN PROGRAM CODE
- CONFIGURABLE IOT DEVICES BASED ON ESP8266 SOC SYSTEM AND MQTT PROTOCOL
- NOISE IMMUNITY OF WIRELESS PERSONAL AREA NETWORKS UNDER DIGITAL PRODUCTION CONDITIONS
- DISTRIBUTED CONVOLUTIONAL NEURAL NETWORK MODEL ON RESOURCE-CONSTRAINED CLUSTER
- TRAFFIC AUTHENTICITY ANALYSIS BASED ON DIGITAL FINGERPRINT DATA OF NETWORK PROTOCOL IMPLEMENTATIONS
- PROCESS CHARACTERISTICS ESTIMATION IN WEB APPLICATIONS USING K-MEANS CLUSTERING
- MULTILINE BRAILLE DISPLAY CONSTRUCTION MODEL
- APPLICATION OF LASER RADIATION FOR PLANT GROWTH STIMULATION
- RISK IDENTIFICATION OF SECURITY INFORMATION VIOLATIONS IN CYBER-PHYSICAL SYSTEMS BASED ON ANALYSIS OF DIGITAL SIGNALS