智能计算课件：Chapter 0说在前面的话.ppt

1、0请改用自请改用自己的真实己的真实姓名！姓名！智能计算智能计算Intelligent Computation夏顺仁夏顺仁2017年年3月月1日日2优化问题是在工程、技术、经济、管理和科学研究等众多优化问题是在工程、技术、经济、管理和科学研究等众多领域中经常遇到的一个研究问题，具有广泛的理论价值和领域中经常遇到的一个研究问题，具有广泛的理论价值和应用价值。应用价值。最优化问题就是在众多方案中寻找最优方案，即在满足一最优化问题就是在众多方案中寻找最优方案，即在满足一定的约束条件下，寻找一组参数值，以使某种定的约束条件下，寻找一组参数值，以使某种最优化测度最优化测度得到满足，或者使系统的某些性能指标

2、达到最大或最小。得到满足，或者使系统的某些性能指标达到最大或最小。最优化理论是一种以数学为基础的古老课题。最优化理论是一种以数学为基础的古老课题。 长期以来，人们对最优化问题进行了探讨和研究，早在长期以来，人们对最优化问题进行了探讨和研究，早在 17 世纪，世纪，英国英国 Newton 和德国和德国 Leibniz 发明蕴含了优化内容的微积分，而法国数发明蕴含了优化内容的微积分，而法国数学家学家 Cauchy (柯西柯西)首次采用首次采用最速梯度下降法最速梯度下降法解决无约束优化问题，后解决无约束优化问题，后来针对约束优化问题又提出了来针对约束优化问题又提出了 Lagrange 乘数法乘数法。

3、前言前言3问题需要的时间（问题需要的时间（复杂度复杂度）与问题）与问题的规模之间是的规模之间是多项式多项式关系关系 近年来，由于计算机日益广泛应用以及其它相关学科迅猛近年来，由于计算机日益广泛应用以及其它相关学科迅猛地发展，使最优化问题的研究不仅成为一种迫切需要，而地发展，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具。因此，最优化理论和算法迅速发且有了求解的有力工具。因此，最优化理论和算法迅速发展起来，最优化技术在实际应用中正发挥着越来越大的作展起来，最优化技术在实际应用中正发挥着越来越大的作用。用。 传统的优化方法根据问题的性质不同，通常将问题划分为传统的优化方法根据问题的

4、性质不同，通常将问题划分为线性规划问题线性规划问题、非线性规划问题非线性规划问题、整数规划问题整数规划问题和和多目标多目标规划问题规划问题等。相应的传统优化方法如牛顿法、共扼梯度法、等。相应的传统优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法、模式搜索法、单纯形法、Rosenbrock 法和法和 Powell 法，在面法，在面对某些大型问题时，需要遍历整个搜索空间，从而会产生对某些大型问题时，需要遍历整个搜索空间，从而会产生搜索的组合爆炸，无法在搜索的组合爆炸，无法在多项式时间内完成搜索多项式时间内完成搜索。如许多。如许多工程优化问题，由于其性质十分复杂，常常需要在复杂而工程优化问题，由于

5、其性质十分复杂，常常需要在复杂而庞大的搜索空间中寻找庞大的搜索空间中寻找最优解最优解或者或者准最优解准最优解。前言前言4前言前言5传统的优化算法面对这样的大型问题已经无能为力，在传统的优化算法面对这样的大型问题已经无能为力，在计算速度计算速度、收敛性收敛性、初值敏感性初值敏感性等方面都远不能满足要求，等方面都远不能满足要求，工程优化问题的求解很困难，因此寻求高效的优化算法成工程优化问题的求解很困难，因此寻求高效的优化算法成为科学工作者的研究目标之一。为科学工作者的研究目标之一。人类从生命进化过程中得到启示，发明了很多智能优化人类从生命进化过程中得到启示，发明了很多智能优化算法来解决上述复杂优化

