高中遗传学概率计算方法篇1
论文关键词：遗传算法
1引言
“物竞天择，适者生存”是达尔文生物进化论的基本原理，揭示了物种总是向着更适应自然界的方向进化的规律。可见，生物进化过程本质上是一种优化过程，在计算科学上具有直接的借鉴意义。在计算机技术迅猛发展的时代，生物进化过程不仅可以在计算机上模拟实现，而且还可以模拟进化过程，创立新的优化计算方法，并应用到复杂工程领域之中，这就是遗传算法等一类进化计算方法的思想源泉。
2遗传算法概述
遗传算法是将生物学中的遗传进化原理和随[1]优化理论相结合的产物，是一种随机性的全局优算法。遗传算法不但具有较强的全局搜索功能和求解问题的能力，还具有简单通用、鲁棒性强、适于并行处理等特点数学建模论文，是一种较好的全局优化搜索算法。在遗传算法的应用中，由于编码方式和遗传算子的不同，构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同点，Holland的遗传算法常被称为简单遗传算法（简记SGa），简单遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，这种改进的或变形的遗传算法，都是以其为基础[1]。
2.1遗传算法几个基本概念
个体(individualString)：个体是遗传算法中用来模拟生物染色体的一定数目的二进制串，该二进制串用来表示优化问题的满意解。
种群(population)：包含一组个体的群体，是问题解的集合。
基因模式(Sehemata)：基因模式是指二进制位串表示的个体中，某一个或某些位置上具有相似性的个体组成的集合，也称模式。
适应度(Fitness)：适应度是以数值方式来描述个体优劣程度的指标，由评价函数F计算得到。F作为求解问题的目标函数，求解的目标就是该函数的最大值或最小值。
遗传算子(geneticoperator)：产生新个体的操作，常用的遗传算子有选择、交叉和变异。
选择(Reproduetion)：选择算子是指在上一代群体中按照某些指标挑选出的，参与繁殖下一代群体的一定数量的个体的一种机制龙源期刊。个体在下一代种群中出现的可能性由个体的适应度决定，适应度越高的个体，产生后代的概率就越高。
交叉(erossover)：交叉是指对选择后的父代个体进行基因模式的重组而产生后代个体的繁殖机制。在个体繁殖过程中，交叉能引起基因模式的重组，从而有可能产生含优良性能的基因模式的个体。交叉可以发生在染色体的一段基因串或者多段基因串。交叉概率（pc）决定两个个体进行交叉操作的可能性数学建模论文，交叉概率太小时难以向前搜索，太大则容易破坏高适应度的个体结构，一般pc取0.25~0.75
变异(mutation)：变异是指模拟生物在自然的遗传环境中由于某种偶然因素引起的基因模式突变的个体繁殖方式。在变异算子中，常以一定的变异概率（pm）在群体中选取个体，随机选择个体的二进制串中的某些位进行由概率控制的变换（0与1互换）从而产生新的个体[2]。如果变异概率太小，就难以产生新的基因结构，太大又会使遗传算法成了单纯的随机搜索，一般取pm=0.1~0.2。在遗传算法中，变异算子增加了群体中基因模式的多样性，从而增加了群体进化过程中自然选择的作用，避免早熟现象的出现。
2.2基本遗传算法的算法描述
用p(t)代表第t代种群，下面给出基本遗传算法的程序伪代码描述：
基本操作：
initpop（）
操作结果：产生初始种群，初始化种群中的个体，包括生成个体的染色体值、计算适应度、计算对象值。
Selection（）
初始条件：种群已存在。
操作结果：对当前种群进行交叉操作。
Crossover（）
初始条件：种群已存在。
操作结果：对当前种群进行交叉操作。
mutation（）
初始条件：种群已存在。
对当前种群进行变异操作。
performevolution（）
初始条件：种群已存在且当前种群不是第一代种群。
操作结果：如果当前种群的最优个体优于上一代的最优本，则将其赋值给bestindi，否则不进行任何操作。
output（）
初始条件：当前种群是最后一代种群。
操作结果：输出bestindi的表现型以及对象值。
3遗传算法的缺点及改进
遗传算法有两个明显的缺点：一个原因是出现早熟往往是由于种群中出现了某些超级个体，随着模拟生物演化过程的进行，这些个体的基因物质很快占据种群的统治地位，导致种群中由于缺乏新鲜的基因物质而不能找到全局最优值；另一个主要原因是由于遗传算法中选择及杂交变异等算子的作用，使得一些优秀的基因片段过早丢失，从而限制了搜索范围，使得搜索只能在局部范围内找到最优值，而不能得到满意的全局最优值[3]。为提高遗传算法的搜索效率并保证得到问题的最优解，从以下几个方面对简单遗传算法进行改进。
3.1编码方案
因实数编码方案比二进制编码策略具有精度高、搜索范围大、表达自然直观等优点数学建模论文，并能够克服二进制编码自身特点所带来的不易求解高精度问题、不便于反应所求问题的特定知识等缺陷，所以确定实数编码方案替代SGa中采用二进制编码方案[4]。
3.2适应度函数
采用基于顺序的适应度函数，基于顺序的适应度函数最大的优点是个体被选择的概率与目标函数的具体值无关，仅与顺序有关[5]。构造方法是先将种群中所有个体按目标函数值的好坏进行排序，设参数β∈(0,1)，基于顺序的适应度函数为：
（1）
3.3选择交叉和变异
在遗传算法中，交叉概率和变异概率的选取是影响算法行为和性能的关键所在，直接影响算法的收敛性。在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为最大变异概率。
3.4种群的进化与进化终止条件
将初始种群和产生的子代种群放在一起，形成新的种群，然后计算新的种群各个体的适应度，将适应度排在前面的m个个体保留，将适应度排在后面m个个体淘汰数学建模论文，这样种群便得到了进化[8]。每进化一次计算一下各个个体的目标函数值，当相邻两次进化平均目标函数之差小于等于某一给定精度ε时，即满足如下条件：
(6)
式中，为第t+1次进化后种群的平均目标函数值，为第t次进化后种群的平均目标函数值，此时，可终止进化。
3.5重要参数的选择
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].四川大学学报:自然科学版,2003.040(002):273-277.
[6]王慧妮,彭其渊,张晓梅.基于种群相异度的改进遗传算法及应用[J].计算机应用,2006,26(3):668-669.
[7]金晶,苏勇.一种改进的自适应遗传算法[J].计算机工程与应用,2005,41(18):64-69.
[8]陆涛,王翰虎,张志明.遗传算法及改进[J].计算机科学,2007,34(8):94-96
高中遗传学概率计算方法篇2
关键词：自适应遗传算法；适应度函数；变异操作；格雷编码；实数编码
中图分类号：tp3文献标识码：a
收录日期：2012年1月12日
引言
遗传算法（Ga）由美国michigan大学的Holland教授于1975年首先提出，后经DeJong、GoldBerg等人改进推广，广泛应用于各类问题。它是一种模拟自然界生物进化过程与机制的全局概率优化搜索方法。
早期遗传算法在进化过程中易出现早熟收敛和局部收敛性差等问题，为了克服上述问题，人们提出了多种改进算法。本文对自适应算法进行改进，算法中不仅交叉和变异概率是自适应的，而且构造了一种自适应的适应度函数，以便更好地进行复制、交叉、变异操作，同时结合实数编码精度高、搜索范围大和二进制编码的收敛速度快、变异操作易实现的特点，算法还采用了实数与二进制编码相结合的方式，在防止早熟的同时还能提高全局搜索能力，最后利用改进算法进行仿真实验，结果表明本算法具有收敛概率高和平均收敛代数少的优点。
一、改进的遗传算法
1、改进的适应度函数。经典遗传算法由选择、交叉和变异三种基本操作构成，适应度函数通常都是用所求函数值表示，首先将函数定义为求最大值maxf，若求最小值则变换函数为max（-f），有时为了编程方便可以加一个足够大的正数m，即max（-f+m），使函数值恒为正，之后将个体按照它们的适应度大小进行选择。通常选择的目的是保留更多高适应度的个体，但为了达到全局最优，防止过早收敛，在选择过程中要尽量保持个体的多样性。通常选择操作采用比例选择法，这样适应度高的个体将有更大的概率被选择。此外，还将适应度函数调整为f'（xi）=f（xi）－，其中f（xi）是xi所对应的函数值，是群体的平均函数值，n为种群内个体数。这种调整使得原本函数值远离群体均值的个体适应度变大，使其被选择的概率增大，而对种群贡献较小的函数值处于中间位置的个体被选择的概率变小，使得在进化前期可以保证种群的多样性，避免产生模式欺骗问题或者过早陷入局部收敛。基于这种思想，为了使进化前期原本函数值低的个体有更大的概率被选择，保持种群多样性防止“早熟”，而在后期可以转成正常选择操作，开始局部求精的搜索。本文将适应度函数改进为：
f'（xi）=f（xi）－t＜0.6ttan（）・f（xi）＋fmaxt＞0.6t（1）
其中，fmax为上一代最优解所对应的函数值，t为当前代数，t为预先设置好的最大迭代次数。
2、格雷码周期变异。由于二进制变异容易控制，可以避免考虑实数变异涉及的变异方向，所以本文在变异操作中采用二进制格雷编码，格雷编码的定义见（2）式，
gray［0］=p［0］if（p［j-1］）＝p［j］gray［j］＝0elsegray［j］＝1（j=1，2，…，l-1）（2）
其中，p为原二进制编码，l为编码长度。格雷编码不仅具有良好的局部搜索能力，还能克服二进制编码Hamming悬崖，之后将变异概率设定成一个周期性变化的函数，见（3）式：
（3）
其中，a，b是待定值，此函数在一个周期内是单调递减的，在进化后期种群趋于稳定时，降低选择压的同时应该采取大概率变异，保持种群的多样性，防止陷入局部解。经测试，当a=3，b=19时算法性能较好。
二、算法步骤
Step1采用实数编码产生初始种群，在函数定义域内按照均匀分布随机产生n个个体，xi（1，2，…n）设定最大进化代数设为t。
Step2计算每个个体的函数值，之后根据计算种群函数的平均值，最后按照本文设定的适应度函数，即（1）式计算当前种群中每个个体的适应度。
Step3根据每个个体的适应度，采用比例选择法。通过这种适应度转换，使得在进化前期原本函数值小的个体将有更大的概率被选择，保持了种群的多样性。
Step4按照概率pc在种群中随机选择父代个体进行交叉操作。
Step5首先依据变异概率pm选定变异个体，然后利用格雷码周期变异操作进行编码、变异、最后解码。
Step6最优保存策略。本文将最优保存策略算法做如下修改：第一步，计算每个个体的函数值，然后排序，找出最优解，最差解；第二步，若上一代最优解的函数值比当前最优解的函数值大，则用上一代的最优解替换当前最优解；若上一代的最优解函数值小，则用上一代的最优解替换当前中的最差解。这样，基于markov链的数学理论分析表明，保留最优个体策略的遗传算法就能够以概率1收敛于最优解。
Step7满足迭代次数即停止，否则代数加1，转入Step2。
三、仿真试验
1、测试函数。选取文献［3、6、7］的测试函数为：
其中，f1为单峰二次函数，当（x1+x2+x3）＝（0，0，0）时有全局最小值0；f2有无数个局部最大值，只有一个全局最大点（0，0），最大值为1；f3是一维连续且含三角函数的多峰函数，当x=1.8505时，全局最大值为3.8503；f4是Schaffer函数，当（x1，x2）=（0，0）时有全局最小值0。
2、测试结果对比分析。用本文算法同基本遗传算法和自适应遗传算法进行比较，其中取种群规模m=200，基本遗传算法的交叉概率pc=0.85和变异概率pm=0.1，自适应遗传算法的交叉概率和变异概率分别为：
，pm2=0.05，f'为两个要交叉个体适应度大的个体适应度值，最大迭代次数设为t＝150，对各测试函数分别独立运行100次得到表1。（表1）
通过实验表明，本文的算法在对函数f1、f3、f4的测试中，达到最优值的收敛代数明显减少，得到了令人满意的效果，对函数f2的测试中虽然本文算法提高了算法的收敛概率，同时收敛的代数也明显减少，所以本文的算法在减少收敛代数方面和提高收敛概率方面是具有优越性的。
四、结束语
本文提出改进的适应度函数，使得在进化初期一些函数值差的个体也能有更高的概率参与到选择、交叉、变异操作中，保存了种群的多样性，同时在自适应交叉的过程也采用了新的方法，使得在避免“近亲繁殖”的基础上扩大了搜索范围，整个算法结合实数编码的全局能力强和格雷码局部收敛能力强的两个特点，在算法中使用了实数编码与格雷编码相结合的方法，使得收敛的迭代次数明显减小。虽然采用格雷编码会导致算法收敛速度慢，但是明显降低了不收敛的次数，大大提高了算法收敛速度和收敛概率，使本文算法具有较高的计算效率。
主要参考文献：
[1]王力，侯燕玲.基于遗传算法通用试题库系统研究[J].微计算机信息，2008.5.
[2]李敏强，寇纪淞，林丹等.遗传算法的基本理论与应用[m].北京：科学出版社，2004.
[3]杨晓华，陆桂华，郦建强.解非线性极大极小问题的格雷码加速遗传算法[J].河海大学学报，2003.31.1.
高中遗传学概率计算方法篇3
关键词全局最优；混合算法；遗传算法；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)有相当多的极小点,全局极小点是=-420.97，=1,2,…,，最优值为-837.97；次最优点为={(,,…,)：=-420.97,,=302.52}，=1,2,…,，次优值-719.53。变量个数n=2时函数f(x)特性如图1示。程序编制和运行环境采用FortranpowerStation4.0，随机数由内部随机函数产生，在奔腾133微机上运行。
采用改进的powell方法计算100次，初值在区间[-500,500]内随机产生，只有6次（即以概率0.06）搜索到全局最优，计算成功的概率极低。
Holland建立的标准（或简单）遗传算法，其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30，交叉概率pc=0.95、变异概率pm=0.05，最大进化代数t=1000，每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低，对于标准遗传算法以目标函数小于-800为搜索成功，标准遗传算法运行100次。当取最大进化代数为t=200时，40次（以概率0.40）搜索到全局最优，平均计算时间为0.51秒；当取t=500时，51次（以概率0.51）搜索到全局最优，平均计算时间为1.13秒。
采用本文混合法计算，取m=30，pc=0.85、pm=0.2，t=100，进行powell搜索的概率ppowell取不同值，混合法运行100次，计算结果见如表1。对于这个具有多极值的算例，多次计算表明ppowell=0.3时，混合法能以完全概率搜索到全局最优的准确值，但是此时混合法计算时间约为标准遗传算法取t=500时计算时间的4/5。对应的浮点编码遗传算法，取m=30，pc=0.85、pm=0.2，t=100，运行100次，82次（以概率0.82）搜索到全局最优（如表1中ppowell=0所示），计算时间约为标准遗传算法取t=500时计算时间的1/8，但是搜索到全局最优的概率却远远高于标准遗传算法。
表1ppowell取不同值时混合法的计算结果
ppowell
0.0
0.02
0.05
0.1
0.2
0.3
求得最优解的次数
82
85
89
94
98
100
求得最优解的概率
0.82
0.85
0.89
0.94
0.98
1.00
平均计算时间/秒
0.14
0.20
0.31
0.47
0.68
0.87
4结束语
针对不可微函数的全局优化问题，本文提出一种把powell方法与浮点编码遗传算法相结合的混合遗传算法，该算法兼顾了遗传算法全局优化方面的优势和powell方法局部搜索能力较强的特点，提高求得全局解的概率。计算结果表明混合法优于遗传算法和powell法，可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息，本文混合法不仅适用于不可微函数优化问题，也适合可微函数全局优化问题。
参考文献
[1]周明，孙树林．遗传算法原理及应用[m]．北京：国防工业出版社，1999．
[2]GoldbergDe.Geneticalgorithmsinsearch,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]GoldbergDe．Real-CodeGeneticalgorithm,VirtualalphabetsandBlocking[J].ComplexSystems，1991，5：139-167．
[8]michalewiczZ．amodifiedgeneticalgorithmforoptimalcontrolproblems[J]．Computersmath.application，1992，23（12）：83-94．
[9]陈宝林．最优化理论与算法[m]．北京：清华大学出版社，1989．
[10]俞红梅．全过程系统能量综合方法的研究[D]．大连理工大学博士学位论文，1998．
Hybridapproachforglobaloptimaofindifferentiablenonlinearfunction
abstractahybridcomputationalintellectivealgorithmforlocatingtheglobaloptimaofindifferentiablenonlinearfunctionwasputforwardbysettingthepowellalgorithminreal-codegeneticalgorithm.thehybridapproachimprovedthelocalsearchingabilityofthegeneticalgorithmandpromotedtheprobabilityfortheglobaloptimagreatly.Becauseonlytheobjectivevaluesareused,thehybridapproachisageneralizedgeneticalgorithmforglobaloptimaofdifferentiableandindifferentiablenonlinearfunctions.
高中遗传学概率计算方法篇4
关键词：多机调度；遗传算法；模拟退火算法；混合遗传模拟退火算法
作业调度问题是生产管理与控制的一个基本问题。按照加工设备数量和加工作业的流动方式，一般可分为单机调度、并行机调度、Flowshop调度、可重入式调度和Jobshop调度等多种类型。作业调度中的许多问题，不仅具有随机性、约束复杂、规模大及多目标冲突等特点，而且许多都属于np完全问题，即使在单机情形也是如此。因此，如何寻求有效可行的调度求解方案，一直是生产管理与控制研究的热点和难点。
一、多机调度问题的数学模型
二、算法分析
自Davis首次将遗传算法（Geneticalgorithms，Ga）引入到调度问题的研究中以来，进化算法（包括遗传算法）在制造生产零件和生产调度研究领域获得了广泛的应用，并取得了较好的优化效果。遗传算法用于求解某些并行多机调度问题也有不少的研究成果。遗传算法的优点是：不受搜索空间的限制性假设的约束，不必要求诸如连续性、导数存在和单峰的假设，并且具有内在的并行性，收敛速度快，能够解决非常困难的寻优问题。当然，传统的遗传算法也有许多缺点，其中最为严重的是“过早收敛”问题。所谓“过早收敛”是指在搜索的初期，由于优良个体急剧增加使种群失去多样性，从而造成程序陷入局部，达不到全局最优解的现象。遗传算法的另一个缺陷是“Ga欺骗”问题，即在Ga的搜索过程中，有可能搜索到最优解然后又发散出去的现象。另外，遗传算法还有参数选择未能定量和不能精确定位最优解等缺陷。
模拟退火算法（Simulatedannealing，Sa）又称为模拟冷却法、统计冷却法、monte－Carlo退火法、随机松弛法和概率爬山法等。模拟退火算法是一种新的统计优化方法，其思想最早是由n．metropolis等人借鉴统计力学中物质退火方法而提出的。1983年Kirkpatrick等人开展了一些富有成效的工作，成功地将该思想引入组合优化理论。模拟退火算法源于对固体退火过程的模拟，采用meteropolis接受准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。模拟退火算法的主要优点之一就是能以一定的概率接收目标函数值不太好的状态。即算法不但往好的方向走也可向差的方向走；这使得算法即便落入局部最优的陷阱中，理论上经过足够长的时间后也可跳出来从而收敛到全局最优解。模拟退火算法的主要缺点是解的质量与求解时间长短之间的矛盾。为得到一个好的近似最优解，需要进行反复迭代运算，当问题的规模不可避免地增大时，缺乏可行的解决途径。
三、多机调度问题的混合遗传模拟退火算法
从测试结果来看，混合遗传模拟退火算法在搜优率上较遗传算法和模拟退伙算法有了较大的提高。从运算过程中的数据可以看出，由于混合遗传模拟退火算法中邻域的选择、变异发生的概率都取自模拟退火的接受概率，再加上它采取了适应度拉伸系数λ，使得遗传算法的“早熟”现象得到很好的解决。另外本文所采用的混合遗传模拟算法的还具有以下优点：①优化行为的增强。它具有Ga算法的优化时间性能和Sa算法可以最终趋于全局最优的优点，克服了Ga算法“过早收敛”问题和Sa算法优化时间性能较差的缺点。②优化效率的提高。它是一种并行而且具有自动保优功能的算法，同时利用Ga和Sa各自不同的邻域搜索结构相结合，这样使得算法在解空间中的搜索能力所增强，优化效率得到提高。③鲁棒性的提高。它的多点搜索消弱了Sa算法对初值的依赖性，同时它还利用Ga算法不影响平稳分布的特性，提高了整个算法的鲁棒性。
遗传算法和模拟退火两种算法均属于基于概率分布机制的优化算法。遗传算法是通过概率意义下的“优胜劣汰”思想的群体遗传操作实现优化；模拟退火算法的优化机制是通过赋予搜索过程一种时变和最终趋于零的概率突变性，来避免陷入局部极小而达到全局最优。本文结合这两种算法的优缺点，将模拟退火的思想引入遗传算法，将模拟退火的接受概率应用于种群的选取以及变异操作，并采用适应值拉伸的方法，极大地缓解了遗传算法的选择压力。它不但丰富和优化了整个过程，而且增强了全局和局部意义下的搜索能力和效率。从试验结果可以看出，本文的混合遗传模拟退火算法在解决多机任务调度问题时较单一的遗传算法、模拟退火算法在优化行为与效率上有了很大的提高。
参考文献：
1、许国平，叶效锋，鲍立威.基于模拟退火遗传算法的车辆路径问题研究[J].工业控制计算机.2004.24(3):58-62.
2、黄德才，郭海东，沈良忠.基于Jit的多目标并行多机调度问题的混合遗传算法[J].系统工程理论与实践.2004.24(3):58-62.
3、张婧，杨炳儒.基于混合遗传算法的聚类模式数据挖掘方法[J].微计算机信息，2006，18：219-221.
4、刘志刚，王建华，耿英三，欧阳森.一种改进的遗传模拟退火算法及其应用[J].系统仿真学报.2004.16(5):1099-1101.
5、尹文君，刘民，吴澄.进化计算在生产线调度研究中的现状与展望[J].计算机集成制造系统-CimS-2001.7(12):1-6.
6、刘民，吴澄.解决并行多机提前/拖后调度问题的混合遗传算法方法[J]自动化学报.2000.26(2):258-262.
7、姚伟力，杨德礼，胡祥培.遗传算法对车间作业调度的研究[J]运筹与管理.1999.8(2):85-88.
8、周明，孙数栋.遗传算法原理及应用.国防工业出版社.1997.
9、行文训，谢金星.现代优化计算方法(第2版).清华大学出版社.2005.09.
10、陈国良，王煦法，庄镇.遗传算法及其应用.人民邮电出版社.2001.02.
高中遗传学概率计算方法篇5
1遗传算法求解非线性方程组的改进
1.1搜索空间方面的改进搜索空间是遗传算法求解非线性方程组中由定义域D决定的一个或多个范围。搜索空间的大小，在一定程度上决定了求解的效率。曾毅［6］提出了一种将种群中的个体按照适应值从大到小排列，根据前n位个体变量的对应二进制编码最高位与最优解对应的二进制编码的最高位是否相同的情况，对搜索空间进行缩小和移动的方法。该方法使得每个变量对应的二进制编码长度无需过长，便可求出高精度的解。成媛媛等提出了根据历代最优解将搜索区间不断划分成较小的区间，不断在各个小的搜索区间递归地调用动态自适应遗传算法，直到达到精度要求或小区间宽度为零停止的方法。这一方法较好地克服了传统方法的局限性，能够在较大的初始区间上以概率为1搜索到区间内的全部解，并能较好地实现并行计算，大幅提高了一般遗传算法求解非线性方程组的收敛速度和稳定性。排新颖等提出了一种梯度的变异步长，即在迭代开始时使用大的步长来进行全局寻优，在后期基本确定真正解的区间时，采用较小的步长进行局部细化搜索。从上述文献来看，在搜索空间方面的改进，主要以动态缩小搜索空间等为主。缩小了搜索空间，意味这提高了求解的速度。因此，这些改进将是对基本遗传算法求解非线性方程组的一种有效补充。
1.2编码方面的改进综上所述，在基本遗传算法求解非线性方程组的过程中，采用了二进制编码。其在程序上易于实现，但实践发现，该编码也带来了编码和解码误差等问题。因此，曾毅，彭灵翔［10］均提出了在求解过程的编码环节使用实数编码来替代二进制编码，从而省略了复杂的编码和解码过程。实数编码虽使得设计和分析难度增加，但通用性较好，可方便地表示范围较大的数，便于在较大的空间进行搜索，同时也改善了遗传算法的计算复杂性，提高了运算效率。传统二进制编码存在Hamming悬崖问题。对于二进制编码方法表示的个体，变异操作有时虽只是一个基因座的差异，而对应的参数值却相差较大。但若使用格雷码来对个体进行编码，则编码串之间的一位差异，对应的参数值也只有微小的差别。这就相当于增强了遗传算法的局部搜索能力，便于对连续函数进行局部空间搜索。因此angelFernandoKuri－morales采用格雷码，取得了较好的使用效果。
1.3传算子方面的改进在使用遗传算法求解非线性方程组时，一般会使用到选择、交叉和变异3个算子。选择算子一般通过赌轮法，交叉和变异操作一般采用根据经验所得的固定概率。罗亚中等在算子设计时以联赛竞争算子为选择算子，该算子可直接通过比较个体的目标函数值完成操作，因此该文的遗传算法适应度函数直接选择为优化目标函数。文中采用了最优保存策略，即当前群体中最优个体不参与交叉运算和变异运算，而是用其来替代本代群体中经过交叉、变异操作后所产生的最差个体。胡小兵等通过设计特定的交叉概率和变异概率函数，实现了交叉概率pc和变异概率pm的动态改变，从而增加求解过程中算法的进化能力和收敛速度。田巧玉等采用了启发式交叉的方式，使用参数“Ratio”指定子辈离较好适应度的父辈有多远。如:父辈是parent1和parent2，而parent1有较好的适应度，则启发式交叉生成的子辈如下child=parent2+Ratio*(parent1－parent2)(4)该文中还采用了Gaussian变异算子。此变异算子在进行变异操作时，将一正态分布、具有均值的随机数加入到父向量的每一项，替换原有的基因值。该Gaussian变异算子由两个参数“Scale”和“Shrink”决定。
针对采用非线性排序，排序的结果通常易陷入局部解。徐红提出了设置参数r，将适应值差别因素以r的比例加入到选择中，能改善搜索性能。参数r的设计及由此得到的交叉概率p''''如下交叉前排序的作用使相邻个体的适应度差别最小，特性相对集中。即采用先排序后交叉可能带来两种效果:(1)加快收敛速度。(2)形成未成熟收敛。希望出现的是前一种情况，因而在搜索初期采用交叉前排序的操作以期提高搜索效率。彭灵翔等在变异算子上使用了最佳个体保留算子和灭绝与移民算子。采用最佳个体保留算子是一种常见的做法，可将有最好适应度的染色体群作为种子传到下一代。灭绝与移民算子在当池中的染色体几乎相同时，或最佳个体的适应度在一定代数内的增幅小于门槛值时起作用。灭绝与移民过程一般分为两部分，开始将最佳染色体之外的染色群全部灭绝。然后移民产生np－1个新的染色体。移民过程是:从第2个到np/2个染色体用产生初始种群的方法产生父辈染色体。其余染色体用最佳适应度的染色体通过变异产生。综上所述，对于算子的改进，主要采用动态变化来替代固定概率的方式。无论哪种改进，均以加快收敛速度和防止早熟为主要目的。从各文献提供的实验数据来看，均取得了一定的效果。
2混合遗传算法求解非线性方程组
混合遗传算法求解非线性方程组主要是通过遗传算法与其他算法相结合等手段来求解的。
与经典迭代方法的混合遗传算法中的杂交算子和变异算子能在全变量空间内搜索方程组的解，经典迭代方法能在收敛点附近局部细致地搜索解。若能将两者混合，有可能发挥好两类算法各自的优势而取得更好的求解效果。目前文献中主要提出了两类混合策略。(1)将经典迭代方法作为算法的一个遗传算子。赵明旺采用牛顿迭代算法与遗传算法结合的混合算法求解非线性方程组，其混合策略是:对子代群体中每个个体以概率pn进行牛顿算子迭代搜索，产生的新迭代值取代父代加入子代群体。该文认为确定牛顿算子概率pn的大小需考虑的因素为:1)所求解的非线性方程组牛顿法迭代过程的收敛性。若其迭代过程收敛较快，则相应的pn可取较小值。否则，则取较大值。2)预定的繁殖代数。若预定的繁殖代数较大，则相应的pn可取小一些。否则，取大一些。
进一步地，赵明旺在文献中将上述思想推广运用至求解相容非线性方程组问题，即求解方程数与变量数可能不一致的情况。罗亚中等，屈颖爽均提出了将拟牛顿法与遗传算法相结合的混合算法求解非线性方程组。文献依据自适应混合算子概率pn对群体利用拟牛顿法进行局部搜索，此文设计了两类混合算子:拟牛顿迭代混合算子和powell混合算子，并进行了分析比较。拟牛顿混合算子的构造方法是:以被选中个体的染色体为初始点进行拟牛顿迭代操作，若算法收敛则以收敛点作为个体新的染色体，若不收敛则不改变个体的染色体。powell混合算子的构造方法是:以个体的染色体为初始点进行powell寻优计算，以优化结果作为个体新的染色体。而文献的中心思想是只对每一代的最优个体利用拟牛顿法进行精细局部搜索。其文中认为自适应混合算子概率pn应该随着进化的增加而变大，最后趋近于一个常数p0，因此提出了如下公式其中，t为遗传算法中设置的最大代数;t为当前进化代数;常数p0∈(0，1］反映了局部强搜索算子对每个个体的最大可能作用程度。p0大则混合算子对遗传算法搜索空间的局部开采愈充分，但相应的计算成本愈大，此文选择p0=0.10。屈颖爽将知名的拟牛顿法—BFGS方法与遗传算法进行混合，其混合策略与赵明旺的一致，即对子代群体中每个个体以概率pn进行拟牛顿算子迭代搜索产生的新迭代值取代父代加入子代群体。值得注意的是此文利用有限markov理论建立了基于基本遗传算法与BFGS算法的混合算法的全局收敛性定理，即证明了保留当前最好解的混合算法收敛到全局最优解。王鹏进一步改进了屈颖爽的工作，主要体现在两个方面:(1)拟牛顿迭代步骤中，首先计算每个体的适应值，从中选择性能好的个体按一定的概率进行拟牛顿迭代。(2)对个体的拟牛顿迭代仅进行一次，在取得良好效果的同时节省了计算量。排新颖等考虑将梯度法与遗传算法混合，其主要思想是用梯度对最优个体进行局部寻优。选择的下降方向是待优化函数负梯度方向，设置一个步长L，在当前点进行局部寻优:若寻优后的函数值小于原来函数值的λ(λ＜1)倍，则寻优成功，更新当前个体，否则L=Lμ，直到L小于一个设定的值。
曹春红等将几何约束问题转化为非线性方程组的形式，并用牛顿迭代算法与遗传算法结合的混合算法求解，取得了较好的效果，其混合策略与赵明旺一致。周丽等提出了一种混合小生境遗传算法与拟牛顿算法求解非线性方程组的新方法，其混合策略与罗亚中等一致。对于由小生境遗传算法产生的一代种群，除最优个体外以一定的概率pn选择其中的个体采用拟牛顿法进行局部寻优，如果寻优后的个体适应度值高于寻优前的适应度值，以优化的结果替换寻优前的个体，否则说明此个体不收敛，不进行替换操作。
3采用经典迭代方法进行求解
C.L.Karr等提出了一种求解非线性方程组的混合算法，此法中遗传算法主要为牛顿迭代算法提供好的初值。此文以求取Gauss－Legendre求积公式节点与系数形成的非线性方程组为典型例子，说明了牛顿迭代算法对求解此类方程组时对迭代初始值高度敏感，而混合算法的求解效果相当不错。田巧玉等在实现遗传算法与拟牛顿法相结合的思路是:在应用遗传算法进行优化设计的基础上，采用拟牛顿法进行二次优化，将获得的结果作为最优的设计结果，即首先运行遗传算法，找到最优点附近的一个点，将它作为拟牛顿法的初始点，以找到目标函数的最小值。此文给出了遗传算法迭代终止条件有两个:一是进化到指定的最大代数;另一个是适应度限，即当前代的最佳适应度值小于或等于规定的值时就停止。吴国辉等考虑到遗传算法全局群体搜索能力及该算法在起始搜索阶段速度非常快的特点，提出先用遗传算法进行n步迭代，直至其收敛结果满足预期要求，进入拟牛顿法的收敛域之内，然后将遗传算法迭代结果作为拟牛顿法迭代初始值继续迭代至精确解。此文对遗传算法迭代的控制办法是当前群体平均适应度小于等于预先设定的精度值。
3.1与其他智能算法的混合遗传算法是模仿自然选择和遗传机制的一种智能优化算法，研究者已将其与其他智能算法如模拟退火算法等进行混合，或者融入如量子计算原理、生物免疫思想等以构造出更具优势的新的智能算法。
3.2遗传退火算法模拟退火算法是由metropolis等基于热力学的退火机制提出来的一种对退火过程进行模拟的算法。遗传算法具有较强的全局搜索能力但容易陷入早熟，而模拟退火算法具较强的局部把握能力，但全局搜索能力不足。因此对两者取长补短的遗传退火算法应运而生，并成功用于全局优化问题的求解。付振岳等将遗传退火算法进一步加以改进并应用到含有超越函数的非线性方程组的求解。
3.3量子遗传算法
量子遗传算法由narayanan等人最早提出的，并经Han等人发展的一种基于量子计算原理的概率优化方法，其用量子位编码来表示染色体，用量子门作用和量子门更新来完成进化搜索，具有种群规模小、全局寻优能力强的特点，已成功用于求解tSp与0－1背包等问题，获得了比传统遗传算法更好的效果。杜娟等提出了一种基于混合量子遗传算法的非线性方程组求解方法。为克服量子遗传算法的求解精度低和加强局部搜索能力，采用拟牛顿法作为一个强局部搜索算子，把量子遗传算法的寻优结果作为拟牛顿法的初值，取得了较好的效果。徐红提出了一种改进量子遗传算法求解非线性方程组的新方法，结果表明此法具有较高的收敛可靠性及较高的精度，对于非线性方程组求解问题具有良好的适应性，特别是一些很难求解的方程组，利用此方法求解更有意义。
3.3免疫遗传算法免疫遗传算法是近年来基于生物免疫机制提出的一种新的智能计算算法，其将生物免疫系统的学习、记忆和多样性的特点引入遗传算法。由于兼顾了搜索速度、全局搜索能力和局部搜索能力，免疫遗传算法正成为优化设计领域的研究热点之一。王景芳等提出了一种烃类蒸汽转化反应器物料衡算的非线性方程组的免疫遗传算法求解方法，取得了良好的效果。该算法由于在遗传算法的基础上引入了高斯变异和基于抗体浓度的更新策略调节机制，能有效地保持抗体的多样性，从而避免了遗传算法中存在的早熟收敛问题。
4并行遗传算法求解非线性方程组
遗传算法具有并行性，其按并行方式搜索一个种群数目的点，而不是单点。其的并行性表现在以下两个方面:一是内在并行性，本身适应大规模并行。最简单的并行方式是让若干台甚至是数千台计算机各自进行独立种群的演化计算，运行过程中甚至不进行任何通信，等到运算结束时才通信比较，选取最佳个体。这种并行处理方式对并行系统结构并无任何限制和要求，即遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，尤其适用现在pC机多线程多进程的并行计算。二是遗传算法的内含并行性。由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间的多个区域，并相互交流信息。使用这种搜索方式，虽然每次只执行与种群规模n成比例的计算，但实质上已进行了大约o(n3)次有效搜索，这就使遗传算法能以较少的计算获得较大的收益。目前并行遗传算法的实现方案分3类:主从式模式(master－Slavemodel)、粗粒度模型(Coarse－Grainedmodel)和细粒度模型(Fine－Grainedmodel)。并行遗传算法正广泛应用于各个领域，已有人将并行遗传算法用在非线性方程组求解上。刘灿文等提出一种自适应并行遗传算法:采用粗粒度模型，将初始种群分为3个子种群，并让这3个子群体按照特点互补的演化规律在并行机的3个进程上分别进化，定期移植或交换部分优秀个体。其中进程0为主进程，主要任务之一是保存自身进化而得的优秀个体并吸收另外两个进程进化而得的优秀个体，使不遭受破坏，目的在于保持优秀个体的多样性。对交叉和变异概率针对不同进程、不同阶段设置不同的值，来提高进化效率，如进程0中的子群体在进化中具有较低的交叉率和变异率，使得优秀个体不易被破坏，而对进程1和进程2用较高的交叉率和变异率，尤其在进化后期，用以探测新的超平面上的优秀个体，不断为进程0提供新的超平面上的优秀个体，防止进程0“早熟”并加快其收敛到全局最优的速度。付振岳等［35］针对一些复杂的含有三角函数或是对数的非线性方程组用遗传算法进行求解，由于该类问题涉及的求解空间大，遗传算法需要更大的初始化种群，为提高算法的性能，引入了并发机制和最大堆来提高硬件利用率和降低某些关键步骤的时间复杂度。根据CpU的利用率和计算等待时间的比率以及CpU的个数，设置合适的线程数，采用细粒度模型，将种群根据线程数分割成相应的组群，每个线程对组群先后进行堆初始化交叉堆初始化变异堆初始化淘汰等操作，设置一个全局变量记录全体线程在执行遗传退火算法中产生的最优个体，每个线程在完成一轮遗传退火行为后，将本组群的最优值与全局最优值进行比较，若本组群最优值优于全局最优值，则用本组群最优值替换全局最优值，反之，则用全局最优值替换本组群最优值。该算法有效地提高了遗传退火算法的性能，加快了求解的速度。
5结束语
高中遗传学概率计算方法篇6
遗传算法是模拟自然界生物遗传和进化的过程，以群体共同进化的形式搜索一个问题的最优解。群体中每个个体并行的进行适应度评价、选择算子、交叉算子和变异算子等操作并产生新一代个体。交叉算子模仿自然进化过程中两个同源染色体通过而重组产生新的染色体。交叉有一定概率可以结合两染色体的优良基因产生更优的个体，交叉算子是累积优良模式的主要环节。变异算子模拟自然界中基因突变，使复制给新个体的染色体中的基因有一定概率转化为其等为基因。适应度评价算子评价每个个体的表现型求最优解的优良程度，为优胜劣汰提供依据。选择算子是模拟自然界优胜劣汰的过程，以较高的概率保留适应度高的基因，激励好的特性在群体中扩散。选择算子在根据适应度选取的基础上具有一定的随机性，因为选择要容忍一定量的较劣个体的存在以保持种群基因的多样性，保证搜索的全局性，防止算法出现早熟现象。
改进小生境变种群规模遗传算法
为使遗传算法对于复杂的约束和目标函数有较好的稳健性和收敛速度，本文介绍了一种带有小生境技术的变种群规模的遗传算法。讨论了种群规模的周期性波动对进化的促进作用，引入了一种新的对约束的处理方法，并改变了选择算子的意义，引入配对算子，规定多父代竞争。整体的程序流程图如图1．
1种群规模波动
传统的遗传算法一般采用固定种群规模。然自然界中大的生物进化一般都与种群规模的大幅度波动同时发生。生物进化可以分为两个阶段，第一阶段环境稳定种群规模缓慢上升，优良基因逐渐产生与积累;第二个阶段，环境发生灾变种群规模下降，优良基因得到选择并在种群中扩散。改进的遗传算法采用变种群规模规则，种群中个体存活多代，并根据其适应性以某概率被淘汰，存活下的个体按其竞争性依概率交叉配对产生新个体。采用改变约束条件惩罚的苛刻程度的方法使种群规模周期性波动，从而逐步催生优良基因。设定惩罚苛刻程度的系数为:
2二维小生境
在自然界中，生物一般总和特征相似的生物生活在一起，繁殖后代。又加上地理位置的限制，基因与外界交流得到限制，一个区域的生物群形成一个基因相对独立的小生境。在传统的遗传算法中，选择、交叉算子在整个群体内进行，所有个体的基因交流没有限制，相对优良的基因会很快的在整个种群内扩散，个体很难保持各自的进化方向，整个种群趋于收敛于一个解。故传统的遗传算法很容易出现早熟现象。为改进算法的全局收敛性，引进小生境的概念，将个体的基因交流限制在一个小区域内进行。如图2所示，在改进的遗传算法中，采用一种位置争夺的小生境技术。将群体投影到一个二维空间。初始种群中个体不会占满全部空间，而是几个个体聚集在一起组成一个初始的子种群，每个子种群之间有一定空间距离。个体在其小生境内进行交叉和配对算子。新生的个体在由母体限定的空间区域内。子种群间会争夺有限的空间，最终使优良基因占有更大空间。
3对目标函数和约束的处理
机械产品的设计要优先考虑满足约束，故机械的优化设计一般为约束优化问题。用遗传算法优化时，处理约束比较常见的方法有如下几种:(1)将不符合约束的个体直接从群体中剔除。(2)采用惩罚函数法，为常用的方法。这种方法要根据不同的约束定义惩罚函数，惩罚函数选取不当将很大的影响优化的收敛速度，或算法很难找到可行解，即使偶然找到，解很差。()采用特殊的编码技术，避免产生不满足约束的解，或采用修复技术，但只适用于个别特殊的优化问题。
考虑到在优化设计时以满足约束优先的原则，受到自然界进化机制的启发，将目标函数与满足约束分别用配对和选择两个算子进行搜索。用选择算子淘汰不满足约束的个体，用配对算子挑选下一代个体的父本，使的竞争性高的个体有更大的机会与母本配对。遗传算法在对所有个体进行目标函数和约束的计算评估出适应性和竞争性后，先通过选择算子淘汰部分个体，再从剩余个体中以每个个体为母本，从此个体的一个邻域通过配对算子得到父本，进而进行交叉算子产生新个体。
4编码
在遗传算法搜索过程中，算法不是直接对求解问题的决策变量进行操作，而是通过编码将解空间投射到基因空间，通过交叉，变异对基因进行操作，这是遗传算法的特点之一。编码是应用遗传算法解决实际问题时要考虑的首要问题，大部分情况下它是影响遗传算法运行效率的主要因素之一。常用的编码方法有:二进制编码法、灰码编码法，浮点数编码法，符号编码法。对于机械优化的问题，设计参数存在尺寸参数等连续值和结构、形状、材料型号等离散量。为保证编码的通用性，采用对离散值和连续值都兼顾的灰码进行编码。
5交叉算子
对于二进制编码的遗传算法，常用的交叉运算方法有单点交叉、双点交叉、均匀交叉等。根据模式理论，为保存优良模式，交叉点选取应越少越好。但如图所示，单点交叉实际上可以看成是默认以基因段开头与末端为一个交叉点的双点交叉，因此单点交叉对在染色体上不同分布的模式保留的概率不同。故采用模式保留概率稳定的双点交叉算子。交叉的另一个问题是交叉点的选取。交叉点选取一般的方法为等概率的随机选取。等概率选取交叉点可能存在交叉两片段的基因型相同的情况，则交叉运算后是基因型未改变，降低了交叉效率。故在交叉中剔除相同基因型的交叉
6变异算子
采用均匀变异算子，对于复制给新个体的每个基因都以父本的变异率变异成其等位基因。变异率会根据个体的适应性在基本变异率的基础上做
7选择算子
传统的遗传算法每个个体只生存一代。选择算子的作用是为配对、交叉产生下一代提供父本。选择算子将适应度高的个体有较高的概率遗传到下一代，适应度较低的个体有较低的概率遗传到下一代。本文提出的遗传算法规定种群的规模是可变的，并且每个个体可以存活一代以上。在改进的遗传算法中选择算子的作用是选择群体中将生存到下一代的个体。根据满足约束的程度计算出适应性，让适应性低的个体有更高的概率被淘汰。选择只保证选择个数的期望为与群体规模成固定比例，个体给选择的概率与个体适应度成正比，本算法的适应度是以满足约束为表征。
8配对算子
配对是在基因池中为交叉运算选出一对父母本的过程，是选择算子与交叉算子的中间过程。常用方法是随机配对。本例中的配对是在小生境的范围内进行的，配对的过程中根据个体的竞争性即目标函数值得优劣进行选择。种群中每个存活2代以上的个体在配对算子中都有一次机会作为母本，在小生境的范围内由近到远顺时针选择父本。目标个体被选择为父本的概率与其在小生境内竞争性的排名成正比。
实验与结果分析
机械问题的模型可分为连续函数问题和组合优化问题两类。为验证改进的遗传算法的性能并证明其在机械设计中的可行性，做了如下几组实验。首先通过解装箱问题验证变种群对搜索速度的影响，之后通过对比改进的遗传算法、微粒群算法和标准遗传算法在解决装箱问题以及工程实中的减速箱齿轮组设计和起重机主梁截面设计问题等三个问题的优化结果检验算法的优化性能，验证改进遗传算法的意义。
1种群规模变化对进化的影响实验
此部分采用的实验模型是组合优化中经典的装箱问题。为验证本文提出的种群规模周期性波动有利于促进种群进化的假设，设计改变种群规模波动幅度的实验。通过改变选择算子中的基本惩罚系数ke0来调节种群规模波动的幅度。本例中按波动从小到大分别进行了三组实验，波动幅度分别为，第一组幅值为0．5;第二组幅值为1;第三组幅值为1．5．上述实验结果均为20次独立重复实验最优个体的目标函数和约束值平均值。实验的结果如图4所示，第二组的优化结果最好，其中有15%能达到最优解4，平均结果为4．85;第三组次之，均能优化到次优解;而波动最小的第一组结果最差，有0%的解只能得到再次优解，平均结果为5．．三组实验的选择比例的平均值均为0．2，只有波动的大小不同。而从实验结果可以看出，种群规模适当的波动可以提高遗传算法的搜索效率和搜索结果，但当波动过大时又会降低搜索结果。可见，种群规模波动对进化具有实际作用。
2改进的遗传算法与其他算法的比较
为验证本文提出的遗传算法的优化性能，以基本遗传算法(SGa)、微粒群算法(pSo)与此处提出的变种群小生境遗传算法(这里简称DGa)做比较。(1)装箱问题本单元做了20重物装16箱、50重物装16箱的两组实验。第一组三种算法结果大致相同，第二实验结果如图5所示。可以看出，三种算法虽然搜寻速度大致相同，但改进的遗传算法能得到更优的最优解。本试验采用直尺圆柱齿轮二级减速器的模型，减速器设计条件为高速轴输入功率为6．2kw，高速轴转速n=1450r/min，总传动比i=1．5，齿宽系数φn=0．4;齿轮材料和热处理:大齿轮钢45、正火HB取值范围为187～207，小齿轮钢45、调质HB取值范围为228～255．要求按总中心距最小来确定总方案中的各主要参数。设计变量取为:()桥式起重机主梁截面的优化桥式起重机主梁，以箱形截面为基本结构，取箱形截面的主要尺寸为设计变量，在满足使用性5结束语遗传算法是对自然界的生物遗传进化的模拟，但是传统的遗传算法在种群规模、交叉繁殖和个体更替等方面的模拟过于简化，实际上弱化了每个个体在群体进化中能起的作用，使得遗传算法很难在解决复杂的问题时保持算法的稳定性，很难收敛于最优解。
高中遗传学概率计算方法篇7
关键词：网络负载平衡；遗传模拟退火
中图分类号：tp311文献标识码：a文章编号：1009-3044(2008)17-21415-03
网络负载平衡是分布式作业调度系统的一种实现。在并行分布计算中，负载平衡牵涉到把一个问题分成一系列能够并行处理的小任务，并且把每一个任务分配到合适的计算资源上，这样的计算资源有可能是一个处理机，也有可能是一台计算机。当作业量不断增加的时候，就有可能出现有的处理器或计算机因系统负担过重而导致性能下降或者死机，而有的处理器则因空闲而浪费资源。网络负载平衡研究的目标就是如何研究一些可以将负载平衡地分配给网络内的各个处理器（计算机）的策略方法，使得整个问题的处理时间减短，而计算资源的利用率得到最大化的利用。
1负载平衡问题的数学模型[1]
负载平衡问题的数学模型可以描述为：假设系统由m台处理计算机组成，依次标记为p0,p1,…,pm-1，处理机之间通过线路进行连接，为了便于评测系统的平衡性，用每台处理机所拥有的数据数来表示其负载，记为w[i]，整个系统的总负载可表示为w=∑w(i)，其中0≤n-1，系统的平均负载为w*=w/n。
2遗传模拟退火算法
遗传算法和模拟退火算法是较为常用的两种智能优化算法，而且各有优缺点，将这两种算法有机地结合在一起，应用于网络负载平衡问题的解决，会取得更好的结果。
2.1遗传算法
遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接收，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理决策等领域得到了广泛的应用。遗传算法给我们呈现出的是一种通用的算法框架，该框架不依赖于问题的种类。遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非线性系统，它更表现出了比其他传统优化方法更加独特和优越的性能。隐含并行性和全局搜索特性是遗传算法的两大显著特征。
2.2模拟退火算法
模拟算法是基于menteCarlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。
在金属热加工工艺中，退火是指将金属材料加热到某一高温状态，然后让其慢慢冷却下来这样一个金属热处理过程。从统计热力学的观点来说，随着温度的降低，物质的能量将逐渐走近于一个较低的状态，并最终达到某种平衡。
模拟退火算法就是基于金属退火的机理而建立起的一种全局最优化方法，它能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。
2.3遗传算法与模拟退火算法的结合
遗传算法由于其运算简单和解决问题的有效能力而被广泛应用到众多的领域。理论上已经证明，遗传算法能从概率的意义上以随机的方式寻求到问题的最优解。但另一方面，应用实践表明，在遗传算法的应用中也会出现一些不尽人意的问题，比如收敛较慢且易陷入局部极值点。另外，遗传算法也无法避免多次搜索同一个可行解，这也是影响遗传算法运行效率的一个因素。
另一方面，梯度法、爬山法、模拟退火算法、列表寻优法等一些优化算法却具有很强的局部搜索能力，而另一些含有问题与相关知识的启发式算法的运行效率也比较高。比如模拟退火算法对具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解。可以预计，在遗传算法的搜索过程中整合这些优化方法的思想、构成一种混合遗传算法(HybridGeneticalgorithm)是提高遗传算法运行效率和求解质量的一个有效手段。
遗传模拟退火算法的结构如图1所示：
遗传模拟退火算法可以理解为在遗传算法中引入模拟退火算法的思想，这有效地缓解了遗传算法的选择压力，并对基因操作产生的新个体实施概率接受版图，不但增强了算法的全局收敛性，而且使算法在优化后期有较强的爬山能力，加快了进化后期的收敛速度。另一方面，遗传模拟退火算法以遗传算法控制寻优的方向，发挥搜索速度快的特点；而用模拟退火算法解决局部收敛的问题，以提高搜索精度。充分发挥了遗传算法的快速全局搜索性能和模拟退火算法的局部搜索能力，因此具有较高的效率和广泛的适用性。
2.4遗传模拟退火算法的基本步骤
简单地说，遗传模拟退火算法的特点在于利用模拟退火算法克服遗传算法的早熟问题，利用遗传算法克服模拟退火算法对初值的依赖性。以下是该算法的一种基本结：
(1)给定群体规模n,k:=0；初始温度tk:=t0，群体pop(k)；
(2)若满足停止规则，则停止计算；否则，在群体pop(k)中每一个染色体i∈pop(k)的领域中随机选一状态j∈n(i)，按模拟退火中的接受概率aij(tk)：(1)
接受或拒绝j，其中f(i)为状态i的目标值，其中f(j)为状态j的目标值，这一阶段n次迭代选出新群体newpop1(k+1)。
(3)在群体newpop1(k+1)中计算适应函数fi(tk)：
(2)
其中fmax是newpop1(k+1)中的最大适应值；按由适应函数决定的概率分布从newpop1(k+1)中随机选n个染色体形成种群newpop1(k+1)。
(4)按遗传算法的常规方法进行交叉得到crosspop1(k+1)；再变异得到mutpop1(k+1)。
(5)tk+1=d(tk)，k=K+1，pop(k)=mutpop1(k+1)，返回第二步。
在遗传模拟退火算法中，在第二步的群体选择时随机搜索了每一个体的领域，选择的范围比单纯的遗传算法要大，实际上是用所有个体的领域取代遗传算法中的，而且采用metropolis准则由式(1)所确定的概率选取，这是模拟退火的一个显著特征。式(2)是一个加速适应值尺度变换函数，在温度较高时加速性不明显，当温度较低时加速性非常显著，是根据退火的第二个特征。第四步中的交叉和变异操作与一般遗传算法中的处理方法一致。
3应用实例
在这一小节中，我们将用一个实际的例子来说明遗传模拟退火算法在网络负载平衡中的应用。
假定我们在一个拥有4台服务器的网络中对16个任务进行网络负载平衡的规划，并且这16个任务各自独立，相互之间没有依存关系，同时这16个任务完成所需要的时间各不相同。
设定实例的任务编号，所需时间如表1所示。
3.1编码
利用遗传算法求解优化问题时，先要将实际问题转换成由基因按一定结构组成的染色体或个体，这一转换操作我们称之为编码。编码的方式比较灵活，在这里，我们设定一个三元组为个体的基因：(i,m,n)，其中，i为任务的编号，m为完成任务所需的时间，n为网络中该任务被分配到的服务器(处理机)编号。例如(1,2,3)表示编号为1的任务所需的完成时间是2个单位时间长度，它被分配到了3号服务器(处理机)上。于是，仿真实验中，一个染色体就可以表示为｛(i,m,n)1≤i≤16,0
3.2初始群体的产生
为了满足遗传算法的群体型操作的需要，必须为遗传操作准备一个若干初始解组成的初始群体。我们设定初始群体规模为20，给定的16个任务编号为1至16，任务完成所需要的时间已知，即三元组(i,m,n)中i和m已经确定。在1至4中随机选择一个数字分配给16个三元组，组成一个染色体，即：｛(1,5,1),(2,6,2)(3,8,2)…｝，共随机产生出20条染色体，生成群体。
3.3适应度函数
遗传算法使用目标函数即适应度函数来评估个体或解的优劣，并作为以后遗传操作的依据。对适应度函数的唯一要求是，针对输入可计算出能加以比较的非负结果。由于是研究负载平衡问题，故利用方差和作为适应度函数。具体如下：
设所有任务完成的时间和为t，服务器的个数为，则理想状态下每台服务器的平均负载为w*=t/n。对于每一个染色体来说，每一个处理器上的任务总完成时间w与w*的差越小越好，故适应度函数为，F的值越小，则染色体的适应度越好。
3.4模拟退火操作
遗传模拟退火算法中的模拟退火操作主要是在个体选择阶段，在这一阶段中，由于遗传算法只选择适应度最好的，而对适应度较低的染色体选择的机率很小，所以容易出现过早收敛的问题，故引入模拟退火算法，使适应度较小的染色体同样有机会被选中，从而跳出局部最优，有利于寻找到全局最优解。我们取初始温度t0为50度，降温系数为0.95。
3.5实例结果及对比
以假定任务为基础，利用VC++编写仿真程序，分析利用普通遗传算法和模拟退火算法进行运算，在初始群体规模、交叉概率、变异概率及遗传代数相同的情况下，得到如下运算结果，
由实验结果可以得出，遗传模拟退火算法比普通的优化算法具有更好的寻求最优解的性能，在相同的条件下，寻找到最优解的概率更大。
4结论
遗传模拟退火算法是遗传算法和模拟退火算法相结合的一种优化算法。遗传算法的并行处理和快速收敛的特点和模拟退火跳出局部最优的能力得以保存，两种不同的领域结构有机结合，搜索效率更高。
本文首次将遗传模拟退火算法应用于网络负载平衡，给出了该算法的结构与运算过程，并通过一个实例证明了其在网络负载平衡方面的有效性，为进一步利用智能化算法解决网络负载平衡问题打下了基础。
参考文献：
[1]彭国震,邱毓兰,彭德纯.若干随机型负载平衡算法[J].计算机工程,27(2):22-23.
[2]林凡,杨晨晖.一种动态网络负载平衡集群的实践方法[J].厦门大学学报(自然科学版).42(4):534-535.
高中遗传学概率计算方法篇8
关键词:智能天线;波束形成;方向图;遗传算法;人类繁殖现象
beam-formingofsmartantennabasedongeneticalgorithm
wulin-jing,lijing-hua,wangjing,nining
(departmentofelectronicengineering,northwesternpolytechnicaluniversity,xi’an710072,china)
abstract:inordertoreducetheside-lobelevelanddeepthenullofsmartantennapatterns,animprovedreal-codedgeneticalgorithmisproposed.thealgorithmimprovesthecrossoveroperatorofstandardgeneticalgorithmbasedonhumanreproductionphenomenon(hrga).so,theslowconvergenceandlocaloptimumofstandardgeneticalgorithmareresolvedandtheconvergencespeedisenhanced.takinganexampleofuniformlineararrayinsimulationexperiment,amplitudeoftheelementexcitedcurrentisoptimizedthroughimprovedga,thepatternisbetter.
keywords:smartantenna;beam-forming;pattern;geneticalgorithm;humanreproductionphenomenon
0引言
智能天线波束形成是通过优化阵元的电流幅度或相位或阵元间距,使天线主波束对准期望信号,旁瓣和零陷对准干扰信号,从而接收有用信号,抑制干扰信号。www.lw881.com由于天线优化问题中的目标函数或约束条件呈多参数、非线性、不可微甚至不连续,因而基于梯度寻优技术的传统数值优化方法无法有效求得工程上满意的结果。而遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,是一种高效、并行、全局搜索的方法,能自适应地控制搜索过程以求得最优解[1]。
但是在智能天线应用领域中,标准遗传算法存在早熟,后期收敛速度慢、计算复杂等问题,于是提出了一些改进的遗传算法。文献[2]提出了一种基于排序的实数编码遗传算法,并应用于唯幅度控制等间距天线阵方向图综合。文献[3]提出交替使用两种遗传繁殖操作产生后代群体,以摆脱收敛对初始群体选择的依赖,应用于超低副瓣线阵天线的方向图综合;文献[4]采用复数编码,并用三个父代染色体线性交叉产生子代个体,将适应度高的个体选择到下一代。针对在标准遗传算法中,由于近亲繁殖,导致很多交叉操作无效的问题,对遗传算法的交叉算子进行了改进,并对阵元激励的幅度进行了优化。实验结果表明,提出的改进方法是有效的。
1基于遗传算法的波束形成
1.1遗传算法基本步骤
遗传算法的设计过程中包含了参数编码方式的选用、初始群体的建立、适应度函数的构造、遗传操作的设计、控制参数的设定。算法的收敛性取决于这五个方面的设计及数值精度和收敛速度的一些折衷。
(1)编码
采用实数编码,直接将阵元的激励电流幅值依次排列构成一个染色体,如:i=[i1,i2,…,in],n为阵元数目。
(2)选择
采用最佳保留选择,即首先通过赌方式选择染色体,然后选择当前种群中最高适应度值的染色体,作为父代染色体,直接保留到下一代,保证算法终止时最后结果为出现适应度最高的个体。
(3)交叉
采用线性交叉产生新个体,设两个父代个体分别为p1,p2:
c1=(2p1+p2)/3
c2=(p1+2p2)/3
c3=(p1+p2)/2
(1)
从c1,c2,c3中选出适应度较高的两个作为后代个体。
(4)变异
采用非均匀变异,对原有的个体做一随机扰动,以扰动后的结果作为变异后的新值。设要变异的个体为p,变异后为p′。
p′=αp
(2)
式中:α为[0,1]之间的随机数。
1.2改进的遗传算法
在遗传算法中,交叉操作是最重要的,是决定算法收敛性能的关键。但是标准遗传算法中,由于近亲繁殖,导致很多交叉操作无效,大大影响算法的收敛速度,甚至不能收敛到全局最优解。出现这一现象的根本原因是:当种群进化到一定阶段时,种群中会出现许多相同或相近的个体,很难产生出新的优良个体,而且两个父代个体中相同的基因越多,交叉操作产生出新个体的概率就越小,操作无效的概率就越大。
针对以上问题,根据人类的繁殖方式,个体必须进行严格的远缘繁殖,对父代个体在交叉之前进行亲缘关系的检测,检测为近亲的父代个体不能直接交叉,要对其进行修正。文献[5]中对相关性进行了定义,并去掉所有与该个体不相关指数为0或1的个体,从而避免出现无效的交叉操作;文献[6]中把适应度小的个体表现型编码的高位修改为与适应度大的个体表现型编码的高位不同的值。
亲缘关系检测及修正方法改进为:通过比较两个个体每个变量的相似度来检测亲缘关系,d=p1(i)-p2(i),其中,p1(i)和p2(i)分别为个体p1,p2的第i个变量,如果d小于或等于一个较小的正数,例如d=0.001,则两变量相似,若两个个体中相似的变量个数超过个体长度的50%,则两个个体视为近亲,不能直接交叉,对其中适应度小的个体进行随机扰动。这样增加了群体中个体的多样性,有助于跳出局部最优,达到全局最优。
1.3线阵模型
考虑由2n个各向同性辐射单元组成的均匀直线阵天线,则天线波束(方向图)为:
f(θ)=∑2ni=1iiejβiejk(i-1)dcosθ
(3)
式中:ii和βi分别是第i个阵元激励的幅度和相位;k=2π/λ为波数;λ为波长;d为阵元间距;θ为信号方向入射角。
利用方向图的对称性,可以减少待优化变量的数目,加快收敛[7]。若阵元激励幅度关于阵中心对称,相位相等且均为0,则线阵天线的归一化方向图为:
f(θ)=20log[∑ni=1iicoski-12dcosθ/∑ni=1ii]
(4)
2实验结果与分析
天线方向图由阵元数目、分布形式、阵元间距、阵元的激励决定,控制这几个因素可以改变波束特征,如主瓣形状、副瓣电平、形成零陷等。其中,最大相对旁瓣电平和零点深度是评价天线性能的重要参数,在阵元数目、阵元间距一定的情况下,用改进的遗传算法对阵元激励的幅度进行优化,以降低最大相对旁瓣电平,以及加深干扰方向零点的深度。
2.1目标函数
目标函数可定义为:
f=msll
(5)
式中:msll为最大相对旁瓣电平,计算公式为msll=maxθ∈s{f(θ)},max为求最大值函数;s为方向图的旁瓣区域,如果主瓣的零功率宽度为2θ0,则:
s={θ|0≤θ≤90°-θ0或90°+θ0≤θ≤180°}
一般情况下,希望msll满足期望值外,还应使在给定nn个方向θi(i=1,2,…,nn)形成一定深度的零点,因此,目标函数还可定义为:
f=αmsll-slvl+βmaxi=1~nn{f(θi)}-nlvl
(6)
式中:slvl为msll期望值;nlvl为零点深度期望值;α和β为权系数,本文令α=1,β=0.1。
2.2遗传参数的设定
(1)群体规模m
群体规模的大小直接影响到遗传算法的收敛性或计算效率。规模过小,容易收敛到局部最优解;规模过大,会造成计算速度降低。群体规模一般取20～200。
(2)交叉概率pc
遗传算法的参数中,交叉概率的选择是影响遗传算法行为和性能的关键,直接影响算法的收敛性。交叉概率越大,新个体产生的速度就越快,然而,交叉概率过大,遗传模式被破坏的可能性也越大,这将使具有高适应度的个体结构很快就会被破坏;但是如果交叉概率过小,会使搜索过程缓慢,以致停滞不前。通常交叉概率pc取0.6～0.9。
(3)变异概率pm
变异在遗传算法中属于辅助性的搜索操作,它的主要目的是保持群体的多样性。如果变异概率取值过小,就不易产生新的个体;如果变异概率取值过大,遗传算法就成了纯粹的随机搜索算法。通常变异概率pm取0.001～0.1。
(4)遗传算法的终止进化代数t
遗传运算的终止进化代数作为一种模拟终止条件,一般视具体问题而定,t取值在100~500之间。
2.3实验结果
实验1:令n=16,d=λ/2,主瓣的零功率宽度为20°,主波束指向为90°,阵元激励电流的幅度ii∈(0,1),以降低最大相对旁瓣电平为目标,目标函数选取式(5),图1中实线是本文改进遗传算法形成的方向图,点虚线是标准遗传算法(直接采用算术交叉)形成的方向图,前者的最大相对旁瓣电平比后者低41356db。
图1降低最大相对旁瓣电平的方向图
实验2:要求在67°方向形成零点,目标函数选取式(6),旁瓣电平期望值slvl=-30db,零点深度期望值nlvl=-60db,图2中实线是本文改进遗传算法形成的方向图,点虚线是标准遗传算法(直接采用算术交叉)形成的方向图。前者的最大相对旁瓣电平比后者低3.1112db,零点深度低22.2347db。
图2在67°方向形成一个零点的方向图
实验3:要求在40°,50°和60°三个方向形成零点,目标函数、slvl及nlvl与例2相同,图3中实线是本文改进遗传算法形成的方向图,点虚线是标准遗传算法(直接采用算术交叉)形成的方向图,前者的最大相对旁瓣电平比后者低12312db,在60°方向零点深度低20.1052db。
图3在40°,50°和60°三个方向形成零点的方向图
3结论
将改进的遗传算法用于智能天线波束形成,仿真结果表明,形成的方向图与标准遗传算法相比,得到了较好的结果。说明对遗传算法所作的改进,在智能天线中降低旁瓣电平以及一定深度零点的形成方面,有很好的应用前景。但是,本文仅对阵元激励的幅度进行了优化,还可以通过同时优化幅度和相位或阵元间距来满足天线的设计要求。
参考文献
[1]雷英杰,张善.matlab遗传算法工具箱及应用[m].西安:西安电子科技大学出版社,2002.
[2]马云辉.阵列天线的遗传算法综合[j].电波科学学报,2001,16(2):172-175.
[3]李东风,龚中麟.遗传算法应用于超低副瓣线阵天线阵方向图综合[j].电子学报,2003,31(1):82-83.
[4]fanyu,jinrong-hong.synthesisofantennausingamodifiedcomplexnumbercodedgeneticalgorithm[j].ieee,2004,8(4):2667-2669.
[5]蔡良伟,李霞.遗传算法交叉操作的改进[j].系统工程与电子技术,2006,28(6):925-927.
高中遗传学概率计算方法篇9
【关键词】遗传学计算数学思想
1.遗传学中的份数与种类（数学中的排列与组合）
在遗传学中孟德尔的两对相对性状的杂交实验中遗传图解如下：
在图解中后代的表现型和基因型都是16份，但是同学们在理解的时候都会误认为表现形和基因型是16种，我们如果用数学中的排列与组合应该理解为16种组合方式，有9种遗传因子组成和4种表现型，在这里表现型应该是4种分别是黄色圆粒、黄色皱粒、绿色圆粒、绿色皱粒，其比例为9：3：3：1，比例之和是16份;基因型有9种YYRRYyRRyyRRYYRrYyRryyRrYYrrYyrryyrr，其比例为1：2：1：2：4：2：1：2：1，比例之和是16份。这样就可以巧用数学妙解遗传。
2.遗传学中的概率（已知概率和未知概率）
在这里我们要求的是同学们分清遗传学中分离定律概率的巧妙运用，比如说一对表现型正常的夫妇生了一个白化病的小孩，请问他们生了一个正常的小孩和再生一个小孩，在这两种情况下有什么区别？遗传图解如下
4号个体是一个已经出生的个体，他的表现型一定正常（概率100%），且他是aa的概率是1/3，他是aa的概率是2/3;然而5号个体是一个还没有出生的个体，这个个体是aa的概率是1/4，是aa的概率是2/4，aa的概率是1/4（正常的概率是3/4，患病概率是1/4），在这里我们应该把概率分为两种即事件已经发生的概率（已知概率）是1/3和2/3，事件还没有发生的概率（未知概率）是1/4、2/4、3/4，这样就可以分清楚如何的利用概率了。
3.遗传学概率的应用（乘法原理和加法原理）
（1）乘法原理：当某一事件发生时，不影响另一事件的发生。这两个事件同时发生的概率等于它们单独发生的概率的乘积p（aB）=pa・pB，
（2）加法原理：当一个事件出现时，另一个事件就被排除，这样的两个事件为互斥事件，这种互斥事件出现的概率是它们各自概率之和。
在我们的遗传学里面也会涉及这样的计算，例如，已知控制两种遗传病的基因分别位于两对同源染色体上，甲病的发病率是a，乙病的发病率是b，则既患甲病又患乙病的概率是ab（乘法原理），只患甲病的概率是a（1-b），只患乙病的概率是b（1-a）（乘法原理）;患一种病的概率是a（1-b）+b（1-a）=a+b-2ab，患病的概率是a（1-b）+b（1-a）+ab=a+b-a（加法原理），合理的利用乘法原理和加法原理快速解决遗传题。
4.基因自由组合定律中的分离定律（合理利用数学展开式）
已知杂交亲本的基因型、等位基因间为完全显性关系且各对基因间独立遗传，（1）求子代基因型：①求子代基因型的种类②求子代基因型的类型③求子代个别基因型所占的比例（2）求子代表现型①求子代表现型的种类②求子代表现型的类型③求子代个别表现型所占的比例，例如基因型为YyRr的个体自交，后代能产生多少种基因型比例是多少？有哪些种类比例是多少？
展开式：（a+b）×（c+d）=ac+ad+bc+bd
分解：Yy×YyYY：2Yy：yy（3黄色：1绿色）
Rr×RrRR：2Rr：rr（3圆粒：1皱粒）
（3黄色：1绿色）（3圆粒：1皱粒）=
9黄色圆粒、3黄色皱粒、3绿色圆粒、1绿色皱粒
（YY：2Yy：yy）（RR：2Rr：rr）=
1YYRR2YyRR1yyRR：2YYRr4YyRr2yyRr1YYrr2Yyrr1yyrr
在合理利用展开式后相关问题迎刃而解。
5.遗传题巧解中系数的合理分配
p：黄色圆粒YYRR×绿色皱粒yyrr
F1黄色圆粒YyRr×黄色圆粒YyRr
F29黄色圆粒、3黄色皱粒、3绿色圆粒、1绿色皱粒
9YR3Yrr3yyR1yyrr
表现型系数的分配：
9黄色圆粒=3黄色×3圆粒3黄色皱粒=3黄色×1皱粒
3绿色圆粒=绿色×1圆粒1绿色皱粒=1绿色×1皱粒
基因型整数系数的分配
9YR=（1YY+2Yy）（1RR+2Rr）=1YYRR2YyRR2YYRr4YyRr
3Yrr=（1YY+2Yy）rr=1YYrr2Yyrr
3yyR=yy（1RR+2Rr）=yyRR2yyRr
1yyrr=1yy×1rr
基因型分数系数的分配
在YR中YYRR=1/9YyRR=2/9YYRr=2/94YyRr=4/9
在Yrr中YYrr=1/3Yyrr=2/3
在yyR中yyRR=1/3yyRr=2/3
高中遗传学概率计算方法篇10
【关键词】逐对分析遗传题
【中图分类号】G633.91【文献标识码】a【文章编号】1006-5962(2012)05(b)-0111-01
常常听见学生这样说,高中生物必修2中遗传题很难分析,遗传所涉及的概率计算更是难上加难,不知从何做起。面对这样的问题,我在教学过程中认识到,活用逐对分析法解遗传题可以大大提高解题效率,而且还可以激发学生学习遗传学的热情。
逐对分析法是指把不同对的基因分开,单独分析每一对基因的情况,再把每一对基因的分析结果综合起来考虑,得出结论的方法。下面从几个方面来说明如何活用逐对分析法解遗传题。
1用逐对分析法计算后代配子种类数、基因型种类数
例1:基因型为aabbCC与aaBBcc的小麦进行杂交,这三对等位基因分别位于非同源染色体上,求F1杂种形成的配子种类数和F2基因型种类数分别是多少？
解析:本题直接用棋盘法综合三对等位基因一起求解,过程非常繁琐,而且容易出错,而用逐对分析法,先求每一对基因的F1杂种形成的配子种类数和F2基因型种类数,再把计算结果综合起来计算即可得出所求的问题,解答方法如下:
aabbCCaaBBccaaBbCc(F1),F1中aa能产生a和a这2种配子,Bb能产生B和b这2种配子,Cc能产生C和c这2种配子,根据基因的自由组合定律可知F1杂种形成的配子种类数为:222=8种;F1自交得F2,aa自交能产生aa、aa和aa这3种基因型,Bb自交能产生BB、Bb和bb这3种基因型,Cc自交能产生CC、Cc和cc这3种基因型,根据基因的自由组合定律可知F2基因型种类数为:333=9种。
答案:8种9种。
由此可见,方法的选择非常重要。所以我们在做题时,应认真分析题目给出的已知条件,然后选择比较好的方法再来解题,可以提高做题的效率。
2用逐对分析法计算后代基因型和表现型不同于亲代的概率
例2:在完全显性条件下,基因型aaBbCc与aaBbcc的两个亲本进行杂交(这三对等位基因是独立遗传的),其子代中基因型和表现型不同于双亲的个体分别占全部子代的多少？
解析:先用逐对分析法求出每一对基因杂交后代与亲代相同的基因型和表现型概率,再根据不同对的非等位基因自由组合可以得出与双亲相同的基因型和表现型,最后用1减去子代与亲代相同的基因型和表现型的概率即可得出后代不同于亲代的基因型和表现型的概率,解答如下:
aaaa1aa:2aa:1aa子代与亲代基因型相同的概率为1/2,表现型相同的概率为3/4,BbBb1BB:2Bb:1bb子代与亲代基因型相同的概率为1/2,表现型相同的概率为3/4,Cccc1Cc:1cc子代与亲代基因型相同的概率为1,表现型相同的概率也为1。所以子代与亲代基因型(aaBbCc或aaBbcc)相同的概率为:1/21/21=1/4,子代与亲代表现型(三对全为显性或两对为显性,一对为隐性)相同的概率为:3/43/41=9/16,从而得出子代与亲代基因型不同的概率为:1-1/4=3/4;表现型不同的概率为:1-9/16=7/16。
答案:3/47/16。
3用逐对分析法来计算后病的概率
例4:人类多指基因(t)对正常指基因(t)为显性;白化基因(a)对正常(a)为隐性,这两对基因都是独立遗传。一个家庭中,父亲是多指,母亲正常,他们有一个白化病但手指正常的孩子,则下一个孩子只有一种病和有两种病的几率分别是()
a．1/2、1/8B．3/4、1/4C．1/4、1/4D．1/4、1/8
解析:父亲是多指,母亲正常,他们有一个白化病但手指正常的孩子,该孩子的基因型为:aatt,从而推出双亲的基因型为:aattaatt。用逐对分析法分析每对基因的的遗传:aaaa1aa:2aa:1aa,tttt1tt:1tt,子代多指占1/2、白化病患者占1/4,所以下一个孩子只有一种病的几率=只患多指的概率+只患白化病的概率为1/23/4+1/41/2=1/2;有两种病的概率为1/41/2=1/8。
答案:a。
4用逐对分析法来分析个体间自由的问题
例5:已知某一动物种群中仅有aabb和aabb两种类型的个体,aabb:aabb=1:1,且种群中雌雄个体比例为1:1,两对基因位于两对同源染色体上,个体之间能自由。则该种群自由产生的子代中能稳定遗传的个体占()
a．1/2B．5/8C．1/4D．3/4
解析:本题解题的关键是要理解自由不等于自交,计算自由产生的子代情况的遗传问题可用逐对分析法把不同对的基因分开,再计算出每个基因的频率,最后求出子代个体的遗传问题。解法如下:
根据aabb:aabb=1:1,可得aa:aa=1:1,a的基因频率=3/4,a的基因频率=1/4;bb的基因型频率为1,所以b的基因频率=1;种群中雌雄个体比例为1:1,因此子代个体的基因型频率为:aabb=aabb=a2b2=(3/4)212=9/16,aabb=a2b2=(1/4)212=1/16,其中能稳定遗传的个体aabb+aabb=9/16+1/16=10/16=5/8。
答案:B。
以上是我在教学中尝试的例子,希望能通过运用逐对分析法来解部分遗传题的方法,启发学生能更好地思考问题,活跃学生的思维,挖掘学生的潜能,提高学习效率。
参考文献
[1]《生物学教学》1995年08期.
[2]《生物学教学》1996年06期.