2010建模竞赛暑期培训人工智能优化算法

主讲教师：杨晓慧E-mail:算法介绍(AlgorithmIntroduction)2010年全国大学生数学建模竞赛暑期培训数学与信息科学学院，2010年7月23日2数学建模十大算法蒙特卡罗算法数据拟合、参数估计、插值等数据处理算法线性规划等规划类问题图论算法动态规划、回溯搜索、分支定界等计算机算法模拟退火、神经网络、遗传算法等最优化理论算法网格算法和穷举法一些连续离散化方法数值分析算法图像处理算法33人工智能优化算法人工神经网络模拟退火遗传算法进化算法*粒子群算法*蚁群算法……4认识“人工智能”人工智能(ArtificialIntelligence,AI)概念是JohnMcCarthy

于1956年在Dartmouth学会上提出的。美国计算机科学家，因在人工智能领域的重大贡献，被称为“人工智能之父”，并因此获得图灵奖他于1948年获得加州理工学院数学学士学位，1951年获得普林斯顿大学数学博士学位JohnMcCarthy5认识“人工智能”（续）人工智能——让机器像人一样思考人工智能是计算机科学的前沿学科，是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学.计算机编程语言和其它计算机软件都因为有了人工智能的进展而得以存在。人工智能涉及学科：哲学和认知科学，数学，神经生理学，心理学，计算机科学，信息论，控制论，不定性论，仿生学等6认识“人工智能”（续）人工智能的目的：通过研究人脑的组成机理和思维方式，企图了解智能的实质，并生产出一种能以人类智能相似的方式做出反应的智能机器——让机器具有智慧，像人一样思考.计算机的出现——人类开始真正有了一个可以模拟人类思维的工具人工智能的领域研究：包括机器人、语言识别、图像识别、自然语言处理和专家系统等.7意识和人工智能的区别人工智能就其本质而言，是对人的思维的信息过程的模拟.对于人的思维模拟可以从两条道路进行：

结构模拟：仿照人脑的结构机制，制造出“类人脑”的机器；功能模拟：暂时撇开人脑的内部结构，而从其功能过程进行模拟。现代电子计算机的产生便是对人脑思维功能的模拟，是对人脑思维的信息过程的模拟.人工智能不是人的智能，更不会超过人的智能.8意识和人工智能的区别（续）“机器思维”同“人类思维”的本质区别：

1.人工智能纯系无意识的机械的物理的过程，人类智能主要是生理和心理的过程.2.人工智能没有社会性.

3.人工智能没有人类的意识所特有的能动的创造能力.4.两者总是人脑的思维在前，电脑的功能在后.9人工智能专业机构美国1.MassachusettsInstituteofTechnology麻省理工学院2.StanfordUniversity斯坦福大学(CA)3.CarnegieMellonUniversity卡内基美隆大学(PA)4.UniversityofCalifornia-Berkeley加州大学伯克利分校……中国1.北京大学2.清华大学3.哈尔滨工业大学

4.厦门大学人工智能研究所

5.中国AI创业研发俱乐部……10经典的人工智能成果人机对弈*1996年2月10-17日,GarryKasparov以4:2战胜“深蓝”(DeepBlue)*1997年5月3-11日,GarryKasparov以3.5:2.5输于改进后的“深蓝”*2003年2月GarryKasparov3:3战平“小深”(DeepJunior)

*2003年11月GarryKasparov2:2战平“X3D德国人”(X3D-Fritz)模式识别

指纹识别、人脸识别、语音识别、文字识别、图像识别、车牌识别等11经典的人工智能成果(续)电影中文名：人工智能片名：AI

年代：2001国家：美国相关著作

