第三章 遗传算法的理论基础

第三章 遗传算法的理论基础

遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。Holland 的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。

3.1 模式定理

不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。

定义3.1 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。

以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001) 。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。

引入模式后，我们看到一个串实际上隐含着多个模式(长度为 n 的串隐含着2n 个模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容

定义3.2 模式H 中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式 0* * * * *的阶数为1。

显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。

定义3.3 模式H 中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作)(H δ。比如，模式 011*1*的定义距为4，而模式 0* * * * *的定义距为0。 模式的阶数和定义距描述了模式的基本性质。

下面通过分析遗传算法的三种基本遗传操作对模式的作用来讨论模式定理。令)(t A 表示第t 代中串的群体，以),,2,1)((n j t A j =表示第t 代中第j 个个体串。

1．选择算子

在选择算子作用下，与某一模式所匹配的样本数的增减依赖于模式的平均适值，与群体平均适值之比，平均适值高于群体平均适值的将呈指数级增长；而平均适值低于群体平均适值的模式将呈指数级减少。其推导如下：

设在第t 代种群)(t A 中模式所能匹配的样本数为m ，记为),(t H m 。在选择中，一个位串j A 以概率/j j i P f f =∑被选中并进行复制，其中j f 是个体)(t A j 的适应度。假设一代中群体大小为n ，且个体两两互不相同，则模式H 在第1+t 代中的样本数为：

()

(,1)(,)i f H m H t m H t n f +=∑

(3.1)

式中，)(H f 是在t 时刻对应于模式的位串的平均适值。

令群体平均适值为_/i f f n =∑，则有

)1,(+t H m =_)

(),(f H f t H m (3.2)

现在，假定模式H 的平均适值高于群体平均适值，且设高出部分为,_

f c c 为常数，则有 )1,(+t H m =),()1(),(___t H m c f f

c f t H m +=+ (3.3)

假设从0=t 开始，c 保持为常值，则有

)1)(0,()1,(c H m t H m +=+ (3.4)

2．交叉算子

然而仅有选择操作，并不能产生新的个体，即不能对搜索空间中新的区域进行搜索，因此引入了交叉操作。下面讨论模式在交叉算子作用下所发生的变化，这里我们只考虑单点交叉的情况。

模式H 只有当交叉点落在定义距之外才能生存。在简单交叉(单点交叉) 下H 的生存概率)1/()(1--=t H P s δ。例如一个长度为5的串以及隐含其中的两个模式为

A = 010110

H 1 = *1* * *0

H 2 =* * *11*

我们注意到模式H1的定义距为4，那么交叉点在6-1=5个位置随机产生时，H 1遭破坏的概率5/1)1/()(2=-=m H P d δ，即生存概率为5/4。

而交叉本身也是以一定的概率c P 发生的，所以模式H 的生存概率为

)1/()(112-?-=-=m H P P P P c d c s δ (3.5)

现在我们考虑交叉发生在定义距内，模式H 不被破坏的可能性。在前面的例子中，若与A 交叉的串在位置2、6上有一位与A 相同，则H 1将被保留。考虑到这一点，式(3.5) 给出的生存概率只是一个下界，即有

)1/()(1-?-m H P P c s δ (3.6)

可见，模式在交叉算子作用下长度短的模式将增多。

3．变异算子

假定串的某一位置发生改变的概率为m P ，则该位置不变的概率为1－m P ，而模式H 在变异算子作用下若要不受破坏，则其中所有的确定位置(…0?或…1?的位) 必须保持不变。因此模式

H 保持不变的概率为)()

1(H o m P -，其中)(H o 为模式H 的阶数。当1<

算子作用下的生存概率为 m H o m s P H o P P )(1)1()(-≈-= (3.7)

综上所述，模式H 在遗传算子选择、交叉和变异的共同作用下，其子代的样本数为

]

)(1][1)(1[)

(),()1,(_m c P H o l H P f H f t H m t H m ---≥+δ (3.8)

式(3.8) 忽略了极小项m c P H o l H P ?+-?)()1/()(δ。通过式(3.8) ，我们就可以给出模式定理。

定理3.1(模式定理) 在遗传算子选择、交叉和变异的作用下，具有阶数低、长度短、平均适值高于群体平均适应度的模式在子代中将以指数级增长。

统计学的研究表明：在随机搜索中，要获得最优的可行解，则必须保证较优解的样本呈指数级增长，而模式定理保证了较优的模式(遗传算法的较优解) 的样本呈指数级增长，从而给出了遗传算法的理论基础。另外，由于遗传算法总能以一定的概率遍历到解空间的每一个部分，因此在选择算子的条件下总能得到问题的最优解。

3.2 积木块假设

由模式定理可知，具有阶数低、长度短、平均适值高于群体平均适值的模式在子代中将以指数级增长。这类模式在遗传算法中非常重要，在这一节给这些模式一个特别的名字——积木块(Building block)。

定义3.4 阶数低、长度短和适值高的模式称为积木块。

由模式定理可知，积木块将以指数级增长。正如搭积木一样，这些“好”的模式在遗传操作下相互拼搭、结合，产生适应度更高的串，从而得到更优的可行解，这正是积木块假设所揭示的内容。

假设3.1 (积木块假设(Building Block Hypothesis)) 阶数低、长度短、适应度高的模式(积木块) 在遗传算子作用下，相互结合，能生成阶数高、长度长、适值高的模式，可最终生成全局最优解。

与积木块一样，一些好的模式在遗传算法操作下相互拼搭、结合，产生适应度更高的串，从而找到更优的可行解，这正是积木块假设所揭示的内容。下面用图来说明遗传算法中积木块生成最优解的过程。

假设每代种群规模为8，S i 表示每代群体中第i 个个体，问题的最优解由积木块AA 、BB 、CC 组成。图3.1为初始种群，个体S 1、S 7含有AA ，个体S 4、S 8含有BB ，个体S 3含有CC 。

S 1

S 2

S 3

S 4

S 5

S 6

S 7

S 8 图3.1 初始种群 当种群进化一代后，图3.2为第二代种群，个体S 1、S 3、S 7含有AA ，个体S 2、S 7含有BB ，个体S 3、S 6含有CC 。个体S 3含有AA 、CC ，个体S 7含有AA 、BB 。当种群进化到第二代后，

图3.3为第三代种群，在群体中，出现了含有积木块AA 、BB 、CC 的个体S 3，个体S 3就是问题的最优解。

S 1 S 2

S 3

S 4

S 5

S 6

S 7

S 8 图3.2 第二代种群

S 1 S 2

S 3

S 4

S 5

S 6

S 7

S 8 图3.3 第三代种群 模式定理保证了较优的模式(遗传算法的较优解) 样本数呈指数增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而这里的积木块假设则指出，遗传算法具备找到全局最优解的能力，即积木块在遗传算子作用下，能生成阶数高、长度长、适应度高的模式，最终生成全局最优解。

3.3 欺骗问题

在遗传算法中，将所有妨碍适应度高的个体的生成从而影响遗传算法正常工作的问题统称为欺骗问题(Deceptive Problem)。遗传算法运行过程具有将阶数低、长度短、平均适应度高于群体平均适应度的模式重组成高阶模式的趋势。如果在低阶模式中包含了最优解，则遗传算法就可能找出这个最优解来。但是低阶、高适应度的模式可能没有包含最优串的具体取值，于是遗传算法就会收敛到一个次优的结果。下面给出有关欺骗性的概念。

定义 3.5(竞争模式) 若模式H 和'H 中，* 的位置完全一致，但任一确定位的编码均不同，则称H 和'

H 互为竞争模式。

定义3.6(欺骗性) 假设)(X f 的最大值对应的X 的集合为*X ，H 为一包含*X 的m 阶

模式。H 的竞争模式为'H ，而且)()('H f H f ，则f 为m 阶欺骗。 定义 3.7(最小欺骗性) 在欺骗问题中，为了造成骗局所需设置的最小的问题规模(即阶数) 。其主要思想是在最大程度上违背积木块假设，是优于由平均的短积木块生成局部最优点

的方法。这里的“最小”是指问题规模采用两位。下面是一个由4个阶数为2、有2个确定位置的模式集：

)

11(*1*****1***)10(*

0*****1***)01(*

1*****0***)00(*

0*****0***f f f f 为简单(达到最小) 起见，我们不考虑 * 位，令)11(f 为全局最优解，为了欺骗遗传算法，Goldberg 设计了两种情况：

Type1：)00()01(f f >

Type2：)01()00(f f >

满足*)1(*)0(f f >或者)1(*)0(*f f >。

按Holland 的模式定理，最小欺骗问题将给遗传算法造成很大困难，遗传算法甚至找不到最优解。但Goldberg 实验的结果却是：Type1问题基本上都很快找到了最优解，Type2问题找到和找不到两种情况都可能出现。

遗传算法中欺骗性的产生往往与适应度函数确定和调整、基因编码方式选取相关。采用合适的编码方式或调整适应度函数，就可能化解和避免欺骗问题。下面以合适的编码方式为例来说明。

一个2位编码的适应度函数为

326

746114)(x x x x f +-+= 采用二进制编码，计算个体的函数值（见表 3.1），则存在第二类欺骗问题。采用格雷编码，计算个体的函数值（见表3.2），则第二类欺骗问题化解为第一类欺骗问题。

表3.1 二进制编码及函数值 表3.2 格雷编码及函数值

采用适当的适应度函数调整方法，设

)(x g ：(00)128,(01)1,(10)(11)32g g g g ====

如果适应度函数)()(x g x f =，则

322)11()10(*)1(5.642)01()00(*)0(=+==+=

f f f f f f 故存在欺骗问题。

如果用适应度函数的调整方法，2()log ()f x g x =，则

5)10()11(,0)01(,7)00(====f f f f

得5*)1(,5.3*)0(==f f ，故不会产生欺骗问题。

3.4 遗传算法的未成熟收敛问题及其防止

在实际中，很多参数优化问题是多参数和非线性的，且往往还伴随着不可微和参数耦合等问题。这时用传统的优化方法解决这种问题，效率很低，有时候甚至根本得不出结果。遗传算法的高鲁棒性和有效性为解决这类问题提供了一种有效的途径。

在实际应用中，遗传算法显示出了顽强的生命力，以其突出的优点而越来越受到重视。但是遗传算法也存在着缺点，在实际应用中也因此出现了一些问题，其中很重要的是遗传算法未成熟收敛(也称为早熟，Premature Convergence ，PC) 问题。对于遗传算法的应用，解决未成熟收敛问题是必要的，否则，遗传算法的一些优良性能(例如全局寻优能力) 将无法完全体现出来。

3.4.1 遗传算法的未成熟收敛问题

1．未成熟收敛现象

未成熟收敛现象主要表现在两个方面：

(1) 体中所有的个体都陷于同一极值而停止进化。

(2) 接近最优解的个体总是被淘汰，进化过程不收敛。

未成熟收敛现象是遗传算法中的特有现象，且十分常见。它指的是，当还未达到全局最优解或满意解时，群体中不能再产生性能超过父代的后代，群体中的各个个体非常相似。未成熟收敛的重要特征是群体中个体结构的多样性急剧减少。这将导致遗传算法的交叉算子和选择算子不能再产生更有生命力的新个体。遗传算法希望找到最优解或满意解，而不是在找到最优解或满意解之前，整个群体就收敛到一个非优个体，它希望能够保持群体中个体结构的多样性，从而使搜索能够进行下去。未成熟收敛问题就像其它算法中的局部极小值(极大值)问题，但它和局部极小值问题有着本质上的不同，未成熟收敛问题并不一定出现在局部极小点。同时，它的产生是带有随机性的，人们很难预见是否会出现未成熟收敛问题。

2．未成熟收敛产生的主要原因

未成熟收敛产生的主要原因有以下几点：

(1) 理论上考虑的选择、交叉、变异操作都是绝对精确的，它们之间相互协调，能搜索到整个解空间，但在具体实现时很难达到这个要求。

(2) 所求解的问题是遗传算法欺骗问题。当解决的问题对于标准遗传算法来说比较困难时，遗传算法就会偏离寻优方向，这种问题被称为遗传算法欺骗问题。

(3) 遗传算法处理的群体是有限的，因而存在随机误差，它主要包括取样误差和选择误差。取样误差是指所选择的有限群体不能代表整个群体所产生的误差。当表示有效模板串的数量不充分或所选的串不是相似子集的代表时，遗传算法就会发生上述类似的情况。小群体中的取样误差妨碍模板的正确传播，因而阻碍模板原理所预测的期望性能产生。选择误差是指不能按期望的概率进行个体选择。

对一个染色体来说，在遗传操作中只能产生整数个后代。在有限群体中，模板的样本不可能以任意精度反映所要求的比例，这是产生取样误差的根本原因，加上随机选择的误差，就可以导致模板样品数量与理论预测值有很大差别。随着这种偏差的积累，一些有用的模板将会从群体中消失。遗传学家认为当群体很小时，选择就不会起作用，这时有利的基因可能

被淘汰，有害的基因可能被保留。引起群体结构发生变化的主要因素是随机波动的——遗传漂移，它也是产生未成熟收敛的一个主要原因。对此可以采用增大群体容量的方法来减缓遗传漂移，但这样做可能导致算法效率的降低。

上述三个方面都有可能产生未成熟收敛现象，即群体中个体的多样性过早地丢失，从而使算法陷入局部最优点。

在遗传算法处理过程的每个环节都有可能导入未成熟收敛的因素。遗传算法未成熟收敛产生的主要原因是，在迭代过程中，未得到最优解或满意解以前，群体就失去了多样性。具体表现在以下几个方面：

(1) 在进化初始阶段，生成了具有很高适应度的个体X 。

(2) 在基于适应度比例的选择下，其它个体被淘汰，大部分个体与X 一致。

(3) 相同的两个个体进行交叉，从而未能生成新个体。

(4) 通过变异所生成的个体适应度高但数量少，所以被淘汰的概率很大。

(5) 群体中的大部分个体都处于与X 一致的状态。

3.4.2 未成熟收敛的防止

在分析了未成熟收敛产生的原因后，下面要解决的是如何防止该现象的发生，即如何维持群体多样性以保证在寻找到最优解或满意解以前，不会发生未成熟收敛现象。解决的方法有以下几种。

1．重新启动法

这是实际应用中最早出现的方法之一。在遗传算法搜索中碰到未成熟收敛问题而不能继续时，则随机选择一组初始值重新进行遗传算法操作。假设每次执行遗传算法后陷入不成熟收敛的概率为)10(<≤Q Q ，那么做n 次独立的遗传算法操作后，可避免未成熟收敛的概率为n Q n F -=1)(，随着n 的增大，)(n F 将趋于1。但是，对于Q 较大的情况，如果优化对象很复杂以及每次执行时间都很长的情况，采用该办法显然是不合适的。

2．配对策略(Mating Strategies )

为了维持群体的多样性，可以有目的地选择配对个体。一般情况下，在物种的形成过程中要考虑配对策略，以防止根本不相似的个体进行配对。因为在生物界，不同种族之间一般是不会杂交的，这是因为它们的基因结构不同，会发生互斥作用，同时杂交后会使种族失去其优良特性。因此，配对受到限制，即大多数是同种或近种相配，以使一个种族的优良特性得以保存和发扬。然而，这里所说的匹配策略有不同的目的。其目的是，由不同的父辈产生的个体试图比其父辈更具有多样性，Goldberg 的共享函数(Sharing Function) 就是一种间接匹配策略。该策略对生物种(Species) 内的相互匹配或至少对占统治地位的物种内的相互匹配有一定限制。Eshelman 提出了一种可以更直接地防止相似个体交配的方法——防止乱伦机制(Incest Prevention Mechanism) 。参与交配的个体是随机配对的，但只有当参与配对的个体间的海明距离超过一定阈值时，才允许它们进行交配。最初的阈值可采用初始群体海明距离的期望平均值，随着迭代过程的发展，阈值可以逐步减小。尽管Eshelman 的方法并不能明显地阻止同辈或相似父辈之间进行交配，但只要个体相似，它就有一定的影响。匹配策略是对具有一定差异的个体进行配对，这在某种程度上可以维持群体的多样性。但它同时也具有一定的副作用，即交叉操作会使较多的模板遭到破坏，只有较少的共享模板得以保留。

3． 重组策略(Recombination Strategies)

重组策略就是使用交叉算子。在某种程度上，交叉操作试图产生与其父辈不同的个体，从而使产生的群体更具多样性。能使交叉操作更具有活力的最简单的方法就是，增加其使用的频率和使用动态改变适应度函数的方法，如共享函数方法。另一种方法是把交叉点选在个

体的具有不同值的位上。只要父辈个体至少有两位不同，所产生的子代个体就会与其父辈不相同。维持群体多样性的更基本的方法是，使用更具有破坏性的交叉算子，如均匀交叉算子。该算子试图交叉近一半的不同位，因而保留的模板比单点或两点交叉所保留的模板要少得多。总之，重组策略主要是从使用频率和交叉点两方面考虑，来维持群体的多样性。这对采用随机选择配对个体进行交叉操作可能有特定的意义，但对成比例选择方式，其效果则不一定明显。

4 替代策略(Replacement Strategies )

匹配策略和重组策略分别是在选择、交叉阶段，通过某种策略来维持群体的多样性。而替代策略是确定在选择、交叉产生的个体中，选择哪一个个体进入新一代群体。De Jong 采用排挤（Crowding ）模式，用新产生的个体去替换父辈中类似的个体。Syscuda 和Whiteley 也采用类似的方法，他们仅把与父辈各个个体均不相似的新个体添加到群体中。这种替换策略仅从维持群体的多样性出发，存在一定的负面影响，即交叉操作会破坏较多模板，但这种影响比前两种策略的要少。

3.5 性能评估

遗传算法的实现涉及到它的五个要素：参数编码、初始群体的设定、适应度函数的设计、遗传操作设计和控制参数设定，而每个要素又对应不同的环境，存在各种相应的设计策略和方法。不同的策略和方法决定了各自的遗传算法具有不同的性能或特征。因此，评估遗传算法的性能对于研究和应用遗传算法是十分重要的。

目前，遗传算法的评估指标大多采用适应度值。特别在没有具体要求的情况下，一般采用各代中最优个体的适应度值和群体的平均适应度值。以此为依据，De Jong 提出了两个用于定量分析遗传算法的测度：离线性能(Off-line Performance)测度和在线性能(On-line Performance)测度，得到两个评估准则。

1．在线性能评估准则

定义3.8 设)(s X e 为环境e 下策略s 的在线性能，)(t f e 为时刻t 或第t 代中相应于环境e 的目标函数或平均适应度函数，则)(s X e 可以表示为

∑==T

t e e t f T s X 1

)(1)( (3.9) 式(3.9) 表明，在线性能可以用从第一代到当前的优化进程的平均值来表示。

2．离线性能评估准则

定义3.9 设)(*s X e 为环境e 下策略s 的离线性能，则有

∑==T t e e

t f T s X 1**)(1)( (3.10) 式中，)}(),2(),1({)(*

t f f f best t f e e e e =。

式(3.10) 表明，离线性能是特定时刻或特定代的最佳性能的累积平均。具体地说，在进化过程中，每进化一代就统计目前为止的各代中的最佳适应度或最佳平均适应度，并计算对进化代数的平均值。

De Jong 指出：离线性能用于测量算法的收敛性，在应用时，优化问题的求解可以得到模

拟，在一定的优化进程停止准则下，当前最好的解可以被保存和利用；而在线性能用于测量算法的动态性能，在应用时，优化问题的求解必须通过真实的实验在线实现，可以迅速得到较好的优化结果。但是，从遗传算法的运行机理可知，在遗传算子的作用下，群体的平均适应度呈现增长的趋势，因此，定义3.8和定义3.9中的)(t f e 和)(*t f e 相差不大，它们所反映的性质也基本一样。

下面以最优化方法的收敛速度和收敛准则来讨论遗传算法的性能。

一般优化问题可描述为求T n x x x x ),,,(21 =，使)(x f 达到最小(或最大) 。最优化方法通常采用迭代方法求它的最优解，其基本思想为：给定一个初始点0x ，按照某一迭代规则产生一个点列}{i x ，使得当}{i x 为有穷点列时，其最后一个点是最优化问题的最优解。当}{i x 是无穷点列时，它有极限点，且其极限点是最优化问题的最优解。一个好的优化算法为：当i x 能稳定地接近全局极小点(或极大点) 的邻域时，迅速收敛于*x ，当满足给定的收敛准则时，迭代终止。

假设一算法产生的迭代点列}{i x 在某种范数意义下收敛，即

0lim *=-∞→x x i i (3.11)

式中，i i i x x α+=+1，i α为步长因子。

若存在实数0>α及一个与迭代次数无关的常数0>q ，使得

q x x x x i i i =--+∞→**1lim (3.12)

则称此算法产生的迭代点列}{i x 具有α-q 阶收敛速度（α为迭代步长因子）。因为i

i x x -+1是*x x i -的一个估计，所以在实际中，一般用i i x x -+1代替*x x i -，作为迭代终止判决条件。

(1) 当1=α，0>q 时，称}{i x 具有q 线性收敛速度。

(2) 当21<<α，0>q 或1=α，0=q 时，称}{i x 具有q 超线性收敛速度。

(3) 当2=α时，称}{i x 具有q 二阶收敛速度。

具有超线性收敛速度和二阶收敛速度的迭代算法的收敛速度比较快。

关于算法的终止准则，实际应用中可以使用各种不同的方法进行确定。Himmeblau 提出了下面的终止准则。 当ε>i x 和ε>)(i x f 时，采用

ε≤-+i

i i x x x 1 或 ε≤-+)()()(1i i i x f x f x f (3.13) 否则采用

ε<-+i i x x 1 或 ε<-+)()(1i i x f x f (3.14)

式中，ε为根据实际问题要求精度给出的适当小的正数。

根据以上Himmeblau 提出的终止准则，实际中可以用各代适应度函数的均值之差来衡量遗传算法的收敛特性。定义收敛性测量函数为：

∑=-+=T

t e e e t f t f T s C 1

)]()1([1)( (3.15) 式中，)('t f e 为时刻t 或第t 代中相应于环境e 的目标函数或平均适应度函数。

从优化问题中寻找最优解或最优解组的角度考虑，可以定义部分在线特性：

∑==T t e n t f T s f 1

')(1)( (3.16) 式中，)('t f e 为群体中对应于最优解或最优解组的个体适应度的均值。

3.6 小生境技术和共享函数

Cavicchio 提出只有在子串的适应度超过父代的情况下，子串才能替代父串进入下一代群体的预选择机制，该机制趋向于替换与其本身相似的个体，能够维持群体的分布特性，并且不断地以优秀个体来更新种群，使种群不断被优化。

De Jong 提出基于排挤的机制，其思想来源于一个有趣的生物现象：在一个有限的生存空间中，各种不同的生物为了延续生存，必须相互竞争各种有限的生存资源。差别较大的个体由于生活习性不同而很少竞争。处于平衡状态的大小固定的种群，新生个体将代替与之相似的旧个体。排挤机制可以维护当前种群的多样性，排挤机制用海明距离来度量个体之间的相似性。这就是小生境技术。

Glodberg 和Richardson 利用共享函数来度量两个个体的相邻关系和程度。给定个体g ，它的共享函数由它与种群中其它个体的相似程度决定。将g 与种群中其它个体逐个比较，若很相似，则对g 的共享函数加一个较大值；否则，就加一个较小值。个体共享度为该个体与群体内其它个体共享函数值之和，即

∑==n j ij i d

S S 1)( (3.17)

式中，ij d 为个体i 和个体j 之间的关系亲密程度；S 为共享函数；i S 为个体i 在群体中的共享度。

个体的适应度的调整公式为：

i s S i f i f )()(= (3.18)

用遗传算法求解Rosenbrock函数最优解实验报告

姓名学号 实验 成绩 华中师范大学计算机科学系 实验报告书 实验题目：用遗传算法求解Rosenbrock函数的最大值问题课程名称：智能计算 主讲教师：沈显君 辅导教师： 课程编号： 班级：2011级 实验时间：2011.11

用遗传算法求解Rosenbrock函数最大值问题 摘要： 本文利用遗传算法研究了求解Rosenbrock函数的最大值问题．在较多的计算机模拟实验结果中表明，用遗传算法可以有效地解决这一问题．文中分析了一种基于遗传算法对Rosenbrock函数最大值问题的求解，得到了适于解决此问题的合理的遗传操作，从而为有效地解决最速下降法所不能实现的某一类函数代化问题提供了一种新的途径．通过对基于遗传算法对Rosenbrock函数最大值问题的求解，进一步理解遗传算法对解决此类问题的思想。 关键词：遗传算法，Rosenbrock函数，函数优化，最速下降法。 Abstract： This paper deals with the maximum of Rosenbrock s function based ongenetic algorithms. The simulated results show that the problem can be solved effectivelyusing genetic algorithms. The influence of some rnodified genetic algorithms on searchspeed is also examined. Some genetic operations suitable to the optimization technique areobtained, therefore, a novel way of solving a class of optimizations of functions that cannot be realized using the method of steepest descent is proposed.Through dealing with the maximum of Rosenbrock s function based ongenetic algorithms，a better understanding of the genetic algorithm to solve such problems thinking. Keyword：ongenetic algorithms，Rosenbrock function，function optimization，Steepest descent method

基于模板匹配算法的数字识别讲解

中南民族大学 毕业论文(设计) 学院: 计算机科学学院 专业: 软件工程年级:2009 题目: 基于模板匹配算法的数字识别学生姓名: 李成学号:09065093指导教师姓名: 李波职称: 讲师 2013年5月

中南民族大学本科毕业论文（设计）原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。 作者签名：2013年月日

摘要 (1) Abstract (1) 1 绪论 (2) 1.1 研究目的和意义 (2) 1.2 国内外研究现状 (2) 2 本文基本理论介绍 (3) 2.1 位图格式介绍 (3) 2.2 二值化 (3) 2.3 去噪 (3) 2.4 细化 (4) 2.5 提取骨架 (4) 3 图像的预处理 (5) 3.1 位图读取 (5) 3.2 二值化及去噪声 (5) 3.3 提取骨架 (6) 4 基于模板匹配的字符识别 (8) 4.1 样本训练 (8) 4.2 特征提取 (8) 4.3 模板匹配 (9) 4.4 加权特征模板匹配 (10) 4.5 实验流程与结果 (10) 5 结论 (16) 5.1 小结 (16) 5.2 不足 (16) 6 参考文献 (17)

基于模板匹配算法的数字识别 摘要 数字识别已经广泛的应用到日常生活中，典型的数字自动识别系统由图像采集、预处理、二值化、字符定位、字符分割和字符识别等几部分组成, 这些过程存在着紧密的联系。传统的模板匹配算法因为图像在预处理之后可能仍然存在较大的干扰，数字笔画粗细不均匀，有较大的噪声，识别效率不高。本文采的主要思想就是对字符进行分类，之后对字符进行细化，提取细化后字符的特征矢量，与模板的特征矢量进行加权匹配，误差最小的作为识别结果。本文在模板匹配法的基础上, 采用了特征值加权模板匹配法, 并且改进了匹配系数的求法。应用该法取得了满意的效果, 提高了识别率。 关键词：模板匹配；数字识别；特征值加权；字符识别； Template matching algorithm-based digital identification Abstract Digital identification has been widely applied to daily life, the typical digital automatic identification system by the image acquisition, pre-processing, binarization, character positioning, character segmentation and character recognition several parts, there is a close link these processes. Traditional template matching algorithm because the image may still exist after pre-greater interference, digital strokes uneven thickness, the noise, the identification efficiency is not high. Adopted herein main idea is to classify the character after character refinement, the characters feature vector extraction refinement, and the template feature vector is weighted matching, the minimum error as a recognition result. Template matching method based on feature weighted template matching method, and improve the matching coefficient method. The application of the method to obtain satisfactory results, to improve the recognition rate. Key words：Template matching; digital identification; characteristic value weighted; character recognition;

遗传算法的优缺点

遗传算法属于进化算法( Evolutionary Algorithms) 的一种, 它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子: 选择、交叉和变异. 。数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。 生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法( GA)。算法中称遗传的生物体为个体( individual )，个体对环境的适应程度用适应值( fitness )表示。适应值取决于个体的染色体(chromosome),在算法中染色体常用一串数字表示，数字串中的一位对应一个基因 (gene)。一定数量的个体组成一个群体(population )。对所有个体进 行选择、交叉和变异等操作,生成新的群体,称为新一代( new generation )。遗传算法计算程序的流程可以表示如下［3］：第一步准备工作 (i)选择合适的编码方案，将变量(特征)转换为染色体(数字串，串长为m。通常用二 进制编码。 (2 )选择合适的参数，包括群体大小(个体数M)、交叉概率PC和变异概率Pm (3、确定适应值函数f (x、。f (x、应为正值。 第二步形成一个初始群体(含M个个体)。在边坡滑裂面搜索问题中，取已分析的可能滑裂 面组作为初始群体。 第三步对每一染色体(串)计算其适应值fi ,同时计算群体的总适应值。 第四步选择 计算每一串的选择概率Pi=fi/F 及累计概率。选择一般通过模拟旋转滚花轮 ( roulette ,其上按Pi大小分成大小不等的扇形区、的算法进行。旋转M次即可选出M个串来。在计算机 上实现的步骤是：产生［0,1］间随机数r，若rpc ,则该串参加交叉操作,如此选出参加交叉的一组后,随机配对。 (2)对每一对，产生［1 , m］间的随机数以确定交叉的位置。 第六步变异 如变异概率为Pm则可能变异的位数的期望值为Pm x mx M,每一位以等概率变异。具体为 对每一串中的每一位产生［0 , 1］间的随机数r,若r

遗传算法求解函数最大值

人工智能 遗传算法函数优化

目录 1引言 (3) 1.1 摘要 (3) 1.2 背景 (3) 2 实验过程 (4) 2.1 程序目标 (4) 2.2 实验原理及步骤 (4) 2.3程序 (5) 2.3.1程序理解： (5) 2.3.3调试程序： (5) 2.4 实验总结 (18)

1引言 1.1 摘要 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。本文将用一个详细的例子来说明用遗传算法解一个简单参数优化问题的过程。这里求解的是一个函数的最大值的问题。 1.2 背景 遗传算法采纳自然进化模型。通过保持一个潜在解的群体执行了多方向的搜索并支持这些方向上的信息构成和交换。群体经过一个模拟进化的过程：在每一代，相对“好”的解产生，相对“差”的解死亡。为区别不同解，我们使用了一个目标（评价）函数，它起着一个环境的作用。 选择是用来确定管理费用或交叉个体，以及被选个体将产生多少个代个体。 杂交组合了两个亲代染色体的特征，并通过交换父代相应的片断形成了两个相似的后代。杂交算子的意图是在不同潜在解之间进行信息交换。 变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因。变异算子的意图是向群体引入一些额外的变化性。 运用遗传算法解题必经的五个步骤： 1．对问题潜在解的遗传表达。 2．产生潜在解初始群体的方法。 3．起环境作用的用“适应值”评价解的适应程度的评价函数。 4．改变后代组成的各种遗传算子。 5．遗传算法所使用的各种参数：群体规模、应用遗传算子的概率等。

2 实验过程 2.1 程序目标 在实验过程中，我们应用遗传算法来模拟一个函数优化的问题。程序所要解决的问题是求f(x1,x2)=21.5+x1*sin(4pi*x1)+x2*sin(20pi*x2)的最大值，其中-3.0≤x1≤12.1及4.1≤x2≤5.8。 2.2 实验原理及步骤 1 ）首先确立变量x1的定义域长度为15.1；所要求的小数点以后第四位精度意味着区间[-3.0, 12.1]应该至少被分成15.1*10000个等距区间，即染色体的第一部分需要18位；自变量x2域长度为 1.7，精度要求区间[4.1, 5.8]应该至少被分成1.7*10000个等距区间，即染色体的第二部分需要15位。所以染色体总长度为33位。用遗传算法的优化函数f,产生了一个有pop_size = 20个染色体的群体。所有染色体的33位都是随机初始化。对每个染色体进行解码并计算解码后的（x1,x2）的适应函数值，eval(vi) (i=1,..,pop_size) = f(x1,x2)。 2）为选择过程建立一个轮盘。计算群体的总适应值F，并计算每个染色体vi (i=1,..,pop_size)的选择概率pi:pi = eval(vi) / F 和累积概率qi: qi = p1 + .. + pi. 3）转动轮盘20次，每次为新群体选择一单个染色体。生成一个区间[0,1]里的20个数的一个随机序列。如果一个随机数位于qi于q(i+1)之间，则q(i+1)被选择。4）对新群体中的个体应用杂交算子。杂交概率pc = 0.25，所以预计染色体中平均有25%将经历杂交。杂交按照下面的方法进行：对新群体中的每个染色体，产生在区间[0,1]里的随机数r,并从随机序列中选出r<0.25的染色体进行杂交。 5）对被选择的染色体随机进行配对。并从区间[1,32]里产生一个随机整数pos。数字pos表示杂交点的位置。 6）算子变异。在一位一位基础上执行。变异概率pm = 0.01,所以我们预计平均将有1%的位经历变异。整个群体共有m*pop_size = 660位，可以预计平均每代有6.6次变异。因为每一位都有均等的机会被变异，所以对群体中的每一位可以产生区间

第三章-遗传算法的理论基础

第三章 遗传算法的理论基础 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。Holland 的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。 3.1 模式定理 不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。 定义3.1 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。 以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001) 。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。 引入模式后，我们看到一个串实际上隐含着多个模式(长度为 n 的串隐含着2n 个模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容 定义3.2 模式H 中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式 0* * * * *的阶数为1。 显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。 定义3.3 模式H 中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作)(H δ。比如，模式 011*1*的定义距为4，而模式 0* * * * *的定义距为0。 模式的阶数和定义距描述了模式的基本性质。 下面通过分析遗传算法的三种基本遗传操作对模式的作用来讨论模式定理。令)(t A 表示第t 代中串的群体，以),,2,1)((n j t A j =表示第t 代中第j 个个体串。 1．选择算子 在选择算子作用下，与某一模式所匹配的样本数的增减依赖于模式的平均适值，与群体平均适值之比，平均适值高于群体平均适值的将呈指数级增长；而平均适值低于群体平均适值的模式将呈指数级减少。其推导如下： 设在第t 代种群)(t A 中模式所能匹配的样本数为m ，记为),(t H m 。在选择中，一个位串 j A 以概率/j j i P f f =∑被选中并进行复制，其中j f 是个体)(t A j 的适应度。假设一代中群体 大小为n ，且个体两两互不相同，则模式H 在第1+t 代中的样本数为：

遗传算法在图像处理中的应用

. . 课程：新技术讲座 题目：遗传算法在图像处理中的应用姓名： 学号：

目录 摘要 (2) 1.引言 (3) 2.遗传算法的基本原理和基本性质 (3) 3.遗传算法在图像处理中的应用 (5) 3.1在图像增强中的应用 (5) 3.2在图像恢复中的应用 (6) 3.3在图像分割中的应用 (7) 3.4在图像压缩中的应用 (8) 3.5在图像匹配中的应用 (9) 4.遗传算法在图像处理中的问题及发展方向 (10) 参考文献 (10)

遗传算法在图像处理中的应用 摘要 遗传算法是一种模拟生命进化机制，基于生物自然选择与遗传机理的随机搜索与优化方法。近几年来，遗传算法广泛应用在生物信息学、系统发生学、计算科学、工程学、经济学、化学、制造、数学、物理、药物测量学和其他领域之中，这种算法得到快速发展，尤其是在计算机科学人工智能领域中。本文将在系统并且深入的介绍遗传算法基本理论的基础上，重点综述遗传算法在数字图像处理中的主要应用，深入研究目前遗传算法在图像处理领域中存在的问题，并对这些问题作出了一些个人的见解，阐述了遗传算法在图像处理应用的发展方向。 关键词：遗传算法，数字图像处理 Abstract Genetic Algorithm is a simulation of the life evolution mechanism, random search and optimization method which is based on the natural selection and genetic mechanism.In recent years,due to the enormous potential of solving complex optimization problems and the successful applications in the industrial field,the Genetic Algorithm developed rapidly,Especially in the field of artificial intelligence in computer science.This article not only describes the basic theoretical foundation of genetic algorithms,but also focus on Genetic Algorithm in digital image processing.Moreover,it studies the problems of the Genetic Algorithm in the field of image processing and the direction of development in the future，Moreover,the author elaborates the personal opinion in the end. keyword ：Genetic Algorithm,Digital image processing

遗传算法

遗传算法的基本理论 一、起源： 早在20世纪50年代和60年代，就有少数人几个计算机科学家独立地进行了所谓的“人工进化系统”研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏形，如大多数系统都遵循“适者生存”的仿自然法则，有些系统采用了基于群体（population）的设计方案，并且加入了自然选择与变异操作，还有一些系统对生物染色体编码进行了抽象处理，应用二进制编码。由于缺乏一种通用的编码方案，人们只能依赖变异而非交叉来产生新的基因结构，早期的算法收敛甚微。20世纪60年代中期，美国Michigan大学的John Holland在A.S.Fraser和H.J.Bremermann等人工作的基础上提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉（即杂交）操作。并且强调将交叉作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了其开创性著作“Adaption in Natural and Artificial System”。以后，Holland等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作作为其广泛、成功地应用奠定了基础。Holland早期有关遗传算法的许多概念一直沿用至今，可见Holland对遗传算法的贡献之大。他认为遗传算法本质上是适应算法，应用最多的是系统最优化的研究。 二、发展： 年份贡献者内容 1962Holland程序漫游元胞计算机自适应系统框架 1968Holland模式定理的建立 1971Hollstein具有交配和选择规则的二维函数优化 1972Bosworth、Foo、Zeigler提出具有复杂变异、类似于遗传算法的基因操作1972Frantz位置非线性和倒位操作研究 1973Holland遗传算法中试验的最优配置和双臂强盗问题 1973Martin类似遗传真法的概率算法理论 1975De Jong用于5个测试函数的研究基本遗传算法基准参数 1975Holland 出版了开创性著作《Adaptation in Natural and Artificial System》 1981Bethke应用Walsh函数分析模式 1981Brindle研究遗传算法中的选择和支配问题 1983Pettit、Swigger遗传算法应用于非稳定问题的粗略研究1983Wetzel用遗传算法解决旅行商问题(TSP) 1984Mauldin基本遗传算法小用启发知识维持遗传多样性1985Baker试验基于排序的选择方法 1985Booker建议采用部分匹配计分、分享操作和交配限制法1985Goldberg、Lingle TSP问题个采用部分匹配交叉 1985Grefenstette、Fitzpattrick对含噪声的函数进行测试 1985Schaffer多种群遗传算法解决多目标优化问题1986Goldberg最优种群大小估计 1986Grefenstette元级遗传算法控制的遗传算法 1987Baker选择中随机误差的减少方法 1987Goldberg复制和交叉时最小欺骗问题(MDP) 1987Goldberg、Richardson借助分享函数的小生境和物种归纳法

遗传算法的应用研究_赵夫群

2016年第17期 科技创新科技创新与应用 遗传算法的应用研究 赵夫群 （咸阳师范学院，陕西咸阳712000） 1概述 遗传算法（Genetic Algorithms，GA）一词源于人们对自然进化系统所进行的计算机仿生模拟研究，是以达尔文的“进化论”和孟德尔的“遗传学原理”为基础的，是最早开发出来的模拟遗传系统的算法模型。遗传算法最早是由Fraser提出来的，后来Holland对其进行了推广，故认为遗传算法的奠基人是Holland。 随着遗传算法的不断完善和成熟，其应用范围也在不断扩大，应用领域非常广泛，主要包括工业控制、网络通讯、故障诊断、路径规划、最优控制等。近几年，出现了很多改进的遗传算法，改进方法主要包括：应用不同的交叉和变异算子；引入特殊算子；改进选择和复制方法等。但是，万变不离其宗，都是基于自然界生物进化，提出的这些改进方法。 2遗传算法的原理 遗传算法是从某一个初始种群开始，首先计算个体的适应度，然后通过选择、交叉、变异等基本操作，产生新一代的种群，重复这个过程，直到得到满足条件的种群或达到迭代次数后终止。通过这个过程，后代种群会更加适应环境，而末代种群中的最优个体，在经过解码之后，就可以作为问题的近似最优解了。 2.1遗传算法的四个组成部分 遗传算法主要由四个部分组成[1]：参数编码和初始群体、适应度函数、遗传操作和控制参数。编码方法中，最常用的是二进制编码，该方法操作简单、便于用模式定理分析。适应度函数是由目标函数变换而成的，主要用于评价个体适应环境的能力，是选择操作的依据。遗传操作主要包括了选择、交叉、变异等三种基本操作。控制参数主要有：串长Z，群体大小size，交叉概率Pc，变异概率Pm等。目前对遗传算法的研究主要集中在参数的调整中，很多文献建议的参数取值范围一般是：size取20~200之间，Pc取0.5~1.0之间，Pm取0~0.05之间。 2.2遗传算法的基本操作步骤 遗传算法的基本操作步骤为： （1）首先，对种群进行初始化；（2）对种群里的每个个体计算其适应度值；（3）根据（2）计算的适应度，按照规则，选择进入下一代的个体；（4）根据交叉概率Pc，进行交叉操作；（5）以Pm为概率，进行变异操作；（6）判断是否满足停止条件，若没有，则转第（2）步，否则进入（7）；（7）得到适应度值最优的染色体，并将其作为问题的满意解或最优解输出。 3遗传算法的应用 遗传算法的应用领域非常广泛，下面主要就遗传算法在优化问题、生产调度、自动控制、机器学习、图像处理、人工生命和数据挖掘等方面的应用进行介绍。 3.1优化问题 优化问题包括函数优化和组合优化两种。很多情况下，组合优化的搜索空间受问题规模的制约，因此很难寻找满意解。但是，遗传算法对于组合优化中的NP完全问题非常有效。朱莹等[2]提出了一种结合启发式算法和遗传算法的混合遗传算法来解决杂货船装载的优化问题中。潘欣等[3]在化工多目标优化问题中应用了并行遗传算法，实验结果表明该方法效果良好。王大东等[4]将遗传算法应用到了清运车辆路径的优化问题求解中，而且仿真结果表明算法可行有效。 3.2生产调度 在复杂生产调度方面，遗传算法也发挥了很大的作用。韦勇福等[5]将遗传算法应用到了车间生产调度系统的开发中，并建立了最小化完工时间目标模型，成功开发了车间生产调度系统模块，并用实例和仿真验证了该方法的可行性。张美凤等[6]将遗传算法和模拟退火算法相结合，提出了解决车间调度问题的混合遗传算法，并给出了一种编码方法以及建立了相应的解码规则。 3.3自动控制 在自动控制领域中，遗传算法主要用于求解的大多也是与优化相关的问题。其应用主要分为为两类，即离线设计分析和在线自适应调节。GA可为传统的综合设计方法提供优化参数。 3.4机器学习 目前，遗传算法已经在机器学习领域得到了较为广泛的应用。邢晓敏等[7]提出了将遗传算子与Michigan方法和基于Pitt法的两个机器学习方法相结合的机器学习方法。蒋培等[8]提出了一种基于共同进化遗传算法的机器学习方法，该方法克服了学习系统过分依赖于问题的背景知识的缺陷，使得学习者逐步探索新的知识。 3.5图像处理 图像处理是一个重要的研究领域。在图像处理过程中产生的误差会影响图像的效果，因此我们要尽可能地减小误差。目前，遗传算法已经在图像增强、图像恢复、图像重建、图像分形压缩、图像分割、图像匹配等方面应用广泛，详见参考文献[9]。 4结束语 遗传算法作为一种模拟自然演化的学习过程，原理简单，应用广泛，已经在许多领域解决了很多问题。但是，它在数学基础方面相对不够完善，还有待进一步研究和探讨。目前，针对遗传算法的众多缺点，也相继出现了许多改进的算法，并取得了一定的成果。可以预期，未来伴随着生物技术和计算机技术的进一步发展，遗传算法会在操作技术等方面更加有效，其发展前景一片光明。 参考文献 [1]周明，孙树栋.遗传算法原理及应用[M].国防工业出版社，1999，6. [2]朱莹，向先波，杨运桃.基于混合遗传算法的杂货船装载优化问题[J].中国船舰研究，2015：10（6）：126-132. [3]潘欣，等.种群分布式并行遗传算法解化工多目标优化问题[J].化工进展，2015：34（5）：1236-1240. [4]王大东，刘竞遥，王洪军.遗传算法求解清运车辆路径优化问题[J].吉林师范大学学报（自然科学版），2015（3）：132-134. [5]韦勇福，曾盛绰.基于遗传算法的车间生产调度系统研究[J].装备制造技术，2014（11）：205-207. [6]黄巍，张美凤.基于混合遗传算法的车间生产调度问题研究[J].计算机仿真，2009，26（10）：307-310. [7]邢晓敏.基于遗传算法的机器学习方法赋值理论研究[J].软件导刊[J].2009，8（11）：80-81. [8]蒋培.基于共同进化遗传算法的机器学习[J].湖南师范大学自然科学学报，2004，27（3）：33-38. [9]田莹，苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报，2007，12（3）：389-396. [10]周剑利，马壮，陈贵清.基于遗传算法的人工生命演示系统的研究与实现[J].制造业自动化，2009，31（9）：38-40. [11]刘晓莉，戎海武.基于遗传算法与神经网络混合算法的数据挖掘技术综述[J].软件导刊，2013，12（12）：129-130. 作者简介：赵夫群（1982，8-），女，汉族，籍贯：山东临沂，咸阳师范学院讲师，西北大学在读博士，工作单位：咸阳师范学院教育科学学院，研究方向：三维模型安全技术。 摘要：遗传算法是一种非常重要的搜索算法，特别是在解决优化问题上，效果非常好。文章首先介绍了遗传算法的四个组成部分，以及算法的基本操作步骤，接着探讨了遗传算法的几个主要应用领域，包括优化、生产调度、机器学习、图像处理、人工生命和数据挖掘等。目前遗传算法以及在很多方面的应用中取得了较大的成功，但是它在数学基础方面相对还不够完善，因而需要进一步研究和完善。 关键词：遗传算法；优化问题；数据挖掘 67 --

遗传算法求解函数极值C语言代码

#include "stdio.h" #include "stdlib.h" #include "conio.h" #include "math.h" #include "time.h" #define num_C 12 //个体的个数，前6位表示x1，后6位表示x2 #define N 100 //群体规模为100 #define pc 0.9 //交叉概率为0.9 #define pm 0.1 //变异概率为10% #define ps 0.6 //进行选择时保留的比例 #define genmax 2000 //最大代数200 int RandomInteger(int low,int high); void Initial_gen(struct unit group[N]); void Sort(struct unit group[N]); void Copy_unit(struct unit *p1,struct unit *p2); void Cross(struct unit *p3,struct unit *p4); void Varation(struct unit group[N],int i); void Evolution(struct unit group[N]); float Calculate_cost(struct unit *p); void Print_optimum(struct unit group[N],int k); /* 定义个体信息*/ typedef struct unit { int path[num_C]; //每个个体的信息 double cost; //个体代价值 }; struct unit group[N]; //种群变量group int num_gen=0; //记录当前达到第几代 int main() { int i,j; srand((int)time(NULL)); //初始化随机数发生器 Initial_gen(group); //初始化种群 Evolution(group); //进化：选择、交叉、变异 getch(); return 0; } /* 初始化种群*/ void Initial_gen(struct unit group[N]) { int i,j; struct unit *p; for(i=0;i<=N-1;i++) //初始化种群里的100个个体 {

遗传算法及其在TSP问题中的应用

遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机

遗传算法应用论文

论文 题目：遗传应用算法 院系：计算机工程系 专业：网络工程 班级学号： 学生姓名： 2014年10月23日

摘要: 遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处理复杂的非线性问题,因此有着广阔的应用前景。 关键词: 遗传算法; 化学计量学; 优化 THEORY AND APPL ICATION OF GENETIC AL GORITHM ABSTRACT: Genetic Algo rithm( GA) is a kind of recursive computational procedure based on the simulation of principle principles of evaluati on of living organisms in nature1Based on brief int roduction of the principle ,the beginning and development of the algorithms ,the pape r reviewed its applications in the fields of optimization ,fitting an d calibration,structure analysis and spectra interpretation variable selection ,and it s usage in combination with othersThe application o f GA needs no initiating knowledge of the system ,and therefore is a comprehensive optimization method with extensive application in terms of processing complex nonlinear problems。 KEY WORDS : Genetic Algorithm( GA) Chemometrics Optimization 遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法，它于1962年被提出，直到1989年才最终形成基本框架。遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 由美国J. H. Ho llad教授提出, 其主要特点是群体搜索策略和群体中个体之间的信息交换。该算法尤其适用于处理传统搜索方法难以解决的复杂和非线性问题, 可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。 顾名思义,遗传算法(Genetic Algorithm ,GA)是模拟自然界生物进化机制的一种算法 ,即遵循适者生存、优胜劣汰的法则 ,也就是寻优过程中有用的保留 ,无用的则去除。在科学和生产实践中表现为 ,在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法 ,即找出一个最优解。这种算法是 1960 年由

遗传算法基本理论实例

目录 _ 一、遗产算法的由来 (2) 二、遗传算法的国内外研究现状 (3) 三、遗传算法的特点 (5) 四、遗传算法的流程 (7) 五、遗传算法实例 (12) 六、遗传算法编程 (17) 七、总结 ......... 错误!未定义书签。附录一：运行程序.. (19)

遗传算法基本理论与实例 一、遗产算法的由来 遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。20世纪40年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型，以及模拟进化过程的算法进行了长期的开拓性的探索和研究。John H.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向。 遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。，直至消亡。达尔文把这一过程和现象叫做“自然选择，适者生存”。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的

遗传算法代码

%求下列函数的最大值% %f(x)=10*sin(5x)+7*cos(4x)x∈[0,10]% %将x的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为(10-0)/(2^10-1)≈0.01。% %将变量域[0,10]离散化为二值域[0,1023],x=0+10*b/1023,其中b是[0,1023]中的一个二值数。 %2.1初始化(编码) %initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)， %长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name:initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength));%rand随机产生每个单元为{0,1}行数为popsize，列数为chromlength的矩阵， %roud对矩阵的每个单元进行圆整。这样产生的初始种群。 %2.2计算目标函数值 %2.2.1将二进制数转化为十进制数(1) %遗传算法子程序 %Name:decodebinary.m %产生[2^n2^(n-1)...1]的行向量，然后求和，将二进制转化为十进制function pop2=decodebinary(pop) [px,py]=size(pop);%求pop行和列数 for i=1:py pop1(:,i)=2.^(py-i).*pop(:,i); end pop2=sum(pop1,2);%求pop1的每行之和 %2.2.2将二进制编码转化为十进制数(2) %decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置 %(对于多个变量而言，如有两个变量，采用20为表示，每个变量10为，则第一个变量从1开始，另一个变量从11开始。本例为1)， %参数1ength表示所截取的长度（本例为10）。 %遗传算法子程序 %Name:decodechrom.m