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

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

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