智能算法.ppt

智能算法 谷俊峰 工业装备结构分析国家重点实验室 工程力学系 运载工程与力学学部 n课程名称 智能算法 n教师联系方式 办公地点综合实验楼1号楼610 Tel13840882960 E-mail n上课时间地点（10-17周） 周三 34节，综362 周五 78节，综362 教学信息 2 n课程目标 1）掌握智能算法的基本概念和原理； 2）学会用智能算法解决优化问题。 n课程重点应用领域 组合优化 n课程要求 u 了解各主要智能算法的起源、原理、操作和应用领域 u 掌握主要智能算法求解优化问题的流程 u 学会智能算法在实际中的应用 课程介绍 3 n课程设计论文和课上报告 n实现实际或者虚拟优化问题的求解。（鼓励与实际问题或者本人未 来研究领域的结合） n在网上下载（一种或多种）智能优化程序；如果自己编程实现更好 ，加分；如果对网上下载程序或自己的编程进行了某种算法上的改进 也很好（加分）。 n论文要求将要优化的问题、所用智能优化方法、计算结果及对结 果的简单分析写成论文，论文格式见样板论文。 n报告要求简要说清所要解决问题以及所用方法和计算结果。ppt 课程考核 4 课程内容 1 绪论 2 遗传算法（1） 3 遗传算法（2） 4 人工神经网络 5 模拟退火算法 6 群智能算法（粒子群，蚁群） 7 模糊逻辑 8 课程汇报 5 nAndries P. Engelbrecht, Computational Intelligence A Introduction, Wiley, New York, 2002. ISBN 0-470-84870-7. n丁永生编著，计算智能理论、技术与应用，科学出 版社，2004.8. ISBN7-03-013902-X. P.481. TP183/27 n褚蕾蕾，陈绥阳，周梦编著，计算智能的数学基础，科 学出版社，2002. TP183/15 n徐宗本，张讲社，郑亚林， 编著，计算智能中的仿生学 理论与算法，科学出版社，2003.5，ISBN7-03-010792-6. P.315. TP183/17 n徐宗本，编著，计算智能（第一册）---模拟进化计算， 高等教育出版社，2004.2，ISBN7-04-013839-5. P.141. n王国俊，编著，计算智能（第二册）---词语计算与Fuzzy集 ，高等教育出版社，2005.2，ISBN7-04-016032-3. P.106. TP183/312 n罗四维，著，大规模人工神经网络理论基础，清华大学 出版社和北方交通大学出版社，2004.2，ISBN7-81082-174-1. P.177. 课程参考书 6 课程参考书 nHaykin S. Neural Networks A Comprehensive Foundation, Macmillan, IEEE Press, 1994. n张乃尧、阎平凡编著，神经网络与模糊控制，清华大学出版 社，2002。 n王小平，曹立明编著，遗传算法--理论、应用与软件实现， 西安交通大学出版社，2002.1。 n张颖，刘艳秋等，软计算方法，科学出版社，2002。 n谷荻隆嗣等，人工神经网络与模糊信号处理，科学出版社， 2003。 n李士勇等，蚁群算法及其应用哈尔滨工业大学出版社， 2004.9 n陈国良、王煦法、庄镇权等，遗传算法及其应用，人民邮电 出版社，1995。 n史忠植，知识发现，清华大学出版社，2002。 n傅京孙等，人工智能及其应用，清华大学出版社，1987。 n蔡自兴、徐光佑，人工智能及其应用清华大学出版社，1996 n蔡自兴， 智能控制---基础与应用，国防工业出版社，1998。 n刘金琨编著， 智能控制， 电子工业出版社，2005.5。 7 第一章 绪论 智能算法 8 提纲 1.1 智能算法 1.2 优化的概念 1.3 优化算法 1.4 计算复杂性 1.5 本章小结 9 1.1 什么是智能 n从感觉到记忆到思维这一过程，称为“智慧”，智慧的结果就产生 了行为和语言，将行为和语言的表达过程称为“能力”，两者合称“智 能”，将感觉、去记、回忆、思维、语言、行为的整个过程称为智能 过程，它是智力和能力的表现。它们分别又可以用“智商”和“能商” 来描述其在个体中发挥智能的程度。“情商”可以调整智商和能商的 正确发挥，或控制二者恰到好处地发挥它们的作用。 n智能及智能的本质是古今中外许多哲学家、脑科学家一直在努力 探索和研究的问题，但至今仍然没有完全了解，以致智能的发生与 物质的本质、宇宙的起源、生命的本质一起被列为自然界四大奥秘 。 n近年来，随着脑科学、神经心理学等研究的进展，人们对人脑的 结构和功能有了初步认识，但对整个神经系统的内部结构和作用机 制，特别是脑的功能原理还没有认识清楚，有待进一步的探索。因 此，很难对智能给出确切的定义。 10 1.1 智能的分类 根据加德纳的多元智能理论，人类的智能可以分成八个范畴 1、语言智能 Linguistic intelligence） 是指有效的运用口头语言或及文字表达自己的思想并理解他人 ，灵活掌握语音、语义、语法，具备用言语思维、用言语表达和欣 赏语言深层内涵的能力结合在一起并运用自如的能力。他们适合的 职业是政治活动家，主持人，律师， 演说家， 编辑， 作家， 记 者，教师等。 2、数学逻辑智能 Logical-Mathematical intelligence 是指有效地计算、测量、推理、归纳、分类，并进行复杂数学 运算的能力。这项智能包括对逻辑的方式和关系，陈述和主张，功 能及其他相关的抽象概念的敏感性。他们适合的职业是科学家、 会计师、统计学家、工程师、电脑软体研发人员等。 3、空间智能 Spatial intelligence 是指准确感知视觉空间及周围一切事物，并且能把所感觉到的 形象以图画的形式表现出来的能力。这项智能包括对色彩、线条、 形状、形式、空间关系很敏感。他们适合的职业是室内设计师、 建筑师、摄影师、画家、飞行员等。 11 1.1 智能的分类 4、身体运动智能 Bodily-Kinesthetic intelligence 是指善于运用整个身体来表达思想和情感、灵巧地运用双手制 作或操作物体的能力。这项智能包括特殊的身体技巧，如平衡、协 调、敏捷、力量、弹性和速度以及由触觉所引起的能力。他们适合 的职业是运动员、演员、舞蹈家、外科医生、宝石匠、机械师等 。 5、音乐智能 Musical intelligence 是指人能够敏锐地感知音调、旋律、节奏、音色等能力。这项 智能对节奏、音调、旋律或音色的敏感性强，与生俱来就拥有音乐 的天赋，具有较高的表演、创作及思考音乐的能力。他们适合的职 业是歌唱家、作曲家、指挥家、音乐评论家、调琴师等。 6、人际智能 Interpersonal intelligence 是指能很好地理解别人和与人交往的能力。这项智能善于察觉 他人的情绪、情感，体会他人的感觉感受，辨别不同人际关系的暗 示以及对这些暗示做出适当反应的能力。他们适合的职业是政治 家、外交家、领导者、心理咨询师、公关人员、推销等。 12 1.1 智能的分类 7、自我认知智能 Intrapersonal intelligence 是指自我认识和善于自知之明并据此做出适当行为的能力。这 项智能能够认识自己的长处和短处，意识到自己的内在爱好、情绪 、意向、脾气和自尊，喜欢独立思考的能力。他们适合的职业是 哲学家、政治家、思想家、心理学家等。 8、自然认知智能 Naturalist intelligence 是指善于观察自然界中的各种事物，对物体进行辨别和分类的 能力。这项智能有着强烈的好奇心和求知欲，有着敏锐的观察能力 ，能了解各种事物的细微差别。他们适合的职业是天文学家、生 物学家、地质学家、考古学家、环境设计师等。 智能是指个体对客观事物进行合理分析、判断及有目 的地行动和有效地处理周围环境事宜的综合能力。 13 n智能的三个层次（1994年，James C. Bezdek） v生物智能（Biological Intelligence, BI） 由人脑的物理化学过 程反映出来的，人脑是有机物，它是智能的基础； v人工智能（Artificial Intelligence, AI） 是非生物的，人造的 ，常用符号来表示，AI的来源是人类知识的精华。 v计算智能（Computational Intelligence, CI） 是由数学方法和 计算机实现的，CI的来源是数值计算的传感器。 从复杂性看 BI AI CI AI是CI到BI的过渡，因为AI中除计算算法之外，还包括符号表示 及数值信息处理。模糊集合和模糊逻辑是AI到CI的过渡。 1.1 智能的层次 14 1.1 人工智能 n什么是人工智能 能力方面 人工智能就是用人工的方法在机器（计算机）上实 现的智能，或称机器智能 学科方面 是一门研究如何构造智能机器或智能系统，以模拟 、延伸和扩展人类智能的学科 nAI的主要研究和应用领域 机器思维、机器感知、机器行为、计算智能计算智能、机器 学习、 分布智能、智能系统、人工心理与人工情感、人 工生命、人工智能的典型应用 15 1.1 计算智能与人工智能 计算智能和人工智能的联系 从关系上说，计算智能属于人工智能的一个分支 人工智能 AI 符号主义 AI起源于数理逻辑，人类认知 的基元是符号，认知过程是符 号表示上的一种运算 行为主义 AI起源于控制论，智能取决于 感知和行为，取决于对外界复 杂环境的适应，而不是推理 联结主义 AI起源于仿生学，特别是人脑 模型，人类认知的基元是神经 元，认知过程是神经元的连接 活动过程 16 1.1 计算智能 n计算智能（Computational Intelligence，CI）是从模 拟自然界生物体系和人类智能现象发展而来，用计算机 模拟和再现自然界的某些智能行为，并用于改造自然的 工程实践的算法总称，是一种新型人工智能研究领域， 也称为智能算法。 n计算智能的三大基本领域包括神经计算、进化计算、 模糊计算。 17 1.1 计算智能的分类 n计算智能 进化计算 神经计算 模糊计算 单点搜索 遗传算法（进化策略，进化规划） 蚁群优化算法 粒子群优化算法 免疫算法 分布估计算法 Memetic算法 人工神经网络 模糊逻辑 模拟退火算法 禁忌搜索算法 18 1.1 计算智能研究领域的主要特点 研究领域主要特点 进进进进化化计计计计算算 模仿生物进化过程和群体智能过程， 模拟大自然的智慧；提供进行随机搜索 和优化的能力 人工神人工神经经经经网网络络络络 模仿人脑的生理构造和信息处理的过 程，模拟人类的智慧；提供系统学习 和适应的能力 模糊模糊逻辑逻辑逻辑逻辑 模仿人类语言和思维中的模糊性概念 ，模拟人类的智慧；提供处理非精确 性和进行近似推理的能力 19 1.1 计算智能发展历程 起步阶段 1950-1969 发展阶段 1970-1989 继续发展 1990年之后 （1）50年代，美国学者Holland，遗传算法 （2）60年代，德国人Rechenberg和Schwefel，进化策略 （3）60年代，美国学者Fogel，进化规划 （4）50年代，Rosenblatt等人，感知器（神经网络） （5）60年代，Zadeh，模糊逻辑理论 （1）遗传算法、进化策略、进化规划的理论基础不断完善（模式 定理），算法之间的区别越来越不明显 （2）80年代，模拟退火算法（1983年）、禁忌搜索算法（1986） 的提出提供了新的优化手段 （3）Hopfield前馈型神经网络结构（1982年）、Rumelhart后向传 播学习算法（1986年）的提出将神经网络的研究推向一个新的学习 高潮 （1）遗传算法（GA）、进化策略（ES）和进化规划（EP）算法 也在不断的发展和完美 （2）1992年，Dorigo等人提出了蚁群算法（ACO），为解决离散 组合优化问题提供了重要的工具 （3）1995年，在Eberhart和Kennedy提出的粒子群优化算法（PSO） 在连续优化问题上得到了广泛的应用 20 1.1 计算智能的特征 主要特征具体特点 智能性智能性 包括算法的自适应性、自组织性，算 法不依赖问题 本身的特点，具有通用 性 并行性并行性 算法基本上是以群体协作的方式对问 题进行优化求解，非常适合大规模并 行处理 健壮性健壮性 算法具有很好的容错性，同时对初始 条件不敏感，能在不同条件下寻找最 优解 21 1.1 计算智能的应用 已应用在优化计算、模式识别、图像处理、自动控制、经济管理、 机械工程、电气工程、通信网络和分子生物学等多个领域，涉及国 防、科技、经济、工业和农业等各个方面 计算智能的主要应用 国防科技经济工业农业 雷达天线设计 卫星轨道参数优化 战场模拟 军事物流优化 干扰抑制 机器学习 数据挖掘 图像处理 模式识别 蛋白质结构预测 多目标优化 多播路由 金融数据分析 证券投资组合 企业现金流管理 企业财务分析与预警 功率电子电路优化 电磁过滤 输电网规划 工作流调度管理 车辆路由 交通控制 排灌工程 水利水电工程 温室控制 水库防洪 农业工程 22 优化问题的数学形式为 1.2 优化问题的定义 如果没有约束，则最优化问题称为无约束最优化问题 X 设计变量； f 目标函数 ； g, h 约束函数 什么是优化就是从各种方案中选取一个最好的。 从数学角度看，优化理论就是研究如何在状态空间中寻找到全 局最优点。 23 根据决策变量xi的取值类型 函数优化 组合优化 混合型优化问题 1.2 优化问题的分类 分类标志 变量个数 变量性 质 约束条件极值个数目标个数函数关系 问题性 质 时间变 化 类型 单变量连续无约束单峰单目标线性确定性静态 离散随机性 多变量混合有约束多峰多目标非线性模糊性动态 24 1.2 函数优化问题 n函数优化问题对应的决策变量均为连续变量，优化 问题 f 的目标函数取决于其对应的连续变量x1, x2, , xn的取值。 n各个取值变量可能是独立的，也可能是互相关联、 互相制约的，他们的取值组合构成了一个问题的解。 n由于决策变量是连续值，因此对每个变量进行枚举 是不可能的。 25 nBenchmark问题典型特点 n单极小 n非凸 n非线性 n多极小 n高维 n强振荡 n噪声 n不可微 1.2 函数优化问题 26 1.2 函数优化问题 n测试函数（Benchmark问题） （1）Sphere Model 其最优状态和最优值为 27 n测试函数 （2）Schwefels Problem 2.22 其最优状态和最优值为 1.2 函数优化问题 28 n测试函数 （3）Schwefels Problem 1.2 其最优状态和最优值为 1.2 函数优化问题 29 n测试函数 （4）Schwefels Problem 2.21 其最优状态和最优值为 1.2 函数优化问题 30 n测试函数 （5）Generalized Rosenbrocks Function 其最优状态和最优值为 1.2 函数优化问题 31 n测试函数 （6）Quartic Function i.e. Niose 其最优状态和最优值为 1.2 函数优化问题 32 n测试函数 （7）Generalized Schwefels Problem 2.26 其最优状态和最优值为 1.2 函数优化问题 33 n测试函数 （7）Generalized Schwefels Problem 2.26 1.2 函数优化问题 34 n测试函数 （8）Generalized Rastrigins Function 其最优状态和最优值为 1.2 函数优化问题 35 n测试函数 （9）Ackleys Function 其最优状态和最优值为 1.2 函数优化问题 36 n测试函数 （9）Ackleys Function 1.2 函数优化问题 37 n测试函数 （10）Generalized Griewank Function 其最优状态和最优值为 1.2 函数优化问题 38 n测试函数 （10）Generalized Griewank Function 1.2 函数优化问题 39 n测试函数 （11）Six-Hump Camel-Back Function 其最优状态和最优值为 1.2 函数优化问题 40 n测试函数 （12）Branin Function 其最优状态和最优值为 1.2 函数优化问题 41 n测试函数 （13）J. D. Schaffer 其最优状态和最优值为 1.2 函数优化问题 42 n测试函数 （22）J. D. Schaffer 此函数在距全局最优点大约3.14范围内存在无穷多个局部极 小将其包围，并且函数强烈振荡。 1.2 函数优化问题 43 1图解法 设计空间 目标函数等值面 约束曲面 可行设计/不可行设计 可行区域 1.2 函数优化问题 n 有约束的函数优化 44 n有约束的函数优化 2 解的影响因素 （1）曲面拓扑性质，线性或凸函数比无规律的函数更容 易求解； （2）可行区域的疏密程度，通常以可行区域占整个搜索 空间的比值来度量； （3）整体最优解与可行区域最优解之比； （4）在最优解处活跃约束的数目，活跃约束数目越多则 最优解离可行区域的边界越近。 1.2 函数优化问题 45 n有约束转化为无约束的处理 1.2 函数优化问题 46 1.2 组合优化问题 n数学表述 n通俗定义所谓组合优化，是指在离散的、有限的数学结构上，寻 找一个（或一组）满足给定约束条件并使其目标函数值达到最大或最小 的解。组合优化问题通常带有大量的局部极值点，往往是不可微的、不 连续的、多维的、有约束条件的、高度非线性问题。 n所属范畴 涉及离散事件的最优编排、分类、次序筛选等 问题，是运筹学的一个重要分支。 47 n典型问题旅行商问题（Traveling salesman problem, TSP） 管梅谷教授1960年首先提出，国际上称之为中国邮递员 问题。 问题描述一商人去n个城市销货，所有城市走一遍再回 到起点，使所走路程最短。 1.2 组合优化问题 48 1.2 组合优化问题 12 34 12 18 10 3 2 使得 最小. 即寻找一个排列 X v1，v2，，vn， 49 n典型问题旅行商问题 计算复杂度指数灾难 城市数2425262728293031 计算 时间 1 sec 24 sec 10 min 4.3 hour 4.9 day 136.5 day 10.8 year 325 year 1.2 组合优化问题 50 n典型问题加工调度问题（Scheduling problem） Job-shopn个不同的工件在m台不同机器上加工，已知第i个工件 在第j台机器上的操作时间为Tij 。事先给定各工件在各机器上的加工次 序（技术约束条件），要求确定与技术约束条件相容的各机器上所有工 件加工顺序，使得加工所有工件的性能指标达到最优（或时间最小） 对工件和机器的约束 1 一个工件不能两次访问同一机器； 2 不同工件的工序之间没有先后约束； 3 工序一旦进行不能中断； 4 每台机器一次只能加工一个工件。 1.2 组合优化问题 51 n典型问题01背包问题（Knapsack problem） 对于n个体积为ai、价值分别为ci的物品，如何将它们装 入总体积为b的背包中，使得所选物品的总价值最大。 数学表达式 1.2 组合优化问题 52 n典型问题装箱问题（Bin packing problem） 有n个尺寸为c的箱子，有n个体积分别为wj （不超过c）的 物品, 如何将这些物品装入箱子，使得所需箱子的个数最少。 i为箱子下标；j为物品的下标 。 1.2 组合优化问题 53 n典型问题图着色问题（Graph coloring problem） 对于n个顶点的无环图G，要求对其各个顶点进行着色， 使得任意两个相邻的顶点都有不同的颜色，且所用颜色种 类最少。 C1第一种颜色 C2第二种颜色 C3第三种颜色 C1 C1C2 C3 C2 A B D CE 1.2 组合优化问题 54 n典型问题图着色问题（Graph coloring problem） 西澳大 利亚 北领地 南澳大 利亚 昆士兰 新南威 尔士 维多利亚 塔斯马尼亚 澳大利亚图形着色问题 1.2 组合优化问题 55 n典型问题图着色问题 中国政区图 个省 个自治区 个直辖市 个特别行政区 1.2 组合优化问题 56 n典型问题聚类问题（Clustering problem） m维空间上的n个模式Xi|i1,2,,n，要求聚成k类，使得 各类本身内的点最相近，如要求 其中Rp为第p类的中心，即 其中，p1,2,,k，np为第p类中的点数。 1.2 组合优化问题 57 n典型问题聚类问题 选址问题设要选定一个供应中心的位置, 这个供应中心为城市中有固定 位置的m个用户服务。供应中心的定位准则是使中心到用户的某个距离 函数值最小。如何选定供应中心的位置, 使其到各个用户的距离总和 S 最 小或者最大距离 d 最小。 , 供应中心位置为 设m个用户的位置分别为 OR 1.2 组合优化问题 58 nBenchmark问题 n城市TSP问题（n30，50，75） Hopfield-10城市TSP问题 Grotschel-442城市TSP问题 Car n Flow-shop问题（n1,2,,8） Rec n Flow-shop问题（n1,3,5,,39,41） FT n or MT n Job-shop问题（n6,10,20） LA n Job-shop问题（n1,6,11,16,21,26,31,36） 1.2 组合优化问题 59 1.3 优化算法 n优化算法定义 所谓优化算法, 其实就是一种搜索过程或规则, 它基于某种原理和 机制, 通过一定的途径或规则来得到满足用户要求的问题的解. n优化算法分类 n局部优化算法 又可以称为经典优化算法，已经得到了人们广泛深入的 研究。目前，运筹学（确定论方法）主要包括这些方面的内容，线 性规划、整数规划、01规划、非线性规划、排队论、决策论。 n全局性优化算法 习惯上称为智能优化算法，是20世纪80年代兴起的新型 全局性优化算法，主要包括禁忌搜索、模拟退火、遗传算法等，其 主要应用对象是优化问题中的难解问题，即NPhard问题。 60 1.3 优化算法 n经典算法 n经典优化算法主要用于解决凸问题或单峰问题，通 常使用确定性搜索策略，其基本思想是在状态转移过程 中，只接受更好的状态，拒绝恶化的状态。 n线性问题单纯形法、椭球算法（多项式算法）， 内点法； n无约束的优化算法包括最速下降法、共轭梯度法 、牛顿法、拟牛顿法、信赖域法。 n约束优化算法包括拉格朗日乘子法，序列二次规 划等。 61 1.3 最速下降法 见右图。局部极小值是C点 x0 梯度，即导数，但是有方向，是 一个矢量。曲线情况下，表达式为 如果，fx0，则x增加，y也增加，相当于B点；如果fx0，则x增加，y 减小，相当于A点。 要搜索极小值C点，在A点必须向x增加方向搜索，此时与A点梯度方向相 反；在B点必须向x减小方向搜索，此时与B点梯度方向相反。总之，搜索 极小值，必须向负梯度方向搜索。 62 1.3 最速下降法 一般情况下分析 yfx1, x2, , xn 假设只有一个极小点。初始给定参数为 x10, x20, , xn0。 问题从这个点如何搜索才能找到原函数的极小值点问题从这个点如何搜索才能找到原函数的极小值点 63 1.3 最速下降法 步骤 1、首先设定两个较小的正数, ; 2、求当前位置处的各个偏导数dy/dx1, dy/dx2, , dy/dxn; 3、按照下述方式修改当前函数的参数值 x11 x10dy/dx1, x21 x20dy/dx2, , xn1 xn0dy/dxn; 4、如果超曲面参数变化量小于，退出；否则返回2。 64 1.3 最速下降法 计算过程 任给一个初始出发点，设为x0-4 1 首先给定两个参数 1.5， 0.01 ； 2 计算导数dy/dx x-2 3 计算当前导数值y -6 4 修改当前参数 x0 -4 x1 x0 - *y -4-1.5*-6 5.0; x0 x1 65 1.3 最速下降法 5 计算当前导数值y 3.0 6 修改当前参数 x1 5.0 x2 5.0 1.5*3.0 0.5; 7 计算当前导数值 y -1.5 8 修改当前参数 x2 0.5 x3 0.5-1.5*-1.5 2.75; x0 x1 x2 x3 66 1.3 最速下降法 9 计算当前导数值y 0.75 10 修改当前参数 x3 2.75 x4 2.75-1.5*0.75 1.625; 11 计算当前导数值 y -0.375 12 修改当前参数 x4 1.625 x5 1.625-1.5*-0.375 2.1875; x0 x1 x2 x3 x4 x5 67 1.3 最速下降法 n可见，当1.5时，搜索呈现振荡形式，在极值点附近反复搜索。 可以证明，当2.0时，搜索将围绕极值点逐渐发散，不会收敛到极值点。 n为了保证收敛，不应当太大。但如果过小，收敛速度将十分缓 慢。可以采用自适应调节的方法加快收敛而又不至于发散。 n n 问题为何当问题为何当 很小时搜索总会成功很小时搜索总会成功 68 1.3 经典算法 n经典算法 n传统实际问题的特点 连续性问题主要以微积分为基础，且问题规模较 小 n追求准确 精确解 n理论的完美 结果漂亮 n主要方法 线性与非线性规划、动态规划、多目标规划 、整数规 划等；排队论、库存论、对策论、决策论等。 n传统的评价方法 算法收敛性（从极限角度考虑） 收敛速度（线性、超线性、二次收敛等） 69 1.3 智能优化算法 n一个优化问题称为是复杂的，通常是指具有下列特征 （1）目标函数没有明确解析表达； （2）目标函数虽有明确表达，但不可能恰好估值； （3）目标函数为多峰函数； （4）目标函数有多个，即多目标优化 n一个优化问题被称为是困难的，通常是指 n目标函数或约束条件不连续、不可微、高度非线性 n问题本身是困难的组合问题。 70 1.3 智能优化算法 n智能优化算法主要用于求解非凸问题或多峰问题 n通常使用概率性搜索策略，即状态转移规则，这是由于实 际的全局性优化问题通常没有解析表达式或者解析表达式非 常复杂难以进行理论分析。 n其基本思想是在可行域中从给定的一个或多个随机初始点 出发进行搜索，利用适当的状态转移规则和合理的概率性状 态接收规则搜索新的更优点，在确定的时间或搜索次数之内 停止算法。 71 1.3 智能优化算法 n经典优化算法与智能优化算法 n经典算法是以一个可行解为迭代的初始值，而智能算法是以一组 可行解为初始值； n经典算法的搜索是确定性的，而智能算法的搜索策略是结构化和 随机化； n经典算法大多都需要导数信息，而启发式算法仅用到目标函数值 的信息； n经典算法对函数性质有着严格要求，而启发式算法对函数性质没 有太大要求； n经典算法的计算量要比启发式算法小的多。 72 1.3 智能优化算法 n局部性和全局性 n优化算法主要由搜索方向和搜索步长组成。经典算法的搜索方向 和搜索步长是由局部信息（如导数）决定的所以只能对局部进行有效的 深度搜索，而不能进行有效的广度搜索，这就导致易于陷入局部极优解 而无法用于解决多峰问题；同时，全局性优化算法采用适当的状态转移 规则和概率性状态接受规则，能够避免过早地陷入局部极优解从而搜索 到全局性最优解，但增加了计算量。 n通常，局部优化算法能够快速地收敛到局部极优解，而全局性优 化算法通过概率搜索可以获得在概率意义上尽可能好的全局性最优解区 域，但是其局部极优点搜索能力较低。这是全局搜索算法和局部搜索算 法之间的固有矛盾。对此人们进行了多种研究。基本解决方法在于二者 的结合，即利用全局性优化算法在整个可行域中搜索最优区域，利用局 部搜索算法搜索最优区域中的最优解。 73 n现代问题的特点 离散性问题主要以组合优化理论为基础 不确定性问题随机性数学模型 半结构或非结构化的问题计算机模拟、决策支持系统 大规模问题并行计算、大型分解理论、近似理论 n智能优化方法 追求满意近似解 实用性强解决实际问题 n智能优化算法的评价方法 计算复杂性 1.3 智能优化算法 74 1.4 计算复杂性 n时间复杂性和空间复杂性概念 算法的时间复杂性算法对时间的需要量（加、减、 乘、除、比较、读、写等操作的总次数）； 算法的空间复杂性算法对空间的需要量（存储空间 的大小，二进制位数）； 问题的时间复杂性所有算法中时间复杂性最小的算 法时间复杂性； 问题的空间复杂性所有算法中空间复杂性最小的算 法空间复杂性； n按照计算复杂性理论研究问题求解的难易程度, 可把问题 分为P类、NP类和NP完全类. 75 n复杂性表示方法 算法或者问题的复杂性可以表示为问题规模n（如 TSP的城市数）的函数， 时间复杂性Tn，关键操作的次数； 空间复杂性Sn，占用的存储单元数量； 1.4 计算复杂性 计算复杂性的基本概念计算复杂性的基本概念 76 1.4 计算复杂性 TSP问题的复杂性计算 77 n多项式算法与非多项式算法 若算法A的时间复杂性为TAnOpn，Opn 为复杂性函数pn主要项的阶，且pn为n的多项式函数 ，则称算法A为多项式算法。 当不存在多项式函数pn时，称相应的算法为非多项 式时间算法或指数时间算法； 随着变量的增加，多项式函数增长的速度比指数函数 和非多项式函数增长的速度要慢得多。 1.4 计算复杂性 78 1.4 计算复杂性 设我们有一台每小时能作M次运算的计算机，并设求解某一问题 已有了两个不同的算法。算法A对规模为n的实例约需作n2次运算 ，而算法B则约需作2n次运算。于是，运用算法A在一小时内大约 可解一个规模为 的实例，而算法B则只能解一个规模为log2M 的问题 两者的差别究竟有多大呢让我们用数字来对比一下。假如计 算机每秒钟可作100万次运算，则算法A一小时大约可解一个规 模为n60000的实例，而算法B在一小时内只能解一个规模小于 28的实例且n每增加1，算法B求解时所化的时间就将增加1倍。 例如算法B求解一个n50的实例将连续运算357年。 多项式算法与非多项式时间算法 79 1.4 计算复杂性 几个多项式时间和指数时间算法的计算时间增长情况 算法要求的计计算 量 规规模n的近似值值 101001000 N101001000 Nlogn336649966 N3103106109 2n10241.2710301.0510301 N3628800101584102567 80 nP类问题（ deterministic polynomial ） 具有多项式时间求解算法的问题类.如果计算工作量在 计算数据规模n的多项式（如n，n2，n3等）的范围内，则 计算花费的机时是可以接受的，该问题称为P问题； 1.4 计算复杂性 从上一节中我们已经看出，在设计离散问题的算法时，应从上一节中我们已经看出，在设计离散问题的算法时，应 当去设计次数尽可能低的多项式时间算法。当去设计次数尽可能低的多项式时间算法。 81 n定义确定性算法 n设A是求解问题的一个算法，如果在算法的整个执行过程中 ，每一步只有一个确定的选择，则称算法A是确定性算法； n定义非确定性算法 n设A是求解问题的一个算法，如果算法A是以以下猜测验证 的方式工作，称算法A为非确定性算法。 猜测阶段对问题的输入实例产生一个任意字串y，在 算法的每次运行，y可能不同，因此猜测是以非确定的形式工作。 验证阶段在这个阶段，用一个确定性算法验证两件事 首先验证猜测的y是否是合适的形式，若不是，则算法停下并回答 no；若是合适形式，则继续检查它是否问题的解，如果确实是的 解，则停下并回答yes，否则停下并回答no。要求验证阶段在多项式 时间内完成。 1.4 计算复杂性 82 1.4 计算复杂性 nNP类问题Non-deterministic Polynomial Problem 如果对于判定问题，存在一个非负整数k，对于输入规 模为n的实例，能够以Onk的时间运行一个非确定性算法 ，得到yes/no的答案，则该判定问题是一个NP类问题。 NP类问题是指一类可以用不确定性多项式算法求解 的判定问题。比如TSP问题的判定版本就是一个NP类问题 。虽然还不能找到一个多项式的确定性算法求解最小的周 游路线，但是可以在一个多项式时间内对任意生成的一个“ 路线”判定是否合法。 83 1.4 计算复杂性 nP与NP的关系 n若问题属于P类，则存在一个多项式时间的确定性算法， 对它进行判定或求解；显然，也可以构造一个多项式时间的非确 定性算法，来验证解的正确性，因此，问题也属NP类。因此，显 然有 n若问题属于NP类，则存在一个多项式时间的非确定性算 法，来猜测并验证它的解；但不一定能构造一个多项式时间的确 定性算法，来对它进行求解或判定。 nPNP 84 1.4 计算复杂性 nNP完全问题 一个判定问题D是NP完全问题的条件是 （1）D属于NP类 （2）NP中的任何问题都能够在多项式时间内转化 为D nNP难问题 一个满足条件（2）但不满足条件（1）的问题被称 为NP难问题。 85 1.4 计算复杂性 nNP完全问题是NP类问题中最难的一类问题，至今已经发现了几 千个，但一个也没找到多项式时间算法。 n如果