遗传算法论文【通用4篇】
【导言】此例“遗传算法论文【通用4篇】”的范文资料由阿拉题库网友为您分享整理,以供您学习参考之用,希望这篇资料对您有所帮助,喜欢就复制下载支持吧!
遗传算法论文【第一篇】
论文关键词:遗传算法
1 引言
“物竞天择,适者生存”是达尔文生物进化论的基本原理,揭示了物种总是向着更适应自然界的方向进化的规律。可见,生物进化过程本质上是一种优化过程,在计算科学上具有直接的借鉴意义。在计算机技术迅猛发展的时代,生物进化过程不仅可以在计算机上模拟实现,而且还可以模拟进化过程,创立新的优化计算方法,并应用到复杂工程领域之中,这就是遗传算法等一类进化计算方法的思想源泉。
2 遗传算法概述
遗传算法是将生物学中的遗传进化原理和随[1]优化理论相结合的产物,是一种随机性的全局优算法。遗传算法不但具有较强的全局搜索功能和求解问题的能力,还具有简单通用、鲁棒性强、适于并行处理等特点数学建模论文,是一种较好的全局优化搜索算法。在遗传算法的应用中,由于编码方式和遗传算子的不同,构成了各种不同的遗传算法。但这些遗传算法都有共同的特点,即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿,来完成对问题最优解的自适应搜索过程。基于这个共同点,Holland的遗传算法常被称为简单遗传算法(简记SGA),简单遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子,其遗传进化操作过程简单,容易理解,是其他一些遗传算法的雏形和基础,这种改进的或变形的遗传算法,都是以其为基础[1]。
遗传算法几个基本概念
个体(IndividualString):个体是遗传算法中用来模拟生物染色体的一定数目的二进制串,该二进制串用来表示优化问题的满意解。
种群(population):包含一组个体的群体,是问题解的集合。
基因模式(Sehemata):基因模式是指二进制位串表示的个体中,某一个或某些位置上具有相似性的个体组成的集合,也称模式。
适应度(Fitness):适应度是以数值方式来描述个体优劣程度的指标,由评价函数F计算得到。F作为求解问题的目标函数,求解的目标就是该函数的最大值或最小值。
遗传算子(genetic operator):产生新个体的操作,常用的遗传算子有选择、交叉和变异。
选择(Reproduetion):选择算子是指在上一代群体中按照某些指标挑选出的,参与繁殖下一代群体的一定数量的个体的一种机制龙源期刊。个体在下一代种群中出现的可能性由个体的适应度决定,适应度越高的个体,产生后代的概率就越高。
交叉(erossover):交叉是指对选择后的父代个体进行基因模式的重组而产生后代个体的繁殖机制。在个体繁殖过程中,交叉能引起基因模式的重组,从而有可能产生含优良性能的基因模式的个体。交叉可以发生在染色体的一段基因串或者多段基因串。交叉概率(Pc)决定两个个体进行交叉操作的可能性数学建模论文,交叉概率太小时难以向前搜索,太大则容易破坏高适应度的个体结构,一般Pc取~
变异(Mutation):变异是指模拟生物在自然的遗传环境中由于某种偶然因素引起的基因模式突变的个体繁殖方式。在变异算子中,常以一定的变异概率(Pm)在群体中选取个体,随机选择个体的二进制串中的某些位进行由概率控制的变换(0与1互换)从而产生新的个体[2]。如果变异概率太小,就难以产生新的基因结构,太大又会使遗传算法成了单纯的随机搜索,一般取Pm=~。在遗传算法中,变异算子增加了群体中基因模式的多样性,从而增加了群体进化过程中自然选择的作用,避免早熟现象的出现。
基本遗传算法的算法描述
用P(t)代表第t代种群,下面给出基本遗传算法的程序伪代码描述:
基本操作:
InitPop()
操作结果:产生初始种群,初始化种群中的个体,包括生成个体的染色体值、计算适应度、计算对象值。
Selection()
初始条件:种群已存在。
操作结果:对当前种群进行交叉操作。
Crossover()
初始条件:种群已存在。
操作结果:对当前种群进行交叉操作。
Mutation()
初始条件:种群已存在。
对当前种群进行变异操作。
PerformEvolution()
初始条件:种群已存在且当前种群不是第一代种群。
操作结果:如果当前种群的最优个体优于上一代的最优本,则将其赋值给bestindi,否则不进行任何操作。
Output()
初始条件:当前种群是最后一代种群。
操作结果:输出bestindi的表现型以及对象值。
3 遗传算法的缺点及改进
遗传算法有两个明显的缺点:一个原因是出现早熟往往是由于种群中出现了某些超级个体,随着模拟生物演化过程的进行,这些个体的基因物质很快占据种群的统治地位,导致种群中由于缺乏新鲜的基因物质而不能找到全局最优值;另一个主要原因是由于遗传算法中选择及杂交变异等算子的作用,使得一些优秀的基因片段过早丢失,从而限制了搜索范围,使得搜索只能在局部范围内找到最优值,而不能得到满意的全局最优值[3]。为提高遗传算法的搜索效率并保证得到问题的最优解,从以下几个方面对简单遗传算法进行改进。
编码方案
因实数编码方案比二进制编码策略具有精度高、搜索范围大、表达自然直观等优点数学建模论文,并能够克服二进制编码自身特点所带来的不易求解高精度问题、不便于反应所求问题的特定知识等缺陷,所以确定实数编码方案替代SGA中采用二进制编码方案[4]。
适应度函数
采用基于顺序的适应度函数,基于顺序的适应度函数最大的优点是个体被选择的概率与目标函数的具体值无关,仅与顺序有关[5]。构造方法是先将种群中所有个体按目标函数值的好坏进行排序,设参数β∈(0,1),基于顺序的适应度函数为:
(1)
选择交叉和变异
在遗传算法中,交叉概率和变异概率的选取是影响算法行为和性能的关键所在,直接影响算法的收敛性。在SGA中,交叉概率和变异概率能够随适应度自动调整,在保持群体多样性的同时保证了遗传算法的收敛性。在自适应基本遗传算法中,pc和pm按如下公式进行自动调整:
(2)
(3)
式中:fmax为群体中最大的适应度值;fave为每代群体的平均适应度值;f′为待交叉的两个个体中较大的适应度值;f为待变异个体的适应度值;此处,只要设定k1、k2、k3、k4为(0,1)之间的调整系数,Pc及Pm即可进行自适应调整。本文对标准的遗传算法进行了改进,改进后的遗传算法对交叉概率采用与个体无关,变异概率与个体有关。交叉算子主要作用是产生新个体,实现了算法的全局搜索能力。从种群整体进化过程来看,交叉概率应该是一个稳定而逐渐变小,到最后趋于某一稳定值的过程;而从产生新个体的角度来看,所有个体在交叉操作上应该具有同等地位,即相同的概率,从而使GA在搜索空间具有各个方向的均匀性。对公式(2)和(3)进行分析表明,适应度与交叉率和变异率呈简单的线性映射关系。当适应度低于平均适应度时,说明该个体是性能不好的个体数学建模论文,对它就采用较大的交叉率和变异率;如果适应度高于平均适应度,说明该个体性能优良,对它就根据其适应度值取相应的交叉率和变异率龙源期刊。
当个体适应度值越接近最大适应度值时,交叉概率和变异概率就越小;当等于最大适应度值时,交叉概率和变异概率为零。这种调整方法对于群体处于进化的后期比较合适,这是因为在进化后期,群体中每个个体基本上表现出较优的性能,这时不宜对个体进行较大的变化以免破坏了个体的优良性能结构;但是这种基本遗传算法对于演化的初期却不利,使得进化过程略显缓慢[6]。因为在演化初期,群体中较优的个体几乎是处于一种不发生变化的状态,而此时的优良个体却不一定是全局最优的,这很容易导致演化趋向局部最优解。这容易使进化走向局部最优解的可能性增加。同时,由于对每个个体都要分别计算Pc和Pm,会影响程序的执行效率,不利于实现。
对自适应遗传算法进行改进,使群体中具有最大适应度值的个体的交叉概率和变异概率不为零,改进后的交叉概率和变异概率的计算公式如式(4)和(5)所示。这样,经过改进后就相应地提高了群体中性能优良个体的交叉概率和变异概率,使它们不会处于一种停滞不前的状态,从而使得算法能够从局部最优解中跳出来获得全局最优解[7]。
(4)
(5)
其中:fmax为群体中最大的适应度值;fave为每代群体的平均适应度值;f′为待交叉的两个个体中较大的适应度值;f为待变异个体的适应度值;pc1为最大交叉概率;pm1为最大变异概率。
种群的进化与进化终止条件
将初始种群和产生的子代种群放在一起,形成新的种群,然后计算新的种群各个体的适应度,将适应度排在前面的m个个体保留,将适应度排在后面m个个体淘汰数学建模论文,这样种群便得到了进化[8]。每进化一次计算一下各个个体的目标函数值,当相邻两次进化平均目标函数之差小于等于某一给定精度ε时,即满足如下条件:
(6)
式中,为第t+1次进化后种群的平均目标函数值,为第t次进化后种群的平均目标函数值,此时,可终止进化。
重要参数的选择
GA的参数主要有群里规模n,交叉、变异概率等。由于这些参数对GA性能影响很大,因此参数设置的研究受到重视。对于交叉、变异概率的选择,传统选择方法是静态人工设置。现在有人提出动态参数设置方法,以减少人工选择参数的困难和盲目性。
4 结束语
遗传算法作为当前研究的热点,已经取得了很大的进展。由于遗传算法的并行性和全局搜索等特点,已在实际中广泛应用。本文针对传统遗传算法的早熟收敛、得到的结果可能为非全局最优收敛解以及在进化后期搜索效率较低等缺点进行了改进,改进后的遗传算法在全局收敛性和收敛速度方面都有了很大的改善,得到了较好的优化结果。
参考文献
[1]邢文训,谢金星。现代优化计算方法[M].北京:清华大学出版社,1999:66-68.
[2]王小平,曹立明。遗传算法理论[M].西安交通大学出版社,2002:1-50,76-79.
[3]李敏强,寇纪淞,林丹,李书全。遗传算法的基本理论与应用[M].科学出版社, 2002:1-16.
[4]涂承媛,涂承宇。一种新的收敛于全局最优解的遗传算法[J].信息与控制,2001,30(2):116-138
[5]陈玮,周激,流程进,陈莉。一种改进的两代竞争遗传算法[J].四川大学学报:自然科学版,(002):273-277.
[6]王慧妮,彭其渊,张晓梅。基于种群相异度的改进遗传算法及应用[J].计算机应用,2006,26(3):668-669.
[7]金晶,苏勇。一种改进的自适应遗传算法[J].计算机工程与应用,2005,41(18):64-69.
[8]陆涛,王翰虎,张志明。遗传算法及改进[J].计算机科学,2007,34(8):94-96
遗传算法论文【第二篇】
关键词:遗传算法;计算机网络;应用
中图分类号:TP18 文献标识码:A 文章编号:1007-9416(2017)04-0134-01
1 遗传算法的基本原理及其特征
遗传算法的基本原理是,通过遗传机理与生物的自然选择的基本特点,对网络数据传输的方式做对应的模拟,从而达到个体与群体之间信息互换的目的,并实现网络之中的信息进行传输与分割,接着可以将信息组合于网络终端,最后实现优化信息搜索功能。遗传算法的基本特征是可直接对结构对象做相关操作,这样就不会受到求导和函数连续性的限制,隐蔽性能力和全局寻优能力比较强。
2 遗传算法在计算机网络中的应用
遗传算法在实际计算机网络优化工程中的应用
在网络拓扑路径优化过程中,怎样由网络流量和终端负载来达到网络拓扑路径的最短化,并使网络布置费用最低,此为网络优化工程中一道难以解决的问题。为了解决这一难题,一般可通过下述方法来解决。先根据各个结点的物理坐标将其按一定的比例进行缩放,得到一个逻辑二维的空间,并把它充当网络优化初始值。在全终端网络问题上,为解决使用遗传算法解决全终端网络的拓扑优化布置的问题,需要顾及到各个终端的负载情况,将在网络连通约束条件下的网络投资费用最低作为优化的目标。先从随机产生的初始网络布置方案开始,使用遗传算法对搜索进程进行逐步优化。针对各个可行的网络布置方案结合结点负载控制表等制约方案来对网络投资费用进行计算,在持续搜索中,实现对全终端网络的评价。所以,可以得出结论,如果网络拓扑路径距离最小,那么在该路径上的网络的布置费用也最低,这是我们优化的方向。
遗传算法在网络入侵检测系统中的应用
在以计算机为工具,以数据库为核心,辅以通信技术来建立客户关系管理的系统中,通过现代化科学技术对每一种资源进行管理和控制,实现网络范围内的共享。在测试系统服务器中,使用的软件的架构为B/S架构,每一个用户可通过浏览器登录并对系统进行访问。在保障数据安全性方面,服务器和工作站可使用UPS不间断电源,使用这种电源还能给减缓电网波动对网络的影响作用。基于网络的入侵检测系统能够获得大量的有价值含量的数据信息,并对数据是否具有破坏性进行确认。如果防火墙抗拒这些尝试,除了防火墙之外的基于网络的入侵检测系统此时就能发挥其作用了,它能查明不明数据的攻击意图。基于主机的入侵检测系统不能对未攻击到防火墙内主机的未遂攻击进行跟踪,但是,信息的丢失,对安全方的威胁是比较大的。在终端主机网络安全技术方面,人们能够接受的规模性的应用有这些:杀毒软件、辅助安全工具和网络防火墙等。
遗传算法在计算机网络可靠度优化计算中的应用研究
在该研究中,我们假设计算机传输介质两节点之间最多只存在一条直线的链接路。该计算机网络可通过数学图来描述即G=(N,L)。通常情况下,网络的节点很难出现故障,网络链接介质是否可靠跟其长度无直接联系,网络链接路与网络通常有两种工作状态出现,一种是正常工作,一种是出现故障。如果全部的计算机网络用户都能实现互相联通,那么就能够构建成G图的一棵生成树,而且能够保障所有结点的正常工作。不论在什么时候,可能只有L种的子集(L)是正常状态,所有结点都是正常状态。所以,在对计算机网络的可靠度进行计算时,需要利用到数学建模。由遗传算法的分析过程,可构建一个计算机网络的通信系统,接着可使用遗传算法做仿真实验。对一个计算机算的网络信道可靠度优化计算的实验,接着,可作多次计算,最后建立对应的数学模型。在计算机网络可靠度优化实验中,恰当地使用遗传算法,能够将网络的稳定性和可靠性进行优化。在算法的调整中,一定要针对基因的表达式的网络连通性进行判别。在这个过程中,可对gij进行观察,如果gij为1,那么可做原交叉变异的操作,如果gij=0,此时可令gij=1,若此时操作还不能实现,那么就可以跳转到初始点重新判别,如此反复,不断循环。
3 结语
遗传算法的研究是具有较大的实际意义的,它在很多复杂的计算机网络问题中能够发挥重要作用。所以,对算法的研究是很有必要的。通过研究,能够消除算法的不利因素的影响,从而有效提升算法的运行质量,使算法在实践中获得更大的作用。
参考文献
[1]李敏强,等。遗传算法的基本理论与应用[M].北京:科学出版社, 2002.
遗传算法论文【第三篇】
关键词:遗传算法;易算算法;数术记遗;历法推步术;内算;外算
calculation in genetics and that in image-number school of yi
li shu-qing
(earthquake publishing house, beijing 100081, china)
abstract: the paper at first pointed out that the ideology basing on human life and emphasizing life development in i ching learning is consistent with the spirit of the rising western genetics calculation methods. secondly, the paper introduced late expert in scientific i ching learning, mr. pan yu-ting's understanding on genetic code, and then introduced the content and structure of the western genetic calculation, regarding dna-in-itself as the hard ware for calculation, the numbers in yi the soft ware. at last, the paper made a contrast between the image-number thinking of i ching learning and that of genetic calculation, and put forward the concept of space illustrated by the 8 tri-grams.
key words: genetic calculation; calculation by yi numbers; calculation in calendar; internal calendar; external calculation
一、引 言
从伏羲画卦到《连山》易的出现,即有象的观念,数已开始萌芽,数与筮联系即有筮数,主要用于占卜。春秋时期,“象”和“数”同时出现在《管子·七法》篇中:“则,象,法,化,决塞,心术,计数。”但象数在春秋初期仍是两个松散联系的概念。到春秋末期,象与数的概念联系比较密切,在《周易·系辞传》中提到“极数定象”,已初步出现象数理论。这时,《系辞传》中只初步论及象数的内在联系,并未详细谈到象数理论的程序。孔子在教书时六艺教学大纲“礼乐射御书数”中的数,是当时日常用的实用数。到孟子时代,即到战国末期,象数理论乃大备,历法推步术也成熟。当时的不少学者会推步术,而星命学为孟、荀二位大儒所不齿。孟子所说的“苟求其故,千岁之日至可坐而致也”,是谈的历法推步术;荀子说:“善为易者不占”。这时,在古算经算法和历法推步术之外,已有经典术数如“三式”等的出现和应用。这两类数的算法,在后汉徐岳《数术记遗》中有提要式的概括总结。对其中提出的14种算法,没有明确指出何者为历法推步术算法,何者为术数算法程序。亦可能是综合的、浑元一体的算法程序。总的看来,有数必有算,有算必有法。形成古算经算法和术数算法是很自然的。在古代可能有互补的趋势。《周易》大衍之数很可能与古六历所用的算法程序有关。唐代张遂的大衍历以及宋秦九韶《数书九章》均涉及大衍算法,而秦汉时期的《九章数学》中则对大衍算法避而不谈。这可能是由于古代大儒亦是视大衍之数带有神秘内容,不敢与正规的应用数学算法相提并论。实际上,大衍之数只是一种现代所说的“不定分析”而已!阮元论曰:“推步之法至大衍备矣,……后来算造者未能及也。然推本易象,终为傅合,昔人谓一行窜入于《易》以眩众,是乃千古定论也”。[1]由此可知,就算法而论,推步术自为推步术,数术自为数术,各成系统,不相涉也。然而,这并不意味着数术算法程序中无合理内容。英人李约瑟常提到术数“内算”很有用。[2]但未作深入探究。宋秦九韶《数书九章》序中论内外算,涉及经典术数三式,其论颇正:“今数术之书尚三十余家,天象历度,谓之缀术。太乙壬甲谓之三式,皆曰内算,言其秘也。九章所载即周官九数,系于方圆者为镚术,皆曰外算,对内而言也。其用相通,不可歧二”。[3]以上所论均涉及数字信息。
21世纪已成为信息时代,信息与象数息息相通。故《系辞传》象数思维应当在今后大放光芒,与西方计算机文化成就携手并进,逐渐融汇成一体。《周易·系辞传》“天地之大德曰生”,“生生之谓《易》”,强调生命演化思想;卦爻的设置上采取乾坤六子的形式,这都与西方新近兴起的遗传算法的精神与具体计算步骤内容相近。
二、遗传密码与象数
近些年来,国内外对于科学易感兴趣的学者,无不重视生物遗传密码的研究成果,并展开《周易》象数与遗传密码细部结构对比的探讨。这方面,尤以已故著名科学易学家潘雨廷教授的研究具有代表性。潘先生博古通今,既深钻过象数理论,又熟悉分子生物学和遗传密码的生物化学含义,他在“科学易”一文中以dna(脱氧核糖核酸)和rna(核糖核酸)为例,来考察其分子结构的变化情况,及其化学键的“象数”。[4]讨论结果如下表所示(暂略):
为了使读者深入理解象数与生物遗传学及遗传密码的对应关系,有必要将有关科学名词加以扼要的解释:
1、遗传密码: dna(脱氧核糖核酸)中核苷酸顺序和蛋白质中的氨基酸顺序之间的关系称为遗传密码。遗传密码是由碱基的三联体(相当于《易经》八卦的三爻),可在dna分子上顺序读出,且互不重迭)。dna是一切生命形式的普遍遗传物质。dna有四种不同的碱基:两种嘌呤,即腺嘌呤和鸟嘌呤,以及两种嘧啶,即胸腺嘧啶和胞嘧啶。dna的结构呈双螺旋结构形式。
由三联体密码重迭,可形成与六十四卦相对应的符号系统。这并非出自偶然,而是自然物的发生和演化合乎易数的自组织作用造成的。潘雨廷教授在《周易纵横录》论文中已作了详细的象数论述,可以参看。
2、核苷酸:上述四种碱基之一与脱氧核糖结合,叫作核苷。核苷的磷酸酯衍生物称之为核苷酸。dna分子是由核苷酸构成的,许多单元接在一起就形成了多核苷酸长链。
3、核糖核酸(rna):rna和dna一样,都是长链分子,亦是由重复的核苷酸单元组成。rna的构成单元有两点与dna不同。首先,rna的糖组分不是脱氧核糖,而是核糖。其次,四种碱基中虽然有三种,即腺嘌呤、鸟嘌呤和胞嘧啶,在rna和dna中都一样。但第四种,即胸腺嘧啶,在rna中为尿嘧啶所代替,它少了一个甲基。在三种rna类型的一种类型中,还偶尔出现别的碱基。
4、信使核糖核酸(mrna):〖htss〗mrna在把密码翻译成专一性蛋白质时起模板作用,并且能把遗传密码的信息从细胞核的dna运送到细胞质,以便促进合成蛋白质的作用。携带着所需要的信息,以决定一个蛋白质分子的整个多肽链的mrna的长度,称为作用子。某些mrna分子携带着不仅合成一个蛋白质分子的信息,这样的mrna称为多作用子。在合成过程中,当密码由dna转录到mrna上时,后者即离开细胞核,通过核膜进到细胞质中。在细胞质中它移动到蛋白质合成的场所,即转移到核糖核蛋白体处。核糖核蛋白体由dna和蛋白质组成。
5、转移核糖核酸(trna):〖htss〗其作用是把细胞质中的氨基酸转移到核糖核蛋白体上蛋白质合成的场所。因此,trna是在特定氨基酸与对它编码的mrna三联体之间起媒介物或转接分子的作用。每个氨基酸都有其互不相同的、专一的trna分子。每种trna含有大约80个核苷酸。
6、反密码子:trna分子上与mrna连接的一定部位是一个由三个碱基组成的顺序,与mrna上的密码子互补,称为反密码子。
7、简并密码:试验表明,虽然任何特定氨基酸密码子的开始两个字母总是不变,然而第三个字母有时却不同。例如,编码丝氨酸的不仅是agu,也有agc。因此,crick 1966年提出“摇摆”假设,这种摇摆在于第三对碱基之间的配合与前两对碱基的精确要求相比多少有些松弛。凡是同一个氨基酸有不同的密码者,这种密码称为简并密码。
三、遗传算法概要
在遗传算法中,可以将模型的一个参数表示为一个二进制数码,全部参数用许多串联在一起的二进制数码组成的字符串(类似一个染色体)代表。从一组初始模型,即一些具有不同染色体的个体组成的种群开始。[5]
遗传算法的基本思想正是基于模仿生物界的遗传过程。它把问题的参数用基因代表,把问题的解用染色体代表(在计算机里为字符串),从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争,适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征,并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境,不断进化,最后收敛到一族最适应环境的类似个体,即得到问题最优的解。值得注意的一点是,现在的遗传算法是受生物进化论学说的启发提出的,这种学说对我们用计算机解决复杂问题很有用,而它本身是否完全正确并不重要(目前生物界对此学说尚有争议)。
遗传算法的基础思想是在本世纪50年代初,由于一些生物学家尝试用计算机模拟生物系统演化时而提出的。
遗传算法是模拟生物通过基因的遗传和变异,有效地达到一种稳定的优化状态的繁殖和选择的过程,从而建立的一种简单而又有效的搜索方法。它运用随机而非确定性的规则对一族而非一个点进行全局而非局部地搜索,它仅利用目标函数而不要求其导数或其它附加限制,它虽然在特定问题上效率也许不是最高,但效率远高于传统随机算法,是一种普遍适用于各种问题的有效方法。遗传算法的主要思路有:
1、繁殖(reproduction):繁殖是根据现有各个体的目标函数值,确定其生存概率,模拟生物界的自然选择,劣者淘汰,适者生存。在遗传算法中,我们人为地保持种群包含的个体总数不变。比较优秀的个体(模型)有较大的生存概率,并可能繁衍,比较差的个体(模型)可能会淘汰。这样产生的下一代的个体,一般都具有较大目标函数值,因而有较大的生存概率。
2、交配(crossover):从种群中随机地选择两两一组的双亲,分别随机地交换部分染色体,各自产生两个新染色体。
3、变异(mutation):染色体按一定概率(一般很小)可随机地产生变异。
遗传算法能够解决的问题不仅限于最优化问题,但无论哪种问题,都要解决两个关键问题:(1)必须能将问题的解答用一组二进制数码表示,即建立解答与二进制数码间的映射(mapping)关系。(2)定义一种对最佳解的定量量度,即适度函数。
四、自然dna“计算机”的“硬件”与软件——象、数
算盘由木框、竹棍、算珠构成,其各类珠算口诀和规则是计算程序。算盘建立了一个珠算空间;易算卦爻,杭辛斋称之为卦材、爻材,相当于易算硬件,《系辞传》所论“八卦成列,象在其中矣”,是八卦空间。《序卦》所论相当于宏观程序。“蓍之德圆而神,卦之德方以智”等有关卦爻功能的论述,相当于基因染色体数的作用。
遗传算法所取法的自然dna的“硬件”(象)经生物化学家多年进行的dna结构分析的研究,相当 图1 dna四种碱基糖环系统及其原子标准指数(暂略)于高分子结构式所表示的原子结构。[6]具体化到dna,则是双链螺旋结构的形象。dna的参数有化学边界距离(以旋转角度表示),边界角(两相邻化学边界间的夹角),扭力角(dna螺旋的扭转角度,0~360°)。然而,前二者是常量。只有扭力角是时常变动的变量。遗传算法主要利用扭力角变量。今将遗传算法所取法的象数——碱基结构式及dna中轴(只表示一个核苷酸单位)扭力角分布等叙述如下:
图1表示dna四个碱基系统及其原子标准指数,图2(暂略)上部表示基本环,其扭力角为χi,其下表示糖环,其扭力角为p(i),γn(i),碱基系统的全过程是自由的,原则上沿单个化学边界“摆动”,就这样与dna糖环连接起来。意即基本环与糖环沿公共边界而“摆动”。这种摆动可能是在传递信息。沿化学界面在糖环上的内循环扭力角χ在空间上受到制约,因为糖环需要闭合。已发现每一核苷酸单位都有八个主要结构参数:χ,νm,p,α,β,γ,ε,ζ(2),〖jp〗这八个参数都限制在一个有限的距离内,原则上,扭力角α,β,γ,ε,ζ(2)及χ位于0~360°之间;δ是中轴和糖环的一部分,这里把δ叫做ν3,δ是一种冗余信息。p,νm距离可以推导出。典型的距离分别是150°~225°,25.0°~50.0°(距离用扭力角变化值表示)。如果dna的8个结构参数已知,则排列位置已知的dna,包括其中所含的n个核苷酸即可完全确定。
dna探针:这种探针(图3)(暂略)在探测环境信息方面,从最原始的单细胞生物变形虫原生质中就存在其原始形态。这种探针机构随宇宙和生物演化而逐渐变得复杂起来。瑞士学者方迪《微精神分析学》一书把这种探针式的尝试作用叫做“伊德”。[7]“伊德”在心理学界受到重视。dna的探针是一种复杂的综合体,在生物分子结构研究方面享有广泛的盛名,称之为dna探针级的研究。探针综合体一部分是由于其核苷酸自补偿作用而出名的。dna探针由一个双链杆和一个环组成。探针最重要的部分是这个环。探针在演化过程中非常守恒(稳定),因此具有重要的生物功能。探针形成于细菌噬菌体最原始的重复功能。dna染色体组存在有复杂的相互作用。这种作用能被其他生物分子所识别、利用,亦可由原生质来识别。
dna相当于一个微观世界,其细部结构和功能远未认识到。可以预料,它作为遗传算法的自然样板,其有用信息,取之不尽,用之不竭。要想改进遗传算法,一定要先取得自然dna的新探索成就。最近对dna的假结点的观测,对dna三叉结构的观测就属于这方面的新探索。dna双链结构相当于太极生两仪,两仪生四象,一分为二的浑沌二分叉结构。将来对dna三叉结构的认识可能引导到对《太玄经》一分为三,中医“三阴三阳”的认识。这并非遥远的呓想,可能是不久的事情了。
五、易算程序问题
易学象数理论自战国形成后,由于社会制度与士大夫意识形态的原因,易数不能走西方公理化的道路。徐岳《数术记遗》积算、太乙算、九宫算都有比较独立的算法。其余不一定有独立的算法。其中提出的14种算法是:积算,太一算,两仪算,三才算,五行算,八卦算,九宫算、运筹算,了知算,成数算,把头算,龟算,珠算,计算(心算)。对每种算法的叙述,只有三言两语,看不出所以然。迄今尚未有人作深入研究。原因是“文献不足故也”。要想恢复14种算法的原样,只有走到基层农民和隐居型的知识分子那里作调查。可惜多少年来无人问津,所以困惑一直未解。我认为调查重点主要是山东半岛蓬莱,镠罘沿海一带山区农村。
《九章数学》“寓理于术”,文中的“术曰”会有算法理论和程序背景。[8]现在唯一可了解的就是珠算算法,此已有全国珠算学会在研究。其中不少口诀规则,堪称算法。可从此入手以及从历代历法推步术的演化中追索易算算法。古有《缀术》,为南北朝祖冲之所创,用于五星的推步(宋秦九韶《数书九章》第三卷天时类有“缀术推星”章)。《缀术》在《算经十书》中有名无书,书已失传。
总之,恢复古代易算程序的研究是一大课题。南京大学天文系朱灿生教授曾拟研究恢复缀术。究竟古代易算详细内容如何,尚待考证恢复。秦汉前后出现的三式(太乙、六壬、奇门)经典术数的推演中可能有易算算法程序的影子。其中既含科学因素,又有不少神秘内容,今后应作开发研究。
六、象数思维与遗传算法的比较
本人研究科学易多年,研究遗传算法已有七、八年,迄今已初步得出易的象数思维基本上等价于遗传算法的性质与功能的初步看法。所谓象数思维主要是包含在孔子及其弟子所作的《易传》中,且主要是《系辞传》。经对比发现,无论用自然遗传过程,生物演化观念,整体观或根据实际观测来认识自然,在问题优化,生物遗传基因交配、变异,以及在溯往和预测问题上都表现了象数思维与遗传算法的相似性。《诗经·小雅》说:“唯其有之,是以似之。”意即两种事物相似的根本原因是二者之间有共同的东西。这亦是《内经》“贤者察同,愚者察异”之意。今将二者比较如下:
1.遗传算法(以下用ga简写表示)和《易》都重视生命现象,特别是遗传过程。《系辞传》说“生生之谓易”,“天地之大德曰生”。
2.ga和《易》都重视演化,重视从混沌到有序的观念,而认为确定不变的存在是暂时的。实际上,ga和《易》都有逼近论思想。
3.二者都有整体观思想:ga用相当染色体的种群(population)数作为基础,用相当基因的二进制数串输入计算机运算。所用数的设计都是一个集合,而不是用单个数。易算用大衍之数50(虚一不用)作为演算基础,亦是整体观。
4.二者都是以实际观测为研究根据。ga是西方实测方法的继续,自不待言。伏羲氏是根据仰观俯察、远取近取进行比较后而画八卦的,不是凭空臆造。
5.ga以求得问题优化解见长。孔子谓《易》是寡过之书,趋吉避凶之书,从广义上看也是一种优化。元吉(大吉)为全局优化,吉或悔而后吉是局部优化。 特别是《易》有《既济》、《未济》二卦作为纲领卦。《既济》乃优化的结果,《未济》也设法使其转变,向《既济》发展,很多卦爻辞字里行间,多有此意。
6.二者重事物之间的相互作用和关系。ga用交配来表达此意,《易》则以“天地镮,万物化醇,男女构精,万物化生”;“天气下降,地气上腾”(《礼记·月令》)来表示。
7.二者均重视质变,ga谓之变异,《周易·系辞传》则说:“穷则变,变则通。”
8.二者均涉及数学空间的理论和应用。ga常用结构参数空间,《易》则有八卦空间:“八卦成列,象在其中矣”;“乾坤成列而易立乎其中矣”。
9.《系辞传》说:“神以知来,智以藏往”。ga既能探索已往解决问题,又能用于地震预报。
ga的作者提出算法的改进问题,主要是深入挖掘dna结构的潜力。而东方思维则有“巢居知风,穴居知雨”的说法,这种说法是科学的,即鸟类和昆虫类(如蚂蚁)均有预测天气变化的功能。如能开发鸟类和蚂蚁体内信息大分子结构奥秘,可以用以改进ga算法的功能。
附注:已故学者刘绍光一元数理论的研究是根据易学象数发展出的一种易算数学分支。这一分支后继乏人或无人。关于一元数理论已出版《一元数理论初探》[9]一书,其中不少与ga有相通之处,如其中提出的位元、序元、结元三个计算程序理论概念,以及磁子、电子、声子、光子、热子、引子、张子等开阖角的问题。均可与ga相互作用,而创造新的算法。
参考文献: [1] (汉)徐岳.数术记遗[m].阮元.畴人传[z].光绪海盐常惺斋刊本.[2] (英)李约瑟.中国科学技术史:第三卷(数学)[m].北京:科学出版社,1978.《中国科学技术史》翻译小组译.
[3] 秦九韶.数书九章[m].宜稼堂丛书[z].民国商务印书馆《丛书集成》本.
[4] 潘雨廷.科学易[a].唐明邦.周易纵横录[c].武汉:湖北人民出版社,1986.
[5] genetic algorithms in search, optimization, and machine learning. addison-wesley publishing company. york.
[6] van nostrand reinhold of genetic algorithms p251~280.(1
8. a genetic algorithm for conformational analysis of dna, written by published by van nostrand reinbold, new york.
遗传算法论文【第四篇】
关键词全局最优;混合算法;遗传算法;Powell方法
1引言
不可微非线性函数优化问题具有广泛的工程和应用背景,如结构设计中使得结构内最大应力最小而归结为极大极小优化(minmax)问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视,常用的算法有模式搜索法、单纯形法、Powell方法等,但是这些方法都是局部优化方法,优化结果与初值有关。
近年来,由Holland研究自然现象与人工系统的自适应行为时,借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法,是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快,在各种问题的求解与应用中展现了其特点和魅力,但是其理论基础还不完善,在理论和应用上暴露出诸多不足和缺陷,如存在收敛速度慢且存在早熟收敛问题[1,2]。为克服这一问题,早在1989年Goldberg就提出混合方法的框架[2],把GA与传统的、基于知识的启发式搜索技术相结合,来改善基本遗传算法的局部搜索能力,使遗传算法离开早熟收敛状态而继续接近全局最优解。近来,文献[3]和[4]在总结分析已有发展成果的基础上,均指出充分利用遗传算法的大范围搜索性能,与快速收敛的局部优化方法结合构成新的全局优化方法,是目前有待集中研究的问题之一,这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿-莱佛森法和遗传算法进行杂交求解旅行商问题,文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题,均取得良好的计算效果,但是不适于不可微函数优化问题。
本文提出把Powell方法融入浮点编码遗传算法,把Powell方法作为与选择、交叉、变异平行的一个算子,构成适于求解不可微函数优化问题的混合遗传算法,该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。
2混合遗传算法
编码是遗传算法应用中的首要问题,与二进制编码比较,由于浮点编码遗传算法有精度高,便于大空间搜索的优点,浮点编码越来越受到重视[7]。考虑非线性不可微函数优化问题(1),式中为变量个数,、分别是第个变量的下界和上界。把Powell方法嵌入到浮点编码遗传算法中,得到求解问题(1)如下混合遗传算法:
min(1)
step1给遗传算法参数赋值。这些参数包括种群规模m,变量个数n,交叉概率pc、变异概率pm,进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。
Step2随机产生初始群体,并计算其适应值。首先第i个个体适应值取为fi’=fmax-fi,fi是第i个个体对应的目标函数值,fmax为当前种群成员的最大目标函数值,i=1,2,…,m。然后按Goldberg线性比例变换模型[2]式(2)进行拉伸。
fi’=a×fi’+b(fi³0)(2)
step3执行比例选择算子进行选择操作。
step4按概率执行算术交叉算子进行交叉操作。即对于选择的两个母体和,算术交叉产生的两个子代为和,是[0,1]上的随机数,1,。
step5按照概率执行非均匀变异算子[8]。若个体的元素被选择变异,,则变异结果为,其中,
(3)
(4)
返回区间[,]里的一个值,使靠近0的概率随代数的增加而增加。这一性质使算子在初始阶段均匀地搜索空间,而在后面阶段非常局部化。是[,]之间的随机数,为最大代数,为决定非均匀度的系统参数。
step6对每个个体按照概率pPowell进行Powell搜索。若个体被选择进行Powell搜索操作,则以作为初始点执行Powell方法得,若则把所得计算结果作为子代,否则,若取=;若取=,1。
step7计算个体适应值,并执行最优个体保存策略。
step8判断是否终止计算条件,不满足则转向step3,满足则输出计算结果。
作为求解无约束最优化问题的一种直接方法,Powell法的整个计算过程由若干轮迭代组成,在每一轮迭代中,先依次沿着已知的n个方向搜索,得一个最好点,然后沿本轮迭代的初始点与该最好点连线方向进行搜索,求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一,开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的,保证算法的收敛性,对替换方向的规则进行改进,在混合法的计算步骤step6中采用文[9]中的改进Powell方法,其求解过程如下:
(1)变量赋初值,n个线性无关的n个方向,…,,和允许误差ε>0,令k=1。
(2)令,从出发,依次沿方向,…,作一维搜索,得到点,…,求指标m,使得-=max{-},令。若ε,则Powell方法计算结束,否则,执行(3)。
(3)求使得=min,令==,若,则Powell方法计算结束,得点;否则,执行(4)。
(4)若,令,否则令(),然后置,转(2)。
3算例
T[-500,500]
图1函数f(x)特性示意图
函数f(x)有相当多的极小点,全局极小点是=-,=1,2,…,,最优值为-;次最优点为={(,,…,):=-,,=},=1,2,…,,次优值-。变量个数n=2时函数f(x)特性如图1示。程序编制和运行环境采用,随机数由内部随机函数产生,在奔腾133微机上运行。
采用改进的Powell方法计算100次,初值在区间[-500,500]内随机产生,只有6次(即以概率)搜索到全局最优,计算成功的概率极低。
Holland建立的标准(或简单)遗传算法,其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30,交叉概率pc=、变异概率pm=,最大进化代数T=1000,每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低,对于标准遗传算法以目标函数小于-800为搜索成功,标准遗传算法运行100次。当取最大进化代数为T=200时,40次(以概率)搜索到全局最优,平均计算时间为秒;当取T=500时,51次(以概率)搜索到全局最优,平均计算时间为秒。
采用本文混合法计算,取m=30,pc=、pm=,T=100,进行Powell搜索的概率pPowell取不同值,混合法运行100次,计算结果见如表1。对于这个具有多极值的算例,多次计算表明pPowell=时,混合法能以完全概率搜索到全局最优的准确值,但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法,取m=30,pc=、pm=,T=100,运行100次,82次(以概率)搜索到全局最优(如表1中PPowell=0所示),计算时间约为标准遗传算法取T=500时计算时间的1/8,但是搜索到全局最优的概率却远远高于标准遗传算法。
表1pPowell取不同值时混合法的计算结果
PPowell
求得最优解的次数
82
85
89
94
98
100
求得最优解的概率
平均计算时间/秒
4结束语
针对不可微函数的全局优化问题,本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法,该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点,提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法,可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息,本文混合法不仅适用于不可微函数优化问题,也适合可微函数全局优化问题。
参考文献
[1]周明,孙树林.遗传算法原理及应用[M].北京:国防工业出版社,1999.
[2],optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989.
[3]孟庆春,贾培发.关于Genetic算法的研究及应用现状[J].清华大学出版社,1995,35(5):44-48.
[4]戴晓晖,李敏强,寇纪松.遗传算法理论研究综述[J].控制与决策,2000,15(3):263-268.
[5]LinW,Delgado-FriasJG.HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995,26(5):387-412.
[6]赵明旺.连续可微函数全局优化的混合遗传算法[J].控制与决策,1997,12(5):589-592.
[7]-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems,1991,5:139-167.
[8]MichalewiczZ.Amodifiedgeneticalgorithmforoptimalcontrolproblems[J].,1992,23(12):83-94.
[9]陈宝林.最优化理论与算法[M].北京:清华大学出版社,1989.
[10]俞红梅.全过程系统能量综合方法的研究[D].大连理工大学博士学位论文,1998.
Hybridapproachforglobaloptimaofindifferentiablenonlinearfunction