遗传研究与应用（共12篇）
遗传研究与应用 篇1
摘要：为更好地优化码头泊位分配,提高泊位利用率,以实现码头泊位利用率最大化为目标,借鉴背包问题的解决方案,将船舶在港时间、作业顺序、泊位安排、机械配置、堆场安排等时空因素,结合遗传算法得出泊位资源安排的最优解。实践证明,该算法能有效缓解人工制订泊位计划所造成的考虑不周全、计划不合理等现象,有效避免了泊位冲突、极大提高了码头泊位利用率,提升了码头作业效益和服务水平。
关键词：泊位调度,背包问题,遗传算法
0 引言
现代港口是国际物流供应链的主要环节,能够提供快速、可靠、灵活的综合物流经营服务是现代港口的重要标志。泊位是决定港口码头的一个关键因素,相对于港口其他设施的投资来说,建造一个新的泊位的费用是非常昂贵的,所以,如何在已有泊位数量的基础上,合理的分配泊位已经成为制约当前港口发展的重要因素。
作为码头重要的作业资源,泊位、泊位计划是码头作业的基础,合理的泊位计划是提高作业效率、缩短船舶在港时间的关键因素。现在全球吞吐量排名前十的港口,其24小时内数量达到几十艘次,因此如何合理安排船舶靠泊顺序和位置,决定了码头岸线资源及堆场、设备、人力资源的合理应用程度,提高泊位计划的合理性对提升整个码头的通过能力和服务水平,有着至关重要的意义[1]。
1 当前泊位计划中存在的问题
当前泊位计划编排的依据主要是根据船公司对码头的重要程度,也就是所谓的“重点客户重点服务”策略;再有就是采用所谓的“先进先出”原则,这样会导致出现物化消耗过大,服务效率低下,客户满意度不高等问题;除此之外,码头泊位计划安排的好与坏,则主要体现在计划员本身对于码头业务的理解程度、作业经验是否丰富等方面,而这些则可能导致作业线路安全隐患或者资源岸线泊位浪费等情况出现。总之缺乏必要的理论支持和系统分析,从而导致泊位计划的随机性较大,这是目前泊位计划制定过程中存在的一个比较普遍的问题。
2 通过基于背包问题的遗传算法解决组合优化问题
遗传算法已经成为组合优化问题的近似最优解的一把钥匙[2][3]。它是一种模拟生物进化过程的计算模型[4],作为一种新的全局优化搜索算法,它具有简单、鲁棒性强、适应并行处理广等特点,非常适合N-P问题的求解。
背包问题是一个典型的组合优化问题,在计算理论中属于NP-完全问题,其计算复杂度为,传统上采用动态规划来求解。
如上所述,我们可以将码头岸线长度作为横轴,时间为纵轴,两者相乘所得面积作为背包大小,其他如泊位水深、船舶吃水、装卸箱量等参数作为约束条件,从而将船舶泊位调度问题,转化为背包问题最优解的求解问题。
3 问题描述
3.1 背包问题概述
背包问题(Knapsack Problem)的一般提法是:已知n个物品的重量(weight)及其价值(或收益profit)分别为wi>0和pi>0,背包的容量(contain)假设设为ci>0,如何选择哪些物品装入背包,可以使得在背包的容量约束限制之内所装物品的价值最大?
该问题的模型可以表示为下述0/1整数规划模型:
式中xi为0-1决策变量,xi=1时表示将物品i装入背包中,xi=0时则表示不将其装入背包中。
3.2遗传算法概述
遗传算法(Genetic Algorithms,GA)是在1975年首次由美国密西根大学的D。J。Holland教授和他的同事们借鉴生物界达尔文的自然选择法则和孟德尔的遗传进化机制基础之上提出的。经过40多年的研究、应用,遗传算法已被广泛地应用于函数优化、机器人系统、模式识别、图像处理、工业优化控制等多个领域。
4 背包问题的遗传算法求解
遗传算法具有“生成+检测”的特点。其基本流程描述如下:
(1)基因编码:
基因编码将n个Xi的值顺序排列,可简单理解为,将符合要求的物品放入背包中,其他的物品则不放入。
(2)编码修复:
利用遗传算法的思想进行修复。修复的基本思想为:
在Xj=1的所有物品中,将价值重量比(C/W)最小的物品取出,直到满足背包的容量约束为止。由此可产生一些新的基因编码串,并且这些新编码串总是相对来说质量比较好的,特别是它们肯定满足问题的约束条件。
(3)适应度函数:
由于对每个个体使用遗传算法修正已保证了不会产生无效染色体,所以在进行个体适应度评价时无须引入度函数项,而是直接用目标函数值作为适应度函数值,即:
(4)选择:采用轮盘赌的方式进行选择。在本算法中,将各基因的适应值事先作处理:
fi(i)=fit(i)-min(fit)+1;以防止适应度函数值出现小于零的情况,并且可以在一定程度上防止适应值差别过大时丢失低适应值基因的有用信息。
(5)交叉:采用单点交叉方式,随机选取一点作为基因的交叉点。
(6)变异:定义参数pm作为变异操作的概率,由(5)得到每个个体中的每个基因值都以概率pm进行变异;
(7)演化:经过选择、交叉和变异操作,得到一个新的种群,对上述步骤经过给定的循环次数的种群演化,遗传算法终止[5]。
根据上面分析,我们不能看出,该算法成败的关键在于适应度函数的建立,确切地说,就是其中的变量xj,以及对应参数cj。
以本案为例,我们可以将码头岸线乘以时间作为背包,单位时间内,码头所能承载的船舶数量最大化,或者说泊位利用率最高,作为我们的目标,而泊位水深、船舶吃水、装卸箱量等参数作为约束条件。
如上所述,解决背包问题的算法有多种,在实践中,我们采用遗传算法来解决泊位调度问题,也就是从获得泊位利用率最高出发,寻找最优解的方法。在绝大多数情况下,寻找最优解的时间复杂度还是比较低的。
在实际生产组织过程中,我们主要通过船公司重要性、码头吃水、船舶载重、以及码头岸线桥吊、机械配置等四个因素作为变量xj,并且根据实际效果,不断调整变量的权数cj,来安排现场泊位,最终获得最佳解,来实现泊位利用率最大化。
5 结论
5.1 作业效果
我们将该算法应用到码头泊位计划系统中,目前该系统已经在青岛前湾集装箱码头公司应用,现将其中某一天码头船舶的真实数据罗列如表1所示。
通过数据对比,我们发现采用先到先安排原则和本文介绍的算法安排的泊位调度,对应泊位利用率从82%提升到87.2%,尤其对于装卸箱量较大的大船,依靠本文提出的算法,能够有效地提高码头的泊位利用率。
5.2 产生效益
实践证明,系统地推广应用,有效规范集装箱码头作业流程,优化码头生产工艺,增强码头作业的安全管理能力,提升作业效率及资源的有效利用率,降低码头的作业成本,不仅提高了港口作业效率和服务质量,更极大提高了港口管理水平和服务能力,实现了良好的经济效益和社会效益。
国际国内集装箱货运领域信息和营销服务提供商美国《JOC》杂志发布《2014年度全球港口和码头生产率研究》,在8000TEU以上集装箱船的码头生产率中,青岛港以157MPH的成绩排名全球第一。
6 结束语
泊位计划是码头的核心计划,合理的泊位计划是提高码头作业效率,缩短船舶在港时间的关键因素,本文根据码头实际,提出了基于背包问题的码头泊位调度遗传算法,实践证明,通过该算法,能有效提高码头的泊位利用率,对码头的生产作业有着较大的推动作用。下一步,将会结合码头岸桥、集卡、天气、上游港口抵、离港情况等因素,对算法做进一步地优化和改进。
参考文献
[1]宋海涛,张连钢,窦亮.集装箱码头泊位优化措施[J].集装箱化.2015.9:5-8.
[2]Goldberg D E.Gennitic Algrithms in Search,Optimization and Machine Learning[J],Adison Wesley Reading.MA,1989.
[3]Khuri s,Back T.Heitkott J,An Evolutionary Approch to Cambinal Optization Problems[J].Proc.of 22st.Annual Computer Science Conference 66-73 Newyork.
[4]Chen Guo-liang,Wang Xu-hua,et.al.Generic Algrithms and its Applications[J].,Beijing People’s Posts and Telecommunications Press 1996.
[5]张燕涛.基于遗传算法的泊位调度问题优化研究及仿真[D].武汉:武汉理工大学,2005.
遗传研究与应用 篇2
—《数学文化》读书报告
黄武浩
弹药2班
2011303521
摘要：遗传学的建立、发展和完善与数学紧密相连。采用“渗透式”教学的方法，把遗传学知识和数学思维有机结合，巧妙应用数学的方法和技巧，将部分遗传现象进行数学抽象和逻辑推理，提升学生对遗传学的认识和理解层次，进一步提高的学习和研究能力。关键词：遗传学数学；数学原理；渗透式教学；逻辑思维
首先作者通过介绍数学是研究各门学科的重要工具，从而引入遗传学教学与数学的关系，21世纪是生命科学的时代，而遗传学特别是分子遗传学在生命科学中据主流地位，它推动着整个生命科学的迅猛发展，近年来遗传学教学信息量剧增与其授课学时不断压缩之间的矛盾日趋突出。遗传学教学工作者提出了概念图的应用、知识的模块化和网络化、学科间的渗透式教学和PBL教学等。但是如何进一步将遗传学知识用数学语言来描述，如何将遗传学的基本概念进行数学抽象，以及如何运用数学思维来讲授遗传学，是遗传学教师面临的新问题，更是新的挑战。
下述为作者结合自己的教学实践总结出的一些经验，颇有理论意义。数学渗透促进遗传学学科的建立和发展
1.1 数学思维的成功应用促进遗传学诞生和发展
1865年，孟德尔的豌豆杂交实验论文首次利用数学统计方法，系统地描述了生物性状的遗传现象，从而提出了分离定律和自由组合定律。由于他的结论是基于统计分析方法，推论严谨，逻辑正确。由于在那个时代数学方法用于生物研究是极不寻常的，所以近半个世纪后的1900年，人们才重新发现类似的现象，这标志着遗传学学科的正式诞生，同时也是数学介入遗传学的开始。而遗传学早期的研究焦点是遗传物质的化学本质，Levene利用磷酸、五碳酸和含氮碱之间的数量关系来有效区别DNA和RNA，同时提出四种核苷酸的数量关系与物种的多样性有关。最近Deng基于DNA的双螺旋结构和碱基的组成又建立了DNA复制的数学模型，这暗示双螺旋结构可能是数学语言在生命活动规律中的一种表现。由此，数学与遗传学的建立和发展密不可分，这可能是数学作为生物类专业学生的基础课程设置的科学依据。
1.2 数学思维在教学应用的展望
兴趣是促进学生主动学习的动力，也是推动学生成才的起点。由于遗传学知识复杂、信息量大、理论性和实践性较强，导致学生对该课程缺乏兴趣。不同学科间知识点的有机衔接是激发学生学习兴趣的有效途径之一。当今生命科学已进入数学化时代利用数学的思维和方法解析基因在遗传发育中的网络关系已成为研究热点，利用数学知识来理解遗传学的概念和原理也成为数学改革的目标和方向。作者提出一个概念：在黑板上画一个大圆和两个小圆，在各个圆中写入一些字母和符号，然后把大圆比作细胞核，两个小圆比作线粒体和叶绿体，而圆中的字母和符号当做基因，最后将大圆中的所有元素构成的集合类比成核基因组，两个圆形成的集合就分别是线粒体基因和叶绿体基因组。这样就建立了类比关系。在集合论基础上，它运用了运动和变化观点，把变量和变量之间的关系归纳为两集合中元素间的对应就是函数思想。
所以教师灵活数学思维和原理来讲解遗传学的概念，用数学的思维进行抽象，能有效激发学生的学习兴趣，达到事半功倍的效果。1.3 数学思维向遗传学教学渗透的作用
在遗传学教学过程中借助数学思维来理解遗传现象的本质，拓展学生的学习视野。如前所述集合与基因组和元素与基因之间的联系，映射法则与基因对形状的作用关系，以及排列组合与减数分裂过程中染色体的行为，事件的概率原理与三大遗传定律的逻辑联系，以及方程和函数思想与功能基因的解析之间的一致性等。适当运用类比、抽象和逻辑推理可以激发学生的积极性，提高学生的自学能力。
围绕“染色体理论”的三大遗传定律：分离定律，自由组合定律和连锁互换定律，是遗传学特别是经遗传学教学体系的主线。根据作者的体会，可以利用概率论原理对其进行数学抽象。思路如下：第一才，快速回顾一下减数分裂的过程和遗传的染色体理论的基本内容；第二，明确一条染色体上有多个基因以及联会是减数分裂的子代细胞只能得到同源染色体中的其中之一，因此一对同源染色体同时进入同一子细胞是一个互斥事件，而每个子细胞获得同源染色体中的一条则是一个必然事件，这就是将分离定律抽象为互斥事件。
遗传学教学通常采用网络式和框架式教学来提高学生自主学习的能力，而学生自主学习能力又是培养学生创新能力的关键。作者也尝试利用数学函数的英文单词“Function”的一词多义来激发学生对遗传学问题的主动思考和探索：“Function”具有功能和函数的意义，结合前面的分析，基因对性状是一种函数关系，也是基因功能的展现形式；由此表明不同的基因和性状之间的函数关系可能存在差异、综上所述，将数学思维和原理向遗传学课堂教学进行渗透引导学生用数学语言对遗传学基本原理进行概括和抽象，能达到事半功倍的效果。
数学原理向遗传学渗透式教学的思考
2.1 数学渗透是培养创新性复合型人才重要途径
创新是民族进步的灵魂，而人才培养的最高境界就是创新性人才的培养，大学又是创新性人才培养的主要基地。当前自然科学的研究正处于一种数学化趋势，用数学的语言和思维来理解生命活动的本质，更是实现新形式下高等院校人才培养目标的需要。过去由于学生对学科间知识点的内在联系缺乏认识，没有形成有机的完整的体系和骨架，不同课程之间的知识是孤立的、静止的和零散的。这严重制约了学生综合创新能力的提高。数学思维具有高度的概括性和严谨的逻辑性，在帮助学生构建完整的知识体系和寻找不同学科知识点的内在联系等方面具有明显优势。因此，在遗传学教学中进行数学渗透，将遗传学知识与数学知识建立起有机的联系，是创新型复合型人才培养的重要途径。2.2 数学渗透是多元化的教学手段和结果
采用多元化的教学手段，注重授课知识的简约化和系统化，使学生从不同的角度来思考问题和解决问题。由于教学概念具有高度的概括性，其推理又具有严谨的逻辑性，因此利用数学思维来讲解遗传学，将遗传学知识系统化和体系化。同事数学知识具有丰富的内涵，有许多可供遗传学教学利用的素材。显而易见，数学渗透是多元化教学手段的必然结果。
2.3 数学渗透是遗传学学科发展的必然趋势
数学是一种科学思想，也是研究生物学的工具，更是一种研究方法和手段。随着数学知识向遗传学研究中的不同层次和领域进行渗透，使的遗传学产生了许多分支学科如群体遗传学、数量遗传学、数量进化遗传学和系统生物学等。而这些学科的发展又反过来促进人们对遗传学现象认识的不断完善和升华，如数量遗传学否定了融合遗传理论，生物信息学的出现为解析基因的功能提供了新的思路和方法。由此可见将包括数学在内的其他学科的知识原理向遗传学教学以及科研进行交叉和融合，是遗传学学科自身发展的必然趋势。
参考文献：
遗传研究与应用 篇3
植物的性状分为质量性状和数量性状，两者在表现和遗传上是不同的。经典数量遗传学基于遗传学和统计学的一些假定，导出了一系列分析数量性状遗传的理论，大量实验数据证实在上述假定的基础上导出的基本公式与理论是有效的。然而，受上述假定的限制，有些研究难以深入，如多基因的基因效应被看成是微效和相等的。盖钧镒等认为大多数量性状多基因间的效应并不相等，也存在主效和微效之分，并依此提出了数量性状的泛主基因+多基因遗传理论；同时结合相应的统计学方法，建立了植物数量性状遗传体系。该遗传体系既可对单个分离世代(如F2、DH、RIL群體等)进行简单分离分析，还可结合不分离群体(如P1、P2和F1群体)进行多世代联合分析。该方法适用于育种工作者利用杂种分离世代的数据对育种性状的遗传组成做出初步判断，制定相应的育种策略，也可用于校验QTL定位所揭示的性状遗传组成。目前，该遗传理论已经将遗传模型拓展至4对主基因+多基因的分离分析方法，并在大豆、水稻、小麦、玉米、棉花以及西红柿、黄瓜等作物中得到了广泛的应用。本文则侧重探讨该遗传理论在小麦抗病、品质及产量相关性状研究中的应用，旨在分析小麦相关性状的遗传组成，为育种提供有益的参考。
遗传研究与应用 篇4
微动指来自于地表和底下深处的随机振动源引起的振幅非常小的地面微弱振动。包括人类等人工源引起的短周期震动和海浪及地球内部活动等自然力引起的长周期震动。
微动探测的主要方法有空间自相关法 (SAC) [1]和频率-波数法 (F-K) [2]两种。本文研究的是基于空间自相关法的微动勘探反演算法中遗传算法的应用于优化。
遗传算法 (Genetic Algorithms, 简称GA) [3]是一种基于生物自然选择与遗传机理的随机搜索与优化方法, 是由美国Michigan大学的John Holland教授创建的。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说, 其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。它本身不仅具有极强的鲁棒性, 还隐含着并行性, 同时还具有全局寻优能力。因此, 从一定意义上说, 遗传算法是一种普遍适用于各种问题的简单而有效的搜索方法。
1 遗传算法优化研究
1.1 遗传算法基本原理
基本遗传算法有五大要素构成:参数的编码方式、初始种群规模的设定、适应度函数的设计方法、各种遗传算子的设计和控制参数的设定, 他们组成了遗传算法的核心内容。[4]
(1) 编码:遗传算法不能直接处理问题空间的参数, 必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码。
(2) 个体适应度:在遗传算法中, 搜索进化的过程是根据评估函数值来对每个个体进行优劣评估的, 这个过程不需要其他外部信息作为参考。这里的评估函数值就是适应度。
(3) 算子;遗传操作中算子主要包括:选择算子、交叉算子以及变异算子三种类型。
(4) 控制参数:遗传算法中有其运行的基本参数被称作操作参数, 在研究优化问题之前必须提前设定这些参数。主要的参数有4种:
N:种群规模, 即种群中个体的数量
T:算法停止条件, 即种群进化代数
Pc:交叉概率
Pm:变异概率
遗传算法实质上是一种以群体和遗传操作为基础进行繁衍、监测和评价的迭代算法。在搜索之前, 将问题的解映射为一个解集空间, 解集空间是由一定数量的二进制个体组成的种群, 以这些代表问题假设解的种群开始, 我们要解决的一个问题就是根据问题的目标函数构造一个适应度函数, 以适应度函数为依据, 对种群中的个体进行评估, 从一大堆数据中寻找一个解。图1为遗传算法的流程图。
1.2 遗传算法优化研究
凭借遗传算法具备的非线性全局优化的能力, 它已经被广发的应用到了诸多领域中, 在微动面波反演的研究中也引入了此方法。但是在解决反演问题的过程中也暴露了一些不足之处, 首先标准遗传算法的计算过程中有早熟收敛[5]的现象, 这一现象致使算法全局寻优的优良性能不能完全显示出来, 其次遗传算法的收敛速度相比于其他传统算法比较慢, 效率低。因此, 针对以上暴露的不足, 本文从四个方面入手, 提出了遗传算法的优化策略, 具体的策略实施过程如下:
(1) 自适应函数的优化
在遗传算法中目标函数通常会作为评估函数值即适应性函数, 在遗传进化中, 超级个体可能会在群体中出现, 就是适应值比群体平均值大很多的个体, 如果根据适应值的比例选择时, 这类超级个体就会占有群体中的绝对比例, 这样算法在运算时就会过早的收敛于一个局部最优值, 这就是所说的早熟现象。下面通过引进一种线性变换来使原有适应性函数得到改变, 避免早熟收敛的发生。这里设f为已有的适应值函数, F为改变的适应值函数用线性组合F=af+b表示。并设定
公式 (1) 中k为一个固定的增量系数。
由上式得:
原有适应度经过线性的变换之后他们之间的差距得到了调整, 群体内多样性的个体得到了保证, 而且这个方法简便计算, 容易实现。
(2) 选择策略的优化
利用最优保存和赌轮[6]选择两种方式相结合的策略作为选择的方法。在群体中首先找到适应值最佳和最差的个体, 把最差的个体用最佳个体替换, 然后允许最佳的两个个体不经过交叉编译而进入下一代, 剩下的个体按正常进行排列, 最后再进行赌轮选择, 这样群体中平均适应值不断得到提高, 而且还使最佳个体的适应值不再减小。
(3) 变异策略的优化
在标准遗传算法中, 群体中单一性的产生有一部分原因是近亲繁殖造成的, 因此为了避免这类事件的发生, 可以让父母A, B多次交叉变异, 在产生的不同的多个个体中筛选出最佳个体放入子代中, 对上述步骤反复执行, 直到子个体数量得到满足。
(4) 遗传操作算子的优化
遗传算法有收敛过早的缺点, 这一缺点是由于同位基因数目不同概率不等, 在进化中某些特定基因越来越少, 造成基因缺失, 致使收敛过早。针对这一现象, 本文引入多元算子到遗传算法中来。例如对二元字符串结构进行变异, 通过同或异或的运算保留了特定基因的多样性, 极大地避免了收敛过早的问题。例如:
经过同或异或后两种逻辑状态必定互补。
根据以上优化策略优化后的遗传算法执行顺序如下:
(1) 子群体的个数要首先确定, 对子群体初始化, 子群体每个的规模是N, 进一步对重新分配的子群体确定进化代数;
(2) 根据规则1, 把各子群体的父代适应值求解;
(3) 对各个子群进行选择操作;
(4) 获取各子群体繁殖的下一代, 变异的规则采用二元变异;
(5) 查看终止条件是否满足, 如过满足, 就退出;
(6) 如果进化代数满足了重新分配子群体的数量, 就开始对子群体重新分配;
(7) 回到 (2) 。
1.3 实验测试
遗传算法的随机优化计算的特点, 使其受参数的影响很大, 参数的不同会使算法对问题的计算产生不同的影响, 恰当的参数可以加速算法早熟收敛, 相反不合适的参数会致使遗传算法收敛变慢, 因此使得计算后无法寻得最优解。然而确定选取什么样的参数目前还没有有效的解决办法。本节从两个不同的方面对优化后的遗传算法进行了测试, 验证优化后的效果和其对参数的敏感度。实验所用函数为
遗传算法对比实验
将遗传算法同优化后的遗传算法进行对比。种群规模设为100, 交叉概率0.72, 变异概率0.15。实验结果如下表。
通过以上实验, 可以看出, 优化后的遗传算法增强了自身的寻优能力, 减少了迭代次数, 明显改善了早熟收敛的情况, 另外优化后的算法参数的选择范围扩大, 参数的选择对算法的影响减小了, 使得算法能够更方便的在实际中应用。
微动反演中遗传算法的实际应用与优化。
选择表2中的模型进行反演, 理论数据根据knoppoff算法的速度递增层模型正演计算得到理论频散曲线。
层状介质微动面波速度反演中反演参数是横波速度VS以及厚度d。纵波速度VP通过下面关于横波速度VS与泊松比μ关系的公式计算:
密度ρ根据纵波速度和密度的统计关系得到。因此实际反演中只对各层的横波速度和层厚度参数反演。因此, 输入参数为各层横波速度和层厚度的上下限。算法目标函数计算式为
式中Viobs是第i个频点上观测的微动面波速度, Vithe是每代在确定模型参数后, 计算得到的同一频点的微动面波速度值, N是频点的个数, 每次迭代时的每个个体是F, 就是模型的参数。
反演结果 (表2所示) 就是获得一组模型的参数, 此组模型参数让上式表述的目标数取值达到最小。所以, 这里就是求解目标函数的最小值。从表2中可以看到优化后的遗传算都各参数的反演结果的相对误差均优于标准遗传算法, 各层的相对误差均不超过10%。结合实际, 进行多次的试算, 具体采用以下参数:种群大小为40-60个, 遗传代数为160代;交叉概率为Pc1=0.92, Pc2=0.75, Pc3=0.6, 遗传概率Pm1=0.1, Pm2=0.09, Pm3=0.01。
由表2和图2所示可以看出, 优化的遗传算法反演结果的相对误差均低于标准遗传算法。从图3和4中可知, 两种方法一般在40-60代就得到最佳解, 其中优化的遗传算法反演1的收敛速度最快, 约在第25代即获得最佳解的。优化的算法运算速度比标准算法提升了2个数量级。
2小结
遗传研究与应用 篇5
摘 要： 由于实体商业市场缺乏像电商平台那样的个性化交互平台，因此无法对客户进行精准营销，使得在商业市场上的竞争力越来越弱。为了解决这一问题，引入商家基因库模型，并记录客户在实体店铺中的历史购物行为、关注的产品类别等，结合最佳邻居、效用函数等提出赋有权重的客户偏好模型。利用改进遗传算法对商家基因库模型与客户偏好模型进行匹配，以实现精准营销。研究以大数据为背景，利用Hadoop集群的MapReduce编程实现改进遗传算法，用以在n维商家空间中快速、精准地找出最符合客户需求的商家。实验结果表明，改进遗传算法相对于传统遗传算法在推荐准确率上平均提升15.6%，在推荐响应时间上提升41.9%。
关键词： 改进遗传算法； 精准营销； 商家基因库； 客户偏好模型； 范围相似度函数； 大数据
中图分类号： TN911.1?34； TP312 文献标识码： A 文章编号： 1004?373X（2018）13?0177?05
Abstract： The entity commerce lacks of personalized interactive platform as the e?commerce，and can′t perform the precision marketing for client，so the competitiveness becomes weaker in commercial markets.For the above problem，the merchant gene library model is introduced，the historical shopping behavior and concerned product category of entity stores are recorded for clients，and the best neighbor and utility function are combined to propose the client preference model with weighting.The improved genetic algorithm is used to match the merchant gene library model with client preference model to realize the precision marketing.On the basis of big data，the MapReduce programming of Hadoop cluster is adopted to improve the genetic algorithm，which can quickly and accurately find out the merchant mostly meeting the requirements of client in n?dimensional merchant space.The experimental results show that the recommended accuracy of the improved genetic algorithm is 15.6% higher than that of the traditional genetic algorithm，and the recommended response time is improved by 41.9%.Keywords： improved genetic algorithm； precision marketing； businesses gene library； client preference model； function of range similarity； big data 0 引 言
?S着“互联网+”的浪潮席卷而来，传统实体商业（如百货商场）却在此次浪潮中受到非常大的冲击。根据iziRetail抽样调查数据显示，2016年上半年全国近六成的百货商场业绩处于下滑状态，很多商场甚至濒临倒闭或者已经倒闭的状况。因此，对于目前的大型实体商业而言，积极探寻新的经营理念，利用先进大数据技术，在新时代、新环境下实现商业模式转型，是目前所有实体商业领导者亟待解决的问题。
研究以某大型实体商业为背景，首先对商场中所有商家所售产品建立商家基因库模型[1]；然后根据客户在此商场中的消费记录、当前关注的产品类别等信息，使用聚类算法构建带权重的客户偏好模型；最后利用改进的遗传算法实现在商家基因库及海量客户群之间快速、精准的匹配，获得匹配度从高到低的推荐列表，并利用新媒体方式为每一位客户实现个性化推荐，以达到精准营销的目的。研究所有模型均建立在大数据分布式处理Hadoop 2.0平台上，此平台本身保证了模型的可用性、高效性及扩展性。
以餐饮业为例，传统遗传算法匹配度在70%～75%范围内的数据有1 140 528条，高于改进遗传算法，其在75%～100%范围内的数据则低于改进遗传算法，推荐率在传统遗传算法基础上平均提高15.6%。改进遗传算法优于传统遗传算法的原因有以下两点：
1）在传统遗传算法之前加入k?means算法对数据进行初始聚类，将商家基因累积，抬高特征值，加快遗传算法对特征基因的识别和匹配分析。
2）在使用传统遗传算法之后加入范围相似度函数求被推荐用户的亲密好友f，对遗传算法得出的相似最优解集做出最优选择，使最优解的范围更精确。4 结 语
本文提出一种改进遗传算法，即首先在传统算法之前加入k?means算法，使数据源特征更具有集中性，再应用遗传算法得出相似最优解集，最后使用自定义范围相似度函数求解推荐率。以上所有算法均采用Hadoop集群MapReduce编程模型并行实现。
本文提出的算法仍有需要改进的地方，以下几个方面需要基于实际情况不断完善。
1）利用k?means算法对用户和商家数据进行初始聚类，其中对[k]值的确定有待完善，当用户和商家的数据有变动时，所确定的[k]值就需要更新。
2）对新用户的数据采集方式可以更具个性化，提高新用户数据参数的精确度以及快速有效地采集并存储其数据，进行精准计算。
3）在计算最终推荐率时，将相似最优解放入[n]维空间中，以其为圆心，人为设定阈值为85%，在此范围的即为最优解的“亲密好友”[f]。因此，在寻找最优解的亲密好友时可以设定一个算法自动确定以最优的相似程度范围取值。参考文献
遗传研究与应用 篇6
【摘 要】将广西卫生职业技术学院2012级检验1班和检验2班分为实验组和对照组，实验组采用TBL教学法授课，对照组以传统教学法进行授课。结果表明：在医学遗传学教学中TBL教学模式能提高学生学习积极性，增强自学能力，促进团队协作交流，教学效果优于传统教法。
【关键词】TBL教学法 医学遗传学 教学改革
【中图分类号】 G 【文献标识码】A
【文章编号】0450-9889（2014）07C-0135-02
医学遗传学是目前医学中最前沿的学科之一，其利用DNA技术研究遗传性疾病的发生机制、传递方式、诊断、治疗、预后、再发风险和预防方法，从而达到控制遗传性疾病的再发，降低其在人群中的危害，提高人类健康水平之目的。医学遗传学既是一门综合性很强的基础课程，又与临床医学紧密相连，其课程知识点繁多，覆盖面广，更新速度快，与其他学科交叉紧密，因此，在传统教学模式下，学生容易出现学科体系不清晰、重点内容不易消化、感觉教学内容枯燥乏味、学习缺乏积极性等问题。显然传统的教学模式已经无法满足新的教育环境下对医学生综合素质全面提高的要求了，这就需要新颖、高效、优质的教学模式加入，并逐步完善。以团队为基础的教学模式（team-based learning，TBL）是以团队为基础，通过将教师讲授和学生讨论有机结合而形成的教学模式，它是美国Oklahoma大学 Larry Michaelsen教授在优化改进以问题为基础的教学模式（problem-based learning，PBL）后，于2002年提出的一种新的教学理念。该教学模式体现了以学生为主体的教学思路，鼓励学生通过团队协作的方式分析问题、解决问题，有效的提高了学生的学习积极性、主动性和团队合作精神，也带来了很好的教学效果。现将TBL教学法引入医学遗传学教学中，通过积极的实践和优化，争取不断提高医学遗传学的教学质量。
一、对象与方法
（一）研究对象。选取广西卫生职业技术学院2012级检验1班和检验2班作为研究对象。检验1班58人作为实验组，检验2班58人作为对照组。两组年龄、综合素质等比较，差异无统计学意义（P>0.05）。
（二）研究方法。对照组采用传统的讲授式教学方式。实验组采用TBL教学模式：授课前，教师要提前一周将与课程内容相关的预习资料发放给学生，供学生预习；对学生进行分组，每组5-7人，分组的原则是成绩优异的学生和成绩一般的学生搭配，积极主动的学生和消极被动的学生搭档，做到组内异质、组间同质。课堂内容包括4个部分：（1）个人测验（10min），先发放试题和答题卡对学生进行一次基础知识测验，由每个学生独立完成，检查学生的预习效果；（2）团队测验（20min），再次发放试题和答题卡给学生进行测试，但这次允许小组内的成员进行讨论，最后得出组内统一的意见；（3）汇报讨论（45min），各小组选派一名代表汇报组内讨论的结果，并针对问题提出相关理由，持有异议的其他小组成员可以通过相互辩论的方式发言；（4）评价总结（15min），教师点评、总结讨论发言和团队协作情况，解释同学们讨论中出现的疑问，总结知识点并提出改进意见。
（三）评价方法。包括：（1）学期末进行医学遗传学闭卷期末考试进行比较；（2）发放教学调查表，统计学生对TBL教学模式的满意度。相应数据使用SPSS 13.0软件进行分析，计量资料采用t检验，计数资料采用x2检验，比较两组教学效果。
二、结果
（一）两组学生医学遗传学考试成绩比较（见表1）。从表1可以知道，两组学生在医学遗传学考试成绩上存在显著差异，t=8.397，P<0.05，实验组的考试成绩优于对照组。
（二）两组学生医学遗传学教学满意度调查表（见表2）。在医学遗传学教学课程结束后，发放教学调查表，分别调查学生对传统教学模式（对照组）和TBL教学模式（实验组）的满意度，发放调查表116分，回收116份，回收率100%。实验组满意率与对照组满意率存在差异，P<0.05，学生们对TBL教学模式更满意。
三、讨论
（一）TBL教学模式能有效激发学生的学习积极性和主动性。TBL教学模式改变了传统教学模式以教师为中心的教育思路，真正体现了以“以生为本”的理念。在上新课前，学生会通过查阅医学杂志、搜索互联网等方式提前准备教师布置的预习资料，一方面提高他们的自学能力、信息检索分析能力，另一方面也增强他们的学习积极性。在TBL教学过程中，以往灌输式的讲授方式被学生分组讨论和教师指导取代，使得枯燥乏味的医学遗传学知识更容易被学生接受，在不断讨论学习的过程中他们会用这些知识点去分析问题、解决问题，因此知识点也更容易被记住、记牢。这在一定程度上会促使学生变被动为主动，激发他们的学习动力。
（二）TBL教学模式能培养学生团队协作能力。TBL教学本质上是一种以小组为单位的集体学习，它以团队为基础，团队中的成员都有不同的任务，如果一个成员不能完成他的任务，那么就会影响到整个团队的成绩，这就要求这个团队分工明确、管理合理、责任清晰才能能高效运作。学生在收集相关资料、讨论分析的过程中，就要与小组其他成员不断进行交流、学习、互助，在互动过程中就会逐渐拉近与他人的距离，培养了团队协作能力，有利于以点带面、以面带片，最终实现组内、组间及全班学生的共同进步。
（三）TBL教学模式能提高教师教学能力和水平。与以往的传统讲授式教学模式不同，TBL改变了教师为中心的模式，这也对教师的教学能力和水平有了更高的要求。在TBL教学模式中，教学的主体已由教师转变为了学生，教师在教学过程中主要的作用是组织课堂、激励团队学习、引导讨论等，这就要求教师具备更加全面、广博的知识，丰富的教学经验，而且具有较强的组织沟通能力。另外，医学遗传学是一门跨专业、融合性很强的前沿学科，知识更新快，需要教师在TBL教学前，不断的通过自学、进修、网络等方式了解本学科及相关学科的前沿知识和技术，这样才能更好地准备教案，将医学遗传学这门学科上好，同时也能不断提高教师教学能力和水平。
TBL教学模式是一种新颖的教学方法，它克服了传统教学模式的部分缺陷，在引入医学遗传学教学中后，我们发现它能有效提高学生的学习积极性和主动性、增强学生团队协作能力，并且有利于提高教师的教学能力和水平。随着TBL教学模式不断完善和改进，这种先进的教学方法必定会对医学教育改革起到推动促进作用。
【参考文献】
[1]傅松滨. 医学遗传学[M].北京：北京大学医学出版社，2009
[2]郭艳红，黄文君，辛敏，等. TBL教学模式在地方医学院校生理学教学中的应用[J].基础医学教育，2013 （2）
[3]谭波涛，潘丽萍，梁红，等. TBL结合LBL模式在生理学教学中的应用研究[J].中国高等医学教育，2012（11）
[4]万能章. TBL教学法对病理学教学效果的影响[J].中国高等医学教育，2011（8）
【作者简介】赖燕燕，女，硕士，广西卫生职业技术学院讲师，研究方向：医学遗传学教育。
遗传研究与应用 篇7
入侵检测通过对计算机和网络资源上的恶意使用行为进行识别和响应, 检测来自外部入侵行为和内部用户的越权行为和滥用 (Misuse) 行为。根据入侵检测所采用的技术把它们分为两大类:异常检测 (Anormaly detection) 和误用检测 (Misuse detection) 。异常检测假定所有的入侵行为都跟正常行为有区别, 这意味可以为系统建立一个正常行为的描述, 理论上可以根据与正常行为的偏离程度来检测入侵行为, 而且可以发现新的入侵行为。误用检测则基于以下事实:能通过某些方式把攻击表示成各种模式, 然后运用模式匹配检测入侵。同时, 这也意味着它们跟病毒检测系统一样, 对已知攻击有着良好的检测效果, 但对未知攻击却无能为力。当前入侵检测系统面临的主要问题是:面对新的攻击或新的环境, 需要建立新的规则库 (误用检测) 或新的系统的正常行为描述 (异常检测) , 而现代入侵方法的多样化的趋势越来越明显, 传统的基于专家知识的手动更新已无法满足当前的需要, 从而造成了攻击特征库或系统正常行为描述更新不及时, 最终导致了高误报率和高漏报率。
近年来, 新墨西哥大学的Forrest等人, Lee等人和Wespi等人研究并发展了一种基于进程运行中的一系列系统调用序列的检测模型, 并用实验证明了有很好的效率, 然而实用起来也有一定的困难。粗糙集理论是由波兰学者Pawlak于1982年提出的, 它作为一种刻画具有不完整性和不确定性信息的全新的数学工具, 其主要思想是:在保持知识库的分类能力不变的前提下, 通过知识 (属性) 约简得出问题的决策或分类规则。目前粗糙集理论已被成功地应用于机器学习、决策分析、过程控制、模式识别与数据挖掘等领域。粗糙集理论的优点是:除了问题所需处理的数据集, 不需要其他先验的知识;利用定义在数据集合U上的等价关系R对U的划分作为知识;它能处理知识的不确定性和不精确性, 是一种客观的数据推理方法。随着粗糙集理论的兴起, 其在处理大量数据, 消除冗余信息方法的优势逐渐引起人们的兴趣, 于是基于粗糙集理论的属性约简方法的入侵检测系统被越来越多的人研究。遗传算法是一种非常有效的全局寻优的优化技术, 具有鲁棒性、隐含并行性和全局搜索等优点。本文利用粗糙集的约简技术结合遗传算法全局搜索的优点, 提出一种针对入侵检测系统的新的遗传-粗糙集算法 (GAR) , 可以很好地提高入侵的检测性能。
1 基于粗糙集-遗传算法的入侵检测方法
1.1 粗糙集理论
粗糙集作为集合论的扩展, 用于研究不完全和不完整信息描述的系统, 它把知识看成是对有关对象论域的划分。粗糙集理论支持数据挖掘系统的多个步骤, 具体包括:信息系统的表示, 数据规约以及规则生成等。
定义1:在粗糙集中, 信息系统是1个二元组I= (U, A) , 其中U是一个非空的有限集合, 称为论域, A是一个非空的有限的属性集合。即对a∈A, a:U→Va, Va是属性a的值域。决策表是形为I= (U, A∪{d}) 的信息系统, 这里dA是决策属性, a∈A是条件属性。
定义2:给定I= (U, A) , 对于属性集BA, 定义IND A (B) ={a∈B, a (u) =a (u') }为A中的B不可分关系。满足关系IND A (B) 的对象u, u'对B中的属性是不可分辨的。
定义3:给定信息系统I= (U, A) , 对于属性集合BA和对象集合XU, 集合BX={x∈U:[X]BX}X={x∈U:[X]B∩x≠}称为X的B的下近似集和上近似集。集合BNB (X) =X-BX称为X的B边界域;POSB (X) =BX称为X的B正域NEG B (X) =U-X称为X的B域。显然X=POSB (X) ∪BNB (X) 。
定义4:属性a∈BA称为B中不必要的, 如果INDA (B) =INDA (B-{a}) ;否则称a为B必要的。如果每一个a∈B都为B中必要的, 则称B为独立的;否则称B为依赖的。
定义5:集合BA, 如果B是独立的, 且INDA (B) =INDA (A) , 则称B为A的一个约简。集合A的所有约简记作RED (A) , A中的所有必要关系组成的集合称为A的核, 记作CORE (A) , 核和约简有如下关系:CORE (A) =∩RED (A) 。
1.2 遗传算法
遗传算法是一种通过模拟自然进化过程搜索最优解的方法。
遗传算法的主要特点是:
(1) 具有高度的鲁棒性, 擅长全局搜索, 可以避免在局部最优解附近徘徊;
(2) 具有良好的并行性, 操作对象是一组可行解, 同时搜索;
(3) 通用性好, 只需利用目标函数的取值信息。
主要运算过程如下:
(1) 随机产生一定数目的初始染色体, 构成种群;
(2) 用评价函数评价每个染色体的优劣;
(3) 进行选择过程, 选择优良的染色体, 形成新的种群;
(4) 对新种群进行交叉和变异操作, 得到后代, 并构成新的种群;
(5) 对新种群重复选择、交叉和变异操作, 经过设定次数的迭代或满足了设定好的结束条件, 就可以将得到的我们认为最好的染色体作为解输出。
1.3 混合遗传算法求解粗糙集的约简
在决策系统的实际应用中, 识别相关属性 (属性域) 是数据挖掘的关键, 对属性进行约简或规约, 能够减少信息的处理量和存储量。基于粗糙集理论的数据约简的基本原理是通过求属性重要性并排序, 在泛化关系中找出与原始数据具有同样决策或分辨能力的相关属性的最小集合, 实现信息约简, 以便产生更简洁、更有意义的知识规则。计算属性集的最小约简是个NP难问题, 所以必须要应用启发式的近似算法来缩短计算时间, 以便得到一个好的, 但可能不是最优的解。由于启发式算法的结果依赖于算法的初始状态或算法的参数, 因此利用遗传算法来寻找更优的初始状态或算法的参数。二者结合而成的混合遗传算法集合了遗传算法和启发式算法的优点, 利用启发式方法作局部优化, 采用遗传算法作全局最优点搜索, 能够在更短的时间内产生更好的属性集的约简。
1.3.1 混合遗传算法的基本策略
(1) 找到一个能给出近似解的启发式算法;
(2) 更改算法, 使算法接受一个为控制序列的参数, 并使算法的结果依赖于这个序列;
(3) 把控制序列编码为一个染色体;
(4) 使用遗传算法来产生控制序列, 然后执行接受这个控制序列的启发式算法, 令算法产生的解的品质为这个序列的适应度;
(5) 进化的结果是产生更优的控制序列, 也就是这个序列能使启发式算法产生更优的解。
1.3.2 产生约简的启发式算法
实验采用了一个简单的、确定性的启发式算法产生属性集的约简, 具体步骤如下:
(1) R为数据集的属性的集合, 令 (b1...bn) =τ (a1...an) 为所有属性的一个有序队列, 以数列τ表示顺序;
(2) 对i=1到n, 执行步骤 (3) 和步骤 (4) ;
(4) 如果R不是约简, R=R∪bi。
算法产生的解总是1个约简, 并且算法的解依赖于属性序列τ (a1...an) , 所以此算法满足混合遗传算法对启发式算法的要求。
2 实验结果和分析
实验中使用了KDDCup99的数据作为训练和检测数据。KDDCup99的原始数据来自于1998年的DARAP入侵检测评估项目, 所有的网络数据来自于一个模拟的美国空军局域网, 网络中加了很多模拟的攻击。实验的训练数据为7周的网络流量, 这些网络流量包含有约500万条网络连接;实验的测试数据为2周的网络流量, 包含有约200万条网络连接。该网络环境中模拟的攻击分为四大类, 如表1所示, 正常的网络连接标记为normal。
实验数据的每一条记录有41个属性, 这些属性可以分为三类:单个tcp连接的基本属性、基于领域知识的连接的内容属性、使用时间窗口为2秒的流量属性。每条记录中的41个属性, 反映TCP连接的基本属性, 包括连接持续时间, 服务端口, 协议类型, 收发字节, 错误包数量和urgent包数量, 连接结束状态;还包含根据专业知识收集的属性, 包括文件产生操作的次数, 登录失败的次数, 是否是root等;以及在2秒钟的时间窗口内收集的统计属性, 包括过去2秒钟内与当前连接的目的主机相同的连接数量, 过去2秒钟内与当前连接请求的服务相同的连接数量, 相同主机的连接中包含SYN错误的百分比, 相同服务的连接中包含SYN错误的百分比, 相同主机的连接中包含REJ错误的百分比, 相同服务的连接中包含REJ错误的百分比等。
实验采用的粗糙集工具RSES (Rough Set Exploration System) 是波兰Warasw和Rzeszow University共同开发的一个具有友好界面的图形化数据分析软件。对数据离散化后, 我们对属性进行约简, 删除那些对生成检测规则无用的属性, 这样就能够减少信息的存储量和处理量。基于粗糙集理论的数据约简的基本原理是通过求属性重要性并排序, 在泛化关系中找出与原始数据具有同样决策或分辨能力的相关属性的最小集合, 实现信息约简, 以便产生更简洁、更有意义的检测规则。最后, 我们以产生的约简为模板, 生成入侵检测规则, 产生的规则具有”IF-THEN’, 的形式。以实验中生成的4个属性集约简为模版我们共生成了365条检测规则, 检测规则的形式如下:
”=>”的左边表示条件属性, 右边表示决策属性, 即分类结果, 方括号内的数字如3600、33表示匹配这条规则的训练数据中网络连接。以第一条检测规则为例, 持续时间小于1.5秒、协议类型为Private、从源主机到目标主机的数据在19bytes和28.5bytes之间且从目标主机到源主机的数据小于79.0bytes的为DoS攻击, 满足这条规则的训练数据有33条。我们用生成的检测规则对测试数据进行分类, 所得到的混淆矩阵如表2所示。
从表中可以看出, 本文提出的基于粗糙集的网络入侵检测方法具有高检测率、低误检率。对于normal连接、DoS和probe攻击的检测率很高 (>97.2%) , 这在现实中有很大的意义, 因为这三类连接往往在数据集中占很大的比例, 例如在KDDCup99的10%的训练和测试数据中三者总合占95%以上。而且本方法对U2R和R2L攻击也有较高的检测率, 虽然低于前三者, 但大于KDDCup99的最好结果3.5% (U2R) 、0.6% (R2L) 。虽然U2R和R2L攻击在数据集中占很小的比例 (<5%) , 但是由于U2R和R2L攻击的危害性较大, 如窃取管理员权限等, 如果能有效地检测出U2R和R2L攻击, 则对入侵检测系统性能的提高是非常明显的, 能够更有效的保护网络环境。
3 结论
本文提出的结合遗传算法与粗糙集的入侵检测方法, 融合了粗糙集和遗传算法两者的优点。GAR系统可以用遗传算法弥补粗糙集传统约简方法在海量数据时所显的不足, 从而在面对海量的网络信息和系统程序调用序列时, 仍然可以快速准确地得到最小决策规则集, 用于指导入侵检测系统。
通过遗传算法使原来基于粗糙集的方法更加适用于信息量日益增大的今天, 大大提高了入侵检测方法的实用性。相信基于遗传-粗糙集方法的入侵检测方法将有广泛的应用前景。
参考文献
[1]Lee W K, Stolfo S J, Mok K W.A Data Mining Framework for Building Intrusion Detection Models[C].Proceeding of the 1999IEEE Symposium on Security and Privacy.1999.
遗传研究与应用 篇8
常规的系统评价方法存在一个共同特点,即采用“对数据结果或分布特征先作某种假定——按照一定准则建立显式评价函数——对建立的评价函数模型进行证实”这样一条证实性数据分析方法。目前常用的评价方法有:模糊综合评价方法在对各指标进行“特征化”处理后,会出现不同程度的信息丢失,为评价结论带来误差;AHP法和灰色关联评价法具有能解决多目标、多层次、多准则决策问题的优势,但评价结果往往受主观因素的支配与干扰;基于特征向量的最优综合评价法,不需人为确定权重,评价结果接近实际,但难于从系统各层次把握被评对象的综合水平及应采取的技术措施。而且由于数学化、形式化等局限性,这类方法对于处理某些高维度、非线性,非正态评价问题的适应能力不强。
针对上述问题, 学术界提出了直接由样本数据驱动的探索性数据分析方法,投影寻踪(Projection Pursuit,PP)方法[1,2]是这类方法的典型代表。所谓投影寻踪就是将高维数据向低维空间投影, 通过分析低维空间的投影特性进而来研究高维数据的特征, 是处理多因素复杂问题的统计方法。投影寻踪聚类(Projection Pursuit Cluster,PPC)模型则是依据投影寻踪思想建立的聚类分析模型, 它已被广泛应用于模式识别和多因素分析领域[3,4,5,6,7,8,9,10,11,12]。其基本思想是:把高维度的数据通过一定的组合投影到低维度子空间上,对于投影到的构型,采用投影指标函数(目标函数)来描述投影值,进而暴露原系统综合评价问题某种分类排序结构的可能性大小,寻找出使投影指标函数达到最优(即能反映高维度数据结构或者特征)的投影值,然后根据该投影值来分析高维度数据的分类结构特征(即投影寻踪聚类评价模型)。其中,投影指标函数的构造及其优化问题是应用PP方法能否成功的关键因素,其复杂性在一定程度上限制了PP方法的深入研究和广泛应用。为此,本文提出基于实数编码的加速遗传算法(Real coding based Accelerating Genetic Algorithm,RAGA)的投影寻踪聚类评价模型,并开展了相应的应用研究。
2 基于遗传算法的投影寻踪聚类评价模型
基于RAGA的投影寻踪聚类评价模型(Projection Pursuit Classification model based on RAGA,RAGA—PPC模型)的建模过程包括以下四个步骤:
(1)评价指标值的无量纲化
设各指标值的样本集(评价对象集)为{x*(i, j)|i=1～n, j=1～p}。其中x*(i,j)为第i个样本第j个指标值,分别为样本的个数(样本容量)和指标的数目。为消除各指标值的量纲和同意各指标值的变化范围,采用下式进行极值归一化处理:
式中, xmax(j), xmin(j)分别为样本集中第j个指标值的最大值和最小值。
(2)构建投影指标函数
PP方法就是把p维数据{x(i,j)|j=1～p}综合成以a=(a(1),a(2),…,a(p))为投影方向的一维投影值z(i):
然后根据{z(i)|i=1～n}的一维散布图进行分类。式(2)中的a为单位长度向量,即
在综合投影值时,要求投影值z(i)的散布特征应为:局部投影点尽可能密集,最好凝聚成若干个点团;而在整体上投影点团之间尽可能分散开。基于此,投影指标函数可构造为
式中, Sz为投影值z(i)的标准差, Dz为投影值z(i)的局部密度,即
式中,
(3)优化投影指标函数
① 投影指标函数的优化
当各指标值的样本集给定时,投影指标函数Q(a)只随投影方向a的变化而变化。不同的投影方向反映不同的数据结构特征,最佳投影方向就是最大可能暴露高维度数据某类特征结构的投影方向。可通过求解投影指标函数最大化问题来估计最佳投影方向,即
这是一个以{a(j)|j=1～p}为优化变量的复杂非线性优化问题,用常规优化方法处理较困难。模拟生物优胜劣汰规则与群体内部染色体信息交换机制的加速遗传算法(RAGA)是一种通用的全局优化方法,可用它来求解上述问题较为简便和有效。
② 基于实码的加速遗传算法原理及实现的流程
基于实码加速遗传算法(RAGA)的选择、交叉、变异是并行处理的,因此RAGA实际搜索范围广,得到全局最优点的机会也大。RAGA的循环可逐步调整、缩小优化变量的寻优区间,解的精度随着循环次数的增加可望逐步提高。
基于实码的加速遗传算法是分别在父代群体的基础上通过选择、交叉、变异算子得到3个子代群体,选择N(群体规模)个优秀个体作为下一代父代群体。有限次运算后进行加速遗传,缩小优秀个体选择的区间(分别将M次演化迭代的S个优秀个体共M×S个体的变化区间作为下一次加速遗传的变量区间),这样演化迭代与加速遗传的反复交替进行可实现遗传进化逐步向最优个体逼近,并且随着接近优秀个体,个体的密度加大,这样可在一定程度上减少早熟收敛的机率。加速遗传算法的流程见图1。
(4)聚类(优序排列)
把由(3)求得的最佳投影方向a*带入式(2)后即得各样本点的投影值z*(i)。投影值z*(i)与z*(j)越接近,表示样本i与样本j越倾向于归为一类。按z*(i)值从大到小排序,据此可把对样本集进行分类。
3 实例运用与分析
现以南京地区(5县4区)的农业生产力综合评价为例[13],进一步说明RAGA—PPC模型的应用。农业生产力综合评价指标体系包括劳动生产率、土地生产率、农业总产值、化肥用量、机械总动力、农村用电量、有效灌溉率、耕地复种指数、每劳动力负担耕地能力、净产值率、水稻气候生产力和小麦气候生产力共12项评价指标,因而指标样本集共有9个(5县4区),12个评价指标(已归一化处理),详见表1。
把该样本集依次代入式(2)、式(4)、式(5)、式(3),即得此例的投影指标函数,然后根据式(6)和式(7)所确定的问题,用RAGA进行优化,即可得到最大投影指标函数为1.02, 最佳投影方向a*=(0.348,0.125,0.095,0.046,0.279,0.503,0.188,0.302,0.286,0.427,0.249,0.262)。把a*代入式(6)后即得个样本的投影值z*(i),结果见表1和图2。
由表1和图2可知:
①该样本集按投影值的大小(即农业生产力综合水平从高到低)排序的样本序号依次为3(江宁县)、9(雨花区)、5(高淳县)、8(栖霞区)、1(六合区)、4(溧水县)、6(浦口区)、7(大厂区)和2(江浦县)。其中样本3和9可评为优,样本5、8和1可评为良,样本4、6和7可评为中等,样本2可评为差。该评价结果于文献[13]的最优综合评价法和多层次灰色关联评价法的结论基本一致。
②根据最佳投影方向,可进一步分析各评价指标对评价结果的影响程度。在本例中, a*值说明, 评价指标6、10、1、8、9、5、12、11、7、2、3和4对评价结果的影响程度依次减小,这可为各地区进一步提高农业生产力水平提供决策依据。
4 结论
投影寻踪模型(PPC)作为一种统计方法,将高维数据通过寻求最佳投影方向映射到低维子空间,将多项系统指标压缩为单向指标进行系统决策评价,可在很大程啡上避免个人主观因素对决策的不良影响,适用于数据量丰富、指标层明晰的评价体系。将基于实码的加速遗传算法(RAGA)与投影寻踪相结合, 解决了高维数据全局寻优的难题, 大大减少了寻优工作量,为高维指标评价与决策研究提供一条新的方法与思路。
本文给出了RAGA—PPC建模的详细步骤,采用实码加速遗传算法简化了投影寻踪的实现过程,克服了传统投影寻踪方法计算复杂、编程实现困难的缺点,并将其应用于农业生产力综合水平评价决策中,不仅得出南京各个区县的综合评判优劣排序, 而且由优化投影方向反映出各个评价指标对各样本总体评判的重要程度,其计算简便,适用性强,评价结果更加准确客观,为投影寻踪方法在各种综合评价中的推广应用提供了强有力的工具。
摘要：针对农业生产力综合评价这类高维指标体系决策问题,采用降维技术:投影寻踪分类模型,利用基于实数编码的加速遗传算法优化其投影方向,将多维数据指标(样本评价指标)转换到低维子空间,根据投影函数值的大小评价出样本的优劣,从而做出决策。该模型最大限度地避免了传统评判中权重取值的人为干扰,评价结果更为准确客观,为农业生产力综合评价决策及其它评判决策问题提供一条新的方法与思路。
遗传算法的应用及研究分析 篇9
1.1 编码
编码是把一个问题的可行解从其解空间转换到GA所能处理的搜索空间的转换方法。而解码是由GA解空间向问题空间的转换。编码机制直接影响着算法的整体性能,也决定了种群初始化和各种遗传算子的设计等各种过程。常用的编码方案有:二进制编码、Gray编码和实数编码等。
1.2 种群的初始化
种群的初始化是指如何生成第一代初始种群。对于二进制编码机制,初始化就是生成多个二进制数串;对于实数编码机制,初始化是指生成多个实数数串。
1.3 适应度函数
适应度是用来衡量群体中各个个体在优化计算中能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大;反之遗传到下一代的概率就相对较小。度量个体适应度的函数称为适应度函数,是根据目标函数确定的,用于区分群体中个体好坏的标准,是算法演化过程的驱动力。
1.4 选择算子
选择算子是从一个旧种群选择生命力顽强的个体位串进行复制,从而产生新种群的过程。不同的选择操作会导致不同的选择效果,较大的选择压力将会使当前种群中的最优个体具有较高的复制数目,算法会以较快的速度收敛,容易出现“早熟”问题。相反,较小的选择压力能使种群的保持多样性,有利于跳出局部最优,收敛于全局最优点,但缺点是收敛速度慢,效率低下。常用的选择算子有:轮盘赌选择、基于排序的选择、局部竞争选择、最佳个体保存选择和Boltzmann选择等。
1.5 交叉算子
交叉算子是指两个相互配对的染色体按照某种方式相互交换自身的部分基因片,从而构成两个新个体的过程。交叉算子不仅要考虑生成更多不同的个体,保持种群的多样性;还要避免破坏种群中的优良个体,加快种群的收敛速度,才能使种群的多样性和收敛性达到和谐的统一。常用的交叉算子有:单点交叉、多点交叉、均匀交叉和算术交叉等。
1.6 变异算子
变异是指父代染色体中的某些基因片,以相对较小的概率发生随机改变的操作过程。变异的概率决定了种群中个体发生变异的机会大小,如果制定过高,容易破坏种群中已有的优良个体结构;如果制定过低,则产生新个体的速度慢,收敛速度慢,甚至可能陷入局部最优。常用的变异算子有:倒位变异、交换变异和插入变异等。研究表明,将多种变异算子在交叉使用或者按照一定的概率进行分配使用,会带来较好的效果[1]。
2 GA遗传算法的特点
2.1 遗传算法相对于其它算法的优越性
(1)GA从问题的初始解集开始嫂索,而不是从单个解开始,覆盖面大,有利于全局择优从而有效地避免局部最优解的干扰。
(2)GA不是对问题的待优化参数本身进行操作,而是通过由这些参数所编码形成的染色体进行交叉,变异和选择等操作,参与操作的信息量大,速度快,效果好,比较容易获得全局最优或逼近全局最优。
(3)GA求解时使用特定问题的信息极少,容易形成通用算法程序,对于有待优化的函数数学限制较少,既不要求可导可微,也不要求函数具有连续性,通用性好,鲁棒性强。
(4)GA通过选择、交叉、变异操作能迅速排除与最优解相差极大的串,这是一个强烈的滤波过程,也是一个并行滤波机制,有极强的容错能力。
(5)GA中的选择、交叉和变异都是随机操作,选择体现了向最优解的迫近,交叉体现了最优解的产生,变异则体现了全局最优解的覆盖。
(6)GA具有隐含的并行性,实现简单,效果良好。
2.2 遗传算法存在的问题
(1)GA在全局最优的搜索上效果良好,而在局部最优的搜索上存在不足。在算法进行的前期,搜索效果良好,而在算法进行的后期,搜索速度缓慢。即使在逼近全局最优时,要获得全局最优解仍要花费很大的搜索代价。
(2)GA虽然实现简单,但实现的效果很大程度上取决问题的表示,种群的规模,最大遗传代数,遗传算子的选择,交叉变异概率等参数,如果设置不好,类似以随机搜索算法。而这些参数又无规律可循,要通过大量的实验来获取,参数的选取不具有通用性,当问题本身发生改变时,要重新指定参数,将要花费很大代价。
(3)GA的“早熟”问题,是指在算法早期,种群中出现了超级个体,该个体的适应值大大超过了当前种群的平均个体适应值Σfi/N,使算法较早收敛于局部最优点,而非全局最优。特别是到了算法进行的后期,超级个体在种群中占据了绝大多数,这时,传统的交叉操作对于相同的超级个体已经不起作用,而变异操作虽然能够为算法补充新的个体,但变异在遗传中毕竟是小概率事件。所以,必须在其他方面对算法进行改进,提高算法的抗干扰能力。
(4)GA对算法的精度、可信度、计算复杂性等方面,还没有有效的定量分析方法。
3 遗传算法的应用[2,3,4,5]
GA由于具有鲁棒性强,实现简单,对问题依赖性小等优点,为求解复杂系统优化问题提供了通用框架,下面是一些主要应用领域:
(1)函数优化:是GA的经典应用领域,也是对GA进行性能评价的常用算例,对于一些非线性、多模型、多目标的函数优化问题,用其他优化方法较难求解,GA却可以得到较好的结果。
(2)组合优化:随问题规模的扩大,搜索空间急剧扩大,对这类复杂问题,实践证明,GA对于组合优化的NP完全问题非常有效。
(3)生产调度问题:GA已成为解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产车间调度、生产规模、人物分配等方面都得到了有效的应用。
(4)自动控制:GA在自动控制领域中的应用日益增加,并显示了良好的效果。如在参数辨识、人工神经网络的结构优化设计和权值学习,都显示了GA的应用优势。
(5)机器人智能控制:GA是源自于对人工自适应系统的研究,已经在移动机器人路径规划、关节机器人运动轨迹规律、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用。
(6)图像处理和模式识别:在图像处理过程中,如扫描、特征提取、图像分割等不可避免的会产生一些误差。目前,GA已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用。
(7)人工生命:基于GA的进化模型是研究人工生命现象的重要理论基础,已在其进化模型、学习模型、行为模型等方面得到应用。
(8)遗传程序设计:Koza发展了遗传程序设计,基本思想是:采用树型结构表示计算机程序,运用遗传算法的思想,通过自动生成计算机序来解决问题。虽然该理论尚未成熟,应用也有些限制,但已成功地应用于人工智能、机器学习等领域。
(9)机器学习:基于GA的机器学习、特别分类器系统,在调整人工神经网络的连接权、神经网络结构的优化设计、和多机器人路径规划系统中得到了成功的应用。
4 遗传算法的研究分析
4.1 算法自身的改进
GA有着自身所特有的巨大优势,但在数学基础、算法结构、实现机理以及算法组成等方面都还存在着不足,为了改善算法的求解性能,扩大算法的应用范围,必须致力于算法自身的改进的研究工作。
4.2 参数的动态自适应
GA中的参数包括种群规模、遗传代数、交叉概率和变异概率等,参数设置的好坏直接影响到算法性能的优劣。如何对这些参数进行配置,一直是研究的重点。参考文献[6]中不仅从理论上证明了自然数编码的前提下存在种群的最优种群规模,而且给出了如何计算最优种群规模的方法。Srinivaszai提出了对交叉概率和变异概率进行算法动态自适应的思想。Fogarty从整数编码的角度研究了变异概率对算法性能的影响。
4.3 小生境技术的遗传算法
小生境技术是指将每代种群中的个体按照适应度的大小划分为多个类,在每个类中选取适应度较大的个体组成一个新的种群,通过这些种群之间的共享机制来完成种群间优秀个体的交流共享,从而达到寻找最优解的搜索过程。不仅能够保持种群的多样性,而且对于算法的全局寻优能力和算法的收敛性都能起到良好的改善作用。
4.4 混合遗传算法
GA在全局最优解的搜索上有其独特的高效性,但局部搜索能力不足。而一些常用的算法,如贪婪算法、模拟退火算法、爬山法等,局部搜索能力很强,通过融合这些算法的优点,弥补GA自身的不足的混合式算法,成为提高算法的效率和求解质量的一个有效途径。
4.5 并行遗传算法
由于GA存在的隐式并行性的特性,可以用并行技术来提高效率。并行GA主要有主从式模型,粗力度模型和细粒度模型三种主要框架。在主从式模型中,主处理器控制整个GA的运行,其他的从处理器则进行个体的初始化,交叉、变异和选择操作,然后由主处理器进行总体调控。在粗细粒度模型中,每个处理器进行整体算法的独立操作,然后各个处理器之间进行个体交流。在细粒度模型中,一个处理器只能够与其周围的处理器之间进行个体交换。在并行算法中,处理器之间的个体交换称之为“迁移”,是并行GA中独特的操作算子。通过迁移算子,可实现最佳个体在不同子种群之间的流动,从而提高各个子种群的之间,加快子种群的收敛。
5 结束语
遗传算法经过几十年的发展,其应用从工程科学到社会科学的诸多领域,今后,拓展更加多样的应用领域将是遗传算法发展的主流。
摘要：在介绍遗传算法的基本原理与方法的基础上,分析了遗传算法相对于其它算法的优越性和存在的问题以及遗传算法的主要应用和研究发展方向。
关键词：遗传算法,智能控制,算法优化
参考文献
[1]Pan Z J,Kang L S.An Adaptive Evolutionary Algorithms for Numerical Optimization.Proc.of SEAL'96,Taejon,Korea,1996:53-60.
[2]L.Davis,Handbook of Genetic Algorithms,van Nostrand Rei-nhold,New York,1991.
[3]席裕庚,柴天佑,恽为民.遗传算法综述.1996,13(60):69-7-708.
[4]刘勇,等.非数值并行算法(二)—遗传算法.北京:科学出版社,1995.
[5]陈国良,等.遗传算法及应用.haviour of A Class of Genetic Adaptive Systems.PhD thesis,University of Michigan,1975.
遗传算法的基本原理及其应用研究 篇10
遗传算法类似于自然进化,通过作用于染色体上基因寻找最好的染色体来求解问题。与自然界相似,遗传算法对求解问题的本身一无所知,它所需要的仅是对遗传算法所产生的染色体有更多的繁殖机会。在遗传算法中,通过随机方式产生若干个所求解问题的数字编码,即染色体,形成初始种群;通过适应度函数给每个个体一个数值评价,淘汰低适应度的个体,选择高适应度的个体参加遗传操作,经过遗传操作后的个体集合形成下一代新的种群,对这个新种群进行下一轮进化。
2 遗传算法的主要步骤
(1)初始化。选择一个群体,即选择一个串或个体的集合bi,i=1,2……n。这个初始的群体也就是问题假设解的集合。一般取n=30~160。通常以随机方法产生串或个体的集合bi,i=1,2……n。问题的最优解将通过这些初始假设解进化而求出。
(2)选择。根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存、不适者淘汰的自然法则。
给出目标函数f,则f(bi)称为个体bi的适应度。以P{选中为选中bi的下一代个体的次数。
显然,从上式可知:(1)适应度较高的个体,繁殖下一代的数目较多;(2)适应较小的个体,繁殖下一代的数目较少,甚至被淘汰。这样,就产生了对环境适应能力较强的后代。对于问题求解角度来讲,就是选择出和最优解较接近的中间解。
(3)交叉。对于选中用于繁殖下一代的个体,随机地选择两个个体的相同位置,按交叉概率P,在选中的位置实行交换。这个过程反映了随机信息交换;目的在于产生新的基因组合,也即产生新的个体。交叉时,可实行单点交叉或多点交叉。
例如有个体
S1=100101
S2=010111
选择左边3位进行交叉操作,则有
S1=010101
S2=100111
一般而言,取值为0.25~0.75。
(4)变异。根据生物遗传中基因变异的原理,以变异概率Pm对某些个体的某些位执行变异。在变异时,对执行变异的串的对应位求反,即把1变为0,把0变为1。变异概率Pm与生物变异极小的情况一致,所以Pm的取值较小,一般取0.01~0.2。
例如有个体S=101011,对其的第1、4位置的基因进行变异,则有S'=001111。
单靠变异不能在求解中得到好处。但是,它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时,交叉是不能产生新的个体的,这时只能靠变异产生新的个体。也就是说,变异增加了全局优化的特质。
(5)全局最优收敛(Convergence to the global optimum)。当最优个体的适应度达到给定的阈值,或者最优个体的适应度和群体适应度不再上升时,则算法的迭代过程收敛、算法结束。否则,用经过选择、交叉、变异所得到的新一代群体取代上一代群体,并返回到第(2)步即选择操作处继续循环执行。
3 遗传算法的应用
3.1 遗传算法的应用关键
遗传算法在应用中最关键的问题有如下3个。
(1)串的编码方式。本质是问题编码。一般把问题的各种参数用二进制编码,构成子串;然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
(2)适应函数的确定。适应函数(fitness function)也称对象函数(object function),这是问题求解品质的测量函数;往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数;但有时需要另行构造。
(3)遗传算法自身参数设定。遗传算法自身参数有3个,即群体大小n、交叉概率Pc和变异概率Pm。
群体大小n太小时难以求出最优解,太大则增长收敛时间。一般n=30-160。交叉概率Pc太小时难以向前搜索,太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构,太大使遗传算法成了单纯的随机搜索。一般取Pm=0.01-0.2。
3.2 遗传算法的主要应用领域
遗传算法的主要应用领域在于函数优化(非线性、多模型、多目标等),机器人学(移动机器人路径规划、关节机器人运动轨迹规划、细胞机器人的结构优化等),控制(瓦斯管道控制、防避导弹控制、机器人控制等),规划(生产规划、并行机任务分配等),设计(VLSI布局、通信网络设计、喷气发动机设计等),组合优化(TSP问题、背包问题、图分划问题等),图像处理(模式识别、特征提取、图像恢复等),信号处理(滤波器设计等),人工生命(生命的遗传进化等)。
4 遗传算法的研究新动向
4.1 基于遗传算法的机器学习
这一新的研究方向把遗传算法从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。遗传算法作为一种搜索算法从一开始就与机器学习有着密切联系。分类器系统CS-1是GA的创立者Holland教授等实现的第一个基于遗传算法的机器学习系统。分类器系统在很多领域都得到了应用。例如,分类器系统在学习式多机器人路径规划系统中得到了成功应用;Goldberg研究了用分类器系统来学习控制一个煤气管道仿真系统;Wilson研究了一种用于协调可移动式视频摄像机的感知运动的分类器系统等。分类器系统在基于遗传算法的机器学习研究中影响很大,但具体实现方法和要解决的具体问题有关。基于遗传算法的概念学习是近几年来机器学习领域的一个较为引人注目的研究方向。由于概念学习隐含的搜索机制,使得遗传算法在概念学习中有用武之地。目前也有一些嵌入领域知识的基于遗传算法的机器学习的研究,如将概念学习中特有的操作遗传化,并显示出一定的优点。此外,学习分类系统的并行实现在基于遗传算法的机器学习研究中也占有相当的分量。
4.2 遗传算法与其他计算智能方法的相互渗透和结合
遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合,以达到取长补短的作用。近年来在这方面已经取得了不少研究成果,并形成了“计算智能”的研究领域,这对开拓21世纪中新的智能计算技术具有重要意义。GA的出现使神经网络的训练(包括连接权系数的优化、网络空间结构的优化和网络的学习规划优化)有了一个崭新的面貌,目标函数既不要求连续,也不要求可微,仅要求该问题可计算,而且搜索始终遍及整个解空间,因此容易得到全局最优解。GA与神经网络的结合正成功地被用于从时间序列的分析来进行财政预算,在这些系统中,训练信号是模糊的,数据是有噪声的,一般很难正确给出每个执行的定量评价,如采用GA来学习,就能克服这个困难,并显著提高系统的性能。Muhlenbein分析了多层感知机网络的局限性,并猜想下一代神经网络将会是遗传神经网络。遗传算法还可以用于学习模糊控制规划和隶属度函数,从而更好地改善模糊系统的性能。将模糊逻辑、神经网络和遗传算法三者有机地结合起来应用于温室夏季温湿度控制中,实验结果表明得到了良好的控制效果。混沌表现出的随机性是系统内在的随机性,被称为伪随机性,在生物进化中起着重要作用,是系统进化与信息之源。混沌与遗传算法的结合已有人进行过尝试,如吴新余等采用多种混沌模型构造随机开关,以此控制交叉操作以改进GA的性能,采用混沌序列构造变异算子,为遗传算法的实现开辟了新的途径。
4.3 并行处理的遗传算法
并行处理的遗传算法的研究不仅是遗传算法本身的发展,而且对于新一代智能计算机体系结构的研究都是十分重要的。GA在操作上具有高度的并行性,许多研究人员都在探索在并行机上高效执行GA的策略。研究表明,只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程,即使不使用并行计算机,我们也能提高算法的执行效率。在并GA的研究方面,一些并GA模型已经被人们在具体的并行机上执行了;并行GA可分为两类:一类是粗粒度并行GA,主要开发群体间的并行性,如Cohoon分析了在并计算机上解图划分问题的多群体GA的性能;另一类是细粒GA,主要开发一个群体中的并行性,如Kosak将群体中的每个个体映射到一个连接机的处理单元上,并指出了这种方法对网络衅设计问题的有效性。
4.4 遗传算法与人工生命的渗透
人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统,人工生命与遗传算法有着密切的关系,基于遗传算法的进化模型是研究人工生命现象的重要理论基础。虽然人工生命的研究尚处于启蒙阶段,但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力,并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成,遗传算法为人工生命的研究提供了一个有效的工具,人工生命的研究也必将促进遗传算法的进一步发展。
4.5 遗传算法与进化规则及进化策略的结合
遗传算法、进化规则及进化策略是演化计算的3个主要分支,这3种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象,所以三者之间有较大的相似性;另一方面,这3种算法又是从不完全相同的角度出发来模拟生物进化过程,分别是依据不同的生物进化背景、不同的生物进化机制而开发出来的,所以三者之间也有一些差异。随着各种进化计算方法之间相互交流深入,以及对各种进化算法机理研究的进展,要严格地区分它们既不可能、也没有必要。在进化计算领域内更重要的工作是生物进化机制,构造性能更加优良、适应面更加广泛的进化算法。
5 结束语
遗传算法经过几十年的发展,逐渐被人们接受和运用。其应用涉及从工程科学到社会科学的诸多领域。在工程领域特别是人工智能和控制领域中的超大规模、非线性系统优化问题中,遗传算法成为有效求解的得力工具,而这些问题正是传统方法难以解决的。由于遗传算法本身就是一个模拟自然演化的具有自组织、自适应和自学习特征的算法,因此它以独立的或与其它方式相结合的形式被用于机器智能系统设计中。
与此同时,遗传算法作为一种非确定性的拟自然算法,为复杂系统的优化提供了一种新方法,并且经过实践证明效果显著。尽管遗传算法在很多领域具有广泛的应用价值,但仍存在一些问题,例如局部搜索能力差,存在未成熟收敛和随机漫游等现象,从而导致算法的收敛性能差,需要很长时间才能找到最优解,这些不足阻碍了遗传算法的推广应用。如何改善遗传算法的搜索能力和提高算法的收敛速度,使其更好地应用于实际问题的解决中,各国学者一直在探索着。
参考文献
[1]BUCHANAN BG,GLICK J.AI topics,A responsibility to celebrate AI responsibly.AI Magazine,Spring2002.
[2]R J MITCHELL,B CHAMBERS,A P ANDERSON.Array pattern synthesis in the complex plane optimized by a genetic algorithm.Electronics letters,1993(20).
[4]SAVIC D A,EVANS K E,SILBERHORN THORSTEN.A genetic algorithm based system for the optimal design of laminate.Computer Aided Civil and Infrastructure Engineering,1999(14).
[5]PATRICK SIZRRY,FRANCOIS GUELY.A Genetic Algorithm for Optimizing Takagi-Sugeror Fuzzy Rule Bases.Fuzzy Sets and Sys-tem,1998(99).
[6]张文修,梁怡.遗传算法的教学基础[M].西安:西安交通大学出版社,2000.
[7]蒋腾旭.智能优化算法概述[J].电脑知识与技术,2007(8).
[8]任庆生,叶中行.遗传算法中常用算子的分析[J].电子学报,2005(5).
[9]余建坤,张文彬,陆玉昌.遗传算法及其应用[J].云南民族学院学报,2002(4).
遗传研究与应用 篇11
关键词：遗传学；研究性教学；示范课程
由于现代生物学的飞速发展，遗传学尤其是分子遗传学部分的内容更新很快，单纯依靠教科书乃至书本参考书，都会跟不上知识更新的速度；另外，遗传学的研究领域宽广，与众多学科交叉融合，形成了许多分支学科。因此，继续采用老师讲学生被动学的模式进行遗传学的教学已不能满足遗传学飞速发展的需要，在遗传学的教学中开展研究性教学势在必行。
研究性课程以其独特的创新品格和实践魅力，深受课程研制者和实践者所关注，成为二期课改的亮点，但同时它又是当前课改的难点。为搞好我校遗传学课程的研究性教学，我们进行了如下的探索：
一、对课程体系和教学内容进行整合和优化
遗传学是我校生命科学学院的主干课程，包括《遗传学》和《遗传学实验》两门独立课程，《遗传学》的教学课时数是54学时（3个学分），《遗传学实验》的课时是36学时（1个学分）。但是遗传学的教学内容几乎涉及到了遗传学科的方方面面，这就造成了知识容量大而课时少的矛盾；其次，随着学校教育体制的
改革和办学方向的战略性调整，生命科学院由原来单纯的师范专业发展到现在的
生物教育专业、生物技术专业、生物工程专业和海洋专业，同时还有国家理科基
地；另外，遗传学的授课对象除了生命科学院的各专业学生外，还有中北学院和强化部的学生。由于各专业的培养目标有所侧重，学生的知识结构和专业基础差异较大。因此，遗传学的教学工作面临着许多困难与挑战。
根据遗传学的学科特色和遗传学教学的实际需要，我们对国内外目前比较普遍使用的遗传学教材的内容体系进行了系统的比较和研究，对本校生物专业已修完遗传学课程的本科生和研究生进行了访谈，对中学的新课改，以及中学的生物学教学要求进行了调研，听取他们对高校遗传学教材体系构建和遗传学教学过程的建议和要求。在此基础上，我们编写了《遗传学》和《遗传学实验》两部教材，由科学出版社于2013年6月出版发行，这两部教材都被遴选为南京师范大学重点教材。
新编教材在保持现有教材风格和优点的基础上，通过全体编著人员的共同努力，形成了如下特色：
（一）凸显遗传学的学科特色，凡是在其他相关教材中应该阐述清楚的内容均不列入本教材，例如，细胞的结构、细胞分裂、DNA的结构、DNA的复制、转录和翻译的过程等。
（二）以基因为主线，按照基因概念的形成和发展的顺序，系统介绍基因的结构、功能、定位、重组、突变、基因工程和调控等核心内容。
（三）连锁与交换是整个遗传学的灵魂。本教材以最大的篇幅对连锁与交换的概念、连锁与交换规律、连锁与交换的证据、连锁与交换的意义、连锁遗传分析、连锁遗传图的绘制、真核生物的连锁与交换、细菌和噬菌体的连锁与交换、真菌的连锁与交换等内容进行了比较全面和系统的阐述。
（四）基因定位是研究基因功能和进行遗传操作的关键，本教材将其独立成章，对各种遗传标记和基因定位的常规技术和方法进行归纳和介绍，不仅使学生明确相关概念，同时了解各种基因定位方法。
（五）孟德尔定律是遗传学科的基石，但是由于当时理论和技术的局限，孟德尔的假说也存在许多缺陷，为了帮助学生系统学习孟德尔的遗传规律，同时将细胞遗传学与现代遗传学密切地联系在一起，在介绍孟德尔遗传规律之后，进一步对孟德尔的遗传规律进行了补充和发展。
（六）细胞遗传和分子遗传是遗传学科的两条主线，本教材对这两部分内容都进行了扩充。在细胞遗传学部分加入了“核型与核型分析”的内容，在分子遗传学部分加入了“基因组与基因组学”、“蛋白质组与蛋白质组学”和“生物信息学”等内容。
（七）我们学习和掌握遗传学知识的目的，除了开发和利用基因资源为人类服务之外，还应该加强遗传保护，减缓重要遗传资源衰退或灭绝的速度，保持遗传多样性。因此，在本教材中引入“保护遗传学”这一章，增强学生保护遗传资源的意识。
（八）《遗传学实验》教材的内容选择和实验安排紧扣《遗传学》教材的知识体系，实验内容涵盖细胞遗传、分子遗传、群体遗传、数量遗传、人类遗传、动物遗传、植物遗传、微生物遗传等不同领域，各个实验的取材方便，操作简洁，涉及的内容与日常生活息息相关。
二、将创造性和自主性学习的要求贯穿于整个教学过程中
在研究性教学中，教师不仅要传授知识，而且要遵循认知规律，以学生为中心，设计教学过程、提供教学资源、提供学习建议，对整个学习过程进行控制，关键环节上对学生进行启发、激励、引导和指导，并及时对学习效果进行评价，使学生从理解和接受式的被动学习转变为探索和研究式的自主学习。
为了激发学生学习热情和对遗传学科的学习兴趣，在每章开始之前都向学生提出一些前瞻性问题，让学生借助网络和学校数据资源进行预习，在课堂教学中对一些热点问题进行随堂讨论，在每章结束之后布置一些重点问题让学生进行探究，使学生的学习不再是死记硬背，而是主动地去进行探索。
三、精选实验内容，激发学生的学习兴趣和研究热情
遗传实验课程历史悠久，随着科技的进步和科学的发展，实验内容在不断地扩充、更新与深化，但是，在遗传史上的一些经典实验仍然需要保留，因为这些实验的原理和设计精髓对现代生物学研究仍然有着不可替代的科学意义。然而，遗传学实验课的学时数又很少，如何解决这个矛盾？在遗传学实验课程的教学中，我们主要进行了如下的探索：
（一）精选经典实验，培养创新能力
像果蝇的杂交这样的传统实验，它的实验原理和设计精髓对现代生物学研究仍然有着不可替代的科学意义，因此仍然需要保留，但是我们绝对不能像以前那样，让学生一步步地按照实验教材的步骤去操作、去验证，学生能够发挥创造性的机会很小，而且有些学生可能在中学就做过了这样的实验。为了克服传统实验的不足，培养学生的探究意识和创新能力，我们只给学生提供果蝇品系和研究目标，让学生自己去设计实验方案，在规定的时间内自己确定研究进程，最终将整个研究过程形成一个综合报告。经过几届学生的实践，我们发现效果非常好，学生可以选择不同的杂交方式、选择不同的基因去进行分析，既验证了相关的遗传理论，又发挥了自己的创造性。
（二） 注重综合性实验，强化操作能力
综合性实验教学是指实验内容涉及本课程的综合知识或与本课程相关的其它课程多个知识点的实验， 要求学生综合已学的知识来设计和操作实验。主要目标是培养学生的综合分析能力、实验动手能力、数据处理能力、查阅资料能力以及运用多学科知识解决问题的能力， 学会应用不同的方法和技术来完成预定的实验内容。在研究性遗传学实验示范课程的教学中，我们设计了多个综合性实验，例如， “人类基因组DNA 的检测与分析”实验，推荐学生用自己的指甲、口腔粘膜和毛囊作为材料，提取自己的基因组DNA，进行琼脂糖凝胶电泳，应用图像分析软件对照片上的图形进行测量，构建DNA 片段大小回归方程，并且根据回归方程计算出各未知DNA 的相对含量，比较和评价各种材料的实验结果。因为是对自己的DNA 进行分析，所以学生对实验的热情都很高。
四、培养学生科技文献获取和利用能力
遗传学的内容更新很快，单纯靠教科书和参考书，跟不上知识更新的速度，因此阅读科技文献成为获取最新学术进展的最佳方法。另外，每个学生将来走向工作岗位后，都可能从事一定的科研或教学活动，利用科技文献的机会是在所难免的。所以获取和利用科技文献的能力应在大学阶段得以充分培养。我们主要采取了如下措施：
（一）向学生介绍国内外的一些与遗传学相关的重要杂志名录、科技文献的检索方法、网络数据库及其使用方法等；
（二）要求学生完成1篇课程论文。教师只提出论文的写作和格式要求，但不拟定具体的题目，由学生根据自己的兴趣或最关注的问题自定选题，然后查阅文献，在课程结束之前，每个学生都必修提交1篇与遗传学相关的综述文章，并按照一定比例计入最终成绩。
（三）鼓励学生参与遗传学任课教师的课题，在老师指导下，积极申报江苏省和南京师范大学的大学生实践创新项目。在科研训练方面，已经取得了理想的成果，每位遗传学任课教师每年都指导由学生自动组成的课题组，成功申请了江苏省和南京师范大学的大学生实践创新项目，而且取得了很好的研究成果，已有多个课题组在国内权威期刊上发表了相关的研究论文。
总之，通过遗传学各任课教师的共同努力，我校的遗传学研究性示范教学工作取得了明显的成效，初步达到了创造性教与学的目的，教学质量有了进一步的提高，为进一步做好我校的遗传学教学工作、不断提高我校的遗传学教学质量奠定了良好基础。我校的遗传学研究性示范教学实践表明，高校的课程教学只有通过改革，紧跟社会和科学发展步伐，才能充满生机活力，获得教学双赢。
基金项目：遗传学研究性教学示范课程项目（南京师范大学）
遗传算法在图像处理的应用研究 篇12
遗传算法是基于达尔文进化论, 在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存, 优胜劣汰等自然进化规则来进行搜索计算和问题求解。遗传算法已从不同学科还有领域得到了普遍的采纳, 从图像调整过程内进行采纳同样产生了非常明显的效果。
2. 遗传算法的基本概述
2.1 概念
遗传算法 (Genetic Algorithm) 简称GA, 是基于达尔文 (Darwin) 的生物进化论和孟德尔 (Mendel) 的遗传学说的推动而产生的非常科学合理的优化算法。
遗传算法定义开始为Bagley J.D于1967年率先表明的, 但是和遗传算法联系紧密的理论还有手段进行认真分析则始于Michigan大学的J.H.Holland博士, 于1975年发表《自然与人工系统中的适应性行为》, 在此著作内详细的说明了遗传算法相关理论还有研究手段, 制订了遗传算法相关定理还有模式, 通过这种方式给遗传算法做好了充分的准备。
2.2 基本原理
遗传算法主要从自然选择还有生物遗传学机理前提之下营造产生的, 按生物学的方法将问题的求解表示成种群中的个体 (用计算机编程时, 一般使用二进制码串表示) , 从而构造出一群包括个可行解的种群, 将它们置于问题的环境中, 根据适者生存和优胜劣汰的原理, 对该种群按照遗传学的的遗传算子进行选择、交叉和变异操作, 不断优化生成新的种群, 这样一持续的发展, 最后能够统一到和环境能够有机保持一致的个体中, 科学合理的解决问题。
2.3 基本操作
遗传操作是关于染色体的运算, 也叫遗传算子 (genetic operator) 。选择、交叉还有变异为非常关键的实施步骤, 共同营造产生了相应的遗传操作。
(1) 选择 (Selection)
选择 (Selection) 运算亦称为繁殖、再生或复制运算, 用于模拟生物界优胜劣汰的自然选择现象。此为从群体内找到能够和环境保持一致的个体, 随之借助此类个体进行培养, 所以部分情况下将其叫做再生 (Reproduction) 。但有时也称为非均匀再生 (differential reproduction) 是因为从找到进行培养的个体过程中, 能够按照个体自身实际适应水平科学合理的判断繁殖量。选择为非常重要的步骤, 能够有效的展示适者生存综合观念。
(2) 交叉 (Crossover)
选择操作能把优秀者从旧种群中选择出来, 但不能创造新的个体。交叉操作则模拟了生物进化过程中的繁殖现象, 从所有进行分析的个体之内, 能够在基因码链一个地点基因开展相应的处理, 从而产生新的个体。
(3) 变异 (Mutation)
变异模拟了生物进化中基因偶然突变现象。这是在选中的个体中, 对个体中的某些基因进行反操作。在以二进制编码的系统中, 染色体的某个基因被随机地由1变为0, 或由0变为1。
遗传算法具体实施步骤能够参考下述:
个体的适应度达到给定的阀值;或者个体的适应度的变化率为零, 根据这一准则来决定是否结束操作。
2.4 应用领域
由于遗传算法水平持续提高, 和遗传算法联系紧密的活动不断出现, 遗传算法慢慢变作了不同学科、不同领域有机结合的关键分析目标。遗传算法能够从不同角度得到了合理的采纳。当前阶段, 研究者表示从人工智能分析过程内, 遗传算法跟人工智能一样, 已成为影响今后十年的关键计算技术。
3. 遗传算法在图像处理中的应用
图像处理就是对图像信息进行了加工处理, 以满足人的视觉心理和实际应用的要求的过程, 是计算机视觉内非常关键的分析目标。从在图像开展扫描、特征搜集、图像分割等调整环节内肯定将产生部分问题, 造成了计算机视觉实用化水平无法快速提高。要使这些误差达到最小, 则需要对这些图像进行处理, 当中涉及大量的优化计算。把遗传算法应用到图像处理, 最重要的一点是利用遗传算法的全局搜索算法, 快速取得函数最优解, 从而得到较好的处理效果。目前已在图像处理中的各种手段能够得到普遍的采纳。
3.1 遗传算法在图像变换中的应用
图像变换是图像增强、图像恢复、图像编码压缩、图像分析描述等的基础, 包括几何变换和可分离正交变换, 常进行的是线性正交变换运算。常采用的图像变换方法有沃尔什-哈达玛;哈尔变换;离散余弦变换;傅立叶变换;小波变换等。
遗传算法应用于图像变换主要解决问题是构造适应度函数。也就是在改变像素的空间位置或估算新空间位置上的像素值中, 遗传算法能够进行并行统计, 能够有效的减少调整运算所需要的实践, 能够合理解决问题, 保证工作质量和水平。从具体实施过程内各种管理参数规模庞大, 往往要借助经验, 所以, 怎样科学合理的管理此类参数, 有效保障变换质量和水平, 应当不断进行分析还有研究。
3.2 遗传算法在图像去噪中的应用
在存在噪声的图像内开展调整为图像处理的起步时期, 同时为图像处理非常关键的环节。降低噪声的手段主要包括了维纳滤波、中值滤波、混合滤波、小波去噪等等, 另外小波去噪质量非常高。
遗传算法能够从具体实施过程内得到合理采纳, 绝大多数为另外滤波器发现合理的参数。在输入图像中, 第一应当系统研究图像自身灰度级范围值还有具体布局现状, 按照输出图像还有输入图像实际灰度对应关系开展相应的调整, 随之能够按照图像质量评价标准营造产生科学合理的适应度函数, 随之能够借助遗传算法持续开展实践活动, 能够发现非常科学合理的灰度变换关系, 随后能够在图像中开展相应的调整, 遗传算法通常无法从图像滤波内得到合理采纳, 主要与另外算法有机统一得到采纳。文献[7]即为借助GA优化数学形态滤波器内top-hat交换和bottom-hat变换的系数, 文献[9-10]主要借助了GA优化模糊隶属度函数。
3.3 基于遗传算法的图像增强
图像增强涉及的操作包括图像降噪、图像特征提取、目标轮廓抽取、黑白图像假彩色生成技术等。遗传算法作为一种智能优化算法在图像控制角度产生的影响关键为发现管理参数的正确答案, 随之实现图像的自适应增强。
在对一幅图像增强过程中, 重新构造新的变换函数, 采用实数编码, 以一个一维五元数组表示一条染色体, 每个参数对应一个基因位, 这样函数的参数范围非常大, 在这样大空间进行搜索, 遗传算法将发挥其优势。遗传算法中个体进化的动力就是所要构建的适应度函数。适应度函数设计就是要兼顾图像的整体与局部, 大的结构和小的细节平衡体现[13]。适应度函数如下:
根据函数执行遗传算法的交叉和变异算子, 实验证明该方法具有较强的自适应性和鲁棒性, 而且得到更好的增强效果。
3.4 基于遗传算法的图像恢复
图像恢复实际就是图像的优化, 利用合适的算法可以使得图像复原到最佳的效果。遗传算法中用适应度来衡量种群中各个染色体在算法运算中可能达到或者接近于最优解的程度, 较大可能遗传到下一代的只能是适应度高的染色体。对于图像复原问题, 适应度函数的确定涉及需复原图像的退化模型, 准确的模型可以最大程度地恢复原始图像。
遗传算法往往能够从灰度图像调整过程内得到合理采纳, 通常把染色体编码变作将不同灰度值当作基础的2维矩阵, 也就是一幅图像当成一个染色体、一个像素当成一个基因, 有效借助自然数编码。所有适应度函数均是F (fi) =||g-h*fi||2
另外, f为个体i所象征的推测恢复图像, g是当前掌握的退化图像, h是退化过程, 函数值往往和个体呈现正比例关系;从交叉具体实践过程中通常借助窗口交叉, 也就是从父代染色体矩阵内找到比较类似的窗口, 开展沟通交流。变异操作能够把彼此相邻的平均值调整还有要进行变异的基因值。整个遗传算法涉及的参数较多, 每一种参数的不同组合, 其对应的遗传算法性能也各异, 最终得到的恢复图像也不尽相同。
3.5 遗传算法在图像分割中的应用
从调整繁琐图像的过程中, 研究者通常要借助多参数开展相应的调整, 从多参数调整环节之内, 优化计算为特别关键的。应用遗传算法除了能够发现最优解, 同时能够有效保证计算效率。在图像分割时用来帮助确定分割阈值, 这是我们将遗传算法引入图像分割的主要目的。文献[11]能够把遗传算法还有神经网络算法有机统一对图像进行调整, 也就是在神经元网络内借鉴遗传算法开展相应的调整, 同时能够有效借助遗传参数, 能够表明不同的级别开展相应的调整。文献[12]能够把遗传算法从图像分割手段内得到合理的采纳, 能够有效的保证图像分割效率还有保证图像处理的时效性。把遗传算法从不同分割手段中进行采纳能够有效的保证工作效率, 找到合理分割阀值为现阶段非常关键的分析热点。
3.6 遗传算法在图像融合中的应用
图像融合技术主要应用于军事、遥感、医学图像处理、自动目标识别以及计算机视觉等领域。众多的融合方法中, 最经典的方法有基于色彩空间变换的IHS变换、Lab变换、YUV变换;基于统计方法的主成份分析、Brovey变换以及基于多尺度分析融合方法的金字塔分解和小波变换[14]。
基于遗传算法的图像融合, 主要是结合图像融合技术, 为其构造的函数提供最佳匹配的快速搜索, 从而加快图像进行寻优速度。基于遗传算法的图像融合过程, 可以简单地作如下概述:首先利用融合方法来获取作为初始粒子的图像, 然后根据后续图像处理的需要来构造目标函数, 再利用遗传算法来优化目标, 从而获取合适的图像。
3.7 基于遗传算法的图像识别
图像识别是通过对采集到的图像进行分析研究, 从而提取目标的特征。作为模式识别范畴的图像识别, 最重要的处理是图像匹配。在图像识别技术之内有效借鉴遗传算法关键为处理部分识别效率难点, 也就是能够借助降低搜索位置规模有效的降低计算总量;另外从精度性识别角度同样产生了非常明显的效果, 同时遗传算法能够避免出现明显波动。
进行图像识别过程中, 将原始图像矩阵变换成列向量来重新构造图像的协方差矩阵, 从而造成图像的维数较高, 加大了整个特征抽取过程所耗费的计算量。引入遗传算法, 先采用图像识别方法进行特征提取, 再用遗传算法对提取的特征进行优化, 从而大大降低了特征空间的维数, 而且具有很好的分类效果, 提高了图像的识别率。
4. 结语
遗传算法主要为和生物进化非常相像的优化搜索算法, 能够借助选择、交叉还有变异操作算子, 借助种群迭代, 找到最优解。另外鲁棒性还有避免函数限制等突出性质造成了能够从不同领域得到合理的采纳。能够把遗传算法从图像处理过程内得到合理的采纳, 首先能够给图像处理指明方向, 其次能够推动遗传算法覆盖面不断延伸。
摘要：介绍了遗传算法的基本概念和基本原理, 分析说明了遗传算法的基本操作以及应用领域;重点概述了遗传算法在图像变换、图像增强、图像恢复、图像分割、图像识别等方面的图像处理中的应用。
【遗传研究与应用】推荐阅读：
遗传算法研究概述07-19
遗传算法的收敛性研究09-18
高度近视的遗传学研究07-21
农学专升本《遗传学》课程教学改革研究论文07-10
植物三种不同遗传方式基因的地理家系谱理论与应用初探08-02
遗传算法原理和应用05-15
遗传与环境的关系06-26
动物遗传原理与育种方法06-26
“性别决定与伴性遗传”说课稿09-24
遗传学实验教学改革的实践与探索08-29