智能算法及应用课件.ppt

1、智能优化算法及应用智能优化算法及应用Intelligent Optimization Algorithms西安工程大学贺兴时西安工程大学贺兴时内容简介内容简介1 1、组合优化问题是组合优化问题是解决离散问题的优化问题运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。典型的优化问题：典型的优化问题：0-10-1背包问题，旅行商问题，背包问题，旅行商问题，机器排序问题等机器排序问题等内容简介内容简介2 2、模拟退火算法模拟退火算法（simulated annealing）退火是一种物理过程，金属物体在加热

2、至一退火是一种物理过程，金属物体在加热至一定的温度后，它的所有分子在状态空间中自定的温度后，它的所有分子在状态空间中自由运动。随着温度的下降，这些分子逐渐停由运动。随着温度的下降，这些分子逐渐停留在不同的状态。在温度最低时，分子重新留在不同的状态。在温度最低时，分子重新以一定的结构排列。模拟退火算法的直观理以一定的结构排列。模拟退火算法的直观理解是：在一个给定的温度，搜索从一个状态解是：在一个给定的温度，搜索从一个状态随机的变化到另一个状态，每一个状态到达随机的变化到另一个状态，每一个状态到达的次数服从一个概率分布。当温度很低时，的次数服从一个概率分布。当温度很低时，以概率以概率1 1停留在最

3、优解。停留在最优解。内容简介内容简介3 3、遗传算法遗传算法（genetic algorithms）遗传算法主要借用生物进化中遗传算法主要借用生物进化中“适者生存适者生存”的规律而设计。遗传算法包含以下主要步的规律而设计。遗传算法包含以下主要步骤：第一是对优化问题的解进行编码；第骤：第一是对优化问题的解进行编码；第二是适应函数的构造和应用，适应函数基二是适应函数的构造和应用，适应函数基本上依据优化问题的目标函数而定；本上依据优化问题的目标函数而定；第第三是染色体的结合；最后是变异。三是染色体的结合；最后是变异。内容简介内容简介3 3、蚁群优化算法（蚁群优化算法（Ant_Algorithm）的基

4、本）的基本思想是模仿蚂蚁依赖信息素进行通信而显示出思想是模仿蚂蚁依赖信息素进行通信而显示出的社会行为。蚂蚁在行动中，会在他们经过的的社会行为。蚂蚁在行动中，会在他们经过的地方留下一些化学物质，称之为地方留下一些化学物质，称之为“信息素信息素”，这些物质能被同一蚁群中后来的蚂蚁感受到，这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后者的行动，蚂蚁选择这并作为一种信号影响后者的行动，蚂蚁选择这条路径的可能性比选择没有这些物质的路径的条路径的可能性比选择没有这些物质的路径的可能性大，后到者留下的信息素会对原有的信可能性大，后到者留下的信息素会对原有的信息素进行加强，这样越短的路径会被越多

5、的蚂息素进行加强，这样越短的路径会被越多的蚂蚁访问，这个过程一直持续到所有的蚂蚁都走蚁访问，这个过程一直持续到所有的蚂蚁都走最短的那一条路径为止。最短的那一条路径为止。内容简介内容简介4 4、粒子群优化算法粒子群优化算法(Particle Swarm optimization)是是一种进化计算技术一种进化计算技术(Evolutionary Computation)，由由Eberhart博士和博士和Kennedy博士发明。源于对鸟博士发明。源于对鸟群捕食的行为研究。群捕食的行为研究。PSO中，每个优化问题的中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为解都是搜索空间中的一只鸟。我们称之为

6、“粒粒子子”。所有的粒子都有一个由被优化的函数决。所有的粒子都有一个由被优化的函数决定的适应值定的适应值(fitness value)，每个粒子还有一个速，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。追随当前的最优粒子在解空间中搜索。内容简介内容简介5 5、人工神经网络人工神经网络(ARTIFICIAL NEURAL(ARTIFICIAL NEURAL NETWORKNETWORK，简称，简称ANN)ANN)是在对人脑组织结构和运是在对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行机制的认识理解

7、基础之上模拟其结构和智能行为的一种工程系统。神经网络的基本原理为：行为的一种工程系统。神经网络的基本原理为：大脑皮层每一点的活力是由其他点势能释放的大脑皮层每一点的活力是由其他点势能释放的综合效能产生。这一势能同下面的因数有关：综合效能产生。这一势能同下面的因数有关：相关其他点的兴奋次数；兴奋的强度；与其不相关其他点的兴奋次数；兴奋的强度；与其不相连的其他点所接受的能量。人工神经网络的相连的其他点所接受的能量。人工神经网络的建立和应用可以归结为三个步骤：网络结构的建立和应用可以归结为三个步骤：网络结构的确定，关联权的确定和工作阶段。确定，关联权的确定和工作阶段。决策变量有限点集约束函数目标函数

