ABSTRACT

For a class of bilevel programming problems, in which the upper-level problem is an interval coefficients fractional program, whereas the lower-level problem is linear, a genetic algorithm based on four fitness functions is presented. Firstly, four certain programs can be gotten by taking upper-lower bounds of the coefficient intervals of the upper level objective. In addition, using the characteristics of the four problems and the optimality conditions of linear programming, a genetic algorithm which takes four objective functions as evaluation is designed, and the best and the worst optimal solutions can be obtained by using the proposed algorithm. Finally, the simulation results show that the proposed algorithm is feasible and efficient.

Keywords:Interval Coefficients, Fractional Bilevel Programming, Genetic Algorithm, Optimality Condition, Optimal Solutions

一类带区间系数的分式双层规划问题的 遗传算法

郭晓芳，李向东

青海师范大学数学系，青海 西宁

Email: 13997193749@163.com

收稿日期：2015年2月7日；录用日期：2015年2月20日；发布日期：2015年2月27日

摘 要

针对上层为区间系数分式规划、下层为线性规划的一类双层规划问题，提出了一种基于四个适应度评估函数的遗传算法。首先，利用上层系数区间的上下端点将原问题转化成四个系数确定的分式双层规划问题；其次，利用四个确定问题的特征和线性规划的最优性条件设计了一个基于四个目标函数评估的遗传算法，通过该算法获得原问题的最好最优解和最差最优解。最后，数值仿真结果表明，该算法是可行有效的。

关键词 :区间系数，分式双层规划，遗传算法，最优性条件，最优解

1. 引言

双层规划是近年来规划论中比较受关注的一个研究领域。双层规划由上、下两层优化问题构成,一般的数学模型如下：

(1)

其中，是上层变量,由上层决策者控制，是下层变量，由下层决策者控制；和分别称为上层目标函数和下层目标函数；为约束域，由不等式组决定。上层问题由上层变量决定，但同时还依赖于下层问题的最优解。下层问题由下层变量决定,又以上层变量的取值为参数,即在解下层问题时把上层变量看成一个参数。

双层规划作为一个递阶决策的优化方法，在资源配置、区域规划、分级管理等实际问题中应用极为广泛。文[1] [2] 对此做了详细阐述。双层规划的算法方面，现阶段提出的有效算法有：K次最好方法、分支定界法等[3] ，并且文[4] 指出双层规划问题是非凸且NP-难的。对于线性分式规划的研究主要集中在其强对偶和弱对偶定理方面[5] 。以上问题都是在系数确定的情况下进行问题求解。然而，在大多数实际问题中，由于客观事物的复杂性和不确定性，人们往往不能明确给出信息的属性，只能给出它的一个变化范围或规律，这意味着问题的系数往往是不确定的。常见的这种系数不确定的优化问题可分为三类：模糊系数、随机系数和区间系数，考虑到隶属度函数和分布函数不易处理，因此往往转化为区间数来求解。因此，研究区间系数优化问题显得尤为重要。

在解决区间系数优化问题的方法中，可以利用区间序关系探讨有效解的KKT条件及原问题与对偶问题的关系[6] [7] 。在单目标规划问题中，基于目标函数对左右端点之间的偏好关系讨论其最优解的方法较多[8] [9] 。在多目标规划问题中，文[10] 针对含模糊系数的多目标规划问题,提出了一个两阶段计算方法。文[11] 对于右端向量为区间数的线性问题给出了目标函数的最优值情况。对于目标函数系数是区间数的双层规划问题，可见的文献很少，文 [12] 提出了一种用泰勒级数来求解线性区间系数双层规划问题的算法，而Calvete [13] 基于区间系数的左右端点提出另一种遗传算法得到了问题的最好最优解和最差最优解。

本文讨论一类上层为区间线性分式规划，下层为线性规划的双层规划。考虑到双层规划问题的非凸性，本文利用遗传算法搜索可行解，通过算法迭代获得原问题的最好最优解和最差最优解。另外为了提高算法的效率，将线性规划的最优性条件嵌入到了算法的设计中。

2 问题模型及相关概念

本文讨论上层目标函数带区间系数的双层分式规划问题，其模型如下：

(2)

其中。为叙述方便，假设上层目标函数的分母总大于零。对于任意的，记相应的双层规划为,即：

(3)

对于问题(3)，一些基本概念如下：

(1) 约束域：

(2) 在上层空间中的投影：

(3) 对于，每个下层的可行集：

(4) 下层合理反应集：

(5) 诱导域：

定义1(最优解)：在中，对任意的，若存在使得成立，则称是的最优解，也是(2)式的一个最优解。

定义2(最好最优解)：若的最优解满足：对任意(2)的最优解，有成立，则称是(2)式的一个最好最优解。

定义3(最差最优解)：若的最优解满足：对任意(2)的最优解，有成立，则称是(2)式的一个最差最优解。

