遗传学条件概率(6篇)

遗传学条件概率篇1

关键词：量子遗传算法；背包问题；修复函数

中图分类号：TP301

文献标识码：A

0引言

背包问题是一个在运筹学领域里常见的优化难题[1]。工厂里的下料问题，管理中的资源分配，资金预算，投资决策，装载问题等均可建模为背包问题。研究该问题的求解方法，无论在理论上，还是在实践中都有较重要的意义。由于采用通常的数学方法很难在有限的时间内找出全局最优解，因此，背包问题的求解方法主要是一些启发式算法[2],如禁忌搜索算法、模拟退火算法等，也有一些文献用遗传算法求解该问题[3],但当问题的规模较大时,传统遗传算法求解的效果不太理想。

近年来，A.Narayannan和KukHyunHan等人将量子力学中量子比特、量子态叠加等概念引入到遗传算法中，提出了量子遗传算法（QuantumGeneticAlgorithm，简称QGA）[4]。它以量子计算的一些概念和理论为基础，如量子比特、量子态叠加等，用量子比特编码来表示染色体，用量子门更新来完成进化搜索。量子遗传算法在种群多样性和计算并行性方面优于传统遗传算法，可有效提高算法的收敛速度，减少早熟收敛[5]。本文提出了一种带修复函数的QGA来求解背包问题，在量子门更新时采用一种通用的旋转角调整策略，使编程更为简单。对于运行中产生的非法解，由修复函数进行修正。几个典型背包问题的测试结果表明，这种具有自修复功能的量子遗传算法在求解背包问题时，性能优于传统遗传算法。

1背包问题的描述

从计算复杂性理论来看，背包问题是个NP难题。它的描述有多种形式，本文仅考虑简单0/1背包问题。

0/1背包问题可描述为：现有m个物品x1,x2,…,xm，每个物品的重量为wi，价值为pi。要从其中挑选若干物品放入背包，背包的总容量为c。问应该如何选择物品，才能使背包中物品的总价值最大。

背包问题的数学表达为：

其中，xi只取0或者1，此时为0/1背包问题。

2量子遗传算法（QGA）简介

量子遗传算法是量子计算与遗传算法的结合。QGA基于量子计算中的量子比特和量子态叠加等概念，将量子比特的概率幅表示用于染色体的编码，这样，一个量子比特染色体可以表示多个态的叠加，使得该算法较传统的遗传算法具有更好的种群多样性和更高的计算并行性。模拟量子坍塌的随机观察使种群更加丰富。在个体更新时采用量子旋转门操作，而不是传统遗传算法中实现较复杂的交叉和变异操作，有效地提高了算法的收敛速度，并且可以方便地在算法的探索（exploration）和开发（exploitation）之间取得平衡，提高算法的寻优效率。

2.1量子比特编码

在QGA中，染色体中的基因不是用确定性的值（如二进制数、浮点数或符号等）表示，而是用量子比特（qubit）表示，或者说是用随机概率方式表示。一个量子比特不仅仅可以表示|0>态或|1>态，而且可以表示这两种状态的任意叠加态，即|0>态和|1>态的任意中间态。所以，该基因所表达的不再是某一确定的信息，而是包含所有可能的信息，对该基因的任一操作也会同时作用于所有可能的信息。一般地，一个基因（即量子比特）的状态可表示为：

其中，α和β分别是|0>和|1>的概率幅，且满足归一化条件：

量子遗传算法中采用的这种量子比特染色体表示形式，使一个染色体可以同时表示多个状态信息（一个m位的量子染色体表示2m个可能的状态），有利于保持种群的多样性，克服早熟收敛。

2.2量子门更新操作

在QGA中，量子比特个体是遗传信息的载体，而对信息的基本操作是由量子门来实现的。量子门通过对量子比特实施一种幺正变换来控制量子态的演化和传递，进而实现种群的进化。量子门的设计是QGA实现的关键，直接影响QGA的性能。一般情况下采用量子旋转门U，其更新过程如下：

为其通过量子旋转门更新后的新基因，θi为旋转角，其大小和符号是根据一个事先设计的调整策略而确定的。旋转角的幅值影响收敛速度，如果幅值过大，会导致早熟；若幅值过小，会使收敛速度减慢。其值一般在0.001π~0.05π之间[6]。与其他的进化算法类似，QGA也是一种概率搜索算法，只是其个体表示具有量子比特的形式。量子染色体的更新由量子门操作来完成，实际上是一种启发式进化策略，有助于提高算法的收敛速度。

3带修复函数的量子遗传算法求解背包问题的实现

3.1修复函数

在求解背包问题时，背包的总容量c是确定的，但是，不一定每个解都满足背包的容量限制条件（∑mi=1wixi≤c），必定有不满足限制条件的解存在，因此，对非法解的处理是解决背包问题的一个重要步骤。

经典背包问题在求最大利润时大多采用惩戒（penalty）函数和修复（repair）函数的方法[7]。本文采用修复函数的方法来修正非法解，使其变为可行的编码。具体实现方法如下：

设置一个寄存器overfilled，放置二值数0或1。1表示背包已装满，0表示背包没满。

(1)overfilled置0。

