权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

A study on efficient algorithms for multiple objective optimization prob-lems

多目标优化问题的高效算法研究

基本信息

批准号：
09680413
负责人：
KUNO Takahito
金额：
$ 1.41万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 1998
项目状态：
已结题

项目摘要

In this research. we formulated some classes of multiple objective optimization problems into single objective nonconvex optimization problems and proposed efficient algorithms for generating globally optimal solutions to the resulting problems. A few of the results are listed below :1 We studied a problem constraining the product of two objectives to be less than or equal to a given constant. We developed an algorithm for generating a globally optimal solution within a finite time. The computational results on a workstation indicated that the algorithm is reasonably practical as long as the number of constraints containing the product is less than five.2 We developed a branch-and-bound algorithm to resolve a multi-objective optimization with a 0-1 knapsack constraint. We incorporated a Lagrangian relaxation into the bounding procedure ; but the time taken for bounding is only a lower-order polynomial in the problem size. The algorithm succeeded in solving problems of 20 objectives and … More 120 variables within 20 seconds.3 We investigated the relationship between the multi-objective optimization with a 0-1 knapsack constraint and a production-transportation problem with concave production costs. We then extended the algorithm for the former to the latter network problem. The computational time needed by the algorithm was a few hundreds times less than those by the existing algorithms.4 We studied a bi-objective shortest path problem and developed two strongly polynomial algo- rithms. One is for the case that the utility function of the decision maker is quasi-concave ; and the other is for the case that the utility function is quasi-convex. We showed that both algorithms are directly applicable to in-car navigation systems and so forth.All the above mentioned problems have highly nonconvex but low-rank structures. We showed that, even though the problems belong to a well-known hard class, it is possible to design efficient algorithms both in theoretical and practical senses, by exploiting their special structures. Less

在这项研究中。我们将某些类别的多目标优化问题转化为单目标非凸优化问题，并提出了生成所得到的问题的全局最优解的有效算法。下面列出了一些结果：1我们研究了一个问题，限制两个目标的产品小于或等于一个给定的常数。我们开发了一种算法，用于在有限时间内生成全局最优解。在工作站上的计算结果表明，该算法是合理的实用，只要包含产品的约束的数量小于5。2我们开发了一个分支定界算法来解决多目标优化与0-1背包约束。我们在定界过程中加入了拉格朗日松弛，但定界所需的时间仅是问题大小的低阶多项式。该算法成功地解决了20个目标的问题， ...更多信息 20秒内120个变量。3我们研究了0-1背包约束的多目标优化与凹生产成本的生产运输问题之间的关系。然后，我们将前者的算法扩展到后者的网络问题。该算法所需的计算时间是现有算法的几百倍。4我们研究了一个双目标最短路问题，并提出了两个强多项式算法。一种是针对决策者的效用函数是拟凹的情况，另一种是针对效用函数是拟凸的情况。我们证明了这两种算法都可以直接应用于车载导航系统等问题。上述问题都具有高度非凸的低秩结构。我们表明，即使问题属于一个众所周知的硬类，它是可能的设计有效的算法在理论和实践意义上，通过利用其特殊的结构。少