遗传算法

第1章遗传算法简介

遗传算法（Genetic Algorithm）起始于20世纪60年代，主要由美国Michigan大学的John Holland与其同事和学生研究形成了一个较完整的理论和方法。从1985年在美国卡耐基梅隆大学召开的第5届目标遗传算法会议（Intertional Conference on Genetic Algorithms:ICGA’85）到1997年5月IEEE的Transaction on Evolutionary Computation创刊，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究逐渐成熟。

1.1遗传算法的产生与发展（略）

1.2遗传算法概要

1.2.1生物进化理论和遗传算法的知识

遗传：

变异：亲代和子代之间，子代和子代的不同个体之间总有些差异，这种现象称为变异，变异是随即发生的，变异的选择和积累是生

命多样性的根源

生存斗争和适者生存：

下面给出生物学的几个基本概念知识，这对于理解遗传算法很重要。染色体：是生物细胞中含有的一种微小的丝状化合物，是遗传物质的主要载体，由多个遗传因子—基因组成。

遗传因子（gene）:DNA长链结构中占有一定位置的基本遗传单位，也称基因。生物的基因根据物种的不同而多少不一。

个体（individual）:指染色体带有特征的实体

种群（population）:染色体带有特征的个体的集合

进化（evolution）;生物在其延续生命的过程中，逐渐适应其生存环境使得其品质不断得到改良，这种生命现象称为进化。生物的

进化是以种群的形式进行的。

适应度（fitness）:度量某个物种对于生存环境的适应程度

选择（selection）:指以一定的概率从种群中选择若干个体的操作

复制(reproduction)

交叉(crossorer)

变异（musation）：复制时很小的概率产生的某些复制差错

编码（coding）:DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看成是从表现型到遗传子

型的映射。

解码（decoding）：从遗传子型到表现型的映射

1.2.2 遗传算法的基本思想

遗传算法是从代表问题可能潜在解集的一个种群开始的。该种群是由经过基因编码的一定数目的个体组成，这需要实现从表现型到基因型的映射即编码。初代种群产生之后，按照适者生存、优胜略汰的原理，逐代进化产生出越来越好的近似种，即在每一代中，根据问题域中个体适应度大小挑选个体，并借助自然遗传学的遗传算子进行组合交叉和变异，产生出代表解的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码可以作为问题近似最优解。

采用多种群即有子种群的算法往往会获得更好的结果。每个子种群像单种群遗传算法一样独立地演算若干代后，在子种群之间进行个体交换。这种多种群遗传算法更加贴近于自然界中种族的进化，称为并行遗传算法。

1.2.3遗传算法的特点

* 自组织，自学习，自适应性

* 本质并行性

*不需要求导或其他辅助知识，而只要影响搜索方向的目标函数和相应的适应度函数

*强调概率转换规则，而不是确定的转换规则

*对给定问题可产生许多的潜存种，最终选择可以由使用者确定，因此对于确认可替代解集而言是特别适合的。（如多目标优化问题）1.3遗传算法的基本操作

遗传算法包括三个基本操作：选择，交叉（基因重组），变异

这些基本操又有许多不同的地方。

1.选择

按比例的适应度算法（proportional fitness assigment）

基于排序的适应度算法（rank-based fitness assignment）

轮盘赌选择（roulette wheel selection）

随机遍历抽样（stochastic universal sampling）

局部选择（lacal selection）

截断选择（tournament selection）

2.交叉或基因重组（crossorer/recombination）

*实值重组（real value recombination）

离散重组（discrete ）、中间(intermediate)重组、线性(linear)

重组、扩展线性(extended linear)重组

*二进制交叉（binary valuel crossorer）

单点交叉、多点（multiple-poinrt）交叉、均匀(uniform)

交叉、洗牌(shuffle)交叉、缩小代理(crossover with reduced

surrogate)

3.变异（mutation）

变异实质上是子代基因按小概率扰动产生的变化，有两种算法，分别为实值变异和二进制变异

第二章基本遗传算法

2.1 一个简单的遗传算法实例

本节介绍一个简单的实例，来考察一下二进制算法的轮盘赌选择、多点交叉和变异操作，以便对遗传算法的基本过程和基本操作有所了解。

表1是一组二进制基因构成的个体组成的初始种群，个体适应度是由某种算法计算得到的。适应度越大代表这个个体越好。这里为了能够符合优胜略汰的原则，个体适应度按照比例转化为选择概率，进而得到累积概率

表1

轮盘赌选择方法类似于博彩游戏中的轮盘赌，将轮盘分成10个（即种群个体数目）扇区，并进行10次选择，从而产生10个[0,1]之间的随机书，图1的尖头表示被选中的染色体。

图1 轮盘赌选择

1到10代表染色体个体序号，扇区大小表示染色体选择概率的大小假设产生的随机数序列为0.070221，0.545929，0.784567，0.44693，0.507893，0.291198，0.71634，0.272901，0.371435，0.854641，将随机数序列与计算获得的累积概率比较，则依次序号为1，8，9，6，7，5，8，4，6，10个体被选中。显然适应度高的个体被选中的概率大，在第一次生存竞争中，序号为2 和3的个体被淘汰，代之以适应度高的个体8 和6，这个过程被称为再生（reproduction）

再生之后重要的遗传操作是交叉，这里仅以单点交叉为例。任意挑选经过选择操作后种群中的两个个体（该两个个体应是不同的）作为交叉对象，随机产生一个交叉点位置，将交叉点位置之右的部分基因进行交叉，如下图2

父个体1 1100000001

父个体2 0001010011

子个体1 1100000011

子个体2 0001010001

图2 单点交叉

如果只考虑交叉操作实现进化机制，在多数情况下是不行的，这与生物界近亲繁殖影响进化历程是类似的。因为种群的个体数是有限的，经过若干代交叉操作，源于一代较好祖先的子个体逐渐充斥整个种群，这样就会出现所谓早熟或过早收敛现象。这样最后获得的个体并非真正意义上的最优种群。为避免这种现象，有必要在进化过程中加入具有新遗传基因的个体，解决方法是模仿生物变异的遗传操作。对于二进制基因码组成的个体种群，实现基因码的小概率翻转，即可达到此目的，如图3（第四位由1翻转为0）

