摘要
非线性双层规划问题是一类递阶优化问题,相关的算法往往需要对每一个上层变量值求一个下层优化问题才能得到一个可行点,这使得算法的计算量很大.目前文献中的算法通常都是基于对每个确定的上层变量,下层最优解唯一的条件,这就意味着每个下层变量的分量都可以看成是上层变量的函数.基于这个思想,同时为了避免频繁计算下层优化问题,文中提出了一种新的方法.这种方法与已有方法的主要不同之处在于,它不需频繁求解下层规划,而是用插值函数近似下层最优解函数.其主要思想如下:首先,取一些上层变量值作为插值节点,计算它们对应的下层问题的最优解,这些最优解的第i个分量作为第i个插值函数的函数值,利用这些节点和函数值计算插值函数;其次,将插值函数代入上层问题,得到一个近似原问题的单层规划;最后用一个新的遗传算法求解该单层规划.由于插值节点和相应的插值函数在进化过程中自适应修正和更新,这样可使得该单层规划问题的最优解逐步逼近原问题的最优解,并且可减少计算量.对25个测试问题的仿真结果表明,该文所提出的算法能以较少的计算量找到这些问题的最好解.
Nonlinear bilevel programming problems are hierarchical optimization problems. For each fixed value of leader＇s variables the existing algorithms are required to solve the follower＇s optimization problem to obtain a feasible point for the whole problem, which results in a large amount of computation. Note that in the existing research works, the condition that the follower＇s optimal solution is unique for each leader＇s variable value is usually adopted. This condition means that each follower＇s variable can be seen as a function of the leader＇s variables although this function is unknown. Based on this observation and to avoid solving the follower＇s problem frequently, a different skill from that of the existing works is used to tackle this difficulty, i. e. , the interpolation functions are adopted to approximate these unknown functions. First, the values of the interpolation function are gotten by solving the follower＇s problem for some given leader＇s variable values （i. e. , the interpolation points）, and the interpolation polynomials （functions） are calculated by using these interpolation points. Then, the follower＇s variables can be replaced by the corresponding interpolation polynomials in the leader＇s problem. As a result, the original nonlinear bilevel programming can be approximated by a single-level programming.Finally, a specifically designed genetic algorithm is proposed for the single-level programming, and the interpolation points and the corresponding interpolation functions are adaptively modified and updated during the evolution so that the optimal solutions of the single-level programming can well approach to those of original nonlinear bilevel programming. Moreover, the computation amount will be decreased. The simulations on 25 can find the best solutions test problems indicate the proposed algorithm a relatively small amount of computation for these test problems
出处
《计算机学报》
EI
CSCD
北大核心
2008年第6期910-918,共9页
Chinese Journal of Computers
基金
国家自然科学基金(60374063)资助~~
关键词
非线性双层规划
插值函数
遗传算法
最优解
nonlinear bilevel programming
interpolation polynomials
genetic algorithm
optimal solutions
