课程大纲

COURSE SYLLABUS

课程代码/名称

Course Code/Title

CSE5012 演化计算及其应用

CSE5012 Evolutionary Computation and Its Applications

课程性质

Compulsory/Elective

专业选修课

Major Elective Courses

课程学分/学时

Course Credit/Hours

授课语言

Teaching Language

中英文

Chinese & English

授课教师

Instructor(s)

姚新，讲席教授，计算机科学与工程系，

xiny@sustech.edu.cn

Xin Yao, Chair Professor, Department of Computer Science and

Engineering, xiny@sustech.edu.cn

是否面向本科生开放

Open to undergraduates

or not

是

先修要求

Pre-requisites

CS303 人工智能

CS303 Artificial Intelligence

教学目标

Course Objectives

本课程介绍演化计算领域的主要概念、技术和应用。学生将要学习演化计算中的几个重要元素：表

示、搜索算子和选择方案。搜索算子包括可在离散或连续搜索空间中使用的重组/交叉算子和变异

算子（非适应性或适应性变异步长和概率）。学生将要学习这些重组/交叉算子和变异算子如何单

独或者通过协同作用来高效率的搜索。选择方案包括基于适应度的选择、排序和轮盘选择算子。染

色体的表示（编码）包括离散型和连续型。处理约束的技术也会有所涉及。本课程也将介绍小生境

和种化、协同演化、多目标演化算法、演化学习以及相关理论知识。本课程还会给学生提供实践的

机会：了解何种情况下演化计算技术是实用的，如何在实际问题中使用这些技术，如何用不同的编

程语言实现这些技术。

This course introduces the main concepts, techniques, algorithms and applications of evolutionary

computation. Students will learn the core elements of evolutionary computation: representation,

search operators and selection schemes. Search operators include different recombination/crossover

operators and mutation operators (non-adaptive or adaptive mutation step-size and probability) for

discrete and continuous search spaces. The students will learn how the recombination/crossover

operators and mutation operators work individually or collaboratively for efficient search. Selection

schemes covered include fitness proportional selection, ranking and tournament selection.

Chromosome representations include both discrete and continuous cases. Constraint handling

techniques will be covered. Other topics covered in this course include niching and speciation, co-

evolution, multi-objective evolutionary optimisation, evolutionary learning, and theories. This course

will also give students some practical experience on when evolutionary computation techniques are

useful, how to use them in practice and how to implement them in different programming languages.

教学方法

Teaching Methods

理论与实践相结合。

Lectures and lab work.

教学内容

Course Contents

Section 1

第一周：演化计算导论

 为何研究自然计算？

 演化计算

 演化计算的历史分支

 演化计算的主要研究领域

[Lab 1] 编写一个简单的进化算法优化一个简单的无约束的函数。

Week 1. Introduction to Evolutionary Computation (EC)

o Why natural computation?

Evolutionary computation

o Different historical branches of EC

Major areas in EC

[Lab 1] Program a simple evolutionary algorithm for optimising a

simple function without constraints.

Section 2

第二周：离散型算子

 离散重组/交叉算子

 离散变异算子

 选择方案

[Lab 2] 比较不同的算子，如单点、多点和均匀交叉算子。

Week 2. Operators for Discrete Representation

o Recombination/Crossover operators

o Mutation operators

Selection schemes

[Lab 2] Compare one-point, multi-point, and uniform crossover

operators.

Section 3

第三周：实数型算子

 实数重组算子

 实数变异算子

 选择方案

 例：混合进化算法和局部搜索

[Lab 3] 比较适用于实数编码的选择方案。

Week 3. Operators for Real-valued Representation

Recombination for real-valued representation

o Mutation for real-valued representation

Selection for real-valued representation

o Example: a hybrid EA with local search

[Lab 3] Compare different selection schemes for real-valued

representation.

Section 4

第四周：搜索算子和编码

 进化算法中的自适应性和参数控制

 编码的重要性

 受欢迎的进化算法变种

[Lab 4] 了解自适应变异算子的控制参数的影响。

Week 4. Search Operators and Representations

o Self-adaptation and parameter control in evolutionary

algorithms (EAs)

Representation is important

o Population EA variants

[Lab 4] Understand the impact of control parameter(s) of self-

adaptive mutators.

Section 5

第五周：组合进化优化

 关于组合进化优化的介绍

 进化算法在旅行家问题的应用

 进化算法在切料问题的应用