图3 变异

变异总是小概率的，即只有个别个体发生变异。其翻转的位置及翻转个数可以是随机的，有时也可以是固定的。

遗传算法的一般流程如图4所示

图4 基于遗传算法流程图

2.2 简单函数优化的实例

前一节所讲的实例是没有真正对象的，只是将遗传算法操作过程结合最简单的轮盘赌选择，单点交叉，单点小概率变异介绍了一下，使学生对遗传算法有一个概要了解，本节结合函数优化问题，使学生了解如何对问题实现编码和解码，如何产生初始种群，如何针对函数优化问题确定适应度函数，将遗传算法的操作全过程表示出来。

考虑下列一元函数求最大值的优化问题：

()sin(10*) 2.0[1,2]f x x x x π=+∈-

由于()f x 在[-1，2]可微，可用微分法先求出其最值：

()s i n (10)10c o s (10

f x x x x πππ'=+= 即

tan(10)10x x ππ=-

解得：

,

0,211,2......200211, 2...

20i i i i i x i x i x i εε-?=+=??=??+?=+=--? 式中(1,2....)i i ε=及i=-1,-2...

是一列接近于0的实数递减序列。

函数()sin(10*) 2.0f x x x π=+的曲线

最后得到

19191937 1.8520

x εε=+=+ 下面我们用遗传算法解决上述函数的最优问题（即求其最大值）

（1）编码

变量x 作为实数，可以视为遗传算法的表现形式。从表现型到

基因型的映射称为编码。通常采用二进制编码形式将某个变量值代表的个体表示为一个[0、1]二进制串。如果设定求解精确到6 位小数，由于区间长度为2-（-1）=3，必须将闭区间[-1，2]分为3*106等份。因为 2097152=221<3*106<=222=4194304

所以编码的二进制串长至少需要22 位

① 将一个二进制串（b 21b 20….b 0）2代表的二进制数化为10进制数：

21

212002100(b b ....b )(2)i i i b x ='==∑g

②x '对应的区间[-1，2]内的实数：

222(1)1.021x x --'=-+-g

串[0………0]和串[1……1]（每个里都是22个数）分别表示区间的两个端点值-1和2。

（2）产生初始种群

一个个体由串长为22的随机产生的二进制串组成染色体的基因码，我们可以产生一定数目的个体组成种群，种群的大小（规模）就是指种群中的个体数目。

（3）计算适应度

适应度大的个体其存活和被选中的概率大。适应度的计算就是对个体的计算，考虑到本例目标函数在定义域内均大于0，而且是求函数最大值，所以直接引用目标函数作为适应度函数：

()()f s f x = 例如x 1=0.637197通过编码得到的二进制串是

s 1=[1000101110110101000111]

这个串就是个体。个体的适应度就是

1111()()s i n (10)2.02.286345f s f x x x π==+= 这里我们选择种群数量为3 ，每个个体为：

s 1=[1000101110110101000111]

s 2=[0000001110000000010000]

s 3=[1110000000111111000101]

分别对应于数量值x 1=0.637197,x 2=-0.958973,x 3=1.627888,三个个体 的适应度计算如下；

1111()()sin(10) 2.0 2.286345f s f x x x π==+=

2233()() 1.078878

()() 3.250650f s f x f s f x ====

显然3 个个体中S 3的适应度最大，为最佳个体。

（4）遗传操作

下面是经过选择操作后的两个个体：

s 2=[0000 00111000000001000]

s 3=[1110 000000111111000101]

首先执行单点交叉， 随机选择一个交叉点，将之后的串交叉

2

S '=[00000 00000111111000101] 3

S '=[11100 01110000000010000] 这两个个体的适应度分别为：

2

3

()(0.998113) 1.940865()(1.666028) 3.459245f s f f s f '=-='== 可以发现2

S '的适应度比S 2和S 3都高。 （问题：这样选择选出种群中个体数目不是越来越少吗） 下面考察变异操作，假定已经以一小概率选择了S 3的第5个遗传 因子（即第5位）变异，遗传因子是由原来的0变为1，产生新的个 体3S '=[1110100000111111000101]，计算该个体的适应度

3

()(1.721638)0.917743f s f '== 可见该个体的适应度比它的父个体的适应度减小了，但如果选中第

10个遗传因子变异，产生新个体为3

S ''=[11100000001111111000101] 3

()(1.630818) 3.343555f s f ''== 又发现3

S ''的适应度比其父个体的适应度改善了。这说明变异操作的“扰动”作用。

（5）模拟结果

设定种群大小为50， 交叉概率P C =0.25，变异概率P m =0.01,按照上述的基本遗传算法，在进行到89代时获得最佳个体： S max =[1101001111110011001111]

X max =1.850549 f(x max )=3.850274

由于数学函数优化问题不需要专门领域的知识，且能较好的反映算法本身的实际效能，所以常用于 GA 的测试问题。下面四个为具有相当复杂度的常用测试函数：

1） Shubert 函数

}}55

1

122(,)cos[(1)1]cos[(1)1]0.5[( 1.42513)(0.80032)]i i f x y i i x i i y x y ==??=++++????++++∑∑

此函数有760个局部极小点，其中只有一个（-1.42513，-0.80032）为全局最小点，最小值为186.7309，自变量的取值范围-10

2） Camel 函数

42222(,)(4

2.1)(44)3x f x y x x x y y y =-+++-+ 此函数有6个局部极小点，其中有两个（-0.0898，0.7126）和(0.0898,-0.7126)为全局最小点，最小值为-1.031628，自变量的取值范围为-100

3）De Jones ’s F 5函数

25526111()0.02()

i j i ij i f x j x a ===++-∑∑

其中2253216016323216

01632()32323232321616323232ij a ?----??= ?-------??。 自变量取值范围为-65535

4） Shsffer ’s F 6函数

(,)0.5(10.001())f x y x y =-++

