Advances in Applied Mathematics
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

Copyright © 2016 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

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

一类区间系数非线性优化问题的遗传算法

李向东

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

收稿日期:2016年2月2日;录用日期:2016年2月20日;发布日期:2016年2月26日

摘 要

本文针对一类带区间系数的非线性优化问题,提出了一种基于均匀搜索的遗传算法。首先,将原问题分解为两个确定的双层规划问题;其次,对两个双层问题的上层变量进行编码,通过求解相应的双层规划获得对个体的评估;最后,为避免近亲繁殖产生相似后代,采用相对距离控制杂交运算;并且引进摆动式正交杂交算子产生后代个体,使后代尽可能均匀产生。数据仿真结果表明,该算法是可行有效的。

关键词 :区间系数,非线性规划,遗传算法,正交设计

1. 引言

随着优化理论知识的不断完善,越来越多的人投入到优化问题的研究当中。目前,常见的优化问题有:线性规划,非线性规划,目标规划,动态规划等,都是用确定型的数学模型去描述实际问题中的所有信息,我们将这一类优化问题称为确定优化问题。而在现实生活中,大部分问题由于一些不确定因素(如:环境变化,预算变动或者技术改革等)的存在,使得对应问题成为不确定问题,根据不确定参数的种类,常见的不确定优化问题可分为:随机规划问题、模糊规划问题和区间规划问题等三类。其中,随机规划问题是指已知随机变量分布函数且所含不确定参数类型为随机变量的优化问题,模糊规划问题是指已知隶属度函数且所含不确定参数类型为模糊数的优化问题。然而,在实际问题中,随机变量的分布函数和模糊数的隶属度函数的获取是很困难的。因此,通过解决上述两种问题来处理实际问题具有很大的局限性。区间规划问题是指优化问题所含的不确定参数是区间,且已知该参数区间的上下界或者中点值和半径。区间规划问题中的参数相对比较容易获取,而且随机变量和模糊数都可以通过一定方法转化为区间,从而随机规划和模糊规划问题均可以转化为区间规划问题。因此,不确定区间优化方法被更多的应用于解决实际问题当中,如铁路空车调配问题[1] ,飞机机翼设计问题 [2] ,最大化盈利问题 [3] ,以及汽油调和优化问题 [4] 等,所以,研究区间参数优化问题具有重要的实际应用价值。

区间规划方法作为一种更切合实际的数学规划,越来越多的人开始对其进行研究。针对区间规划所讨论问题的类型,通常分为以下几种:区间系数线性规划 [5] 、区间系数非线性规划 [6] 、区间系数多目标优化 [7] 和区间系数双层规划问题 [8] 等。一般采用定义新的区间序关系,通过该序关系给出问题的最优值区域或将问题转化为一个或多个确定性问题求解两大类。针对区间线性规划问题,郭均鹏等 [9] 提出了一种基于决策者满意度的区间排序关系,把区间不等式约束转化为确定型约束的求解方法。文献 [10] 基于可行性测试和压缩技术给出了一种求解区间线性规划问题的方法。对于区间系数非线性问题,蒋峥等 [11] 提出一种采用递阶优化方式求解区间参数不确定非线性规划的算法。文献 [12] 通过应用对偶定理和变量代换技术提出了一种解决区间二次规划的数值求解方法。对于区间多目标规划问题,巩敦卫等 [13] 通过定义区间序关系和拥挤距离来反映最优解质量和最优解分布情况,并基于排序关系和拥挤距离选择最优解。文献 [14] 提出一种基于区间权重解决多目标模糊规划问题的方法。对于区间系数双层规划问题,Calvete提出了一种基于极点排序技术求解区间系数线性双层规划的方法。由于问题本身的难度,目前给出的有效算法很少文,且主要针对线性规划问题。

本文讨论了一类带区间系数非线性规划问题,文中首先将目标区间系数进行编码,每一组系数取值作为一个个体。然后,将原问题转化为两个双层子问题。求解过程中本文使用正交设计矩阵产生均匀分布的初始种群,并采用随机抽取的方式进行杂交和变异操作,在杂交过程中,使用正交杂交算子 [15] 产生后代个体,并对每一个后代进行选择性单点摆动来保证个体的差异性,变异算子采用改进的随机变异,通过以上操作使得最终产生的后代个体尽可能均匀分布。最后,运用传统优化方法通过搜索目标系数区间求解得到两个目标值,并将这两个目标值作为遗传算法的个体适应度。算法通过比较个体的适应度,在一次的运算中同时获得问题的最优值区间上界和下界。

