i

UNIVERSIDADE TÉCNICA DE LISBOA

INSTITUTO SUPERIOR TÉCNICO

Diversity-Enhanced Genetic Algorithms for

Dynamic Optimization

CARLOS MIGUEL DA COSTA FERNANDES (Mestre)

Dissertação para obtenção do Grau de Doutor em Engenharia

Electrotécnica e de Computadores

Orientador: Doutor Agostinho Cláudio da Rosa

Júri

Presidente: Presidente do Conselho Científico do IST

Vogais: Doutor Rui Luís Vilela de Lima Mendes

Doutor Agostinho Cláudio da Rosa

Doutor Juan Julián Merelo Guervós

Doutor Fernando Miguel Pais da Graça Lobo

Doutor Nuno Cavaco Gomes Horta

Doutor Pedro Manuel Santos de Carvalho

Dezembro de 2009

ii

iii

Título: Algoritmos Genéticos com Diversidade Genética para Optimização Dinâmica

Nome: Carlos Miguel da Costa Fernandes

Doutoramento em: Engenharia Electrotécnica e de Computadores

Orientador: Agostinho Cláudio da Rosa

Resumo

Diversas aplicações industriais têm componentes dinâmicas que conduzem a variações na

função objectivo, e os Algoritmos Genéticos (AGs), devido à adaptabilidade, surgem como

ferramentas apropriadas para resolver este tipo de problemas. A tese propõe dois novos

métodos evolutivos para optimização dinâmica. O primeiro está direccionado para a

recombinação e, com um mecanismo auto-regulado, evita cruzamentos entre soluções

semelhantes, mantendo, dessa forma, diversidade genética. O segundo é um novo operador

de mutação do qual emergem taxas variáveis auto-reguladas, com uma distribuição

adequada para optimização dinâmica. Propõe-se ainda um método híbrido eficaz que

combina as duas estratégias. O objectivo, e principal alegação da tese, é criar protocolos

inspirados em sistemas reais que melhoram o desempenho dos AGs sem aumentar a sua

complexidade, e sem informação a priori sobre o problema.

As propostas foram testadas numa vasta gama de problemas e demonstraram ser mais

eficazes do que outros AGs, nomeadamente quando as mudanças não são rápidas. O

algoritmo híbrido demonstrou ser particularmente eficaz, pois alarga a gama de aplicações

nas quais cada método, isolado, tem um bom desempenho. Tal como é proposto, os

algoritmos são robustos e não aumentam o espaço de parâmetros, cumprindo dessa forma

algumas exigências das aplicações reais.

Palavras-chave: Computação Evolutiva, Algoritmos Genéticos, Optimização Dinâmica,

Acasalamenteo Não-Aleatório, Criticalidade Auto-Organizada, Diversidade Genética.

iv

v

Abstract

Many industrial applications have dynamic components that lead to variations of the

fitness function and Genetic Algorithms (GAs) adaptiveness is an appropriate tool to solve

this type of problems. The thesis proposes two new evolutionary methods to tackle dynamic

problems. The first acts upon mating and avoids crossover between similar individuals, via

a self-regulated mechanism, thus preserving genetic diversity. The second is a new

mutation operator able to evolve self-regulated mutation rates with a particular distribution

that is suited for dynamic optimization. Finally, an efficient hybrid method that combines

both strategies is proposed. The objective and main claim is the possibility of designing

nature-inspired protocols for GAs that are efficient when evolving on dynamic

environments while preserving algorithms’ complexity and not requiring a priori

information about the problem.

The proposals are tested on a wide range of problems and are able to outperform

frequently other GAs, namely when the frequency of change is lower. The hybrid scheme

proves to be particularly effective since it broadened the range of dynamics in which each

method by itself excels. As projected, the proposed techniques are robust and do not

increase parameters’ set, thus fulfilling necessary conditions for real-world applications.

Keywords: Evolutionary Computation, Genetic Algorithms, Dynamic Optimization,

Genetic Diversity, Non-Random Mating, Self-Organized Criticality.

vi

vii

Acknowledgments

I have a debt of gratitude to all of you who assisted me, encouraged me and guided me

during this long and hard (although exhilarating) project.

I am deeply grateful to all my colleagues, co-workers, and co-authors, both from Laseeb,

in Lisbon, and Geneura, in Granada, and also to Claudio Lima (also one of my co-authors)

from Universidade do Algarve, who introduced me to the fascinating new generation of

Evolutionary Algorithms. In particular, I would like to salute Juanlu, my colleague at

Geneura and my dear friend, who supported me in some the hardest periods of this work. I

also thank to my advisor Agostinho Rosa, and the thesis committee, Rui Vilela Mendes and

Pedro Carvalho, for their support and advice.

A special thank to J.J. Merelo, who welcomed me in Granada in his prolific and ―warm‖

laboratory. Another special thank to Jorge Calado; although we never discussed a single

issue of this thesis, it is of his sage advices I think often on those occasions when things

hardly make any sense.

To my Father and my Mother goes my deepest expression of gratitude.

Finally, this thesis is dedicated to Maria João Martins.

Carlos M. Fernandes

Granada, March 15, 2009

This work was supported by Ministério da Ciência e Tecnologia, Research Fellowship

SFRH/BD/18868/2004, partially supported by Fundação para a Ciência e a Tecnologia

(ISR/IST plurianual funding) through POS_Conhecimento Program that includes FEDER

funds.

viii

ix

Table of Contents

Chapter 1 ............................................................................................................................................. 1

1.1 Objectives ............................................................................................................................ 1

1.2 Contributions ....................................................................................................................... 7

1.3 Thesis Outline ................................................................................................................... 10

Chapter 2 ........................................................................................................................................... 13

2.1 Introduction ....................................................................................................................... 13

2.2 Evolutionary Algorithms ................................................................................................... 14

2.3 Uncertainties in Optimization Problems ........................................................................... 18

2.4 Dynamic Optimization ...................................................................................................... 19

2.5 Evolutionary Algorithms for Dynamic Optimization ........................................................ 22

2.5.1 Estimation of Distribution Algorithms ...................................................................... 31

2.6 Swarm intelligence in Dynamic Environments ................................................................. 35

2.7 Dynamic Problems ............................................................................................................ 40

2.8 Dynamic Problems Generators .......................................................................................... 44

2.9 A Critical Note on the Experimental Research Methodology on Dynamic Optimization 47

2.10 Summary ........................................................................................................................... 49

Chapter 3 ........................................................................................................................................... 51

3.1 Introduction ....................................................................................................................... 51

3.2 Random and Non-Random Mating ................................................................................... 52

3.3 Non-Random Mating Evolutionary Algorithms ................................................................ 56

3.4 The Adaptive Dissortative Mating Genetic Algorithm ..................................................... 63

3.5 Summary ........................................................................................................................... 66

Chapter 4 ........................................................................................................................................... 67

4.1 Introduction ....................................................................................................................... 67

4.2 Functions ........................................................................................................................... 69

4.2.1 Methodology ............................................................................................................. 74

4.2.2 Results: Functions f1, f2 and f3 ................................................................................... 77

4.2.3 Results: Function f4 ................................................................................................... 81

4.2.4 Results: Knapsack Problem ....................................................................................... 85

x

4.2.5 Results: Royal Road R1 ............................................................................................ 85

4.2.6 Results: Royal Road R4 ............................................................................................ 86

4.3 ADMGA Scalability with Trap Functions ........................................................................ 88

4.4 Genetic Diversity and Threshold Dynamics ...................................................................... 93

4.4.1 Genetic Diversity ....................................................................................................... 93

4.4.2 Threshold’s dynamics ................................................................................................ 96

4.5 Assortative Mating, Mutation Probability and Chromosome Codification ..................... 101

4.5.1 Assortative Mating and Mutation Probability ......................................................... 102

4.6 Extending ADMGA to Other Types of Codification ...................................................... 104

4.7 Summary ......................................................................................................................... 105

Chapter 5 ......................................................................................................................................... 107

5.1 Introduction ..................................................................................................................... 107

5.2 Results: Dynamic Trap Functions ................................................................................... 107

5.2.1 Standard GAs .......................................................................................................... 112

5.2.2 Random Immigrants GAs ........................................................................................ 122

5.2.3 Hypermutation Schemes .......................................................................................... 126

5.2.4 Assortative and Dissortative Mating GAs ............................................................... 129

5.2.5 Order-5 Dynamic Trap Problems ............................................................................ 133

5.3 Results: Dynamic Royal Road and Knapsack ................................................................. 135

5.3.1 Dynamic Royal Road .............................................................................................. 136

5.3.2 Dynamic 0-1 Knapsack ........................................................................................... 141

5.4 Summary ......................................................................................................................... 142

Chapter 6 ......................................................................................................................................... 145

6.1 Introduction ..................................................................................................................... 145

6.2 Self-Organized Criticality ............................................................................................... 146

6.2.1 Bak-Tang-Wisenfeld Sandpile Model ..................................................................... 150

6.2.2 The Bak-Sneppen Model ......................................................................................... 153

