Abstract: For a kind of fractional bilevel programming problems with more than one linear follower, a genetic algorithm based on a new encoding scheme was proposed. Firstly, the dual theory was applied to transform the original problem to a singlelevel nonlinear programming; secondly, all individuals were encoded by considering feasible base of the follower's dual problem. For any individual given, the dual variables can be solved, which makes the nonlinear problem become a linear fractional programming; finally, the resulting linear fractional programming was resolved and the objective value was taken as the fitness of this individual. Based on the encoding scheme and fitness evaluation, the efficiency of the genetic algorithm is improved, which is also illustrated by the simulation of four examples.

Key words: Bilevel programming, genetic algorithm, fractional programming, dual theory, optimal solutions

摘要： 针对一类具有多个线性下层问题的分式双层规划， 提出一种基于新编码方式的遗传算法。 首先，利用对偶理论，将问题化为单层非线性规划；接着，利用下层对偶问题的可行基编码，针对任意编码个体，解出对偶变量值，使得单层规划变为线性分式规划；最后，求解产生的线性分式规划，其目标值作为个体的适应度值。 这种编码方式及适应度的计算有效提高了遗传算法的效率。 通过对4个算例的计算，验证了算法的有效性。

关键词: 双层规划, 遗传算法, 分式规划, 对偶理论, 最优解