计算机应用 ›› 2014, Vol. 34 ›› Issue (1): 185-188.DOI: 10.11772/j.issn.1001-9081.2014.01.0185

• 人工智能 • 上一篇    下一篇

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

樊扬扬,李和成   

  1. 青海师范大学 数学系,西宁 810008
  • 收稿日期:2013-07-03 修回日期:2013-09-07 出版日期:2014-01-01 发布日期:2014-02-14
  • 通讯作者: 樊扬扬
  • 作者简介:樊扬扬(1988-),女,山东菏泽人,硕士研究生,主要研究方向:最优化、进化算法;李和成(1973-),男,青海乐都人,教授,博士,主要研究方向:最优化、进化计算、供应链模型。
  • 基金资助:

    国家自然科学基金资助项目;青海省自然科学基金项目

Genetic algorithm for solving linear bilevel programming with interval coefficients

FAN Yangyang,LI Hecheng   

  1. Department of Mathematics, Qinghai Normal University, Xining Qinghai 810008, China
  • Received:2013-07-03 Revised:2013-09-07 Online:2014-01-01 Published:2014-02-14
  • Contact: FAN Yangyang

摘要: 针对一类上层目标函数带区间系数的线性双层规划问题,提出了一种基于双适应度函数评估的遗传算法(GA)。该算法的特点是在一次运算中同时获得最好最优解和最差最优解。首先,利用双层规划约束域的顶点进行个体编码,以上层目标函数中系数的上下端点构造两个适应度函数;其次,利用适应度函数排序种群中的个体,并按从好到差的次序验证个体的下层最优性,直到找到一个可行个体;最后,在算法运行中更新找到的可行个体。通过对4个算例的仿真实验,表明算法是可行且有效的。

关键词: 线性双层规划, 遗传算法, 区间系数, 最优解, 最优值

Abstract: For a kind of linear bi-level programming problems with interval coefficients in the upper level objective, a Genetic Algorithm (GA) was proposed by using a double fitness function evaluation technique, which was characterized by simultaneously obtaining the best optimal solution as well as the worst one in one run of the genetic algorithm. Firstly, individuals were encoded by using the vertices of the constraint region, and a double fitness was constructed by the upper and lower bounds of the upper level objective coefficients. Secondly, fitness functions were used to sort all individuals in populations. According to the order, the feasibility of individual was checked one by one until a feasible individual was found. Finally, the feasible individual was updated in executing algorithm. The simulation results on four computational examples show that the proposed algorithm is feasible and efficient.

Key words: linear bilevel programming, Genetic Algorithm (GA), interval coefficient, optimal solution, optimal value

中图分类号: