最新多目标优化问题的求解算法教学讲义ppt课件.ppt

《最新多目标优化问题的求解算法教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多目标优化问题的求解算法目录一、多目标优化问题概述二、基于蚁群算法的多目标优化多目标优化问题(Multi-objectiveOptimizationProblem,MOP)是由VilfredoPareto首次从数学的角度提出的。一、多目标优化问题概述4.多目标优化问题的基本方法现有的研究多目标优化问题的基本方法往往是把各个目标通过带权重系数的方式转化为单目标优化问题，如线性加权法、约束法、目标规划法、分层序列法等。这几种方法存在一些局限性，如有些方法计算效率较低，无法逐一与所有可行解的目标值进行比较，有些方法需要进行多次优化，加权值法带有较强的主观性，有失科学性。4.多目标优化

2、问题的基本方法因此，随着实际中多目标优化问题的日益复杂，也为了使优化更符合实际情况，许多对多目标综合模型的优化开始转向运用智能启发式算法。运用较多的有遗传算法、蚁群算法、粒子群算法等，这些智能方法普遍具有高效性，较强的全局搜索的能力，将其应用到大型复杂网络系统问题中具有一定研究价值。二、基于蚁群算法的多目标优化1.基本原理蚁群算法(Antcolonyalgorithm,ACA)由M.Dorigo，VManiezzo等人提出的是一种智能优化算法。蚁群算法是模拟蚂蚁觅食过程中总是能够找到从蚁穴到食物之间的最短路径的行为过程。我们用“信息素”来描述蚂蚁在搜索食物的过程中产生的物质，这

3、种物质能够被后续的蚂蚁感知并该物质的浓度来指导其前进的方向。蚂蚁选择某条路径的概率就是根据该路径上的信息素浓度，浓度高被蚂蚁选择的概率就越大。依照这种信息交流的方式，蚂蚁最终寻找到最短的搜索到食物的路径。2.TSP问题案例3.多目标优化作用机理本文以基本蚁群算法为基础，采用了基于多种群的蚁群优化算法。多种群优化算法解决多目标优化问题的基本思想是:将蚁群按照目标函数的个数分成对应的种群数，假如有M个目标函数那么将蚁群分成M个种群，各个种群搜索时彼此是独立的，按照一定的规则进行路径的选择、信息素的更新，使各种群之间相互作用，最终找到Pareto最优解。在对多目标问题的研究中，有的是

4、把多目标转化成单目标优化问题。而实际工程项目中，成本、工期、质量及安全之间不能用简单的线性或者非线性关系来描述，所以本文为了更符合实际情况，将协同化思想引入到蚁群算法中，针对四个目标建立四个蚁群，各种群在各自的目标要求下搜索Pareto解集。（1）问题的抽象及算法的定义把建筑工程项目中每一道工序作为完成整个工程项目所必须经过的路径，那么所有工序的顺序序列构成一条完整的工程项目的全通路。即人工蚂蚁搜索的路径是由n道工序构成的施工网络图。由于每道工序有不同种工作模式(即实施方案)，一个。道工序的工程项目就构成了一个nxm的矩阵(如下所示)，蚂蚁就是在该矩阵中进行搜索。矩阵中，lm表

5、示第i道工序的第m种工作模式。那么蚂蚁的搜索路径可以表示如下:每边可以采用三元组来表示，如(i，J1，J2)表示第i个工作单元采用的第J1，各实施方案，第i+1个工作单元采用的是第J2个实施方案。图中的每一条从一行到n行的线路表示整个项目的一个实施计划方案，工期、成本、质量及安全的多目标优化问题实际上就是在图中找出一条从一行到n行的线路，使得四大目标协同最优。（2）路径选择策略根据建筑工程项目施工管理中的工期、成本、质量和安全四大目标，将蚂蚁分为四个种群。假设一共有N只蚂蚁，每只蚂蚁的行走路径代表一个施工项目的实施计划方案，蚂蚁每做一次选择就是为某项工序选择一种施工方案，依次为

6、每个工作单元选择一种施工方案。选取其中一只蚂蚁k为例，把每个工作单元的节点当作一个起始点，蚂蚁根据各边上的信息素强度来选择下一步的移动方向，在完成工序i的第J1个实施方案后继续选择工序i+1的第J2种实施方案的概率为:（3）信息素更新方式所有蚂蚁完成一次循环后，各边的信息素强度按照下式更新:（4）种群间信息素的协调方式协同进化思想是由Ehrlich和Raven首先的提出的，主要研究的是植物和植物性昆虫互相作用时会对彼此进化产生的影响。协同进化是指当存在多个种群时，任何一个种群和其它种群之间存在相互作用，其它种群会对该种群造成影响，能够促进对该种群在当前环境中的进化。本文把协同进

7、化的思想引入到多种群蚁群算法中，从而解决基于多种种群的蚁群算法的多目标优化问题。本文采用的是多种群蚁群算法，考虑到每个种群存在不同的搜索目标，彼此之间相互影响，例如在起初寻找最低成本的路径和最高质量的路径的进化方向就是相反的，为了避免各目标向目标的反方向进行，从协同进化的角度考虑，把各种群搜索求得的解，分别代入四个目标函数中求解出对应的函数值，并与目标值进行比较，当存在种群的目标函数值不满足目标值时，对满足的路径上的信息素可以进行交叉或者变异操作，防止已经满足要求的种群“背道而驰”，使得后续