智能计算导论

1

1.1引言

1.1.1优化问题

1.1.2传统优化方法

1.1.3现代优化方法

1.2最优化问题及其分类

1.2.1函数优化问题

1.2.2组合优化问题

1.3启发式算法

1.3.1启发式算法的定义

1.3.2启发式算法的分类

1.3.3启发式算法的性能分析

1.4计算复杂性与NP完全问题

1.4.1计算复杂性的基本概念

1.4.2P,NP,NP-C和NP-hard

智能优化计算2

1.1引言

智能优化计算优化技术？以数学为基础，解决各种工程问题优化解优化技术的用途系统控制人工智能模式识别生产调度

……

1.1.1优化问题

3

1.1引言

智能优化计算最优化问题的描述

最优化问题的数学模型的一般描述：

1.1.1优化问题

4

1.1引言

智能优化计算待解决的问题

连续性问题，以微积分为基础，规模较小、多峰多谷传统的优化方法

理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。

传统的评价方法

算法收敛性、收敛速度

1.1.2传统优化方法

5

1.1引言

智能优化计算待解决的问题

离散性、不确定性、大规模现代的优化方法启发式算法（heuristicalgorithm）追求满意（近似解）实用性强（解决实际工程问题）现代的评价方法算法复杂性

1.1.3现代优化方法

6

1.2最优化问题及其分类（函数优化和组合优化）智能优化计算数学表述

难点高维多峰值

1.2.1函数优化问题

7

1.2.2常见求解方法

1.一维函数优化

优选法：黄金分割法、分数法、正交实验设计特点：只能解决单峰函数的最优值问题搜索法：按照某种方向（如最速下降方向、梯度方向）选取步长搜索（是一种迭代技术）2.多维函数优化

特点：迭代+搜索选取初始点、按照某个方向（如最速下降方向、梯度方向）选取步长搜索最速下降法、梯度与共轭梯度法、Newton法（拟Newton法）等等一般只能解决单峰函数的最优化问题（why?)8

测试函数（8）GeneralizedSchwefel’sProblem2.26(multimodal)典型的多峰、多谷函数，确定性算法求解很可能导致局部最优9

1.2最优化问题及其分类

智能优化计算（1）SphereModel(unimodal)

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题

10

1.2最优化问题及其分类

智能优化计算测试函数（2）Schwefel’sProblem2.22(unimodal)

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题11

1.2最优化问题及其分类

智能优化计算测试函数（3）Schwefel’sProblem1.2

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题12

1.2最优化问题及其分类

智能优化计算测试函数（4）Schwefel’sProblem2.21

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题13

1.2最优化问题及其分类

智能优化计算测试函数（5）GeneralizedRosenbrock’sFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题14

1.2最优化问题及其分类

智能优化计算测试函数（6）StepFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题15

1.2最优化问题及其分类

智能优化计算测试函数（6）StepFunction

1.2.3函数优化之常见的Benchmark问题16

1.2最优化问题及其分类

智能优化计算测试函数（7）QuarticFunctioni.e.Niose

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题17

1.2最优化问题及其分类

智能优化计算测试函数（8）GeneralizedSchwefel’sProblem2.26

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题18

1.2最优化问题及其分类

智能优化计算测试函数（8）GeneralizedSchwefel’sProblem2.26(multimodal)

1.2.3函数优化之常见的Benchmark问题19

1.2最优化问题及其分类

智能优化计算测试函数（9）GeneralizedRastrigin’sFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题20

1.2最优化问题及其分类

智能优化计算测试函数（10）Ackley’sFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题21

1.2最优化问题及其分类

智能优化计算测试函数（10）Ackley’sFunction

1.2.3函数优化之常见的Benchmark问题22

1.2最优化问题及其分类

智能优化计算测试函数（11）GeneralizedGriewankFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题23

1.2最优化问题及其分类

智能优化计算测试函数（11）GeneralizedGriewankFunction

1.2.3函数优化之常见的Benchmark问题24

1.2最优化问题及其分类

智能优化计算测试函数（12）GeneralizedPenalizedFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题25

1.2最优化问题及其分类

智能优化计算测试函数其中，

1.2.3函数优化之常见的Benchmark问题26

1.2最优化问题及其分类

智能优化计算测试函数（13）GeneralizedPenalizedFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题27

1.2最优化问题及其分类

智能优化计算测试函数（14）Shekel’sFoxholesFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题28