(2)若∑mi=1wixi>c，则overfilled置1。

(3)当overfilled为1时，随机选择一个xi使其为0，直到∑mi=1wixi≤c。此时，将overfilled置0。

(4)当overfilled为0时，随机选择一个xj使其为1，直到∑mi=1wixi>c。此时，将overfilled置1。

(5)将最后选择的一个xj置回0。

3.2算法实现

带修复函数的量子遗传算法求解背包问题的具体实现步骤如下：

（1）初始化：产生初始种群

其中qtj为第t代种群中的第j个量子染色体。

式中，n是种群中量子染色体的数目，由于量子遗传算法具有高度并行性，所以种群规模可以很小而不影响算法的性能，本文中取n=10；m为量子染色体的长度，即背包中物品的个数。初始化时，全部染色体的所有基因

都被初始化为1/2，这意味着一个染色体取到所有可能值的概率是相等的。

（2）量子坍塌：对Q(t)中的个体进行一次观测，以获得一组确定的解P(t)={xt1,xt2,…,xtn}。其中，第j个染色体的观测值xtj={xtj1,xtj2,…,xtjm}是一个长度为m的二进制串，其每一位xtji的值观测为0或1是根据相应量子比特的概率选择得到的。具体观测过程为：产生一个0~1之间的随机数r，若||2

（3）修正非法解：采用3.1节所述的修复函数修正不可行编码，使所有的编码都满足背包限制条件，变为可行的编码。

（4）计算适应度：选取适应度函数为背包中物品的总价值。第j个染色体的适应度值fj=∑mi=1pi•xji。式中，pi是背包中第i个物品的价值；xji为第j个染色体的第i位观测值，m为染色体长度，即背包中物品的个数。由于要求背包的最大价值，所以适应度值越大的个体越好。

（5）更新种群：通过量子旋转门，根据(3)式和(4)式更新Q(t)。本文采用一种通用的旋转角调整策略[8]，如式(5)所示：

式中，θi为旋转角；sign为符号函数；xtji和bti分别为解xtj与当前最优解bt的第i位；f(xtj)和f(bt)分别是它们的适应度值；

为种群中第j个染色体的第i个基因对；Δθi为量子比特旋转的角度，其大小可以控制算法的收敛速度，本文中取0.01π。此调整策略可以用通常的表格形式表示，如表1。表中s(αtjiβtji)为量子比特旋转的方向函数。图1是量子旋转门作用于量子比特个体的示意图。例如，当xtji=0，bti=1时，若f(xtj)≤f(bt)，为使当前个体收敛到具有更高适应度的染色体，应该增加当前解对应量子比特取1的概率，即要使|变大，此时，在图1中，若(αtji,βtji)在第1，3象限，θ应向逆时针方向旋转（取正值），若在第2，4象限，θ应向顺时针方向旋转（Δθi取负值）。

为了验证本文提出带修复函数的量子遗传算法在求解背包问题时的有效性，以两个典型的背包问题为例，测试该方法的性能，并与传统遗传算法（CGA）进行比较。

算例1

采用文献[9]中的一个背包问题实例，例子中有50个物品可供选择，具体参数如下：

算法参数：

•带修复函数的量子遗传算法（QGA）：种群大小为10，最大进化代数为500；

•传统遗传算法（CGA）：种群大小为50，最大进化代数为500，交叉概率0.8，变异概率0.05。

用QGA解决此背包问题，可得到如图3的进化过程曲线。用该算法可以求出该问题的最优解决方案，决策变量xi(i=1,2,…,m)为11010101111011011011011111110100001010011000001000，背包的总价值为3B103，总质量为1B000。而用传统遗传算法（种群大小sizepop=50，最大进化代数maxgen=500，交叉和变异概率分别为0.8和0.05）解决该背包问题无法得到全局最优解，运行结果如图4所示。将图3和图4进行比较不难看出，传统遗传算法（CGA）的平均适应度迅速趋向全局最佳适应度，而量子遗传算法（QGA）的平均适应度趋向全局最佳适应度的趋势比较缓慢，由此可以说明，QGA虽然种群较小，但却具有更好的种群多样性。

物品随机产生，物品个数m分别取100、250和500，物品重量wi为1~10之间均匀分布的随机数，物品价值pi=wi+5，背包容量c=12∑mi=1wi。

采用传统遗传算法（CGA）和量子遗传算法（QGA）分别对m＝100、m＝250和m＝500的三种背包问题进行求解，算法参数同算例1，得到每代最佳适应度的比较如图5所示。从图5中可以看出，量子遗传算法的寻优能力明显优于传统遗传算法。

分别用CGA和QGA对上述背包问题进行50次试验，记录下每次运行的最佳适应度值，即背包的最大总价值。50次运行结果的最优值、平均值和最差值如表2所示。

从以上两个例子中可以看出，在求解背包问题时量子遗传算法的寻优能力优于传统遗传算法。而且，从两者的平均适应度曲线的比较可以看出，量子遗传算法虽然种群规模小，但仍能保持种群中个体的多样性，可以避免早熟收敛。而传统遗传算法在进化后期适应度高的个体大量繁殖，充斥整个解空间，这样就容易导致算法停止在局部最优解上。总之，带修复函数的量子遗传算法在求解背包问题时具有优良的性能。