《视读人工智能》、《人工智能的未来》、《人工智能哲学》、《人工智能：一种现代的方法》……1212人工神经网络(ArtificicalNeuralNetwork,ANN)模拟退火(SimulatedAnnealing,SA)遗传算法(GeneticAlgorithm,GA)进化算法(EvolutionaryAlgorithm,EA)*粒子群优化算法(ParticalSwamOptimizationAlgorithm,PSOA)*蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA)人工智能优化算法1313人工神经网络(ArtificicalNeuralNetwork,ANN)模拟退火(SimulatedAnnealing,SA)遗传算法(GeneticAlgorithm,GA)进化算法(EvolutionaryAlgorithm,EA)*粒子群优化算法(ParticalSwamOptimizationAlgorithm,PSOA)*蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA)人工智能优化算法14人工神经网络(ArtificicalNeuralNetworks,ANNs)1943年，心理学家W.S.McCulloch和数理逻辑学家W.Pitts建立了神经网络和数学模型，称为MP模型。人工神经网络（ArtificialNeuralNetworks，简写为ANNs）也简称为神经网络（NNs）或称作连接模型（ConnectionistModel），它是一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。人工神经网络是集脑科学、神经心理学和信息科学等多学科的交叉研究领域，是近年来高科技领域的一个研究热点。15人工神经网络基本组成人工神经网络中处理单元的类型分为三类：输入单元、隐单元和输出单元。16人工神经网络中，神经元处理单元可表示不同的对象，例如特征、字母、概念，或者一些有意义的抽象模式。输入单元接受外部世界的信号与数据；输出单元实现系统处理结果的输出；隐单元是处在输入和输出单元之间，不能由系统外部观察的单元。神经元间的连接权值反映了单元间的连接强度，信息的表示和处理体现在网络处理单元的连接关系中。人工神经网络是一种非程序化、适应性、大脑风格的信息处理，其本质是通过网络的变换和动力学行为得到一种并行分布式的信息处理功能，并在不同程度和层次上模仿人脑神经系统的信息处理功能。涉及神经科学、思维科学、人工智能、计算机科学等多个领域的交叉学科。17人工神经网络基本流程

算法过程*从随机的权值开始*反复应用这个神经网络算法到每个训练样例，只要它误分类样例，就根据输入得到的误差来修改神经网络的权值*重复这个过程，直到正确分类所有的训练样例18右图表示了几种常见的激励函数。

1.阈值型函数（见图（a），（b））

2.饱和型函数（见图（c））

3.双曲函数（见图（d））

4.S型函数（见（e））

5.高斯函数（见图（f））几种常见的激励函数19人工神经网络的基本特征1.非线性*非线性关系是自然界的普遍特性。*大脑的智慧就是一种非线性现象。*人工神经元处于激活或抑制二种不同的状态，这种行为在数学上表现为一种非线性关系。*具有阈值的神经元构成的网络具有更好的性能，可以提高容错性和存储容量。20人工神经网络的基本特征（续）2.非局限性*一个神经网络通常由多个神经元广泛连接而成。*一个系统的整体行为不仅取决于单个神经元的特征，而且可能主要由单元之间的相互作用、相互连接所决定。*通过单元之间的大量连接模拟大脑的非局限性。*联想记忆是非局限性的典型例子。21人工神经网络基本特征（续）3.非常定性

*人工神经网络具有自适应、自组织、自学习能力。*神经网络不但处理的信息可以有各种变化，而且在处理信息的同时，非线性动力系统本身也在不断变化。*经常采用迭代过程描写动力系统的演化过程。224.非凸性

