1: Introduction to Evolutionary Computing 进化计算导论

Positioning of Evolutionary Computation进化计算的定位

  1. EC is part of computer science - computational intelligence - bio-inspired computing

EC 是计算机科学的一部分，属于计算智能（computational intelligence），也属于受生物启发的计算（bio-inspired computing）

  1. Biology delivered inspiration and terminology

生物学为 EC 提供了灵感和术语。

  1. EC can be used as a tool for biological research

EC 也可以作为生物学研究的工具。

4.Systematic trial-and-error (generate-and-test)
problem solving

系统化的试错式（生成并测试）问题求解方法。

Motivation and Inspiration for EC

Motivation

1.Solve complex problems (NP-hard, multimodal, noisy, dynamic, multi-objective)

解决复杂问题（NP难、多模态、带噪声、动态、多目标）

2.Develop automatic problem solvers

开发自动问题求解器

3.Need for robust algorithms that are applicable to a wide range of similar problems, without much tailoring for specific problem settings

需要能够应用于广泛类似问题的 鲁棒 算法，而无需针对特定问题场景进行大量调整

4.Simulate natural evolution

模拟自然演化

Engineer evolution自然进化的机制工程化

EVOLUTION PROBLEM SOLVING
Environment环境 Problem问题
Individual个体 Candidate Solution候选解
Fitness适应度 Quality 解的质量

Fitness :chances for survival and reproduction生存和繁殖的机会

Ingredients of evolution

进化所需要的几个基本要素

image-20260925173658896

Natural evolution -> evolutionary algorithms（EA）

从自然进化到进化算法

Natural evolution evolutionary algorithms
Population种群 Population种群
Heredity遗传 Representation编码方式
Variation operators变异算子/产生变化的操作
Variation变异 / 差异 Variation operators
Differential reproduction差异性繁殖 Evaluation 评估
Selection选择
Replacement替换

Evolutionary algorithm

image-20260925174447886

History

image-20260925174509396

Evolutionary AI（进化式人工智能)

  • Creative 有创造性

  • Adaptive 能够适应变化

  • Diversity 多样性

Problem categorization问题类型

image-20260925174859811

Consists of three components由三个部分组成
Different problems for different unknown components 当未知的部分不同，就会形成不同类型的问题

Problem type 1: Optimization 优化问题

We have a model of our system and seek inputs that give us a specified goal

我们已经有一个系统模型，我们要找到一个合适的 Input，让系统产生我们想要的 Output

image-20260925175230166

Examples
- Time tables for university, call center, or hospital 大学、呼叫中心或医院的时刻表
- Traveling salesman problem (TSP)旅行推销员问题
- Knapsack problem背包问题

优化是在找：哪一个 Input 能产生最好的 Output

Problem type 2: Modeling 建模

We have corresponding sets of inputs and outputs and seek model that delivers correct output for every known input

我们有一组相应的输入和输出，并寻求一个模型，该模型能针对每个已知的输入给出正确的输出

image-20260925175321256

Examples
- Classification of data, handwriting recognition数据分类、手写识别
- Predicting stock exchange price development预测股票价格走势
- Voice-control system for smart phone智能手机语音控制系统

Problem type 3: Simulation 模拟

We have a given model and wish to know the outputs that arise under different input conditions

我们已经有一个给定的模型，并希望知道在不同输入条件下会产生什么输出

Often used to answer “what-if” questions in evolving dynamic environments

模拟经常用于回答动态变化环境中的“如果……会怎样？”问题

image-20260925175610164