1.2最优化问题及其分类

智能优化计算测试函数其中，

1.2.3函数优化之常见的

Benchmark问题29

1.2最优化问题及其分类

智能优化计算测试函数（15）Kowalik’sFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题30

1.2最优化问题及其分类

智能优化计算测试函数其中，

1.2.3函数优化之常见的Benchmark问题31

1.2最优化问题及其分类

智能优化计算测试函数（16）Six-HumpCamel-BackFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题32

1.2最优化问题及其分类

智能优化计算测试函数（17）BraninFunction

其最优状态和最优值为

1.2.3函数优化之常见的

Benchmark问题33

1.2最优化问题及其分类

智能优化计算测试函数（18）Goldstein-PriceFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题34

1.2最优化问题及其分类

智能优化计算测试函数（19）Hartman’sFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题35

1.2最优化问题及其分类

智能优化计算测试函数（20）Hartman’sFunction

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题36

1.2最优化问题及其分类

智能优化计算测试函数（21）Shekel’sFamily

m分别取5，7和10，其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题37

1.2最优化问题及其分类

智能优化计算测试函数（22）J.D.Schaffer

其最优状态和最优值为

1.2.3函数优化之常见的Benchmark问题38

1.2最优化问题及其分类

智能优化计算测试函数（22）J.D.Schaffer

此函数在距全局最优点大约3.14范围内存在无穷多个局部极小将其包围，并且函数强烈振荡。

1.2.3函数优化之常见的Benchmark问题39

1.2最优化问题及其分类

智能优化计算有约束的函数优化常用受约束测试函数；影响因素：（1）曲面拓扑性质，线性或凸函数比无规律的函数更容易求解；（2）可行区域的疏密程度，通常以可行区域占整个搜索空间的比值来度量；

1.2.3函数优化之常见的Benchmark问题40

1.2最优化问题及其分类

智能优化计算有约束的函数优化常用受约束测试函数；影响因素：（3）整个搜索空间中整体最优解与可行区域最优解之比，特别当整体最忧解离可行区域很近时将使其对惩罚项非常敏感；（4）在最优解处活跃约束的数目，活跃约束数目越多则最优解离可行区域的边界越近。

1.2.3函数优化之常见的Benchmark问题41

1.2最优化问题及其分类

智能优化计算数学表述所属范畴涉及离散事件的最优编排、分类、次序筛选等问题，是运筹学的一个重要分支。

1.2.4组合优化问题

42

1.2最优化问题及其分类

智能优化计算典型问题——旅行商问题（Travelingsalesmanproblem,TSP）给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。

1.2.2组合优化问题

12341218103243TSP问题实例10城市TSP问题20城市TSP问题44TSP问题实例230城市TSP问题48城市TSP问题45

1.2最优化问题及其分类

智能优化计算典型问题——旅行商问题（Travelingsalesmanproblem,TSP）计算复杂度：指数灾难

1.2.2组合优化问题

城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325year46

1.2最优化问题及其分类

智能优化计算典型问题——加工调度问题（Schedulingproblem,如Flow-shop,Job-shop）

Job-shop：n个工件在m台机器上加工，Oij：第i个工件在第j台机器上的操作，Tij：相应的操作时间已知。事先给定各工件在各机器上的加工次序（技术约束条件），要求确定与技术约束条件相容的各机器上所有工件的加工顺序，使得加工性能指标达到最优。若各工件技术约束条件相同，转化为Flow-shop。

1.2.2组合优化问题

47

1.2最优化问题及其分类

智能优化计算典型问题——加工调度问题（Schedulingproblem,如Flow-shop,Job-shop）计算复杂性：可能的排列方式有（n！）m

多目标优化动态性状态相依

1.2.2组合优化问题

48

1.2最优化问题及其分类

智能优化计算典型问题——0－1背包问题（Knapsackproblem）对于n个体积为ai、价值分别为ci的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大。

1.2.2组合优化问题

背包问题的贪婪算法49

1.2最优化问题及其分类

智能优化计算典型问题——装箱问题（Binpackingproblem）有n个尺寸不超过1的物品，有数个尺寸为1的箱子，如何将这些物品装入箱子，使得所需箱子的个数最少。

1.2.2组合优化问题

50

1.2最优化问题及其分类

智能优化计算典型问题——图着色问题（Graphcoloringproblem）对于n个顶点的无环图G，要求对其各个顶点进行着色，使得任意两个相邻的顶点都有不同的颜色，且所用颜色种类最少。