[Lab 5] 设计和实现一个进化算法解决旅行家问题。

Week 5. Evolutionary Combinatorial Optimisation

Introduction to combinatorial optimisation

Travelling salesman problem

o Cutting stock problem

[Lab 5] Design and implement an evolutionary algorithm to solve the

travelling salesman problem.

Section 6

第六周：学生作业报告（计分）

[Lab 6] （继续）学生作业报告（计分）。

Week 6. Presentation of Assignment (marked)

[Lab 6] (Continued) Presentation of Assignment (marked).

Section 7

第七周：种群多样性、小生境技术和种化

 小生境的动机

 不同的小生境技术

 适应性分享

 拥挤和种化

[Lab 7] 在多峰问题下比较不同的小生境技术。

Week 7. Population Diversity, Niching and Speciation

Why niching

o Different niching techniques

Fitness sharing

o Crowding and speciation

[Lab 7] Compare niching methods for multi-modal optimisation.

Section 8

第八周：期中考试

[Lab 8] 实现一个进化策略。

Week 8. Mid-term Test

[Lab 8] Implement a self-adaptive evolutionary strategy.

Section 9

第九周：多目标进化优化

 多目标优化和帕累托最优

 多目标进化算法

 从多目标到超多目标

 多目标学习

[Lab 9] 学习使用前沿的多目标进化优化软件 PlatEMO。

Week 9. Multi-objective Evolutionary Optimisation

o Multi-objective optimisation and pareto dominance

Multi-objective evolutionary algorithms (MOEAs)

o From Multi- to Many objective optimization

Multi-objective learning

[Lab 9] Practice with PlatEMO.

Section 10

第十周：学生作业报告（计分）

[Lab 10] （继续）学生作业报告（计分）。

Week 10. Presentation of Assignment (marked)

[Lab 10] (Continued) Presentation of Assignment (marked).

Section 11

第十一周：约束处理

 常见的惩罚方法

 随机排序

 修复方法

 特殊的编码和算子

[Lab 11] 在为旅行家问题设计的进化算法上使用惩罚机制和修复方

法。

Week 11. Constraint Handling

o Common penalty methods

Stochastic ranking

o Repair functions

o Special representations and operators

[Lab 11] Apply penalty methods and repair methods to the

evolutionary algorithm designed for a travelling salesman problem.

Section 12

第十二周：遗传编程

 作为个体的树

 遗传编程的主要步骤和算子

 适用于树的搜索算子

 多目标遗传编程

[Lab 12] 使用遗传编程自动演化奇偶校验函数。

Week 12. Genetic Programming

o Trees as individuals

Major steps of genetic programming and its operators

o Multi-objective genetic programming

[Lab 12] Genetic programming for evolving parity functions.

Section 13

第十三周：演化学习

 基本思想和动机

 可信度赋值（信用分配）和两种主要的演化学习方法

 演化规则系统

 演化神经网络

[Lab 13] 设计和实现一个学习分类系统。

Week 13. Evolutionary Learning (EL)

Basic ideas and motivations

o Credit assignment and two major approaches to EL

Evolving rule-based systems

o Evolving neural networks

[Lab 13] Design and implement a learning classifier system.

Section 14

第十四周：学生作业报告（计分）

[Lab 14] （继续）学生作业报告（计分）。

Week 14. Presentation of Assignment (marked)

[Lab 14] (Continued) Presentation of Assignment (marked).

Section 15

第十五周：协同演化

 理论框架

 一般性框架举例

 估计协同演化学习的一般性

[Lab 15] 协同演化在其它领域的概念和应用。

Week 15. Co-evolution

o Theoretical framework

Examples of generalisation framework

o Estimating generalisation in co-evolutionary learning

[Lab 15] The concept of co-evolution in other fields.

Section 16

第十六周：进化计算的理论分析

 收敛和收敛速率

 计算时间复杂度

 没有免费的午餐（定理）

 模式定理

 适应度地形的表征

[Lab 16] 分析一个简单进化算法在一个二进制优化问题上的时间复杂

度。

Week 16. Theoretical Analysis of Evolutionary Algorithms

o Convergence and convergence rate

Computational time complexity

o No free lunch theorem

o Schema theorems

Fitness landscape characterisation

[Lab 16] Runtime analysis of a simple EA for a binary optimsation