遗传学条件概率篇2

一、定义适用度拓展性总结

定义，尤其是重、难点知识相关的定义，层次和限制条件都比较多，应用中变化繁杂，因此，课堂教学中必须引导学生对定义的理解进行“点破立”的引导.

案例1：基因频率的定义

根据基因频率的定义出发，可总结出如下公式1：A基因频率=

A/A+a.

在实践中，利用传统的哈代―温伯格平衡定律公式：A=p，a=q，则A+a=p+q=1，AA+Aa+aa=p2+2pq+q2=1，由此推导出公式2：An=AAn+1/2Aan；an=aan+1/2Aan(n代表第几代)，同时针对自由条件下可以推导出公式3：AAn=A2n-1；Aan=2An-1×an-1；aan=a2n-1(n代表第几代)，如果面对部分个体不可育的情况，则学生生搬硬套公式便会出现问题.

例1（2010全国卷2）4．已知某环境条件下某种动物的AA和Aa个体全部存活，aa个体在出生前会全部死亡，现该动物的一个大群体，只有AA、Aa两种基因型，其比例为1∶2.假设每对亲本只一次且成功受孕，均为单胎.在上述环境条件下，理论上该群体随机产生的第一代中AA和Aa的比例是（）.

A．1∶1B.1∶2C.2∶1D.3∶1

如果对公式1作出适当修正:A可育=可育个体中A/可育个体中A+可育个体中a，则相应变化：公式2：An可育=AAn可育+1/2Aan可育；an可育=aan可育+1/2Aan可育(n代表第几代)，同理针对自由条件下，可以推导出公式3：AAn可育=An-1可育2；Aan=An-1可育2×an-1可育；aan=an-1可育2(n代表第几代)，本题即可简化解之.

二、解题过程的归纳性总结

解题过程中的生成性总结，一般是有较强的实用性、针对性和概括性.

案例2：家族系谱图解题步骤：

1．判断遗传方式，写出相应的表现型通式：如图中根据口诀，判断甲为常染色体上隐性遗传，乙为X染色体上隐性遗传，由此表现型通式为：甲正常：A_，甲患病：aa；乙正常：XB_，乙患病：Xb_.

2．据所求个体表现型，写出其部分基因组成：如图中6号为A_XBX-，7号为A_XBY.

3．据所求个体相关的隐性个体，补全其基因型：如据甲病隐性1号、乙病隐性5号，6号为1/2AaXBXB或1/2AaXBXb，据甲病隐性8号，7号为1/3AAXBY或2/3AaXBY.

对此在实践中发现，并完善性归纳：（1）若所求个体的父母或子女中有隐性个体，则该个体部分基因型中相关遗传病的未知基因一定为隐性；（2）若父母或子女中无隐性个体，而其兄弟姐妹中存在隐性个体，则该个体部分基因型中相关遗传病的未知基因应有两种情况.

4．分枝法求每对性状的患病概率：

甲病：6号Aa×7号Aa(2/3)

患病（隐性）：aa=2/3×1/4=1/6

正常（显性）：A_=1-1/6=5/6

乙病：6号XBXb(1/2)×7号XBY

患病（隐性）：Xb_=1/2×1/4=1/8

正常（显性）：XB_=1-1/8=7/8

当然，无论显性还是隐性遗传，均从隐性性状突破.复习实践中还会涉及到夫妇一方为来自随机人群，结合自由下的基因频率、基因型频率变化，计算中尤其注意比例：人群中携带者概率与正常人群中携带者的区别.

5．据问题组合比例：例：6号、7号生出两病都患的个体概率应为1/6×1/8；6号、7号生出正常个体的概率应为5/6×7/8.组合比例要注意多元化解法：如6号、7号生出患一种病的个体的概率：（1）1/6×7/8+1/8×5/6；

（2）1-1/6×1/8-5/6×7/8；（3）1/6+1/8-2×1/6×1/8；（4）5/6+7/8-2×5/6×7/8.

三、解题方法的完善性总结

解题往往注重方法的归结，针对不同知识点特殊题型进行总结，让学生在参与归纳中理解方法，在实践中学会拓展.

案例3：家族系谱图中遗传方式判断归纳

归纳口诀：

①无中生有为隐性，②隐性遗传看女病，③父子都病X性，④病男父亲携常性；⑤有中生无为显性，⑥显性遗传看男病，⑦母女都病X性.⑧直系男病伴Y性.

对上述总结需配套理解：

原理：①②③句的原理：X染色体上隐性遗传（色盲症为

既定的预设方案继续下去，老师就应该灵活地改变教学方法，甚至是教学的程序，这便是“生成”.“生成”是学生思维活跃的体现，一旦有“生成”，说明学生完全沉浸于生物世界，有着愉悦的求知欲.一堂完整的、高效的课，就应该在老师的组织和引导下走向精彩的生成.所以，“预设”和“生成”并不矛盾，“预设”是高中生物课堂有效学习的基础，“生成”是高中生物课堂有效学习的发展，二者是辩证统一的关系.有了充分的“预设”，激发合理的“生成”，这才是一节完美的生物课.

