进化算法变体在现实世界应用中的探索

需积分: 7 105 浏览量更新于2024-07-18 收藏 11.31MB PDF 举报

"本书《Variants of Evolutionary Algorithms for Real-World Applications》主要探讨了进化算法的各种变体在现实世界应用中的使用。编辑包括Raymond Chiong、Thomas Weise和Zbigniew Michalewicz，他们都是各自领域的专家。这本书深入研究了如何利用这些算法解决实际问题，并提供了丰富的案例和实例。" 进化算法是一种模拟自然界中物种进化过程的计算方法，主要用于优化复杂问题。这些算法基于达尔文的适者生存和自然选择理论，包括遗传算法（Genetic Algorithms）、遗传编程（Genetic Programming）、粒子群优化（Particle Swarm Optimization）等。它们在解决多目标优化、组合优化、参数估计等问题中表现出强大的能力。本书的重点在于讨论进化算法的不同变体，这些变体是为了适应特定问题或提高算法性能而设计的。例如，通过修改选择、交叉和变异操作，可以改进基本算法的表现。选择操作决定了哪些个体将进入下一代，交叉操作是新个体生成的方式，而变异操作则增加了种群的多样性，防止算法陷入局部最优。在实际应用中，进化算法被广泛应用于工程设计、金融优化、机器学习、人工智能、生物信息学等领域。书中的内容可能涵盖了如何针对特定应用调整算法参数，以及如何处理大规模和高维度的问题。此外，可能还涉及了与其他优化技术如模拟退火、禁忌搜索等的比较。书中提到的“ABC”可能是指Artificial Bee Colony算法，这是一种受到蜜蜂采蜜行为启发的全局优化算法。这种算法通过模拟工蜂、侦查蜂和蜂巢的行为来寻找解决方案，尤其适用于多模态优化问题。《Variants of Evolutionary Algorithms for Real-World Applications》是一本关于如何应用和改进进化算法以解决现实世界挑战的宝贵资源。它不仅为研究人员提供了深入的理论分析，也为工程师和实践者提供了实用的指导，帮助他们在各自的领域中有效地应用这些强大的计算工具。

4 C. Blum et al.

our focus is to discuss what Evolutionary Algorithms (EAs) – one of the

most popular metaheuristic methods – are and how they diﬀer from other

metaheuristics. The aim is not to give a deﬁnitive answer to the question

“What is an EA?” – it is almost impossible for anyone to do so. Instead,

we will systematically explore and discuss the traditional and modern views

of this topic. We start by describing what metaheuristics are, followed by

the core question of what EAs are. We then present some of the most well-

known EAs, such as Genetic Algorithms (GAs), Genetic Programming (GP),

Evolution Strategies (ES) and Evolutionary Programming (EP). After that,

we extend our discussion to Memetic Computing, taking a look at the rele-

vance/connection between EAs and Memetic Algorithms (MAs). Finally, we

also discuss the similarities and diﬀerences between EAs and the Swarm In-

telligence algorithms such as Particle Swarm Optimization (PSO) and Ant

Colony Optimization (ACO).

2 Metaheuristics

The ﬁeld of metaheuristics has a rich history. During the second half of the

20th century, with the development of computational devices and demands of

industrial processes, the necessity to solve some optimization problems arose

despite the fact that there was not suﬃcient prior knowledge (hypotheses)

on the optimization problem for the application of an exact method. In fact,

in the majority of industrial cases, the problems are highly nonlinear, or

characterized by a noisy ﬁtness, or without an explicit analytical expression

as the objective function might be the result of an experimental or simulation

process. In this context, the earliest metaheuristics have been designed. The

term metaheuristic, from the greek meta-euriskein which means beyond the

search, refers to a computational method which progressively attempts to

improve one or more candidate solutions while searching for the optimum.

Whenever an optimization problem is to be solved, we expect that there is

some kind of utility measure which deﬁnes how good a solution is or how high

the costs are. Usually this measure is given in the form of a mathematical

function f. Then, as stated before, the inputs for which the function takes on

the minimal (or maximal) value is sought. Sometimes, multiple such functions

have to be optimized simultaneously.

A metaheuristic is a method for solving a general class of optimization

problems. It combines utility measures in an abstract and hopefully eﬃcient

manner, typically without utilizing deeper insights into their inner structure.

Metaheuristics do not require hypotheses on the optimization problem nor

any kind of prior knowledge on the objective function. The treatment of

objective functions as “black boxes” [11, 42, 45, 102] is the most prominent

and attractive feature of metaheuristics. Metaheuristics obtain knowledge

about the structure of an optimization problem by utilizing statistics obtained

from the possible solutions (i.e., candidate solutions) evaluated in the past.

Evolutionary Optimization 5

This knowledge is used to construct new candidate solutions which are likely

to have a high utility.

Many diﬀerent types of metaheuristics emerged during the last 30 years,

and the majority of them have been inspired by some aspects of the nature

