多目标优化算法与求解策略

多目标优化算法与求解策略2多目标优化综述2.1多目标优化的基本概念多目标优化问题(Multi-objectiveOptimizationProblem，MOP)起源于许多实际复杂系统的设计、建模和规划问题，这些系统所在的领域包括工业制造、城市运输、资本预算、森林管理、水库管理、新城市的布局和美化、能量分配等等。几乎每个重要的现实生活中的决策问题都要在考虑不同的约束的同时处理若干相互冲突的目标，这些问题都涉及多个目标的优化，这些目标并不是独立存在的，它们往往是祸合在一起的互相竞争的目标，每个目标具有不同的物理意义和量纲。它们的竞争性和复杂性使得对其优化变得困难。多目标最优化是近20多年来迅速发展起来的应用数学的一门新兴学科。它研究向量目标函数满足一定约束条件时在某种意义下的最优化问题。由于现实世界的大量问题，都可归结为含有多个目标的最优化问题，自70年代以来，对于多目标最优化的研究，在国内和国际上都引起了人们极大的关注和重视。特别是近10多年来，理论探索不断深入，应用范围日益广泛，研究队伍迅速壮大，显示出勃勃生机。同时，随着对社会经济和工程设计中大型复杂系统研究的深入，多目标最优化的理论和方法也不断地受到严峻挑战并得到快速发展。近几年来，将遗传算法(GeneticAlgorithm，GA)应用于多目标优化问题成为研究热点，这种算法通常称作多目标优化进化算法或多目标优化遗传算法。由于遗传算法的基本特点是多方向和全局搜索，这使得带有潜在解的种群能够一代一代地维持下来。从种群到种群的方法对于搜索Pareto解来说是十分有益的。一般说来，科学研究与工程实践中许多优化问题大都是多目标优化问题。多目标优化问题中各目标之间通过决策变量相互制约，对其中一个目标优化必须以其它目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。与单目标优化问题的本质区别在于，多目标优化问题的解不是唯一的，而是存在一个最优解集合，集合中元素称为Pareto最优或非劣最优。所谓Pareto最优就是，不存在比其中至少一个目标好而其它目标不劣的更好的解，也就是不可能通过优化其中部分目标而其它目标不至劣化。Pareto最优解集中的元素就所有目标而言是彼此不可比较的。下面从严格的数学描述角度介绍多目标优化问题的含义。通常在多目标优化领域中广泛采用并普遍接受的别劝尸问题的数学定义如下：定义1.1(MOP)：一般材MOP由n个决策变量参数、k个目标函数和m个约束条件组成，目标函数、约束条件与决策变量之间是函数关系。最优化目标如下：Maximizey=f(x)=(f1(x)，f2(x)，…，fk(x))S.t.e(x)=(e1(x)，e2(x)，…，em(x))≤0（2-1）其中x=(x1，x2，…，xn)∈XY=(y1，y2，…，yk)∈Y这里x表示决策向量，y表示目标向量，X表示决策向量x形成的决策空间，Y表示目标向量y形成的目标空间，约束条件e(x)≤0确定决策向量的可行的取值范围。当有多个目标函数存在的时候，“最优解”概念产生了新的变化。因为在解决多目标问题时，实际上是求一组均衡解，而不是单个的全局最优解。这个被普遍采用的最优解的概念是FrancisYsidroEdgeworth早在1881年提出来的。随后著名的法国经济学家和社会学家帕雷托(VilfredoPareto)在1896年推广了这个概念，他从经济学的角度将本质上不可比较的多个目标转化成单个指标进行优化求解，这里就涉及到多目标的概念。帕雷托首次提出向量优化的概念，即现在广泛使用的Pareto最优。MOP的本质在于大多情况下各子目标可能是相互冲突的，某子目标的改善可能引起其它子目标性能的降低，即同时使多个子目标均达到最优一般是不可能的，否则就不属于多目标优化研究的范畴。解决MOP的最终手段只能是在各子目标之间进行协调权衡和折衷处理，使各子目标函数均尽可能达到最优。因此，MOP的最优解与单目标优化问题的最优解有着本质上的区别，为了正确求解MOP，必须对其解的概念进行定义。定义1.2(可行解集)：可行解集fX定义为满足式(2-1)中的约束条件e(x)的决策向量x的集合，即}0)(|{xeXxXf（2-2）fX的可行区域所对应的目标空间的表达式为：)}({)(xfYxfYfXxff（2-3）对于式（2-3），表示可行解集fX中的所有x，经优化函数映射形成目标空间中的一个子空间，该子空间的决策向量均属于可行解集。对于极小化问题，可以很容易转化为上述的最大化问题来进行求解。单目标优化问题的可行解集能够通过它的唯一的目标函数f来确定方案之间的优劣关系和程度。对于MOP问题来说，情况则有所不同，因为一般来说，fX中的决策向量是无法进行全部排序的，而只能对某个指标进行排序，即部分排序。大多数情况下，类似于单目标优化的最优解在多目标优化问题中是不存在的，只存在Pareto最优解。多目标优化问题的Pareto最优解仅仅只是它的一个可以接受的非劣解或满意解，并且通常的多目标优化问题大多具有很多个Pareto最优解。若一个多目标优化问题存在所谓的最优解，则该最优解必定是Pareto最优解，并且Pareto最优解也只由这些最优解组成，再不包含其它解。因此Pareto最优解是多目标优化问题的合理的解集合。通常多目标优化问题的Pareto最优解是一个集合。对于实际应用问题，必须根据对问题的了解程度和决策人员的个人偏好，从多目标优化问题的Pareto最优解中挑选出一个或多个解作为所求多目标优化问题的最优解。因此求解多目标优化问题的首要步骤和关键是求出尽可能多的Pareto最优解。2.2传统的多目标优化方法大多数传统的多目标优化方法将多个目标减少为一个，然后用数学规划工具求解问题。为了用数学规划工具求解问题，首先需要用数字的形式来表明偏好。数字越大，偏好越强。这种需求促成了各种标量化方法的发展。采用这些方法将多目标优化问题转换为单目标或一系列单目标优化问题，然后可以求解变换后的问题。传统的多目标优化方法有多种，本文选取约束法、加权法、距离函数法、最小最大法这四种多目标优化方法来进行简单的介绍。2.2.1约束法在MOP问题中，从k个目标函数f1(x)，f2(x)，…，fk(x)中，若能够确定一个主要的目标，例如f1(x)，而对于其他的目标函数f2(x)，…，fk(x)只要求满足一定的条件即可，例如要求：kibxfai,3,2,)(这样我们就可以把其他目标当做约束来处理，则MOP问题可以转换为求解如下的单目标优化问题：Maximize)(1xf..tS0))(,),(),(()(21xexexexemkibxfa,,3,2,)(12.2.2加权法加权法将为每个目标函数分配权重并将其组合成为一个目标函数，加权法的基本思想是由Zadeh首先提出，加权方法可以表示如下：Maximizekiiixfxz1)()(..tSfXxi称为权重，不失一般性，通常权重可以正则化使得ki11，求解上述不同权重的优化问题则能够输出一组解。这种方法的最大缺点就是不能在非凸性的均衡曲面上得到所有的Pareto最优解。2.2.3距离函数法距离函数法需要使用理想点，定义理想点如下：定义1.3(理想点)：理想点用),,,(**2*1*kyyyy来表示，其中kiXxxfyft,,3,2},|)(sup{1*。点*y称为理想点（idealpoint）是因为通常该点无法达到。对于每个目标来说，寻找理想点*y是可能的。距离函数法寻找与理想点最近的解，根据理想点*y的定义，对于目标空间的每一个元素，我们无法得到比理想解更好的结果。给定Yy，y与*y的距离函数来近似：*)(yyyr其中*yy是在某种特定范数意义上从y到*y的距离。由于pL范数比较清晰，因此经常采用，对于一个给定的正数1p，有：pkjpjjpyyyypyr/11**);(pL范数意义下的最优解就是最小化);(pyr的点。距离函数);(pyr对于每一个*jjyy的值的重视程度相同。如果具有不同的重要性，可以指派一个权重向量),,,(21k来表明不同的重要程度，在这种情况下，有下面的加权pL范数：pkjpjjpjpyyyywpyr/11*,*),;(2.2.4分层序列法分层序列法是把MOP问题的k个目标函数，按其重要程度排一个次序。例如，不妨设MOP问题的k个目标函数已经排好次序：)(1xf最重要，)(2xf次之，)(3xf再次之，……，最后一个目标为)(xfk。先求出问题：Maximize)(1xf..tS0))(,),(),(()(21xexexexem的最优解)1(x及最优值*1f。即：)(1*11xfMaxfRx其中fXR1再求解问题Maximize)(2xf..tS2Rx问题的最优解)2(x及最优值*2f。即：)(2*22xfMaxfRx其中})(|{*1112fxfxRR继续求解问题Maximize)(3xf..tS3Rx问题的最优解)3(x及最优值*3f。即：)(3*33xfMaxfRx其中})(|{*2223fxfxRR……如此继续下去，直到求出第k个问题Maximize)(xfk..tSkRx问题的最优解)(kx及最优值*kf。即：)(*xfMaxfkRxkk其中})(|{*111kkkkfxfxRR这样求得的)(kx就是MOP问题在分层序列意义下的最优解，即)(*kxx，而))(,),(),((**2*1*xfxfxfFk为MOP问题的最优值。2.3传统优化方法的局限性传统方法的优点在于它继承了求解单目标优化问题的一些成熟算法的机理。但是经典方法如加权法求解多目标优化问题时，对Pareto最优前沿的形状很敏感，不能处理前沿的凹部，并且求解问题所需的与应用背景相关的启发式知识信息获得很少，导致无法正常实施优化或优化效果差，特别对于大规模问题，这些多目标优化方法很少真正能被使用。前面介绍的传统的多目标优化方法存在一些局限性，主要包括一下几点：(l)一些古典方法如加权法求解多目标优化问题时，对Pareto最优前端的形状很敏感，不能处理前端的凹部。(2)只能得到一个解。然而，在实际决策中决策者通常需要多种可供选择的方案。(3)传统方法共同存在的一个关键问题就是为了获得Pareto。最优集须运行多次优化过程，由于各次优化过程相互独立，往往得到的结果很不一致令决策者很难有效地决策，而且要花费巨额时间开销。(4)多个目标函数之间量纲不同，难以统一。为了避免其中的一个目标函数支配其他目标函数，精确的给出所有目标函数的标量信息，就必须有每一个目标的全局先验知识，计算量巨大，很难实现。(5)加权值的分配带有较强的主观性。由于是人为规定各个目标函数的权值，因此带有很大的主观性。最近遗传算法己经作为一种多目标优化方法崭露头角。它的优点在于可处理大规模的搜索空间、在单轮优化期间产生多个均衡解，可有效克服古典方法的局限性，所以本文采用遗传算法对关系模型进行优化。2.4遗传算法的基本原理和方法达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。遗传算法(Gen