此函数有无限个局部极大点，其中只有一个（0，0）为全局最大，最大值为1。自变量的取值范围为-100

2.3遗传基因型

Holland 提出的遗传算法是采用二进制编码来表现个体遗传基因型的，它使用的编码符号集由二进制符号0和1组成，因此实际的遗传基因是一个二进制符号串，其优点在于编码、解码操作简单，交叉、变异等遗传操作便于实现，而且便于利用模式定理进行理论分析等。其缺点在于，不便于反映所求问题的特定知识，对于一些连续函数的优化问题，也由于遗传算法的随机特征而使得其局部搜索能力较差，对于一些多维、高精度要求的连续函数优化，二进制编码存在着连续函数离散化时的映射误差，个体编码串较短时，可能达不到精度要求；而个体编码较长时，虽然能提高精度，但却会使算法的搜索空间急剧扩大，造成遗传算法的性能降低。为提高遗传算法的局部搜索能力，后来又陆续产生了：格雷码（Gray Code ）等。为改善遗传算法的计算复杂性，提高算法效率提出了浮点码和符号编码。随着生物计算理论研究的兴起，有人提出DNA 编码法，并在模糊控制器优化

应用中取得很好的效果。

遗传算法的进化过程是建立在编码机制基础上的，编码技术对于算法性能如搜索能力和种群多样性等影响很大，例如二进制编码搜索能力强，而种群多样性弱，浮点编码则正好相反。二进制编码的种群稳定性比浮点编码差。

浮点编码对个体i t x 的第p 个基因进行变异操作

()()(0,)i i p D t t x p x N ψδ=+ （N 为高斯噪声）

可见浮点数编码操作的变量可以任意地小，这样可以保证只要变异量是足够的小，产生的新个体可以与父个体充分的接近。而二进制编码的变异操作不能保证父个体与新个体的充分接近，因此其种群稳定性比浮点差。

一个好的编码方法应具有下面9个特征：

！）完整性（completeness ）原则上，分布在所有问题域的解都可能被构造出来。

2）封闭性（closure ）每个基因编码对应一个可接受的个体，封闭性保证系统从不产生无效的个体。

3）紧致性（compactness ）若两种基因编码g 1和g 2都被解码成相同的个体，若g 1比g 2占的空间小，就认为g 1比g 2紧致。

4) 可扩展性（scalability）对于具体的问题，编码的大小确定了解码的时间，两者存在一定的函数关系，若增加一种表现型，作为基因的编码大小也相应增加。

5）多重性（multiplicity）多个基因解码成一个表现型，即从基因型到相应的表现型空间是多对一的关系，这是基因的多重性。若相同的基因型被解码成不同的表现型，这是表现型的多重性。

6）个体可塑性（flexibility）决定表现型与相应给定基因是受环境影响的。

7）模块性（modulatity）若表现型的构成中有多个重复的结构，在基因型编码中这种重复应当是避免的。

8）冗余性（redundancy）冗余性能够提高可靠性和鲁棒性

9）复杂性（complexity）包括基因型的结构复杂性，解码复杂性，计算时空复杂性（基因解码、适应值、再生等）

以上特性有时是相矛盾的。

2.4 适应度函数及其尺度变换

遗传算法在进化搜索中基本不利用外部信息，即以适应度函数（fitness function）为依据，利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换

而成的。 对目标函数值域的某种映射变换成为适应度的尺度变换（fitness scaling ）

1. 几种常见的适应度函数

① 直接以待求解的目标函数转化为适应度函数，即

若目标函数为最大化问题 Fit(f(x))=f(x)

若目标函数为最小化问题 Fit(f(x))=-f(x)

这种适应度函数简单、直观，但存在两个问题，其一是可能不满足常用的轮盘赌选择中的概率非负的要求；其二是某些待求解的函数在函数值分布上相差很大，因此得到的平均适应度可能不利于体现种群的平均性，影响算法的性能。

② 若目标函数为最小问题，则

max max (),()(())0

c f x f x c Fit f x -

式中max c 为f(x)的最大值估计。 反之，则min min

(),

()(())0f x c f x c Fit f x ->?=??其他

min c 为f(x)的最小值估计

这种方法是第一种方法的改进，称为“界限构造法”，但max c min c 的

构造与选择困难。

③ 若目标函数取为最小问题：

1(())0,()01()Fit f x c c f x c f x =≥+≥++

若目标函数为最大问题：

1

(())0,()01()Fit f x c c f x c f x =≥-≥+-

这种方法与2相似，c 为目标函数界限的保守估计值

2. 适应度函数的作用

在选择操作时会出现以下问题：

① 在遗传进化的初期，通常会产生一些超常的个体，若按照比例选择法，这些异常个体因竞争力太突出而控制了选择过程，影响算法的全局优化进程。

② 在遗传进化的后期，即算法接近收敛时由于种群中个体适应度较小时，继续优化的潜能降低，可能获得某个局部最优解。 上述问题我们称为遗传算法的欺骗问题。适应度函数设计不当有可能造成这种问题的出现。

3. 适应度函数的确定

主要满足以下条件：

① 单值、连续、非负、最大化

② 合理、一致性：要求适应度值反映对应解的优劣程度，这个条件的达成往往比较难以衡量

③ 计算量小

④ 通用性强：对某些具体问题，应尽可能通用

4. 适应度函数的尺度变换

1） 线性变换法：*f f αβ'=+

αβ和的确定有多种方法，但要满足以下条件：

① 原适应度的平均值要等于标定后的适应度平均值，以保证适

应度为平均值的个体在下一代的期望复制数为1，即

avg

avg f f '= ② 变换后的适应度最大值应等于原适应度平均值的最大倍数，以控制适应度最大的个体在下一代中的复制数。试验表明，指定倍数C mult 可在1.0-2.0范围内。即根据上述条件可确定

线性比例的系数：

max

mult avg f c f '=

4遗传算法与函数优化