*一个系统的演化方向，在一定条件下将取决于某个特定的状态函数，例如能量函数，它的极值相应于系统比较稳定的状态。*非凸性是指这种函数有多个极值，故系统具有多个较稳定的平衡态，这将导致系统演化的多样性。人工神经网络基本特征（续）23人工神经网络ANN是一种模仿动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。ANN人工神经网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到信息处理的目的；ANN具有自学习、自组织、自适应和实时学习等能力，可以通过预先提供的一批相互对应的输入——输出数据，分析掌握两者之间潜在的规律，最终根据这些规律，用新的输入数据来推算输出结果，这种学习分析的过程被称为“训练”。241943年，心理学家W.S.McCulloch和数理逻辑学家W.Pitts建立了神经网络和数学模型，称为MP模型，开创了人工神经网络研究的时代。人工神经网络的研究受到了各个发达国家的重视*美国国会通过决议将1990年1月5日开始的十年定为“脑的十年”*国际研究组织号召它的成员国将“脑的十年”变为全球行为*在日本的“真实世界计算（RWC）”项目中，人工智能的研究成了一个重要的组成部分。*……人工神经网络的发展25人工神经网络的优越性1.具有自学习功能。例如实现图像识别时，只在先把许多不同的图像样板和对应的应识别的结果输入人工神经网络，网络就会通过自学习功能，慢慢学会识别类似的图像。自学习功能对于预测有特别重要的意义。预期未来的人工神经网络计算机将为人类提供经济预测、市场预测、效益预测等。2.具有联想存储功能。用人工神经网络的反馈网络可以实现这种联想。3.具有高速寻找优化解的能力。寻找一个复杂问题的优化解，往往需要很大的计算量，利用一个针对某问题而设计的反馈型人工神经网络，发挥计算机的高速运算能力，可能很快找到优化解。26神经网络的主要应用领域自动控制领域：主要有系统建模和辨识，参数整定，极点配置，内模控制，优化设计，预测控制，最优控制，滤波与预测容错控制等。处理组合优化问题：成功解决了旅行商问题、最大匹配问题、装箱问题和作业调度问题等。模式识别：手写字符，汽车牌照，指纹和声音识别，还可用于目标的自动识别，目标跟踪，机器人传感器图像识别及地震信号的鉴别。图像处理：对图像进行边缘监测，图像分割，图像压缩和图像恢复。机器人控制：对机器人轨道控制，操作机器人眼手系统，用于机械手的故障诊断及排除，智能自适应移动机器人的导航，视觉系统。医疗：在乳房癌细胞分析，移植次数优化，医院费用节流，医院质量改进等方面均有应用。27