6.3 SOC in Evolutionary Computation ................................................................................. 154

6.4 The Sandpile Mutation .................................................................................................... 156

6.4.1 First version ............................................................................................................. 158

6.4.2 Second Version........................................................................................................ 163

6.5 Summary ......................................................................................................................... 166

Chapter 7 ......................................................................................................................................... 169

xi

7.1 Introduction ..................................................................................................................... 169

7.2 GGASM First Version: Results ......................................................................................... 170

7.3 GGASM (2): Results ......................................................................................................... 176

7.3.1 Comparing the Genetic Algorithms with Sand Pile Mutation ................................. 177

7.3.2 SORIGA and EIGA ................................................................................................. 179

7.4 Grain Rates and Mutation Rates ...................................................................................... 182

7.4.1 Grain Rate and Optimal Results .............................................................................. 183

7.4.2 Offline Mutation Rate ............................................................................................. 186

7.4.3 Online mutation rate ................................................................................................ 188

7.5 Summary ......................................................................................................................... 195

Chapter 8 ......................................................................................................................................... 197

8.1 Introduction ..................................................................................................................... 197

8.2 Dissortative Mating and Sand Pile Mutation................................................................... 197

8.3 Dynamic Royal Road Functions ...................................................................................... 201

8.4 Dynamic Knapsack Problems ......................................................................................... 203

8.5 Fast Dynamic Problems................................................................................................... 204

8.6 Summary ......................................................................................................................... 209

Chapter 9 ......................................................................................................................................... 213

xii

xiii

List of Figures

Figure 2.1: Pseudo-code of the Standard Genetic Algorithm (SGA). ................................................ 16

Figure 2.2: Pseudo-code of the Random Immigrants Genetic Algorithm (RIGA). ............................. 29

Figure 2.3: The Swarm Intelligence model by Fernandes et al. (2005a) evolving on a multimodal

function. .................................................................................................................................... 38

Figure 2.4: Dynamics proposed by Angeline (1992) as possible trajectories of the base function

over time along with their projection onto the (𝑥, 𝑦)-plane. Linear (left), circular (centre) and

random dynamics (right). Taken from (Angeline, 1992). .......................................................... 43

Figure 3.1: Pseudo-code of the Adaptive Dissortative Mating Genetic Algorithm (ADMGA). .......... 64

Figure 4.1: Three-dimensional plot of the sphere model. ................................................................ 69

Figure 4.2: Three-dimensional plot of the Ackley function. .............................................................. 70

Figure 4.3: Three-dimensional plot of the 𝑓4 function. .................................................................... 72

Figure 4.4: Function 𝑓3. AES values for different mutation probability values. Parameters: 𝑛 = 4;

𝑝𝑐 = 1.0; 𝑛 = 8. .................................................................................................................... 79

Figure 4.5: Function 𝑓1. Comparing ADMGA with two CHC-like algorithms. ................................... 80

Figure 4.6: The bisection method for determining the optimal population size of a GA. ................ 87

Figure 4.7: Generalized order-𝑘 trap function. ................................................................................. 90

Figure 4.8: Scalability with 𝑚−𝑘 trap functions (𝑘 = 2, 𝑘 = 3 and 𝑘 = 4). Optimal population

size and AES values for different problem size 𝑙 = 𝑘 × 𝑚. .................................................... 92

Figure 4.9: Scalability with 𝑚−𝑘 trap functions (𝑘 = 2, 𝑘 = 3 and 𝑘 = 4). Comparing ADMGA

with an elitist generational GA (GGA 2-e) and a steady-state GA (SSGA)................................. 92

Figure 4.10: Genetic diversity and best fitness. 𝑚−𝑘 trap function with 𝑘 = 4 and 𝑚 = 10.

Selectorecombinative GAs with 𝑝𝑐 = 1.0, 𝑛 = 400 and 2-elitism. SSGA 1 creates and

replaces 2 individuals per generation. SSGA 2 creates and replaces 𝑛2 = 200 individuals per

generation. ................................................................................................................................ 95

Figure 4.11: Genetic diversity and best fitness. Comparing SSGA 2 with nAMSSGA (top) and

pAMSSGA (bottom). 𝑚−𝑘 trap function with 𝑘 = 4 and 𝑚 = 10. Selectorecombinative GAs

with 𝑝𝑐 = 1.0, 𝑛 = 400 and 2-elitism. .................................................................................. 96

xiv

Figure 4.12: Function 𝑓3. ADMGA’s threshold value after one generation (𝑡𝑠𝑡 = 1) measured as

the percentage 𝑙. Results averaged over 10 independent runs. .............................................. 98

Figure 4.13: ADMGA’s threshold value after one generation (𝑡𝑠𝑡 = 1) measured as a percentage of

𝑙. Random selection. Results averaged over 10 independent runs. ......................................... 98

Figure 4.14: Function 𝑓1. 𝑡𝑠 when ADMGA is run with different 𝑝𝑚 values. Parameters: 𝑛 = 4

and 𝑙 = 200. Uniform crossover. Results averaged over 10 independent runs. ................... 99

Figure 4.15: Function 𝑓1 and 𝑓2. 𝑡𝑠 values. Parameters: 𝑛 = 4, 𝑙 = 200 and 𝑝𝑚 = 0.007.

Uniform crossover. Results averaged over 25 independent runs. ......................................... 100

Figure 4.16: Function 𝑓4. 𝑡𝑠 values with different population size 𝑛. Parameters: 𝑙 = 40 and

𝑝 𝑚 = 0.02. Uniform crossover. Results averaged over 25 runs. ......................................... 101

Figure 4.17: Threshold (𝑡𝑠) value during ADMGA’s run on three 𝑚−𝑘 trap functions with the same

length 𝑙 = 𝑘 × 𝑚 .................................................................................................................. 102

Figure 5.1: Order-3 dynamic trap functions: ADMGA, GGA and SSGA averaged offline performance

when population size 𝑛 changes. ............................................................................................ 112

Figure 5.2: Order-3 dynamic trap functions: GGA’s offline performance on the twelve scenarios

with different population size n and 𝑝𝑚 = 1𝑙 ...................................................................... 113

Figure 5.3: Order-3 dynamic problems: GGA, SSGA and ADMGA averaged offline performance

with different pm. Population size: 𝑛 = 30. ........................................................................... 113

Figure 5.4: Order-4 dynamic problems: GGA’s performance on the twelve scenarios with 𝑝𝑚 = 1𝑙

and three population size 𝑛 values. ......................................................................................... 115

Figure 5.5: Order-4 dynamic problems: comparing GGA, SSGA and ADMGA performance with

population size 𝑛 = 30. ......................................................................................................... 116

Figure 5.6: Order-4 dynamic problems. Comparing GGA, SSGA and ADMGA performance with

population size 𝑛 = 60 and different 𝑝𝑚values. ................................................................... 116

Figure 5.7: Order-4 dynamic problems. Best-of-generation values measured throughout the run —

online performance — when 𝜌 = 0.05 (top row) and 𝜌 = 0.95 (bottom row); 𝜀 = 48,000.

GGA (𝑝𝑚 = 1𝑙) and ADMGA (𝑝𝑚 = 2𝑙) with 𝑛 = 30 (left column) and 𝑛 = 60 (right).

................................................................................................................................................. 119

Figure 5.8: “Slow” order-4 dynamic problems. 𝜀 = 480,000. Online performance when 𝜌 = 0.05

(left) and 𝜌 = 0.95 (right). GGA ( 𝑝𝑚 = 1𝑙) and ADMGA (𝑝𝑚 = 2𝑙). Population size:

𝑛 = 30. .................................................................................................................................. 120

xv

Figure 5.9: “Fast” order-4 dynamic trap problems. 𝜀 = 2,400. Online performance with different

severity values. GGA (𝑝𝑚 = 1𝑙) and ADMGA (𝑝𝑚 = 1𝑙). Population size: 𝑛 = 30. ........ 121

Figure 5.10: Order-3 (top row) and order-4 (bottom row) dynamic trap problems. Comparing

ADMGA, RIGA and SORIGA with 𝑛 = 30. RIGA and SORIGA’s parameter 𝑟𝑟 is set to 𝑟𝑟 = 4.

................................................................................................................................................. 123

Figure 5.11: Comparing the offline performance of ADMGA, GGA and EIGA with different

population size 𝑛 values. ......................................................................................................... 124

Figure 5.12: Order-4 dynamic problems: comparing ADMGA, HM 1 (𝑝𝑚 = 0.5) and HM 2

(𝑝𝑚 = 0.3) performance with population size: 𝑛 = 30. .................................................. 127

Figure 5.13: Order-4 dynamic problems. Online performance of GGA and Hypermutation (HM 1)

on low severity scenarios (𝜏 = 0.05). Population size: 𝑛 = 30. GGA and HM 1 with

𝑝𝑚 = 1𝑙. Hypermutation: 𝑝𝑚 = 0.5. ................................................................................ 129

Figure 5.14: Order-3 dynamic problems (𝑘 = 3, 𝑚 = 10). Comparing GGA, and GGA with

