ABSTRACT
We study the behaviour of a (1,λ)-ES that applies a simple repair mechanism to infeasible candidate solutions for the problem of maximising a linear function with a single linear constraint. Integral expressions that describe the strategy's one-generation behaviour are derived and used in a simple zeroth order model for the steady state of the strategy. Applied to the analysis of cumulative step size adaptation, the approach provides an intuitive explanation for the algorithm's behaviour as well as a condition on the setting of its parameters. A comparison with the strategy that resamples infeasible candidate solutions rather than repairing them is drawn, and the qualitatively different behaviour is explained.
- D. V. Arnold. Noisy Optimization with Evolution Strategies. Kluwer Academic Publishers, 2002. Google ScholarDigital Library
- D. V. Arnold. On the use of evolution strategies for optimising certain positive definite quadratic forms. In Genetic and Evolutionary Computation Conference -- GECCO 2007, pages 634--641. ACM Press, 2007. Google ScholarDigital Library
- D. V. Arnold. On the behaviour of the (1,lambda)-ES for a simple constrained problem. In H.-G. Beyer and W. B. Langdon, editors, Foundations of Genetic Algorithms -- FOGA 2011, pages 15--24. ACM Press, 2011. Google ScholarDigital Library
- D. V. Arnold and H.-G. Beyer. Performance analysis of evolutionary optimization with cumulative step length adaptation. IEEE Transactions on Automatic Control, 49(4):617--622, 2004.Google ScholarCross Ref
- D. V. Arnold and D. Brauer. On the behaviour of the (1 + 1)-ES for a simple constrained problem. In G. Rudolph et al., editors, Parallel Problem Solving from Nature -- PPSN X, pages 1--10. Springer Verlag, 2008.Google Scholar
- D. V. Arnold and A. MacLeod. Step length adaptation on ridge functions. Evolutionary Computation, 16(2):151--184, 2008. Google ScholarDigital Library
- H.-G. Beyer. Ein Evolutionsverfahren zur mathematischen Modellierung stationärer Zustände in dynamischen Systemen. PhD thesis, Hochschule für Architektur und Bauwesen, Weimar, 1989.Google Scholar
- H.-G. Beyer and H.-P. Schwefel. Evolution strategies -- A comprehensive introduction. Natural Computing, 1(1):3--52, 2002. Google ScholarDigital Library
- C. A. Coello Coello. Constraint-handling techniques used with evolutionary algorithms. In Proceedings of the 2008 GECCO Conference Companion on Genetic and Evolutionary Computation, pages 2445--2466. ACM Press, 2008. Google ScholarDigital Library
- O. Kramer and H.-P. Schwefel. On three new approaches to handle constraints within evolution strategies. Natural Computing, 5(4):363--385, 2006. Google ScholarDigital Library
- R. Mallipeddi and P. N. Suganthan. Problem definitions and evaluation criteria for the CEC 2010 Competition on Constrained Real-Parameter Optimization. Technical report, Nanyang Technological University, Singapore, 2010.Google Scholar
- E. Mezura-Montes and C. A. Coello Coello. A simple multi-membered evolution strategy to solve constrained optimization problems. IEEE Transactions on Evolutionary Computation, 9(1):1--17, 2005. Google ScholarDigital Library
- A. Ostermeier, A. Gawelczyk, and N. Hansen. Step-size adaptation based on non-local use of selection information. In Y. Davidor et al., editors, Parallel Problem Solving from Nature -- PPSN III, pages 189--198. Springer Verlag, 1994. Google ScholarDigital Library
- A. I. Oyman, K. Deb, and H.-G. Beyer. An alternative constraint handling method for evolution strategies. In Proc. of the 1999 IEEE Congress on Evolutionary Computation, pages 612--619. IEEE Press, 1999.Google ScholarCross Ref
- I. Rechenberg. Evolutionsstrategie -- Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Friedrich Frommann Verlag, 1973.Google Scholar
- T. P. Runarsson and X. Yao. Stochastic ranking for constrained evolutionary optimization. IEEE Transactions on Evolutionary Computation, 4(3):274--283, 2000. Google ScholarDigital Library
- T. P. Runarsson and X. Yao. Search biases in constrained evolutionary optimization. IEEE Transactions on Systems, Man and Cybernetics -- Part C: Applications and Reviews, 35(2):233--243, 2005. Google ScholarDigital Library
- H.-P. Schwefel. Numerical Optimization of Computer Models. Wiley, 1981. Google ScholarDigital Library
- H.-P. Schwefel. Evolution and Optimum Seeking. Wiley, 1995.Google ScholarDigital Library
Index Terms
- Analysis of a repair mechanism for the (1,λ)-ES applied to a simple constrained problem
Recommendations
On the behaviour of the (1,λ)-es for a simple constrained problem
FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithmsWe study the behaviour of the (1,λ)-ES for a linear problem with a single linear constraint. The algorithm produces offspring until λ feasible candidate solutions have been generated and selects the best of those as the next generation's parent. ...
Resampling versus repair in evolution strategies applied to a constrained linear problem
We study the behaviour of multi-recombination evolution strategies for the problem of maximising a linear function with a single linear constraint. Two variants of the algorithm are considered: a strategy that resamples infeasible candidate solutions ...
On the behaviour of the (1, λ)-es for a conically constrained problem
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computationWe consider a conically constrained optimisation problem where the optimal solution lies at the apex of the cone and study the behaviour of a (1,λ)-ES that handles constraints by resampling infeasible candidate solutions. Expressions that describe the ...
Comments