139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Evolutionary computation algorithms are employed to minimize functions with large number of variables. Biogeography-based optimization (BBO) is an optimization algorithm that is based on the science of biogeography, which researches the migration patterns of species. These migration paradigms provide the main logic behind BBO. Due to the cross-disciplinary nature of the optimization problems, there is a need to develop multiple approaches to tackle them and to study the theoretical reasoning behind their performance. This book explains the mathematical model of BBO algorithm and its variants created to cope with continuous domain problems (with and without constraints) and combinatorial problems.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 422
Veröffentlichungsjahr: 2017
Ähnliche
Table of Contents
Cover
Title
Copyright
1 The Science of Biogeography
1.1. Introduction
1.2. Island biogeography
1.3. Influence factors for biogeography
2 Biogeography and Biological Optimization
2.1. A mathematical model of biogeography
2.2. Biogeography as an optimization process
2.3. Biological optimization
2.4. Conclusion
3 A Basic BBO Algorithm
3.1. BBO definitions and algorithm
3.2. Differences between BBO and other optimization algorithms
3.3. Simulations
3.4. Conclusion
4 BBO Extensions
4.1. Migration curves
4.2. Blended migration
4.3. Other approaches to BBO
4.4. Applications
4.5. Conclusion
5 BBO as a Markov Process
5.1. Markov definitions and notations
5.2. Markov model of BBO
5.3. BBO convergence
5.4. Markov models of BBO extensions
5.5. Conclusions
6 Dynamic System Models of BBO
6.1. Basic notation
6.2. Dynamic system models of BBO
6.3. Applications to benchmark problems
6.4. Conclusions
7 Statistical Mechanics Approximations of BBO
7.1. Preliminary foundation
7.2. Statistical mechanics model of BBO
7.3. Further discussion
7.4. Conclusions
8 BBO for Combinatorial Optimization
8.1. Traveling salesman problem
8.2. BBO for the TSP
8.3. Graph coloring
8.4. Knapsack problem
8.5. Conclusion
9 Constrained BBO
9.1. Constrained optimization
9.2. Constraint-handling methods
9.3. BBO for constrained optimization
9.4. Conclusion
10 BBO in Noisy Environments
10.1. Noisy fitness functions
10.2. Influence of noise on BBO
10.3. BBO with re-sampling
10.4. The Kalman BBO
10.5. Experimental results
10.6. Conclusion
11 Multi-objective BBO
11.1. Multi-objective optimization problems
11.2. Multi-objective BBO
11.3. Real-world applications
11.4. Conclusion
12 Hybrid BBO Algorithms
12.1. Opposition-based BBO
12.2. BBO with local search
12.3. BBO with other EAs
12.4. Conclusion
APPENDICES
Appendix A: Unconstrained Benchmark Functions
Appendix B: Constrained Benchmark Functions
Appendix C: Multi-objective Benchmark Functions
Bibliography
Index
End User License Agreement
Guide
Cover
Table of Contents
Begin Reading
Pages
C1
iii
iv
v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
325
326
327
G1
G2
G3
G4
G5
G6
G7
G8
Metaheuristics Set
coordinated byNicolas Monmarché and Patrick Siarry
Volume 8
Evolutionary Computation with Biogeography-based Optimization
Haiping Ma
Dan Simon
First published 2017 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK
www.iste.co.uk
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA
www.wiley.com
© ISTE Ltd 2017
The rights of Haiping Ma and Dan Simon to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2016954823
British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British LibraryISBN 978-1-84821-807-9
1The Science of Biogeography
Biogeography is the science studying the distribution of species and ecosystems in geographic space and through time. It is usually considered a subset of physical geography because it often is related to the study of the physical environment, and how it affects species and shapes their distribution across space. It is concerned not only with habitation patterns, but also with the factors responsible for variations in distribution. It aims to analyze where species live, and in what abundance. Biogeography has strong ties to biology, ecology, evolution, climatology and soil science.
Overview of the chapter
This chapter provides the basic notations and ideas that form the foundation of biogeography-based optimization (BBO). This chapter first gives an introduction to natural biogeography in section 1.1, and then focuses on island biogeography in section 1.2. Some interesting factors that influence biogeography and that inspire BBO algorithmic features are described in section 1.3.
1.1. Introduction
The science of biogeography can be traced to the work of 19th Century naturalists, most notably Alfred Wallace [WAL 06] and Charles Darwin [KEY 01] (see Figure 1.1). Wallace is usually considered the father of biogeography, although Darwin is much better known because of his preeminence in publishing the theory of evolution. Science views the distribution of species in the world as a result of continuous evolution. Some species evolve locally.
Figure 1.1.Photographs of Charles Darwin (left) and Alfred Wallace (right)
The science of biogeography answers many varied questions. As writer David Quammen put it [QUA 96], “…biogeography does more than ask Which species? and Where. It also asks Why? and, sometimes more crucially, Why not?” Biogeography developed in an attempt to answer some of these questions, such as why there are so many kinds of animals and plants in the world. It seeks to explain why some of these animals and plants are rare while others are common. It seeks to explain why some animals and plants are widely dispersed while others are confined to a limited area. It seeks to explain why some parts of this world are richer in species than others. The study of biogeography helps us to answer these types of questions.
Modern biogeography is the study of the geographical distribution of animals and plants while taking into account species counts, present and past, the habitats in which they are found, and ecological relationships. By observing the geographic distribution of species, we can see that the following factors are associated with biogeography: air pressure, physiography, ocean currents, latitude, temperature, amount of sun light, precipitation and wind. Biogeography combines information and ideas from many fields, ranging from the physiological and ecological constraints on species dispersal, to geological and climatological phenomena that operate at global spatial scales and evolutionary time frames. The short-term interactions within a habitat and between species comprise the ecological application of biogeography. Historical biogeography deals with the long-term, evolutionary periods of time, and broader classifications of species.
There are two important theories in biogeography that have been developed to address the distribution of biological species in the world: the distance-decay theory [NEK 99] and the island biogeography theory [MAC 67]. The distance-decay theory asserts that the correlation and similarity between species in any two geographical locations will continue decreasing as the distance between the two increases. Island biogeography asserts that those islands that are closely spaced will support more biological species than islands that are far apart. It is this second theory that explains that species on closely spaced islands are rarely threatened by extinction, compared to tiny isolated islands. Geographic information systems scientists say that the above two theories were developed in order to explain the distribution of species, but not the distribution or even the movement of humans. That is, the purpose of these theories is to understand the factors affecting species distribution, to predict future trends in species distribution, and to solve ecological problems that have a spatial aspect.
Because of the focus of this book, we do not emphasize one theory more than the other, and we do not further discuss the essence of the science of biogeography. We focus instead on using island biogeography to inspire an evolutionary algorithm to solve optimization problems: biogeography-based optimization (BBO).
1.2. Island biogeography
In the early 1960s, Robert MacArthur and Edward Wilson began working on mathematical models of island biogeography, culminating in their classic 1967 book The Theory of Island Biogeography [MAC 67]. They were mostly interested in the distribution of species between neighboring islands, and mathematical models of the extinction and migration of species. Since MacArthur and Wilson’s work, biogeography has become a major subset of biology [HAN 97]. Figure 1.2 shows photographs of Robert MacArthur and Edward Wilson.
Figure 1.2.Photographs of Robert MacArthur (left) and Edward Wilson (right)
Biogeography is most keenly focused on islands. Islands are often manageable areas of study because they are more condensed than larger ecosystems on the mainland. Islands are also attractive locations for study because they allow scientists to look at habitats that new invasive species have only recently colonized, and to observe how they disperse throughout the island and change it. Scientists can then apply their understanding to similar but more complex mainland habitats. Islands are very diverse in their biomes, ranging from tropical to arctic climates. This diversity allows for a wide range of species studies in different parts of the world.
Mathematical models of island biogeography describe speciation (the evolution of new species), the migration of species between islands, and the extinction of species. The term island here is descriptive rather than literal. An island is considered any habitat that is geographically isolated from other habitats. In the classic sense of the term, an island is isolated from other habitats by water. But islands can also be habitats that are isolated by stretches of desert, rivers, mountain ranges, predators, man-made artifacts or other obstacles. For example, an island could consist of a riverbank that supports herbs, or a pond that supports insects [HAN 97].
Geographical areas that are friendly to life are said to have a high habitat suitability index (HSI) [WES 87]. Features that correlate with HSI include factors such as rainfall, vegetative diversity, topographic diversity, land area and air temperature. These features that characterize habitability are called suitability index variables (SIVs). In terms of habitability, SIVs are the independent variables of the habitat, and HSI is the dependent variable.
Islands with a high HSI tend to support many species, and islands with a low HSI can support only a few species. Islands with a high HSI have many species that emigrate to nearby habitats, simply by virtue of the large number of species that they host. Emigration from an island with a high HSI does not occur because species want to leave their home; after all, the home island is an attractive place to live. The reason that emigration occurs from these islands is due to the accumulation of random effects on a large number of species with large populations. Emigration occurs as animals ride flotsam, swim, fly or ride the wind to neighboring islands. When a species emigrates from an island, the species does not completely disappear from the island; only a few representatives emigrate, so an emigrating species remains present on its home island while at the same time migrating to a neighboring island.
Islands with a high HSI not only have a high emigration rate, but they have a low immigration rate because they already support many species. The species that arrive at such islands will tend not to survive, even though the HSI is high, because there is too much competition for resources.
Islands with a low HSI have a high immigration rate because of their low populations. Again, this is not because species want to immigrate to such islands; after all, these islands are undesirable places to live. The reason that immigration occurs on these islands is because there is a lot of geographical room for additional species. Whether or not the immigrating species can survive in its new home, and for how long, is another question. However, species diversity is correlated with HSI, so more species arriving at a low HSI island will result in a greater chance that the island’s HSI will increase [WES 87].
Figure 1.3 depicts species migration between islands, and Figure 1.4 illustrates a model of species abundance on a single island [MAC 67]. The immigration and emigration rates are functions of the number of species on the island. We have depicted the migration curves as straight lines, but in general they might be more complicated curves, as we will discuss later.
Figure 1.3.Species migrate between islands via flotsam, wind, flying, swimming and other methods. For a color version of this figure, see www.iste.co.uk/ma-simon/evolutionary.zip
Figure 1.4.Species migration model of an island, based on [MAC 67], where S0is the equilibrium species count
Consider the immigration curve. The immigration rate λ decreases monotonically as the number of species on the island increases, since as S increases, there is less room on the island for new species. The maximum possible immigration rate to the habitat is I, which occurs when there are zero species on the island. As the number of species increases, the island becomes more crowded, fewer species are able to survive immigration, and the immigration rate decreases. The largest possible number of species that the habitat can support is Smax, at which point the immigration rate is zero.
Now consider the emigration curve. The emigration rate μ should be, from reasoning parallel to that above, a monotonically increasing function of S. If area is proportional to population sizes, and emigrations are the chance result of demographic stochasticity, then as the number of species increases, the number of species that are subject to chance emigrations increases in proportion, and the relationship is linear. If there are no species on the island, then the emigration rate is zero. As the number of species on the island increases, it becomes more crowded, more species leave the island, and the emigration rate increases. The maximum emigration rate is E, which occurs when the island contains the largest number of species that it can support.
Finally, consider the equilibrium species count. The migration model predicts that there is a value S0 at which the immigration rate and the emigration rate balance; there is a dynamic equilibrium. At that point, species on the island immigrate at a rate equal to disappearances due to emigration. This is a stable equilibrium since, if the number of species on the island is perturbed, the imbalance between the immigration and emigration rates at the new S would tend to return island diversity toward its equilibrium value. Below S0, additional species accumulate and the immigration rate is larger than the emigration rate. Above S0, the reverse is true, emigrations exceed immigrations, and the number of species declines to S0.
1.3. Influence factors for biogeography
We have discussed the basic theory of island biogeography, which is the study of the geographical distribution of biological species on islands. There are many interesting influence factors closely associated with biogeography, including the following.
Nonlinear migration: Classic island biogeography theory assumes that the immigration and emigration rates are linear with respect to the number of species, as shown in Figure 1.4. However, there is no reason to suppose that the migration curves are linear. Empirical data suggest that biological migration rates are probably nonlinear functions of the number of species [MAC 67]. Pioneer species are likely to rapidly colonize an island that has a higher immigration rate, and later less robust species follow. They will not only immigrate later, but the rate at which they immigrate will be lower because they have less intrinsic ability for colonization. The rate at which species accumulate on islands is therefore initially rapid and then slower. Also, among poor species, the successful immigration of any one species has less effect on the immigration rates of other species than does the earlier immigration of pioneer species. Therefore, this part of the immigration curve should be flatter; that is, the rate of immigration should be less affected by the arrival of poor species. The result is an immigration rate curve which is nonlinear. For the purpose of simplicity in evaluating the basic implications of the migration model, the emigration curve can be viewed as a mirror image of the immigration curve, and it would also be nonlinear in this case.
Habitat similarity: In island biogeography, immigration rate is correlated with island isolation [ADL 94]. Islands that are isolated are relatively well buffered from immigration. This intuitive idea is called the distance effect [WU 95]. It also stands to reason that emigration rates are correlated with island isolation. The environmental uniqueness of an island is related to island isolation because environmental conditions vary predictably with geographical distance [LOM 00a]. Similar islands could be viewed as clustered together, and belong to the same archipelago. However, dissimilar islands are not part of an archipelago. This tends to increase the immigration and emigration rates between similar islands, and decrease those rates between dissimilar islands. On the other hand, islands in different archipelagos can interact with each other, just as species can migrate across archipelagos. However, migration across archipelagos is less likely than migration within archipelagos. A quantitative way to determine the effect of island isolation on migration rates is given in Hanski [HAN 99]. Figure 1.5 shows two well-known archipelagos: the Fernando de Noronha archipelago in Brazil and the Ksamil archipelago in Albania.
Initial immigration: Classic island biogeography theory indicates that the immigration rate decreases as the number of species increase, as shown in Figure 1.4, which corresponds to a monotonic decrease in immigration rate with the number of species. However, recent advances in biogeography indicate that a monotonic immigration rate curve may be overly simplistic. For some pioneer species, an initial increase in species count results in an initial increase in the immigration rate [WU 95]. This is because these early immigrants modify the island to make it more hospitable to other species. That is, the positive effect of increased diversity due to initial immigration overcomes the negative effect of increased population size, which corresponds to an initial increase in immigration rate as species count increases. This phenomenon can be viewed as a temporary positive feedback mechanism in biogeography. That is, an island with a low HSI accepts species from other islands, increasing its HSI, which subsequently increases its likelihood of accepting even more species from other islands.
Figure 1.5.The Fernando de Noronha archipelago in Brazil (left) and the Ksamil archipelago in Albania (right)
Species mobility: Classic island biogeography theory assumes that all species are equal in their migratory ability. In reality, some species are more mobile than others, and some species are better dispersers than others. For example, insect and bird species are generally more mobile than mammals and therefore are more likely to migrate. Figure 1.6 shows that bird species have fast migratory ability and elephant species have slow migratory ability. Efforts have been made in biogeography to incorporate species-specific characteristics into island biogeography theory [LOM 00b]. The species migration model in Figure 1.4 assumes that all species are equally mobile. But the species migration model would be more accurate if species mobility were considered. That is, each individual species would have its own migration curves for each individual island.
Population size: In island biogeography, an island not only has a certain number of species, but each species also has a population size. Those species that are well adapted to their environment tend to increase in population, while those that are not well adapted have a lower equilibrium population. That is, the correlation between a particular species and an island’s HSI could be used to determine the equilibrium population of each species. Species with a high HSI contribution would have high equilibrium populations, and those with a low HSI contribution would have low equilibrium populations. We could assume that each species approaches its equilibrium population exponentially [CAS 89]. This approach would result in more flexibility for the species migration model. In addition, those species with a large population would have a greater likelihood of immigrating to neighboring islands. This discussion of population size is similar to species mobility as discussed above.
Figure 1.6.Bird species with fast migratory ability (left) and elephant species with slow migratory ability (right)
Species age: In biology, species age influences extinction rate and mobility [GRO 05]. Just as individual mortality is high at a young age, low at middle age and high again at old age, species mortality follows the same pattern. Young species tend to be unstable and susceptible to extinction. Middle-aged species are well established but still mobile. Old species are stagnant and less likely to adapt. That is, species of different ages have different emigration and immigration rates. Species that have been recently introduced to an island have a higher extinction rate and a lower emigration rate, middle-aged species have a lower extinction rate and a higher emigration rate, and older species revert to the pattern of high extinction rate and low emigration rate.
Predator/prey relationships: In biology, certain species have adversarial relationships. These relationships do not necessarily harm the prey species. For instance, prey may respond to predators by reducing the exploitation of their resources, thus benefiting themselves in the long term [HAN 97]. However, the more common scenario is one in which predators reduce prey to such an extent that one or both populations face extinction. Predator/prey relationships can be inferred from a population by examining islands and noting which pairs of species have a low probability of coexisting. Those species can then be modeled as a predator/prey pair. Combining this information with the HSI contribution of each species would result in defining the predator species as the adversary that is positively correlated with island HSI, and the prey species as the adversary that is negatively correlated with island HSI. The predator/prey relationship might lead to a non-zero equilibrium population, or it might lead to the extinction of one or both populations [GOT 08, HAN 97]. Most predator/prey models in biology are for two-species systems, but a more complete description would be obtained if existing predator/prey models could be extended to multi-species systems.
Resource competition