dissortative (nAMGGA) and assortative mating (pAMGGA). Population size: 𝑛 = 30. Pool

size: 𝑝 = 4 (AMGGAs). .......................................................................................................... 130

Figure 5.15: Order-4 dynamic problems. Effects of increasing pool size 𝑝 on nAMGGA’s

performance. 𝑛 = 30 (first row) and 𝑛 = 60 (second row)................................................ 131

Figure 5.16: Order-5 dynamic problems. ADMGA and nAMGGA (𝑝 = 4) offline performance.

Population size: 𝑛 = 60. ........................................................................................................ 133

Figure 5.17: Order-5 problem with 𝜀 = 48,000 and 𝜌 = 0.05. nAMGGA online performance with

different 𝑝𝑚values. Population size: 𝑛 = 60. ....................................................................... 134

Figure 5.18: Offline performance of ADMGA (𝑝 𝑚 = 1𝑙), nAMGGA with p = 4 (𝑝𝑚 = 1(8 × 𝑙))

and nAMGA with p = 30 (𝑝𝑚 = 1(16 × 𝑙)) on twelve order-5 dynamic scenarios. Population

size: 𝑛 = 1,000. ..................................................................................................................... 134

Figure 5.19: Dynamic royal road R1 problems: ADMGA, GGA and EIGA offline performance.

Population size n = 30. ADMGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise. GGA:

𝑝𝑚 = 1𝑙; EIGA: 𝑝𝑚 = 2𝑙, 𝑝𝑚𝑖 = 2𝑙 and 𝑟𝑒𝑖 = 0.2. ........................................................ 136

Figure 5.20: Dynamic royal road R1 problems: ADMGA, GGA and EIGA offline performance on the

nine scenarios. Population size: 𝑛 = 60. ADMGA: 𝑝𝑚 = 1𝑙 when 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙

otherwise. GGA: 𝑝𝑚 = 1𝑙. EIGA: 𝑝𝑚 = 1𝑙, 𝑝𝑚𝑖 = 1𝑙 and 𝑟𝑒𝑖 = 0.2. ............................. 137

xvi

Figure 5.21: Royal Road R4. ADMGA and nAMGA online performance. Population size: 𝑛 = 3,000.

𝜀 = 300,000. ADMGA with 𝑝𝑚 = 2𝑙. nAMGA with 𝑝𝑚 = 1(2 × 𝑙) and 𝑝 = 4. ............ 140

Figure 5.22: Dynamic knapsack problem. Offline performance of ADMGA and EIGA. ADMGA

with 𝑝𝑚 = 1𝑙 and EIGA with 𝑝𝑚 = 2𝑙 ................................................................................. 142

Figure 6.1: The Gutenberg-Richter law. The magnitude of the earthquakes and their frequency

show a power-law proportion. Taken from (Bak, 1996). ........................................................ 149

Figure 6.2: The Bak-Sneppen model. .............................................................................................. 154

Figure 6.3: A section of a sand pile attached to a population: genes 𝑙1, 𝑙2, 𝑙3 from chromosomes

𝑛1, 𝑛2, 𝑛3 . The height of the cell (𝑙2, 𝑛2) is 𝑧(𝑙2, 𝑛2) = 3. If one grain is dropped in that

site, an avalanche may occur. Then, four grains will topple to the cell’s von Neumann

neighbourhood and (𝑙2, 𝑛3) will also reach critical 𝑧 value. If conditions are favourable,

avalanche and mutations may proceed. ................................................................................. 160

Figure 6.4: The pseudo-code of the sand pile mutation as proposed by Fernandes et al. (2008a).

................................................................................................................................................. 161

Figure 6.5: Order-4 dynamic trap functions. GGASM (1) and EIGA offline performance on each

dynamic scenario. Population size: 𝑛 = 60. Uniform crossover with 𝑝𝑐 = 1.0. Tournament

selection. GGASM (1) with 𝑔𝑟 = (𝑛 × 𝑙)4 if 𝜀 = 2,400 and 𝑔𝑟 = (𝑛 × 𝑙)16 otherwise. EIGA

with 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise. .......................................................... 164

Figure 6.6: The pseudo-code of the sand pile mutation (enhanced version). The main differences

are in the initialization procedure and in the normalized fitness. .......................................... 165

Figure 7.1: Comparing GGA and GGASM offline performance on Royal Road with 𝜀 = 24,000.

Population size: 𝑛 = 120. GGA: 𝑝 𝑚 = 1𝑙. GGASM: 𝑔𝑟 = 10 × 𝑙. ...................................... 174

Figure 7.2: Royal Road. GGASM mutation rate variation with 𝜀 = 1,200. Mutation rate is measured

every generation by comparing all the alleles in the population before and after 𝑔𝑟 grains are

dropped on sand pile............................................................................................................... 175

Figure 7.3: Order-3 dynamic problems: GGASM (1) and GGASM (2) performance with different

𝑔𝑟 and population size: 𝑛 = 30. ........................................................................................... 177

Figure 7.4: Order-3 dynamic trap problems. GGASM (1) and GGASM (2) offline performance.

Population size: 𝑛 = 30. GGASM (1): 𝑔𝑟 = (𝑛 × 𝑙)4 if 𝜀 = 2,400 and 𝑔𝑟 = (𝑛 × 𝑙)16

otherwise. GGASM (2): 𝑔𝑟 = (𝑛 × 𝑙)16 if 𝜀 = 2,400 and 𝑔𝑟 = (𝑛 × 𝑙)32 otherwise. ...... 178

xvii

Figure 7.5: Order-4 dynamic trap problems: GGASM (1) and GGASM (2) offline performance on

twelve scenarios. Population size: 𝑛 = 60. GGASM (1): 𝑔𝑟 = (𝑛 × 𝑙)4 if 𝜀 = 2,400 and

𝑔𝑟 = (𝑛 × 𝑙)16 otherwise. GGSM (2): 𝑔𝑟 = (𝑛 × 𝑙)8 if 𝜀 = 2,400 and 𝑔𝑟 = (𝑛 × 𝑙)32

otherwise. ................................................................................................................................ 178

Figure 7.6: Order-3 dynamic trap problems: GGASM (2), EIGA and SORIGA offline performance.

Population size: n = 30. GGASM (2): 𝑔𝑟 = (𝑛 × 𝑙)16 when 𝜀 = 2,400 and 𝑔𝑟 = (𝑛 × 𝑙)32

otherwise. EIGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise. SORIGA: 𝑝𝑚 = 1(8 × 𝑙)

................................................................................................................................................. 179

Figure 7.7: Order-4 dynamic trap problems: GGASM (2), EIGA and SORIGA offline performance.

Population size: 𝑛 = 60. GGASM (2): 𝑔𝑟 = (𝑛 × 𝑙)8 if 𝜀 = 2,400 and 𝑔𝑟 = (𝑛 × 𝑙)32

otherwise. EIGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise. SORIGA: 𝑝𝑚 = 1(16 × 𝑙)

if 𝜀 = 2,400 and 𝑝𝑚 = 1(4 × 𝑙) otherwise. ........................................................................ 180

Figure 7.8: Order-4 dynamic problem. GGASM (2) and EIGA online performance on the order-4

scenario with 𝜀 = 48,000 and 𝜌 = 0.95. Population size: 𝑛 = 60. GGASM (2) with 𝑔𝑟 =

(𝑛 × 𝑙)32. EIGA with 𝑝𝑚 = 2𝑙. Parameters as in Figure 7.7. .............................................. 182

Figure 7.9: Order-3 dynamic trap functions. GGA and GGASM (2) offline performance with different

𝑝𝑚 and 𝑔𝑟 values. Population size: 𝑛 = 30. ......................................................................... 184

Figure 7.10: Grain rates plotted against the resulting offline mutation rates. ............................... 187

Figure 7.11: Order-4 dynamic trap problems. GGASM (2) online mutation rate. Population size:

𝑛 = 60. Grain rate: 𝑔𝑟 = (𝑛 × 𝑙)32. ε = 2,400. .............................................................. 190

Figure 7.12: Order-4 dynamic trap problems. GGASM (2) online mutation rate. Population size:

𝑛 = 60. Grain rate: 𝑔𝑟 = (𝑛 × 𝑙)32. ε = 24,000. ............................................................ 191

Figure 7.13: Order-4 dynamic problems. Logarithm of the mutation rates abundance plotted

against their values. ................................................................................................................ 193

Figure 7.14: Order-4 dynamic trap problems. GGASM (2) online mutation rate. Population size:

𝑛 = 60. Grain rate: 𝑔𝑟 = (𝑛 × 𝑙)32. Speed of change ε = 2,400 (top), speed of change:

ε = 24,000 (bottom, only the mutation rates of the first 400 generations are plotted). .... 194

Figure 8.1: Order-3 dynamic trap problems: GGASM, ADMGA and ADMGASM offline performance.

Population size: 𝑛 = 30. GGSM (2) : 𝑔𝑟 = (𝑛 × 𝑙)16 if 𝜀 = 2,400 and 𝑔𝑟 = (𝑛 × 𝑙)32

