﻿ 一类区间系数非线性优化问题的遗传算法 A Genetic Algorithm for a Class of Nonlinear Optimization Problems with Interval Coefficients

Vol.05 No.01(2016), Article ID:17016,7 pages
10.12677/AAM.2016.51017

A Genetic Algorithm for a Class of Nonlinear Optimization Problems with Interval Coefficients

Xiangdong Li

Department of mathematics, Qinghai Normal University, Xining Qinghai

Received: Feb. 2nd, 2016; accepted: Feb. 20th, 2016; published: Feb. 26th, 2016

ABSTRACT

For a class of nonlinear programming problems with interval coefficients, a genetic algorithm based on a uniformly searching scheme is proposed in this paper. Firstly, the original problem is transformed into two exact bilevel programs. Secondly, the upper level variables are encoded as individuals, and these individuals are evaluated by solving the bilevel programs. Finally, in order to avoid producing similar offspring by inbreeding, a relative distance is adopted to provide a threshold value for crossover. Also, an orthogonal crossover operator with point oscillating is provided to generate offspring as uniformly as possible. The experimental data indicate that this algorithm is feasible and effective.

Keywords:Interval Coefficients, Nonlinear Programming Problem, Genetic Algorithm, Orthogonal Design

1. 引言

2. 问题模型及转化

(1)

(2)

(3)

(2)可进一步写成如下单层规划：

(4)

(2)和(3)是双层规划问题，一般来讲是非凸不可微的，为了有效求解这个问题，我们采用遗传算法框架求解。利用上层变量c的取值区间作为搜索空间，求解下层，获得对应的目标值。通过比较目标值获得最好和最差最优解。

3. 算法设计

3.1. 个体编码

3.2. 适应度评估

(5)

3.3. 杂交算子

。随着种群的进化和改进，个体趋于一致，两个父代个体定义的区间越来越小。由于Q是固定的，离散化的点越来越近，因此，可以得到越来越多精确的结果。

3.4. 变异算子

3.5. 算法步骤

1) 初始化：设置种群规模，杂交概率，变异概率及算法最大运行代数

2) 运用正交设计矩阵在系数区间内均匀产生个个体，得到初始种群，记为，令

3) 对每个个体进行适应度评估；

4) 对中的个体通过相对距离的判定进行杂交，后代集记为

5) 对中的个体按变异概率进行变异，变异后代集合记为

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

7) 若迭代次数达到，则停止迭代，输出适应度最大和最小的个体。否则，令，转4)。

4. 算例

Table 1. The optimal results

Table 2. The worst result

5. 结束语

A Genetic Algorithm for a Class of Nonlinear Optimization Problems with Interval Coefficients[J]. 应用数学进展, 2016, 05(01): 124-130. http://dx.doi.org/10.12677/AAM.2016.51017

1. 1. 曲思源. 铁路空车调配问题的区间线性规划模型及算法[J]. 华东交通大学学报, 2015, 32(3): 6-11.

2. 2. Majumder, L. and Rao, S.S. (2009) Interval-Based Optimization of Aircraft Wings under Landing Loads. Computers and Structures, 87, 225-235. http://dx.doi.org/10.1016/j.compstruc.2008.10.005

3. 3. Liu, S.T. (2009) Using Geometric Programming to Profit Maximization with Interval Coefficients and Quantity Discount. Applied Mathematics and Computation, 209, 259-265. http://dx.doi.org/10.1016/j.amc.2008.12.035

4. 4. 蒋峥. 区间参数不确定系统优化方法及其在汽油调和中的应用研究[D]: [博士学位论文]. 杭州: 浙江大学, 2005.

5. 5. Duprajitno, H. (2010) Linear Programming with Interval Arithmetic. International Journal of Contemporary Mathematical Sciences, 5, 323-332.

6. 6. Jiang, C., Han, X., Liu, G.R. and Liu, G.P. (2008) A Nonlinear Interval Number Programming Method for Uncertain Optimization Problems. European Journal of Operational Research, 188, 1-13. http://dx.doi.org/10.1016/j.ejor.2007.03.031

7. 7. Oliveira, C. and Antanes, C.H. (2007) Multiple Objective Linear Programming Models with Interval Coefficients—A Illustrated Overview. European Journal of Operational Research, 181, 1434-1463. http://dx.doi.org/10.1016/j.ejor.2005.12.042

8. 8. Calvete, H.I. and Cale, C. (2012) Linear Bilevel Programming with Interval Coefficients. Journal of Computational and Applied Mathematics, 236, 3751-3762. http://dx.doi.org/10.1016/j.cam.2011.10.012

9. 9. 郭均鹏, 吴育华. 区间线性规划的标准型及其求解[J]. 系统工程, 2003(3): 79-82.

10. 10. Huang, G.H. and Cao, M.F. (2011) Analysis of Solution Methods for Interval Programming. Journal of Environmental Informatics, 17, 54-64. http://dx.doi.org/10.3808/jei.201100187

11. 11. 蒋峥, 戴连奎, 吴铁军. 区间非线性规划问题的确定化描述及其递阶求解[J]. 系统工程理论与实践, 2005(1): 110-116.

12. 12. Liu, S.T. and Wang, R.T. (2007) A Numerical Solution Method to Interval Quadratic Programming. Applied Mathematics and Computation, 189, 1274-1281. http://dx.doi.org/10.1016/j.amc.2006.12.007

13. 13. Gong, D.W., Qin, N.N. and Sun, X.Y. (2010) Evolutionary Algorithms for Multi-Objective Optimization Problems with Interval Parameters. IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), Changsha, 23-26 September 2010, 411-420. http://dx.doi.org/10.1109/bicta.2010.5645160

14. 14. Sen, S. and Pal, B.B. (2013) Interval Goal Pro-gramming Approach to Multiobjective Fuzzy Goal Programming with Interval Weights. Procedia Technology, 10, 587-595. http://dx.doi.org/10.1016/j.protcy.2013.12.399

15. 15. 王宇平. 进化计算的理论和方法[M]. 北京: 科学出版社, 2011.

16. 16. 刁在筠, 刘桂真, 宿洁, 马建华. 运筹学[M]. 北京: 高等教育出版社, 2007.