涉及二次函数的多目标优化

文摘

多目标优化是现在一个词的顺序工程项目。虽然涉及的想法很简单,任何程序的实现来解决一般问题不是一个容易的任务。进化算法普遍存在作为一个令人满意的技术找到一组候选的解决方案。通常他们供应一个离散的帕累托面前,即使这方面是连续的。在本文中,我们提出三种方法求解无约束多目标优化问题涉及二次函数。首先,biobjective优化定义在二维的空间中,一组连续的帕累托分析发现。第二,适用于多目标优化,测试条件,提出了检查决策空间中的一个点是否帕累托最优,第三,函数中定义n维空间,直接noniterative算法找到帕累托集。简单的问题凸显了该方法的适用性。

1。介绍

生活是关于决策和最优解的选择不是独家主题为科学家,工程师,和经济学家。决策存在于日常生活中。寻找一个令人愉快的空缺,每个人都会制定一个旅行社的优化问题,一个问题和一个最少的钱访问最多的地方在最少的时间内,最大程度的舒适。通常所有的设计问题有多个目标;也就是说,他们是多目标。此外,设计目标往往是对立的。

埃奇沃斯(1)是定义一个最优的先锋经济多准则决策问题,伦敦大学国王学院。它是关于multiutility问题的上下文中两个消费者,和。”它是需要找到一个点 这样在任何方向我们采取一个无限小的步骤, 和 不增加在一起,但是,当一个增加,减少。”

几年后,在1896年,帕累托(2瑞士洛桑大学的),,他的两个主要理论,制定循环的精英和帕累托最优。”社会最优的资源配置没有达到只要有可能使至少一个人最好在他自己的估计,同时保持其他人也像以前一样在自己的估计。”

自那时以来,许多研究人员一直致力于开发方法来解决这种问题。有趣的是,对于问题的解决方案有多个目标,也称为多准则优化或向量优化,被视为帕累托最优解或帕累托面前,虽然,施(3)观察,他们应该被视为Edgeworth-Pareto解决方案。

严格的审核,包括多目标优化的概念和方法是由当天艳阳高照4由戈德堡[],进化算法5由Deb[]和进化多目标优化6]。这项工作中采用的理论依据多目标优化是基于这些引用。

由于计算机的发展,大规模优化问题成为工程设计中常见的任务。高速计算机的发展和越来越多地使用在几个工业分支导致重大变化在设计过程。目前,电脑,每次快,允许工程师考虑更广泛的设计可能性和优化流程允许系统备选方案之间的选择,因为它们是基于一些合理的标准。如果充分使用,在大多数情况下,这些程序可以改善甚至产生设计的最终结果。

伴随着计算机的发展,许多优化研究的重点是数值方法来解决任何类型的问题,但有时可以简化问题提供重要线索的设计师在权衡阶段决定。

目前的工作旨在将新方法解决多目标优化问题,提供了一个快速解决方案的帕累托集如果涉及的目标函数是二次。

论文的其余部分被组织成3部分。在第一部分一般多目标优化问题是制定和帕累托最优解的性质角度,定义了满足必要的条件。在第二部分中,三个命题是解决涉及二次函数的无约束多目标优化问题。在第一部分一般问题由两个二维的函数。在这种情况下,建议允许找到帕累托分析”。在第二部分,问题考虑三个或更多的函数的极小化问题,将决定在二维空间。在这种情况下,命题有助于找到帕累托点和决策空间的边界。在第三部分,命题的决策空间扩展到任何尺寸大小。最后,结论和建议部分提出了未来的工作。

2。多目标优化问题

多目标优化问题(MOOP)可以由以下方程: 在哪里是一个矢量与标量目标函数的值最小化。包含设计变量的向量,也称为决策变量,在设计空间中定义。和分别是,设计的上下边界变量。代表了不等式约束函数和的等式约束函数。方程(1 b)(1 d)定义的可行的解决方案,,在设计空间。的约束类型的””功能的““功能可能转化为第一类如果乘以−1。同样,问题考虑了”最小化”,因为函数”最大化“可以转化为前乘以−1。

2.1。帕累托最优解

