几种智能算法的原理及应用介绍.ppt

几种智能算法的原理 及应用介绍,学 院：数学与统计学院 指导教师：阮小娥 汇 报 人：王 彭,讨论班报告,主要内容：,1. 遗传算法 2. 蚁群算法 3. 模拟退火算法 4. 粒子群算法 5. 总结与体会,1. 遗传算法,1.1 遗传算法简介 1.2 遗传算法的基本思想 1.3 遗传算法的基本操作 1.4 遗传算法的构成要素 1.5 遗传算法的操作步骤 1.6 遗传算法的特点 1.7 遗传算法的应用领域 1.8 遗传算法的应用举例,1.1 遗传算法简介,遗传算法简称GA（Genetic Algorithms）是1962年由美国Michigan大学的Holland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。 遗传算法是以达尔文的自然选择学说为基础发展起来的。,自然选择学说包括以下三个方面： （1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。 （2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。 （3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。,1.2 遗传算法的基本思想,遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。,1.3 遗传算法的基本操作,遗传算法的基本操作主要有：复制、交叉、变异。,（1）复制（Reproduction Operator） 复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。 复制操作可以通过随机方法来实现。首先产生01之间均匀分布的随机数，若某串的复制概率为40%，则当产生的随机数在0.401.0之间时，该串被复制，否则被淘汰。,1.3 遗传算法的基本操作,（2）交叉（Crossover Operator） 复制操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。 交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。 交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法，应用较广。它是指染色体切断点有一处，例：,1.3 遗传算法的基本操作,（3）变异(Mutation Operator) 变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变为0，或由0变为1。 若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。变异操作如下所示：,1.4 遗传算法的构成要素,遗传算法的构成要素主要有：染色体编码方法、个体适应度评价、遗传算子及遗传算法的运行参数。,（1）染色体编码方法 基本遗传算法使用固定长度的二进制符号来表示群体中的个体，其等位基因是由二值符号集0,1所组成。初始个体基因值可用均匀分布的随机值生成，如：,就可表示一个个体，该个体的染色体长度是18。,1.4 遗传算法的构成要素,（2）个体适应度评价 基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的概率多少。为正确计算这个概率，要求所有个体的适应度必须为正数或零。因此，必须先确定由目标函数值J到个体适应度f之间的转换规则。,（3）遗传算子 基本遗传算法使用下述三种遗传算子： 选择运算:使用比例选择算子； 交叉运算:使用单点交叉算子； 变异运算:使用基本位变异算子或均匀变异算子。,1.4 遗传算法的构成要素,（4）基本遗传算法的运行参数 有下述4个运行参数需要提前设定： M ：群体大小，即群体中所含个体的数量，一般取为20-100； G ：遗传算法的终止进化代数，一般取为100-500； Pc：交叉概率，一般取为0.4-0.99； Pm：变异概率，一般取为0.0001-0.1。,1.5 遗传算法的操作步骤,对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：,第一步：确定决策变量及各种约束条件； 第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法； 第三步：确定表示可行解的染色体编码方法； 第四步：确定解码方法； 第四步：确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则； 第五步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法。 第六步：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数。,1.5 遗传算法的操作步骤,遗传算法流程图：,1.6 遗传算法的特点,遗传算法的主要特点有：,（1）遗传算法是对参数的编码进行操作，而非对参数本身，这就是使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等机理； （2）遗传算法同时使用多个搜索点的搜索信息。传统的优化方法往往是从解空间的单个初始点开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前。 遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。 （3）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。,1.6 遗传算法的特点,遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题等。 （4）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。 （5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索； （6）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广； （7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。,1.7 遗传算法的应用领域,遗传算法的应用领域主要有：函数优化、组合优化、生产调度问题、自动控制、机器人、图像处理等。,（1）函数优化 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。,（2）组合优化。 随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。,1.7 遗传算法的应用领域,（3）生产调度问题 在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。,（4）自动控制 在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得到了初步的应用。例如，利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。,1.7 遗传算法的应用领域,（5）机器人 例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。,（6）图像处理 遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。,1.8 遗传算法的应用举例,1 用遗传算法求函数极值,利用遗传算法求Rosenbrock函数的极大值：,求解该问题遗传算法的构造过程：,（1）确定决策变量和约束条件,决策变量为：,（2）建立优化模型,1.8 遗传算法的应用举例,（3）确定编码方法,用长度为10位的二进制编码串来分别表示两个决策变量x1,x2。10位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1,x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。 从离散点-2.048到离散点2.048 ，分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。 将x1,x2分别表示的两个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一一对应的关系。,例如：,表示一个个体的基因型，其中前10位表示x1，后10位表示x2。,1.8 遗传算法的应用举例,（4）确定解码方法,解码时需要将20位长的二进制编码串切断为两个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。 依据个体编码方法和对定义域的离散化方法可知，将代码y转换为变量x的解码公式为：,例如，对个体：,它由两个代码所组成,上述两个代码经过解码后，可得到两个实际的值,1.8 遗传算法的应用举例,（5）确定个体评价方法,由于Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即,选个体适应度的倒数作为目标函数,选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。,（6）确定个体评价方法,群体大小M=80，终止进化代数G=100，交叉概率Pc=0.60，变异概率Pm=0.10。,（7）确定遗传算法的运行参数,1.8 遗传算法的应用举例,（8）实验过程,完全随机生成初始种群,循环八次，达到暂时的最优值：,3414.8,对应的x1、x2坐标为：,(-1.9799,-1.9159),种群向暂时的最优染色体靠近。,1.8 遗传算法的应用举例,平均分配坐标轴生成初始种群,循环八次，达到最优值：,3905.9,对应的x1、x2坐标为：,(-2.0480,-2.0480),种群向最优染色体靠近。,1.8 遗传算法的应用举例,上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。 采用上述方法进行仿真，经过100步迭代，最佳样本为,即当,时，Rosenbrock函数具有极大值，极大值为3905.9。,1.8 遗传算法的应用举例,2 用遗传算法进行图像匹配,（1）问题描述：,从一张图片中找出与另一张图片相似的部分。（为了便于说明问题，本实验中目标图片为匹配图片加黑色背景随机生成，如下图所示：）,1.8 遗传算法的应用举例,2 用遗传算法进行图像匹配,（2）编码,对匹配图片左上角第一个像素在目标图片内的位置进行编码（要求匹配图片不能超出目标图片的边界），采用二进制编码。,（3）计算适应度,适应度函数取为两幅图片对应位置上的值差的平方和的倒数。,（4）选择,按适应度函数的大小计算种群中某个体被选中的概率，按概率选择下一代种群。,1.8 遗传算法的应用举例,2 用遗传算法进行图像匹配,（5）交叉,单点交叉、多点交叉（要求匹配图片不能超出目标图片的边界）。,（6）变异,要求匹配图片不能超出目标图片的边界。,1.8 遗传算法的应用举例,（7）实验结果与分析,对于此类简单的图片匹配的问题，遗传算法通常能较快的收敛到一个较好的位置，但对于复杂一些的图片匹配问题，容易收敛到局部极值点。,2. 蚁群算法,2.1 蚂蚁生物学特征 2.2 Deneubourg双桥实验 2.3 蚁群算法的定义 2.4 蚁群算法的原理 2.5 蚁群算法的规则 2.6 蚁群算法的特点 2.7 蚁群算法的应用领域 2.8 蚁群算法的应用举例,2.1 蚂蚁的生理学特征,蚂蚁在8000万年前就建立起了自己的社会。许多“蚂蚁城市”往往由5000万个成员组成，并且是一个组织完好的复杂“城市”。,蚂蚁的群体行为主要包括寻找食物、任务分配和构造墓穴。,研究中主要是以蚂蚁寻找食物之后能选择一条最短路径来连接蚁穴和食物源。,蚂蚁具有智能么？,生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，看起来没有集中的指挥，但他们却能协同的工作，集中食物建立起稳固的蚁穴，依靠群体的能力发挥出了超出个体的智能。,2.2 Deneubourg双桥实验,Pasteels，Deneubourg和Goss（1987）全部都在实验中研究真实蚂蚁信息素的遗留行为，他们称之为“双桥实验”。在这个双桥实验模型中，蚁穴通过一个蚁穴和食物源之间用两个长度相等的桥连接。作者使用能够辨认路径的阿根廷蚂蚁，简而言之这些蚂蚁可以预测或者搜索他们的群类。,2.2 Deneubourg双桥实验,等长双桥实验,在前面的设定下，蚂蚁开始探索蚁穴周围的环境最终到达食物源。沿着他们的在蚁穴和食物源之间的路径，阿根廷释放信息素，开始每个蚂蚁都随机选择两条桥之间的的一个，在随后的阶段里因为随机的波动，其中一个桥的信息素表现出比另外一条的信息素更为集中，因此吸引了更多的蚂蚁。这个行为增加了这个桥上的信息素，也就吸引了更多的蚂蚁。因此，过了一段时间以后，整个种群都聚合于使用这个高度集中的桥运送。,2.2 Deneubourg双桥实验,Goss，Aron，Deneubourg和Pasteel（1989）提出上述双桥实验的变种，在其中一个桥要比另一个桥更长，如下图所示；在这种情况下，蚂蚁选择了近的路径首先到达了蚁穴。因此，短桥比长桥得到了更为密集的信息素增长了蚂蚁选择短桥的的可能性。Goss，Aron，Deneubourg和Pasteel（1990）将观察的的真实的蚂蚁建立到假设的模型中。首先，假设桥上残留的信息素量和过去一段时间经过该桥的蚂蚁数成正比(信息素挥发的情况);其次某一时刻蚂蚁按照桥上信息素量的多少来选择某支桥，即蚂蚁选择某支桥的概率与经过该桥的蚂蚁数成正比。当所有的m只蚂蚁都经过两支桥以后，设Am和Bm分别为经过A桥和B桥的蚂蚁数(Am+Bm=m)，则第m+1只蚂蚁选择A(B)桥的概率为:,2.2 Deneubourg双桥实验,公式表明：往A走的蚂蚁越多，选择分支A的概率就越高。 n和k用以匹配真实实验数据。 “n”决定选择公式的非线性程度。（n越大，信息素多一点的分支选择概率越高） “k”表示对未标记的分支的吸引程度。（k越大，则进行非随机化选择所需的信息素浓度越高） 这种概率的表达方式是实际的蚂蚁路径选择实验推导而来的，比较符合实验的参数设置是n=2和k=20.,2.3 蚁群算法的定义,蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。,这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种新型的启发式优化算法。,人工蚁群与真实蚂蚁的异同比较：,相同点： （1）都存在一个群体中个体相互交流通信的机制 （2）都要完成一个相同的任务 （3）利用当前信息进行路径选择的随机选择策略 不同点： （1）人工蚂蚁他们的移动是从一个状态到另一个 状态的转换 （2）人工蚂蚁具有一个记忆其本身过去行为的内在状态 （3）人工蚂蚁存在于一个与时间无关联的环境之中 （4）人工蚁不是盲从的，受环境空间的启发 （5）人工蚁可以根据要求增加功能,2.4 蚁群算法的原理,蚂蚁在运动过程中会通过在路上释放一种特殊的分泌物信息素来寻找路径。当它碰到一个还没有走过的路口是就随机的选择一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口时，选择信息量较大的路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上得信息量越来越大，而其他路径上的信息量却随时间逐渐减少最终整个蚁群会找出最优路径。,（1）蚁群之间通过信息素和环境进行通信。 （2）蚂蚁对环境的反应由其内部模式决定。 （3）个体水平上，每个蚂蚁相对独立；群体水平上，每只蚂蚁的行为是随机的。,蚁群算法的理论假设,2.5 蚁群算法的规则,蚁群算法中的蚂蚁满足的规则主要有以下几个方面：,蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。,（1）范围,蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内环境信息。环境以一定的速率让信息素消失 。,（2）环境,2.5 蚁群算法的规则,在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。,（3）觅食规则,每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。,（4）移动规则,2.5 蚁群算法的规则,如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。,（5）避障规则,每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。,（6）撒播信息素规则,根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。,2.6 蚁群算法的特点,在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织。如果系统在获得空间的、时间的或者功能结构的过程中，没有外界的特定干预，我们便说系统是自组织的。在抽象意义上讲，自组织就是在没有外界作用下使得系统墒增加的过程(即是系统从无序到有序的变化过程)。蚁群算法充分休现了这个过程，以蚂蚁群体优化为例子说明。当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作用，自发的越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过程。,（1）蚁群算法是一种自组织的算法。,2.6 蚁群算法的特点,每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。,（2）蚁群算法是一种本质上并行的算法。,2.6 蚁群算法的特点,从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统一个微小扰动，使得各个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。因此，正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进行。,（3）蚁群算法是一种正反馈的算法。,2.6 蚁群算法的特点,相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。,（4）蚁群算法具有较强的鲁棒性。,2.7 蚁群算法的应用领域,蚁群算法主要应用于：组合优化问题、车间作业调度问题、网络路由问题、车辆路径问题、机器人领域、电力系统、故障诊断、控制参数优化、岩土工程、生命科学等若干领域。,2.8 蚁群算法的应用举例,蚁群算法解决TSP问题,旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。,2.8.1 问题描述,2.8 蚁群算法的应用举例,（1）蚂蚁主体具有的特征：,2.8.2 用蚁群算法解决TSP问题,在从城市i到j的过程中或者一次循环结束，在边（i，j）释放信息素。 有概率的访问下一个城市，这个概率是两城市间和连接两城市的路径上存有轨迹量的函数。 不允许蚂蚁访问已经访问过的城市,2.8 蚁群算法的应用举例,（2）引入相关记号,为了模拟实际蚁群的行为首先引入以下记号：,2.8 蚁群算法的应用举例,（3）蚂蚁从一个城市移动到另一个城市的概率,在初始时刻，各条路径上的信息素量相等，设,。,蚂蚁k（k=1，2，m）在运动中根据各条路径上的信息素量决定转移方向。,位于城市i的蚂蚁k选择移动到城市j的概率,为：,公式 1,2.8 蚁群算法的应用举例,（4）禁忌表,与真实蚁不同，人工蚁群系统具有记忆功能。为了满足蚂蚁必须经过所有n个不同的城市这个约束条件，为每只蚂蚁都设计了一个数据结构，成为禁忌表。用来记录了t时刻蚂蚁已经经过的城市，不允许该蚂蚁在本次循环中再经过这些城市。当本次循环结束后禁忌表被用来计算该蚂蚁所建立的解决方案。之后禁忌表清空蚂蚁又可以自由地选择。,2.8 蚁群算法的应用举例,（5）信息素的调整,经过n个时刻，蚂蚁完成一次循环，各路径上的信息素根据如下公式调整：,其中：,表示第k只蚂蚁在时刻(t,t+1)留在路径(i,j)上的信息素。,表示本次循环路径(i,j)上的信息素增量。,公式 3,2.8 蚁群算法的应用举例,（6）实现过程,2.8 蚁群算法的应用举例,2.8 蚁群算法的应用举例,2.8 蚁群算法的应用举例,（5）仿真结果,采用MATLAB来仿真实现蚁群算法解TSP问题 。对全国31个省会城市的一个TSP计算。通过程序仿真得到。实验结果非常好！,2.8.3 用遗传算法解决TSP问题,（1）用遗传算法解TSP问题主要集中在以下几个方面：,2.8.3 用遗传算法解决TSP问题,采用适当的表示方法表示个体的编码； 设计可用的遗传算子，以保持父代的特性避免新个体的不可行性； 防止算法过早的收敛。,（2）编码,路径表示是TSP问题最自然、最直接的表示方式。它直接采用城市在路径中的相对位置来进行表示。 例如，路径517862934直接表示成（5 1 7 8 6 2 9 3 4）。,2.8.3 用遗传算法解决TSP问题,（3）交叉,部分映射杂交 首先随机地在父体中选取两个杂交点，并交换相应的段，再根据该段内的城市确定部分映射。在每个父体上先填入无冲突的城市，而对有冲突的城市依照映射关系选择候选的城市，直到找到无冲突的城市填入，按此方法获得了杂交后的两个后代。 实例：如两父串及匹配区域为 A9 8 4 | 5 6 7 | 1 3 2 0 B8 7 1 | 2 3 0 | 9 5 4 6 首先交换A和B的两个匹配区域，得到 A9 8 4 | 2 3 0 | l 3 2 0 B8 7 1 | 5 6 7 | 9 5 4 对于A、B两子串中匹配区域以外出现的遍历重复，依据匹配区域内的位置映射关系，逐一进行交换。对于A有2到5，3到6，0到7的位置符号映射，对A的匹配区以外的2，3，0分别以5，6，7替换，则得 A”9 8 4 | 2 3 0 | 1 6 5 7 同理可得： B”8 0 1 | 5 6 7 | 9 2 4 3 这样，每个子串的次序部分地由其父串确定。,2.8.3 用遗传算法解决TSP问题,（3）变异,倒置变异 利用简单的倒置操作来进行变异。即首先在父体中随机地选择两个截断点，然后将该两点内的子串中的城市进行反序操作。 A 1 2 3 | 4 5 6 | 7 8 9 0 A1 2 3 | 6 5 4 | 7 8 9 0 插入变异 插入算子就是随机选择一个城市，并将它插入到一个随机位置中去。 A 1 2 3 4 5 6 7 8 9 A1 2 5 3 4 6 7 8 9 移位变异 移位算子是选择一个子路径巡回，然后把它插入一个随机的位置 互换变异 互换变异也被称作基于次序的变异（order-based mutation），操作方法是：随机的选择两个城市，并交换其所处的位置 对于串A A 1 2 3 4 | 5 6 7 | 8 9 若对换点为4，7，则经对换后，A为 A1 2 3 7 | 5 6 4 | 8 9,2.8.3 用遗传算法解决TSP问题,从群体规模来看，有变化规模的方式，也有恒定规模的群体构成方式等。 在遗传算法中，最常见的选择机制是依据适应度的比例概率选择机制；在有限规模的群体中，适应度较高的个体有较大的机会繁殖后代，即生物进化论上的适者生存规则。 在新一代群体构成方法方面存在： N方式：全部替换上一代群体的全刷新代际更新方式。 E方式：保留一个最好的父串的最佳保留（elitist）群体构造方式。 G方式：按一定比例更新群体中的部分个体的部分更新方式（或称代沟方法，这种情况的极端是每代仅删去一个最不适的个体的最劣死亡方式）。 B方式：从产生的子代和父代中挑选最好的若干个个体的群体构成形式。 一般讲，N方式的全局搜索性能最好，但收敛速度最慢；B方式收敛速度最快，但全局搜索性能最差；E方式和G方式的性能介于N方式和B方式之间。在求解货郎担问题的应用中，多选用E方式。,（4）选择机制和群体构成,2.8.3 用遗传算法解决TSP问题,算法简单，从总体趋势上看，算法总是朝着路径和变小的方向收敛的，得到的结果也较好，不过收敛速度较慢，且存在比较好的染色体（路径）被淘汰的情况。,（5）实验结果与分析,3.模拟退火 算法,3.1 模拟退火算法简介 3.2 模拟退火算法基本原理 3.3 优化问题与物理退火的类比,3.1 模拟退火算法简介,模拟退火的思想,开始使劲晃动(先高温加热)然后慢慢降低摇晃的强度(逐渐降温)退火过程。,想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中如果只让其在表面滚动，则它只会停留在局部极小点/ 如果晃动平面，可以使乒乓球弹出局部极小点/ 技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出。,模拟退火的思路,算法的目的,解决NP复杂性问题； 克服优化过程陷入局部极小； 克服初值依赖性。,3.2 模拟退火算法基本原理,（1）物理退火过程,加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将溶解为液体，溶解过程与系统的熵增过程联系，系统能量也随温度的升高而增大，使得每一粒子的状态都具有充分的随机性。 等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。 冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。在常温时达到基态，内能减为最小。,退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列， 固体达到某种稳定状态。,物理退火过程的发展阶段,3.2 模拟退火算法基本原理,（2）数学表述,物体加热至一定温度后，所有分子在状态空间D中自由运动，随着温度的下降，分子逐渐停留在不同的状态。在温度最低时，分子重新以一定的结构排列。 在温度T, 分子停留在状态r满足Boltzmann概率分布:,其中：,表示分子能量的一个随机变量；,表示状态r的能量；,为Boltzmann常数，,为概率分布的标准化因子：,；,。,3.2 模拟退火算法基本原理,在同一个温度T，选定两个能量E1E2，有,四个能量点r = 1, 2, 3, 4 三个温度点t = 20, 5, 0.5,状态与温度关系的例子,3.2 模拟退火算法基本原理,（1）在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率; （2）温度越高，不同能量状态对应的概率相差越小；温度足够高时， 各状态对应概率基本相同; （3）随着温度的下降，能量最低状态对应概率越来越大；温度趋于0 时，其状态趋于1。,在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率1停留在最优解。,上表表明：,模拟退火算法求解思路：,3.3 优化问题与物理退火的类比,4.粒子群算法,4.1 粒子群算法简介 4.2 粒子群算法的基本原则 4.3 粒子群算法的基本条件 4.4 粒子群算法的数学表述,4.1 粒子群算法简介,粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。 PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。,4.1 粒子群算法简介,优化策略为两个动作的合成： （1）鸟群向距离食物最近的那只鸟的方向飞行 （2）每只鸟向自身的最优方向飞行,已知：（1）鸟的位置（2）距离食物最近的那只鸟,求解：这群鸟在最短时间搜寻到这块食物的飞行策略,模拟群鸟觅食过程,4.2 粒子群算法的基本原则,粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个CAS。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：,（1）避免与相邻的鸟发生碰撞冲突； （2）尽量与自己周围的鸟在速度上保持协调和一致； （3）尽量试图向自己所认为的群体中靠近。,仅通过使用这三条规则，boids系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。,4.3 粒子群算法的基本条件,基本条件,（1）目标搜索空间为D维空间。 （2）粒子群由m个粒子组成。 （3）第i个粒子在D维空间的位置为,（4）第i个粒子的飞翔速度为,（5）第i个粒子的最优位置,（6）全局最优位置,4.2 粒子群算法的数学表述,PSO算法数学表示如下：,设搜索空间为D维，总粒子数为n。第i个粒子位置表示为向量Xi=( xi1, xi2, xiD )；第i个粒子 “飞行”历史中的过去最优位置（即该位置对应解最优）为Pi=( pi1,pi2,piD )，其中第g个粒子的过去最优位置Pg为所有Pi ( i=1, ,n)中的最优；第i个粒子的位置变化率（速度）为向量Vi=(vi1, vi2, viD)。每个粒子的位置按如下公式进行变化（“飞行”）：,4.2 粒子群算法的数学表述,（1） （2）,其中，C1,C2为正常数，称为加速因子；rand( )为0，1之间的随机数；w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。第d（1dD）维的位置变化范围为-XMAXd , XMAXd，速度变化范围为-VMAXd , VMAXd，迭代中若位置和速度超过边界范围则取边界值。,4.2 粒子群算法的数学表述,粒子群初始位置和速度随机产生，然后按公式(1)(2)进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群(Global)分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群(Local)内历史最优Pl调整位置，即公式(2)中Pgd换为Pld。,5 总结与体会,（1）智能算法源于对现实生活中事物的观察与思考。 （2）智能算法普遍原理简单，易于理解，且结果较好。 （3）可以解决很难给出解析表达式的问题。 （4）当把实际问题编码等手段抽象为智能模型的时候，与问题本身的实际意义关系不大，易于推广。 （5）算法的收敛性证明较麻烦。 （6）算法收敛较慢，有时候与初值的选取关系较大，算法的收敛速度及结果好坏有时候有“看脸”的成分。（这正与日常事物的运行规律相符） （7）在以后的学习研究过程中应善于观察、善于思考，灵感来源于生活！,Thats all! Thank you for attending!,