8、,.,0)(.)(minDxxgtsxf.|)(min)(,:,0)(,|:),(FxxfxfFxxFxfxgDxxFDfFD最优解，如果可行解（点）目标函数有限点集可行域决策变量定义域装包？问题：如何以最大价值件物品单位价值，第件物品单位体积，第背包容积.,1:.,1:niicniiabii.1,0i0i 1(1.3).,1,1,0 (1.2),as.t.(1.1)maxn1ii1iniiiniiDxnixbxxc物品，不装第物品装第，其中决策变量包容量限制总价值数学模型：ij1ij1min (1.4)s.t.1.1,2,(1.5)i 1.1,2,ijijijnjnid xxinxjn数学模

9、型：总路长只从城市 出来一次,(1.6)1,21,1,2,(1.7)0,1,1,2,.(1.8):ij,s :s 1,iji j sijijijjxssnsnxi jn ijdijx只走入城市 一次在任意城市子集中不形成回路决策变量其中城市 与城市 之间的距离集合 中元素的个数，走城市 和城市0.:,:,ijjiijjiijTSP ddi jTSP ddi j之间的路径，不走城市 和城市 之间的路径对称距离非对称距离12,.na aa11m in.1,1,2,1,1,2,0,1,1,2,;1,2,B:1,0 .BibbniibiibibBs txina xbBxinbBibxib数 学 模 型

10、：其 中装 下 全 部 物 品 需 要 的 箱 子，第物 品 装 在 第个 箱 子，第物 品 不 装 在 第个 箱 子启发式算法（启发式算法（heuristic algorithmheuristic algorithm）定义1.基于基于直观或经验构造的算法，在可接受构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个问题的每个实例的一个可行解，该可行解与最，该可行解与最优解偏差事先不一定可以预计优解偏差事先不一定可以预计.定义2.启发式算法是一种技术，在可接受的计启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该

11、解的可行性算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。与最优性，无法描述该解与最优解的近似程度。特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.,|j),(iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iin,|j),(iA n1,2,.,NNji nnijd)(),(ji|1)0(Aij),2,1(nw0ims 1)(sL)(sL0i1 s m()|(,),()LsNl i lAl Ls或0()|(,),()L sNTli lA lL si 且(1),(1)ijijijl T

12、kpjTk0,ijpjT()(),:LsLsj ij0()|(,),()Ls N T l ilAl Lsi 且000,()(),:;i LsLsi i i1 s m()L sN()L s()L sN()()f L tf L W()WLt111()(1)(1)(,)()(1)(1)(,)kijkijijkijkki jWWkki jW 为 上的一条弧不是 上的一条弧(),:1ijkkkln1,ln(1)kkkKk k1K 1kk(1)()kijk(,)()1,0iji jAkk()k01 0.5 11011()1.5 5011110ijDd1,1,2,32kk0112 112 112112011

13、2 112(0)(0)112 1120112112 112 1120ij1:,(1)4;2:,(2)3.5;3:,(3)8;4:,(4)4.5;WABCDA f WWACDBA f WWADCBA f WWABDCA f W第一只第二只第三只第四只01 241 61 241 601 241 24(1)(1)1 241 1201 61 241 61 240ij重复外循环，由于上一次得到的重复外循环，由于上一次得到的W2已经是全局已经是全局最优解，因此按算法步骤最优解，因此按算法步骤3的信息素更新规则，的信息素更新规则，无论蚂蚁如何行走，都只是对无论蚂蚁如何行走，都只是对W2路线上的城市路线上的城

14、市信息素进行增强，其他的城市信息素进行挥发。信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵得到更新矩阵这是第一次外循环结束的状态。这是第一次外循环结束的状态。01 485 241 485 2401 481 48(2)(2)1 481 4805 241 485 241 480ij重复外循环，由于重复外循环，由于W2全局最优解，全局最优解，GBAS只记只记录第一个最优解，因此一但得到了全局最优解，录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行而只是不断增强最优路线的信息素，同

15、时进行挥发。第三次外循环后得到的信息素矩阵为：挥发。第三次外循环后得到的信息素矩阵为：01 9611 481 9611 4801 961 96(3)(3)1 961 96011 481 9611 481 960ij蚂蚁以一定的概率从城市蚂蚁以一定的概率从城市i到城市到城市j进行转移，信进行转移，信息素的更新在息素的更新在STEP 3 完成，并随完成，并随K而变化。假而变化。假设第设第K次外循环后得到信息素矩阵次外循环后得到信息素矩阵 ，得到当前最优解得到当前最优解 。第第K次循环前的信息素和最优解为次循环前的信息素和最优解为 ，经过第经过第K次外循环后，得到次外循环后，得到 。由。由于蚂蚁的一步转移概率是随机的，从于蚂蚁的一步转移概率是随机的，从 到到 也是随机的，是一个马尔可夫过程。也是随机的，是一个马尔可夫过程。()()|(,)ijkk i jA()W k(1),(1)kW k(),()kWk(1),(1)kW k(),()k W k