“最优”的概念在解决多目标优化问题被称为“帕累托最优。”A solution is said to be Pareto optimal if there is no way to improve one objective without worsening at least another; that is, the feasible point是帕累托最优,如果没有其他可行的意义这样对所有和。由于冲突的目标函数的性质,帕累托最优解通常是分散在该地区,因此无法同时最小化所有目标函数。在解决优化问题得到帕累托集或帕累托最优解决方案在设计空间中定义和帕累托前沿,目标函数的图像,在标准空间,计算最优解集。

2.2。帕累托最优的必要条件

事实上,表达的多目标优化问题(1)- (1 d)是普通字符。方程代表简略优化时的问题。根据当天艳阳高照4),如在简略优化问题,解决方案的帕累托最优必须满足Karush-Kuhn-Tucker(马)条件下,表示如下: 在哪里权重因子的梯度目标函数,计算点,。代表了权重因子的梯度th不等式约束函数,相关的约束功能,是零当不活跃;也就是说,。代表了权重因子的梯度th等式约束函数,。

方程(2)(2 e)形成的必要条件描述的是一个帕累托最优当天艳阳高照(4]。它们满足帕累托的完整映射前如果问题是凸目标函数是连续可微的空间。否则,该解决方案将取决于附加条件,如马勒所示和Arora7]。

我们将在第二部分提出的方法可以分类后验偏好清晰度和最重要的一个广泛的文献综述方法解决多目标优化问题可以在奥古斯托et al。8]。

3所示。二维C类的函数¹

在本节中,我们提出一个简单的策略来确定决策空间中的帕累托集函数空间和相应的帕累托面前,MOOP涉及两个二维的可微函数。考虑一个无约束多目标优化问题。从(2),最优条件可以被下面的命题。

命题1。如果存在一个帕累托面前最小化问题和两个连续可微的函数中定义说,和然后在决策空间的点,这两个函数的梯度是平行的,相反,定义一组连续的帕累托连接这两个函数的最小值。

每个函数的梯度是正交的轮廓和向外从起薪点,曲线中提到的命题1就是这两个函数的梯度的轨迹是平行的,相反,如图1。

3.1。两个二次函数中定义空间

命题1相当一般,但正如我们的重点是二次函数让我们解决无约束biobjective优化问题涉及二次函数中定义二维决策空间;也就是说,。问题定义如下:最小化:

应用最优条件,,(3)和(3 b结果在以下:

的系统(4)是齐次、非平凡解,需要一个奇点;也就是说,必须零系数矩阵的行列式。考虑 结果在接下来的二次曲线: 在哪里

功能梯度和定义的曲线是平行的(6),但他们必须相反,导致积极的重量(4)。被系统奇异,找到一个权重之间的关系和我们可以只使用一个方程的另一种是它的线性组合。使用第一个方程,这个关系可以推断如下: 有积极的价值当且仅当哪一个

因此,(6)提供的轨迹函数梯度是平行的,(9)定义了帕累托集的两个二次函数最小化问题。的上限(9) 如果第一项达到或第二。作为两个术语是第一个组件和这些条件分别意味着解决方案已经结束了最低或以上最小值。总之,二次函数的帕累托集将二次曲线连接的函数最小值和梯度是平行的,方向相反。

例如,让我们考虑以下biobjective问题:最小化: 从(6),帕累托集的形式 并受到下列不等式:

在图2(一个)函数的轮廓和在二维空间描述的决定。厚的灰色连续曲线代表(12)和厚蓝色曲线满足的彩色部分(13像预期的那样),被连续帕累托集,即曲线沿着梯度向量是平行的,相反。在图2 (b),连续曲线中的帕累托集函数的图像空间,即帕累托。此外,蓝点点优化函数的图像是在规则的网格计算在设计空间。

相比之下,如图2 (c)和2 (d)改编自奥古斯托et al。8),解决方案是通过遗传算法NSGA二世Deb et al。9]。可以看出函数空间中的点是均匀分布的,但它们并不是在决策空间。这是因为搜索过程在大多数的气体主要是函数空间,试图得到一个均匀帕累托。

3.2。三个或三个以上函数中定义空间

在前一节中我们发现一个封闭形式的解决方案优化的两个二次函数空间二维的决定。不幸的是,我们没有发现类似的解决问题当我们添加更多的功能。然而,命题背后的想法1仍然是有用的。

考虑一个涉及三个连续可微函数的优化问题,,。如果一个点属于帕累托集,它必须满足(2),(2 b),(2摄氏度),(二维)和(2 e)。因此,一个梯度向量,将其他两个的线性组合,和;也就是说,积极的重量,这样就存在