(see [19] for a recent collection of nature-inspired algorithms). These include a

variety of Hill Climbing techniques (deterministic and stochastic), the Swarm

Intelligence algorithms (PSO and ACO), Artiﬁcial Immune Systems, Diﬀer-

ential Evolution, Simulated Annealing, Tabu Search, Cultural Algorithms,

Iterated Local Search, Variable Neighborhood Search, and – of course – Evo-

lutionary and co-Evolutionary Algorithms.

Metaheuristics can be classiﬁed based on diﬀerent criteria. For example,

some of them process a single solution (e.g., Simulated Annealing), whereas

some others process a set of solutions and are called population-based meth-

ods (e.g., EAs). Some metaheuristics are deterministic (e.g., Tabu Search),

others are stochastic (e.g., Simulated Annealing). Some generate complete

solutions by modifying complete solutions (e.g., EAs), while some others con-

struct new solutions at every iteration (e.g., ACO). Many of these metaheuris-

tics oﬀer unique features, but even within a single approach, there are many

variants which incorporate diﬀerent representation of solutions and diﬀerent

modiﬁcation or construction techniques for new solutions.

3 What Are “Evolutionary Algorithms”?

So, what are EAs? Perhaps the best place to start in answering the question

is to note that there are at least two possible interpretations of the term

evolution. It is frequently used in a very general sense to describe something

that changes incrementally over time, such as the software requirements for

a payroll accounting system. The second meaning is its narrower use in biol-

ogy, where it describes an evolutionary system that changes from generation

to generation via reproductive variation and selection. It is this Darwinian

notion of evolutionary change that has been the core idea in EAs.

3.1 Principles Inspired by Nature

From a conventional point of view, an EA is an algorithm that simulates –

at some level of abstraction – a Darwinian evolutionary system. To be more

speciﬁc, a standard EA includes:

1. One or more populations of individuals competing for limited resources.

2. These populations change dynamically due to the birth and death of indi-

viduals.

3. A notion of ﬁtness which reﬂects the ability of an individual to survive

and reproduce.

4. A notion of variational reproduction: oﬀspring closely resemble their par-

ents, but are not identical.

6 C. Blum et al.

In a nutshell, the Darwinian principles of evolution suggest that, on aver-

age, species improve their ﬁtness over generations (i. e., their capability of

adapting to the environment). A simulation of the evolution based on a set

of candidate solutions whose ﬁtness is properly correlated to the objective

function to optimize will, on average, lead to an improvement of their ﬁtness

and thus steer the simulated population towards the solution.

3.2 The Basic Cycle of EAs

In the following, we try to introduce a very simple EA consisting of a sin-

gle population of individuals exist in an environment that presents a time-

invariant notion of ﬁtness. We will do this from a general perspective, com-

prising most of the conventional EAs.

Like in nature, an individual may have two diﬀerent representations: the

data structure which is processed by the genetic search procedures and the

format in which it is assessed by the environment (and ﬁnally handed to

the human operator). Like in biology, in the context of EAs, the former

representation is referred to as genotype and the latter as phenotype.EAs

usually proceed in principle according to the scheme illustrated in Fig. 1. Its

steps can be described as follows:

Evaluation

compute the objective

values

of the candidate

solutions

compute the objective

values of the candidate

solutions

GPM

apply the genotype-

phenotype

mapping and

obtain

the phenotypes

apply the genotype-

phenotype mapping and

obtain the phenotypes

Fitness AssignmentFitness Assignment

use the objective values

determine fitness

values

use the objective values

to determine fitness

values

Initial Population

create an initial

population of random

individuals

create new individuals

from

the mating pool by

crossover

and mutation

create new individuals

from the mating pool by

crossover and mutation

ReproductionReproduction

SelectionSelection

select the fittest indi-

viduals

for reproduction

select the fittest indi-

viduals for reproduction

Fig. 1. The basic cycle of EAs

1. In the ﬁrst generation, a population of n>0 individuals is created. Usu-

ally, these individuals have random genotypes but sometimes, the initial

population is seeded with good candidate solutions either previously known

or created according to some other methods.

Evolutionary Optimization 7

2. The genotypes, i. e., the points in the search space, are then translated

to phenotypes. In the case that search operations directly work on the

solution data structures, this genotype-phenotype mapping is the identity

mapping.

3. The values of the objective functions are then evaluated for each candidate

solution in the population. This evaluation may incorporate complicated

simulations and calculations.

4. With the objective functions, the utility of diﬀerent features of the can-

didate solutions has been determined. If there is more than one objective

function, constraint, or other utility measure, then a scalar ﬁtness value is

assigned to each of them.

5. A subsequent selection process ﬁlters out the candidate solutions with poor

ﬁtness and allows those with good ﬁtness to enter the mating pool with a

higher probability.

6. In the reproduction phase, oﬀspring are derived from the genotypes of the