xviii

otherwise. ADMGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise. ADMGASM: 𝑔𝑟 = (𝑛 ×

𝑙)2 for every 𝜀. ........................................................................................................................ 198

Figure 8.2: Order-4 dynamic trap problems: GGASM (2), ADMGA and ADMGASM offline

performance. Population size: 𝑛 = 60. GGSM (2): 𝑔𝑟 = (𝑛 × 𝑙)8 if 𝜀 = 2,400 and

𝑔𝑟 = (𝑛 × 𝑙)32 otherwise. ADMGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise.

ADMGASM: 𝑔𝑟 = (𝑛 × 𝑙)4 for every 𝜀. ................................................................................... 199

Figure 8.3: Dynamic royal road 𝑅1. GGASM (2), ADMGA, GGA and EIGA offline performance.

Population size: 𝑛 = 60. ADMGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise. GGA:

𝑝𝑚 = 1𝑙. EIGA: 𝑝𝑚 = 2𝑙. GGASM (2): 𝑔𝑟 = (𝑛 × 𝑙)32. ...................................................... 201

Figure 8.4: Dynamic royal road R1 problems. ADMGA, ADMGASM and GGASM (2) offline

performance. Population size: 𝑛 = 60. ADMGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙

otherwise. ADMGASM: 𝑔𝑟 = (𝑛 × 𝑙)16 if 𝜀 = 2,400 and 𝑔𝑟 = (𝑛 × 𝑙)8 otherwise. GGASM

(2): 𝑔𝑟 = (𝑛 × 𝑙)32 for every 𝜀 value. .................................................................................. 201

Figure 8.5: Knapsack dynamic problems. ADMGA, EIGA and GGASM (2) offline performance.

ADMGA: 𝑝𝑚 = 1𝑙. EIGA: 𝑝𝑚 = 2𝑙. GGASM: 𝑔𝑟 = (𝑛 × 𝑙)2. ................................................ 203

Figure 8.6: Knapsack dynamic problems. ADMGA, EIGA and ADMGASM offline performance.

ADMGA: 𝑝𝑚 = 1𝑙. EIGA: 𝑝𝑚 = 2𝑙. ADMGASM: 𝑔𝑟 = (𝑛 × 𝑙)2. .......................................... 204

xix

List of Tables

Table 4.1: Knapsack problem data. 100 items (randomly generated) with strongly correlated sets

of randomly generated data. .................................................................................................... 73

Table 4.2: Functions 𝑓1, 𝑓2 and 𝑓3. Best results attained by each algorithm. The results are

averaged over 100 runs. All configurations attained 100% success rates. .............................. 78

Table 4.3: Comparing the performance of the algorithms using paired two tailed t-tests with 198

degrees of freedom at a 0.05 level of significance. Symbol ≈ means that the algorithms are

statistically equivalent, that is, the null hypothesis — the datasets from which the offline

performance and the standard deviation are calculated are drawn from the same distribution

— is not rejected. Parameters as in table 4.2. .......................................................................... 79

Table 4.4: Function 𝑓4. Best success rates and corresponding AES values for several 𝑝𝑚 values.

Parameters: GGA: 𝑛 = 60; 𝑝𝑐 = 0.9; nAMGA: 𝑛 = 30; 𝑝𝑐 = 0.9: pAMGA: 𝑛 = 60;

𝑝𝑐 = 1.0; ADMGA: 𝑛 = 360. ................................................................................................. 81

Table 4.5: Function 𝑓4. CHC success rates and corresponding AES. ................................................. 84

Table 4.6: Knapsack problem. Best configurations. Final MBF values (averaged over 100 runs) after

100,000 evaluations. Percentage of runs (%) in which the solution with fitness 1853 is

attained. .................................................................................................................................... 84

Table 4.7: Royal road R1. Best configurations. All configurations attained 100% success rates. .... 86

Table 4.8: Royal road modified R4. Optimal population size, success rate, and number of

evaluations to reach a solution averaged over 100 runs (plus standard deviation). ............... 88

Table 4.9: ADMGA threshold values after the first generation (𝑡 = 1). Parameter values and

recombination operators as in the best configurations found in previous sections. ............... 97

Table 4.10 ADMGA, SAMGA and SAMXPGA results on four different functions. SR measures the

number of runs in which the global optimum is attained. ...................................................... 104

Table 5.1: Order-3 trap functions (𝑘 = 3, 𝑚 = 10). Offline performance. Population size 𝑛 =

30. ADMGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2400 and 𝑝𝑚 = 2𝑙 otherwise. GGA: 𝑝𝑚 = 1𝑙 for every 𝜀.

SSGA: 𝑝𝑚 = 2𝑙 for every 𝜀. .................................................................................................... 114

xx

Table 5.2: Order-4 trap problems (𝑘 = 4, 𝑚 = 10). Offline performance of the best

configuration of each GA. Population size: 𝑛 = 30. ADMGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and

𝑝𝑚 = 2𝑙 otherwise. GGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 or 𝜀 = 48,000 and 𝑝𝑚 = 2𝑙 if

𝜀 = 24,000. SSGA: 𝑝𝑚 = 2𝑙 if 𝜀 = 2,400 or 𝜀 = 24,000 and 𝑝𝑚 = 4𝑙 if 𝜀 = 48,000.

................................................................................................................................................. 117

Table 5.3: Order-4 trap problems (𝑘 = 4, 𝑚 = 10). Offline performance of the best

configuration of each GA. Population size: 𝑛 = 60. ADMGA: 𝑝𝑚 = 1(2 × 𝑙) if 𝜀 = 2,400

and pm = 2𝑙 otherwise. GGA: 𝑝𝑚 = 1𝑙 for every ε. SSGA: 𝑝𝑚 = 2𝑙 for every 𝜀. SSGA:

𝑝𝑚 = 2𝑙 if 𝜀 = 2,400 or 𝜀 = 2,400 and 𝑝𝑚 = 4𝑙 if 𝜀 = 48,000. ................................. 117

Table 5.4: Statistical comparison by paired two-tailed t-tests with 58 degrees of freedom at a 0.05

level of significance. The null hypothesis states that the datasets from which the offline

performance and the standard deviation are calculated are drawn from the same distribution.

The test result is shown as + sign when ADMGA is significantly better than GGA or SSGA, −

sign when ADMGA is significantly worst, and ≈ sign when the algorithms are statistically

equivalent (i.e, the null hypothesis is not rejected). Parameters as in Table 5.1 and Table 5.2.

................................................................................................................................................. 118

Table 5.5: Order-4 trap problems (𝑘 = 4, 𝑚 = 10). Mean best-of-generation values attained by

the best configuration of each algorithm. Population size 𝑛 = 30. ADMGA: 𝑝 𝑚 = 1𝑙 if

𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise. GGA: 𝑝𝑚 = 1𝑙 for every 𝜀. SORIGA: 𝑝𝑚 = 1(16 × 𝑙)

if 𝜀 = 2,400 and 𝑝𝑚 = 1(4 × 𝑙) otherwise. EIGA: 𝑝 𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝 𝑚 = 2𝑙

otherwise. ................................................................................................................................ 125

Table 5.6: Order-3 and order-4 dynamic problems (𝑚 = 10). Statistical comparison of algorithms

by paired two-tailed 𝑡-tests with 58 degrees of freedom at a 0.05 level significance.

Population size: 𝑛 = 30. The 𝑡-test results are shown as + signs when ADMGA is significantly

better, − signs when ADMGA is significantly worst, and ≈ signs when the algorithms are

statistically equivalent. Parameters as in Table 5.5. ............................................................... 126

Table 5.7: Order-4 trap problems (𝑘 = 4, 𝑚 = 10). Offline performance. Population size 𝑛 =

30. ADMGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2400 and 𝑝𝑚 = 2𝑙 otherwise. HM 1 (𝑝𝑚 = 0.5) and HM 2

(𝑝𝑚 = 0.3) with 𝑝𝑚 = 1𝑙 for every 𝜀. ............................................................................... 128

xxi

Table 5.8: Statistical comparison of algorithms by paired two-tailed t-tests with 58 degrees of

freedom at a 0.05 level significance. The t-test result is shown as + sign when ADMGA is

significantly better than HM 1 or HM 2, − sign when is significantly worst, and ≈ sign when the

algorithms are statistically equivalent. Population size: 𝑛 = 30. ADMGA: 𝑝𝑚 = 1𝑙 if

𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise. HM 1: 𝑝𝑚 = 1𝑙 and 𝑝𝑚 = 0.5. HM 2: 𝑝𝑚 = 1𝑙 and

𝑝𝑚 = 0.3. ............................................................................................................................. 128

Table 5.9: Order-3 (𝑘 = 3) and order-4 (𝑘 = 4) dynamic trap problems (𝑚 = 10). Statistical

comparison by paired two-tailed t-tests with 58 degrees of freedom at a 0.05 level

significance. The 𝑡-test results are shown as + sign when ADMGA is significantly better, − sign

when ADMGA is significantly worst, and ≈ sign when the algorithms are statistically