problem.

10.

课程考核

Course Assessment

考试及作业：

 作业

关于演化计算的报告（30%）

算法设计、程序和论文（30%）

 考试

o 闭卷期中考试（20%）

o 闭卷期末考试（20%）

Exams and assignments:

 Assignments

Presentations about evolutionary computation（30%）

o Algorithm design, programs and reports（30%）

 考试

o Unseen mid-term test（20%）

o Unseen final exam（20%）

11.

教材及其它参考资料

Textbook and Supplementary Readings

Books:

T. Baeck, D. B. Fogel, and Z. Michalewicz (eds.). Handbook of Evolutionary Computation, IOP Publ. Co.

& Oxford University Press, 1997. Part A.

Z Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs (3rd edition), Springer-

Verlag, Berlin, 1996.

X. Yao (ed). Evolutionary Computation: Theory and Applications. World Scientific Publ. Co.,

Singapore, 1999. (ISBN 3-540-65907-2)

W Banzhaf, P Nordin, R E Keller & Frank D Francone. Genetic Programming: An Introduction. Morgan

Kaufmann, 1999.

Supplementary readings:

Various articles in journals and conference proceedings, including, but not limited to:

X. Yao (1996b), ``An overview of evolutionary computation,'' Chinese Journal of Advanced Software

Research (Allerton Press, Inc., New York, NY 10011), 3(1):12-29, 1996.

K.-H. Liang, X. Yao and C. S. Newton, ``Combining landscape approximation and local search in global

optimization,'' Proc. of the 1999 Congress on Evolutionary Computation, Vol. 2, IEEE Press,

Piscataway, NJ, USA, pp.1514-1520, July 1999.

X. Yao, Y. Liu and G. Lin, `` Evolutionary programming made faster,'' IEEE Transactions on

Evolutionary Computation, 3(2):82-102, July 1999.

K.-H. Liang, X. Yao, C. S. Newton and D. Hoffman, ``A New Evolutionary Approach to Cutting Stock

Problems with and Without Contiguity,'' Computers and Operations Research, 2001.

P. Darwen and X. Yao (1995a), `` A dilemma for fitness sharing with a scaling function,'' Proc. of 1995

IEEE Conference on Evolutionary Computation (ICEC'95), Perth, Australia, IEEE Press, pp.166-171.

P. Darwen and X. Yao (1996b), `` Every niching method has its niche: fitness sharing and implicit

sharing compared,'' Proc. of Parallel Problem Solving from Nature (PPSN) IV, Vol.1141, Lecture Notes

in Computer Science, Springer-Verlag, Berlin, pp.398-407, 1996.

Pollack, J, Blair, A. and Land, M. (1996). Coevolution of A Backgammon Player. Proceedings Artificial

Life V, C. Langton, (Ed), MIT Press.

Juillé, H. and Pollack, J. B. (1996). Dynamics of Co-evolutionary Learning. Proceedings of the Fourth

International Conference on Simulation of Adaptive Behavior, Cape Cod, MA, September 9 - 13, 1996,

MIT Press, pp. 526-534.

Juillé, H. and Pollack, J. B. (1996). Co-evolving Intertwined Spirals. Proceedings of the Fifth Annual

Conference on Evolutionary Programming, San Diego, CA, February 29 - March 2, 1996, MIT Press, pp.

461-468.

Poon, J. and Maher, M.L. (1996). Emergent Behaviour in Co-Evolutionary Design. in JS Gero (ed)

Artificial Intelligence in Design '96, Kluwer Academic.

C. A. Ceollo Ceollo, "Self-adaptive penalties for GA-base optimization," Proceedings of the 1999

Congress on Evolutionary Computation (CEC'99), volume I, pp.573-580, IEEE Press, USA.

Z. Michalewicz and M. Schoenauer, "Evolutionary Algorithms for Constrained Parameter Optimization

Problems," Evolutionary Computation, 4(1), 1996.

T. Baeck, D. B. Fogel, and Z. Michalewicz (eds.), Handbook of Evolutionary Computation, IOP Publ. Co.

& Oxford University Press, 1997. Sections C5.1 and C5.6

T. P. Runarsson and X. Yao, ``Stochastic Ranking for Constrained Evolutionary Optimization,'' IEEE

Transactions on Evolutionary Computation, 4(3):284-294, September 2000.