因为不等式约束，可以通过增加松弛变量使其变为等式，故不失一般性，在以下讨论中将其变为。

由文[14] 的证明可知，(2)的最好最优解在上层目标中分子系数区间取左端点而分母取右端点或左端点处达到，最差最优解在上层目标的分子系数区间取右端点而分母取左端点或者右端点处达到。基于该结论，将(2)式转化为如下四个上层目标系数确定的双层优化问题：

(4)

(5)

(6)

(7)

其中通过求解(4)和(5)选择较小的解作为(2)的最好最优解，通过求解(6)和(7)选择较大的解作为(2)的最差最优解。考虑到这四个问题只有目标函数有区别，因此设计了一个具有四个适应度评估函数的遗传算法求解。

3. 算法设计

遗传算法是一种基于生物进化论和遗传学机理的概率搜索方法，它对函数的可微性没有特别要求，而且具有全局收敛性、鲁棒性，简单通用，适于并行处理等优点。因此本文采用遗传算法来求解问题(2)。

3.1. 个体编码

本文基于线性规划的最优性条件设计算法，通过考虑最优基矩阵来求解问题，因此采用约束矩阵的行标编码。表示矩阵的所有的列标，从中选择出个元素。若这个元素代表的列线性无关，即组成一个基矩阵，则这列就可作为一个个体，表示为。

3.2. 适应度评估

对任意一个个体，通过计算下列四个函数得到对个体的评估：

(8)

(9)

(10)

(11)

由于问题4~7有相同的结构，因此，仅以(4)为例给出适应度评估过程。

从(4)的下层出发，设个体，对应的基矩阵为。则下层基解的表达式为：

进一步，考虑到这个解的最优性和可行性，求解如下问题：

(12)

目标函数值为第一个函数对个体的评估。同理，可计算其它目标函数对该个体的评估值，与(12)相比，仅仅目标函数不同。算法通过比较所获得的目标函数值得到最好和最差最优解。

3.3. 杂交算子

若个体，被选择作为杂交后代，在中给定一个交叉位。把两个个体中相同的元素除去后将交叉位左边的元素互换，再将相同元素按另一个个体中的次序添加进去，得到的个体作为交叉后代。

3.4. 变异算子

给定一个正整数，从中选择个作为进基变量，根据单纯形法的最小比率原则决定中的个变量出基，从而得到变异后代。

3.5. 算法步骤

算法描述如下：

(1) 设置参数：给定种群规模，杂交概率，变异概率，最大迭代次数。

(2) 产生初始种群：按个体产生的办法随机产生规模为的初始种群，置。

(3) 适应度评估及检验：用给出适应度评估方法评估种群中的每个个体，每个个体有四个适应度值；

(4) 杂交：按给定杂交方式进行杂交，杂交后代集合记为；

(5) 变异：按给定变异方式进行变异，变异后代集合记为；

(6) 选择：从的个体中，根据四个适应度函数分别选择最小的个个体组成下一代种群；

(7) 终止或循环：若迭代次数等于最大迭代次数，则停止迭代，分别输出四个适应度最小的点。这四个解中适应度值最小的为最好最优解，最大的为最差最优解；否则，令，转(4)。

4. 算例

由于区间系数分式双层规划的例子在文献中极为少见，因此，在文[15] 中选择如下算例：

(13)

该问题的最优值是0.615，对应的最优解为：。把最优解带入下层目标函数的分母中将其变为常数且将上层目标函数的所有系数上下浮动两个单位产生一个区间，将问题变为如下的上层函数为区间分式规划而下层函数是线性规划的双层分式规划：

(14)

四个相应的目标函数为：

不难看出，该问题的最好最优值应该不大于0.615。算法中的相关参数取值如下：，，，在CPU2.40 GHz，内存为4 GB的笔记本电脑上，利用提出的遗传算法求解这个例子，独立运行10次，结果如表1：

表1中最好计算结果指的是10次运行中相应目标值的最好情况和平均值，最后一行为比较后的最好最优解和最差最优解。从表1中的数据可以看出文[15] 中的最优解介于本文得到的最好最优解与最差最优解之间。

5. 结束语

针对一类上层为线性分式区间规划，下层是线性规划的分式双层规划问题，基于上层系数区间端点和线性规划最优性条件，提出了基于四个适应度函数评估的遗传算法。该算法的特点是利用了带区间系

表1. 算法计算结果

数的分式函数值在区间端点处达到的特点，避免了区间内部点的搜索，节约了计算量。

文章引用

郭晓芳,李向东, (2015) 一类带区间系数的分式双层规划问题的遗传算法
A Genetic Algorithm for a Class of Fractional Bilevel Programming Problems with Interval Coefficients. 应用数学进展,01,63-69. doi: 10.12677/AAM.2015.41008

参考文献 (References)