selected individuals by applying the search operations (which are called

reproduction operations in the context of EAs). There are usually two dif-

ferent reproduction operations: mutation, which modiﬁes one genotype,

and crossover, which combines two genotypes to a new one. Whether the

whole population is replaced by the oﬀspring or whether they are inte-

grated into the population as well as which individuals to recombine with

each other depends on the applied population handling strategy.

7. If the termination criterion is met, the evolution stops here. Otherwise,

the evolutionary cycle continues with the next generation at point 2.

Of course, such an algorithm description is too abstract to be executed

directly.

3.3 Do All EAs Fit to the Basic Cycle?

According to our discussion so far, a simple answer to the question “What

are EAs?” would be that EAs are those based on the concepts gleaned from

natural evolution and which roughly adhere to the principles and the ba-

sic cycle introduced in the previous sections. From a high-level perspective,

however, the deﬁnition is not so clear.

When solving a new challenging problem, often a new optimization method

is designed. It is necessary to specify how the individuals in the population

represent the problem solutions, how the ﬁtness is calculated, how parents

are selected, how oﬀspring are produced, and how individuals are selected for

removal from the population (i. e., to die

). Each of these decisions results

in an EA variant with diﬀerent computational properties.

The “death” of an individual, candidate solution, or agent in terms of meta-

heuristic optimization means that it is removed from the set of elements under

investigation and deleted from memory, possibly due to being replaced by a bet-

ter element.

8 C. Blum et al.

Will these design decisions result in an EA? Before you answer, let us

recall that the (1 + 1) EA does not require a population of solutions but

processes just one individual (and is comparing it with its only oﬀspring).

Many “Evolutionary Algorithms” assume deterministic selection methods,

many “Evolutionary Algorithms” take advantage of smart initialization and

problem-speciﬁc operators. Some “Evolutionary Algorithms” have been ex-

tended with memory structures (e.g., when they operate in dynamic envi-

ronments) or by a parameter called temperature (to control mutation rates).

The list could go on.

While there is a well-researched set of “default” EAs which we will intro-

duce in the next section, for many real-world applications it is necessary to

derive new, specialized approaches. Examples for this can be found in [103–

105] as well as the collection in this book [20].

3.4 Conventional EAs

Historically, computer scientists and engineers had started to consider draw-

ing inspiration from evolutionary principles for solving optimization problems

as early as the 1950s (see [4, 5], and [39]). In the 1960s and 1970s, three re-

search lines were developed in parallel [73]: EP [38], ES [91], and GAs [55].

De Jong’s PhD thesis [25] further increased the interest in this ﬁeld, and his

PhD student Grefenstette, in turn, started the International Conference on

Genetic Algorithms and their Applications (ICGA) [52] in 1985. At the 1991

ICGA [6], the three original research streams came together, with Hans-Paul

Schwefel presenting the ES. At the same venue, Koza [64] introduced the new

concept of Standard GP and Zbigniew Michalewicz outlined the concepts of

diﬀerent data structures which can undergo the evolutionary process in the

so-called Evolutionary Programs [75]. This was considerably the ﬁrst time

all major areas of Evolutionary Computation were represented at once. As a

result, the Evolutionary Computation Journal by MIT Press was established,

later followed by the IEEE Transactions on Evolutionary Computation.The

idea of unifying concepts, such as “Evolutionary Algorithms” (or the more

general idea of Evolutionary Computation [73]), was then born. Thereafter,

the ﬁrst IEEE Congress on Evolutionary Computation [74] was initiated in

1994.

From the 1990s onwards, many new ideas have been introduced. One of

the most important developments is the discovery that EAs are especially

suitable for solving problems with multiple, possibly conﬂicting optimization

criteria – the Multi-Objective Evolutionary Algorithms (MOEAs) [22, 29].

Today, the second, improved versions of NSGA [30, 98] and SPEA [113, 114]

may be the most popular members of this MOEA family.

There is also growing interest in co-evolutionary EAs, originally introduced

by Hillis [53] back in 1989. Potter and De Jong [88, 89] developed cooperative

co-evolution, which is now regarded as one of the key approaches for tack-

ling large-scale optimization problems because it provides a viable way to

www.allitebooks.com

剩余468页未读，继续阅读

kernelkoder

粉丝: 57
资源: 317

进化算法变体在现实世界应用中的探索

np难问题近似算法(绝版好书)

Efficient Variants of the ICPalgorithm

Graph Neural Networks_ A Review of Methods and Applications----清华大学周杰.pdf

Help me write a literature review of the research on path planning algorithms for satellite maps

the vanilla transformer

The consumer was configured to find a runtime of a component compatible with Java 11, packaged as a jar, and its dependencies declared externally. However we cannot choose between the following variants of org.jetbrains.kotlin:kotlin-gradle-plugin:1.7.0:

what deferent from chitGpt and chatGpt

使用aarch64-linux-android23-clang工具链编译libjvm.so

最新资源