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

多目的优化问题的求解算法

第一页，共32页。目录一、多目的优化问题概述二、基于蚁群算法的多目的优化第二页，共32页。多目的优化问题(Multi-objectiveOptimizationProblem,MOP)是由VilfredoPareto首次从数学的角度提出的。一、多目的优化问题概述第三页，共32页。

单目的优化问题，只有一个目的函数，人们只需要寻找满足该目的函数的最优解即可。多目的优化问题，由于存在多个目的函数和约束条件，所以当一个目的到达最优就很有可能令其它目的最劣，各个目的彼此间互相牵制和影响的，难以实现所有目的的最优化，所以不能根据一个目的是否到达来评价函数解的优劣程度，因此通常用一个最优解的集合来表示多目的优化问题的解。这种解称作Pareto最优解。1.多目的优化问题与单目的优化问题的不同点第四页，共32页。

工程工程施工过程中，多目的已经成为当今施工管理的一大特点，不能看某一目的要求是否实现来评价这个施工方案的合理与否，只有满足平衡好多个目的要求的施工方案才是好的施工方案。因此，选取最优解集中的一个或多个解作为所求问题的解，并据此确定出对应的最优施工方案。2.施工管理的一大特点第五页，共32页。

3.多目的优化问题的定义第六页，共32页。

4.多目的优化问题的根本方法现有的研究多目的优化问题的根本方法往往是把各个目的通过带权重系数的方式转化为单目的优化问题，如线性加权法、约束法、目的规划法、分层序列法等。这几种方法存在一些局限性，如有些方法计算效率较低，无法逐一与所有可行解的目的值进展比较，有些方法需要进展屡次优化，加权值法带有较强的主观性，有失科学性。第七页，共32页。

4.多目的优化问题的根本方法因此，随着实际中多目的优化问题的日益复杂，也为了使优化更符合实际情况，许多对多目的综合模型的优化开场转向运用智能启发式算法。运用较多的有遗传算法、蚁群算法、粒子群算法等，这些智能方法普遍具有高效性，较强的全局搜索的才能，将其应用到大型复杂网络系统问题中具有一定研究价值。第八页，共32页。

二、基于蚁群算法的多目的优化1.根本原理蚁群算法(Antcolonyalgorithm,ACA)由M.Dorigo，VManiezzo等人提出的是一种智能优化算法。蚁群算法是模拟蚂蚁觅食过程中总是可以找到从蚁穴到食物之间的最短途径的行为过程。我们用“信息素〞来描绘蚂蚁在搜索食物的过程中产生的物质，这种物质可以被后续的蚂蚁感知并该物质的浓度来指导其前进的方向。蚂蚁选择某条途径的概率就是根据该途径上的信息素浓度，浓度高被蚂蚁选择的概率就越大。按照这种信息交流的方式，蚂蚁最终寻找到最短的搜索到食物的途径。第九页，共32页。

问题案例第十页，共32页。

第十一页，共32页。

第十二页，共32页。3.多目的优化作用机理本文以根本蚁群算法为根底，采用了基于多种群的蚁群优化算法。多种群优化算法解决多目的优化问题的根本思想是:将蚁群按照目的函数的个数分成对应的种群数，假设有M个目的函数那么将蚁群分成M个种群，各个种群搜索时彼此是独立的，按照一定的规那么进展途径的选择、信息素的更新，使各种群之间互相作用，最终找到Pareto最优解。

第十三页，共32页。在对多目的问题的研究中，有的是把多目的转化成单目的优化问题。而实际工程工程中，本钱、工期、质量及平安之间不能用简单的线性或者非线性关系来描绘，所以本文为了更符合实际情况，将协同化思想引入到蚁群算法中，针对四个目的建立四个蚁群，各种群在各自的目的要求下搜索Pareto解集。

第十四页，共32页。〔1〕问题的抽象及算法的定义把建筑工程工程中每一道工序作为完成整个工程工程所必须经过的途径，那么所有工序的顺序序列构成一条完好的工程工程的全通路。即人工蚂蚁搜索的途径是由n道工序构成的施工网络图。由于每道工序有不同种工作形式(即施行方案)，一个。道工序的工程工程就构成了一个nxm的矩阵(如下所示)，蚂蚁就是在该矩阵中进展搜索。矩阵中，lm表示第i道工序的第m种工作形式。

第十五页，共32页。那么蚂蚁的搜索途径可以表示如下:

