理学第一章绪论ppt课件

智能优化计算,1,课程名称智能计算教师联系方式办公地点：实验楼2408，Tel-mail：zhao_tongzhou上课时间地点周四34节，2408,智能计算,2,课程定位解决的问题：优化问题解决的方法：智能方法数学工具实用方法考核方式笔试或报告,智能计算,3,内容安排最优化问题概述禁忌搜索算法(Tabusearch)模拟退火算法(SimulatedAnnealing)遗传算法(GeneticAlgorithm)神经网络优化算法(NeuralNetwork)群智能算法，包括蚁群算法(AntColonyOptimization)、粒子群算法(ParticleSwarmOptimization)广义领域搜索算法及其统一结构,智能计算,4,参考书1邢文训,谢金星.现代优化计算方法.北京:清华大学出版社,2005.2王凌.智能优化算法及其应用.北京:清华大学出版社,2001.3阎平凡,张长水.人工神经网络与模拟进化计算.北京:清华大学出版社,2005.,智能计算,5,参考书4王小平,曹立明.遗传算法理论、应用与软件实现.西安:西安交通大学出版社,2002.5黄席樾等.现代智能算法理论及应用.北京：科学出版社,2005.6高尚,杨静宇.群智能算法及其应用.北京:中国水利水电出版社,2006.,智能计算,6,第一章绪论,智能计算,7,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,8,1.1引言,智能计算,优化技术？以数学为基础，解决各种工程问题优化解优化技术的用途系统控制人工智能模式识别生产调度,1.1.1优化问题,9,1.1引言,智能计算,最优化问题的描述最优化问题的数学模型的一般描述：,1.1.1优化问题,即：讨论求函数f(x)的最小值问题，即确定xD,使F(x*)=minF(x),g(x)=,g(x)是F(x)的梯度，H(x)是F(x)的Hesse矩阵。,10,1.1引言,智能计算,待解决的问题连续性问题，以微积分为基础，规模较小传统的优化方法理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性、收敛速度,1.1.2传统优化方法,11,1.1引言,智能计算,待解决的问题离散性、不确定性、大规模现代的优化方法启发式算法（heuristicalgorithm）追求满意（近似解）实用性强（解决实际工程问题）现代的评价方法算法复杂性,1.1.3现代优化方法,12,1.2最优化问题及其分类（函数优化和组合优化）,智能计算,数学表述难点高维多峰值,1.2.1函数优化问题,13,1.2最优化问题及其分类,智能计算,测试函数（Benchmark问题）（1）SphereModel其最优状态和最优值为,1.2.1函数优化问题,14,1.2最优化问题及其分类,智能计算,测试函数（2）SchwefelsProblem2.22其最优状态和最优值为,1.2.1函数优化问题,15,1.2最优化问题及其分类,智能计算,测试函数（3）SchwefelsProblem1.2其最优状态和最优值为,1.2.1函数优化问题,16,1.2最优化问题及其分类,智能计算,测试函数（4）SchwefelsProblem2.21其最优状态和最优值为,1.2.1函数优化问题,17,1.2最优化问题及其分类,智能计算,测试函数（5）GeneralizedRosenbrocksFunction其最优状态和最优值为,1.2.1函数优化问题,18,1.2最优化问题及其分类,智能计算,测试函数（6）StepFunction其最优状态和最优值为,1.2.1函数优化问题,19,1.2最优化问题及其分类,智能计算,测试函数（6）StepFunction,1.2.1函数优化问题,20,1.2最优化问题及其分类,智能计算,测试函数（7）QuarticFunctioni.e.Niose其最优状态和最优值为,1.2.1函数优化问题,21,1.2最优化问题及其分类,智能计算,测试函数（8）GeneralizedSchwefelsProblem2.26其最优状态和最优值为,1.2.1函数优化问题,22,1.2最优化问题及其分类,智能计算,测试函数（8）GeneralizedSchwefelsProblem2.26,1.2.1函数优化问题,23,1.2最优化问题及其分类,智能计算,测试函数（9）GeneralizedRastriginsFunction其最优状态和最优值为,1.2.1函数优化问题,24,1.2最优化问题及其分类,智能计算,测试函数（10）AckleysFunction其最优状态和最优值为,1.2.1函数优化问题,25,1.2最优化问题及其分类,智能计算,测试函数（10）AckleysFunction,1.2.1函数优化问题,26,1.2最优化问题及其分类,智能计算,测试函数（11）GeneralizedGriewankFunction其最优状态和最优值为,1.2.1函数优化问题,27,1.2最优化问题及其分类,智能计算,测试函数（11）GeneralizedGriewankFunction,1.2.1函数优化问题,28,1.2最优化问题及其分类,智能计算,测试函数（12）GeneralizedPenalizedFunction其最优状态和最优值为,1.2.1函数优化问题,29,1.2最优化问题及其分类,智能计算,测试函数其中，,1.2.1函数优化问题,30,1.2最优化问题及其分类,智能计算,测试函数（13）GeneralizedPenalizedFunction其最优状态和最优值为,1.2.1函数优化问题,31,1.2最优化问题及其分类,智能计算,测试函数（14）ShekelsFoxholesFunction其最优状态和最优值为,1.2.1函数优化问题,32,1.2最优化问题及其分类,智能计算,测试函数其中，,1.2.1函数优化问题,33,1.2最优化问题及其分类,智能计算,测试函数（15）KowaliksFunction其最优状态和最优值为,1.2.1函数优化问题,34,1.2最优化问题及其分类,智能计算,测试函数其中，,1.2.1函数优化问题,35,1.2最优化问题及其分类,智能计算,测试函数（16）Six-HumpCamel-BackFunction其最优状态和最优值为,1.2.1函数优化问题,36,1.2最优化问题及其分类,智能计算,测试函数（17）BraninFunction其最优状态和最优值为,1.2.1函数优化问题,37,1.2最优化问题及其分类,智能计算,测试函数（18）Goldstein-PriceFunction其最优状态和最优值为,1.2.1函数优化问题,38,1.2最优化问题及其分类,智能计算,测试函数（19）HartmansFunction其最优状态和最优值为,1.2.1函数优化问题,39,1.2最优化问题及其分类,智能计算,测试函数其中，,1.2.1函数优化问题,40,1.2最优化问题及其分类,智能计算,测试函数（20）HartmansFunction其最优状态和最优值为,1.2.1函数优化问题,41,1.2最优化问题及其分类,智能计算,测试函数其中，,1.2.1函数优化问题,42,1.2最优化问题及其分类,智能计算,测试函数（21）ShekelsFamilym分别取5，7和10，其最优状态和最优值为,1.2.1函数优化问题,43,1.2最优化问题及其分类,智能计算,测试函数其中，,1.2.1函数优化问题,44,1.2最优化问题及其分类,智能计算,测试函数（22）J.D.Schaffer其最优状态和最优值为,1.2.1函数优化问题,45,1.2最优化问题及其分类,智能计算,测试函数（22）J.D.Schaffer此函数在距全局最优点大约3.14范围内存在无穷多个局部极小将其包围，并且函数强烈振荡。,1.2.1函数优化问题,46,1.2最优化问题及其分类,智能计算,有约束的函数优化常用受约束测试函数；影响因素：（1）曲面拓扑性质，线性或凸函数比无规律的函数更容易求解；（2）可行区域的疏密程度，通常以可行区域占整个搜索空间的比值来度量；,1.2.1函数优化问题,47,1.2最优化问题及其分类,智能计算,有约束的函数优化常用受约束测试函数；影响因素：（3）整体最优解与可行区域最优解之比；（4）在最优解处活跃约束的数目，活跃约束数目越多则最优解离可行区域的边界越近。,1.2.1函数优化问题,48,1.2最优化问题及其分类,智能计算,数学表述所属范畴涉及离散事件的最优编排、分类、次序筛选等问题，是运筹学的一个重要分支。,1.2.2组合优化问题,49,1.2最优化问题及其分类,智能计算,典型问题旅行商问题（Travelingsalesmanproblem,TSP）给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。,1.2.2组合优化问题,1,2,3,4,12,1,8,10,3,2,50,1.2最优化问题及其分类,智能计算,典型问题旅行商问题（Travelingsalesmanproblem,TSP）计算复杂度：指数灾难,1.2.2组合优化问题,51,1.2最优化问题及其分类,智能计算,典型问题加工调度问题（Schedulingproblem,如Flow-shop,Job-shop）Job-shop：n个工件在m台机器上加工，Oij：第i个工件在第j台机器上的操作，Tij：相应的操作时间，已知。事先给定各工件在各机器上的加工次序（技术约束条件），要求确定与技术约束条件相容的各机器上所有工件的加工顺序，使得加工性能指标达到最优。若各工件技术约束条件相同，转化为Flow-shop。,1.2.2组合优化问题,52,1.2最优化问题及其分类,智能计算,典型问题加工调度问题（Schedulingproblem,如Flow-shop,Job-shop）计算复杂性：可能的排列方式有（n！）m多目标优化动态性状态相依,1.2.2组合优化问题,53,1.2最优化问题及其分类,智能计算,典型问题01背包问题（Knapsackproblem）对于n个体积为ai、价值分别为ci的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大。,1.2.2组合优化问题,背包问题的贪婪算法,54,1.2最优化问题及其分类,智能计算,典型问题装箱问题（Binpackingproblem）有n个尺寸不超过1的物品，有数个尺寸为1的箱子，如何将这些物品装入箱子，使得所需箱子的个数最少。,1.2.2组合优化问题,55,1.2最优化问题及其分类,智能计算,典型问题图着色问题（Graphcoloringproblem）对于n个顶点的无环图G，要求对其各个顶点进行着色，使得任意两个相邻的顶点都有不同的颜色，且所用颜色种类最少。,1.2.2组合优化问题,C1：第一种颜色C2：第二种颜色C3：第三种颜色,56,1.2最优化问题及其分类,智能计算,典型问题聚类问题（Clusteringproblem）m维空间上的n个模式Xi|i=1,2,n，要求聚成k类，使得各类本身内的点最相近，如要求其中Rp为第p类的中心，即其中，p=1,2,k，np为第p类中的点数。,1.2.2组合优化问题,57,1.2最优化问题及其分类,智能计算,Benchmark问题n城市TSP问题（n=30，50，75）Hopfield-10城市TSP问题Grotschel-442城市TSP问题CarnFlow-shop问题（n=1,2,8）RecnFlow-shop问题（n=1,3,5,39,41）FTnorMTnJob-shop问题（n=6,10,20）LAnJob-shop问题（n=1,6,11,16,21,26,31,36）,1.2.2组合优化问题,30城市TSP问题（d*=423.741byDBFogel）4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450,58,1.3启发式算法,智能计算,最优算法一个问题的最优算法求得该问题每个实例的最优解；启发式算法一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下给出待解决优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。,1.3.1启发式算法的定义,59,1.3启发式算法,智能计算,启发式算法的特点是一种技术；不能保证所得解的最优性；启发式算法的发展历史20世纪40年代起步20世纪6070年代被鄙视20世纪70年代观点转变20世纪80年代至今研究热潮,1.3.1启发式算法的定义,60,1.3启发式算法,智能计算,例子背包问题的贪婪算法（Greedyalgorithm）贪婪算法：采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedycriterion）。,1.3.1启发式算法的定义,61,1.3启发式算法,智能计算,例子背包问题的贪婪算法（Greedyalgorithm）STEP1STEP2,1.3.1启发式算法的定义,62,1.3启发式算法,智能计算,启发式算法的优点1.模型误差、数据不精确性、参数估计误差等可能造成最优算法的解比启发式算法的解更差；2.复杂问题无法求得最优算法或最优算法太复杂；3.简单易行，直观，程序简单。启发式算法的缺点1.不能保证最优；2.不稳定；3.依赖于实际问题、设计者经验。,1.3.1启发式算法的定义,63,1.3启发式算法,智能计算,简单直观的算法一步算法：不在两个可行解之间比较，在未终止的迭代过程中，得到的中间解有可能不是可行解；例：背包问题的贪婪算法改进算法：迭代过程是从一个可行解到另一个可行解变换，通过两个解的比较而选择好的解，直到满足一定的要求为止；例：TSP问题的2opt方法,1.3.2启发式算法的分类,64,1.3启发式算法,智能计算,数学规划算法用连续优化（如线性规划）的方法求解组合优化问题（如整数线性规划模型），其中包括一些启发式规则。基于数学规划的理论。,1.3.2启发式算法的分类,65,1.3启发式算法,智能计算,现代优化算法禁忌搜索算法模拟退火算法遗传算法人工神经网络蚁群算法粒子群算法混合算法,1.3.2启发式算法的分类,特点：基于客观世界中的一些自然现象；建立在计算机迭代计算的基础上；具有普适性，可解决实际应用问题。,66,1.3启发式算法,智能计算,评价算法优劣的指标算法的复杂性（计算效率）解的偏离程度（计算效果）算法的稳健性（不同实例、不同时间、不同起点的差异）评价算法优劣的手段最坏情况分析（纯理论）概率分析（理论分析）计算模拟分析（统计特性）,1.3.3启发式算法的性能分析,67,1.4计算复杂性与NP完全问题,智能计算,时间复杂性和空间复杂性概念算法的时间复杂性：算法对时间的需要量（加、减、乘、除、比较、读、写等操作的总次数）；算法的空间复杂性：算法对空间的需要量（存储空间的大小，二进制位数）；问题的时间复杂性：所有算法中时间复杂性最小的算法时间复杂性；问题的空间复杂性：所有算法中空间复杂性最小的算法空间复杂性；,1.4.1计算复杂性的基本概念,68,1.4计算复杂性与NP完全问题,智能计算,复杂性问题分类P类、NP类、NP完全类复杂性表示方法复杂性表示为问题规模n（如TSP的n）的函数，时间复杂性T(n)，关键操作的次数；空间复杂性S(n)，占用的存储单元数量；,1.4.1计算复杂性的基本概念,69,1.4计算复杂性与NP完全问题,智能计算,复杂性表示方法若算法A的时间复杂性为TA(n)=O(p(n)，O(p(n)为复杂性函数p(n)主要项的阶，且p(n)为n的多项式函数，则称算法A为多项式算法。当不存在多项式函数p(n)时，称相应的算法为非多项式时间算法或指数时间算法；随着变量的增加，多项式函数增长的速度比指数函数和非多项式函数增长的速度要慢得多。,1.4.1计算复杂性的基本概念,70,1.4计算复杂性与NP完全问题,智能计算,P类问题（deterministicpolynomial）具有多项式时间求解算法的问题类迄今为止，许多组合优化问题都没有找到求最优解的多项式时间算法。NP类问题(Nondeterministicpolynomial)定义1实例是问题的特殊表现，所谓实例就是确定了描述问题特性的所有参数的问题，其中参数值称为数据，这些数据占有计算机的空间称为实例的输入长度。,1.4.2P,NP,NP-C和NP-hard,71,1.4计算复杂性与NP完全问题,智能计算,NP类问题(Nondeterministicpolynomial)定义2若一个问题的每个实例只有“是”或“否”两种回答，则称该问题为判定问题。例，TSP的判定问题：给定z，是否存在n个城市的一个排列W，使得f(W)z。满足f(W)z的一个排列W称为判定问题的“是”答案（可行解）。,1.4.2P,NP,NP-C和NP-hard,72,1.4计算复杂性与NP完全问题,智能计算,NP类问题(Nondeterministicpolynomial)若存在一个多项式g(x)和一个验证算法H，对一类判定问题A的任何一个“是”的判定实例I都存在一个字符串S是I的“是”回答，满足其输入长度d(S)不超