多目标优化问题的求解算法PPT课件

多目标优化问题的求解算法,2017.12.06,1,.,目录,一、多目标优化问题概述,二、基于蚁群算法的多目标优化,2,.,多目标优化问题(Multi-objectiveOptimizationProblem,MOP)是由VilfredoPareto首次从数学的角度提出的。,一、多目标优化问题概述,3,.,单目标优化问题，只有一个目标函数，人们只需要寻找满足该目标函数的最优解即可。多目标优化问题，由于存在多个目标函数和约束条件，所以当一个目标达到最优就很有可能令其它目标最劣，各个目标彼此间互相牵制和影响的，难以实现所有目标的最优化，所以不能根据一个目标是否达到来评价函数解的优劣程度，因此通常用一个最优解的集合来表示多目标优化问题的解。这种解称作Pareto最优解。,1.多目标优化问题与单目标优化问题的不同点,4,.,工程项目施工过程中，多目标已经成为当今施工管理的一大特点，不能看某一目标要求是否实现来评价这个施工方案的合理与否，只有满足均衡好多个目标要求的施工方案才是好的施工方案。因此，选取最优解集中的一个或多个解作为所求问题的解，并据此确定出对应的最优施工方案。,2.施工管理的一大特点,5,.,3.多目标优化问题的定义,6,.,4.多目标优化问题的基本方法,现有的研究多目标优化问题的基本方法往往是把各个目标通过带权重系数的方式转化为单目标优化问题，如线性加权法、约束法、目标规划法、分层序列法等。这几种方法存在一些局限性，如有些方法计算效率较低，无法逐一与所有可行解的目标值进行比较，有些方法需要进行多次优化，加权值法带有较强的主观性，有失科学性。,7,.,4.多目标优化问题的基本方法,因此，随着实际中多目标优化问题的日益复杂，也为了使优化更符合实际情况，许多对多目标综合模型的优化开始转向运用智能启发式算法。运用较多的有遗传算法、蚁群算法、粒子群算法等，这些智能方法普遍具有高效性，较强的全局搜索的能力，将其应用到大型复杂网络系统问题中具有一定研究价值。,8,.,二、基于蚁群算法的多目标优化,1.基本原理,蚁群算法(Antcolonyalgorithm,ACA)由M.Dorigo，VManiezzo等人提出的是一种智能优化算法。蚁群算法是模拟蚂蚁觅食过程中总是能够找到从蚁穴到食物之间的最短路径的行为过程。我们用“信息素”来描述蚂蚁在搜索食物的过程中产生的物质，这种物质能够被后续的蚂蚁感知并该物质的浓度来指导其前进的方向。蚂蚁选择某条路径的概率就是根据该路径上的信息素浓度，浓度高被蚂蚁选择的概率就越大。依照这种信息交流的方式，蚂蚁最终寻找到最短的搜索到食物的路径。,9,.,2.TSP问题案例,10,.,11,.,12,.,3.多目标优化作用机理,本文以基本蚁群算法为基础，采用了基于多种群的蚁群优化算法。多种群优化算法解决多目标优化问题的基本思想是:将蚁群按照目标函数的个数分成对应的种群数，假如有M个目标函数那么将蚁群分成M个种群，各个种群搜索时彼此是独立的，按照一定的规则进行路径的选择、信息素的更新，使各种群之间相互作用，最终找到Pareto最优解。,13,.,在对多目标问题的研究中，有的是把多目标转化成单目标优化问题。而实际工程项目中，成本、工期、质量及安全之间不能用简单的线性或者非线性关系来描述，所以本文为了更符合实际情况，将协同化思想引入到蚁群算法中，针对四个目标建立四个蚁群，各种群在各自的目标要求下搜索Pareto解集。,14,.,（1）问题的抽象及算法的定义,把建筑工程项目中每一道工序作为完成整个工程项目所必须经过的路径，那么所有工序的顺序序列构成一条完整的工程项目的全通路。即人工蚂蚁搜索的路径是由n道工序构成的施工网络图。由于每道工序有不同种工作模式(即实施方案)，一个。道工序的工程项目就构成了一个nxm的矩阵(如下所示)，蚂蚁就是在该矩阵中进行搜索。矩阵中，lm表示第i道工序的第m种工作模式。,15,.,那么蚂蚁的搜索路径可以表示如下:,每边可以采用三元组来表示，如(i，J1，J2)表示第i个工作单元采用的第J1，各实施方案，第i+1个工作单元采用的是第J2个实施方案。图中的每一条从一行到n行的线路表示整个项目的一个实施计划方案，工期、成本、质量及安全的多目标优化问题实际上就是在图中找出一条从一行到n行的线路，使得四大目标协同最优。,16,.,（2）路径选择策略,根据建筑工程项目施工管理中的工期、成本、质量和安全四大目标，将蚂蚁分为四个种群。假设一共有N只蚂蚁，每只蚂蚁的行走路径代表一个施工项目的实施计划方案，蚂蚁每做一次选择就是为某项工序选择一种施工方案，依次为每个工作单元选择一种施工方案。选取其中一只蚂蚁k为例，把每个工作单元的节点当作一个起始点，蚂蚁根据各边上的信息素强度来选择下一步的移动方向，在完成工序i的第J1个实施方案后继续选择工序i+1的第J2种实施方案的概率为:,17,.,18,.,（3）信息素更新方式,所有蚂蚁完成一次循环后，各边的信息素强度按照下式更新:,19,.,20,.,21,.,（4）种群间信息素的协调方式,协同进化思想是由Ehrlich和Raven首先的提出的，主要研究的是植物和植物性昆虫互相作用时会对彼此进化产生的影响。协同进化是指当存在多个种群时，任何一个种群和其它种群之间存在相互作用，其它种群会对该种群造成影响，能够促进对该种群在当前环境中的进化。本文把协同进化的思想引入到多种群蚁群算法中，从而解决基于多种种群的蚁群算法的多目标优化问题。,22,.,本文采用的是多种群蚁群算法，考虑到每个种群存在不同的搜索目标，彼此之间相互影响，例如在起初寻找最低成本的路径和最高质量的路径的进化方向就是相反的，为了避免各目标向目标的反方向进行，从协同进化的角度考虑，把各种群搜索求得的解，分别代入四个目标函数中求解出对应的函数值，并与目标值进行比较，当存在种群的目标函数值不满足目标值时，对满足的路径上的信息素可以进行交叉或者变异操作，防止已经满足要求的种群“背道而驰”，使得后续迭代的种群能够朝着有利路径逼近最优解。,23,.,本文中，为每个目标设定一个目标阀值，各种群都在该工程的施工网络可靠性框图上进行搜索，把每个种群每搜索得到的新解(一个实施方案的工序组合)依次代入目标函数中，所得值和预先设定阀值进行比较分析。,产生以下几种情况:,若四个种群搜索的解对应的函数值都优于目标值的，就把把该解加到入解集中，再按照公式(4-15)进行更新。若搜索出的解和非支配解集中的某个解相同，就对这条路径上的信息素进行一定比例减少，防止陷入局部最优。若有三个目标函数值优于设定的目标值，就将这三个目标种群在其对应的路径上选取其中某段路径，对此路径上的信息素进行变异处理。,24,.,若有两个目标函数值优于设定的目标值，那么将这两个目标种群在其对应的路径上选择其中某一段的信息素进行变异处理。若只有一个目标函数值优于设定的目标阀值，就把这个种群在这条路径的的信息素和其它三个种群相同段上的信息素进行交叉处理。除了以上几种情况之外，当四个目标函数值均劣于目标值时，就根据如下公式更新信息素，并进行下一次的迭代搜索。,25,.,（5）路径对蚂蚁的吸引程度,26,.,（6）非支配解集的构造,在求解多目标优化问题时，在向Pareto前沿逼近的过程中往往需要构造非支配解集，即利用多目标优化算法不断寻找最优和收敛的过程。群体进化过程中形成的最优个体集合就构成了非支配解集。因此，求解多目标优化问题的Pareto最优解，可理解成是构造非支配解集的过程。,27,.,为防止搜索过程中出现相同的非支配解的情况，在算法中设置了一个外部集合A(t)用来存放当前搜索到的非支配解，从而更好地指导蚂蚁对可行区域的搜索。通过和目标值比较，判断是否将该解存放于A(t)中，当搜索到一个满足条件的解，但与A(t)解集中的解相同时，就不再存放于A(t)中。,28,.,（1）搜索禁忌表的构造,4.算法的实现,就建筑工程项目施工过程而言，有些活动可能会制约其他活动的执行，每项工序都受到其紧前紧后工序的制约，为了防止蚂蚁搜索出的路径不符合实际工程情况，设立了一个搜索禁忌表，使蚂蚁只能搜索禁忌表内允许的节点。随着蚂蚁遍历过程的不断更新，搜索禁忌表也不断更新。如第k只蚂蚁的搜索禁忌表为allowed，当蚂蚁经过工序节点i后，就将其已经经过的节点存放在、isited集(表示蚂蚁已经遍历的节点的集合)中，并且更新该只蚂蚁的allowed。,29,.,基本思路,（2）算法的实现及流程