每边可以采用三元组来表示，如(i，J1，J2)表示第i个工作单元采用的第J1，各施行方案，第i+1个工作单元采用的是第J2个施行方案。图中的每一条从一行到n行的线路表示整个工程的一个施行方案方案，工期、本钱、质量及平安的多目的优化问题实际上就是在图中找出一条从一行到n行的线路，使得四大目的协同最优。第十六页，共32页。〔2〕途径选择策略根据建筑工程工程施工管理中的工期、本钱、质量和平安四大目的，将蚂蚁分为四个种群。假设一共有N只蚂蚁，每只蚂蚁的行走途径代表一个施工工程的施行方案方案，蚂蚁每做一次选择就是为某项工序选择一种施工方案，依次为每个工作单元选择一种施工方案。选取其中一只蚂蚁k为例，把每个工作单元的节点当作一个起始点，蚂蚁根据各边上的信息素强度来选择下一步的挪动方向，在完成工序i的第J1个施行方案后继续选择工序i+1的第J2种施行方案的概率为:

第十七页，共32页。第十八页，共32页。〔3〕信息素更新方式

所有蚂蚁完成一次循环后，各边的信息素强度按照下式更新:

第十九页，共32页。

第二十页，共32页。

第二十一页，共32页。〔4〕种群间信息素的协调方式协同进化思想是由Ehrlich和Raven首先的提出的，主要研究的是植物和植物性昆虫互相作用时会对彼此进化产生的影响。协同进化是指当存在多个种群时，任何一个种群和其它种群之间存在互相作用，其它种群会对该种群造成影响，可以促进对该种群在当前环境中的进化。本文把协同进化的思想引入到多种群蚁群算法中，从而解决基于多种种群的蚁群算法的多目的优化问题。

第二十二页，共32页。本文采用的是多种群蚁群算法，考虑到每个种群存在不同的搜索目的，彼此之间互相影响，例如在起初寻找最低本钱的途径和最高质量的途径的进化方向就是相反的，为了防止各目的向目的的反方向进展，从协同进化的角度考虑，把各种群搜索求得的解，分别代入四个目的函数中求解出对应的函数值，并与目的值进展比较，当存在种群的目的函数值不满足目的值时，对满足的途径上的信息素可以进展穿插或者变异操作，防止已经满足要求的种群“背道而驰〞，使得后续迭代的种群可以朝着有利途径逼近最优解。

第二十三页，共32页。本文中，为每个目的设定一个目的阀值，各种群都在该工程的施工网络可靠性框图上进展搜索，把每个种群每搜索得到的新解(一个施行方案的工序组合)依次代入目的函数中，所得值和预先设定阀值进展比较分析。

产生以下几种情况:①假设四个种群搜索的解对应的函数值都优于目的值的，就把把该解加到入解集中，再按照公式(4-15)进展更新。假设搜索出的解和非支配解集中的某个解一样，就对这条途径上的信息素进展一定比例减少，防止陷入部分最优。②假设有三个目的函数值优于设定的目的值，就将这三个目的种群在其对应的途径上选取其中某段途径，对此途径上的信息素进展变异处理。第二十四页，共32页。③假设有两个目的函数值优于设定的目的值，那么将这两个目的种群在其对应的途径上选择其中某一段的信息素进展变异处理。④假设只有一个目的函数值优于设定的目的阀值，就把这个种群在这条途径的的信息素和其它三个种群一样段上的信息素进展穿插处理。⑤除了以上几种情况之外，当四个目的函数值均劣于目的值时，就根据如下公式更新信息素，并进展下一次的迭代搜索。

第二十五页，共32页。〔5〕途径对蚂蚁的吸引程度

第二十六页，共32页。〔6〕非支配解集的构造

在求解多目的优化问题时，在向Pareto前沿逼近的过程中往往需要构造非支配解集，即利用多目的优化算法不断寻找最优和收敛的过程。群体进化过程中形成的最优个体集合就构成了非支配解集。因此，求解多目的优化问题的Pareto最优解，可理解成是构造非支配解集的过程。

第二十七页，共32页。为防止搜索过程中出现一样的非支配解的情况，在算法中设置了一个外部集合A(t)用来存放当前搜索到的非支配解，从而更好地指导蚂蚁对可行区域的搜索。通过和目的值比较，判断是否将该解存放于A(t)中，当搜索到一个满足条件的解，但与A(t)解集中的解一样时，就不再存放于A(t)中。

第二十八页，共32页。〔1〕搜索禁忌表的构造4.算法的实现就建筑工程工程施工过程而言，有些活动可能会制约其他活动的执行，每项工序都受到其紧前紧后工序的制约，为了防止蚂蚁搜索出的途径不符合实际工程情况，设立了一个搜索禁忌表，使蚂蚁只能搜索禁忌表内允许的节点。随着蚂蚁遍历过程的不断更新，搜索禁忌表也不断更新。如第k只蚂蚁的搜索禁忌表为allowed，当蚂蚁经过工序节点i后，就将其已经经过的节点存放在、isited集(表示蚂蚁已经遍历的节点的集合)中，并且更新该只蚂蚁的allowed。第二十九页，共32页。根本思路〔2〕算法的实现及流程图