计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (10): 139-143.DOI: 10.3778/j.issn.1002-8331.1512-0137

• 模式识别与人工智能 • 上一篇    下一篇

一类区间系数二次双层规划问题的遗传算法

李向东,李和成   

  1. 青海师范大学 数学系,西宁 810000
  • 出版日期:2017-05-15 发布日期:2017-05-31

Genetic algorithm for a class of quadratic bi-level programming problems with interval coefficients

LI Xiangdong, LI Hecheng   

  1. Department of Mathematics, Qinghai Normal University, Xining 810000, China
  • Online:2017-05-15 Published:2017-05-31

摘要: 针对上下层均含区间系数的二次双层规划,提出了一种基于两个适应度评估的遗传算法。将下层目标系数区间作为遗传算法的搜索空间,对于每一个确定的个体,下层问题不含区间系数;利用二次规划的最优性条件,将个体所对应的问题转化为两个确定的二次规划;利用基枚举方法求解这两个二次规划问题,相应的最优值作为个体的两个适应度。算法通过两个适应度的比较,获得问题的最好最优解和最差最优解。数值仿真结果表明,该算法是可行有效的。

关键词: 区间系数, 二次双层规划, 遗传算法, 最优性条件, 最优解

Abstract: For a class of quadratic bilevel programming problems with interval objective coefficients in the leader’s and lower’s levels, a genetic algorithm with two fitness functions is presented. Firstly, the coefficient interval of the lower’s level objective is taken as the search space of the genetic algorithm. After doing so, for each individual, the lower’s level of the resulting problem doesn’t involve interval coefficients; In addition, the optimality conditions of quadratic programming are used to further transform the resulting problem into two exact quadratic programs. Furthermore, these two quadratic programs are solved by the base-enumerating method and its optimal values are taken as two fitness values. Finally, the best and the worst optimal solutions can be obtained by comparing two fitness values of all individuals. The simulation results show that the proposed algorithm is feasible and efficient.

Key words: interval coefficients, quadratic bilevel programming, genetic algorithm, optimality condition, optimal solutions