第四章遗传算法与函数优化 4.1 研究函数优化的必要性： 首先，对很多实际问题进行数学建模后，可将其抽象为一个数值函数的优化问题。由于问题种类的繁多，影响因素的复杂，这些数学函数会呈现出不同的数学特征。除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解外，大部分情况下需要通过数值计算的方法来进行近似优化计算。 其次，如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题。这主要是因为现实问题种类繁多，影响因素复杂，若对各种情况都加以考虑进行试算，其计算工作量势必太大。由于纯数值函数优化问题不包含有某一具体应用领域中的专门知识，它们便于不同应用领域中的研究人员能够进行相互理解和相互交流，并且能够较好地反映算法本身所具有的本质特征和实际应用能力。所以人们专门设计了一些具有复杂数学特征的纯数学函数，通过遗传算法对这些函数的优化计算情况来测试各种遗传算法的性能。 4.2 评价遗传算法性能的常用测试函数 在设计用于评价遗传算法性能的测试函数时，必须考虑实际应用问题的数学模型中所可能呈现出的各种数学特性，以及可能遇到的各种情况和影响因素。这里所说的数学特性主要包括： ●连续函数或离散函数； ●凹函数或凸函数； ●二次函数或非二次函数； ●低维函数或高维函数； ●确定性函数或随机性函数； ●单峰值函数或多峰值函数，等等。 下面是一些在评价遗传算法性能时经常用到的测试函数： (1)De Jong函数F1： 这是一个简单的平方和函数，只有一个极小点f1(0, 0, 0)＝0。