精心的预设是为了精彩的生成，同时从生成的效果中还可以看出预设是不是充分，两者互为补充.所谓“凭栏听雨”还需“未雨绸缪”，所以说预设是必须的，生成是必要的.我们不能一昧的只是追求预设的完美，同时还要思考如何处理好意料之外的生成.只有两者兼备，达到了预设与生成的平衡，我们的课堂才是丰富多彩的课堂、充满生机的课堂、和谐的课堂.

例）：

XbXbXbXbY，女病父子必病

⑤⑥⑦句的原理：X染色体上显性遗传（眼球震颤病为例）：

XAX-XAYXAX-，男病母女必病

条件限制：

a：①句中的“无”（⑤句中的“有”）为父母均无（有）；而①句中的“有”

（⑤句中的“无”）为子代中部分个体有（无）.

如图1中：1、2看4隐性，4看1常染色体

如图2中：1、2看4显性，1看4常染色体

b：②中“看女病”（⑥中“看男病”）为看系谱图中所有生病的女性（所

有生病的男性）；③、⑦中的都病遵循“一票否决”原则，即只要所

有生病女性的父亲和儿子（所有生病男性的母亲和女儿）中有一个不

患病，就不是X性染色体上的基因，而是常染色体上的基因控制的.

如图3中，需看的病女：4、5、11、17，由于17看12常染色体

c:④句针对隐性病但又无女病，则从病男父亲的携带致病基因与否，判

断其基因位于常染色体还是性染色体.

如图4中：1、2看3隐性，若3看1携带致病基因常染色体，若3看1不携带致病基因X染色体

上述遗传判断，其原理是学生常用的判断角度，但基础较弱或接受能力欠缺的学生运用的有效性不够，所以通过口诀记忆配以完善性的注意点，可以提高学生的正确率和应对的灵活性.

实例4：细胞分裂方式判断的“三看识别法”

1．一看染色体奇偶性：奇数减数第二次分裂

偶数二看

原理：设体细胞中染色体数为2n，则有丝分裂和减数分裂各时期的染色体数和形情况如下：

据上所述，n若为奇数，只可能是减数第二次分裂.

2．二看有无同源染色体：无同源染色体减数第二次分裂

有同源染色体三看

原理：（1）减数第一次分裂发生同源染色体的分离后，减二分裂细胞中无同源染色体

（2）同源染色体：配对的两条染色体，形状和大小一般相同，一条来自父方，一条来自母方.

注意：若细胞分裂图为着丝点分裂状态，则看细胞一极有无同源染色体；

若细胞分裂图为非着丝点分裂状态，则看整个细胞中有无同源染色体.

3．三看有无同源染色体的配对或分离：有同源色体配对或分离减数第一次分裂

无同源色体配对或分离有丝分裂

遗传学条件概率篇3

[关键词]遗传概率计算发散思维

【例题】（2012江苏卷·30）人类遗传病调查中发现两个家系都有甲遗传病（基因为H、h）和乙遗传病（基因为T、t）患者，系谱图如下。以往研究表明在正常人群中Hh基因型频率为10-4。请回答下列问题（所有概率用分数表示）：

（1）甲病的遗传方式为，乙病最可能的遗传方式为。

（2）若I-3无乙病致病基因，请继续以下分析：

①I-2的基因型为；II-5的基因型为。

②如果II-5与II-6结婚，则所生男孩同时患两种遗传病的概率为。

③如果II-7与II-8再生育一个女儿，则女儿患甲病的概率为。

④如果II-5与h基因携带者结婚并生育一个表现型正常的儿子，则儿子携带h基因的概率为。

笔者以求解“II-5与II-6所生男孩同时患两种遗传病的概率”为例，从多角度思考，以期殊途同归。

解答如下：据I-1、I-2不患甲病，而II-2患甲病，可判定甲病为常染色体上隐性遗传病；又据I-3、I-4不患乙病，而II-9患乙病且I-3无乙病致病基因，可知乙病为伴X染色体隐性遗传病。因为II-5既不患甲病也不患乙病，所以II-5与甲病相关基因型为HH或Hh，与乙病相关基因型为XTY。又因II-6既不患甲病也不患乙病，所以II-6与甲病相关基因型为HH或Hh，与乙病相关基因型为XTXT或XTXt。

[解法一]（常规法）：II-5基因型可能为HHXTY、HhXTY；II-6基因型可能为HHXTXT、HHXTXt、HhXTXT、HhXTXt。所以，婚配组合有八种：①HHXTY×HHXTXT；②HHXTY×HHXTXt；③HHXTY×HhXTXT；④HHXTY×HhXTXt；⑤HhXTY×HHXTXT；⑥HhXTY×HHXTXt；⑦HhXTY×HhXTXT；⑧HhXTY×HhXTXt。其中只有组合⑧所生男孩才会同时患两病，其概率为×××=。

[解法二]（四边形法）：已知有甲、乙两种遗传病，且按照自由组合定律独立遗传，若子代中不患甲病概率为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。据题可得，所生男孩患甲病的概率为××=（即上图中的D），患乙病的概率为×=（即上图中的C），同时患两种病的概率为D×C=。这种方法不仅能把患病情况很直观地表示出来，而且解题过程简单明了，计算不易出错。