1.2.2组合优化问题

C1：第一种颜色C2：第二种颜色C3：第三种颜色C1C1C2C3C2ABDCE51

1.2最优化问题及其分类

智能优化计算典型问题——聚类问题（Clusteringproblem）

m维空间上的n个模式{Xi|i=1,2,…,n}，要求聚成k类，使得各类本身内的点最相近，如要求其中Rp为第p类的中心，即

其中，p=1,2,…,k，np为第p类中的点数。

1.2.2组合优化问题

52

1.2最优化问题及其分类

智能优化计算典型问题——任务分配问题（TaskAssignmentProblemTAP）

TAP是把一个应用程序（application)的任务（Tasks）分配到分布式计算系统中的计算机上，目标是优化某个或某几个性能指标。

1.2.2组合优化问题

53

1.2最优化问题及其分类

智能优化计算典型问题——任务分配问题（TAP）

1.2.2组合优化问题

54

1.2最优化问题及其分类

智能优化计算

1.2.2组合优化问题

典型问题——任务分配问题（TAP）

应用程序用任务交互图（TaskInteractionGraphTIG）G(V,ET)表示，其中V=(1,2,…m)表示任务集合，ET表示边的集合，每条边表示任务之间的交互（通信）。55

1.2最优化问题及其分类

智能优化计算

1.2.2组合优化问题

典型问题——任务分配问题（TaskAssignmentProblemTAP）

分布式计算系统用处理机交互图（ProcessorsInteractionGraphPIG）G(P,ET)表示，其中P=(1,2,…n)表示系统中处理机的集合，ET表示通信链路的集合，每条边表示一条通信链路。56

1.2最优化问题及其分类

智能优化计算

1.2.2组合优化问题

典型问题——任务分配问题（TaskAssignmentProblemTAP）

我们这里仿真局域网分布式计算系统。并假设处理机异构（Heterogeneous）,及每个任务在各个处理机上的执行时间不同；网络同构，即所有链路的通信速度相同。

57

智能优化计算

1.2.2组合优化问题

典型问题——任务分配问题（TAP）

优化目标1：最小化执行代价与通信代价之和1.2最优化问题及其分类任务执行代价：处理机之间的通信代价：58

1.2最优化问题及其分类智能优化计算

1.2.2组合优化问题

典型问题——任务分配问题（TAP）

优化目标1：最小化执行代价与通信代价之和分配方案A总代价：TAP的目标是找到一种具有最小代价的分配方案：59

1.2最优化问题及其分类智能优化计算

1.2.2组合优化问题

典型问题——任务分配问题（TAP）也可描述为有约束的0-1二次整数规划问题：其中r是任务数，n是处理机数，mi是任务i的存储需求，pi是任务i的计算负载需求。60

智能优化计算

1.2.2组合优化问题

典型问题——任务分配问题（TAP）

优化目标2：最小化周转时间（turnaroundtime)1.2最优化问题及其分类分配到处理机k上的任务总的执行代价：分配到处理机k上的任务与分配到其它处理机上的任务总的通信代价：61

智能优化计算

1.2.2组合优化问题

典型问题——任务分配问题（TAP）

优化目标2：最小化周转时间（turnaroundtime)1.2最优化问题及其分类对于某一给定的分配方案A，处理机k总的执行代价：62

智能优化计算

1.2.2组合优化问题

典型问题——任务分配问题（TAP）

优化目标2：最小化周转时间（turnaroundtime)1.2最优化问题及其分类一个分配方案的最终代价（finalcost）由具有最大Ctotal(A)值的处理机,即由负载最重的处理机决定：此时，TAP的目标是找到一种具有最小代价的分配方案，即负载尽量均衡：63

1.3启发式算法（Heuristic）

智能优化计算最优算法一个问题的最优算法求得该问题每个实例的最优解；启发式算法一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下给出待解决优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。

1.3.1启发式算法的定义

64

1.3启发式算法

智能优化计算启发式算法的特点是一种技术；不能保证所得解的最优性；启发式算法的发展历史

20世纪40年代——起步

20世纪60～70年代——被鄙视

20世纪70年代——观点转变

20世纪80年代至今——研究热潮

1.3.1启发式算法的定义

65

1.3启发式算法

智能优化计算例子——背包问题的贪婪算法（Greedyalgorithm）