2. 问题模型及转化

本文讨论带区间系数的非线性优化问题,数学模型如下:

(1)

其中,维区间向量参数,分别为区间的上下界标号,为约束条件,问题(1)的目标函数值为区间。

首先,将原问题转化为如下

(2)

(3)

两个双层规划问题。

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

(4)

但这样我们需要设计两个算法求解最好最优解和最差最优解。为了避免这个问题,我们保留(2)的形式。利用(2)和(3)只差上层目标优化方向的区别,设计统一的算法。

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

3. 算法设计

3.1. 个体编码

采用遗传算法搜索目标系数区间,因此,每一组系数的取值作为种群的个体。令个体,其中

3.2. 适应度评估

对任意一个个体,通过计算(2)和(3)的下层问题获得适应度评估,即计算如下非线性规划问题:

(5)

算法通过比较所获得的目标函数值得到最优值的上界和下界。

3.3. 杂交算子

对于大部分杂交算子,若两个个体各分量都相近,杂交所产生的后代个体与父代个体依然相似,这样的近亲繁殖将导致获得的解不变,搜索速度变慢。为防止此类情况发生,本文采用计算相对距离的方法来克服近亲繁殖问题。

对任意两个个体,定义两者之间的相对距离公式为:

显然,越小,两个个体的相似度越大,反之,相似度越小。通过设定相对距离的大小来确定两个个体是否杂交。本文的相对距离表示为,即两个个体的相对距离大于是进行杂交的必要条件。若两个个体符合杂交条件,则采用离散化正交杂交算子进行杂交,具体操作如下:

为任意两个父代个体,它们定义的空间记为,其中,

离散化每个区间为Q个水平,使得任何两个连续水平之间的距离相同。如:把第维的区间离散化成,其中,

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

在离散化之后,本文采用正交设计选择一个小的但具有代表性的样本来作为后代备选集,然后在该集合中选择最好的点作为杂交后代。

由于父代个体是随机选取,若相同父代个体被重复选取,则导致后代个体相同。本文在杂交之前进行预处理,采用个体各分量选择性摆动克服该问题,即使在父代相同的情况下依然会产生不同的后代个体,具体方法如下:

首先,对两个父代个体各产生一个之间的随机数,若大于预先设定的阈值,则对相应个体各个分量进行摆动操作:

其中,之间的随机数,为一个小正数。在上式中,以相同的概率执行加减运算,若超过边界,则取边界值。

其次,用得到的代替,完成对各个分量的摆动。

3.4. 变异算子

对参加变异的父代个体进行变异,后代个体的分量按如下方式产生:随机产生一个0或者1,取

其中之间的随机数,T为最大运行代数,g为代数。

3.5. 算法步骤

算法步骤如下:

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

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

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

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

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

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

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

该算法的显著特点是对解区间进行尽可能均匀地搜索,且问题的最优值的上下界在一次算法运行中同时获得,从而提高了求解效率。

4. 算例

由于区间系数非线性规划问题算例极少,本文通过对现有确定系数算例 [16] 扰动系数,构造成新的算例。由于没有改变函数结构,同时,目标系数变成了区间,因此计算难度比原问题更大。

例:

该问题的最优值是−4.50。

Table 1. The optimal results

表1. 最优计算结果

Table 2. The worst result

表2. 最差计算结果

将目标个别系数上下浮动一个单位,则问题变为如下区间系数的情形:

可见原问题的最优值应介于对应区间系数问题最优解区间之间。

在CPU2.6 GHZ,内存为4 GB的笔记本电脑上,利用提出的遗传算法求解该算例。算法的相关参数取值如下:

对每个问题,运行提出的遗传算法30次,记录问题的最好最优值和最差最优值及相应参数c的值。计算结果见表1表2。其中表1给出了最好最优值的计算结果(最好值,平均值和最差值)以及最好值对应的c和x值;表2给出了最差最优值的计算结果以及对应的c和x值。

从计算结果来看,本次运算所获得的最优值区间包含原问题的最优值,因此算法运算是有效的。

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

参考文献 (References)

  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.

期刊菜单