进化算法 遗传算法.ppt

1. Introduction to Genetic Algorithms
Institute of Intelligent Information Processing, XiDian University
优化问题
对于一个求函数最大值的优化问题，一般可描述为下述数学规划模型：
Soft Computing Lab.
2
XiDian UNIVERSITY
例：无约束单目标，多峰
Soft Computing Lab.
3
XiDian UNIVERSITY
约束单目标
Soft Computing Lab.
4
XiDian UNIVERSITY
约束多目标
Soft Computing Lab.
5
XiDian UNIVERSITY
TSP
旅行商问题（TSP,traveling salesman problem）
管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。
问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。（n-1)!/2
Soft Computing Lab.
6
XiDian UNIVERSITY
TSP
A
D
E
C
B
The one below is length: 33
A
B
C
D
E
A
5
7
4
15
B
5
3
4
10
C
7
3
2
7
D
4
4
2
9
E
15
10
7
9
Soft Computing Lab.
7
XiDian UNIVERSITY
传统最优化面临新挑战：实际问题
离散性问题——主要指组合优化
不确定性问题——随机性数学模型
半结构或非结构化的问题
大规模问题：超高维
动态优化问题
有噪的
现代优化方法：
追求满意—近似解
实用性强—解决实际问题
Soft Computing Lab.
8
XiDian UNIVERSITY
优化问题的复杂性
Complexity: Hard problems and Easy problems
When S is small (. 10, 100, or only 1,000,000 or so items), we can simply do so-called exhaustive search(穷举搜索)
Exhaustive search: Generate every possible solution, work out its fitness, and hence discover which is best (or which set share the best fitness) 比如从n个数找到最大
This is also called Enumeration(列举法）
Soft Computing Lab.
9
XiDian UNIVERSITY
问题的复杂度
This is all about characterising how hard it is to solve a given problem. Statements are made in terms of functions of n, which is meant to be some indication of the size of the problem. .:（通过n的一个函数来描述问题的复杂度）
Correctly sort a set of n numbers（排序）
Can be done in around n log n steps
Find the closest pair out of n vectors（从n个向量找出最接近两个)
Can be done in O(n2) steps
Find best multiple alignment of n sequences.
Can be done in O(2n) steps …
Soft Computing Lab.
10
XiDian UNIVERSITY