Examples:
- Evolutionary economics进化经济学
- Artificial life人工生命
- Impact analysis of a new tax system新税制的影响分析

  • Solving an optimization or a modeling problem requires the identification of a particular object in a space of possibilities

    解决一个optimization优化问题或者modeling建模问题，需要在一组可能性构成的空间中，找出一个特定的对象

  • This space can be, and usually is, enormous or even infinite

    这个空间可能非常巨大，而且通常确实非常巨大，甚至可能是无限的

  • Problem solving -> search

    问题求解 → 搜索

  • Search space: the collection of all objects of interest including the solution we are seeking

    Search space（搜索空间）：所有我们感兴趣的对象所组成的集合，其中也包含我们正在寻找的那个解

Optimization vs. constraint satisfaction优化问题 vs. 约束满足问题

  • Objective function: assigning a value to a solution that reflects its quality

    Objective function目标函数:给一个 solution 分配一个数值，用这个数值反映这个 solution 的质量。

    用来回答这个解有多好

  • Constraint: binary evaluation whether a given requirement holds or not

    约束：二元地判断某个要求是否满足。

    binary evaluation(二元地判断):True / False

    Constraints Objective function: Yes Objective function: No
    Yes Constrained optimization problem带约束的优化问题 Constraint satisfaction problem约束满足问题
    No Free optimization problem无约束优化问题 No problem

What does an EA need to solve a problem?一个进化算法（EA, Evolutionary Algorithm）要解决问题,需要哪些东西

  • A representation of candidate solutions

    一种表示候选解的方法。

  • A way to generate candidates

    一种产生候选解的方法。

  • A way to evaluate them

    一种评价这些候选解的方法

  • A way to select among them

    一种从这些候选解中进行选择的方法。

  • A way to handle constraints

    一种处理约束的方法

Questions we should be able to answer now

现在我们应该已经能够回答的问题

  1. What is evolutionary computing? 什么是进化计算？
Answer 答案 Evolutionary Computing (EC) is a class of computational methods inspired by natural evolution. It uses a population of candidate solutions and repeatedly applies evaluation, selection, and variation to improve the solutions.
进化计算（EC）是一类受到自然进化启发的计算方法。它使用一组候选解，并不断进行评价、选择和变异，从而逐步改进这些解。
  1. Why use it? 为什么要使用进化计算？
Answer 答案 Evolutionary Computing is useful for solving complex problems, especially when the search space is very large, difficult, noisy, dynamic, multimodal, or multi-objective.
进化计算适合用于解决复杂问题，特别是当搜索空间非常大，或者问题具有困难、噪声、动态变化、多峰或多目标等特点时。
  1. What is the basic abstraction? 基本抽象是什么？
Answer 答案 The basic abstraction is:基本抽象是:
Input → Model → Output
输入 → 模型 → 输出
Different problem types depend on which component is unknown. For example, optimization searches for the input, while simulation determines the output.
根据哪一个部分是未知的，可以形成不同的问题类型。例如，优化问题寻找合适的输入，而模拟问题是在已知输入和模型的情况下求输出。
  1. What is an individual in an EA? 在进化算法中，individual 是什么？
Answer / 答案 An individual in an Evolutionary Algorithm is one candidate solution to the problem. A collection of individuals forms a population.
在进化算法中，一个 individual 就是问题的一个候选解（candidate solution）。 许多个 individual 组成一个 population（种群）。
  1. What is fitness? 什么是 fitness？
Answer / 答案 Fitness is a value that represents the quality of a candidate solution.
Individuals with better fitness generally have a greater chance of being selected and contributing to future generations.
Fitness 是一个用来表示候选解质量的数值。
Fitness 更好的个体通常有更大的机会被选择，并对之后的世代产生影响。
  1. Why is search important? 为什么搜索很重要？
Answer / 答案 Search is important because the set of possible candidate solutions, called the search space, can be extremely large or even infinite.
Evolutionary Algorithms search this space to find good or optimal solutions without examining every possible solution.
搜索很重要，因为所有可能候选解组成的集合，也就是 search space（搜索空间），可能非常巨大，甚至是无限的。
进化算法通过在这个搜索空间中进行搜索，找到较好的或最优的解，而不需要检查每一个可能的解。