TY - JOUR

T1 - Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change

AU - Oliveto, Pietro S.

AU - Zarges, Christine

N1 - Publisher Copyright:
© 2014 Elsevier B.V.

PY - 2015/1/4

Y1 - 2015/1/4

N2 - Evolutionary dynamic optimisation has become one of the most active research areas in evolutionary computation. We consider the Balance function for which the poor expected performance of the (1+1) EA at low frequencies of change has been shown in the literature. We analyse the impact of populations and diversity mechanisms towards the robustness of evolutionary algorithms with respect to frequencies of change. We rigorously prove that there exists a sufficiently low frequency of change such that the (μ+1) EA without diversity requires exponential time with overwhelming probability for sublinear population sizes. The same result also holds if the algorithm is equipped with a genotype diversity mechanism. Furthermore we prove that a crowding mechanism makes the performance of the (μ+1) EA much worse (i.e., it is inefficient for any population size). On the positive side we prove that, independently of the frequency of change, a fitness-diversity mechanism turns the runtime from exponential to polynomial. Finally, we show how a careful use of fitness-sharing together with a crowding mechanism is effective already with a population of size 2. We shed light through experiments when our theoretical results do not cover the whole parameter range.

AB - Evolutionary dynamic optimisation has become one of the most active research areas in evolutionary computation. We consider the Balance function for which the poor expected performance of the (1+1) EA at low frequencies of change has been shown in the literature. We analyse the impact of populations and diversity mechanisms towards the robustness of evolutionary algorithms with respect to frequencies of change. We rigorously prove that there exists a sufficiently low frequency of change such that the (μ+1) EA without diversity requires exponential time with overwhelming probability for sublinear population sizes. The same result also holds if the algorithm is equipped with a genotype diversity mechanism. Furthermore we prove that a crowding mechanism makes the performance of the (μ+1) EA much worse (i.e., it is inefficient for any population size). On the positive side we prove that, independently of the frequency of change, a fitness-diversity mechanism turns the runtime from exponential to polynomial. Finally, we show how a careful use of fitness-sharing together with a crowding mechanism is effective already with a population of size 2. We shed light through experiments when our theoretical results do not cover the whole parameter range.

KW - Diversity mechanisms

KW - Evolutionary dynamic optimisation

KW - Populations

KW - Runtime analysis

UR - http://www.scopus.com/inward/record.url?scp=84927946654&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2014.10.028

DO - 10.1016/j.tcs.2014.10.028

M3 - Article

SN - 0304-3975

VL - 561

SP - 37

EP - 56

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - A

ER -