equivalent. ADMGA: 𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise. nAMGGA: 𝑝𝑚 = 1𝑙 if

𝑛 = 2, 𝑝𝑚 = 1(2 × 𝑙) if 𝑛 = 4 and 𝑝𝑚 = 1(4 × 𝑙) if 𝑛 = 8. ........................................ 132

Table 5.10: Order-5 dynamic trap problems (𝑘 = 5, 𝑚 = 10). Statistical t-tests. The ≈ sign means

that the algorithms are statistically equivalent. ADMGA with 𝑝𝑚 = 2𝑙. nAMGGA (𝑛 = 4)

with pm = 1(8 × 𝑙). Parameters as in Figure 5.18. .................................................................. 135

Table 5.11: Royal road R1 dynamic problems. Offline performance. Parameters as in Figure 5.19

and Figure 5.20. ....................................................................................................................... 137

Table 5.12: Royal road R1 dynamic problems. Statistical comparison of algorithms by paired two-

tailed t-tests with 58 degrees of freedom at a 0.05 level significance. The t-test result

regarding ADMGA and other GAs is shown as + sign when ADMGA is significantly better, −

sign when ADMGA is significantly worst, and ≈ sign when the algorithms are statistically

equivalent. Parameters as in Figure 5.19 and Figure 5.20. ..................................................... 138

Table 5.13: Royal road R1 dynamic problems. Offline performance. Population size n = 30. ADMGA:

𝑝𝑚 = 1𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 2𝑙 otherwise.; nAMGA with 𝑝 𝑚 = 1(2 × 𝑙) and 𝑝 = 4.

................................................................................................................................................. 139

Table 5.14: Royal road modified 𝑅4 dynamic problems. Mean best-of-generation values attained

by the best configuration of ADMGA and nAMGA (𝑛 = 4). The last row shows the best

algorithms in each scenario (after t-tests). The ≈ symbol means that the results are

statistically equivalent. ADMGA: 𝑝𝑚 = 2𝑙; nAMGA: 𝑝𝑚 = 1(2 × 𝑙) ................................... 139

xxii

Table 5.15: Royal road modified R4 dynamic problems. Offline performance of ADMGA and

Hypermutation (HM). ADMGA: 𝑝𝑚 = 2𝑙; Hypermutation: 𝑝𝑚 = 1𝑙 and 𝑝𝑚 = 0.5 ....... 141

Table 5.16: Dynamic 0-1 knapsack problem. Offline performance of the best configuration of each

GA. ADMGA with 𝑝𝑚 = 1𝑙. GGA: 𝑝𝑚 = 2𝑙 if 𝜀 = 2,400 and 𝑝𝑚 = 1𝑙 otherwise. nAMGA

(𝑝 = 4): 𝑝𝑚 = 1(2 × 𝑙) if 𝜀 = 2,400 and 𝑝𝑚 = 1(4 × 𝑙) otherwise. EIGA: 𝑝𝑚 = 2𝑙. .. 141

Table 7.1: Royal Road R1 dynamic problems. Population size: 𝑛 = 120. 2-point crossover.

Crossover probability: 𝑝𝑐 = 0.7. Tournament selection (𝑘𝑡𝑠 = 0.9). GGASM: 𝑔𝑟 = 10 × 𝑙.

RIGA 1: 𝑝𝑚 = 1𝑙; 𝑟𝑟 = 3. RIGA 1: 𝑝𝑚 = 1𝑙; 𝑟𝑟 = 12. GGA: 𝑝𝑚 = 1𝑙. ............................. 172

Table 7.2: Deceptive 1 dynamic problems. Population size: 𝑛 = 120. 2-point crossover. Crossover

probability: 𝑝𝑐 = 0.7. Tournament selection (𝑘𝑡𝑠 = 0.9). GGASM: 𝑔𝑟 = 50 × 𝑙. RIGA 1:

𝑝𝑚 = 1𝑙; 𝑟𝑟 = 3. RIGA 1: 𝑝𝑚 = 1𝑙; 𝑟𝑟 = 12. GGA: 𝑝𝑚 = 1𝑙. ......................................... 172

Table 7.3: Deceptive 2 dynamic problems. Population size: 𝑛 = 120. 2-point crossover. Crossover

probability: 𝑝𝑐 = 0.7. Tournament selection (𝑘𝑡𝑠 = 0.9). GGASM: 𝑔𝑟 = 50 × 𝑙. RIGA 1:

𝑝𝑚 = 1𝑙; 𝑟𝑟 = 3. RIGA 1: 𝑝𝑚 = 1𝑙; 𝑟𝑟 = 12. GGA: 𝑝𝑚 = 1𝑙. ......................................... 172

Table 7.4: Royal Road R1 dynamic problems. Statistical comparison of algorithms by paired two-

tailed t-tests with 58 degrees of freedom at a 0.05 level of significance. The t-test result is

shown as + sign when ADMGA is significantly better than GGA or SSGA, − sign when ADMGA

is significantly worst, and ≈ sign when the algorithms are statistically equivalent. Parameter

settings as in Table 7.1. ........................................................................................................... 173

Table 7.5: Deceptive 1 dynamic problems. Statistical comparison of algorithms by paired two-

tailed t-tests with 58 degrees of freedom at a 0.05 level of significance. Parameter settings as

in Table 7.2. ............................................................................................................................. 173

Table 7.6: Deceptive 2 dynamic problems. Statistical comparison of algorithms by paired two-

tailed t-tests with 58 degrees of freedom at a 0.05 level of significance Parameter settings as

in Table 7.3. ............................................................................................................................. 173

Table 7.7: Comparing GGASM and SORIGA. Population size: 𝑛 = 120. 𝑝𝑚 = 0.01; 𝑝𝑐 = 0.7;

SORIGA: 𝑟𝑟 = 3; GGASM: 𝑔𝑟 = 10 × 𝑙 (Royal Road) and 𝑔𝑟 = 50 × 𝑙 (Deceptive 1 and 2).176

Table 7.8: Order-3 trap problems (𝑘 = 3, 𝑚 = 10). GGASM (2), GGA, SORIGA and EIGA offline

performance. Population size: 𝑛 = 30. Parameters as in Figure 7.6 (and GGA with 𝑝𝑚 = 1𝑙).

................................................................................................................................................. 180

xxiii

Table 7.9: Order-4 trap problems (𝑘 = 4, 𝑚 = 10). GGASM (2), GGA, SORIGA and EIGA offline

performance. Population size: 𝑛 = 30. Parameters as in Figure 7.7 (and GGA with 𝑝𝑚 = 1𝑙).

................................................................................................................................................. 181

Table 7.10: Order-3 and order-4 dynamic problems (𝑚 = 10). Statistical comparison of

algorithms by paired two-tailed t-tests with 58 degrees of freedom at a 0.05 level

significance. The t-test results are shown as + signs when GGASM (2) is significantly better, −

signs when GGASM (2) is significantly worst, and ≈ signs when the algorithms are statistically

equivalent. Parameters as in Figure 7.6 and Figure 7.7. ......................................................... 181

Table 7.11: Optimal GGASM (2) grain rates for each type of problem and type of scenario (𝑛 is the

population size and 𝑙 is the chromosome length). .................................................................. 183

Table 7.12: Equation 7.1 and equation 7.2 computed for each problem and type of scenario. .... 185

Table 7.13: Order-4 dynamic trap problems. Offline mutation rate............................................... 186

Table 7.14: Knapsack dynamic problems. Offline mutation rate. ................................................... 187

Table 7.15: Mutation rate median values (averaged over 30 independent runs). ......................... 189

Table 8.1: Order-3 and order-4 trap problems (𝑚 = 10). ADMGA, GGASM (2) and ADMGASM offline

performance. Population size: 𝑛 = 30. Parameters as in Figure 8.2. ................................... 200

Table 8.2: Order-3 and order-4 dynamic problems (𝑚 = 10). Population size: 𝑛 = 30 (order-3)

and 𝑛 = 60 (order-4). Statistical comparison of algorithms by paired two-tailed t-tests with

58 degrees of freedom at a 0.05 level significance. The t-test results regarding are shown as +

signs when ADMGASM is significantly better, − signs when is significantly worst, and ≈ signs

when the algorithms are statistically equivalent. Parameters as in Figure 8.1 and Figure 8.2.

................................................................................................................................................. 200

Table 8.3: Royal road R1 dynamic problems. Numerical results. Parameters as in Figure 8.3

(SORIGA with 𝑝𝑚 = 1(8 × 𝑙))................................................................................................ 202

Table 8.4: Royal road R1 dynamic problems. Population size 𝑛 = 60. Statistical comparison of the

GGASM (2) by paired two-tailed t-tests with 58 degrees of freedom at a 0.05 level

significance. The t-test results are shown as + signs when GGASM is significantly better, − signs

when GGASM is significantly worst, and ≈ signs when the algorithms are statistically

equivalent. Parameters as in Figure 8.3 (SORIGA with 𝑝𝑚 = 1(8 × 𝑙)). ............................... 202

