Markov Chain Analysis of Cumulative Step-size Adaptation on a Linear Constrained Problem

Abstract

This paper analyzes a (1, $\lambda$)-Evolution Strategy, a randomized comparison-based adaptive search algorithm, optimizing a linear function with a linear constraint. The algorithm uses resampling to handle the constraint. Two cases are investigated: first the case where the step-size is constant, and second the case where the step-size is adapted using cumulative step-size adaptation. We exhibit for each case a Markov chain describing the behaviour of the algorithm. Stability of the chain implies, by applying a law of large numbers, either convergence or divergence of the algorithm. Divergence is the desired behaviour. In the constant step-size case, we show stability of the Markov chain and prove the divergence of the algorithm. In the cumulative step-size adaptation case, we prove stability of the Markov chain in the simplified case where the cumulation parameter equals 1, and discuss steps to obtain similar results for the full (default) algorithm where the cumulation parameter is smaller than 1. The stability of the Markov chain allows us to deduce geometric divergence or convergence , depending on the dimension, constraint angle, population size and damping parameter, at a rate that we estimate. Our results complement previous studies where stability was assumed.

Evolutionary Computation, Massachusetts Institute of Technology Press (MIT Press): STM Titles, 2015

References in corpus (1)

• Markov Chain Analysis of Cumulative Step-size Adaptation on a Linear Constrained Problem

Cited by in corpus (32)

• Markov Chain Analysis of Cumulative Step-size Adaptation on a Linear Constrained Problem
• Bat Algorithm: A Novel Approach for Global Engineering Optimization
• Difficulty Adjustable and Scalable Constrained Multi-objective Test Problem Toolkit
• A Niching Indicator-Based Multi-modal Many-objective Optimizer
• Memetic Viability Evolution for Constrained Optimization
• Beetle Swarm Optimization Algorithm:Theory and Application
• A Covariance Matrix Self-Adaptation Evolution Strategy for Optimization under Linear Constraints
• Mitigating Unfairness via Evolutionary Multi-objective Ensemble Learning
• Modulation of calmodulin lobes by different targets: an allosteric model with hemiconcerted conformational transitions
• Optimizing Controller Placement for Software-Defined Networks
• Push and Pull Search for Solving Constrained Multi-objective Optimization Problems
• The MOEADr Package - A Component-Based Framework for Multiobjective Evolutionary Algorithms Based on Decomposition
• An Instance Space Analysis of Constrained Multi-Objective Optimization Problems
• IRS-Aided Overloaded Multi-Antenna Systems: Joint User Grouping and Resource Allocation
• Confronting SUSY SO(10) with updated Lattice and Neutrino Data
• B-Splines for Sparse Grids: Algorithms and Application to Higher-Dimensional Optimization
• Inference of neutrino flavor evolution through data assimilation and neural differential equations
• HAWKS: Evolving Challenging Benchmark Sets for Cluster Analysis
• Solving the G-problems in less than 500 iterations: Improved efficient constrained optimization by surrogate modeling and adaptive parameter control
• Adaptive Ranking Based Constraint Handling for Explicitly Constrained Black-Box Optimization
• Push and Pull Search Embedded in an M2M Framework for Solving Constrained Multi-objective Optimization Problems
• A ranking approach to global optimization
• MOEA/D with Angle-based Constrained Dominance Principle for Constrained Multi-objective Optimization Problems
• HPC-based Solvers of Minimisation Problems for Signal Processing
• A New Repair Operator for Multi-objective Evolutionary Algorithm in Constrained Optimization Problems
• Handling equality constraints by adaptive relaxing rule for swarm algorithms
• SWAF: Swarm Algorithm Framework for Numerical Optimization
• Statistical Model Checking based Analysis of Biological Networks
• Nonlinear Optimization in R using nlopt
• Parameter inference and model selection in signaling pathway models
• Towards a generic implementation of matrix-element maximisation as a classifier in particle physics
• Interpretable and Fair Generalized Additive Neural Networks via Multi-objective Learning