﻿ 一类带区间系数的分式双层规划问题的遗传算法 A Genetic Algorithm for a Class of Fractional Bilevel Programming Problems with Interval Coefficients

Advances in Applied Mathematics
Vol.04 No.01(2015), Article ID:14883,6 pages
10.12677/AAM.2015.41008

A Genetic Algorithm for a Class of Fractional Bilevel Programming Problems with Interval Coefficients

Xiaofang Guo, Xiangdong Li

Department of Mathematics, Qinghai Normal University, Xining Qinghai

Email: 13997193749@163.com

Received: Feb. 7th, 2015; accepted: Feb. 20th, 2015; published: Feb. 27th, 2015

Copyright © 2015 by authors and Hans Publishers Inc.

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

1. 引言

(1)

2 问题模型及相关概念

(2)

(3)

(1) 约束域：

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

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

(4) 下层合理反应集：

(5) 诱导域：

(4)

(5)

(6)

(7)

3. 算法设计

3.1. 个体编码

3.2. 适应度评估

(8)

(9)

(10)

(11)

(12)

3.3. 杂交算子

3.4. 变异算子

3.5. 算法步骤

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

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

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

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

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

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

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

4. 算例

(13)

(14)

5. 结束语

Table 1. Result of algorithm

A Genetic Algorithm for a Class of Fractional Bilevel Programming Problems with Interval Coefficients. 应用数学进展,01,63-69. doi: 10.12677/AAM.2015.41008

1. 1. Miller, T., Friesz, T. and Robin, R. (1992) Heuristic algorithms for delivered price spatially competitive network facility location problem. Annals of Operations Research, 34, 177-202.

2. 2. 高自友, 张好智, 孙会君 (2004) 城市交通网络问题中双层规划模型方法及应用. 交通运输信息工程, 4, 440- 445.

3. 3. Calvete, H.I. (2012) The bilevel linear fractional programming fractional programming problem. European Journal of Operational Research, 114, 188-197.

4. 4. Bard, J.F. (2009) Computational difficulties of bilevel linear programming. Encyclopedia of Optimization, 12, 225-228.

5. 5. Yang, X.M. (1996) Duality for generalized ninlinear fractional programs. Mathematics in Practice and Theory, 3, 122- 128.

6. 6. Effati, S. (2012) Solving the interval valued linear fractional programming problem. American Journal of Computational Mathematics, 12, 51-55.

7. 7. Heien, C.W. (2000) On interval valued nonlinear programming problem. Math Operation Research, 10, 134-145.

8. 8. Masahiro, I.L. (1991) Goal programming problems with interval coefficients and target intervals. European Journal of Operational Research, 3, 345-360.

9. 9. Stesan, H.J. (1996) Multiobjective programming in optimization of interval objective functions. European Journal of Operational Research, 3, 594-598.

10. 10. Feyzan, J.D. (2007) A two-phase approach for multiobjective programming problems with fuzzy coefficients. Information Science, 23, 511-520.

11. 11. Chinneck, J.W. and Ramadan, K. (2000) Linear programming with interval coefficients. Journal of Operational Research Society, 5, 209-220.

12. 12. Kocken, H.G., Emiroğlu, İ., Güler, C., Taşçı, F. and Sivri, M. (2013) The fractional transportation problem with interval demand supply and costs. Proceedings of International Conference on Mathematical Sciences and Statistics, 1557, 339-344.

13. 13. Calvete, H.I. and Herminia, I. (2012) Linear bilevel programming with interval coefficient. Journal of Computational and Applied Mathematics, 2, 100-113.

14. 14. Hladík, M. (2010) Generalized linear fractional programming under interval uncertainty. European Journal of Operational Research, 2, 242-246.

15. 15. Calvete, H.I., Galé, C. and Mateo, P.M. (2009) A genetia algorithm for solving linear fractional bilevel problems. Annals of Operations Research, 166, 39-56.