BP(Backpropagation)神经网络是一种误差反向传播网络,是目前气象预报研究中应用较为普遍的一种，由于气象要素之间也存在着很大的非线性，天气预报业务中已有人开始进行人工神经网络预报方法的研究。随着我国T213数值预报产品质量的提高，数值预报产品的释用成了提高天气预报精度的主要途径之一。数值预报产品与预报对象的同时性，使因果关系更明确。下面利用我国T213数值预报产品做输入因子，尝试应用（BP）人工神经网络的方法，做保定市短期24小时的降水分级预报。人工神经网络在短期降水预报中的应用28BP网络流程图在使用BP算法时，应注意的几个问题是：1.学习开始时，各隐含层连接权系数的初值应以设置较小的随机数较为适宜。2.采用S型激发函数时，由于输出层各神经元的输出只能趋于1或0，不能达到1或0。在设置各训练样本时，期望的输出分量dpk不能设置为1或0，以设置为或0，1较为适宜。3.学习速率η的选择，在学习开始阶段，η选较大的值可以加快学习速度。学习接近优化区时，η值必须相当小，否则权系数将产生振荡而不收敛。平滑因子α的选值在左右。29因子的具体选取与处理由于人工神经网络的输入和输出之间反映的是一种非线性关系，用传统的求线性相关系数的方法选因子，显然是不太合适。首先建立保定市的降水模型，从保定市的降水模型入手，要求天气学意义清楚，物理意义明确30保定市的降水模型通过对降水过程的总结，建立保定降水的简单预报模型：1、东高西低：高空天气形势应该具备东部是高压或高压脊，西部有低压或低压槽，保定位于南或西南气流里，简称‘东高西低；2、垂直运动条件：降水时一定存在低层要有水平辐合，高层水平辐散，有上升运动；3、水汽条件：具备充足的水汽和水汽输送；4、能量条件：处于一定强度的锋区内和一定的层结条件；这些条件定性分析比较简单，和降水没有确定的定量关系，预报员凭预报经验作预报，很难客观化。人工神经网络应用是使这一经验预报方法客观化的好方法。31因子的具体选取依据降水的主要条件，从我国T213数值预报产品中选取反映保定降水条件的物理量。共从36小时预报中选出10个网格点要素，分别是：湿度条件：850HPA的相对湿度、水汽通量；垂直速度条件：850的散度、200的散度、700的垂直速度、降水量、700的涡度；（以上为116E、39N网点的值）东高西低条件：110E、120E、39N两点850的高度差；锋区和能量条件：116E、35N、45N两点850的温度差、TS。32BP神经网络的建立采用三层BP人工神经网络模式，输入层为10个神经元，对应10个预报因子。输出层为3个神经元，对应降水的大中小三个降水量级。中间层一般取输入层和输出层数的平均，这里取7个神经元。如图1所示，X为输入层，H为隐含层，Y为预报输出层。网络训练1.预报因子0~1化：Xi=(Xmax-Xi)/(Xmax-Xmin)2.在训练以前我们取0~1之间的随机数为连接权重系数Uil、Wlt和阀值Rl、Sj赋初值。由于训练开始时误差常常较大，它们将在以后的训练学习过程中自动逐步调节3.02年，我台从3月到11月接收T213数值预报产品齐全的共有159天，用前109天的资料作为网络训练样本33训练结果经过两万多次的训练，总体预报误差达到了4.0以下。终止训练后。这109天中共有降水日27天，其中小雨20天，中雨6天，大雨以上降水一次。训练结束时27天降水全部报出，量级也全部正确，只是空报两次小雨过程，历史拟合率达到27/29=93%。试报结果在试报的50天中共有降水8次，其中大雨2次，漏一次，一次报中雨。中雨3次，报对2次，漏一次。3次小雨，一次报中雨，漏2次。另空报2次小雨，定性准确率4/10=40%。34分析与讨论1.拟合率虽然很高，但试报准确率不太理想。这可能与样本少，降水模型过于简单，且不分季节有关。如果增加历史样本，分季节、分类型建立降水模型。根据不同模型的特点，分别找不同的预报因子，有可能提高实际的预报准确率.2.BP神经网络的输入与输出不象回归方程的输入与输出是线性关系，而是非线性的。因此，因子的选好比较困难，没有较好的数学方法，所以采用建降水模式的方法，找物理意义较明确的因子。但不同的预报员可能选择的不同因子.3535人工智能优化算法人工神经网络(ArtificicalNeuralNetwork,ANN)模拟退火(SimulatedAnnealing,SA)遗传算法(GeneticAlgorithm,GA)进化算法(EvolutionaryAlgorithm,EA)*粒子群优化算法(ParticalSwamOptimizationAlgorithm,PSOA)*蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA)36模拟退火(SimulatedAnnealing,SA)模拟退火是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。源于固体退火原理。将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一部先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。37模拟退火(续)根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。38模拟退火算法的基本思想1.初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L2.对k=1，……，L做第(3)至第6步：3.产生新解S′4.计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数5.若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.6.如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。7.T逐渐减少，且T->0，然后转第2步。39模拟退火算法特点模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。4040人工智能优化算法人工神经网络(ArtificicalNeuralNetwork,ANN)模拟退火(SimulatedAnnealing,SA)遗传算法(GeneticAlgorithm,GA)进化算法(EvolutionaryAlgorithm,EA)*粒子群优化算法(ParticalSwamOptimizationAlgorithm,PSOA)*蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA)41遗传算法是一类模拟达尔文生物进化论的自然选择和遗传算法机理的生物进化过程的计算模型，借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索最优化方法。遗传算法最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》,遗传算法这个名称才逐渐为人所知，通常称为“简单遗传算法”。遗传算法(GeneticAlgorithm,GA)42直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法的主要特点43遗传算法的定义遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。44遗传算法的定义（续）由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。45遗传算法流程图由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。46遗传算法的一般算法遗传算法是由进化论和遗传学机理而产生的搜索算法。

1.创建一个随机的初始状态：初始群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。

2.评估适应度：对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。47遗传算法的一般算法(续)3.繁殖(包括子代突变)带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。

