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