[解法三]（集合法）：据题可知，所生男孩不患甲病的概率为，不患乙病的概率为，正常的概率为×=；根据下图可得：两病兼患的概率=（患甲病的概率+患乙病的概率）—（1—正常的概率）=（+）—（1—）=。

[解法四]（雌雄配子结合法）：因为本题所求的是所生男孩两病兼患的概率，所以只需考虑含Y的与卵细胞结合即可。具体结果见下表：

遗传学条件概率篇4

“自交”还是“测交”,这的确是一个很基本又很引人深思的问题。那究竟是什么原因?历史局限的原因,思维方式的原因,还是另有玄机?

仔细分析其原因,应该包括以下几方面:

其一,是孟德尔假说一演绎法思维上的原因。

假说一演绎法是指在观察和分析基础上提出问题以后,通过推理和想像提出解释问题的假说,根据假说进行演绎推理,再通过实验检验演绎推理的结论。如果实验结果与预期结果相符,就证明假说是正确的,反之,则说明假说是错误的。孟德尔的豌豆实验过程是这样的:纯种的高茎豌豆和矮茎豌豆无论正交还是反交,杂交后产生的F1代总是高茎的,而F1代自交得F2代中高茎豌豆和矮茎豌豆的比例是3:1。孟德尔通过对第二代豌豆的性状的观察和统计分析,通过严谨的推理和大胆的想象,提出了遗传因子的分离假说。一个正确的假说应该不仅能解释两个或更多个已知事实,还应该能预言与构思假说是不同类的事实,能预言或解释背景知识预想不到的现象或事实。所以要验证其假说的正确性,孟德尔如果再用自交的办法,就是用一种现象来验证同一个现象,属于重复实验。即使实验现象与假说相符,说服力也不强。于是,他就另辟蹊径,采用F1代测交的实验来证明亲代杂交和F1代自交得来的假说。如果实验结果与预期结果相符,就足以证明其假说的正确性了。

其二,测交能更好的反应F1的基因型及产生的配子类型。

孟德尔的假说提到遗传因子是独立的、不融合的,在体细胞中是成对的,则杂合子的细胞中应该是显性遗传因子和隐性遗传因子并存,其形成的配子中只含有一个显性遗传因子或者一个隐性遗传因子。如果能通过直接观察或检测的手段判断,那当然最好。但就当时的技术条件和遗传学发展的水平来看,是不可能通过“观察”来真实的看到或检测到这个现象的。怎样才能形象地证明这个推断呢?测交即可做到这点。测交就是让F1与隐性纯合子杂交。由于隐性纯合子形成的配子中只含一种隐性遗传因子,对其他遗传因子无遮盖作用,不影响其他遗传因子表达性状,所以从它与别的配子结合得到后代的表现型,就可以得知F1中一对遗传因子的类型。这样,孟德尔从测交的后代结果(高茎豌豆和矮茎豌豆的比例是1:1)中,就能直观地证明F1的遗传因子组合(基因型)及产生的配子类型。

其三,测交实验得隐性纯合子后代的概率更高,能比较容易观察和统计,实验结果更准确科学。

遗传学条件概率篇5

关键词：数据挖掘；遗传算法；关联规则

中图分类号：TP18文献标识码：A文章编号：1009-3044(2008)35-2504-03

AKindofImprovedGeneticAlgorithmBasedonAssociationRulesMining

LAIWan-qin,LEIXiao-zhen

(FujianCommunicationsTechnologyCollege,FuZhou350007,China)

Abstract:Tothetraditionalgeneticalgorithmeasilyleadtoprematureconvergenceofthealgorithmandintotheplightoflocaloptimum,orConvergencetoomuchtimeandconsumealargeamountoftimetosearchforflaws，thistextproposedakindofimprovedgeneticalgorithm,Thealgorithmadoptsanadaptivemutationrateandimprovethemethodsofindividualchoice,andthiswillimprovethegeneticalgorithmusedinthedataminingassociationrules.Theexperimentalresultsshowthattheefficiencyofthealgorithmfordatabase.

Keywords:datamining;geneticalgorithm;associationrule

1引言

遗传算法是一种基于生物进化论和分子遗传学的全局随机搜索算法，具有很强的随机性、鲁棒性和隐含并行性，能快速、有效地进行全局优化搜索，是处理大规模数据项目集的有效方法。目前基于遗传算法的数据挖掘方法有了一定的进展，基于遗传算法的关联规则研究也取得了一些成果。但是，传统的遗传算法存在一定的缺陷，容易导致算法的过早收敛而陷于局部最优困境，或收敛时间过长而消耗大量的搜索时间。因此，本文提出了一种改进的遗传算法，该算法采用一种自适应变异率和改进的个体选择方法，用来克服上述问题，并且将这种改进遗传算法应用于关联规则的挖掘。

2遗传算法原理