4.下一代如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。48遗传算法的一般算法(续)5.并行计算*非常容易将遗传算法用到并行计算和群集环境中。*一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。*另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。4949人工智能优化算法人工神经网络(ArtificicalNeuralNetwork,ANN)模拟退火(SimulatedAnnealing,SA)遗传算法(GeneticAlgorithm,GA)进化算法(EvolutionaryAlgorithm,EA)*粒子群优化算法(ParticalSwamOptimizationAlgorithm,PSOA)*蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA)50进化算法(EvolutionaryAlgorithms,EA)进化算法包括遗传算法、进化程序设计、进化规划和进化策略等等，进化算法的基本框架还是简单遗传算法所描述的框架，但在进化的方式上有较大的差异，选择、交叉、变异、种群控制等有很多变化。遗传算法对交叉操作要看重一些，认为变异操作是算法的辅助操作；而进化规划和进化策略认为在一般意义上说交叉并不优于变异，甚至可以不要交叉操作。51现在我们讨论另一种生物系统——社会系统.更确切的是,在由简单个体组成的群落与环境以及个体之间的互动行为.也可称做“群智能”(swarmintelligence).这些模拟系统利用局部信息从而可能产生不可预测的群体行为。例如floys和boids,他们都用来模拟鱼群和鸟群的运动规律,主要用于计算机视觉和计算机辅助设计.在计算智能(computationalintelligence)领域有两种基于群智能的算法.蚁群算法(antcolonyoptimization)和粒子群算法(particleswarmoptimization).背景：人工生命（续）52鸟群运动53鱼群运动鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可带动整个鱼群逃避。54一只蚂蚁或鱼的行为能力非常有限，它几乎不可能独立存在于自然世界中，而多个蚂蚁或鱼形成的Swarm则具有非常强的生存能力，且这种能力不是通过多个个体之间能力简单叠加所获得的。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息（包括环境信息和附近其它个体的信息）改变自身的一些行为模式和规范，这样就使得群体涌现出一些单个个体所不具备的能力和特性，尤其是对环境的适应能力。这种对环境变化所具有适应的能力可以被认为是一种智能5555人工智能优化算法人工神经网络(ArtificicalNeuralNetwork,ANN)模拟退火(SimulatedAnnealing,SA)遗传算法(GeneticAlgorithm,GA)进化算法(EvolutionaryAlgorithm,EA)*粒子群优化算法(ParticalSwamOptimizationAlgorithm,PSOA)*蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA)56问题的引入设想这样一个场景：*一群鸟在随机搜索食物*在这个区域里只有一块食物*所有的鸟都不知道食物在那里，但是他们知道当前的位置离食物还有多远问题：找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。粒子群优化算法就是从这种模型中得到启示并用于解决优化问题。57粒子群算法(ParticleSwamOptimize,PSO)PSO是一种进化计算技术(EvolutionaryComputation,EC)，由R.C.Eberhart博士和J.Kennedy博士于1995年开发的一种演化计算技术，源于对鸟群捕食的行为研究。JamesKennedyRussellC.Eberhart58粒子群算法(ParticleSwamOptimize,PSO)群(Swarm)来源于微粒群符合M.M.Millonas在开发应用于人工生命(artificiallife)的模型时所提出的群体智能的5个基本原则。每个优化问题的解都是搜索空间中的一只鸟。我们称之为粒子(Particle)。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。59基本PSO算法粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个CAS。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：1.避免与相邻的鸟发生碰撞冲突；2.尽量与自己周围的鸟在速度上保持协调和一致；3.尽量试图向自己所认为的群体中靠近。仅通过使用这三条规则，boids系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。60PSO初始化为一群随机粒子(随机解)然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。*第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest.*另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。*另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。粒子群优化算法61在寻找这两个最优值时,粒子根据如下公式更新自己的速度和新的位置：v[]=v[]+c1*rand()*(pbest[]-present[])+c2*rand()*(gbest[]-present[])(a)

present[]=persent[]+v[](b)

