资源描述：
《用遗传算法求解病态线性方程组_黄松奇》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第33卷第8期数学的实践与认识Vol.33No.82003年8月MATHEMATICSINPRACTICEANDTHEORYAugust,2003用遗传算法求解病态线性方程组1,21黄松奇,黄守佳(1.郑州轻工业学院信息与计算科学系,郑州450002)(2.清华大学数学科学系,北京100084)摘要:众所周知,病态方程组的条件数较大,当输入数据有微小扰动或计算过程中的舍入误差都可能引起输出数据的很大扰动,使得解严重失真,因此求解此类方程组是相当困难的.本文尝试使用遗传算法来求解病态线性方程组,得到了较好的结果,并与传统的求解方法作了简单的比较.关键词:病态方程
2、组;遗传算法1引言在图象处理、解卷积、模型参数估计等许多领域都需要求解病态线性方程组,但是由于病态方程组的条件数较大,输入数据有微小扰动或计算过程中的舍入误差都可能引起输出数据的很大扰动,即问题的解很不稳定,因此求解此类方程组是相当困难的.遗传算法(GeneticAlgorithm)是美国密执根大学Holland教授倡导发展起来的,是一种基于生物进化的机制和原理并引用随机理论的全局优化搜索方法.近年来遗传算法(GA)以其高效、实用等特点在各领域中得到了广泛的应用,并越来越受到重视.2基本遗传算法描述遗传算法是一种基于生物进化过程的组合优化方法,其基本思想是:随
3、着时间的更替,只有最适合的物种才得以进化.遗传算法利用全局搜索技术,通过对决策空间的一个集合施行选择、交叉、变异等一系列遗传操作产生一个新的集合,通过循环操作,不断产生新集合,并使得新的集合包含接近最优解的编码.遗传算法在求解优化问题时,需要定义一个适应度函数,并把待求解问题的可行解编码为由一个编码串表示的个体,使得适应度最大的个体对应于待求解问题的最优解,这样只要找到了适应度最大的个体,也就得到了问题的最优解.2.1适应度函数的设计在遗传算法中,以个体的适应度的大小来确定个体被遗传到下一代群体中的概率.个体的适应度是由适应度函数来计算的,因此为了正确地计算不
4、同情况下各个个体的遗传概率,要求所有个体的适应度必须非负,同时还要保证适应度最大的个体对应于优化问题的最优解.2.2编码遗传算法并不直接对可行解进行运算,而是以可行解的某种编码为运算对象,通过对这些编码个体进行选择、交叉、变异等遗传操作,不断产生更优的编码个体,达到优化的目的.收稿日期:2003-03-0898数学的实践与认识33卷2.3构造遗传算子遗传算子主要由选择算子、交叉算子和变异算子构成.1)选择算子选择算子的作用是从当前代中选择出一些比较优良的个体并将其复制到下一代群体中.比例算子是最常用的选择算子.比例选择就是按照每个个体的适应度在全部个体的适应度
5、之和中所占的比例来决定各个个体被遗传到下一代中的概率.2)交叉算子交叉算子的作用是通过按照某种方式交换两个个体的部分编码,而形成两个新个体.单点交叉算子是最常用的交叉算子.3)变异算子变异算子就是将个体编码串中某些编码位上的值用其它值替换而形成一个新个体.基本位变异算子是最常用的变异算子.变异算子的作用是通过随机改变个体中某些编码位的值,达到改善群体多样性的目的.3遗传算法求解线性方程组考虑如下形式的线性方程组:AX=b其中A为n阶非奇异方阵,X和b为n维向量要使用遗传算法来求解此方程组,首先要把上述问题转化为一个函数优化问题,为此构造如下的优化问题:nmin
6、f(X)=‖AX-b‖∞,X∈R***易见f(X)=0ZAX=b,即X是方程组AX=b的解构造适应度函数1nF(X)=,X∈R1+f(X)显然F(X)>0,且当f(X)=0时F(X)的值最大1)按比例选择算子计算各个个体被遗传到下一代群体中的概率.2)基于实数编码方式我们选择均匀算术交叉算子,其具体执行过程是:对群体中的个体进行两两随机配对,依设定的交叉概率pc,对每一对相互配对的个体XA,XB依下式进行算术交叉,产生两个新个体XC=AXB+(1-A)XA(1)XD=AXA+(1-A)XB其中A是一参数由于适应度越大的个体越接近于最优解,所以可以认为最优个体应
7、当在适应度大的个体的附近,对于均匀交叉算子(1)式,当A取固定值时,显然不能反映上述特点,为此,令F(XA)A=(2)F(XA)+F(XB)不妨设F(XA)>F(XB),用XC=AXA+(1-A)XB(3)8期黄松奇,等:用遗传算法求解病态线性方程组99这样一个加权和产生新个体XC,显然A越大,XC就越接近XA,当F(XA)远大于F(XB)时,由(3)式产生的新个体就离XA很近,就能够达到在适应度大的个体附近进行搜索的目的.3)基于实数编码方式,我们选取均匀变异算子,也就是分别用符合某一范围内均匀分布的随机数,以某一较小的概率来替换个体编码串中各个编码位上的值
8、,具体就是:依次指定个体编码串中每个编