(2)De Jong 函数F2： 这是一个二维函数，它具有一个全局极小点f 2(1，1) = 0。该函数虽然是单峰值的函数，但它却是病态的，难以进行全局极小化。 (3)De Jong 函数F3： 这是一个不连续函数，对于]0.5,12.5[--∈i x 区域内的每一个点，它都取全局极小值 30),,,,(543213-=x x x x x f 。

论文-遗传算法的基本步骤

遗传算法 遗传算法（Genetic Algorithm）是基于进化论的原理发展起来的一种广为应用，高效的随机搜索与优化的方法。它从一组随机产生的初始解称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，成为“染色体”是一串符号。这些染色体在每一代中用“适应度”来测量染色体的好坏, 通过选择、交叉、变异运算形成下一代。选择的原则是适应度越高,被选中的概率越大。适应度越低，被淘汰的概率越大。每一代都保持种群大小是常数。经过若干代之后，算法收敛于最好的染色体，它很可能是问题的最优解或次优解。这一系列过程正好体现了生物界优胜劣汰的自然规律。 比如有编号为1到10的特征，现在要选取其中的5个，基于遗传算法的特征选择可以如下这样直观的理解： 下续（表格） 下续……

即设有4个不同的初始特征组合，分别计算判别值，然后取最大的2个组合（[1,2,3,4,9]和[1,3,5,7,8]）进行杂交，即互换部分相异的特征（4和7），得到新的两个特征组合（[1,2,3,7,9]和[1,3,4,5,8]）,然后再计算这两个新的组合的判别值，和原来的放在一起，再从中选择2个具有最大判别值的组合进行杂交。如此循环下去，在某一代的时候就得到了一个最好的特征组合（比如第2代的[1,3,5,7,9]的特征组合）。当然，在实际中每代的个体和杂交的数量是比较大的。 遗传算法的具体的步骤如下：

1.编码：把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。为了减少组合数量，在图像中进行分块（比如5*5大小的块），然后再把每一块看成一个基因进行组合优化的计算。每个解的基因数量是要通过实验确定的。 2.初始群体（population）的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。N个个体，构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。这个参数N需要根据问题的规模而确定。 3.交换(crossover)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。由交换概率( P)挑选的每两个父代 c 通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体。可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。这个判据的选取是GA的关键所在。

遗传算法

基于新的混合遗传算法的订单生产工序顺序相关的流水车 间调度问题研究 A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem Mohammad Mirabi ?S. M. T. Fatemi Ghomi ?F. Jolai 2013年5月29号收到该文献,2014年3月18号录取,2014年4月9日出版.作者（2014）.这篇文章在开放存取的https://www.doczj.com/doc/806576364.html, 网站发表 摘要流水车间调度问题（FSP）用于处理m台机器n个工序的流水作业。尽管FSP是典 型的NP-hard问题，依然没有有效的算法以找到这个问题的最优解。为了减少库存，延迟和安装成本,在工作时间一定,序列相关的每台机器上解决流水车间调度排序问题，在这提出了一种有三个遗传算子的新型混合遗传算法（HGA）。该算法应用一种改进的方法来生成初始种群，并使用一种应用迭代交换过程改进初始解的改进启发式算法。我们认为订单式生产方式，工序间隔时间是基于最大安装成本的禁忌搜索算法的解。此外，与最近开发的启发式算法通过计算实验结果比较表明，该算法在解\的精度和效率方面表现出非常强的竞争力。 关键词:混合遗传算法流水作业调度序列相关 引言 流车间调度问题（FSP）作为在制造业研究的主要问题已经近七十年。在一个有M台机器的流水作业车间中有m个工位,每个工序又有一台或几台机器。此外，有n个工件在m个工位上依次加工。在经典的流水作业问题里，每个工位都有一台机器，这一领域的研究吸引了最多的人次。FSP的两个主要子问题是序列独立时间设置（SIST）和顺序相关时间设置（SDST）。SDST流水作业问题更具有现实意义，但是吸引的注意力却少得多，特别是2000年以前（Allahverdi等，2008） 在流水车间调度问题的目标是找到一个序列的机器加工的作业，以便一个给定的标准进行了优化。这里有n个工件在每台机器上操作的可能的顺序，以及（N！）*M个的可能处理顺序。流水作业调度的研究通常只参加置换序列，其中操作的处理顺序是所有机器。在这里，我们也采用这种限制。 最小化所有最大完工时间作业（成为完工期并通过的Cmax表示）是公知的，也是在文献M. Mirabi (&) Group of Industrial Engineering, Ayatollah Haeri University of Meybod, P.O. Box 89619-55133, Meybod, Iran e-mail: M.Mirabi@https://www.doczj.com/doc/806576364.html, S. M. T. Fatemi Ghomi Department of Industrial Engineering, Amirkabir University of Technology, P.O. Box 15916-34311, Tehran, Iran e-mail: Fatemi@aut.ac.ir F. Jolai Department of Industrial Engineering, College of Engineering, University of Tehran, P.O. Box 14395-515, Tehran, Iran

遗传算法

遗传算法发展前景概况 （华北电力大学电气与电子工程学院，北京102206） 摘要：遗传算法是一种基于生物进化自然选择和群体遗传机理的，适合于复杂系统优化的自适应概率优化技术，近年来，因为遗传算法求解复杂优化问题的巨大潜力和在工业工程领域的成功应用，这种算法受到了国内外学者的广泛关注，本文介绍了遗传算法研究现状和发展的前景，概述了它的理论和技术，并对遗传算法的发展情况发表了自己的看法。 关键词：遗传算法; 遗传算子；进化计算；编码 GENERAL GENETIC ALGORITHM DEVELOPMENT PROSPECT (North China Electric Power University Electrical And Electronic Engineering Institute,Beijing102206) ABSTRACT: Genetic algorithm is a kind of natural selection and based on biological evolution of genetic mechanism, group suitable for complex system optimization adaptive probability optimization technique, in recent years, because genetic algorithm for solving complex optimization problem in the huge potential and the successful application of industrial engineering, this algorithm was wide attention of scholars at home and abroad, this paper introduces the current research status and development of genetic algorithm, summarizes the prospect of its theory and technology of genetic algorithm and the development of published opinions of his own. KEY WORD: Genetic algorithm; Genetic operator; Evolutionary computation; coding 1.引言 现在，遗传算法正在迅速发展，遗传算法与其很强的解决问题能力和适合于复杂系统的自适应优化技术渗透到研究和工业工程领域，在电力系统，系统辨识,最优控制，模式识别等领域有了很广泛的应用，取得了很好的效果。 2.遗传算法基本思想 遗传算法是建立在自然选择和群体遗传学基础上的随机，迭代和进化，具有广泛适用性的搜索方法，所有的自然种类都是适应环境而生存，这一自然适用性是遗传算法的主要思想。 遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，其内部基因决定了个体的外部表现。因此，在一开始就要实现外部表现到内部基因的映射，即编码工作，通常采用二进制码。初始种群产生之后，按照适者生存和优胜劣汰的原则，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小选择个体，并借助自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集和种群，这种过程将导致种群像自然进化那样产生比前代更适应于环境的后代种群，末代种群中的最有个体经过解码，可以作为问题近似最优解。 遗传算法采纳了自然进化模型，如选择，交叉，变异等，计算开始时，种群随机初始化产生一定数目的N个个体，并计算每个个体的适应度函数，如果不满足优化准则，就开始新一代的计算。为了产生下一代，按照适应度选择个体父代进行基因重组二产生子代。所有的子代按一定的概率进行变异，子代取代父代构成新一代，然后重新计算子代的适应度。这一过程循环执行，直到满足优化准则为止。 3.遗传算法基本操作

AI人工智能的几种常用算法概念

一、粒子群算法 粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩写为PSO，是近年来发展起来的一种新的进化算法(（Evolu2tionary Algorithm - EA）。PSO 算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的交叉(Crossover) 和变异(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。 优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题.为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度.爬山法精度较高,但是易于陷入局部极小.遗传算法属于进化算法(EvolutionaryAlgorithms)的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解.遗传算法有三个基本算子:选择、交叉和变异.但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.1995年Eberhart博士和kennedy博士提出了一种新的算法;粒子群优化(ParticalSwarmOptimization-PSO)算法.这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性. 粒子群优化(ParticalSwarmOptimization-PSO)算法是近年来发展起来的一种新的进化算法(Evolu2tionaryAlgorithm-EA).PSO算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价

遗传算法经典MATLAB代码

遗传算法经典学习Matlab代码 遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。 对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法 % % 求下列函数的最大值 % % 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^n 2^(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世纪40年代，就有学者开始研究利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。 早期的研究特点是侧重于对一些复杂操作的研究。最早意识到自然遗传算法可以转化为人工智能算法的是J.H.Hnllaad教授。1965年，Holland教授首次提出了人工智能操作的重要性，并将其应用到自然系统和人工系统中。1967年，Holland教授的学生.J.D.Bagley在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文，从而创立了自适应遗传算法的概念e J.D.Bagley发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。1970年，Cavicchio把遗传算法应用于模式识别。Holistien最早把遗传算法应用于函数优化。20世纪70年代初，Holland 教授提出了遗传算法的基本定理—模式定理，从而奠定了遗传算法的理论基础。模式定理揭示出种群中优良个体(较好的模式)的样本数将以指数级规律增长，因而从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程。1975年，Holland教授出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性》。同年，K.A.De Song在博士论文《遗传自适应系统的行为分析》‘护结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，为遗传算法及其应用打下了坚实的基础，他所得

出的许多结论迄今仍具有普遍的指导意义。20世纪80年代，Hntland 教授实现了第一个基于遗传算法的机器学习系统—分类器系统(Classifier Systems，简称CS)，提出了基于遗传算法的机器学习的新概念，为分类器系统构造出了一个完整的框架。1989年，D.J.Goldberg 出版了专著—《搜索、优化和机器学习中的遗传算法》。该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。可以说这本书奠定了现代遗传算法的科学基础，为众多研究和发展遗传算法的学者所瞩目。1991年，L,Davis编辑出版了《遗传算法手册》一书，书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用样本，为推广和普及遗传算法的应用起到了重要的指导作用。1992年，J.R.Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传规划(Genetic Programming,简称GP)的概念。

遗传算法的计算性能的统计分析

第32卷 第12期2009年12月 计 算 机 学 报 CH INESE JOURNA L OF COMPU TERS Vol.32No.12 Dec.2009 收稿日期:2008210219;最终修改稿收到日期:2009209227.本课题得到国家自然科学基金(60774084)资助.岳 嵚,男,1977年生,博士研究生,主要研究方向为进化算法.E 2mail:yueqqin@si https://www.doczj.com/doc/806576364.html,.冯 珊,女,1933年生,教授,博士生导师,主要研究领域为智能决策支持系统. 遗传算法的计算性能的统计分析 岳 嵚 冯 珊 (华中科技大学控制科学与工程系 武汉 430074) 摘 要 通过对多维解析函数的多次重复计算并对计算结果进行统计分析来讨论遗传算法的可靠性和可信度,结果表明:遗传算法的计算结果具有一定的稳定性,可以通过采用多次重复计算的方法提高计算结果的可信度,并用以评价算法及其改进的实际效果.关键词 遗传算法;计算可靠性;置信区间 中图法分类号TP 18 DOI 号:10.3724/SP.J.1016.2009.02389 The Statistical Analyses for Computational Performance of the Genetic Algorithms YU E Qin FENG Shan (Dep artment of Contr ol Science and Eng ineering ,H uazhong University of Science and T ech nology ,W u han 430074) Abstr act In this paper,the author s discuss the reliability of the GAs by reiteratively computing the multi 2dimensional analytic functions and statistical analysis of the results.The analysis re 2sults show that the GAs have certain stability;it could improve the reliability by reiteratively computation and estimates the effects of improvements. Keywor ds genetic algorithms;computational stability;confidence interval 1 遗传算法的随机性 遗传算法是将生物学中的遗传进化原理和随机优化理论相结合的产物,是一种随机性的全局优化算法[1].遗传算法作为一种启发式搜索算法,其计算结果具有不稳定性和不可重现性;遗传算法的进化过程具有有向随机性,整体上使种群的平均适应度不断提高.现在学术界对遗传算法中的某些遗传操作的作用机制还不十分清楚,遗传算法的许多性能特点无法在数学上严格证明.遗传算法的计算过程会受到各种随机因素的影响,如随机产生的初始种群和随机进行的变异操作等,尤其初始种群对计算结果影响较大.但另一方面,大量的实算结果表明,遗传算法的计算结果具有一定的规律性,在统计意义上具有一定的可靠性,这样就可以对待求解问题 进行多次重复计算后取平均值的方法,提高遗传算 法在实际计算中的准确性和可信度. 包括遗传算法在内的启发式搜索算法主要用于解决大型的复杂优化问题,这些问题一般难以使用传统的优化算法解决.遗传算法对这类问题的计算结果也难达到精确的最优解.这给对用遗传算法解决实际工程优化问题的计算结果的评价带来了困难,在实际工程计算中也难以评价遗传算法及其改进型的计算效果的优劣. 为了分析遗传算法的计算性能,本文采用的计算对象是一个复杂的多维解析函数.使用这类函数评价遗传算法计算性能的好处是可以事先通过其他方法求得最优解,这样便于评价遗传算法及其改进型的计算效果.本文从统计学角度对多次重复计算的结果进行分析,试图得到遗传算法的稳定性和可信度方面的相关结论,通过分析遗传算法及其改进

三个遗传算法matlab程序实例

遗传算法程序（一）: 说明: fga.m 为遗传算法的主程序; 采用二进制Gray编码,采用基于轮盘赌法的非线性排名选择, 均匀交叉,变异操作,而且还引入了倒位操作! function [BestPop,Trace]=fga(FUN,LB,UB,eranum,popsize,pCross,pMutation,pInversion,options) % [BestPop,Trace]=fmaxga(FUN,LB,UB,eranum,popsize,pcross,pmutation) % Finds a maximum of a function of several variables. % fmaxga solves problems of the form: % max F(X) subject to: LB <= X <= UB % BestPop - 最优的群体即为最优的染色体群 % Trace - 最佳染色体所对应的目标函数值 % FUN - 目标函数 % LB - 自变量下限 % UB - 自变量上限 % eranum - 种群的代数,取100--1000(默认200) % popsize - 每一代种群的规模；此可取50--200(默认100) % pcross - 交叉概率,一般取0.5--0.85之间较好(默认0.8) % pmutation - 初始变异概率,一般取0.05-0.2之间较好(默认0.1) % pInversion - 倒位概率,一般取0.05－0.3之间较好(默认0.2) % options - 1*2矩阵,options(1)=0二进制编码(默认0),option(1)~=0十进制编 %码,option(2)设定求解精度(默认1e-4) % % ------------------------------------------------------------------------ T1=clock; if nargin<3, error('FMAXGA requires at least three input arguments'); end if nargin==3, eranum=200;popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==4, popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==5, pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==6, pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==7, pInversion=0.15;options=[0 1e-4];end if find((LB-UB)>0) error('数据输入错误,请重新输入(LB

遗传算法实验报告

遗传算法实验报告 专业：自动化姓名：张俊峰学号：13351067 摘要：遗传算法，是基于达尔文进化理论发展起来的一种应用广泛、高效的随机搜索与优化方法。本实验利用遗传算法来实现求函数最大值的优化问题，其中的步骤包括初始化群体、个体评价、选择运算、交叉运算、变异运算、终止条件判断。该算法具有覆盖面大、减少进入局部最优解的风险、自主性等特点。此外，遗传算法不是采用确定性原则而是采用概率的变迁规则来指导搜索方向，具有动态自适应的优点。 关键词：串集最优化评估迭代变异 一：实验目的 熟悉和掌握遗传算法的运行机制和求解的基本方法。 遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下： （1）随机产生一个确定长度的特征字符串组成的初始种群。。 （2）对该字符春种群迭代地执行下面的步骤a和步骤b，直到满足停止准则为止： a计算种群中每个个体字符串的适应值； b应用复制、交叉和变异等遗传算子产生下一代种群。 （3）把在后代中表现的最好的个体字符串指定为遗传算法的执行结果，即为问题的一 个解。 二：实验要求 已知函数y=f（x 1,x 2 ,x 3 ,x 4 ）=1/(x 1 2+x 2 2+x 3 2+x 4 2+1),其中-5≤x 1 ,x 2 ,x 3 ,x 4 ≤5, 用遗传算法求y的最大值。三：实验环境

操作系统：Microsoft Windows 7 软件：Microsoft Visual studio 2010 四：实验原理与步骤 1、遗传算法的思想 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体极为P（t），进过一代遗传和进化后，得到第t+1代群体，他们也是由多个个体组成的集合，记做P（t+1）。这个群体不断地经过遗传和进化操作，并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现性X将达到或接近于问题的最优解。 2、算法实现步骤 ①、产生初始种群：产生初始种群的方法通常有两种：一种是完全随机的方法产生的，适合于对问题的解无任何先验知识的情况；另一种是将某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选择样本，t=0,随机产生n个个体形成一个初始群体P（t），该群体代表优化问题的一些可能解的集合； ②适应度评价函数：按编码规则，将群体P（t）中的每一个个体的基因码所对应的自变量取值代入目标函数，算出其函数值f，i=1,2,…,n,f越大，表示该个体有较高的适应度，更适合于f所定义的生存环境，适应度f为群体进化提供了依据； ③选择：按一定概率从群体P（t）中选出m个个体，作为双亲用于繁殖后代，产生新的个体加入下一个群体P（t+1）中。此处选用轮盘算法，也就是比例选择算法，个体被选择的概率与其适应度成正比。 ④交叉（重组）：对于选中的用于繁殖的每一个个体，选择一种交叉方法，产生新的个体；此处采取生成随机数决定交叉的个体与交叉的位置。 ⑤变异：以一定的概率Pm从群体P（t+1）中随机选择若干个个体，对于选中的个体随机选择某个位置，进行变异； ⑥对产生新一代的群体返回步骤③再进行评价，交叉、变异如此循环往复，使群体中个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高，则迭代过程收敛，算法结束。 五：实验结果 实验结果的显示取决于判断算法终止的条件，这里可以有两种选择：1、在程序中设定迭代的次数；2在程序中设定适应值。本实验是在程序中实验者输入需要迭代的次数来判断程序终结的。

遗传算法的计算性能的统计分析

遗传算法遗传算法的计算性能的统计分析 岳嵚冯珊 （华中科技大学控制科学与工程系） 摘要：本文通过对多维解析函数的多次重复计算并对计算结果的进行统计分析来讨论遗传算法的可靠性和可信度，结果表明：遗传算法的计算结果具有一定的稳定性，可以通过采用多次重复计算的方法提高计算结果的可信度，并用以评价算法及其改进的实际效果。 关键词：遗传算法；计算可靠性；置信区间 分类号：TP18 1遗传算法的随机性 遗传算法是将生物学中的遗传进化原理和随机优化理论相结合的产物，是一种随机性的全局优化算法[1]。遗传算法作为一种启发式搜索算法，其计算结果具有不稳定性和不可重现性；遗传算法的进化过程具有有向随机性，整体上使种群的平均适应度不断提高。现在学术界对遗传算法中的某些遗传操作的作用机制还不十分清楚，遗传算法的许多性能特点无法在数学上严格证明。遗传算法的计算过程会受到各种随机因素的影响，如随机产生的初始种群和随机进行的变异操作等，尤其初是始种群对计算结果影响较大。但另一方面，大量的实算结果表明，遗传算法的计算结果具有一定的规律性，在统计意义上具有一定的可靠性，这样就可以对待求解问题进行多次重复计算后取平均值的方法，提高遗传算法在实际计算中的准确性和可信度。 包括遗传算法在内的启发式搜索算法主要用于解决大型的复杂优化问题，这些问题一般难以使用传统的优化算法解决。遗传算法对这类问题的计算结果也难达到精确的最优解。这给对用遗传算法解决实际工程优化问题的计算结果的评价带来了困难，在实际工程计算中也难以评价遗传算法及其改进型的计算效果的优劣。 为了分析遗传算法的计算性能，本文采用的计算对象是一个复杂的多维解析函数。使用这类函数评价遗传算法计算性能的好处是可以事先通过其他方法求得最优解，这样便于评价遗传算法及其改进型的计算效果。本文从统计学角度对多次重复计算的结果进行分析，试图得到遗传算法的稳定性和可信度方面的相关结论，通过分析遗传算法及其改进型求解解析问题的计算效果，再把所得到的相关结论推广应用到复杂的工程实际问题中去。 遗传算法在实际使用中有多种形式的变型，经典遗传算法是遗传算法的最简单的形式，但是经典遗传算法并不理想。本文使用的是粗粒度并行遗传算法。粗粒度并行遗传算法是遗传算法的一个重要改进型。它具有比经典遗传算法更好的计算性能。 2算例、实验方法和实验结果 2.1算例 本文所使用的算例是Deb 函数： ]10,10[,)]4cos(10[10)(12?∈??+=∑=i n i i i Deb x n x x x f i π（1） Deb 函数是一个高维的非凸函数，该函数在点（9.7624，9.7624，…，9.7624）上取得最大

最新最全的遗传算法工具箱及说明

最新最全的遗传算法工具箱Gaot_v5及说明 Gaot_v5下载地址：https://www.doczj.com/doc/806576364.html,/mirage/GAToolBox/gaot/gaotv5.zip 添加遗传算法路径： 1、 matlab的file下面的set path把它加上，把路径加进去后在 2、 file→Preferences→General的Toolbox Path Caching里点击update Toolbox Path Cache更新一下，就OK了

遗传算法工具箱Gaot_v5包括许多实用的函数，各种算子函数，各种类型的选择方式，交叉、变异方式。这些函数按照功能可以分成以下几类：

主程序 ga.m提供了 GAOT 与外部的接口。它的函数格式如下： [x endPop bPop traceInfo]=ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps, selectFn,selectOps,xOverFNs,xOverOps,mutFNs,mutOps) 输出参数及其定义如表 1 所示。输入参数及其定义如表 2 所示。 表1 ga.m的输出参数 输出参数 定义 x 求得的最好的解，包括染色体和适应度 endPop 最后一代染色体（可选择的） bPop 最好染色体的轨迹（可选择的） traceInfo 每一代染色体中最好的个体和平均适应度（可选择的） 表2 ga.m的输入参数 表3 GAOT核心函数及其它函数

核心函数： (1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始种群的生成函数 【输出参数】 pop--生成的初始种群 【输入参数】 num--种群中的个体数目 bounds--代表变量的上下界的矩阵 eevalFN--适应度函数 eevalOps--传递给适应度函数的参数 options--选择编码形式(浮点编码或是二进制编码)[precision F_or_B],如 precision--变量进行二进制编码时指定的精度 F_or_B--为1时选择浮点编码，否则为二进制编码,由precision指定精度) (2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,... termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)--遗传算法函数 【输出参数】 x--求得的最优解 endPop--最终得到的种群 bPop--最优种群的一个搜索轨迹 【输入参数】

GA遗传算法概述

遗传算法及其应用 摘要：遗传算法是一种基于生物自然选择和遗传机理的随机搜索与优化方法。近年来,由于遗传算法在求解复杂问题中的巨大潜力及其在工业工程领域的成功应用,受到了国内外学者的广泛关注。本文详细介绍了遗传算法的基本原理、主要特征以及主要应用。 关键词：遗传算法；选择算子；交叉算子；变异算子 Genetic Algorithm and Its Application Abstract: Genetic algorithm is a random search and optimization method based on biological natural selection and genetic mechanism. In recent years,genetic algorithm has attracted many domestic and overseas scholars' attention for its potential in solving many complex problems and its successful application in the field of industrial engineering, This paper introduces the basic principle ,the main characteristics and applications of genetic algorithm in detail. Key words: genetic algorithm, selection operator, crossover operator, mutation operator 1.遗传算法发展历史 1967年，Holland的学生Bagley在其博士论文中首次提出“遗传算法”[1]。1970年，Cavicchio把遗传算法应用于模式识别[2]。Hollstien最早把遗传算法应用于函数优化[3]。20世纪70年代，Holland教授提出了遗传算法的基本定理—模式定理[4]，从而奠定了遗传算法的理论基础。1975年，Holland教授出版了第一本系统论述遗传算法和人工自适应系统的专著《Adaptation in Natural and Artificial Systems》。同年，K.A.De Song在博士论文《遗传自适应系统的行为分析》结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，为遗传算法及其应用打下了坚实的基础，他所得出的许多结论迄今仍具有普遍的指导意义。 2.遗传算法理论 2.1遗传算法的基本思想 遗传算法借鉴Darwin 的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传的机理。与传统搜索算法不同，遗传算法从一组随机产生的初始解（称为群体）开始。群体中的每个个体是问题的一个解，称为“染色体”，这些染色体在后代迭代过程中不断进化。遗传算法主要通过选择、交叉和变异来实现,其本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。 遗传算法是一个迭代的过程，在每次迭代过程中都保留一组候选解，按解的好坏进行排序，按照约束条件从中选取一组解，利用遗传算法中的三个算子对其进行计算，产生新一代的候选解，重复此过程直到满足某种收敛条件为止。 2.2遗传算法的数学基础 定义1：模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集（0,1，*）的字符串，符号*代表（0,1）中的任意字符。例如：10**1 定义2：模式H中确定位置的个数称为模式H的阶，记O(H)。例如O(10**1)=3。 定义3：模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距，记作δ(H)。例如δ(10**1)=4。 模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的

人工智能之遗传算法论文含源代码

30维线性方程求解 摘要：非线性方程组的求解是数值计算领域中最困难的问题，大多数的数值求解算法例如牛顿法的收敛性和性能特征在很大程度上依赖于初始点。但是对于很多高维的非线性方程组，选择好的初始点是一件非常困难的事情。本文采用了遗传算法的思想，提出了一种用于求解非线性方程组的混合遗传算法。该混合算法充分发挥了遗传算法的群体搜索和全局收敛性。选择了几个典型非线性方程组，考察它们的最适宜解。 关键词：非线性方程组；混合遗传算法；优化 1. 引言遗传算法是一种通用搜索算法，它基于自然选择机制和自然遗传规律来模拟自然界的进化过程，从而演化出解决问题的最优方法。它将适者生存、结构化但同时又是 随机的信息交换以及算法设计人的创造才能结合起来，形成一种独特的搜索算法，把一些解决方案用一定的方式来表示，放在一起成为群体。每一个方案的优劣程度即为适应性，根据自然界进化“优胜劣汰”的原则，逐步产生它们的后代，使后代具有更强的适应性，这样不断演化下去，就能得到更优解决方案。 随着现代自然科学和技术的发展，以及新学科、新领域的出现，非线性科学在工农业、经济政治、科学研究方面逐渐占有极其重要的位置。在理论研究和应用实践中，几乎绝大多数的问题都最终能化为方程或方程组，或者说，都离不开方程和方程组的求解。因此，在非线性问题中尤以非线性方程和非线性方程组的求解最为基本和重要。传统的解决方法，如简单迭代法、牛顿法、割线法、延拓法、搜索法、梯度法、共轭方向法、变尺度法，无论从算法的选择还是算法本身的构造都与所要解决的问题的特性有很大的关系。很多情况下,算法中算子的构造及其有效性成为我们解决问题的巨大障碍。而遗传算法无需过多地考虑问题的具体形式，因为它是一种灵活的自适应算法，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效。而且，遗传算法是一种高度并行的算法，且算法结构简单，非常便于在计算机上实现。本文所研究的正是将遗传算法应用于求解非线性方程组的问题。 2. 遗传算法解非线性方程组为了直观地观察用遗传算法求解非线性方程组的效果，我们这里用代数非线性方程组作为求解的对象问题描述：非线性方程组指的是有n 个变量（为了简化讨论，这里只讨论实变量方程组）的方程组 中含有非线性方程。其求解是指在其定义域内找出一组数能满足方程组中的每 个方程。这里，我们将方程组转化为一个函数则求解方程组就转化为求一组值使得成立。即求使函数取得最小值0 的一组数，于是方程组求解问题就转变为函数优化问题 3. 遗传算子 遗传算子设计包括交叉算子、变异算子和选择算子的设计。