遗传算法（GeneticAlgorithms，GAs），是模拟生物在自然环境中遗传和进化过程而形成的一种自适应全局优化概率搜索算法。他在解决大空间、多峰值、非线性、全局优化等高复杂度问题时显示了独特的优势[1]。把待解决问题的参数编成二进制码或十进制码（也可编成其他进制码）即基因，若干基因组成一个染色体（个体），许多染色体进行类似于自然选择、配对交叉和变异的运算，经过多次重复迭代（即世代遗传）直至得到最后的优化结果[2]。使用遗传算法解决问题时涉及到以下七个主要因素[3]。

1)编码

将待求解问题的解根据约束条件、选择合适的编码方法（比如二进制、整数、实数编码方法、格雷码编码、多参数级联编码、多参数交叉编码等），编码成通过位串表示的染色体。不同的编码，有不同的特点，使用时应根据需要选择[4]。

2)适应度函数

遗传算法采用适应度这个概念度量群体中个体在优化算法计算中可能达到、接近于或有利于找到最优解的优良程度，适应度是遗传算法选择操作的惟一依据。

3)选择算子

遗传算法中最重要的就是选择、交叉、变异这三个基本算子。选择算子一般采用赌选择，在这种选择算法中，每条染色体的适应度函数值占所有染色体适应度函数值总和的比例即为该染色体被选择的概率，根据这个概率，从原有的染色体中挑选出染色体放入池中，新的染色体可以有重复。

4)交叉算子

交叉是指每对染色体选择一个随机位置，其后的二进制串进行交换即可。常见的交叉方法有单点交叉、多点交叉等等，一般采用单点交叉。

5)变异算子

变异算子有利于增加群体多样性，变异方法也有很多，但最常用的就是基本位变异算法。

6)控制参数

遗传算法中控制参数的选择也是很重要的，一般参数取值范围如下:

种群大小N:即群体中所含个体的数量。种群大小影响GA的有效性，N太小，GA会很差或根本找不出问题的解，因为太小的种群数目不能提供足够的采样点;N太大，会增加计算量，使收敛时间增长。一般取为20~100;

遗传代数T:控制着遗传算法的终止代数。一般取为100~500;

交叉概率Pc:控制着交叉操作的频率，Pc太大，会使高适应值的结构很快被破坏掉，Pc太小搜索就会停止不前。一般Pc取0.4~0.99;

变异概率Pm:是增大种群多样性的第二个因素，Pm太小不会产生新的基因块，Pm太大，会使GA变成随机搜索。一般Pm取0.0001~0.10

7)终止条件

终止条件可以设定为规定的进化代数，也可以设定为当群体中某个解的适应值达到某一预先规定的范围内时停止，还可以迭代若干代直至群体中的个体不再发生变化。

3关联规则定义

设I={i1,i2,.....im}是个m不同项目的集合，D是一组事务的集合，D中每一事务T是I的子集，并且有一个标识符TID。设A是一个项集，事务T包含A当且仅当A⊆T，关联规则是形如A⇒B.的蕴涵式，其中A⊆I,B⊆I，且A∩B=ϕ，其意义在于一个事务中的某些项的出现，可以推测出另一个项在同一事务集中出现。规则A⇒B在事务集D中成立，具有支持度S，其中S是D中事务包含A∪B的百分比，即概率P(A∪B)；规则A⇒B在事务D中具有置信度C，C是指如果D中包含A的事务同时也包含B的百分比，也就是条件概率P(A/B)：

Support(A⇒B)=P(A∪B)（1）

Confidence(A⇒B)=P(A/B)（2）

关联规则可以理解为一个命题，即如果一个事务支持项目集A,则它也有一定的可能性支持项目集B，这一可能性称这为规则的可信度，记为conf(R)或C(R)。

规则R的可信度为支持项目集A的事务T也支持项目集B的条件概率。一个关联规则必须具备足够大的支持度和可信度。对于给定最小可信度minconf和最小支持度minsup，如果conf(R)≥minconf,supp(R)≥minsupp，则称关联规则R关于数据库成立，规则称为强规则。

4改进的遗传算法用于关联规则挖掘

早熟问题是遗传算法中不可忽视的现象，其具体表现为：1)群体中所有的个体都陷于同一极值而停止进化；2)接近最优解的个体总是被淘汰，进化过程不收敛。

为了解决这二个问题：1)提出了一种自适应变异率方法，可以避免过度变异造成不收敛，或陷入局部最优解；2)提出了一种基于排序的个体选择方法，将其应用于遗传算法进化后期，从而防止适应度高的个体数量迅速增长造成个体差异过小而提前收敛。

4.1自适应变异率

在遗传算法进化的早期阶段，如采用固定的变异概率Pm，则当Pm取值很小时，变异算子对群体不会产生影响，不利于新的基因的引入;当Pm取值很大时，有可能破坏群体中的优良基因，使得算法收敛速度变慢甚至不收敛。在这里提出一种自适应变异率方法，应用于进化的早期阶段，变异率表示如下:

（3）

其中，Pm(n)是第n代的变异率，Pm(n+1)是第n+1代的变异率，初始变异率为Pm(0)，fi(n)为第n代种群个体i的适应度，fmax(n)是第n代种群最高适应度，fi(n+1)是第n+1代个体i的适应度，fmax(n+1)是第n+1代种群最高适应度，m为种群个体数量，λ为调整系数。