6、问题。算法来解决上述复杂优化问题。前言前言6p遗传算法遗传算法(Genetic Algorithm， GA)参考了生物种群通过遗参考了生物种群通过遗传和自然选择不断进化的功能传和自然选择不断进化的功能;p粒子群优化算法粒子群优化算法(Particle Swarm Optimization， PSO)模拟模拟了鸟群觅食迁徙中个体与群体协调一致的机理了鸟群觅食迁徙中个体与群体协调一致的机理;p蚁群算法蚁群算法(Ant Colony Optimization， ACO)模拟了蚂蚁群体模拟了蚂蚁群体在路径选择和信息传递方面的行为在路径选择和信息传递方面的行为;p文化基因算法文化基因算法(Memetic

7、 algorithm， MA)，是一种基于种群，是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。采用不的全局搜索和基于个体的局部启发式搜索的结合体。采用不同的搜索策略可以构成不同的文化基因算法，如同的搜索策略可以构成不同的文化基因算法，如全局搜索全局搜索策策略可以采用遗传算法、进化策略、进化规划等，略可以采用遗传算法、进化策略、进化规划等，局部搜索局部搜索策策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式局部搜索等。引式局部搜索等。前言前言7p人工免疫系统人工免疫系统(Artificial Immune System，

8、AIS)模仿了生物模仿了生物免疫系统的学习和认知功能免疫系统的学习和认知功能;p蛙跳算法蛙跳算法(Frog Leaping Algorithm， FLA)结合了文化基因结合了文化基因和粒子群算法的种群智能优化算法的优点，具有概念简单，和粒子群算法的种群智能优化算法的优点，具有概念简单，调整的参数少，计算速度快，全局搜索寻优能力强，易于实调整的参数少，计算速度快，全局搜索寻优能力强，易于实现的特点。现的特点。p布谷鸟搜索算法布谷鸟搜索算法(Cuckoo Search， CS），也叫杜鹃搜索，也叫杜鹃搜索， 通过模拟某些种属布谷鸟的寄生育雏来有效地求解最优化问通过模拟某些种属布谷鸟的寄生育雏来有效

9、地求解最优化问题的算法。同时，题的算法。同时，CS也采用相关的也采用相关的Levy飞行搜索机制。飞行搜索机制。p头脑风暴优化算法头脑风暴优化算法(Brain Storm Optimization， BSO)，是，是基于人类创造性解决问题的思路而提出的。人类是世界上最基于人类创造性解决问题的思路而提出的。人类是世界上最聪明的动物，聪明的动物，BSO是受其社会性行为启发所产生的优化算法。是受其社会性行为启发所产生的优化算法。前言前言8p细菌捕食算法细菌捕食算法(Bacterial Forging Optimization， BFO) ，基于，基于Ecoli大肠杆菌在人体肠道内吞噬食物行为，具有群体

10、智能算法大肠杆菌在人体肠道内吞噬食物行为，具有群体智能算法并行搜索、易跳出局部极小值等优点，包括趋化并行搜索、易跳出局部极小值等优点，包括趋化(chemotaxis)、复制复制(reproduction)和驱散和驱散(elimination-dispersal)3个步骤。个步骤。p人工蜂群算法人工蜂群算法(Artificial Bee Colony， ABC)，是模仿蜜蜂行，是模仿蜜蜂行为提出的一种优化方法，无需了解问题的特殊信息，只需要对为提出的一种优化方法，无需了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最问题进行优劣的比较，通过各人工蜂个体的局部寻优行

11、为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。终在群体中使全局最优值突现出来，有着较快的收敛速度。p人工鱼群算法人工鱼群算法(Artificial Fish )， 该算法根据水域中鱼生存数该算法根据水域中鱼生存数目最多的地方就是本水域中富含营养物质最多的地方这一特点目最多的地方就是本水域中富含营养物质最多的地方这一特点来模拟鱼群的觅食行为而实现寻优。鱼的三大基本行为：来模拟鱼群的觅食行为而实现寻优。鱼的三大基本行为：觅食、觅食、聚群聚群和和追尾追尾。前言前言9p禁忌搜索算法禁忌搜索算法(Tabu Search 或或 Taboo Search， TS)，从一个，从一个初始可行解出发，

12、选择一系列的特定搜索方向（移动）作为初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让目标函数值变化最多的移动。为避免陷入试探，选择实现让目标函数值变化最多的移动。为避免陷入局部最优解，搜索中采用了灵活的局部最优解，搜索中采用了灵活的“记忆记忆”技术，对已经进技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。行的优化过程进行记录和选择，指导下一步的搜索方向。p人工神经网络技术人工神经网络技术(Artificial Neural Networks， ANN）是）是一种模仿动物神经网络行为特征，进行分布式并行信息处理一种模仿动物神经网络行为特征，进行分布式并行信息处

13、理的算法数学模型的算法数学模型;p模拟退火算法模拟退火算法(Simulated Annealing， SI)思路源于物理学中思路源于物理学中固体物质的退火过程固体物质的退火过程;p前言前言10这些算法的共同点：都是通过模拟或揭示某些自然界的现这些算法的共同点：都是通过模拟或揭示某些自然界的现象和过程得到发展，在优化领域，称之为象和过程得到发展，在优化领域，称之为智能计算智能计算算法，算法，或者或者智能优化智能优化。从实质上来说，从实质上来说，智能计算智能计算算法是一类具有自适应调节功能算法是一类具有自适应调节功能的搜索寻优技术，目前它已经被广泛地应用到组合优化问的搜索寻优技术，目前它已经被广泛

14、地应用到组合优化问题、机器学习、人工生命、自动控制以及动态系统的故障题、机器学习、人工生命、自动控制以及动态系统的故障诊断等领域中。诊断等领域中。前言前言11人工智能人工智能(AI)主要研究用人工的方法和技术，模仿、延伸和主要研究用人工的方法和技术，模仿、延伸和扩展人的智能，实现机器智能。它自扩展人的智能，实现机器智能。它自1956 年被提出以来取年被提出以来取得了很大的进展和成功。得了很大的进展和成功。传统人工智能主要运用知识进行问题求解：以知识为对象，传统人工智能主要运用知识进行问题求解：以知识为对象，研究知识的表示方法、知识的运用和知识获取。研究知识的表示方法、知识的运用和知识获取。近年

15、来神经生理学和脑科学的研究成果表明，脑的感知部近年来神经生理学和脑科学的研究成果表明，脑的感知部分，包括视觉、听觉、运动等脑皮层区不仅具有输入分，包括视觉、听觉、运动等脑皮层区不仅具有输入/输出输出通道的功能，而且具有直接参与思维的功能。智能不仅是运通道的功能，而且具有直接参与思维的功能。智能不仅是运用知识，通过推理解决问题，智能也处于用知识，通过推理解决问题，智能也处于感知通道感知通道。 前言前言12人工智能可以分成两大类：人工智能可以分成两大类：符号智能符号智能与与计算智能计算智能。以知识为基础，通以知识为基础，通过推理进行问题求过推理进行问题求解，也即所谓的传解，也即所谓的传统人工智能。

16、统人工智能。以数据为基础，通过训练建立联系，以数据为基础，通过训练建立联系，进行问题求解。人工神经网络、遗传进行问题求解。人工神经网络、遗传算法、模糊系统、进化程序设计、人算法、模糊系统、进化程序设计、人工生命等都包括在计算智能。工生命等都包括在计算智能。前言前言13计算智能是以计算智能是以生物进化的观点认识和模拟智能生物进化的观点认识和模拟智能。按照这一。按照这一观点，智能是在观点，智能是在生物的遗传、变异、生长以及外部环境生物的遗传、变异、生长以及外部环境的自的自然选择中产生的。在前进废退、优胜劣汰的过程中，适应度然选择中产生的。在前进废退、优胜劣汰的过程中，适应度高的结构被保存下来，智能

17、水平也随之提高，因此计算智能高的结构被保存下来，智能水平也随之提高，因此计算智能就是就是基于结构演化的智能基于结构演化的智能。主要方法：遗传算法、人工神经网络、遗传程序、演化程主要方法：遗传算法、人工神经网络、遗传程序、演化程序、局部搜索、模拟退火等等。它们具有共同的要素：序、局部搜索、模拟退火等等。它们具有共同的要素：自适自适应的结构、随机产生的或指定的初始状态、适应度的评测函应的结构、随机产生的或指定的初始状态、适应度的评测函数、修改结构的操作、系统状态存储器、终止计算的条件、数、修改结构的操作、系统状态存储器、终止计算的条件、指示结果的方法、控制过程的参数指示结果的方法、控制过程的参数。

18、同时具有。同时具有自学习、自组自学习、自组织、自适应织、自适应的特征和的特征和简单、通用、鲁棒性强、适于并行处理简单、通用、鲁棒性强、适于并行处理的优点。在并行搜索、联想记忆、模式识别、知识自动获取的优点。在并行搜索、联想记忆、模式识别、知识自动获取等方面得到了广泛的应用。等方面得到了广泛的应用。前言前言14典型算法：典型算法：遗传算法、粒子群算法、免疫算法、模拟退火遗传算法、粒子群算法、免疫算法、模拟退火算法、蚁群算法，都是一种仿生算法，基于算法、蚁群算法，都是一种仿生算法，基于“从大自然中获从大自然中获取智慧取智慧”的理念，通过人们对自然界独特规律的认知，提取的理念，通过人们对自然界独特规

19、律的认知，提取出适合获取知识的一套计算工具。因此通过自适应学习的特出适合获取知识的一套计算工具。因此通过自适应学习的特性，这些算法达到了全局优化的目的。性，这些算法达到了全局优化的目的。当前计算智能正在蓬勃发展，研究计算智能的领域十分活当前计算智能正在蓬勃发展，研究计算智能的领域十分活跃。虽然智能算法研究水平暂时还很难使跃。虽然智能算法研究水平暂时还很难使“智能机器智能机器”真正真正具备人类的智能，但具备人类的智能，但人工脑人工脑将不仅是模仿生物脑的功能，而将不仅是模仿生物脑的功能，而且两者具有相同的特性，两者的结合将使人工智能的研究向且两者具有相同的特性，两者的结合将使人工智能的研究向着更广

20、和更深的方向发展，计算智能将探索智能的新概念、着更广和更深的方向发展，计算智能将探索智能的新概念、新理论、新方法和新技术，而这些研究将在以后的发展中取新理论、新方法和新技术，而这些研究将在以后的发展中取得重大的成就。得重大的成就。前言前言15群体智能群体智能(Swarm/Collection Intelligence, SI)：源自对自然界源自对自然界中昆虫群体的观察，群居性生物通过协作表现出的宏观智能中昆虫群体的观察，群居性生物通过协作表现出的宏观智能行为特征被称为群体智能。行为特征被称为群体智能。 群体智能的提出由来已久，人们很早以前就发现，在自然界群体智能的提出由来已久，人们很早以前就发

21、现，在自然界中，有的生物依靠其个体的智慧得以生存，有的生物却能依中，有的生物依靠其个体的智慧得以生存，有的生物却能依靠群体的力量获得优势。靠群体的力量获得优势。在这些群体生物中，单个个体没有很高的智能，但个体之间在这些群体生物中，单个个体没有很高的智能，但个体之间可以分工合作、相互协调，完成复杂的任务，表现出比较高可以分工合作、相互协调，完成复杂的任务，表现出比较高的智能。它们具有高度的自组织、自适应性，并表现出非线的智能。它们具有高度的自组织、自适应性，并表现出非线性、涌现的系统特征。性、涌现的系统特征。前言前言16SI遵循的五条基本原则：遵循的五条基本原则：n邻近原则邻近原则( Proxi

22、mity Principle) ，群体能够进行简单的空间，群体能够进行简单的空间和时间计算和时间计算;n品质原则品质原则(Quality Principle) ，群体能够响应环境中的品质，群体能够响应环境中的品质因子因子;n多样性反应原则多样性反应原则( Principle of Diverse Response) ，群体的行，群体的行动范围不应该太窄动范围不应该太窄;n稳定性原则稳定性原则(Stability Principle) ，群体不应在每次环境变化，群体不应在每次环境变化时都改变自身的行为时都改变自身的行为;n适应性原则适应性原则(Adaptability Principle) ，在

23、所需代价不太高的，在所需代价不太高的情况下，群体能够在适当的时候改变自身的行为。情况下，群体能够在适当的时候改变自身的行为。前言前言17SI的特点：的特点：(1) 控制是分布式的，不存在中心控制。因而它更能够适应当前网控制是分布式的，不存在中心控制。因而它更能够适应当前网络环境下的工作状态，并且具有较强的鲁棒性，即不会由于某一络环境下的工作状态，并且具有较强的鲁棒性，即不会由于某一个或几个个体出现故障而影响群体对整个问题的求解。个或几个个体出现故障而影响群体对整个问题的求解。(2) 群体中的每个个体都能够改变环境，这是个体之间间接通信的群体中的每个个体都能够改变环境，这是个体之间间接通信的一种

24、方式，这种方式被称为一种方式，这种方式被称为“激发工作激发工作”(Stigmergy) 。由于群体。由于群体智能可以通过非直接通信的方式进行信息的传输与合作，因而随智能可以通过非直接通信的方式进行信息的传输与合作，因而随着个体数目的增加，通信开销的增幅较小，因此，它具有较好的着个体数目的增加，通信开销的增幅较小，因此，它具有较好的可扩充性。可扩充性。(3) 群体中每个个体的能力或遵循的行为规则非常简单，因而群体群体中每个个体的能力或遵循的行为规则非常简单，因而群体智能的实现比较方便，具有简单性的特点。智能的实现比较方便，具有简单性的特点。(4) 群体表现出来的复杂行为是通过简单个体的交互过程突

25、现出来群体表现出来的复杂行为是通过简单个体的交互过程突现出来的智能的智能( Emergent Intelligence) ，因此，群体具有自组织性。，因此，群体具有自组织性。前言前言18本课程将概述几种智能计算的有关理论、技术。本课程将概述几种智能计算的有关理论、技术。通过对基准函数、遗传算法、粒子群优化、细菌捕食、模通过对基准函数、遗传算法、粒子群优化、细菌捕食、模糊逻辑、头脑风暴等智能计算方法的学习，希望大家理解并糊逻辑、头脑风暴等智能计算方法的学习，希望大家理解并掌握这些算法的基本流程，掌握基本应用技能，理解系统设掌握这些算法的基本流程，掌握基本应用技能，理解系统设计的思想，从而为后续相

26、关研究提供必要的基础。计的思想，从而为后续相关研究提供必要的基础。 授课形式：授课形式：专题讲座专题讲座自学自学自主实验自主实验 考核形式：考核形式：独立研究实践独立研究实践报告报告前言前言课程网站：课程网站：http:/ or http:/znjs.jpkc.cc/19参考教材：参考教材： Eberhart，史玉回，智能计算从概念到实现，人，史玉回，智能计算从概念到实现，人民邮电出版社，民邮电出版社，2009.2 焦李成等，免疫优化计算、学习与识别，科学出焦李成等，免疫优化计算、学习与识别，科学出版社，版社，2007.7 纪震等，粒子群算法及应用，科学出版社，纪震等，粒子群算法及应用，科学出版社，2009.1 谭营译，计算群体智能基础，清华大学出版社，谭营译，计算群体智能基础，清华大学出版社， 2009.10. 谭营译，计算智能导论，谭营译，计算智能导论， ，清华大学出版社，清华大学出版社， 2010.6.前言前言20