线性-线性分式型区间系数双层规划问题的遗传算法

Genetic algorithm for solving linear-linear fractional bilevel programming problems with interval coefficients

针对一类上层为线性规划、下层为线性分式规划的区间系数双层规划问题,提出了一种基于系数取值区间搜索的遗传算法。首先,对下层目标系数进行个体编码,使得对每一编码个体,原问题被转化为确定的双层规划问题;其次,利用分式规划的最优性条件求解得到确定性问题;最后,算法通过不断进化下层目标系数找到最好最优解和最差最优解。数值仿真结果表明,该算法是可行并有效的。

For a class of bilevel programming problems with interval coefficients, in which the upper-level problem is linear, whereas the lower-level problem is a linear fractional program, a genetic algorithm was presented by taking the coefficient intervals as the searching space. Firstly, individuals could be gotten by encoding the lower-level objective coefficients such that the original problem could be transformed into certain bilevel programs for each encoded individual; in addition, the optimality results were used to solve these certain problems; finally, the best and the worst solutions could be obtained by evolving the coefficients of the lower level objective. The simulation results show that the proposed algorithm is feasible and efficient.