Evolutionary Optimization in Dynamic Environments Book

	Preface	xi
1.	Brief Introduction to Evolutionary Algorithms	1
1.	From Biology to Software	1
2.	Basic Evolutionary Algorithm	4
3.	Further Aspects	7
3.1	Representation	7
3.2	Parallelization	8
3.3	Runtime Comparisons	10
Part I	Enabling Continuous Adaptation
2.	Optimization in Dynamic Environments	13
1.	Categorization of Dynamic Environments	14
2.	Suitable Benchmark Problems	17
2.1	Dynamic Bit-Matching	17
2.2	Moving Parabola	18
2.3	Time-Varying Knapsack Problem	19
2.4	Moving Peaks Function	20
2.5	Scheduling Problems	24
2.6	Oscillating Peaks	25
3.	Measuring Performance	26
4.	Detecting Changes in the Environment	28
3.	Survey: State of The Art	31
1.	Restart / Re-Initialization	31
2.	Adapting Mutation	34
3.	Implicit or Explicit Memory	38
4.	Modifying Selection	42
5.	Multi-Population Approaches	44
5.1	Self-Organizing Scouts	44
5.2	Shifting Balance GA	45
5.3	Multinational GA	45
6.	Other Approaches	46
6.1	Immune Systems	46
6.2	Parallel EA Variants	46
6.3	Evolving Control Rules	46
6.4	Modeling the System	47
6.5	Stochastic Genetic Algorithm	47
6.6	Clan-based Evolution	48
6.7	Dual and Folding Genetic Algorithm	48
7.	Further Aspects	49
7.1	Steady-State or Generational Replacement?	49
7.2	Darwinian vs. Lamarckian Learning	50
7.3	Parameter Settings	51
7.4	Other Related Work	51
4.	From Memory to Self-Organization	53
1.	Memory/Search	54
1.1	General Thoughts about Memory	54
1.2	The Best of Two Worlds	56
2.	Self-Organizing Scouts	58
5.	Empirical Evaluation	67
1.	General Remarks on the Experimental Setup	67
2.	Default Parameter Settings	69
3.	Oscillating Peaks Function	71
3.1	Standard Test Case	72
3.2	The Influence of Change Frequency	76
3.3	Non-vanishing Peaks	78
4.	Moving Peaks Function	81
4.1	Sensitivity of Parameter Settings	81
4.2	The Effect of Peaks Movements	86
4.3	Changing the Number of Peaks	90
4.4	The Influence of Change Frequency	94
4.5	Higher Dimensionality	96
4.6	Correlation of Shifts	97
6.	Summary of Part 1	99
Part II	Considering Adaptation Cost
7.	Adaptation Cost Vs. Solution Quality	105
1.	Introduction to Multi-Objective EAs	106
2.	Related Work	109
3.	Guided Multi Objective Evolutionary Algorithm	111
4.	Experimental Results	114
5.	Summary of Chapter 7	121
Part III	Robustness and Flexibility--Precaution against Changes
8.	Searching for Robust Solutions	125
1.	Motivation	125
2.	Related Work	128
3.	Test Problems	132
4.	Experimental Setup and Default Parameters	136
5.	How to select the final solution?	138
6.	Influence of Several EA Parameters	141
6.1	The Number of Samples Throughout the Run	141
6.2	Allowed Running Time	142
6.3	Selection Pressure	143
6.4	Steady State vs. Generational Reproduction	144
6.5	Population Size	147
6.6	The Island Model	153
6.7	Selection Method	154
7.	Evaluating Good Individuals More Often	156
8.	Minimizing the Estimation Error	158
9.	Better Sampling Methods	160
10.	Changing the Sample Size	163
11.	Looking at Other Individuals in the Neighborhood	167
12.	Summary of Chapter 8	169
9.	From Robustness to Flexibility	173
1.	Related Work	174
2.	Dynamic Job Shop Scheduling	175
2.1	Decomposing Dynamic JSSPs	175
2.2	The Role of Schedule Builders	176
3.	A Flexibility Measure for Dynamic Stochastic JSSPs	178
4.	Empirical Evaluation	180
5.	Summary of Chapter 9	183
10.	Summary and Outlook	185
	References	191
	Index	207