这样就使得种群优良基因不会过度变异被破坏而造成收敛时间过长，又有利于新基因的引入，避免早熟而陷入局部最优，从而提高了遗传算法的性能。

4.2改进的个体选择方法

采用一种改进的选择淘汰方法，应用于遗传算法的后期:

1)适应度大小对待筛选个体排序；

2)前1/4个体复制2份，前1/4至2/4部分个体复制1份，进入下一轮选择；

3)前2/4至3/4部分个体保留，进入下一轮选择；

4)前3/4至4/4部分个体淘汰，不再进入下一轮选择。

4.3改进的遗传算法用于关联规则挖掘

4.3.1遗传算法编码

遗传算法最基本的问题是编码问题。一个好的编码方法，会使交叉、变异等遗传操作更方便实现。

当我们找到了一条形如A1∧A2∧…∧An⇒B1∧B2∧…∧Bn的关联规则时，实质上是在事务数据库中找到了这样一条规则:A1∧A2∧…∧An和B1∧B2∧…∧Bn。同时为真时在整个事务集中所占的百分比大于用户给定支持度，且B1∧B2∧…∧Bn为真在条件A1∧A2∧…∧An为真条件下的概率大于用户给定的可信度。其中(A1,A2,…An;B1,B2,…Bn)为事务数据库中的一个个字段。

本文采用实数组方法进行编码，实数数组中元素的个数与事务数据库中的字段个数相对应，元素值代表了元素的属性值，如表1所示的数据库。

用一个长度为N的数组来表示表1所表示的事务数据库的个体编码，A[1]表示字段1,A[2]表示字段2,....,A[R]表示字段R;将属性值用数值型的值表示，例如:用数值1表示属性值11，数值2表示属性值12,…，数值MR表示属性值MR，这样就可以用数组A[N]的元素值来表示相对应字段的属性值。另外用值0表示此属性与其它的属性无关联。表1所示的数据库的编码如图1所示。

用实数数组编码，不仅编码简单，易于实现，而且也便于遗传算子的操作。进行这样的编码后，交叉、变异等的操作就变成了对数组的操作。

4.3.2适应度函数的构造

综合考虑可信度和支持度，把其适应度定义为如下形式：

F(X⇒Y)=αS(X⇒Y)+βC(X⇒Y)

其中，α，β分别为支持度和可信度在评价规则时所占的份额，当某一个个体不能解释成合法的规则时，则认为该个体是无用规则(违反了实际)，记其适应度为：

Fitness=0

根据上面定义的适应度函数，能够搜索出高支持度和置信度的个体，也即规则。

4.3.3规则评价和提取

为了评价一条规则是否满足发现目标，可以通过一个规则评价函数来计算给定个体的支持度和置信度，然后据此判定该个体是否是想要的规则。在算法的运行中，对任意适应度高于某一指定值的个体，都调用规则评价函数对它进行评价。如果该个体满足规则要求，假设支持度大于0.1且可信度大于0.8，则将其存入规则库。在算法结束后，还要对规则库进行冗余规则的淘汰，最后留在规则库中的规则就是本次发现过程的最终规则。

4.3.4算法描述

step1：初始种群P(0)；获取用户给定的支持度S，可信度C；

step2：对当前种群P(t)中的每一个个体计算适应值；

step3：对当前种群P(t)进行改进个体选择的选择操作；

step4：对当前种群P(t)进行交叉操作；

step5：对当前种群P(t)进行变异操作；

step6：生成新的种群P(t+1)；

step7：同终止代数T进行对比，如果达到终止条件，则终止并输出规则，否则转步骤2。

5仿真实验及分析

在用户填写上网活动的数据库的数据挖掘中采用本文提出的改进遗传算法，目的是发现用户网上各种活动的关联规则。

用户上网活动的取值表属性（字段）如表2。

根据实际情况，活动名属性取值分别为股票=1、网上购物=2、在线游戏=3、娱乐=4、新闻=5、在线影视=6、邮件=7、聊天=8。

对每项活动属性取值分别为喜欢=1、一股=2、偶尔=3、从不=0，因此用户上网络活动的情况用8位的十进制数字来表示，处理后的数据映射结果如表3。

如王小华“03311022”表示用户“王小华”喜欢网上购物和玩在线游戏，偶尔会浏览娱乐或新闻内容网页，上网一般会聊天、观看在线影视和收发邮件，但从不在网上进行股票交易活动。

实验中，根据以上算法，我们选择了有效的调查问卷500份，随机生成N=20表示关联规则的初始种群，适应度函数中α=2.5,β=0.5。初始变异率Pm(0)=0.05，自适应变异率公式中λ=1.5，交叉概率Pc=0.7进化终止条件为fmax-fmin

对运行结果进行合并相似规则的最终处理，发现以下规则：

1)(支持度20%，可信度85%)=>

2)(支持度15%，可信度80%)=>

3)(支持度10%，可信度90%)=>

从以上规则可以看出该算法根据指定的支持度闭值0.10和可信度闭值0.8而发现的规则与实际情况比较吻合。

6结论