其中v[]是粒子的速度,persent[]是当前粒子的位置.pbest[]和gbest[]是个体极值和全局极值，rand()是介于（0，1）之间的随机数.c1,c2是学习因子.通常c1=c2=2.在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax.62粒子群算法的流程初始化一群微粒（群体规模为m），包括随机的位置和速度；评价每个微粒的适应度；对每个微粒，将它的适应值和它经历过的最好位置pbest的作比较，如果较好，则将其作为当前的最好位置pbest；对每个微粒，将它的适应值和全局所经历最好位置gbest的作比较，如果较好，则重新设置gbest的索引号；根据方程(1)变化微粒的速度和位置；如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数Gmax），回到2。63粒子群算法的参数PSO参数包括：群体规模m，惯性权重w，加速常数c1和c2，最大速度Vmax，最大代数Gmax。Vmax决定在当前位置与最好位置之间的区域的分辨率（或精度）。如果Vmax太高，微粒可能会飞过好解，如果Vmax太小，微粒不能进行足够的探索，导致陷入局部优值。该限制有三个目的：防止计算溢出；实现人工学习和态度转变；决定问题空间搜索的粒度。惯性权重w使微粒保持运动的惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。加速常数c1和c2代表将每个微粒推向pbest和gbest位置的统计加速项的权重。低的值允许微粒在被拉回来之前可以在目标区域外徘徊，而高的值导致微粒突然的冲向或者越过目标区域。64粒子群算法的参数（续）如果没有后两部分，即c1=c2=0，微粒将一直以当前的速度飞行，直到到达边界。由于它只能搜索有限的区域，将很难找到好的解。如果没有第一部分，即w=0，则速度只取决于微粒当前的位置和它们历史最好位置pbest和gbest，速度本身没有记忆性。假设一个微粒位于全局最好位置，它将保持静止。而其它微粒则飞向它本身最好位置pbest和全局最好位置gbest的加权中心。在这种条件下，微粒群将统计的收缩到当前的全局最好位置，更象一个局部算法。在加上第一部分后，微粒有扩展搜索空间的趋势，即第一部分有全局搜索的能力。这也使得w的作用为针对不同的搜索问题，调整算法全局和局部搜索能力的平衡。65粒子群算法的参数（续）如果没有第二部分，即c1=0，则微粒没有认知能力，也就是“只有社会(social-only)”的模型。在微粒的相互作用下，有能力到达新的搜索空间。它的收敛速度比标准版本更快，但是对复杂问题，比标准版本更容易陷入局部优值点。如果没有第三部分，即c2=0，则微粒之间没有社会信息共享，也就是“只有认知(cognition-only)”的模型。因为个体间没有交互，一个规模为m的群体等价于m个单个微粒的运行。因而得到解的几率非常小。6666人工智能优化算法人工神经网络(ArtificicalNeuralNetwork,ANN)模拟退火(SimulatedAnnealing,SA)遗传算法(GeneticAlgorithm,GA)进化算法(EvolutionaryAlgorithm,EA)*粒子群优化算法(ParticalSwamOptimizationAlgorithm,PSOA)*蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA)67蚁群觅食食物食物食物巢穴巢穴巢穴68问题引入为什么小小的蚂蚁能够找到食物？它们具有智能么？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？*首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物；*其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；*再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小。69预期的结果各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。70蚁群优化算法的分析然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，它们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？71简单行为规则1.范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。2.环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。723.觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。4.移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。简单行为规则（续）735.避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。6.播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。简单行为规则（续）74问题：蚂蚁究竟是怎么找到食物的呢？在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动，而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。75问题：蚂蚁如何找到最短路径？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。76蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Colorni，Dorigo和Maniezzo在1991年提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA)Dorigo77自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”（pheromone）作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁群优化算法(AntColonyOptimizationAlgorithm,ACOA)78蚁群算法的引申跟着蚂蚁的踪迹，你找到了什么？通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点：多样性和正反馈多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。79蚁群算法的参数说明最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。错误概率表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。速度半径表示蚂蚁一次能走的最大长度，也表示该蚂蚁的感知范围记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。80蚁群算法应用现状蚁群算法在电信路由优化中已取得了一定的应用成果。HP公司和英国电信公司设计了蚁群路由算法(AntColonyRouting，ACR)还在许多经典组合优化问题中获得了成功的应用，如二次规划问题(QAP)、机器人路径规划、作业流程规划、图着色(GraphColoring)、武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、Bayesiannetworks的训练和集合覆盖等应用优化问题。81混流装配线(SMMAL)调度问题混流装配线(sequencingmixedmodelsonanassemblyline,SMMAL)是指一定时间内，在一条生产线上生产出多种不同型号的产品，产品的品种可以随顾客需求的变化而变化。SMMAL是车间作业调度问题(job-shopschedulingproblem,JSP)的具体应用之一。82问题描述以汽车组装为例，即在组装所有车辆的过程中，所确定的组装顺序应使各零部件的使用速率均匀化。如果不同型号的汽车消耗零部件的种类大致相同，那么原问题可简化为单级SMMAL调度问题。83问题描述i表示车型数的标号n表示需要装配的车型数m表示装配线上需要的零部件种类总数p表示生产调度中子装配的标号表示零部件p的理想使用速率j表示车型调度结果(即排序位置)的标号D表示在一个生产循环中需要组装的各种车型的总和84问题描述di表示在一个生产循环中车型i的数量bip表示生产每辆i车型需要零部件p的数量表示在组装线调度中前j-1台车消耗零部件p的数量和85蚁群算法在SMMAL中的应用假设有3种车型A、B、C排序，每个生产循环需A型车3辆，B型车2辆，C型车1辆，则每个循环共需生产6辆车。采用下图的搜索空间定义，列表示6个排序阶段，行表示有3种车型可以选择。蚁群算法就是不断改变圆圈的大小，最终寻找到满意的可行解。搜索的初始状态86简单SMMAL排序的搜索空间举例经过若干次迭代之后，搜索空间变化，此时最可能的可行解为B-A-C-A-B-A若干次迭代后的状态87局部搜索()的计算局部搜索采用的是贪婪策略基本思路：每一步均从当前可选择策略中选取，使目标函数值增加最少的策略，即在确定第j个位置组装的车型时，如果有多种车型可供选择，则从中选择一种车型i，使第j个位置组装车型i时各零部件的使用速率最为均匀。88状态转移概率状态转移概率公式如下89信息素更新规则LB表示目标函数的下限值表示当前目标函数的平均值Zcutr表示当前的目标函数值这种动态标记的方法可在搜索过程中加大可行解间信息素的差别，避免算法早熟90实验数据91实验参数设置蚂蚁系统蚂蚁数量N_ant=5最大循环周期Ncmax=400=0.2Q=20000=0.9LB=0.0蚁群系统q0=0.5全局更新规则中的

