遗传学概率问题(6篇)
遗传学概率问题篇1
关键词：遗传算法；最优化问题；最优解；求解步骤；运算效率
中图分类号：TP312文献标识码：A文章编号：1009-3044(2011)19-4654-02
SolvingOptimizationProblemsBasedonGeneticAlgorithm
SONGJie-peng1,2
(1.ChinaUniversityofMiningandTechonlogy,Xuzhou221116,China;2.XuzhouNormalUniversity,Xuzhou221116,China)
Abstract:Geneticalgorithmisakindofeffectivemethodtosolveoptimizationproblems,andinsolvingcomplexglobaloptimizationproblem,ithasbeensuccessfullyused.Thebasicstepsofgeneticalgorithmaresummarized,andthrougharealexample,thedetailedoperationstepsofgeneticalgorithmaredescribed,whichincludesinitialchromosomesgeneration,chromosomesevaluation,selection,crossoverandmutation.VCandVBprogramminglanguagesareappliedforrealizingtheabovesteps,andtheresultsshowthatVCisbetterthanVBinoperationefficiencyoptimality.
Keywords:geneticalgorithm;optimizationproblem;optimalsolution;solvingsteps;operationefficiency
遗传算法是一种通过模拟自然进化过程搜索最优解的方法[1]。遗传算法本身并不要求对优化问题的性质作一些深入的数学分析，从而对那些不太熟悉数学理论和算法的使用者来说，无疑是方便的[2]。本文结合实例探讨了遗传算法求解最优化问题的具体步骤，并同时应用VC和VB进行编程，对其运算结果进行比较。
1遗传算法的求解过程
生物遗传物质的主要的载体称为染色体，在遗传算法中，染色体通常是一串数据（或数组），它用来作为优化问题的解的代码，但它本身并不一定是解[3]。应用遗传算法求解一般要经过这样的几个过程[4]：首先，随机产生一定数目的初始染色体，由这些染色体组成一个种群，其中，种群中染色体的数目被称为种群的大小或规模。然后，用评价函数来评价得到的每个染色体的优劣，即染色体对环境的适应程度(称为适应度)，用来作为以后遗传操作的依据。接着，进行选择过程，选择过程的目的是为了从当前种群中选出优良的染色体，使它们成为新一代的染色体，判断染色体是否优良的标准就是它们各自的适应度，也就是染色体的适应度越高，它被选择的机会就越多。通过选择过程，产生新的种群。再对这个新的种群进行一定概率的交叉操作，这个操作是遗传算法中的主要操作之一，类似于生物的杂交。然后进行变异操作，以挖掘种群中不同个体的多样性，克服其有可能陷入局部解的问题[5]。这样，经过上边的各种运算后产生的新的染色体称为后代。然后再对产生的后代重复进行选择、交叉和变异这几个操作，在迭代到设定的次数后，把生成的最好的染色体拿来作为优化问题的最优解。
2用遗传算法求解最优化问题实例
应用遗传算法求解极大化问题：
2.1初始产生pop_size个染色体
用染色体V＝（x1,x2,x3）来作为解的代码。解的可行性由下面的检验函数检验：如果(x1
这样，可以从这个超几何体中抽取初始染色体x1=u(0,1),x2=u(0,1),x3=u(0,1)
其中u(0,1)表示服从区间[0,1]上的均匀分布的随机数。如果生成的染色体不可行，则拒绝接受，再重新生成一个新的染色体，如果可行，则接受它作为种群的一名成员。经过有限次抽样后，得到30个（设定种群的规模为30，即pop_size=30）可行的染色体。
2.2计算每个染色体的评价函数值
计算产生的30个染色体的的函数值，并按照由高到低的顺序排序，记函数值最大的染色体编号为V1，其余的顺次为V2，V3，…，V30。
定义基于序的评价函数为[6]
其中，a为给定的一个介于0到1之间的数据，例如a=0.05，当i=1时，意味着染色体是最好的，i=30时是最差的。
2.3选择过程
选择过程可以通过如下四步给出[7]：
步骤1对每个染色体Vi,计算累积概率qi：
步骤2从区间(0,q30]中产生一个随机数r。
步骤3若qi-1
步骤4重复步骤2和步骤3共30次，得到30个复制的染色体。
2.4交叉操作
定义参数Pc作为交叉操作的概率，从i=1到30重复执行如下步骤：产生一个[0,1]之间的随机数r，若r
c为在（0,1）区间中产生的一个随机数，如果产生的两个新的后代X和Y均可行，则用它们代替父代，否则再一次产生随机数c，再进行染色体的交叉，直到得到的X和Y均可行或循环到给定的次数后结束。
2.5变异操作
定义参数Pm作为遗传系统中的变异概率，从i=1到30重复执行如下步骤：产生一个[0,1]之间的随机数r，若r
用V＝（x1，x2，…，xn）表示上面的过程中生成的父代，再按照以下方法对生成的父代进行变异[8]。设M为在初始化的过程中任意定义的一个较大的数，在n维欧氏空间中任意产生一个d作为变异的方向，计算染色体V+M・d的值并将其代入约束条件中，如果判断后是不可行的，那么将M调整为0和M之间的任意一个随机数，再重新计算新染色体V+M・d的值，然后再判断它的可行性，重复上述过程直到得到的新染色体通过检验为止。若在设定的迭代次数内未能得到新的可行解，那么将M赋值为0。上述操作结束后，用X=V+M・d这个新得到的染色体替换原先的染色体V。重复进行选择、交叉、变异操作，直到给定的迭代次数为止。
2.6结果
将上边的步骤用C语言写成程序，并在VC++6.0下运行，当设定交叉概率为0.3，变异概率为0.2，迭代1000次时，求得的最好解是（0.5767,0.5768,0.5786），函数值是2.2795。当设定交叉概率为0.3，变异概率为0.05，迭代3000次时，求得的最好解为（0.5817,0.5732,0.5771），函数值是2.2795。由此，可以看出，最优解并不唯一。
为了验证结果是否为最好，又将上述算法在VB6.0下编程运行，同样设定交叉概率为0.3，变异概率为0.2，迭代次数为1000，经过很长时间的运行后，显示的结果为（0.577,0.507,0.635），函数值为2.269。而且在用VB运行时，若在用生成随机数Rnd()函数前加上初始化种子数语句Randomize，则每次运行的结果都有一点差别。所以在编写涉及大量计算的程序时，还是选用执行效率高且结果更优的C语言为好。
3结论
本文给出了遗传算法的基本原理与步骤。将其应用于最优化问题，结合实例给出了详尽求解过程，并同时采用VC和VB编程。结果表明，在应用遗传算法求解最优化问题时，选用C语言编程求解，结果更加接近最优解，其求解效率也比VB语言要高。
参考文献：
[1]王小平,曹立明.遗传算法――理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[2]唐焕文,秦学志.实用最优化方法[M].大连:大连理工大学出版社,2004.
[3]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001.
[4]黄少荣.遗传算法及其应用[J].电脑知识与技术,2008,4(7):1874-1876.
[5]岳,冯珊.遗传算法的计算性能的统计分析[J].计算机学报,2009,32(12):2389-2392.
[6]刘宝碇,赵瑞清,王纲.不确定规划及应用[M].北京:清华大学出版社,2003.
[7]周丽,张智顺.遗传算法求解函数极值的应用[J].电脑知识与技术,2007,4(21):802-803.
遗传学概率问题篇2
关键词：物流；VRP；遗传算法
中图分类号：TP18
随着电子商务时代的来临，消费者的消费习惯产生了巨大的变化，同时也给货运物流行业带来了全新的发展。货运配送业务量也在逐年增长，如何加快物流配送的速度，进一步达到快速、及时、节约的物流配送目的就成了时下亟待解决的问题。本文中我们对车辆物流配送建立了数学模型，然后利用遗传算法对该模型进行求解，并结合实际情况将该模型予以改进。最后将其应用到实践之中。
1货运物流管理
1.1物流的概念和发展
物流的概念最早在形成于美国，起初被称为PhysicalDistribution（PD），即实体分配或配送。到了1963年，物流的概念被引入日本，进一步解释为“利用现代信息技术和设备，将物品从供应地向接收地准确的、及时的、安全的、保质保量的、门到门的合理化服务模式和先进的服务流程。
“物流”自上个世纪70年代末引进我国以来，经历了近20年的研讨酝酿、启蒙尝试，到90年代后半期，在改革开放和现代化建设的强有力推动下，伴随着信息技术的迅猛发展和跨国公司的大举进入引起了社会各界广泛关注。现代物流就不单纯考虑了货物配送的问题，而且还要考虑从供应商到制造商的原材料采购，以及制造商在产品生产制造过程中的运输、仓储、装卸、配送和信息等各个方面，如何全面地、综合性地提高经济效益和效率的问题。
1.2国内货运物流的现状
随着我国正式加入世界贸易组织，国内的运输业和物流业正面临着前所未有的挑战和机遇。随着UPS、Fedex等物流巨头的进入，无论从资金、管理、技术和能力上，我国的物流业都毫无优势可言。
在新的经济形势下，客户对车辆运输提出了更高的要求。不仅要加快运输速度，保证货物运达的成功率和效率，减少转运周期，减少流动资金占用，还要利用自身的物流信息为客户提供物流管理，从而为客户和运输企业本身创造更多的价值。因为运输成本是物流成本中仅次于仓储成本的第二大成本，而利用车辆货运又在全国货运总量中占有很大的比例，因此车辆运输成本的节约将给运输企业以及客户带来巨大的经济效益。
2遗传算法
2.1遗传算法的概念和基本流程
遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年在他的专著《自然和人工系统的适应性》首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。
遗传算法（GeneticAlgorithm）是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。其主要特点是群体搜索策略和种群中个体之间的信息交换、搜索不依赖于梯度信息。它尤其适用于处理传统搜索方法难以解决的复杂和非线性问题。
遗传算法效仿基于自然选择的生物进化，是一种模仿生物进化过程的随机方法，下面先介绍几个生物学的基本概念和术语，这对于理解遗传算法是非常重要的。
定义1.染色体（Chromosome）。生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由多个遗传因子—基因组成。
定义2.个体（Individual）。指染色体带有特征的实体。
定义3.种群（Population）。带有特征个体的染色体集合称为种群。该集合内个体的总数称为群体的大小。有时个体的集合也称为个体群。
定义4.适应度（Fitness）。在研究自然界，卜生物遗传和进化现象时，生物学家使用适应度这个术语度量某个物种对于生存环境的适应程度。对生存环境适应度高的物种获得更多的繁殖机会，而生存环境适应度低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝。
定义5.选择（selection）。指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是种基于适应度的优胜劣汰的过程。
定义6.复制（Reproduction）。细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。
定义7.交叉（Crossover）。有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，亦即在两个染色体的某一个相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称为基因重组，俗称“杂交”。
定义8.变异（Mutation）。在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。
我们习惯上把Holland1975年提出的GA称为传统的GA。它的主要步骤如下：编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001～0.01之间。变异为新个体的产生提供了机会。遗传算法的基本处理流程如图1所示。
2.2遗传算法与物流配送的关系
车辆路径问题是一个NP完全问题，只有当其规模较小时才有可能寻求其精确解。因此，如何针对车辆路径问题的特点，构造运算简单、性能优异的启发式算法，对物流系统以及许多可以转化为车辆路径问题的组合优化问题都有十分重要的意义。在求此类问题时，若不能利用问题的固有知识来缩小搜索空间，很容易产生搜索的组合爆炸，因此研究在搜索过程中自适应地完成搜索过程，从而得到最优解或次优解的通用的搜索算法一直是令人瞩目的课题。遗传算法就是这种特别有效的算法。它的主要特点是简单、通用、鲁棒性强，适应于并行分布处理，应用范围广。目前，遗传算法已经在求解车辆路径问题方面取得了成功的应用。但传统标准遗传算法（GA）易陷入局部极值解，出现“早熟收敛”现象。为此，本文针对遗传算法在求解车辆路径问题中存在的“早熟收敛”、易陷入局部极值点、寻优效率不够理想等问题，研究出了新的改进遗传算法，以消除传统遗传算法中的不足，提高算法寻优效率。它无法用常规的最优算法求得精确的最优解，为此，人们使用各种启发式算法来解决它。在启发式算法中，现代优化算法是近年来发展起来的一类启发式算法，其中的遗传算法更以其独特的思想方法受到人们的重视。
3遗传算法在货运物流中的应用
3.1货运物流配送的数学模型
车辆货运物流运输路径问题（VRP）可描述为：从配送中心用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重辆一定，要求合理安排汽车路线，使总运距最短，并满足以下条件：
（1）每条配送路径的长度不超过汽车一次配送的最大行驶距离；
（2）每条配送路径上各需求点的需求量之和不超过汽车载重量；
（3）每个需求点的需求必须满足，且只能由一辆汽车送货；设配送中心有K辆汽车，每辆汽车的载重量为Qk（1，2，…K），其一次配送的最大行驶距离为Dh，需要向L个需求点送货，每个需求点的需求量为qi（i=1，2，…L），需求点i到j的运距为Dij，配送中心到各需求点的距离为doj（i，j=1，2，…L）。再设nk为第k辆汽车配送的需求点数（nk=0表示未使用第k辆汽车）用集合Rk表示第k条路径，其中的元素rki表示需求点rki在路径k中的顺序为i（不包括配送中心），令rk0=0表示配送中心，则可建立如下物流配送路径优化问题的数学模型的目标函数：
3.2改进的交叉算子
遗传算法的车辆路径规划方法中，不管是在已知的环境或者未知环境，遗传算法的交叉概率都给出一个值。虽然这并不影响对遗传算法的平稳运行，但很容易在在交叉过程当中丢失最优解。这主要是因为用于个体的交叉都是随机选择的，适应值大的个体与适应值小的个体有相同的交叉概率，也就有同样的被交叉机会，而适应值大的个体进行交叉后，有可能会降低平均适应度，损失最优解。
本文在遗传算法的改进方法中，提出了一种自适应交叉概率的方法，交叉概率的方法，该方法令大适应值个体具有小交叉概率，小适应值个体具有大交叉概率，这样就保证了最优个体在交叉操作中能够保存下来。该方法的表达式为：Pc=K1×（fmax-f`）/（fmax-fmin）+K2
其中，fmax、fmin。和f`，分别为种群的最大适应度数值、最小适应函数值和相交叉的两个个体中的较大适应值k1、k2分别为算法的收敛系数，且k1+k2=1。这种自适应交叉概率的方法，保证了具有大适应值的个体保留下来，选择适应值小的个体进行交叉。
3.3求解问题的混合遗传算法HGA-VRP
为了提高优化的效果和算法的时间效率，本文提出了一种求解VRP问题的混合遗传算法HGA-VRP（HybridGeneticAlgorithmforVehicleroutingProblem）。HGA-VRP将2-opt算法作为变异算子，以改进的自适应交叉概率方法获取交叉算子以提高优化的效果。
HGA-VRP的编码方案采用常用的路径标示基因编码方案。个体的适应度由个体所代表的适应值函数来决定，适应值函数越小则个体的适应度越高。HGA-VRP算法在交叉算子方面，采用改进的自适应交叉算子，采用2-opt算法作为遗传算法的变异算子。
HGA-VRP算法的计算步骤如下：
（1）初始化：根据多个货物配送点建立坐标空间模型。并对坐标进行基因编码。
（2）生成初始种群：把产生一系列可行路径顺序排列作为染色体的编码方法，在程序中染色体用数组存储，生成初始种群M。
（3）遗传代数计数器初始化，options=0。
（4）循环处理步骤4a至步骤4d，直到设定的最大进化代数。
a.以路径长度的倒数作“适应值函数”，具体表达如下：
对种群中的个体计算适应值的长度，并对个体按适应值从小到大排序。
b.选择算子：按照赌的方法选出新的种群。
c.交叉操作：交叉操作是在选出的部分子种群中进行的，其结果关系到算法的收敛速度，所以是遗传算法中比较重要的一个算子。根据低适应值函数个体具有高交叉率，高适应值函数个体具有低交叉率的原则，引入如下自适应产生交叉概率方法：Pc=K1×（fmax-f`）/（fmax-fmin）+K2
d.变异算子：选择种群中M*Pm的个体，Pm是变异概率。采用2-opt邻域搜索优化算法对所选个体进行优化。
4结论
本文介绍了货运物流管理的概况，以及国内货运物流的现状，指出了货运物流管理信息化的意义，详细研究了遗传算法在货运物流配送问题中的应用，在VRP模型的基础上，结合实际地建立了合适的数学模型，设计实现了解决该问题的改进混合遗传算法，采用了自适应交叉操作和2-opt邻域搜索优化算法来优化变异操作，对遗传算法中的各个步骤进行了研究，实现了完整的遗传算法。本文所提出的改进遗传算法的是一种较为合理、相对完善的车辆货运物流运输路径问题解决方案，具有一定的理论和现实意义。
参考文献：
[1]宋华，胡左浩.现代物流与供应链管理[M].经济管理出版社，2000.
[2]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].中国物资出版社，2001，6.
[3]张文修.遗传算法的数学基础[M].西安交通大学出版社，2000.
[4]阎庆，鲍远律.新型遗传模拟退火算法求解物流配送路径问题[J].计算机应用，2004，6：261-263.
[5]EllehiTaniguehi，RussellG.Thompson，TadashiYamada，RonVanDuin.CityLogistics：NetworkModelingandIntelligentTransportSystems.PERGMAON.2001：2-3.
遗传学概率问题篇3
遗传学是高中生物的重要组成部分，也是高考的重要考点，而遗传学中的概率计算又常常是高考命题中的重点和热点。我从事多年的高三生物教学，深知该部分知识常令学生头痛，特别是遗传系谱图中概率计算让相当一部分学生望而生畏，即使基础知识很扎实的学生也常常难免失误。为除去学生的畏难思想，降低学生的失误率，我总结出“四边形对角线法则”来解决有关问题。
二、“四边形对角线法则”模型
已知有甲、乙两种遗传病，且按照自由组合定律独立遗传，若子代中不患甲病概率为A（甲病正常概率为A），则患甲病概率为D；若子代中不患乙病概率为B（乙病正常概率为B），则患乙病概率为C，如下图：
在上图四边形ABCD中：
边AB表示：子代正常概率A・B
边DC表示：子代同时患两种病概率为D・C
对角线AC表示：子代只患乙病概率A・C
对角线BD表示：子代只患甲病概率B・D
对角线AC+BD表示：子代患一种病概率A・C+B・D
三、例题解析
例1.白化病为常染色体隐性遗传病，受基因A，a控制，色盲为伴X染色体隐性遗传病，致病基因为b，设一对夫妇基因型为AaXX和AaXY，求该夫妇所生的男孩中：（1）只患一种病的概率；（2）患两种病的概率；（3）正常的概率。
解析：（1）求出四边形四个顶点的数值
按照基因的分离规律可知，由亲代Aa×Aa子代男孩不患白化病概率为3/4，患白化病的概率为1/4；由亲代XX×XY子代男孩不患色盲概率为1/2，患色盲的概率为1/2，所以四边形ABCD四个顶点的数值分别为A=3/4，B=1/2，C=1/4，D=1/2。
（2）构建“四边形及其对角线”
（3）按“四边形对角线法则”计算
所生的男孩中患一种病的概率：对角线乘积相加=（3/4）×（1/2）+（1/4）×（1/2）=1/2
所生的男孩中患两种病的概率：（1/4）×（1/2）=1/8
所生的男孩正常的概率：（3/4）×（1/2）=3/8
答案：该夫妇所生男孩中只患一种病的概率为1/2，患两种病的概率为1/8，正常的概率为3/8。
例2.下图为患甲病（显性基因为A，隐性基因为a）和乙病（显性基因为B，隐性基因为b）两种遗传病系谱图，Ⅱ1不含乙病致病基因，问：Ⅲ1和Ⅲ4婚配后，子代只患一种病的概
据Ⅱ、Ⅱ患甲病，而Ⅱ、Ⅱ的女儿Ⅲ正常，可判断甲病为常染色体显性遗传。
据Ⅱ、Ⅱ不患乙病，而Ⅲ患乙病，故乙病为隐性遗传病，又因为Ⅱ不含乙病致病基因，所以乙病为伴X染色体隐性遗传病。
（2）求出Ⅲ和Ⅲ基因型
因为Ⅲ不患甲病，故Ⅲ的甲病基因型为aa；因为Ⅲ患乙病，所以Ⅲ的乙病基因型为XY，所以Ⅱ和Ⅱ的乙病基因型为XY和XX，Ⅲ的乙病基因型为1/2XX或1/2XX。综合上面两方面分析可知：
因为Ⅱ、Ⅱ患甲病，而Ⅲ不患甲病，所以Ⅱ、Ⅱ的甲病基因型均为Aa，由上图可知Ⅲ的甲病基因型为1/3AA或2/3Aa；因为Ⅲ不患乙病，所以Ⅲ的乙病基因型为XY。综合上面两方面可知：
据基因型aa×（1/3AA，2/3Aa），可求子代不患甲病概率：（2/3）×（1/2）=1/3，患甲病概率2/3，据基因型（1/2XX，1/2XX）×XY，可求子代不患乙病概率：7/8，患乙病概率（1/2）×（1/4）=1/8。
（5）按“四边形对角线法则”计算
子代只患一种病的概率：（1/3）×（1/8）+（2/3）×（7/8）=15/24=5/8
子代患两种病的概率：（2/3）×（1/8）=1/14
子代正常的概率：（1/3）×（7/8）=7/24
遗传学概率问题篇4
作者简介：陈轩（1990―），男，湖北汉川人，硕士研究生，研究方向：智能控制与智能应用。
文章编号：1003-6199(2014)02-0089-04
摘要：区域防空雷达网是防空作战空情预警的发展趋势，为了提高区域雷达网探测能力和抗综合电子干扰、抗隐身技术与隐身飞机的威胁，抗低空、超低空突防及抗反辐射导弹(ARM)的能力，研究雷达组网的问题，介绍免疫遗传算法的基本原理和特点，提出基于免疫遗传算法的雷达组网方法，通过计算机仿真实验证明方法的可行性。
关键词：免疫遗传算法；雷达组网；覆盖系数
中图分类号：TP39文献标识码：A
お
ApproachtoRadarNettingBasedonImmuneGeneticAlgorithm
お
CHENXuank,HUANGXinhan
(SchoolofAutomation,HuazhongUniversityofScienceandTechnology,Wuhan,Hubei430074,China)
Abstract:Regionalairdefenseradarnettingisthetendencyofairdefensewarfareinfuture,inordertoimprovethedetectiveperformanceandtheperformanceofantisynthesizedelectronicinterference,antistealthtechniqueandstealthaircraft,antilow,ultralowaltitudepenetrationandantianti-radiationmissiles(ARM),radarnettingisstudied.Theprincipleandcharacteristicsofimmunegeneticalgorithmisintroduced,andimmunegeneticalgorithmisputforwardinradarnetting.Thesimulationexperimentbycomputersindicatesvalidofthismethod.
Keywords:immunegeneticalgorithm;radarnetwork;coveragecoefficient
1引言
随着新型空袭兵器和航天技术的不断发展，单台雷达无论在探测能力上，还是电子防御功能上都有较大的局限性，因此雷达组网技术在现代战争和人类对宇宙的探测中起着举足轻重的作用，该技术是通过将多功能、多类型、多频段的雷达进行组网，实现实时数据传输，资源共享，并在此基础上对数据实时处理，这已被证明是一种有效的方法［1］。雷达组网系统的关键问题是如何对多台雷达进行最佳组网以获得最优的防御能力。目前进行雷达组网的方法很多，常用的有效用函数法或专家法，它们是根据雷达覆盖防守区域面积、雷达部署任务、单台雷达探测距离、地形、衔接角、遮蔽角、起伏角等因素进行加权求和得到阵地的效用值，但是这些都不能很好地解决执行速度的问题。将免疫遗传算法应用于雷达组网，能较快地使布阵接近最优解，从而避免了采用穷举的方法带来执行速度慢的问题，并且克服了遗传算法未成熟收敛和局部搜索能力差的缺陷。
2免疫遗传算法原理和设计
2.1免疫遗传算法原理
生物免疫系统对抗原会自动产生相应的抗体来防御，这一过程被称为免疫应答。在此过程中，部分抗体作为记忆细胞保存下来，当同类抗原再次侵入时，记忆细胞被激活并产生大量抗体，使再次应答比初次应答更迅速，体现了免疫系统的记忆功能。同时，抗体与抗体之间也相互促进和抑制，以维持抗体的多样性及免疫平衡，这种平衡是依浓度机制完成的，即抗体的浓度越高，则越受抑制，反之亦然，体现了免疫系统的自我调节功能。抗体的浓度计算是系统保持种群多样性的基本手段之一［2］。
传统的遗传算法是一种具有“生成+检测”的迭代过程的搜索算法，而免疫遗传算法IGA(ImmuneGeneticAlgorithm，IGA)则是一种借鉴生物免疫系统的自适应识别和排除侵入机体的抗原性异物的功能，将生物免疫系统的学习、记忆、多样性和识别特点引入的遗传算法。在解决实际问题时，目标函数和约束条件作为抗原输入，随后产生初始抗体群，计算抗原和抗体的亲和力用来描述可行解与最优解的逼近程度，并通过一系列遗传操作的计算，在保持抗体多样性的情况下，找出针对该抗原的抗体，即问题的解［3］。免疫遗传算法与传统的遗传算法相比，具有如下显著特点：
1）具有免疫记忆功能：可加快搜索速度，提高总体搜索能力，确保快速收敛于全局最优解；
2）具有抗体的多样性保持功能：可提高全局搜索能力，避免未成熟收敛；
3）具有自我调节功能：可提高局部搜索能力。
2.2免疫遗传算法设计
免疫遗传算法在标准遗传算法的基础上增加了抗体浓度概率计算、抗体的促进与抑制等模块来提高解的多样性。该算法因为将免疫系统中抗体多样性维持机制引入了遗传算法，使得其性能比标准遗传算法更进了一步。在解决实际问题时，目标函数和约束条件作为抗原输入，随后产生初始抗体群，并通过一系列遗传操作及抗体亲和度的计算，在保持抗体多样性的情况下，找出针对该抗原的抗体，也就是问题的解［3］。免疫遗传算法的流程图如图1所示，其基本的步骤如下：
计算技术与自动化2014年6月
第33第2期陈轩等:基于免疫遗传算法的雷达组网方法
1）算法初始化。输入抗原及设定参数：输入目标函数以及约束条件，作为抗原的输入；设定种群规模、选择概率、交叉概率、变异概率等参数。
2）初始抗体产生。在第一次迭代时，抗体通常在解空间中用随机的方法产生。
3）亲和度及浓度的计算。计算各抗体和抗原的亲和度以及各抗体的浓度。
4）终止条件判断。判断是否满足终止条件，如果满足终止条件，将与抗原亲和度最高的抗体加入细胞记忆数据库，然后终止；否则继续。
5）选择、交叉、变异操作。根据设置的选择概率、交叉概率和变异概率选择抗体，对抗体进行交叉和变异操作。
6）根据以上的操作更新群体以后转入步3)。
ネ1免疫遗传算法流程图オ
3采用免疫遗传算法的雷达组网
3.1雷达组网问题描述
在采用免疫遗传算法进行雷达组网的方案中，雷达的覆盖系数为：
Е=［(∪Ni=1Si)∩Sarea］/Sarea(1)
式中Si为第i台雷达的探测范围，N为雷达总数，Sarea给定的责任区域。ρ∈［0，1］表示N台雷达所覆盖的有效责任区域占总责任区域的比重。maxρ为本次雷达组网的目标函数，也就是免疫遗传算法中的抗原，即
maxρ=max［(∪Ni=1Si)∩Sarea］/Sarea(2)
3.2抗体编码
雷达坐标是所求问题解的信息，为了缩小抗体空间，提高搜索效率，采用了对雷达组网比较直观的抗体编码方式，假设一共有5台雷达进行组网，则N种雷达布阵的方案可以表示为如下的结构：
X11Y11X12Y12X13Y13X14Y14X15Y15第1种雷达组网方案
X21Y21X22Y22X23Y23X24Y24X25Y25
第2种雷达组网方案
……
Xn1Yn1Xn2Yn2Xn3Yn3Xn4Yn4Xn5Yn5
第n种雷达组网方案
其中，Xn1Yn1Xn2Yn2Xn3Yn3Xn4Yn4Xn5Yn5（n表示雷达组网的任意一种方案）分别是第1台、第2台、第3台、第4台和第5台雷达的横坐标和纵坐标。雷达布阵的每一种方案对应为免疫遗传算法中抗体种群中的每一个个体。
3.3亲和力计算
亲和力是指发生免疫系统识别的抗体和抗原的结构越互补，结合越可能发生，而把彼此结合的强度称之为亲和力。抗原需要尽可能好的与入侵的抗体相结合。二者匹配程度越好，结合就越好，抗原和抗体亲和力就越大。对于雷达组网问题，抗原对应的是雷达组网的最大覆盖系数，由于雷达组网的总责任区域的面积是一定的，可以定义抗体Ab与抗原Ag的之间的亲和力为：
(Ab,Ag)=1Tb－Tg(3)
式中：Tb，Ta分别为抗体Ab，Ag对应的雷达网的覆盖系数，其中Tg也是所求的最大的雷达网覆盖系数。
定义抗体Ab1与抗体Ab2之间的亲和力为：
App(Ab1,Ab2)=1|Tb1－Tb2|(4)
式中：Tb1、Tb2分别为抗体Ab1与抗体Ab2对应的雷达网覆盖系数［4］。
3.4算法选择、交叉、变异算子
免疫遗传算法能使抗体保持多样性并且最终能够收敛到最优解的主要操作，就是因为在算法中有选择、交叉和变异算子的存在，从而使整个抗体群沿着适应度较好的方向搜索。
1)选择算子
选择是根据适者生存原则选择下一代抗体，在基于免疫遗传算法的雷达组网中选择的是下一代的组网方案。采用如下的选择算子：
PS(xi)=αρ(xi)∑ni=1ρ(xi)+(1－α)1Ne－ciβ(5)
式中：ρ(xi)是以式(1)为适应度函数的雷达组网覆盖系数；ci是抗体xi的浓度，即群体中相似抗体所占的比重［5］，即
ci=和抗体i亲和度大于λ的抗体数N(6)
其中λ为相似常数，一般取为0.9~1；
α和β是常数调节因子；N是该种群内抗体的总数。
2)交叉
交叉是在选中的抗体中，对两个不同的个体按交叉概率Pc随机选中相同的位置进行基因交换(一般交叉概率取值为0.15~0.75)，从而产生新的抗体，也就是新的雷达组网方案。如果对于5台组网雷达，随机选择的是抗体1和抗体2进行交叉，抗体1和抗体2的编码如下：
抗体1：X11Y11X12Y12X13Y13X14Y14X15Y15
抗体2：X21Y21X22Y22X23Y23X24Y24X25Y25
按照交叉概率产生的交叉点为4，则交叉以后的抗体1和抗体2的编码分别是：
抗体1：X11Y11X12Y12X23Y23X24Y24X25Y25
抗体2：X21Y21X22Y22X13Y13X14Y14X15Y15
3)变异
变异是在选中的抗体中，对个体中的某些基因以一定的变异概率对某些抗体的某些位执行异向转化(一般变异概率的取值为0.01~0.2)。在变异的时候，对于交叉过程中产生的抗体方案，随机产生一个介于［-MAX/2,+MAX/2］的数字rand，其中MAX为横坐标和纵坐标可取的最大值。变异以后坐标值x’与原来值x之间的关系如下：
x，=x+rand(7)
变异以后如果x′＞MAX，则取x′=MAX；如果x，
单靠变异不能在求解中得到好处，但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样的时候，选择和交叉无法产生新的基因，这时只能靠变异产生新的基因，即变异增加了全局优化的特质。
3.5基于浓度的种群更新
由式(5)可见，本文中的选择算子是采用基于抗体的雷达组网覆盖系数以及抗体浓度的选择概率Ps(xi)，从而有效地保证了抗体的多样性，避免了算法的早熟问题，能够获得更好的覆盖系数。
4仿真实验
根据前面的算法流程，选取目标函数为N台雷达所覆盖的有效责任区域占总责任区域的比重。雷达的台数分别为3台，4台，5台，初始抗体的数量为N=50，即一共有50种方案。利用Иmatlab仿真的结果如图2所示。ネ贾芯匦慰虮硎镜氖亲橥雷达阵地的有效范围(长为200公里，宽为100公里)，雷达的类型一共有两种，即探测范围为50公里的雷达和探测范围为30公里的雷达。参照雷达组网的实际要求，在仿真的过程中，最多只提供2台性能优越的雷达，效能较差的雷达数量不限。
ィa）3台雷达的面积覆盖率
ィb）4台雷达的面积覆盖率
ィc）5台雷达的面积覆盖率
图2matlab仿真结果
在图2中当雷达数量为3台时，组网雷达的面积覆盖率为87.84%（图2（a））；当为4台时，组网雷达的面积覆盖率为91.53%（图2（b））；当为5台时，组网雷达的覆盖率为94.27%（图2（c））。将仿真的结果与传统遗传算法的组网覆盖率对比［6］，如表1所示。
表1雷达组网覆盖率对比
3台雷达
4台雷达
5台雷达
传统遗传算法覆盖率
81.5%
86.1%
88.2%
免疫遗传算法覆盖率
87.84%
91.53%
94.27%
由表1可以看出，基于免疫遗传算法雷达组网的覆盖率要高很多，将免疫遗传算法应用于雷达组网是一种有效的方法。
5结论
雷达组网能够有效地提高雷达系统的整体性能，更好的适应高科技电子战、信息战。将免疫遗传算法应用于雷达组网系统，能够有效地提高雷达网的面积覆盖率。免疫遗传算法与传统的遗传算法相比，能够克服传统遗传算法的未成熟收敛，提高全局搜索能力。
参考文献
［1］彭获由.区域性雷达组网［J］.电子科学技术评论,1992(3):1-6
［2］LUOWENJIAN,CAOXIANBIN,WANGXUFA.AnImmuneGeneticAlgorithmBasedonImmuneRegulation［A］.Proceedingsofthe2002CongressonEvolutionaryComputationCEC2002.May12-17,2002.Honolulu,USA.Vol.2:801-806.
［3］段玉波,任伟建,霍凤财,等.一种新的免疫遗传算法及其应用［J］,2005,20(10):1185-1188.
［4］谢刚,武斌,谢克明.基于免疫遗传算法的TSP优化问题求解［J］.太原理工大学学报,2007,38(3):199-201.
遗传学概率问题篇5
1模型原型
【例1】（2012·江苏卷）人类遗传病调查中发现两个家系中都有甲遗传病（基因为H、h）和乙遗传病（基因为T、t）患者，系谱图如图1所示。以往研究表明在正常人群中Hh基因型频率为10-4。请回答下列问题（所有概率用分数表示）：
如果Ⅱ7与Ⅱ8再生育一个女儿，则女儿患甲病的概率为。
答案：1/60000。
解析：根据系谱图中正常的Ⅰ1和Ⅰ2的后代中有一个女患者Ⅱ2，说明甲病为常染色体隐性遗传。Ⅱ7的基因型为H，其中HH占1/3，Hh占2/3。根据题意，正常人群中Hh的基因型频率为10-4，也就是Ⅱ8基因型为H-的概率。故女儿患甲病的概率=2/3×10-4×1/4=1/60000。
点拨：基因频率与遗传系谱图结合的概率计算模型的原型是遗传系谱图中的个体与自然人群中的个体交配，且自然人群中的相关个体基因型频率已知。在遗传系谱图中根据亲子代关系计算相关个体基因型的概率后，直接结合自然人群中相关个体基因型频率运用乘法原理求解。
2模型拓展
【例2】（2013·安徽卷）图1是一个常染色体遗传病的家系系谱。致病基因（a）是由正常基因（A）序列中一个碱基对的替换而形成的。
一个处于平衡状态的群体中a基因的频率为q。如果Ⅱ2与一个正常男性随机婚配，他们第一个孩子患病的概率为。如果第一个孩子是患者，他们第二个孩子正常的概率为。
答案：q/3（1+q）3/4
解析：Ⅱ2的基因型是A_，其中Aa占2/3，AA占1/3。一个处于平衡状态的群体中a基因的频率为q，则AA的频率为（1-q）2，Aa的频率为2（1-q）q。正常男性中Aa的概率为Aa/（AA+Aa）=2（1-q）q/[（1-q）2+2（1-q）q]=2q/（1+q），则他们第一个孩子患病的概率为2/3×2q/（1+q）×1/4=q/[3（1+q）]。如果第一个孩子是患者，则Ⅱ2与正常男性的基因型均为Aa，他们第二个孩子正常的概率为3/4。
点拨：模型拓展较原型的区别在自然人群中的相关基因型个体的概率未知。先按照哈温平衡计算此概率，再按照亲子代关系计算遗传系谱图中相关基因型个体的概率，最后结合自然人群中相关个体基因型频率运用乘法原理求解。
3模型演练
图3为患甲病（显性基因A，隐性基因a）和乙病（显性基因B，隐性基因b）两种遗传病的系谱，Ⅱ3和Ⅱ8两者的家庭均无乙病史。
假设某地区人群中每10000人当中有1900个甲病患者，若Ⅲ12与该地一女子结婚，则他们生育一个患甲病男孩的概率为。
答案：1/60000
解析：某地区人群中每10000人当中有1900个甲病患者，不患甲病的是10000-1900=8100，所以aa的概率是8100/10000=0.81，由此算出a的基因频率是0.9，的基因频率是0.1。Ⅲ12的基因型是A_，其中Aa占2/3，AA占1/3。
方法一（配子法）：Ⅲ12产生配子的种类及比例是A占2/3，a占1/3;自然人群中A占0.1，a占0.9。所以若Ⅲ12与该地一女子结婚后代不患病的概率是aa=1/3×0.9=0.3，后代患病的概率是1-0.3=0.7，故后代患病男孩的概率是0.7×1/2=0.35。本文由wWW.dyLw.NeT提供，第一论文网专业教育教学论文和以及服务，欢迎光临dYLw.nET
遗传学概率问题篇6
【关键词】自适应遗传算法；混合遗传算法；作业车间调度
引言
关于车间调度问题的改进遗传算法（ImprovedGeneticAlgorithm，IGA）研究，国内外学者已经做了大量的工作，并取得了一定的成绩，但对于容易出现局部最优、形成早熟的缺点仍没有很好的解决[1]。
该文提出了用并行结构将动态自适应技术（DynamicAdaptiveTechnology）[2]和混合启发式算法（SimulatedAnnealingAlgorithm）[3]结合起来的并行自适应和混合遗传算法（ParallelTwoGeneticAlgorithm，PTGA）。该算法利用自适应遗传算法（AdaptiveGeneticAlgorithm，AGA）[2]来提高局部搜索速度，利用混合遗传算法（SimulatedAnnealingGeneticAlgorithm，SAGA）[3]来提高局部搜索能力，从而提高算法的收敛概率，降低陷入局部最优，产生早熟的可能性。并通过经典模型LA01来验证算法的收敛效果。
1相关问题描述
1.1作业车间调度问题模型
1.2应用算法
自适应遗传算法(AGA)[2]是Srinvivas等设计的个体的交叉率和变异率可以随进化过程动态变化的改进遗传算法。混合遗传算法（SAGA）[3]是将遗传算法与模拟退火（SimulatedAnnealing）结合在一起来改进算法搜索过程中存在早熟和局部搜索能力差的问题。
2PTGA的调度设计
2.1算法的功能与结构
PTGA的框架结构是并行的，即算法上的并行，是为了解决陷入局部最优，产生早熟和收敛概率低的现象，不同于并行遗传算法[4][5]在处理器上的并行。
算法的功能：PTGA分为主干和两个分支。主干监控全部染色体并基于全局执行选择操作；分支（1）用改进自适应遗传算法实现，分支（2）用混合遗传算法实现。两个分支分别接受来自主干的染色体进行交叉等操作，产生新个体，并将其交给主干进行选择。
2.2交换策略
两个分支之间交换染色体，需要考虑到交换频率、交换数目这两个问题。
（1）交换频率f：即每隔多少代交换两分支的优质染色体。如果f过小，一个分支陷入局部最优时，使得另一个分支很容易也陷入局部最优；如果f过大，不能体现两分支的相互促进作用。
（2）交换数目T：即每次交换时要交换的个体数目。交换的染色体过多，会使得两个分支的染色体趋于相同，也会令算法陷入局部最优。
针对作业车间调度的典型问题LA01，将PTGA的交换频率和f交换数目做了大量的实验统计分析，当f=5,T=2，时LA01问题的平均迭代次数经验值最低。
3实验结果分析
以文献[1]中的LA01经典问题为例，对三种遗传算法进行仿真，实验参数设置均相同，
从表2的实验结果可以看出，在都能找到最优解的前提下，本文提出的算法收敛概率更高，更不易出现早熟收敛的现象。
表2实验结果
从图3可以看出，通过这种优化方案算法更早的收敛且非常稳定。这是由于改进的遗传操作使搜索的结果朝着好的区域发展。说明本文提出的PTGA有较好的搜索和跳出局部最优的能力。
4结论
通过对并行遗传算法的结构分析，构建了并行自适应遗传算法和混合遗传算法（PTGA），通过对作业车间调度的经典调度模型算法实现得到的实验结果，验证了该算法可加速跳出局部最优解和提高算法的收敛概率，更加趋近于全局寻优。
【参考文献】
［1］王凌.车间调度及其遗传算法[M].北京:清华大学出版社，2003.
［2］XingYingjie，ChenZhentong，SunJingetc.AnImprovedAdaptiveGeneticAlgorithmforJob-ShopSchedulingProblem.ICNC'07-FSKD'07,p287-291.
［3］KirkpatricS，GelattCD,VecchiMP.Operationalbysimulatedannealing.Science.1983,220：671～680.
［4］侯广坤,骆讲鹏.一种理想并行遗传算法原理.软件学报.1999,10（5）：557~559.