本文在阐述关联规则的挖掘算法的基础上，对传统遗传算法进行了一些改进并将改进的遗传算法运用于关联规则的提取，结合上网活动调查表，给出了改进的遗传算法进行关联规则挖掘的实例。仿真实验证明了算法的有效性和可行性。

参考文献：

[1]李敏强,寇纪淞,李丹,等.遗传算法的基本理论与应用[M].北京:科学出版社,2003.

[2]陈根社,陈新海.遗传算法的研究与进展[J].信息与控制,1994,23(4):215-222.

遗传学条件概率篇6

关键词：遗传算法，结构自重，结构优化

中图分类号：O342

引言

相比于其他算法，遗传算法具有一定的并行性，适用范围广泛。对复合材料夹层结构防护门的结构参数进行优化设计，涉及的因素条件比较多，通过选择遗传算法进行优化计算，可以不受限制性条件的约束，对其结构参数进行优化设计。

1.遗传算法简介

遗传算法（GeneticAlgorithm），顾名思义，就是将遗传过程应用在算法领域，通过借助适者生存的进化规律，与一些算法思路相结合，实现算法计算，其基本形式是进行随机化搜索。遗传算法的主要特点是对界定的种群中的对象进行操作，而不是对既定函数进行分析，避免了求解复杂函数存在的一些限定问题；通过选取基于概率化的寻优方式，不必遵循确定的规则，具有一定的自适应性，能根据算法进程调整搜索方向，从而自动获取适应度高的搜索空间并参与指导。

对于防护门的结构优化问题，其基本思路可以归纳为：确定目标函数>分析设定约束条件>利用优化算法计算求解。

2.防护门结构可靠性分析

本文设计的复合结构防护门是复合材料夹层结构，分析这种层合板形式的防护门的可靠性，需要评价整个防护门系统的可靠性。防护门结构的可靠性可以定义为：在一定的现实环境内，结构能够承担一定程度的荷载，起到防护作用，满足相关的战术技术指标。通常，结构的可靠性是以极限状态来标志的，通过定义失效概率将结构的可靠性定量表示，如果防护门结构达到极限状态的情况超过了失效概率的容许值，则可以认定防护门结构失效。

根据防护门可靠性的定义，通过以下三个步骤对复合材料夹层结构防护门的可靠性进行分析：

（1）获取与复合材料夹层结构防护门相关联的随机变量的资料。

（2）建立复合材料夹层结构防护门的失效准则。

（3）计算复合材料夹层结构防护门可靠性指标。

3.防护门结构的遗传算法优化计算

3.1优化的数学模型

在本文的防护门结构优化设计中，以结构的质量最小为目标，目标函数可描述如下：

（1）

目标函数中的三部分分别代表结构中三层的质量。对于整个防护门体系，可以认为各层的面积是一样的，而各层的密度也是定值，因此，可以取结构的厚度最小为目标函数，参照密度的比值，给各层的厚度加上一定的权重，由此目标函数可以修改为：

（2）

以可靠性满足一定的要求为约束条件，建立优化数学模型。对于本文的防护门结构，建立防护门的结构优化模型，如下式：

：（3）

3.2遗传算法实施

对于如何满足约束的问题，近年来在遗传算法中产生了拒绝策略、修复策略、改进遗传算子策略以及惩罚策略这几类方式控制遗传运算获得的不可行后代。设计一个惩罚函数，通过惩罚不可行解将约束问题转化为无约束问题。

对于本文涉及的防护门结构的约束条件，拟选用加法形式，构造带有惩罚项的适值函数：

（4）

其中，代表染色体，为目标函数，是惩罚函数。

Matlab程序提供了遗传算法工具箱，根据建立的结构优化数学模型以及对遗传算法实施过程的相关分析，在Matlab中进行编程，对防护门结构优化模型进行求解。初始化种群大小为100，采用基于赌的策略进行选择，交叉概率取0.8，变异概率取0.15。迭代200次后结束算法，输出结果。

输出的最优解为：，，

此时目标函数的值。

3.3结果讨论

在直径为15mm，长度为80mm，初速度为1837m/s的平头圆柱形破片的作用下，求得复合材料夹层结构防护门各防护层的厚度分别为：面层15.32mm、芯层20.60mm、背层16.48mm。此时目标函数的值为h=42.00mm。

在相同破坏条件下，根据侵彻计算经验公式：

（5）

计算只选用均质钢材料的防护门材料厚度。式中，代表材料密度，是材料的极限抗拉强度，通过试验导出的值为；是法线着角，为材料厚度。经计算，对于均质钢结构防护门选用钢材料的厚度需要达到51.28mm。

4.结束语

本文选用遗传算法对防护门结构进行优化设计。通过对防护门的可靠性进行分析，建立了基于防护门抗侵彻能力的结构优化模型，并结合实例对防护门的厚度参数进行了优化计算。从优化结果来看，与均质钢结构的防护门相比，以陶瓷作为芯层的复合材料夹层结构防护门利用优化算法设计合理的结构参数，能够在降低结构自重的基础上既满足既定的战术技术指标，又达到了结构优化的目的。

参考文献：

[1]王小平，曹立明.遗传算法：理论、应用与软件实现[M].西安交通大学出版社，2012