A4.3.7 · Machine learning approaches (HL only)
A4.3.7 · 机器学习方法(仅 HL)
Genetic Algorithms
遗传算法
A delivery courier could try every possible order to visit five towns, but the number of routes explodes as more towns are added. A genetic algorithm instead breeds a population of routes, keeping the better ones and combining them, the way evolution favours a fitter trait.
一名送货员本可以尝试所有可能的顺序去拜访五个镇,但随着镇的数量增加,可能的路线数量会爆炸式增长。遗传算法转而"培育"一群路线,保留较好的那些并把它们组合起来,就像进化偏爱更适应的性状一样。
Unlike the earlier statements in A4.3, a genetic algorithm is not a way of learning from data at all; it is a search and optimisation technique, useful whenever the space of possible solutions is far too large to check exhaustively.
与 A4.3 之前的几条考纲陈述不同,遗传算法根本不是一种从数据中学习的方式;它是一种搜索和优化技术,当可能解的空间大到无法逐一穷举检查时就很有用。
Explainer
讲解
Borrowing from natural selection
借鉴自然选择
A genetic algorithm keeps a population of candidate solutions, scores each one with a fitness function, and repeatedly builds a new population using selection (fitter individuals are more likely to be chosen), crossover (combining parts of two solutions) and mutation (a small random change), until a good enough solution is found or a stopping point is reached.
遗传算法维护一群候选解构成的种群,用一个适应度函数为每一个打分,然后反复利用选择(更适应的个体更有可能被选中)、交叉(组合两个解的一部分)和变异(一次小的随机改变)来构建新的种群,直到找到足够好的解或达到停止条件。
| Term | Meaning |
|---|---|
| Population | A set of candidate solutions (individuals) to the problem |
| Fitness function | A score for how good a solution is; higher is better |
| Selection | Choosing which individuals get to reproduce, weighted toward higher fitness |
| Crossover | Combining parts of two parent solutions into a new offspring solution |
| Mutation | A small random change to an individual, keeping the population diverse |
| Termination | The stopping rule: a generation limit, a time limit, or "good enough" fitness reached |
| 术语 | 含义 |
|---|---|
| 种群 | 问题的一组候选解(个体) |
| 适应度函数 | 为一个解的好坏打分;分数越高越好 |
| 选择 | 决定哪些个体能够繁殖,倾向于适应度更高的个体 |
| 交叉 | 把两个父代解的一部分组合成一个新的子代解 |
| 变异 | 对一个个体做一次小的随机改变,以保持种群的多样性 |
| 终止 | 停止规则:代数上限、时间限制,或已达到"足够好"的适应度 |
Worked example
例题
Evolving a delivery route
演化出一条配送路线
A courier must visit Ashgrove (A), Bellmont (B), Cedarville (C) and Dunmore (D) and return to the depot. Fitness is 1 ÷ total distance, so a shorter route scores higher.
一名送货员必须走遍 Ashgrove (A)、Bellmont (B)、Cedarville (C) 和 Dunmore (D),再回到仓库。适应度是 1 ÷ 总距离,所以路线越短,分数越高。
Explainer
讲解
Where genetic algorithms are used
遗传算法用在哪里
| Application | What is being evolved |
|---|---|
| Route planning / logistics | The order in which stops are visited, minimising total distance or time (the travelling salesperson problem) |
| Scheduling | The assignment of tasks or shifts to time slots, minimising conflicts or cost |
| Engineering design | The physical layout of a system (e.g. turbine placement in a wind farm), maximising output against cost |
| Control systems / robotics | The parameters of a controller, maximising stability or performance |
| 应用 | 被演化的是什么 |
|---|---|
| 路线规划 / 物流 | 访问各站点的顺序,使总距离或时间最小(旅行推销员问题) |
| 排班调度 | 把任务或班次分配到时间段,使冲突或成本最小 |
| 工程设计 | 系统的物理布局(例如风电场中涡轮机的摆放),在成本约束下使产出最大 |
| 控制系统 / 机器人 | 控制器的参数,使稳定性或性能最大 |
Check your understanding
检验你的理解
A route [Ashgrove, Bellmont, Cedarville, Dunmore] is changed to [Ashgrove, Dunmore, Cedarville, Bellmont] by swapping two stops, with no other route involved. Which genetic operator is this?
一条路线 [Ashgrove, Bellmont, Cedarville, Dunmore] 通过交换两个站点变成了 [Ashgrove, Dunmore, Cedarville, Bellmont],没有涉及其他路线。这是哪一种遗传算子?
Common mistake
常见错误
RecurringDescribing a genetic algorithm as "trying random solutions until one works". Random routes ARE generated, but only in the very first population. After that, selection weighted by fitness means fitter solutions are far more likely to be chosen as parents, and crossover deliberately recombines the successful parts of good solutions rather than starting over. Mutation adds only a small amount of randomness, to avoid getting stuck, not to drive the whole search.
反复出现把遗传算法描述成"随机尝试各种解,直到有一个可行"。随机路线的确会被生成,但只在最初的那一代种群中。之后,按适应度加权的选择意味着更适应的解被选为父代的可能性大得多,而交叉是刻意重组好的解中成功的部分,而不是从头再来。变异只加入少量的随机性,是为了避免陷入停滞,而不是驱动整个搜索。
Wrong: "A genetic algorithm just keeps generating random routes until it happens to find a short one."
错误: "遗传算法只是不断生成随机路线,直到碰巧找到一条短的。"
Right: "Only the first generation is random. After that, fitter routes are more likely to be selected as parents, and crossover combines successful parts of two good routes into a new one, so the population improves generation by generation rather than searching blindly."
正确: "只有第一代是随机的。之后,更适应的路线更可能被选为父代,交叉把两条好路线中成功的部分组合成一条新的,所以种群是一代代改进的,而不是盲目搜索。"
Revision questions
复习题
Specimen-paper style. Write an answer, then reveal the marking points and mark yourself.
采用样卷风格。写下答案,然后展开评分要点给自己打分。
[2]Define what a fitness function does inside a genetic algorithm.
[2]在遗传算法的语境下定义适应度函数。
Marking points
评分要点
- A function that scores how good a candidate solution is.
- Used to guide selection, higher-fitness individuals are more likely to be chosen to reproduce.
- 一个为候选解打分、衡量其好坏的函数。
- 用来指导选择,适应度更高的个体更有可能被选中繁殖。
[4]Describe the roles of crossover and mutation in a genetic algorithm.
[4]描述交叉和变异在遗传算法中的作用。
Marking points
评分要点
- Crossover combines parts of two parent solutions to form a new offspring solution.
- It lets successful traits from two good solutions combine into a potentially better one.
- Mutation makes a small random change to an individual.
- It keeps the population diverse and helps avoid getting stuck at a solution that is only locally good.
- 交叉把两个父代解的一部分组合成一个新的子代解。
- 它让两个好解中成功的特性组合成一个可能更好的解。
- 变异对一个个体做一次小的随机改变。
- 它保持种群的多样性,有助于避免陷入一个只是局部较好的解。
[3]Describe one real-world application of genetic algorithms.
[3]描述遗传算法的一个现实应用。
Marking points
评分要点
- Named application, e.g. delivery route planning, staff scheduling, or wind turbine placement.
- States what is being represented as an individual in the population.
- States what the fitness function measures for that application.
- 指出一个具体应用,例如配送路线规划、员工排班,或风力涡轮机布局。
- 说明种群中的一个个体代表什么。
- 说明该应用中适应度函数衡量的是什么。
[3]Explain why a genetic algorithm is more likely than random guessing to find a good route as generations pass.
[3]解释为什么随着代数增加,遗传算法比随机猜测更有可能找到一条好路线。
Marking points
评分要点
- Selection is weighted by fitness, so fitter routes are more likely to become parents than a purely random choice would allow.
- Crossover combines successful parts of two good routes rather than generating an unrelated new route.
- Only mutation is random, and it is applied in small amounts, so the population improves generation by generation instead of resetting each time.
- 选择按适应度加权,所以更适应的路线成为父代的可能性,高于纯随机选择所允许的程度。
- 交叉组合两条好路线中成功的部分,而不是生成一条毫不相关的新路线。
- 只有变异是随机的,而且施加的幅度很小,所以种群是一代代改进的,而不是每次都从头重来。
Flashcards
记忆卡片
Active recall for this statement’s key terms.
针对本条考纲陈述关键术语的主动回忆练习。
Keep this statement’s practice with you
把这条考纲陈述的练习保存下来
Free account: save your progress and unlock every revision question for A4.3.7, and every other IB CS 2027 statement.
免费账户:解锁 A4.3.7 以及所有其他 IB CS 2027 考纲陈述的每一道复习题,并同步你的学习进度。