xxiv

Table 8.5: Royal road R1 dynamic problems. Population size 𝑛 = 60. Statistical comparison of

ADMGASM, ADMGA and GGASM (2) by paired two-tailed t-tests with 58 degrees of freedom at

a 0.05 level significance. The t-test results are shown as + signs when ADMGASM is

significantly better, − signs when ADMGASM is significantly worst, and ≈ signs when the

algorithms are statistically equivalent. Parameters as in Figure 8.4....................................... 203

Table 8.5: Order-3 dynamic trap functions (𝑘 = 3; 𝑚 = 10). Population size: 𝑛 = 30. The t-test

results are shown as + signs when Alg(orithm) 1 is significantly better than Alg(orithm) 2, −

signs when algorithm 1 is significantly worst, and ≈ signs when the algorithms are statistically

equivalent. ............................................................................................................................... 206

Table 8.6: Order-4 dynamic trap functions (𝑘 = 4; 𝑚 = 10). Population size: 𝑛 = 60. The t-test

results are shown as + signs when algorithm 1 is significantly better than algorithm 2, − signs

when algorithm 1 is significantly worst, and ≈ signs when the algorithms are statistically

equivalent. ............................................................................................................................... 207

Table 8.7: Order-4 dynamic trap functions (𝑘 = 4; 𝑚 = 10). Population size: 𝑛 = 60. Statistical

tests. The t-test results are shown as + signs when algorithm 1 is significantly better than

algorithm 2, − signs when algorithm 1 is significantly worst, and ≈ signs when the algorithms

are statistically equivalent....................................................................................................... 209

Table 8.8: Order-4 dynamic trap functions (𝑘 = 4; 𝑚 = 10). Population size: 𝑛 = 60. Statistical

tests. The t-test results are shown as + signs when algorithm 1 is significantly better than

algorithm 2, − signs when algorithm 1 is significantly worst, and ≈ signs when the algorithms

are statistically equivalent....................................................................................................... 210

Table 8.9: Order-4 dynamic trap functions (𝑘 = 4; 𝑚 = 10). Population size: 𝑛 = 60. Results of

the t-tests comparing the performance of EIGA and GGA. The t-test results are shown as +

signs when algorithm 1 is significantly better than algorithm 2, − signs when algorithm 1 is

significantly worst, and ≈ signs when the algorithms are statistically equivalent. ................. 211

xxv

List of Abbreviations

ACO: Ant Colony Optimization

ADMGA: Adaptive Dissortative Mating Genetic Algorithm

ADMGASM: Adaptive Dissortative Mating Genetic Algorithm with sand pile mutation

AMGA: Assortative Mating Genetic Algorithm

ECGA: Extended Compact Genetic Algorithm

EDA: Estimation of Distribution Algorithm

EIGA: Elitism-based Immigrants Genetic Algorithm

GA: Genetic Algorithm

GASM: Genetic Algorithm with sand pile mutation

GGA: Generational Genetic Algorithm

GGASM: Generational Genetic Algorithm with sand pile mutation

nAMGA: negative Assortative Mating Genetic Algorithm

pAMGA: positive Assortative Mating Genetic Algorithm

PBIL: Population Based Incremental Learning

PSO: Particle Swarm Optimization

RIGA: Random Immigrants Genetic Algorithm

SOC: Self-Organized Criticality

SORIGA: Self-Organized Random Immigrants Genetic Algorithm

SRP-EA: Self-Regulated Population size Evolutionary Algorithm

SSGA: Steady-State Genetic Algorithm

UMDA: Univariate Marginal Distribution Algorithm

xxvi

xxvii

Sisyphus was condemned by the gods to forever roll a huge

stone up a mountain, only to see it fall back to the bottom

each time he reached the summit.

Samuel Florman, in The Existential Pleasures of Engineering

xxviii

1

Chapter 1

Introduction

1.1 Objectives

In recent years, dynamic optimization — i.e., optimization of non-stationary

functions — became one of the major themes of research on Evolutionary Computation

(Holland, 1975; Goldberg, 1989a; Bäck, 1996). Since dynamic components are, along

with non-linear constraints and multiple objectives, one of the properties that frequently

appear in real-world problems, and because for a long time Evolutionary Computation

has entered the realm of industrial applications — namely, due to its efficiency on non-

linearity and multiobjectives —, it was expected that, sooner or later, this field would

raise a growing interest amongst the community. The interest in the subject, though, is

not recent, and many studies have been published since the beginning of the

investigations on evolutionary systems for optimization purposes, in the 1960s. In fact,

and as referred by Jin and Branke1 in their survey on evolutionary optimization in

uncertain environments (Jin & Branke, 2005), the earliest application of Evolutionary

Computation to dynamic environments dates back to 1966, and its description appears

in the seminal book by Fogel2, Owens and Walsh, Artificial Intelligence through

Simulated Evolution (Fogel et al. 1966).

1 Jurgen Branke is one of the most prominent researchers in evolutionary optimization, author and co-author of many

papers on the subject, which will be addressed throughout this thesis. He published the book Evolutionary

Optimization in Dynamic Environments (Branke, 2002) in 2002, after his homonymous thesis in 2000 (Branke,

2000). 2 Lawrence Fogel (1928-2007) was one of Evolutionary Computation’s founding fathers, and the author of the first

dissertation in the field (Fogel, 1964).

2

However, this line of investigation only fully started after Goldberg and Smith’s

paper (Goldberg & Smith, 1987) on diploid Genetic Algorithms (GAs) (Goldberg,

1989a) for dynamic optimization problems, published, in 1987. A few years later, two

important and widely cited papers were published, one by Cobb, proposing the well-

known Hypermutation scheme (Cobb, 1990) and another one by Grefenstette,

proposing the Random Immigrants Genetic Algorithm (Grefenstette, 1992). In a way,

each one of these approaches is a kind of main paradigm of two of the four categories

defined by Branke to classify evolutionary techniques for dynamic optimization

(Branke, 1999): reaction to changes (hypermutation), diversity maintenance (random

immigrants), memory schemes and multi-population approaches — see Chapter 2 for a

detailed description of Jin and Branke’s categories and of some of the previously

proposed Evolutionary Algorithms for dynamic optimization. Since Cobb and

Grefenstette’s papers, and especially after Branke’s research on this issue, the

investigations on Evolutionary Algorithms for dynamic optimization attracted a vast

number of scientists and the publications on the subject experienced a consistent

growth, on both international journals and peer-reviewed conference proceedings3.

Nowadays, these increasing research efforts are being mainly directed towards

diversity maintenance and memory schemes. This is probably because many multi-

population schemes may be classified within one of the remaining categories (and some

of them are really hard to distinguish from memory schemes), and because evolutionary

schemes that react to changes can only be applied when it is easy to detect those same

changes — and, in addition, their efficiency is strongly dependent on the intensity of

the changes. Moreover, ―pure‖ multi-population schemes usually require complex

updating and migration strategies that makes it difficult to tune and implement the

algorithms.

On the other hand, diversity maintenance techniques — which in general do not

require any knowledge about the problem and its dynamics —, may slow down the

3 For instance, in 2005, the Journal of Soft Computing released a special issue on dynamic optimization, and, in

2006, IEEE published a Transactions on Evolutionary Computation special issue on Evolutionary Computation in

the presence of uncertainty.

3

convergence of the algorithm during the stationary periods, a characteristic that may

harm the performance when the consecutive changes in the fitness function are

separated by short periods of time. Finally, memory schemes may be very effective, but

their utility is believed to be restricted to a certain type of dynamics.

Each type of strategy has its advantages and drawbacks. However, diversity

maintenance algorithms, due to the fact that they usually do not (necessarily) rely on a

complex parameter setting and neither on any particular knowledge about the function

and the dynamics, may be regarded as the most robust evolutionary approach to

dynamic optimization (even though other strategies may be better when tackling

dynamic problems from which some information is available). For these reasons, the

conclusions about the algorithms’ spectrum of application are more reliable when

investigating Evolutionary Algorithms that act upon diversity in order to tackle

dynamic problems, since they are not designed to match any particular characteristic of

those problems.

This thesis is focused on this type of approaches and argues that it is possible — by

searching for inspiration in natural systems — to develop new techniques and improve

not only standard GAs on dynamic optimization problems, but also other diversity

maintenance strategies that are being proposed by the scientific community. In addition

(and this is an important issue), it is possible to build those schemes by relying on a

self-adjustable behaviour, without increasing the algorithms’ complexity — it is hard to

evaluate the pay-off of using a novel technique if the parameter space grows or if it

narrows the region of the parameter space in which the algorithm performs well.

Finally, it is hoped that this work also sheds some light on the behaviour of traditional

GAs on dynamic environments, namely on how their performance reacts to different

parameter settings. It is shown, for instance, that standard GAs may work better than it

is believed, when compared to state-of-the-art proposals, if the parameters are properly

tuned. Moreover, two of the typical Evolutionary Algorithms’ parameters —

population size and mutation probability — are shown to deeply affect the algorithms’

performance. Only after understanding the full extent of Evolutionary Algorithms’