在图3这样的条件的梯度向量,,与他们相关的加权因素,,分别说明。

一个平衡条件存在时是面向通过相反的角部门定义的其他两个梯度向量,即和。

基于这个想法,我们建议以下。

命题2。让被定义的单位向量,,单位向量正交;也就是说,。如果属于帕累托集的多目标优化问题涉及连续和可微函数中定义,那么至少存在三个单位向量,说,,,满足下列条件:

的方向在两个semiplanes把决策空间。如果向量指向一边,然后(15一个)和(15 b)状态向量和另一边,(15摄氏度)指出,他们之间放置。

方程(15一个),(15 b)和(15摄氏度)形成条件测试点是帕累托最优。这个测试可能是有用的,如果问题几乎没有优化函数作为探索所有杰出的集和三个梯度向量问题目标函数;的最大的排列的必须检查。让我们应用命题2找到解决方案的一个无约束MOOP三二次目标函数,其中两个是那些定义为(11个)和(11 b)和第三个定义

在图4应用帕累托帕累托集发现,测试点的常规电网在设计空间划分为每个坐标轴50分,对所有,,所示。连续获得了帕累托集的边界应用命题1为每个目标函数。

3.3。二次函数中定义空间

在前两个部分我们已经考虑无约束MOOP用二次函数在二维空间中定义。进入更大的尺寸,让我们定义一个二次函数空间,写如下: 与 和是一个方便的地方坐标系统的定义,局部坐标系的位置相关的全球,然后呢坐标变换矩阵,从地方到全球坐标系统。

使用(18),(17)可以改写如下: 调用,(19)可以改写如下: 作为光滑,其梯度向量是吗 矩阵,以及它的转化形式的对称黑森,,包含第二次偏导数。

这些定义,让是一个无约束的解决方案MOOP涉及二次函数中定义空间。因此,存在,满足(2);也就是说,

作为是一个二次,(21可以使用)和(22)的形式

在(23),重量,以及搜索解决方案都是未知的。让我们假设所有是已知的;也就是说,。因此,(23)可以改写如下: 调用 然后(24)可以改写如下:

让我们假设所有是正定;也就是说,,尽管。如果是真实的,非负和满足标准化平等,也就是说,,然后也将正定,因此它的逆将永远存在。

因此,帕累托最优的解决方案可以很容易地发现解决(27);也就是说,

在这种方法中,我们认为是已知的。因此,,(25),,(26),及时发现。虽然这并非如此的通解(22),这种方法是非常有用的发现帕累托集和帕累托面前无约束多目标优化问题涉及二次函数考虑以下。

命题3。考虑一个MOOP涉及二次函数,每个函数的黑森正定。获得下面的步骤提出了帕累托最优解决方案。(1)随机排序,时间间隔的组件,一个向量包含权重。(2)执行标准化等。(3)计算和。(4)解决线性系统帕累托点与。(5)重复步骤(1)(4)的数字帕累托点想要的。

甚至要求的解决方案线性系统,该方法是根据矩阵的顺序非常快。

推进应用程序之前,考虑一个椭球封闭在一个平行六面体的大小,,,如图5。还要考虑当地坐标系统,在椭球与起源中心,面向固定,沿semiaxes。

二次函数,表示该椭球的家庭可以写成: 的矩阵定义在图5。

可以旋转椭球周围th坐标轴;也就是说,。让,,旋转角度,,,轴,分别。每一个旋转矩阵描述了数据9(一个),9 (b),9 (c)和附录。然后,定义的通用旋转矩阵

局部坐标系可以定位在一个点相对于全局坐标系统,。在这种情况下,椭球表面上的点可以引用的全球系统

变换矩阵(18),我们分离在(31日);也就是说, 被一个正交矩阵,它的倒数等于它的转置;也就是说,。

与前面的定义,考虑下面的无约束MOOP: 与,在表中定义1,见图6(一)。

帕累托集这个问题,见图6 (b)通过应用命题3算法,= 5000。所有的点,一个普通的2 GHz的双处理器电脑3 Gb内存,运行Matlab,花费0.99秒的处理时间。

因为所有椭圆体被放置飞机周围旋转轴,在帕累托集飞机。大胆点帕累托集边界被发现同样的方法应用于功能成对。根据命题1,在这种情况下,帕累托集必然是一条曲线。