贪婪算法：采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedycriterion）。

1.3.1启发式算法的定义

66

1.3启发式算法

智能优化计算例子——背包问题的贪婪算法（Greedyalgorithm）STEP1STEP2

1.3.1启发式算法的定义

67

1.3启发式算法

智能优化计算启发式算法的优点

1.模型误差、数据不精确性、参数估计误差等可能造成最优算法的解比启发式算法的解更差；

2.复杂问题无法求得最优算法或最优算法太复杂；

3.简单易行，直观，程序简单。启发式算法的缺点

1.不能保证最优；

2.不稳定；

3.依赖于实际问题、设计者经验。

1.3.1启发式算法的定义

68

1.3启发式算法

智能优化计算简单直观的算法

一步算法：不在两个可行解之间比较，在未终止的迭代过程中，得到的中间解有可能不是可行解；例：背包问题的贪婪算法

改进算法：迭代过程是从一个可行解到另一个可行解变换，通过两个解的比较而选择好的解，直到满足一定的要求为止；例：TSP问题的2－opt方法

1.3.2启发式算法的分类

P1P6P2P5P3P42203122224434369

1.3启发式算法

智能优化计算

数学规划算法用连续优化（如线性规划）的方法求解组合优化问题（如整数线性规划模型），其中包括一些启发式规则。基于数学规划的理论。

1.3.2启发式算法的分类

70

1.3启发式算法

智能优化计算现代优化算法禁忌搜索算法模拟退火算法遗传算法人工神经网络蚁群算法粒子群算法混合算法

1.3.2启发式算法的分类

特点：基于客观世界中的一些自然现象；建立在计算机迭代计算的基础上；具有普适性，可解决实际应用问题。71

1.3启发式算法

智能优化计算评价算法优劣的指标算法的复杂性（计算效率）解的偏离程度（计算效果）算法的稳健性（不同实例、不同时间、不同起点的差异）评价算法优劣的手段最坏情况分析（纯理论）概率分析（理论分析）计算模拟分析（统计特性）

1.3.3启发式算法的性能分析

72

1.4计算复杂性与NP完全问题

智能优化计算时间复杂性和空间复杂性概念

算法的时间复杂性：算法对时间的需要量（加、减、乘、除、比较、读、写等操作的总次数）；

算法的空间复杂性：算法对空间的需要量（存储空间的大小，二进制位数）；

问题的时间复杂性：所有算法中时间复杂性最小的算法时间复杂性；

问题的空间复杂性：所有算法中空间复杂性最小的算法空间复杂性；

1.4.1计算复杂性的基本概念

73

1.4计算复杂性与NP完全问题

智能优化计算复杂性问题分类

P类、NP类、NP完全类复杂性表示方法复杂性表示为问题规模n（如TSP的n）的函数，时间复杂性T(n)，关键操作的次数；空间复杂性S(n)，占用的存储单元数量；

1.4.1计算复杂性的基本概念

74

1.4计算复杂性与NP完全问题

智能优化计算复杂性表示方法若算法A的时间复杂性为TA(n)=O(p(n))，O(p(n))为复杂性函数p(n)主要项的阶，且p(n)为n的多项式函数，则称算法A为多项式(polynomial)算法。

当不存在多项式函数p(n)时，称相应的算法为非多项式时间算法或指数时间算法；随着变量的增加，多项式函数增长的速度比指数函数和非多项式函数增长的速度要慢得多。

1.4.1计算复杂性的基本概念

75

1.4计算复杂性与NP完全问题

智能优化计算P类问题（deterministicpolynomial）

具有多项式时间求解算法的问题类迄今为止，许多组合优化问题都没有找到求最优解的多项式时间算法。NP类问题(Nondeterministicpolynomial)

定义1实例是问题的特殊表现，所谓实例就是确定了描述问题特性的所有参数的问题，其中参数值称为数据，这些数据占有计算机的空间称为实例的输入长度。

1.4.2P,NP,NP-C和NP-hard

76

1.4计算复杂性与NP完全问题

智能优化计算NP类问题(Nondeterministicpolynomial)

定义2若一个问题的每个实例只有“是”或“否”两种回答，则称该问题为判定问题。例，TSP的判定问题：给定z，是否存在n个城市的一个排列W，使得f(W)≤z。满足f(W)≤z的一个排列W称为判定问题的“是”答案（可行解）。

1.4.2P,NP,NP-C和