4

efficiency on dynamic environments, it is possible to design alternative schemes that

can improve their performance on a significant number of problems and dynamics.

The thesis restricts the investigation to GAs4 —although some features of the

proposed schemes are easily extended to other Evolutionary Algorithms (Bäck, 1996)

— and proposes two bio-inspired techniques that enhance their performance on a wide

range of problems, and a hybrid scheme that mixes both strategies and further enhances

the performance. As stated above, the research has been mainly focused on diversity

maintenance techniques, due to their broader scope of applications and because these

schemes are closer to the definition of ―black-box dynamic optimization5‖. The

fundamental challenge is to deal with changing environments without information

regarding the changes — although it is assumed that the number of environments or the

period between changes do vary unboundedly, otherwise no other method outperforms

random restarts of the Evolutionary Algorithm’s population after a change and the

whole objective of this thesis would be incompatible with the no-free-lunch theorem

for optimization (Wolpert & McReady, 1997). That is, while some approaches are

based on increasing population’s diversity after a change, this thesis focus on

maintaining diversity throughout the run — either by avoiding diversity loss, or by

introducing large amounts of genetic novelty in the population from time to time —,

removing the need to predict the changes and their severity. In addition, the thesis’s

proposals do not rely on memory schemes, and thus are expected to maintain a stable

behaviour in a wider spectrum of dynamics than memory-based GAs. (On the other

hand, by relying on ―blind‖ diversity maintenance strategies, it is expected that the

proposed algorithms experience some difficulties in dynamic optimization scenarios

where changes appear fast. This hypothesis is confirmed by the experiments.)

For that purpose, the research has looked for inspiration on natural phenomena, like

sexual reproduction strategies (see Chapter 3) and Self-Organized Criticality (Chapter

6), resulting in two distinct techniques that act upon mating — the Adaptive

4 In fact, the experiments were only conducted on Genetic Algorithms with binary codifications, but the extension to

other types of codification is trivial. 5 Black-box optimization algorithms need little or no information about a problem to solve it.

5

Dissortative Mating Genetic Algorithm (ADMGA) — and mutation — Genetic

Algorithm with sand pile mutation (GASM).

ADMGA main feature is a selection and recombination scheme that avoids crossover

between similar individuals, leading to a slower decrease of the genetic diversity. This

way, diversity is maintained at a higher level. Unlike the Random Immigrants GA —

the main paradigm of diversity maintenance strategies — the proposed method works

by avoiding diversity loss, rather than introducing novelty in each iteration of the

algorithm.

The sand pile mutation replaces traditional mutation by an operator that is able to

introduce large amounts of genetic novelty in the population, in an undeterministic

manner. This behaviour is achieved by incorporating, in a traditional GA, a model that

is known to display a power-law proportion between the size of an event and its

frequency. Like random immigrants schemes, GASM deals with changing environments

by trying to supply the population with novel genetic material in a regular basis,

although not cyclic or predictable. However, and unlike Random Immigrants, this

proposal achieves that by spreading the new genes throughout the population, instead

of introducing new randomly generated elements in that same population.

To evaluate the efficiency of the proposed methods, the algorithms are tested in a

wide range of problems and dynamics (including trap deceptive functions, a class of

problems for which there are several experimental and theoretical studies, and which in

nowadays are the core of many studies on Evolutionary Computation), and compared to

other evolutionary techniques, including standard GAs and some classical methods for

dynamic optimization. In addition, the proposals are compared with two recently

proposed GAs for non-stationary function optimization: Elitism-based Immigrants GA

(EIGA) (Yang, 2008) and Self-Organized Random Immigrants GA (SORIGA) (Tinós

and Yang, 2007).

There is a huge amount of Evolutionary Algorithms specifically designed for

dynamic optimization, some with just minor changes when compared to standard

evolutionary approaches, and others that model rather complex strategies. It is not

possible to evaluate a new proposal against all these algorithms, and, in fact, it is not

6

expected that any method outperforms all the others, especially in wide range of

problems. What is important here is to try to identify in which conditions a proposed

scheme may improve traditional GAs’ performance, and then confirm that assumption

with a proper experimental setup and check if the proposal is able to excel where other

algorithms are not.

SORIGA and EIGA appear in the test set for several reasons. First, they were selected

because they were published very recently — SORIGA in 2007 (Tinós & Yang, 2007)

and EIGA in 2008 (Yang, 2008) — in reputed international journals. SORIGA, in

particular, was chosen also because it is the approach closer to the sand pile mutation

and in (Tinós, 2007) it is stated that the algorithm is able to outperform other GAs on

several test problems. EIGA was selected because it is a very simple scheme, it does

not rely on complicated strategies, it only adds one parameter to the standard parameter

set (as it will be shown in the following chapter, the proposals of this thesis do not

increase the size of the parameter set) and the report (Yang, 2008) claims that EIGA is

able to outperform several other algorithms on dynamic problems. For all these

reasons, those two algorithms appear to be suited to accompany other strategies on the

extensive test set prepared for this work.

In the end, and after an intensive experimental study that explores all the

potentialities of traditional GAs, Random Immigrants GAs, Hypermutation schemes,

SORIGA and EIGA, it will be shown that the proposed algorithms are able to

outperform all other methods on a wide range of problems and dynamics, namely when

the changes are not very fast. In addition, SORIGA and EIGA will be shown to fail

when the test set examines a large amount of configurations, by setting the algorithms

parameter to different values. In particular, it will be shown how important mutation

rate and population size are for the behaviour of the algorithms. Population size, in

particular, is often neglected on many investigations on Evolutionary Algorithms and

dynamic optimization. This work stresses out the importance of having a population

size properly tuned, in order to avoid comparing suboptimal configurations of the

algorithms, and thus misleading the conclusions about the efficiency of the proposed

methods.

7

The following section summarizes the contributions of this thesis, by briefly

describing the research process that lead to ADMGA and GGASM, and indicating the

peer-reviewed conference proceedings and international journals in which each step of

the investigations has been published.

1.2 Contributions

This thesis describes two strategies conceived to deal with non-stationary functions.

However, these investigations are only a part of a larger body-of-work, which studied

the behaviour of several algorithms on dynamic environments. Although they are not

described in the text, some parts of this research were crucial for the thesis, since they

inspired many ideas behind the proposed algorithms.

The first investigations and publications related with the complete body-of-work have

been focused on an Artificial Life model, proposed by Chialvo and Milonas (1995),

which simulates the stigmergic behaviour of a particular species of ants on a

homogenous habitat. Ramos and Almeida (2005) later extended Chialvo and Milonas’s

model in order to evolve it on digital image habitats and showed how the artificial

swarm can evolve, from local interactions, a complex global behaviour that allowed

them to ―recognize‖ the digital image, and even to react to changing images (that is, if

one replaces one image by another one, the swarm is able to readapt itself to the new

environment). However, due to an important characteristic of stigmergic systems —

memory — the model is not able to adapt to the second image as fast as it adapts to the

first habitat. In collaboration with Ramos, the author of this thesis introduced an

evolutionary mechanism that, together with the stigmergic nature of the model, greatly

increased its capability to adapt to changing environments. The results achieved by the

new model on changing digital images appear in (Fernandes et al., 2005b). Meanwhile,

the model was being adapted for mathematical function optimization. The results are

similar to those attained in image processing: the combination of stigmergy with

selective reproduction greatly improved the ability of the swarm to find the optimal

8

regions of the fitness landscape. The first results on stationary and non-stationary

environments are in (Fernandes et al., 2005a). Later, Ramos, Fernandes and Rosa

(2005) tested the model on a wider range of dynamic environments6.

The results in (Fernandes et al., 2005a), (Fernandes et al., 2005b), (Ramos et al.,

2006) and (Ramos et al., 2007) inspired the idea of having a GA with varying

population size to tackle dynamic optimization problems7. Varying population GAs

have been studied since the beginning of 1990s, although most of the approaches have

reached a dead end. Fernandes and Rosa (2006) tried to overcome some of difficulties

of dynamic populations with the Self-Regulated Population Size Evolutionary

Algorithm (SRP-EA). The preliminary results on stationary environments were quite

promising, but in the meantime, a simpler and effective approach arose from SRP-EA,

simply by using a fixed size population. That algorithm is the aforementioned

ADMGA. The algorithm was first studied under a stationary optimization framework,

and the results were published in 2008 in the Journal of Soft Computing (Fernandes &

Rosa, 2008a). In the meantime, scalability tests with deceptive functions were

published as a book chapter in Advances in Evolutionary Computation (Fernandes &

Rosa, 2008b). In that same paper, the first studies on dynamic environments are

presented. Later, in (Fernandes et al., 2008e), the algorithm was applied to dynamic

trap and deceptive functions and a dynamic knapsack problem. Finally, an exhaustive

study on ADMGA and dynamic deceptive functions is in submission as a journal paper.

An alternative — and, as it will be shown, complementary — method for maintaining

the diversity of Genetic Algorithms throughout the run is proposed by Fernandes

