《智能优化方法》由会员分享，可在线阅读，更多相关《智能优化方法（75页珍藏版）》请在金锄头文库上搜索。
1、智能优化方法Nature Inspired Computation考核方式考核方式n课程设计报告课程设计报告n用一种（或多种）智能优化方法，实现实际或者虚用一种（或多种）智能优化方法，实现实际或者虚拟优化问题的求解。拟优化问题的求解。n鼓励与本人未来研究领域的结合。鼓励与本人未来研究领域的结合。n报告形式：小论文或实验报告的形式，要求包含：报告形式：小论文或实验报告的形式，要求包含：实验目的、技术方案、量化的实验结果、对结果的实验目的、技术方案、量化的实验结果、对结果的简单分析（或解释）。简单分析（或解释）。n提交源程序。提交源程序。n12月月4日前，将日前，将1份打印件放到我的信箱里。份打印
2、件放到我的信箱里。课程资源课程资源nftp:/202.38.67.66nUsername: networksnPassword: networksn参考教材：参考教材：n1.智能优化算法及其应用智能优化算法及其应用，王凌，清华版。，王凌，清华版。n2.遗传算法及其应用遗传算法及其应用，陈国良等，人民邮，陈国良等，人民邮电版，电版，1999。第一章第一章 概述概述n最优化问题的定义最优化问题的定义n最优化问题的分类最优化问题的分类n关于计算复杂性关于计算复杂性n最优化方法的一般结构最优化方法的一般结构最优化问题的定义最优化问题的定义最优化问题的一般形式为最优化问题的一般形式为 其中其中x Rn是
3、决策变量，是决策变量，f(x)为目标函数，为目标函数，X Rn为约束集或可行集。特别地，如果约束集为约束集或可行集。特别地，如果约束集 X = Rn，则最优化问题称为无约束最优化问题，则最优化问题称为无约束最优化问题 不仅限于不仅限于实数集实数集不一定能表示为不一定能表示为一数学表达式一数学表达式最优化问题的定义最优化问题的定义约束最优化问题通常写为约束最优化问题通常写为 这里这里E 和和I 分别是等式约束的指标集和不等式分别是等式约束的指标集和不等式约束的指标集，约束的指标集，ci(x)是约束函数是约束函数最优化问题的分类最优化问题的分类按照运筹学的观点分类：按照运筹学的观点分类：n线性规划
4、线性规划n非线性规划非线性规划n整数规划整数规划n动态规划动态规划n多目标规划多目标规划n。最优化问题的分类最优化问题的分类从应用的角度分类：从应用的角度分类：n数值优化（函数优化，建模）数值优化（函数优化，建模）n组合优化组合优化n可靠性设计问题可靠性设计问题n调度问题调度问题n高级运输问题高级运输问题n网络设计与路径网络设计与路径n有限资源的有限资源的最优调配最优调配最优化问题举例最优化问题举例(1)n函数优化函数优化令令 S 为为 Rn 上的有界子集，上的有界子集，f: SR 为为 n 维实值维实值函数，所谓函数函数，所谓函数 f 在在 S 域上全局最大化就是寻域上全局最大化就是寻求点求
5、点 Xmax S 使得使得函数优化问题函数优化问题函数优化问题函数优化问题函数优化问题函数优化问题最优化问题举例最优化问题举例(2)n系统建模系统建模n给定模型的结构给定模型的结构f(x)和决策变量的定义域；和决策变量的定义域；n给定实际系统的输入和输出样本数据；给定实际系统的输入和输出样本数据；n寻找一组最优决策变量，使得模型在测试样寻找一组最优决策变量，使得模型在测试样本集上的输出误差最小。本集上的输出误差最小。最优化问题举例最优化问题举例(3)n组合优化组合优化定义：组合优化问题定义：组合优化问题是一个最小化问题，或是一个最大是一个最小化问题，或是一个最大化问题，它由下面三部分组成：化问
6、题，它由下面三部分组成：(1)实例集合；实例集合；(2)对每一个实例对每一个实例 I，有一个有穷的可行解集合有一个有穷的可行解集合 S(I)；(3)目标函数目标函数 f，它对每一个实例它对每一个实例 I 和每一个可行解和每一个可行解 ，赋以一个有理数，赋以一个有理数 。 组合优化问题组合优化问题n一个通俗的定义：一个通俗的定义：所谓组合优化，是指在所谓组合优化，是指在离散的离散的、有限的数学结构上，、有限的数学结构上，寻找一个（或一组）满足给定寻找一个（或一组）满足给定约束条件约束条件并使其目标函并使其目标函数值达到最大或最小的解。数值达到最大或最小的解。般来说，组合优化问题般来说，组合优化问
7、题通常带有大量的局部极值点，往往是不可微的、不连通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的续的、多维的、有约束条件的、高度非线性的NPNP完全完全（难）问题（难）问题，因此，精确地求解组合优化问题的全局，因此，精确地求解组合优化问题的全局最优解的最优解的“有效有效”算法一般是不存在的。算法一般是不存在的。组合优化问题组合优化问题n集覆盖问题（集覆盖问题（set-covering problem）n装箱问题（装箱问题（bin-packing problem）n背包问题（背包问题（knapsack problem）n指派问题（指派问题（assignmen
8、t problem）n旅行商问题（旅行商问题（traveling salesman problem）n影片递送问题（影片递送问题（film delivery problem）n最小生成树问题（最小生成树问题（minimum span tree problem）n图划分问题（图划分问题（graph partitioning problem）n作业调度问题（作业调度问题（job-shop scheduling problem）组合优化问题组合优化问题集覆盖问题集覆盖问题n集覆盖问题集覆盖问题（set-covering problem）n对于一个对于一个m行行n列的列的01矩阵矩阵A，每行代表一种任
9、务，每列每行代表一种任务，每列代表一个人，代表一个人，aij=1表示第表示第j个人能完成第个人能完成第i个任务。每个人都个任务。每个人都有一个雇佣代价。问题的目标是：用最小的代价选择一些有一个雇佣代价。问题的目标是：用最小的代价选择一些人（矩阵的列），使得每一个任务都至少有一个人能完成。人（矩阵的列），使得每一个任务都至少有一个人能完成。n设向量设向量x的元素的元素 xj=1 表示列表示列 j 被选中（费用是被选中（费用是cj0），）， xj=0 则表示其未被选中（则表示其未被选中（j=1,2,n）。）。n已经证明集覆盖问题是已经证明集覆盖问题是NP完全问题完全问题。组合优化问题组合优化问题集
10、覆盖问题集覆盖问题n如果所有费用如果所有费用cj都相同，则问题称为单一费用问题都相同，则问题称为单一费用问题（unicost set-covering problem）。）。如果为等式约束，如果为等式约束，则称为集划分问题（则称为集划分问题（set partitioning problem）组合优化问题组合优化问题集覆盖问题集覆盖问题nCost = 291 0 1 0 1 0组合优化问题组合优化问题装箱问题装箱问题n装箱问题装箱问题（bin packing problem）所装物品不得超过箱所装物品不得超过箱子的容积子的容积一个物品只能放一个物品只能放入一个箱子入一个箱子用最少的箱子将用最少的
11、箱子将所有物品都装下所有物品都装下组合优化问题组合优化问题装箱问题装箱问题n货运装箱问题货运装箱问题n截铜棒问题截铜棒问题n布匹套裁问题布匹套裁问题n。n装箱问题属于装箱问题属于NP难问题难问题组合优化问题组合优化问题背包问题背包问题0/1背包问题：背包问题：给出几个体积为给出几个体积为S1，S2，Sn的物体的物体和容量为和容量为C的背包；要求找出的背包；要求找出n个物件的一个子集使其个物件的一个子集使其尽可能多地填满容量为尽可能多地填满容量为C的背包。的背包。数学形式：数学形式： 最大化最大化 满足满足 组合优化问题组合优化问题背包问题背包问题广义背包问题：广义背包问题：输入由背包容积输入由
12、背包容积C和两个向量：物品体和两个向量：物品体积积S(S1，S2，Sn)和物品价值和物品价值P(P1，P2，Pn)组成。设组成。设X为一整数集合（物品的标识），为一整数集合（物品的标识），X1，2，3，n，T为为X的子集，则问题就是找出满足约束的子集，则问题就是找出满足约束条件，并使总价值最大的子集条件，并使总价值最大的子集T。 数学形式：数学形式： 最大化最大化 满足满足 组合优化问题组合优化问题背包问题背包问题n在应用问题中，设在应用问题中，设S的元素是的元素是n项经营活动各自所需项经营活动各自所需的资源消耗，的资源消耗，C是所能提供的资源总量，是所能提供的资源总量，P的元素是的元素是人们
13、从每项经营活动中得到的利润或收益，则背包人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。的资源有效分配问题。n背包问题属于背包问题属于NP-NP-难问题难问题组合优化问题组合优化问题背包问题背包问题n多选择背包问题：多选择背包问题：有一个容积有限的背包。要放入背有一个容积有限的背包。要放入背包的物品被分为不重叠的若干类，每类中有若干不同包的物品被分为不重叠的若干类，每类中有若干不同的物品，从每类中选择一个物品，使得物品总体积在的物品，从每类中选择一个物品，使得物品总体积在满足背包容积约束的前
14、提下最大化收益。满足背包容积约束的前提下最大化收益。n属于属于NPNP难问题难问题组合优化问题组合优化问题背包问题背包问题ni为类下标；为类下标；j为类中物品的下标；为类中物品的下标；ni是第是第i类中物品的数类中物品的数量；量；cij是第是第i类中第类中第j个物品的收益；个物品的收益；m是类的数量；是类的数量；wij为第为第i类中第类中第j个项目的体积，个项目的体积，W是背包的容积。是背包的容积。最大化所选物品最大化所选物品的总价值的总价值所选物品的总体积不所选物品的总体积不得超过背包容积得超过背包容积每一类中只能每一类中只能选一个物品选一个物品组合优化问题组合优化问题旅行商问题旅行商问题n
15、旅行商问题旅行商问题（Traveling Salesman Problem）n寻寻找找一一条条最最短短的的遍遍历历n个个城城市市的的路路径径，或或者者说说搜搜索索整整数数子子集集X1，2，n（X的的元元素素表表示示对对n个个城城市市的的编编号号）的的一一个个排排列列(X) = v1，v2，vn，使使下下式式取取最最小值。小值。n式中的式中的d(vi, vi+1)表示城市表示城市vi到城市到城市vi+1的距离。的距离。n对称旅行商问题是对称旅行商问题是NP难问题难问题组合优化问题组合优化问题影片递送问题影片递送问题n影片递送问题影片递送问题（Film Delivery Problem）n一盘影片
16、拷贝要在一盘影片拷贝要在n个电影院放映。每个电影院放映的次数个电影院放映。每个电影院放映的次数已定，记为一个非负的整数已定，记为一个非负的整数di(i1，2，n)。两个影院两个影院间的距离记为间的距离记为wij，若影院若影院i和和j不能直接相连，则令不能直接相连，则令wij+ 。n问题是要为影片递送员找一个巡回，从主影院问题是要为影片递送员找一个巡回，从主影院1开始，将影开始，将影片拷贝送到第片拷贝送到第i家影院家影院di(i1，2，n)次，最后回到主影次，最后回到主影院院1，并极小化总的路线长度。当所有的，并极小化总的路线长度。当所有的di(il，2，n)为为1时，时，FDP变为经典的变为经
17、典的TSP。nFDP是是TSP的新扩展，它可以推广到一大类路径与排序问题的新扩展，它可以推广到一大类路径与排序问题中。中。组合优化问题组合优化问题最小生成树问最小生成树问题题n最小生成树问题最小生成树问题（Minimum Span Tree Problem）n考虑一个连通的无向图考虑一个连通的无向图G(V, E)，其中，其中，V = (v1, v2, , vn是代表终端或通信站的有限的端点集。是代表终端或通信站的有限的端点集。Eeij | eij = (vi, vj), vi, vj V 是代表终端或站间连线的有限边集。每条边有是代表终端或站间连线的有限边集。每条边有一个记为一个记为W wij
18、 | wij = w(vi, vj), wij 0, vi, vj V的正实数的的正实数的权重，代表距离、价格等。端点和边有时也称为节点和连权重，代表距离、价格等。端点和边有时也称为节点和连线。线。n生成树是连接生成树是连接V中所有端点的来自中所有端点的来自E的最小边集，因此对于的最小边集，因此对于图图G至少可找到一棵生成树。最小生成树，记为至少可找到一棵生成树。最小生成树，记为T*，是边的是边的权重和最小的生成树。其描述如下：权重和最小的生成树。其描述如下：组合优化问题组合优化问题图划分问题图划分问题n图的二划分问题图的二划分问题：对于一无向图：对于一无向图G，设其顶点集合为设其顶点集合为V
19、，将顶点集合将顶点集合V划分为两个子集划分为两个子集V1和和V2，Vl V2 ，求使求使V1和和V2两顶点子集之间联结最少的一种划分。两顶点子集之间联结最少的一种划分。n图的划分问题在电子线路设计中非常重要。例如，在图的划分问题在电子线路设计中非常重要。例如，在多层印刷电路板的布局设计中，使层间联线数目最少多层印刷电路板的布局设计中，使层间联线数目最少的器件布局等。由于图的划分问题的计算复杂度极高的器件布局等。由于图的划分问题的计算复杂度极高(3000个节点的二划分问题的搜索空间可达个节点的二划分问题的搜索空间可达10900)，因，因此，在实用规模上精确求出最优解是不可能的。此，在实用规模上精
20、确求出最优解是不可能的。组合优化问题组合优化问题调度问题调度问题n广义地讲，调度问题考虑的是随着时间的变化，如何广义地讲，调度问题考虑的是随着时间的变化，如何调度有限的资源在执行任务的同时满足特定约束。调度有限的资源在执行任务的同时满足特定约束。n资源：人力、金钱、机器、工具、材料、能源、等等。资源：人力、金钱、机器、工具、材料、能源、等等。n任务：制造系统的加工工序；计算机系统的信息处理。任务：制造系统的加工工序；计算机系统的信息处理。n任务的表征：完成时间、预期时间、相对紧急权重、任务的表征：完成时间、预期时间、相对紧急权重、处理时间和资源消耗。处理时间和资源消耗。组合优化问题组合优化问题
21、调度问题调度问题古典作业车间调度问题（古典作业车间调度问题（Job-shop Scheduling）：有：有m台不台不同的机器和同的机器和n个不同的工件，每个工件包含一个由多道工序个不同的工件，每个工件包含一个由多道工序组成的工序集合，工件的工序顺序是预先给定的。每道工组成的工序集合，工件的工序顺序是预先给定的。每道工序用它所要求的机器和固定的加工时间来表示。此外对工序用它所要求的机器和固定的加工时间来表示。此外对工件和机器有一些约束，例如：件和机器有一些约束，例如：(1) 一个工件不能两次访问同一机器；一个工件不能两次访问同一机器；(2) 不同工件的工序之间没有先后约束；不同工件的工序之间没
22、有先后约束；(3) 工序一旦进行不能中断；工序一旦进行不能中断； (4) 每台机器一次只能加工一个工件；每台机器一次只能加工一个工件；(5) 下达时间和交货期都不是给定的。下达时间和交货期都不是给定的。问题：确定机器上工序的顺序，以最小化完成所有工件所问题：确定机器上工序的顺序，以最小化完成所有工件所需的最小加工持续时间。需的最小加工持续时间。n关于各类优化问题的工程实例，请参考：关于各类优化问题的工程实例，请参考：n遗传算法与工程优化遗传算法与工程优化n玄光男，程润伟著，清华大学出版社玄光男，程润伟著，清华大学出版社关于计算复杂性关于计算复杂性科学出版社科学出版社关于计算复杂性关于计算复杂性
23、n利用计算机求解某一类问题的方法，称为利用计算机求解某一类问题的方法，称为计算方法计算方法，简称简称算法算法。所谓算法是指可用来求解某一问题的、可。所谓算法是指可用来求解某一问题的、可在多种计算机上实现的数据处理流程。是带有一般性在多种计算机上实现的数据处理流程。是带有一般性的一步一步的过程。是用来描述任一计算流程的抽象的一步一步的过程。是用来描述任一计算流程的抽象形式，其一般性可以超越任何具体实现时的细节。形式，其一般性可以超越任何具体实现时的细节。 n可计算理论可计算理论从建立某个可恰当描述计算机工作原理的从建立某个可恰当描述计算机工作原理的计算模型出发，精确定义什么是计算、什么是可计算，
24、计算模型出发，精确定义什么是计算、什么是可计算，再进一步回答某个或某类问题可否用计算机求解的问再进一步回答某个或某类问题可否用计算机求解的问题。题。n若所给问题可以求解，则称该问题是若所给问题可以求解，则称该问题是可计算的可计算的或或可解可解的的，否则称为，否则称为不可解不可解。 关于计算复杂性关于计算复杂性n计算复杂性理论计算复杂性理论试图在一般框架下分析各种不同类型试图在一般框架下分析各种不同类型的问题，通过考察可能存在的、求解某个问题的、不的问题，通过考察可能存在的、求解某个问题的、不同算法的复杂性程度，同算法的复杂性程度，来衡量（求解）该问题的难易来衡量（求解）该问题的难易程度程度，如
25、是否很难求解或较易求解等。，如是否很难求解或较易求解等。 n算法的计算复杂性算法的计算复杂性回答的是求解问题的回答的是求解问题的某一个算法所某一个算法所需要的各种资源的量需要的各种资源的量，它主要考虑的是设计可以用于，它主要考虑的是设计可以用于估计、定界任一算法求解某些类型的问题时所需要的估计、定界任一算法求解某些类型的问题时所需要的和仅需的计算资源量的技术或方法。和仅需的计算资源量的技术或方法。 n对于同一问题，常常有几个不同的算法可以求解它，对于同一问题，常常有几个不同的算法可以求解它，一个很自然的问题就是，一个很自然的问题就是，什么是求解该问题的一个什么是求解该问题的一个 “ “好好”算
26、法？算法？ 算法的计算复杂性算法的计算复杂性n广义地讲，一个算法的有效性可以用执行该算广义地讲，一个算法的有效性可以用执行该算法时所需要的各种法时所需要的各种计算资源计算资源的量来度量。的量来度量。 n计算资源：计算资源：运行时间运行时间，内存空间内存空间n算法的计算复杂性：算法的计算复杂性：时间复杂性时间复杂性，空间复杂性，空间复杂性n如何比较算法的时间复杂性呢？如何比较算法的时间复杂性呢？n需要定义一个统一的计算平台模型，以消除不同形需要定义一个统一的计算平台模型，以消除不同形式计算机对算法复杂性分析的影响（图灵机、随机式计算机对算法复杂性分析的影响（图灵机、随机存取机。）存取机。）n需要
27、定义一个统一的时间单位（需要定义一个统一的时间单位（一次初等运算一次初等运算）n相比于具体的时间值，我们更关心：随着问题规模相比于具体的时间值，我们更关心：随着问题规模的增大，算法的计算复杂性是如何变化的？即以问的增大，算法的计算复杂性是如何变化的？即以问题规模题规模n为变量的计算复杂性函数为变量的计算复杂性函数f(n)的属性。的属性。n问题规模的度量与所采用的问题规模的度量与所采用的编码策略编码策略（包括描述问（包括描述问题所需的字符集，以及描述方式）有关。题所需的字符集，以及描述方式）有关。算法的计算复杂性算法的计算复杂性n给定任一问题给定任一问题，假设已找到描述该问题例子的一个合假设已找
28、到描述该问题例子的一个合理编码策略理编码策略e，则对则对的任一例子的任一例子I，称其依编码策略称其依编码策略e所得的相应字符串描述中所含字符的个数为其所得的相应字符串描述中所含字符的个数为其输入长输入长度度，并将该输入长度的具体数值作为例子，并将该输入长度的具体数值作为例子 I 的大小的的大小的正式度量。正式度量。 算法的计算复杂性算法的计算复杂性n考虑典型的旅行商问题。该问题的参数是由所需访问考虑典型的旅行商问题。该问题的参数是由所需访问城市的一个有限集合城市的一个有限集合C=C1,C2,Cm和对和对C中每一对中每一对城市城市Ci,Cj之间的距离之间的距离d(Ci,Cj)所组成。旅行商问题的
29、任所组成。旅行商问题的任何一个例子是通过限定城市的数目，并指定每两个城何一个例子是通过限定城市的数目，并指定每两个城市之间的具体距离而得到的。例如：市之间的具体距离而得到的。例如：C=C1,C2,C3,C4,d(C1,C2)=10,d(C1,C3)=5,d(C1,C4)=9,d(C2,C3)=6,d(C2,C4)9和和d(C3,C4)=3就构成一个具就构成一个具体例子，而这个例子的一个解是排序体例子，而这个例子的一个解是排序因因为四个城市的这个排序所对应的路线是所有可能旅行为四个城市的这个排序所对应的路线是所有可能旅行路线中长度最小的，为路线中长度最小的，为27。 算法的计算复杂性算法的计算复
30、杂性若用字母表若用字母表 C,/,0,1,2,3,4,5,6,7,8,9C,/,0,1,2,3,4,5,6,7,8,9中的字符表示旅行商问题的具体例子，则前面中的字符表示旅行商问题的具体例子，则前面例子可以用字符串例子可以用字符串C1,C2,C3,C4/10/5/9/6/9/3C1,C2,C3,C4/10/5/9/6/9/3来描述。其相应的输入长度为来描述。其相应的输入长度为3232，从而称这个，从而称这个例子的大小为例子的大小为3232。 算法的计算复杂性算法的计算复杂性n定义：算法的时间复杂度定义：算法的时间复杂度n对对某某一一问问题题和和任任一一可可能能的的输输入入长长度度n，称称用用所
31、所给给算算法法求求解解的的所所有有大大小小为为n的的例例子子所所需需的的时时间间的的最最大大值值为为该该算法在输入长度为算法在输入长度为n时的复杂性。时的复杂性。n对对于于不不同同的的算算法法，就就有有着着不不同同的的时时间间复复杂杂性性函函数数。复复杂杂性性函函数数的的不不同同变变化化方方式式反反映映了了算算法法的的好好坏坏程程度度。例例如如，时时间间复复杂杂性性函函数数关关于于输输入入长长度度的的增增长长速速度度就就是是判判别一个算法时间效率的主要指标。别一个算法时间效率的主要指标。算法的计算复杂性算法的计算复杂性n在计算机科学中存在这样一个一般的约定：仅当算法在计算机科学中存在这样一个一
32、般的约定：仅当算法的时间复杂性函数随问题例子输入长度的增加而多项的时间复杂性函数随问题例子输入长度的增加而多项式地增长时，才认为这个算法是实用的、有效的。按式地增长时，才认为这个算法是实用的、有效的。按照这种观点，则可以将算法分为两大类。照这种观点，则可以将算法分为两大类。n多项式时间算法多项式时间算法（polynomial time algorithmpolynomial time algorithm） n指数时间算法指数时间算法（exponential time algorithmexponential time algorithm） 算法的计算复杂性算法的计算复杂性n多多项项式式时时间间
33、算算法法（polynomial time algorithm）：是是指指存存在在某某个个以以输输入入长长度度n为为变变量量的的多多项项式式函函数数p(n),使使其其时时间间复复杂杂性性函函 数数 为为 O(p(n)的的 算算 法法 。 因因 此此 ， 复复 杂杂 性性 为为O(n),O(106n3),O(5n8)等的算法均为多项式时间算法。等的算法均为多项式时间算法。n指数时间算法指数时间算法（exponential time algorithm）：）：是指任何其是指任何其时间复杂性函数不可能如上用多项式函数去界定的算法。时间复杂性函数不可能如上用多项式函数去界定的算法。这类算法的时间复杂性函
34、数典型的例子有这类算法的时间复杂性函数典型的例子有2n,n!,nn,nlbn等。等。 算法的计算复杂性算法的计算复杂性n对于定义于正整数集上的两个正实值函数对于定义于正整数集上的两个正实值函数f(n)与与g(n)，若存在两个常数若存在两个常数c c 0，使得当使得当n充分大时有充分大时有cg(n)f(n)cg(n)，则记则记 f(n) = O(g(n)。n利用利用O(*)可以将函数划分为不同的类，在复杂性理论可以将函数划分为不同的类，在复杂性理论中，对如此定义的同一类型的不同函数往往不加区分。中，对如此定义的同一类型的不同函数往往不加区分。 算法的计算复杂性算法的计算复杂性算法的计算复杂性算法
35、的计算复杂性n总结：总结：n首先，定义的时间复杂性为最坏情形度量。首先，定义的时间复杂性为最坏情形度量。n其其次次，在在考考虑虑算算法法的的复复杂杂性性时时，我我们们通通常常只只关关心心算算法在问题例子的规模法在问题例子的规模n充分大时的表现。充分大时的表现。n第三，关于问题的难解性、一个算法是多项式时间第三，关于问题的难解性、一个算法是多项式时间算法还是指数时间算法等，本质上并不依赖特定的算法还是指数时间算法等，本质上并不依赖特定的编码和具体的计算模型。编码和具体的计算模型。问题的复杂性分类问题的复杂性分类n为了能在统一的框架下刻画、研究任何问题的可行解为了能在统一的框架下刻画、研究任何问题
36、的可行解与求解它的复杂程度，并起到便于描述算法的定义以与求解它的复杂程度，并起到便于描述算法的定义以及相关的理论结果，需要对问题的定义进行进一步抽及相关的理论结果，需要对问题的定义进行进一步抽象与统一化。象与统一化。n目前所广泛采用的目前所广泛采用的描述问题的方法描述问题的方法主要有两种：一是主要有两种：一是将任一问题转化为所谓的将任一问题转化为所谓的可行性检验问题可行性检验问题（feasibility problemfeasibility problem），），二是把问题转述为二是把问题转述为判定问判定问题题（decision problemdecision problem）。）。 问题的复
37、杂性分类问题的复杂性分类n“判判定定问问题题”是是答答案案只只有有是是与与非非两两种种可可能能的的问问题题。一一个个判判定定问问题题可可简简单单地地由由其其所所有有例例子子的的集集合合D和和答答案案为为“是是”的例子所构成的子集的例子所构成的子集Y D来组成。来组成。n为了反映实际问题所具有的特性，通常所采用的标准描为了反映实际问题所具有的特性，通常所采用的标准描述方法由两部分组成。述方法由两部分组成。“例子例子”：用诸如集合、图、函：用诸如集合、图、函数等各种描述分量来刻画判定问题的一般性例子；数等各种描述分量来刻画判定问题的一般性例子；“问问题题”：陈述基于一般性例子所提出的一个：陈述基于
38、一般性例子所提出的一个“是是/非非”提问。提问。 n实际中几乎所有问题都可直接或间接地转述为判定问题。实际中几乎所有问题都可直接或间接地转述为判定问题。 问题的复杂性分类问题的复杂性分类n语言（语言（language）：对于字符的任一有限集合对于字符的任一有限集合 ，用，用 *表示由表示由 中的字符所组成的所有有限长度字符串的集中的字符所组成的所有有限长度字符串的集合。若合。若L为为 *的一个子集，则称的一个子集，则称L为字符集为字符集 上的一个语上的一个语言。例如，言。例如，01,001,111,1010110就是字符集就是字符集 0, 1上的一个语言。上的一个语言。 n判定问题与语言之间的
39、对应关系是通过编码策略判定问题与语言之间的对应关系是通过编码策略e来实来实现的。现的。定义定义“语言语言”：L,e = x*: 为为e所使用的字符集、所使用的字符集、 而而x为某个例子在为某个例子在e下的编码下的编码 n如果一个结论对语言如果一个结论对语言L,e成立，我们就说它在编码策成立，我们就说它在编码策略略e之下对问题之下对问题成立。成立。 问题的复杂性分类问题的复杂性分类n确定性单带图灵机确定性单带图灵机（Deterministic one-tape Turing MachineDTM）：）：一个一个DTM由一个有限状态控制由一个有限状态控制器、一个读写头和一条双向的、具有无限多个带格
40、的器、一个读写头和一条双向的、具有无限多个带格的线性带组成。线性带组成。 问题的复杂性分类问题的复杂性分类一个一个DTM程序（程序（program）应详细规定下列信息：应详细规定下列信息：（1）带带中中所所有有字字符符的的一一个个有有限限集集合合 ，它它应应包包括括输输入入字字符表子集符表子集 和一个特别的空白符号和一个特别的空白符号b- 。（2）一一个个有有限限状状态态集集Q，它它包包括括初初始始状状态态q0和和两两个个特特有有的停机状态的停机状态qY和和qN。（3）一个转移函数）一个转移函数可可以以设设计计一一个个DTM程程序序来来完完成成任任何何可可在在某某一一通通常常计计算算机上实现的
41、任一计算。机上实现的任一计算。 问题的复杂性分类问题的复杂性分类n称称一一个个带带有有输输入入字字符符表表 的的DTMDTM程程序序M M接接受受x*，当当且且仅当它作用于输入仅当它作用于输入 x 时停机于状态时停机于状态qY 。n只有当一个只有当一个DTMDTM程序对定义于其输入字符表上的所有可程序对定义于其输入字符表上的所有可能字符串均停机时，我们才称其为一个能字符串均停机时，我们才称其为一个算法算法。相应地，。相应地，称一个称一个DTMDTM程序程序M M在编码策略在编码策略e之下求解判定问题之下求解判定问题 ，如，如果果M M对定义于其输入字符表上的所有输入字符串均停机对定义于其输入字
42、符表上的所有输入字符串均停机且有且有L LM M = = L,e。nL LM M = = x x * *: :M M接受接受x x 表示由程序表示由程序M M所识别的语言。所识别的语言。 问题的复杂性分类问题的复杂性分类n一个一个DTM程序程序M对于输入对于输入x的计算所用的时间定义为该的计算所用的时间定义为该程序从开始直至进入停机状态为止所运行的步数。程序从开始直至进入停机状态为止所运行的步数。 n时间复杂性函数的定义：对于一个对所有输入时间复杂性函数的定义：对于一个对所有输入 x* 均停机的均停机的DTM程序程序M，定义其时间复杂性函数定义其时间复杂性函数TM : Z+ Z+为为 TM(n
43、) = maxm: 存在一个存在一个x* ，| x | = n，使得使得M对对 输入输入x的计算需要时间的计算需要时间m。 问题的复杂性分类问题的复杂性分类n若若存存在在一一个个多多项项式式p(n)，使使得得对对所所有有的的n Z+，有有TM(n) p(n)，则称程序，则称程序M为一个多项式时间为一个多项式时间DTM程序。程序。n定义定义P类语言（问题）：类语言（问题）：P L:存存在在一一个个多多项项式式时时间间DTM程程序序M，使使得得L= LM n若若存存在在一一个个多多项项式式时时间间DTM程程序序，它它在在编编码码策策略略e之之下下求解求解 ，即，即L,e P ，则称该判定问题，则称
44、该判定问题属于属于P。问题的复杂性分类问题的复杂性分类n非非确确定定性性单单带带图图灵灵机机（Non-Deterministic Non-Deterministic one-tape one-tape Turing Turing MachineNDTMMachineNDTM，又又称称非非确确定定性性图图灵灵机机）完完全全是是一一种种假假想想的的机机器器，通通常常有有两两种种方方法法来来描描述述它它：多多值模型和假想模块模型。值模型和假想模块模型。n用用假假想想模模块块模模型型，NDTMNDTM可可描描述述成成：除除多多了了一一个个猜猜想想模模块块外外，它它与与DTMDTM有有着着完完全全相相同
45、同的的结结构构，而而这这个个猜猜想想模模块块带带有有自自己己的的仅仅可可对对条条带带写写的的猜猜想想头头，它它提提供供了了写写下下猜猜想的办法，并仅用于此目的。想的办法，并仅用于此目的。问题的复杂性分类问题的复杂性分类n对于一个输入对于一个输入x*，NDTMNDTM程序的计算分为两个不同的程序的计算分为两个不同的阶段：阶段：猜想阶段猜想阶段和和检验阶段检验阶段。 问题的复杂性分类问题的复杂性分类n一般来说，对于一个给定的输入字符串一般来说，对于一个给定的输入字符串x，NDTM程序程序M将会做无限多个可能的计算，对每一个可能猜想串将会做无限多个可能的计算，对每一个可能猜想串都有一个相应的计算，如
46、果这些计算中至少有一个为都有一个相应的计算，如果这些计算中至少有一个为可接受的计算，则称可接受的计算，则称NDTM程序程序M接受接受x，相应地，相应地，M所识别的语言定义为：所识别的语言定义为：问题的复杂性分类问题的复杂性分类n定义一个定义一个NDTM程序程序M接受接受x LM所需地时间为：在所需地时间为：在M对对x的所有可接受计算中，程序从一开始直到进入停机的所有可接受计算中，程序从一开始直到进入停机状态状态qY为止，在猜想和检验阶段所进行的步数的最大为止，在猜想和检验阶段所进行的步数的最大值。值。nM的时间复杂性函数的时间复杂性函数 TM: Z+Z+ 则定义为则定义为TM(n) = max
47、1 m: 存在一个长度为存在一个长度为n的的x LM， 使得使得M要接受它所需的时间为要接受它所需的时间为m问题的复杂性分类问题的复杂性分类n若存在一个多项式若存在一个多项式 p(n) ，使得对所有的使得对所有的n 1，有有TM(n) p(n)，则称则称NDTM程序程序M为一个多项式时间为一个多项式时间NDTM程序。程序。n定义定义NP类语言（问题）：类语言（问题）：nNP = L: 存在一个多项式时间存在一个多项式时间NDTM程序程序M，使得使得LM=Ln称判定问题称判定问题 在编码策略在编码策略e之下属于之下属于NP，若若L , e NP。相应的求解算法称相应的求解算法称多项式时间不确定算
48、法多项式时间不确定算法。问题的复杂性分类问题的复杂性分类n若若 NP，则存在一个多项式则存在一个多项式 p 使得使得 可以用一个时间可以用一个时间复杂性为复杂性为 O(2p(n) 的确定性算法来求解。的确定性算法来求解。n在非确定性图灵机上时间复杂性为在非确定性图灵机上时间复杂性为 q(n) 的判定问题和的判定问题和在确定性图灵机上时间复杂性为在确定性图灵机上时间复杂性为 q(n)kq(n) 的问题相当，的问题相当，因此，因此，直观上我们有理由认为非确定性图灵机要比确直观上我们有理由认为非确定性图灵机要比确定性图灵机的处理能力大，应能有效求解后者所不能定性图灵机的处理能力大，应能有效求解后者所
49、不能有效解决的许多复杂问题有效解决的许多复杂问题。nP NP问题的复杂性分类问题的复杂性分类n所谓从一个语言所谓从一个语言 L1 1*到另一个语言到另一个语言L2 2*的的多项多项式变换式变换是指满足下面两个条件的函数是指满足下面两个条件的函数f: 1* 2*:(1) 存在计算存在计算f的一个多项式时间的一个多项式时间DTM程序。程序。(2) 对于所有的对于所有的x 1*， x L1当且仅当当且仅当f(x) L2。用记号用记号L1 L2表示存在一个从表示存在一个从L1到到L2的多项式变换。的多项式变换。n称一个语言称一个语言L（判定问题判定问题 ）为）为NP完全完全的的(NPC)，如果如果L
50、NP( NP)，且对所有别的语言且对所有别的语言L NP( NP)，均有均有L L( )。问题的复杂性分类问题的复杂性分类n关系关系 在这些语言（或判定问题）的等价类上建立了一在这些语言（或判定问题）的等价类上建立了一个偏序（个偏序（L1 L2 意味着意味着L1比比L2不难不难）。）。nP类问题组成了这一偏序下类问题组成了这一偏序下“最小最小”的等价类，从而可的等价类，从而可以看作是由计算上以看作是由计算上“最容易最容易”的语言（判定问题）所的语言（判定问题）所构成。构成。n由由NP完全的语言（判定问题）所形成的另一个等价类完全的语言（判定问题）所形成的另一个等价类则包含了则包含了NP类中那些
51、类中那些“最困难最困难”的语言（问题）。的语言（问题）。问题的复杂性分类问题的复杂性分类n设设 1和和 2都是判定问题。我们说都是判定问题。我们说 1在多项式时间内在多项式时间内可可图灵规约图灵规约简称简称规约规约为为 2，如果存在，如果存在 1的一个算法的一个算法A1，它多次调用求解它多次调用求解 2的算法的算法A2作为其子程序，并且作为其子程序，并且若假设每次调用该子程序若假设每次调用该子程序A2均需用单位时间，则均需用单位时间，则A1为为一个多项式时间的算法。并把一个多项式时间的算法。并把A1叫做从叫做从 1到到 2的多项的多项式时间规约，记为式时间规约，记为 T。问题的复杂性分类问题的
52、复杂性分类n如果如果 1可图灵规约到可图灵规约到 2，那么，那么 2是多项式时间可解是多项式时间可解蕴涵蕴涵 1是多项式时间可解的，从而表明是多项式时间可解的，从而表明 2至少和至少和 1一样的难。一样的难。n定义：对于判定问题定义：对于判定问题 ，若存在一个，若存在一个NP完全的问题完全的问题 ，使得，使得 T ，则称问题，则称问题 是是NP困难困难的（的（NP-hard）经典最优化方法的一般结构经典最优化方法的一般结构n通常采用迭代方法通常采用迭代方法n基本思想：给定解空间中的一个初始点基本思想：给定解空间中的一个初始点x0 Rn，按照某按照某一迭代规则产生一个点序列一迭代规则产生一个点序
53、列xk，使得当使得当xk是有穷点是有穷点列时，其最后一个点是最优化模型问题的最优解。列时，其最后一个点是最优化模型问题的最优解。n一个好的算法应具备的典型特征为：迭代点一个好的算法应具备的典型特征为：迭代点xk能稳定能稳定地接近局部极小点地接近局部极小点x*的邻域，然后迅速收敛于的邻域，然后迅速收敛于x* 。当当给定的某种收敛准则满足时，迭代即终止。给定的某种收敛准则满足时，迭代即终止。 经典最优化方法的一般结构经典最优化方法的一般结构n设设xk为为第第k次次迭迭代代点点，dk为为第第k次次搜搜索索方方向向， k为为第第k次次步长因子，则第步长因子，则第k次迭代为次迭代为xk+1 = xk +
54、 k dkn不同的步长因子不同的步长因子 k和不同的搜索方向和不同的搜索方向dk构成了不同的方构成了不同的方法。法。n在经典最优化方法中，搜索方向在经典最优化方法中，搜索方向dk是是 f 在在xk点处的下降点处的下降方向，即方向，即dk满足满足或者或者 经典最优化方法的一般结构经典最优化方法的一般结构最优化方法的基本结构为：最优化方法的基本结构为：(1) 给定初始点给定初始点x0，(a) 确确定定搜搜索索方方向向dk，即即依依照照一一定定规规则则，构构造造 f 在在xk点点处的下降方向作为搜索方向处的下降方向作为搜索方向(b) 确定步长因子确定步长因子 k，使目标函数值有某种意义的下降，使目标
55、函数值有某种意义的下降(c) 令令 xk+1 = xk + k dk(2) 若若xk+1满满足足某某种种终终止止条条件件，则则停停止止迭迭代代，得得到到近近似似最最 优解优解xk+1。否则，重复以上步骤否则，重复以上步骤优化算法及其分类优化算法及其分类n经典算法经典算法。包括线性规划、动态规划、整数规划和分。包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法。枝定界等运筹学中的传统算法。n构造型算法构造型算法。用构造的方法快速建立问题的解。譬如，。用构造的方法快速建立问题的解。譬如，调度问题中的典型构造型方法有：调度问题中的典型构造型方法有：Johnson法、法、Palmer法、法
56、、Gupta法、法、CDS法、法、Daunenbring的快速接近法、的快速接近法、NEH法等。法等。优化算法及其分类优化算法及其分类n改进型算法改进型算法，或称邻域搜索算法。从任一解出发，对，或称邻域搜索算法。从任一解出发，对其邻域的不断搜索和当前解的替换来实现优化。根据其邻域的不断搜索和当前解的替换来实现优化。根据搜索行为，它又可分为局部搜索法和指导性搜索法。搜索行为，它又可分为局部搜索法和指导性搜索法。n局部搜索法局部搜索法。以局部优化策略在当前解的邻域中贪婪搜。以局部优化策略在当前解的邻域中贪婪搜索，如只接受优于当前解的状态作为下一当前解的贪心索，如只接受优于当前解的状态作为下一当前解
57、的贪心法；接受当前解邻域中的最好解作为下一当前解的爬山法；接受当前解邻域中的最好解作为下一当前解的爬山法等。法等。n指导性搜索法指导性搜索法。利用一些指导规则来指导整个解空间中。利用一些指导规则来指导整个解空间中优良解的探索，如优良解的探索，如SA、GA、EP、ES和和TS等。等。优化算法及其分类优化算法及其分类n基于系统动态演化的方法基于系统动态演化的方法。将优化过程转化为系统动。将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如态的演化过程，基于系统动态的演化来实现优化，如神经网络和混沌搜索等。神经网络和混沌搜索等。n混合型算法混合型算法。指上述各算法从结构或操作上相混合
58、而。指上述各算法从结构或操作上相混合而产生的各类算法。产生的各类算法。优化算法及其分类优化算法及其分类n枚举法枚举法n确定性优化算法确定性优化算法n各类数学规划算法，如单纯形法，分支定界各类数学规划算法，如单纯形法，分支定界法，牛顿法，。法，牛顿法，。n随机优化算法随机优化算法n各类自然计算方法，如模拟退火法，禁忌搜各类自然计算方法，如模拟退火法，禁忌搜索法，演化算法，。索法，演化算法，。优化算法及其分类优化算法及其分类n用户往往面临两种选择：用户往往面临两种选择：n寻找全局最优解，不管耗费多少计算资源；寻找全局最优解，不管耗费多少计算资源；n在用户许可的资源（主要是时间资源）消耗在用户许可的
59、资源（主要是时间资源）消耗范围内，寻找尽可能范围内，寻找尽可能“好好”的解；的解；n在严重缺乏先验知识的情况下，如何尽在严重缺乏先验知识的情况下，如何尽量快速地找到问题的量快速地找到问题的“好好”的解？的解？一些基本策略一些基本策略n贪心策略（贪心策略（Greedy Strategy）n局部搜索（局部搜索（Local Search）n如何得到如何得到“好好”的初始可行解？的初始可行解？n如何选择一个如何选择一个“好好”的邻域结构或其它定义方式？的邻域结构或其它定义方式？n确定某一搜索它的方法。确定某一搜索它的方法。n群体策略（群体策略（Population-based Search）n分而治之（分而治之（Divide and Conquer）n在搜索过程中学习（在搜索过程中学习（Learning during Search）