和局部更新规则中的均取0.192实验参数设置最大-最小蚂蚁系统选取全局最优解带有精英策略的蚂蚁系统精英蚂蚁数量:1只93实验结果94实验界面95实验界面96蚁群系统在TSP问题中的应用10城市TSP问题20城市TSP问题97蚁群系统在TSP问题中的应用30城市TSP问题48城市TSP问题98内容结构：研究内容界定研究背景配送模式研究优化调度研究模拟实验致谢基于蚁群算法的教育资源优化配送99研究对象：教育信息资源研究环境：网络环境下研究问题：资源配送研究重点：配送中调度优化处理研究目的：形成资源及时有效的共享研究内容界定100研究背景东北师大理想信息技术研究院信息化教育平台国家级火炬计划项目、国家电子基金项目等项目支持被教育部中央电化教育馆评定为国内同类产品中唯一的“教育认证精品”软件所研制的教育资源涵盖小学、初中、高中各主干学科与全国20多个省市近300个地（市、州）、县（市、区）的教育主管部门以及3800多所中小学校建立了合作关系，在全国建立了18个研究与应用实验基地；对32000多中小学教师进行过信息技术培训。101研究背景（续）有信息技术与课程整合、教育资源、多媒体制作、软件研发等研究机构和220多专业人员。1、中心资源库的资源不断累积2、用户群的逐渐增