帕累托图所示6 (d)。应该注意到这方面获得了通过一个简单的解决方案的帕累托最优条件不使用任何迭代算法。

在下一个示例中与不同方向三个椭圆体,表中定义2和附录,是分布式的空间。

这个优化问题的帕累托集发现该方法描述曲面如图7(一)。帕累托前沿,在函数空间,如图7 (b)。

增加无约束MOOP函数表中定义的,3和附录,该方法在1.17秒内生成三维帕累托集如图8。

在方便定义的所有函数的问题空间;然而,命题3可以应用于二次函数中定义空间。

4所示。结论

大多数实际问题与他们的目标函数多目标被敌对的。为了解决这个问题许多研究人员正在开发方法来解决多目标优化问题而不降低单一目标。到目前为止,进化算法普遍存在一般技术找到一组候选人的最优解决方案。这些算法提供了一种离散函数空间中的帕累托前的照片,没有带来太多的决策空间的信息。

在本文的框架中,我们提出了不同的方法来确定无约束多目标优化问题的帕累托集涉及二次目标函数。提出了三种不同的过程。一个用于biobjective优化函数中定义空间,这导致帕累托集的解析解。对于三个或三个以上函数中定义空间条件测试,能够检查决策空间中的一个点是否帕累托最优。第三种方法,适用于多目标优化函数中定义空间和黑森正定,直接算法在任意有效的发现基于帕累托最优权重向量。一些说明性的例子被用来强调方法的潜力。

很显然,两个截然不同的二维函数的帕累托集是一个曲线,和三个及以上,帕累托集是一个表面上。在三维空间中两个截然不同的三维功能,帕累托集将空间曲线;三个功能,一个表面;对于以上四个功能,固体。虽然限制了方法的无约束优化,作者相信他们可以扩展到约束问题和工作。

附录

参见图9(一个),9 (b),9 (c)和表2和3。

命名法

糖尿病:	决策者
	目标函数向量
遗传算法:	遗传算法
:	th不等式约束函数
:	th等式约束函数
:	的目标函数
马:	Karush-Kuhn-Tucker
:	等式约束的功能
:	不等式约束函数
MOOP:	多目标优化问题
NSGA II:	Nondominated排序遗传算法,两个版本
:	维度的设计空间
:	函数或标准空间
:	决策变量和设计空间
:	可行域的设计空间
:	th决策变量
:	决策变量向量
:	Nondominated解决方案的多目标优化问题
:	上下边界的设计空间
:	权重因子的目标函数梯度状况马
:	向量的
:	权重因子为th不等式约束梯度状况马
:	向量的
:	权重因子为在马条件等式约束梯度
:	向量的
:	梯度算子。

利益冲突

作者宣称没有利益冲突有关的出版。

引用

1. f . y .埃奇沃思数学心理:一篇关于数学的道德科学的应用c。保罗,伦敦,英国,1881年,p . Kegan编辑。
2. 诉帕累托,手动的政治经济由a s Schiwier翻译,从法国版的1927年,奥古斯都·m·凯利出版商,纽约,纽约,美国,1971年。
3. w·施多准则优化工程和科学应用,艾德。a .德国美诺公司全体会议出版社,纽约,纽约,美国,1988年。
4. k . m .当天艳阳高照,非线性多目标优化施普林格,1998年。
5. d·戈德堡遗传算法在搜索和机器学习美国,addison - wesley,阅读,质量,1989年。
6. k . Deb,使用进化算法多目标优化目标约翰·威利& Sons,纽约,纽约,美国,2001年。视图:MathSciNet
7. r·t·马勒和j·s·Arora,”调查的多目标优化方法工程”,结构和多学科优化,26卷,不。6,369 - 395年,2004页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
8. o·b·奥古斯托·f·班尼斯,卡罗,“一种新的决策方法在多目标优化问题,“尽管Operacional,32卷,不。2、331 - 369年,2012页。视图:出版商的网站|谷歌学术搜索
9. k . Deb, s . Agrawal A Pratab, t . Meyarivan”快速精英non-dominated排序遗传算法多目标优化,“皮肤病的报告200001年,NSGA, 2000年。视图:谷歌学术搜索

版权

版权©2014年奥斯卡布里托奥古斯托等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。