6 Although the swarm is not suited (at least in its current form) for dynamic optimization — due to the high ratio

between the number of ants and the size of the search space —, its results, as aforementioned, inspired some of the

following investigations conducted for this thesis. In addition, other authors successfully applied the model to

image segmentation (Laptik & Navakauskas, 2007) and automated testing in software engineering (Mahanti &

Banerjee, 2006). Finally, the author of this thesis, in collaboration with Mora, Ramos, Merelo, Rosa and Laredo,

extended the model to deal with clustering and classification problems (Mora et al., 2008; Fernandes et al.,

2008f). The same model is also described in (Fernandes, 2008) and (Fernandes, 2009), where it is addressed as

potential creative tool, and where some possible dialogues between Art and Science are also mentioned. 7 The same results also inspired another line of work that mixed ideas from swarm algorithms with Estimation of

Distribution Algorithms (Lorrañga & Lozano, 2002; Pelikan et al., 1999). Those investigations led to some very

interesting results in (Fernandes et al., 2008b), (Lima et al., 2008a) and (Lima et al., 2008b), although they were

left out of this thesis. However, in a way, that research also inspired the sand pile mutation, because it deals with

self-organization and Evolutionary Algorithms.

9

(Fernandes et al., 2008b) in collaboration with Merelo, Ramos and Rosa. The scheme,

called sand pile mutation, is based on the Self-Organized Criticality theory (Bak et al.,

1987; Bak, 1996) and maintains population diversity by engaging in a varying mutation

intensity that is driven by events holding a power-law proportion between their

magnitude and their abundance. The method — after some changes that enhanced its

performance when compared to the version presented in (Fernandes et al., 2008b) —

attains very good results on a wide range of dynamic problems, and, like ADMGA,

outperforms two recently proposed evolutionary approaches — in (Tinós & Yang,

2007) and (Yang, 2008a) — for dynamic optimization in most of the dynamic scenarios

in the test set. When hybridized, the sand pile mutation and ADMGA’s mating scheme

result in a highly efficient algorithm that outperforms both strategies on most of the

proposed dynamic scenarios. Appendix A shows the complete list of publications

related with the body of work developed during the making of this thesis.

Summarizing, this thesis contributes to the Evolutionary Computation research field

in general and the evolutionary dynamic optimization in particular with:

A new mating scheme, inspired by the behaviour of natural species, which

preserves diversity and improves GAs’ performance on many dynamic

scenarios. ADMGA is also shown to improve GAs’ scalability on stationary

deceptive trap functions. The algorithm’s main feature consists of a simple

self-regulated mechanism that does not add complexity to the tuning effort.

A new mutation operator, inspired by the Self-Organized Criticality theory,

which introduces diversity in the population, thus improving its ability to react

to changes. The distribution of the mutation rates depends on the type of

problem and also on the dynamics of changes. In addition, the distribution’s

shape is particularly suited for dynamic optimization, because in some

generations large amounts of genetic diversity are introduced in the

population. Raising the mutation rate is a classical strategy for evolutionary

dynamic optimization, but unlike previous approaches, GASM is self-

regulated.

10

A hybrid scheme that mixes and improves the performance of both strategies.

By mixing the mating and selection scheme with the novel mutation operator,

the hybrid algorithm combines dissortative mating propensity to maintain

diversity with the sand pile mutation rate capability of introducing diversity.

The resulting hybrid broadens the range of dynamics in which each algorithm

excels.

Experimental studies that shed some light on how the GAs performance

varies with different mutation probability values and population size. To the

extent of our knowledge, there are no other studies on Evolutionary

Computation and dynamic optimization that investigate the effects of

parameter values in such a detail.

The algorithms do not increase GAs’ parameter space and do not require any

knowledge about the problem or dynamics of changes, as proposed.

The new methods improve the performance of not only traditional GAs, but

also the results of two state-of-the-art algorithms on many dynamic scenarios.

Finally, it is hoped that, due to the characteristics of the proposed methods —

the algorithms work without previous knowledge about the dynamics and do

not increase standard parameter space —, this line of work goes beyond

investigations on prototypes and inspire industrial applications.

1.3 Thesis Outline

This thesis is written in book-style with survey chapters and descriptions of

experimental studies. The survey chapters describe the Evolutionary Computation

research areas addressed by the thesis, and also the subjects which inspired some of the

techniques proposed in this work. Those survey chapters also try to put the present

research in perspective to other evolutionary approaches based on the natural systems.

The case study chapters are included to demonstrate the potential of the algorithms on

dynamic optimization problems.

11

The remaining of the thesis is structured as follows: Chapter 2 gives a survey on

optimization in uncertain environments, with a special emphasis on dynamic

optimization, which is the main subject of the thesis. Several previously proposed

Evolutionary Algorithms and other bio-inspired methods for dynamic optimization are

described within a framework that divides them according to strategies to deal with

changes. Typical dynamic problems and dynamic problem generators are described, as

well as a number of criteria along which dynamic environments may be classified and

tested.

Chapter 3 focuses on dissortative mating strategies for Genetic Algorithms and

presents ADMGA, and Chapter 4 describes the experiments conducted with the

algorithm on a wide range of stationary environments. Scalability tests on deceptive

functions are also presented in Chapter 4, while Chapter 5 describes the experiments

and results on dynamic optimization problems.

Chapter 6 addresses Self-Organized Criticality models, describes some optimization

algorithms based on such theory and presents the sand pile mutation. Chapter 7

describes the results attained by this method on dynamic environments, and Chapter 8

proposes a hybrid algorithm that mixes ADMGA’s mating strategy and the new

mutation protocol.

Finally, Chapter 9 concludes the thesis and outlines plans for future research.

12

13

Chapter 2

Optimization in Uncertain

Environments

2.1 Introduction

This chapter addresses evolutionary optimization in uncertain environments,

particularly those with time-varying (i.e., dynamic) fitness functions, which is the main

target of the investigations performed for the thesis. The most prominent types of

evolutionary techniques used in dynamic environments are described, along with their

specific fields of application, that is, the type of environmental dynamics for which the

different algorithms are more suited. Since robustness8 in dynamic optimization is the

main theme of the thesis, a special emphasis will be put on the limitations of some

efficient but, on the other hand, narrow-ranged methods. In addition, algorithms for

dynamic optimization of the same type of those described in the following chapter –

and used to evaluate the effectiveness of the proposed methods − are carefully

described. Classification of uncertain environments and bio-inspired algorithms for

dynamic optimization follows the ideas in (Jin & Branke, 2005) and (Branke, 2002).

The dynamic problem generator presented in (Yang, 2004) — used throughout this

investigation — and other well-known dynamic benchmark problems are also

described. The chapter ends with a critical note on experimental research methodology

for dynamic optimization. But first, a brief description of Evolutionary Computation in

8 In this context, robustness means that the efficiency of the algorithms is not limited to very specific kind of

dynamics. It may be stated that a robust algorithm is more suited for “black-box optimization”, that is, for dealing

with problems without using any previous knowledge about them. A different meaning for robustness is addressed

in the next section, under the different types of uncertain dynamics framework.

14

general, and Genetic Algorithms (GAs) in particular, is provided. The description just

aims at introducing the basic concepts of GAs. The unfamiliarized reader may then

refer (Holland, 1975), (Goldberg, 1989a) and (Bäck, 1996) for more details on this

particular class of metaheuristics

2.2 Evolutionary Algorithms

As stated in the abstract of Bäck’s book Evolutionary Algorithms in Theory and

Practice (Bäck, 1996):

―Evolutionary Algorithms are a class of direct, probabilistic search and

optimization algorithms gleaned from the model of organic evolution. (...)‖

The main idea behind Evolutionary Algorithms is Charles Darwin’s (1809-1882)

theory of natural selection (Darwin, 1859). This class of algorithms is usually divided

into three sub-classes — GAs, Evolution Strategies and Genetic Programming — but

some features are common to them: selection of the best solutions in a population,

recombination and mutation9. This thesis deals mainly with GAs, and so the following

description will focus on that type of Evolutionary Algorithms. Although Evolution

Strategies and Genetic Programming comprise some features of their own, GAs are

sufficient to illustrate the general idea.

A GA is a population of candidate solutions to a problem that evolve towards optimal

(local or global) points of the search space by recombining parts of the solutions to

generate a new population. The decision variables of the problem are encoded in strings

with a certain length and cardinality. In GAs’ terminology, these strings are referred to

as chromosomes, each string position is a gene and its values are the alleles. The alleles

may be binary, integer, real-valued, etc, depending on the codification (which in turn

may depend on the type of problem).

9 Some Evolutionary Algorithms may work without recombination, others without mutation, but the general

framework can be defined in such a way.

15

The ―best‖ parts of the chromosomes — or building-blocks — are guaranteed to

spread across the population by a selection mechanism that favours better (or fitter)

solutions. The quality of the solutions is evaluated by computing the fitness values of

the chromosomes, and this fitness function is usually the only information given to the

GA about the problem. This is the reason why GAs and other Evolutionary Algorithms

are so efficient as ―black-box-optimization‖ tools —