遗传算法的交叉算子分析

《遗传算法的交叉算子分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《农业网络信息》2009年第5期交流园地遗传算法的交叉算子分析邓春燕（河池学院计算机与信息科学系，广西宜州546300）摘要：交叉算子是遗传算法中的一种重要算子。文章介绍了编码方法基础上的各种交叉算子，以及如何应用到复杂问题，如组合优化、调度问题。关键词：遗传算法；遗传算子；交叉算子中图分类号：TP399文献标识码：B文章编码：1672－6251（2009）05－0124－03AnalysisofcrossoveroperatorofgeneticalgorithmDENGChun-yan(DepartmentofComputerandInf

2、ormationScience,HechiUniversity,Yizhou546300,China)Abstract:CrossoveroperatorisanimportantoperatorofGeneticalgorithm.Acodingmethodbasedonavarietyofcrossoveroperatorwasintroducedinthispaper.Itprovidedthemethodstosolvethecomplexproblems,suchascombinatorialoptimization,schedul

3、ingissues.Keywords:Geneticalgorithm;Geneticoperator;Crossoveroperator1引言映个体好坏的情况）；④WHILE<未满足迭代终止条遗传算法(GA）是由美国Michigan大学的John件〉DO；⑤用轮盘赌选择法选择出若干个个体进行Holland教授于20世纪60年代末期创建的。它是模繁殖，个体可以重复；⑥随机配对，按一定概率（交仿自然界生物进化机制发展起来的随机全局搜索和优叉概率）进行单点交叉操作，并生成两个子个体；⑦化方法，借鉴了达尔文进化论和孟德尔、摩尔根遗传按一定概率（变异

4、概率）变异二进制个体串中某个学理论。其本质是一种高效、并行、全局搜索的方（些）位；⑧适应度评估测试个体适应度；⑨END法，能在搜索过程中自动获得和积累有关空间搜索的DO。[1]，[5～7]知识，并自适应地控制搜索过程以获得最优解。3遗传算法中的交叉算子2基本遗传算法在生物的自然进化过程中，两个同源染色体通过JohnHolland教授通过模拟生物进化过程设计了交配而重组，形成新的染色体，从而产生出新的个体最初的遗传算法，我们称为基本遗传算法(标准遗传或物种。交配重组是生物遗传和进化过程中的一个主算法或简单遗传算法）。要环节。模仿这个环节遗传算法

5、中使用交叉算子来产[2]一般地遗传算法由以下成分组成:①问题解的生新的个体。遗传表示；②创建解的初始种群的方法；③根据个体3.1遗传算法中的交叉适应值对其进行优劣判定的评价函数；④用来改变复交叉又称重组，是按较大的概率从群体中选择两制过程中产生的子个体遗传组成的遗传算子（交叉和个个体，交换两个个体的某个或某些位。交叉体现了变异）；⑤遗传算法参数。信息交换的思想。①交叉操作是遗传算法中最主要的[2]基本遗传算法的流程如下:①使用二进制编码对遗传操作。其作用是组合出新的个体，在串空间进行搜索空间进行编码；②随机产生包含n个个体的初始有效搜索，同时

6、降低对有效模式的破坏概率；②交叉种群；③适应度评价测试个体适应度（个体适应度反运算是遗传算法区别于其他进化算法的重要特征，它收稿日期：2009－03－13基金项目：广西研究生科研创新项目（2008105930701M51）作者简介：邓春燕(1971-),女，硕士研究生，讲师，研究方向：粗糙集理论与方法、数据挖掘。—124—《农业网络信息》2009年第5期交流园地在遗传算法中起关键的作用，是产生新个体的主要方产生两个交叉点，然后按随机产生的0、1、2三个[4]法；③交叉算子的设计包括如何确定交叉点的位置和整数进行基因交换，从而形成两个新的个体。

7、当随如何进行部分基因交换两个方面的内容。设计交叉算机数是0时，配体的前面部分交叉;当随机数是1时，子应考虑如下几点：①保证前一代中有优秀个体的性配体的中间部分交叉;当随机数是2时，配体的后面部状能够在后一代的新个体中尽可能得到遗传和继承；分交叉。②交叉算子设计和编码设计需协调操作。还有其他的交叉算子，如：缩小代理交叉、洗牌单点交叉：单点交叉又称为简单交叉，它是指在交叉等。个体编码串中只随机设置一个交叉点，然后在该点相3.2适合浮点数编码的交叉算子互交换两个配体个体的部分染色体。图1为单点交叉浮点数编码方法是指个体的每个基因值用某一范运算的示意

8、图。围内的一个浮点数来表示，个体的编码长度等于其决交叉前:A策变量的个数。除上述所述的适合二进制编码方法的B交叉算子可用于浮点数编码方法的交叉操作中，还使交叉后:A