An Efficient and Accurate Solution Methodology for Bilevel Multi-Objective Programming Problems Using a Hybrid Evolutionary-Local-Search Algorithm
An Efficient and Accurate Solution Methodology for Bilevel Multi-Objective Programming Problems Using a Hybrid Evolutionary-Local-Search Algorithm
复制标题
DOI：
10.1162/evco_a_00015
复制
发表时间：
2010-09-01
影响因子：
6.8
通讯作者：
Sinha, Ankur
中科院分区：
文献类型：
--
作者：
Deb, Kalyanmoy;Sinha, Ankur
双层优化问题涉及两个优化任务（上层和下层），其中上层的每个可行解必须对应于下层优化问题的最优解。这些问题通常出现在许多实际问题解决任务中，包括最优控制，过程优化，游戏策略开发，运输问题等。然而，它们通常被转换成一个单一的水平优化问题，通过使用近似的解决方案的过程，以取代较低的水平优化任务。虽然存在一些涉及单目标双层规划问题的理论，数值和进化优化研究，但没有多少研究着眼于双层规划问题的每个级别中的多个冲突目标的上下文。在本文中，我们解决了一些复杂的问题，解决多目标双层规划问题，提出了具有挑战性的测试问题，并提出了一个可行的和混合的进化与本地搜索为基础的算法作为解决方法。混合方法比现有的方法和规模以及40个变量的困难的测试问题，在这项研究中使用。群体大小和终止标准是自适应的，因此用户不需要提供额外的参数。这项研究表明，一个明确的生态位的进化算法在解决这些困难的问题，具有实际意义相比，他们通常的解决方案，由一个计算昂贵的嵌套程序。这项研究开辟了许多问题的多目标双层规划，希望这项研究将激励EMO和其他研究人员更加关注这一重要和困难的问题解决活动。
Bilevel optimization problems involve two optimization tasks (upper and lower level), in which every feasible upper level solution must correspond to an optimal solution to a lower level optimization problem. These problems commonly appear in many practical problem solving tasks including optimal control, process optimization, game-playing strategy developments, transportation problems, and others. However, they are commonly converted into a single level optimization problem by using an approximate solution procedure to replace the lower level optimization task. Although there exist a number of theoretical, numerical, and evolutionary optimization studies involving single-objective bilevel programming problems, not many studies look at the context of multiple conflicting objectives in each level of a bilevel programming problem. In this paper, we address certain intricate issues related to solving multi-objective bilevel programming problems, present challenging test problems, and propose a viable and hybrid evolutionary-cum-local-search based algorithm as a solution methodology. The hybrid approach performs better than a number of existing methodologies and scales well up to 40-variable difficult test problems used in this study. The population sizing and termination criteria are made self-adaptive, so that no additional parameters need to be supplied by the user. The study indicates a clear niche of evolutionary algorithms in solving such difficult problems of practical importance compared to their usual solution by a computationally expensive nested procedure. The study opens up many issues related to multi-objective bilevel programming and hopefully this study will motivate EMO and other researchers to pay more attention to this important and difficult problem solving activity.