求解双层规划的多目标布谷鸟算法

Multi-objective Cuckoo Search Algorithm for Bi-level Programming Problems

双层规划是一类具有主从递阶结构的优化问题,属于NP-hard范畴。本文利用KKT条件将双层规划问题转化为等价的单层约束规划问题,通过约束处理技术进一步转化为带偏好双目标无约束优化问题,提出多目标布谷鸟算法求解策略。该算法采用Pareto支配和ε-个体比较准则,充分利用种群中优秀不可行解的信息指导搜索过程;设置外部档案集存储迭代过程中的优秀个体并通过高斯扰动改善外部档案集的质量,周期性替换群体中的劣势个体,引导种群不断向可行域或最优解逼近。数值实验及其参数分析验证了算法的有效性。

The bi-level programming problem （BLPP）addresses an optimization problem with leader-follower hier-archical？ structure, an NP-hard problem in the strong sense. The BLPP is reformulated into an equivalent sin-gle-level constrained optimization problem by using the KKT conditions associated to the lower-level problem.Further, the derived problem is transformed into a bi-objective optimization problem by a constraints handlingscheme, i. e. , introducing a new objective of minimizing constraints violation. For the resolution, a multi-objective cuckoo search algorithm is proposed. In the algorithm, the Pareto dominance and ε-comparison rule areadopted in purpose of exploiting the information of in-feasible solutions to efficiently guide the search process.Additionally, an archive is used to store better-performing candidate and a Gaussian mutation is applied on it inorder to search promising solutions. Then, some worstest individuals are periodically substituted by the archive.The computational experiments and parameter analysis claim the effectiveness of the proposed algorithm.