遗传算法理论与应用

遗传算法理论与应用

遗传算法(genetic algorithms, GA)是人工智能的重要新分支，是基于达尔文进化论，在微型计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存、优胜劣汰等自然进化规则来进行搜索计算和问题求解。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。遗传算法对许多用传统数学难以解决或明显失效的非常复杂问题，特别是最优化问题，GA提供了一个行之有效的新途径。

一.遗传算法的发展

遗传算法起源于对生物系统所进行的计算机模拟研究。早在20世纪40年代，就有学者开始如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入60年代后，美国密执安大学的Holland教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术——遗传算法。下面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡献。

1.J．H．Holland

20世纪60年代，Holland认识到了生物的遗传和自然进化现象与人工自适应系统的相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。

70年代，Holland教授提出了遗传算法的基本定理——模式定理(Schema Theorem)，从而奠定了遗传算法的理论基础。模式定理揭示出了群体中的优良个体(较好的模式)的样本数将以指数级规律增长，因而从理论上保证了遗传算法是一个可以用来寻找最优可行解的优化过程。1975年，Holland出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性(Adaptation in Natural and Artificial Systems)》。

80年代，Holland教授实现了第一个基于遗传算法的机器学习系统——分类器系统(Classifier Systems，简称CS)，开创了基于遗传算法的机器学习的新概念，为分类器系统构造出了一个完整的框架。

2.J．D．Bagley

1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。这些都与目前遗传算法中所使用的算子和方法相类似。他还敏锐地意识到了在遗传算法执行的不同阶段可以使用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创立了自适应遗传算法的概念。

3.K．A．De Jong

1975年，De Jong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。例如，对于规模在50~100的群体，经过10~20代的进化，遗传算法都能以很高的概率找到最优或近似最优解。他推荐了在大多数优化问题中都较适用的遗传算法的参数，还建立了著名的De Jong五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。

4.D．J．Goldberg

1989年，Goldberg出版了专著《搜索、优化和机器学习中的遗传算法(Genetic Algorithms

in Search, Optimization and Machine Learning)》。该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。可以说这本书奠定了现代遗传算法的科学基础，为众多研究和发展遗传算法的学者所瞩目。

5.L ．Davis

1991年，Davis 编辑出版了《遗传算法手册(Handbook of Genetic Algorithms)》一书，书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实例。这本书为推广和普及遗传算法的应用起到了重要的指导作用。

6.J ．R ．Koza

1992年，Koza 将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(Genetic Programming ，简称GP)的概念。他将一段LISP 语言程序作为个体的基因型，把问题的解编码为一棵树，基于遗传和进化的概念，对由数组成的群体进行遗传运算，最终自动生成性能较好的计算机程序。Koza 成功地把他提出的遗传编码的方法应用于人工智能、机器学习、符号处理等方面。

二．遗传算法的原理和特点

遗传算法将生物进化原理引入待优化参数形成的编码串群体中，按着一定的适值函数及一系列遗传操作对各个个体进行筛选，从而使适值高的个体被保留下来，组成新的群体，新群体包含上一代的大量信息，并且引入了新的优于上一代的个体。这样周而复始，群体中各个体适值不断提高，直至满足一定的极限条件。此时，群体中适值最高的个体即为待优化参数的最优解。正是由于遗传算法独具特色的工作原理，使它能够在复杂空间进行全局优化搜索，并且具有较强的鲁棒性；另外，遗传算法对于搜索空间，基本上不需要什么限制性的假设（如连续、可微及单峰等）。

同常规优化算法相比，遗传算法有如下特点：

（1）遗传算法是对参数的编码进行操作，而非对参数本身。遗传算法首先基于一个有限的字母表，把最优化问题的自然参数集编码为有限长度的字符串。例如，一个最优化问题：在整数区间[0,31]上求函数2

()f x x 的最大值。若采用传统方法，需不断调节x 参数的取值，直至得到最大的函数值为止。而采用遗传算法，优化过程的第一步是把参数x 编码为有限长度的字符串，常用二进制字符串，设参数x 的编码长度为5，“00000”代表0，“11111”代表31，区间[0,31]上的数与二进制编码之间采用线性映射方法；随机生成几个这样的字符串组成初始群体，对群体中的字符串进行遗传操作，直至满足一定的终止条件；求得最终群体中适值最大的字符串对应的十进制数，其相应的函数值则为所求解。可以看出，遗传算法是对一个参数编码群体进行操作，这样提供的参数信息量大，优化效果好。

（2）遗传算法是从许多点开始并行操作，并非局限于一点，从而可有效防止搜索过程收敛于局部最优解。

（3）遗传算法通过目标函数计算适值，并不需要其他推导和附加信息，因而对问题的依赖性较小。

（4）遗传算法的寻优规则是由概率决定的，而非确定性的。

（5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索。 （6）遗传算法对所求解的优化问题没有太多的数学要求。由于它的进化特性，它在解的搜索中不需要了解问题的内在性质。遗传算法可以处理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的，甚至是混合的搜索空间。

（7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度。

三．遗传算法的应用

遗传算法提供了一种求解复杂杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域：

（1）函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。

（2）组合优化。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。

（3）生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。

（4）自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。

（5）机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。

（6）图像处理。图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地，目前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。

（7）人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。

（8）遗传编程。Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。

（9）机器学习。学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。

四．遗传算法的基本遗传学基础

遗传算法是根据生物进化的模型提出的一种优化算法。自然选择学说是进化论的中心内容，根据进化论，生物的发展进化主要由三个原因，即遗传、变异和选择。

遗传是指子代总是和亲代相似。遗传性是一切生物所共有的特性，它使得生物能够把它的特性、性状传给后代。遗传是生物进化的基础。

变异是指子代和亲代有某些不相似的现象，即子代永远不会和亲代完全一样。它是一切生物所具有的共有特性，是生物个体之间相互区别的基础。引起变异的原因主要是生活环境的影响、器官使用的不同及杂交。生物的变异性为生物的进化和发展创造了条件。

选择是指具有精选的能力，它决定生物进化的方向。在进化过程中，有的要保留，有的要被淘汰。自然选择是指生物在自然界的生存环境中适者生存，不适者被淘汰的过程。通过不断的自然选择，有利于生存的变异就会遗传下去，积累起来，使变异越来越大，逐步产生了新的物种。

生物就是在遗传、变异和选择三种因素的综合作用过程中，不断地向前发展和进化。选择是通过遗传和变异起作用的，变异为选择提供资料，遗传巩固与积累选择的资料，而选择则能控制变异与遗传的方向，使变异和遗传向着适应环境的方向发展。遗传算法正是吸取了自然生物系统“适者生存、优胜劣汰”的进化原理，从而使它能够提供一个在复杂空间中随机搜索的方法，为解决许多传统的优化方法难以解决的优化问题提供了新的途径。

五．基本遗传算法描述

5.1 基本遗传算法的构成要素

（1）染色体编码方法。基于遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0,1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数生成。如：

X=

100111000101101

n=。

就可表示一个个体，该个体的染色体长度是18

（2）个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。

（3）遗传算子。基本遗传算法(SGA)使用下述三种遗传算子：

●选择运算使用比例选择算子；

●交叉运算使用单点交叉算子；

●变异运算使用基本位变异算子或均匀变异算子。

（4）基本遗传算法的运行参数。基本遗传算法有下述4个运行参数需要提前设定：

●M：群体大小，即群体中所含个体的数量，一般取为20~100。

●T：遗传运算的终止进化代数，一般取为100~500。

p：交叉概率，一般取为0.4~0.99。

●

c

●m p ：变异概率，一般取为0.0001~0.1。 5.2 基本遗传算法描述

下面给出基本遗传算法的伪代码描述：

Pr ocedure SGA begin

initialize (0)t=0while (t )do

for 1to do

Evaluate fitness of ();end for for 1to do

Select operation of ();end for

for 1to /2do

Crossover operation of ();end for for 1to do

Mutation operation of P T i M P t i M P t i M P t i M ====；；

≤();end for

for 1to /2do (1)();end for 1;end while end

P t i M P t P t t t =+==+

5.3 基本遗传算法的形式化定义

基本遗传算法可定义为一个8元组：

0(,,,,,,,)SGA C E P M T =ΦΓψ

其中C ——个体的编码方法；

E ——个体适应度评价函数；

0P ——初始群体；

M ——群体大小；

Φ——选择算子； Γ——交叉算子；

ψ——变异算子；

T ——遗传运算终止条件。

5.4 基本遗传算法工作示意图

图1 遗传算法工作示意图

六．遗传算法的手工模拟计算示例

为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各个主要执行步骤，如表1所示。

【例】求下述二元函数的最大值：

22121211max (,)..{0,1,2,,7}{0,1,2,,7}

f x x x x s t x x ?=+?∈??∈?

现对其主要运算过程作如下解释：

（1）个体编码。遗传算法的运算对象是表示个体的符号串，所以必须把变量12,x x 编码为一种符号串。该例题中，1x 和2x 取0~7之间的整数，可分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制整数就形成了个体的基因型，表示一个

可行解。例如，基因型101110X =所对应的表现型是：[5,6]T

X =。个体的表现型x 和基

因型X 之间可通过编码和解码程序相互转换。

（2）初始群体的产生。遗传算法是对群体进行的进化操作，需要给其准备一些表示其

实搜索点的初始群体数据。本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。一个随机产生的初始群体如表1-1中第②栏所示。

（3）适应度计算。遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度。为计算函数的目标值，需先对个体基因型X 进行解码。表1-1中第③、④栏所示为初始群体中各个个体的解码结果，第⑤栏所示为各个个体所对应的目标函数值，它也是个体的适应度，第⑤栏中还给出了群体中适应度的最大值和平均值。

（4）选择运算。选择运算把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中，本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是：先计算出群体中所有个体的适应度的总和i

f

∑；其次计算出每个个体的相对适应度的

大小i

i

f f ∑，如表1中第⑥栏所示，它即为每个个体被遗传到下一代群体中的概率，每

个概率值组成一个区域，全部概率值之和为1；最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。如表1中第⑦、⑧栏所示为一随机产生的选择结果。

（5）交叉运算。交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。本例采用单点交叉的方法，其具体操作过程是：先对群体进行随机配对，如表1中第⑨栏所示为一种随机配对情况；其次随机设置交叉点位置，如表1中第⑩栏所示为一随机产生的交叉点位置，其中的数字表示交叉点设置在该基因座之后；最后再相互交换配对染色体之间的部分基因。表1中第?栏所示为交叉运算的结果。

例如，若第3号和第4号个体在第4个基因座之后进行交叉运算，则可得到两个新的个体：

第3号个体：1 0 1 0 1 1 1 0 1 0 0 1 第4号个体：1 1 1 0 0 1 1 1 1 0 1 1

可以看出，其中新产生的个体“111011”的适应度较原来两个个体的适应度都要高。

（6）变异运算。变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：首先确定出各个个体的基因变异位置，如表1中第?栏所示为随机产生的变异点位置，其中的数字表示变异点设置在该基因座处；然后按照某一概率将变异点的原有基因值取反。表1第?栏所示为变异运算结果。

例如，若第3号个体的第2个基因座需要进行变异运算，则可产生一个新的个体：

第3号个体：1 0 1 0 0 1 1 1 1 0 0 1

对群体()P t 进行一轮选择、交叉、变异运算之后可得到新一代的群体(1)P t +。如表1第?栏所示。表中第?、?、?、?栏还分别表示出了新群体的解码值、适应度和相对适应度，并给出了适应度的最大值和平均值等。从表1中可以看出，群体经过一代迭代之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体“111111”。

交叉操作 第2位变异

表1 遗传算法的手工模拟运算

七．遗传算法的模式理论 7.1 模式

在遗传算法中，我们只使用了0和1，这儿我们再引入一个通配符*，它既可以被认为是1，也可以被认为是0，在此基础上，我们有如下定义：

定义1：一个模式就是一个相同的构形，它描述了一个染色体的集合，这些染色体在某些位上是确定的，而其他位的值可以不同。例如模式*1*描述了一个由四个染色体组成的集合{010,011,110,111}。

定义2：一个模式H 的阶（位数或阶数order ）就是模式中确定位置的数目，记为()O H 。 定义3：一个模式H 的定义长度是模式中第一个确定位置与最后一个确定位置之间的距离，记为()H δ。

遗传算法中染色体的遗传操作实质上是模式的运算，通过分析模式在遗传操作下的变化，就可以了解什么性质被保留，什么性质被丢弃，从而把握遗传算法的实质，这也正是模

式定理所要揭示的内容。 7.2 模式定理

下面的讨论均假设群体中包含N 个染色体，每个染色体长度为n 。

我们首先讨论选择对模式的作用。设在t 时刻，群体中模式H 所能匹配的染色体数为

(,)m H t ，而在选择阶段，一个染色体是根据其适应值进行复制的，因此1t +时刻这种模式

的数量为：

()

(,1)(,)j

f H m H t m H t N f +=??

∑ 其中()f H 是模式H 所有样本的平均适应值，j f 为染色体j 的适应值。若记群体平均适应值j

f

f N

=

∑，则有：

()(,1)(,)f H m H t m H t f

+=?

可见，模式数量变化的方向完全取决于模式的平均适应值与群体平均适应值之比：若模式的平均适应值高于群体平均适应值，其数量将会增加，反之，其数量将会减少。

下面我们对模式数量的变化速度作一粗略的估计。设模式H 的评价适应值一直高于群体平均适应值，且

()(1)f H c f

c ≡+为常数

则有

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

可见，在选择算子作用下，平均适应值高于群体平均适应值的模式将按指数增长，而平均适应值低于群体平均适应值的模式将按指数级减少。

同时我们还可以看到，当(,0)0m H =时，则(,)0m H t ≡，即仅有选择算子无法产生新的模式，不能对搜索空间新的区域进行搜索，因而需要引入交叉算子。为了更清楚地认识交叉算子的作用，我们先来看一个长度为8的染色体及包含在其中的两个模式：

001110001*0*****02****10**A H H ===

若A 被选中参加交叉，而七个交叉位置被选中的概率相同，则只有当交叉位置为1时，模式1H 才会被保留下来，而只有当交叉位置为5时，模式2H 才可能被破坏。由于只有当交叉位置落在模式中第一个确定位置与最后一个确定位置之间时，模式才会被破坏，因此考虑其定义长度，对任意一个模式H 而言，其定义长度为()H δ，则该模式被破坏的概率为：

()

1

d H P n δ=

-

从中我们看出，一个模式的定义长度越长，其被破坏的可能性越大。下面我们再考虑交叉后模式H 生存的概率。在前面的例子中，如果与A 一起参加交叉的染色体在位置2或8上有

一位与A 相同，则交叉后得到的新染色体仍将包含模式1H 。考虑到这一点，我们可以得到一个模式生存概率的下界：

()

11

s c

H P p n δ--≥

综合考虑选择和交叉的作用，则有

()()

(,1)(,)[1]1c f H H m H t m H t p n f

δ+?

?--≥

由上式可以看出，在选择和交叉的共同作用下，模式的增长（或减少）取决于两个因素：1)

模式的平均适应值是否高于群体平均适应值；2)模式是否具有较短的定义长度。显然，那些平均适应值高于群体平均适应值、具有短的定义长度的模式将会增加。

最后考虑变异操作。由于染色体的某一位发生变化的概率为m p ，而模式H 在变异算子下若要不被破坏，则其中所有确定位置必须保持不变，因而模式H 保持不变的概率为

()(1)O H m p -，当1m p 时，模式H 在变异算子作用下的生存概率为：

()(1)1()O H s m m P p O H p =-≈-

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

()()

(,1)(,)[1()]1c m f H H m H t m H t p O H p n f

δ+?

?---≥

通过这一式子，我们就可以给出如下的模式定理：

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

统计确定理论中的双角子机问题表明：要获得最优的可行解，则必须保证较优解的样本数呈指数级增长。而模式理论保证了较优的模式（遗传算法的较优解）的样本数呈指数级增长，从而给出了遗传算法的理论基础，Holland 指出了遗传算法是一个寻找可行解的可实现的优化过程。

八．遗传算法应用中的一些基本问题

在遗传算法的应用中，除了复制、交叉和变异等基本操作外，还必须考虑目标函数到个体适值的映射、适值的调整、编码原则和多参数编码映射方法等基本问题。 8.1 目标函数值到适值形式的映射

适值是非负的，任何情况下总希望越大越好；而且目标函数有正、有负甚至可能是复数值；且目标函数和适值间的关系也多种多样。如求最大值对应点时，，目标函数和适值变化方向相同；求最小值对应点时，变化方向恰好相反；目标函数值越小的点，适值越大。因此，存在目标函数值向适值映射的问题。

首先应保证映射后的适值是非负的，其次目标函数的优化方向应对应于适值增大的方向。

对最小化问题，一般采用如下适值函数()f x 和目标函数()g x 的映射关系：

max max

(),()()0,

c g x g x c f x -

?其他 其中，max c 可以是一个输入参数，或是理论上的最大值，或是到目前所有代（或最近的k 代）之中见到的()g x 的最大值，此时max c 随着代数会有所变化。

对最大化问题，一般采用下述方法：

min min

(),()()0,

g x c g x c f x ->?=?

?其他 式中，min c 既可以是输入值也可以是当前最小值或最近的k 代中的最小值。

对指数函数问题，一般采用下述方法：

()()g x f x c =

其中，c 一般取1.618或2（最大化）、0.618（最小化）。这样，既保证了()0f x ≥，又使()f x 的增大方向与优化方向一致。

8.2 适值的调整

为了使遗传算法有效地工作，必须保持种群内位串的多样性和位串之间的竞争机制。现将遗传算法的运行分为开始、中间和结束三个阶段来考虑：在开始阶段，若一个规模不太大的种群内有少数非凡的个体（适值很高的位串），按通常的选择方法（选择复制的概率为/i i f f ∑，期望的复制数为/i i f f ）

，这些个体会被大量地复制，在种群中占有大的比重，这样就会减少种群的多样性，导致过早收敛，从而可能丢失一些有意义的搜索点或最优点，而进入局部最优；在结束阶段，即使种群内保持了很大的多样性，但若所有或大多数个体都有高的适值，从而种群平均适值和最大适值相差无几，则平均适值附近的个体和具有最高适值的个体，被选中的机会相同，这样选择就成了一个近乎随机的步骤，适值的作用就会消失，从而使搜索性能得不到明显改进。因此，有必要对种群内各位串的适值进行有效调整，既不能相差太大，又要拉开档次，强化位串之间的竞争性。现将适值三种调整方法：窗口法、函数归一化法和线性调整法简介如下。

1.窗口法

它是一种简单有效的适值调整方法，调整后的个体适值为

min ()j j F f f a =--

其中，j f 为原来个体的适值；min f 为每代种群中个体适值的最小值；a 为一常数。在进化的后期窗口法增加了个体之间的差异。

2.函数归一化法

该法是将个体适值转换到最大值与最小值之间成一定比例的范围之内，这一范围由选择压力sp k 决定。具体步骤如下。

（1）根据给定的选择压力sp k ，求种群中适值调整后的适值最小值为

min max

min 1sp

f f F k +=

+

其中，min f 和max f 是调整前种群个体适值的最小值和最大值。适值调整后种群中适值最大值为

max min sp F k F =

（2）计算线性适值转换的斜率为

max min

max min

F F F f f -?=

-

（3）计算每个个体的新适值为

min min ()j j F F F f f =+?-

其中，j f 为调整前第j 个个体适值。在进化的早期，函数归一化法缩小了种群内个体之间的差异，而在进化的后期又适当增大了性能相似个体之间的差异，加快了收敛速度。

3.线性调整法

线性调整法是一个有效的调整方法。设f 是原个体适值，F 是调整后个体的适值

F af b =+

系数a 、b 可通过多种方法选取。不过，在任何情况下均要求avg F 应与avg f 相等，即应满足的条件为

max avg avg

mult avg

F f f c F =???

=?? 其中，mult c 是最佳种群所要求的期望副本数，是一个经验值，对于一个不大的种群（50~100n =）来说，可在1.2~2的范围内取值。

8.3 编码原则

遗传算法参数编码原则有两种：深层意义上的建筑块原则和最小符号表原则。而后者是一种应用广泛的应用原则。

最小符号表原则要求选择一个使问题得以自然表达的最小符号编码表。在前面讨论中使用的都是二进制符号编码表{0,1}，任何一个长度为l 的位串都包含在{0,1}中。根据遗传算法的模式理论，遗传算法能有效工作的根本原因，在于其能有效地处理种群中的大量模式，尤其是那些定义长度短、确定位数少、适值高的模式（即建筑块）。因此，编码应使确定规模的种群中包含尽可能多的模式。

假设有一个非二进制的包含k 个字母编码的符号表V '及二进制编码的符号表V ，即

12{,,,}k V a a a '=

{0,1}V =

为了表达同样多的点数，在各自的空间中两种编码的长度分别为l '和l ，即有

2l l k '=

此时，在二进制编码中包含的模式数（单个位串）为3l

。在非二进制编码中，单个位串包含的模式数为(1)l k '

+。可以证明，当2k >时，3(1)l l k '

>+。

8.4 多参数级联定点映射编码

对于具有多个实数参数的函数优化问题，一个实用的编码方案是，多参数级联定点映射编码方法。

前面已考虑过无符号定点整数的编码，[0,2]l x ∈。若要求在参数空间编码，一种改造这一区间的方法是将编码后的无符号整数[0,2]l

线性映射到特定区间min max [,]U U 上。这样，就可以仔细控制一些决定性变量的变化范围和精度，其映射代码的精度为：

max min

21

l

U U δ-=

- 为了设计多参数编码，可把相互关联的参数按要求简化成若干单一参数代码。 假设有几个参数需要编码：

(1)(1)

1min max (2)(2)2min max ()()min max [,][,]

[,]

n n n x U U x U U x U U ∈∈∈

采用二进制编码，先对各参数分别编码：

1x ：1l 位，1

(1)

[0,21]l U ∈-；1

(1)(1)

max min

121

l U U δ-=- 2x ：2l 位，2

(2)

[0,21]l U

∈-；2(2)(2)max min

221

l U U δ-=

-

n x ：n l 位，()

[0,21]n

l n U

∈-；()()max min

21

n

n n n l U U δ-=- 建立映射：

()

()min 1,2,,i i i i

x U U i n δ=+=

将级联各编码参数构成的一个整体，即

1

2

12()

(1)

(2)

111212122212||n

n n l l l l l ij n n nl U U U b b b b b b b b b b

其中，{0,1}ij b ∈。

遗传算法的基本原理

第二章 遗传算法的基本原理 2.1 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S 作为搜索空间，f ：S —>R 为目标函数，全局优化问题作为任务)(max x f S x ∈给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值+∞<=)(**x f f 称为一个全局最大值，当且仅当x ? S x ∈，(ρi i b a <，i 12）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P ； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。

2.1.3 遗传编码 由于GA 计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA 个体的表现型集合做组成的空间称为问题（参数）空间，由GA 基因型个体所组成的空间称为GA 编码空间。遗传算子在GA 编码空间中对位串个体进行操作。 定义：由问题空间向GA 编码空间的映射称为编码，而有编码空间向问题空间的映射成为译码。 1）2）3）它们对1） 2） k =1,2,…,K; l =1,2,…,L; K=2L 其中，个体的向量表示为),,,(21kL k k k a a a a =，其字符串形式为kL k k k a a a s 21=，s k 称为个体a k 对应的位串。表示精度为)12/()(--=?L u v x 。 将个体又位串空间转换到问题空间的译码函数],[}1,0{:v u L →Γ的公式定义为： 对于n 维连续函数),,2,1](,[),,,,(),(21n i v u x x x x x x f i i i n =∈=，各维变量的二进制

谈谈遗传算法的原理

谈谈遗传算法的原理 发表时间：2011-08-24T09:52:45.450Z 来源：《魅力中国》2011年7月上供稿作者：朱小宝 [导读] 从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。 朱小宝 (南昌航空大学飞行器工程学院江西南昌 330029) 中图分类号：TP301.6 文献标识码：A 文章编号：1673-0992（2011）07-0000-01摘要：自从霍兰德于1975年在他的著作《Adaption im Natural and artificial Systems》中首次提出遗传算法以来，经过了近30年的研究，现在已经发展到了一个比较成熟的阶段，并且在实际中得到了很好的应用。为了更好的了解遗传算法，本文通过最简单的一个手工计算实例来还原遗传算法的全过程。 关键词：遗传算法生物进化染色体种群 自然界的生物进化是按“适者生存，优胜劣汰”规律进行的，而遗传算法就是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性，这是一种全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定。 遗传算法采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的操作对象是一群二进制串(称为染色体)，即种群。这里每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。 遗传算法主要步骤： （1）编码：由于遗传算法不能直接处理解空间的数据，必须通过编码将它们表示成遗传空间的基因型串结构数据。 （2）选择初始种群：随机产生N个初始串结构数据，每个串结构数据称为一个个体，也称为染色体，N个个体体构成了一个种群。 （3）选择适应度函数：遗传算法在搜索过程中一般不需要其他外部信息或知识，仅用适应度函数来评价个体的适应度。 （4）选择：利用选择概率再随机的选择个体和复制数量。选择算子的设计可依据达尔文适者生存的进化论原则，选择概率大的被选中的机会较多。 （5）杂交：对被选中的个体进行随机配对并随机的选择基因交换位，交换基因后产生新的个体，全体新个体构成新的（下一代）种群。 （6）变异：变异操作是按位进行求反，对二二进制编码的个体而言，就是对随机选中的某位进行求反运算，即“0”变“1”，“1”变大“0”。 （7）一代种群通过遗传，即选择、杂交和变异产生下一代种群。新种群又可重复上述的选择、杂交和变异的遗传过程。 为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各个主要执行步骤。 求下述二元函数的最大值： Max f(x1,x2)= x12+ x22 S,t, x1∈{1,2,3,4,5,6,7} x2∈{1,2,3,4,5,6,7} (1) 个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种符号串。本题中，用无符号二进制整数来表示。因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。例如，基因型 X＝101110 所对应的表现型是：x＝[5，6]。个体的表现型x和基因型X之间可通过编码和解码程序相互转换。 (2) 初始群体的产生 群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。 如：011101，101011，011100，111001 (3) 适应度汁算 目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接用目标函数值作为个体的适应度。 (4) 选择运算 我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是： 1.先计算出群体中所有个体的适应度的总和 fi ( i=1.2,…,M )； 2.fi其次计算出每个个体的相对适应度的大小 fi / ，它即为每个个体被遗传到下一代群体中的概率， 3.每个概率值组成一个区域，全部概率值之和为1； 4.最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。

遗传算法的基本原理

遗传算法的基本原理 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】

第二章 遗传算法的基本原理 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S 作为搜索空间，f ：S —>R 为目标函数，全局优化问题作为任务)(max x f S x ∈给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值+∞<=)(**x f f 称为一个全局最大值，当且仅当)()(*x f x f S x ≤?∈?成立时，S x ∈*被称为一个全局最大值点（全局最大解）。 局部极大值与局部极大值点（解）的定义： 假设在S 上给定了某个距离度量ρ，如果对S x ∈'，0>?ε，使得对S x ∈?， )()(),(''x f x f x x ≤?<ερ，则称x ’为一个局部极大值点，f (x ’)为一个局部极大值。当目标函数有多个局部极大点时，被称为多峰或多模态函数（multi-modality function ）。 主要考虑两类搜索空间： 伪布尔优化问题：当S 为离散空间B L ={0,1}L ,即所有长度为L 且取值为0或1的二进制位串的集合时，相应的优化问题在进化计算领域称为伪布尔优化问题。 连续参数优化问题：当取S 伪n 维实数空间R n 中的有界集合],[1i i n i b a S =∏=，其中i i b a <，i = 1, 2, … , n 时，相应的具有连续变量的优化问题称为连续参数优化问题。 对S 为B L ={0,1}L ，常采用的度量时海明距离，当],[1i i n i b a S =∏=时，常采用的度量就是欧氏距离。 2.1.2 遗传算法的基本流程 遗传算法的基本步骤如下： 1）选择编码策略，把参数集合X 和域转换为位串结构空间S ； 2）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P ； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。 2.1.3 遗传编码 由于GA 计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA 个体的表现型集合做组成的空间称为问题（参数）空间，由GA 基因型个体所组成的空间称为GA 编码空间。遗传算子在GA 编码空间中对位串个体进行操作。

遗传算法的原理及MATLAB程序实现

1 遗传算法的原理 1.1 遗传算法的基本思想 遗传算法（genetic algorithms，GA）是一种基于自然选择和基因遗传学原理，借鉴了生物进化优胜劣汰的自然选择机理和生物界繁衍进化的基因重组、突变的遗传机制的全局自适应概率搜索算法。 遗传算法是从一组随机产生的初始解（种群）开始，这个种群由经过基因编码的一定数量的个体组成，每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，其内部表现（即基因型）是某种基因组合，它决定了个体的外部表现。因此，从一开始就需要实现从表现型到基因型的映射，即编码工作。初始种群产生后，按照优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 计算开始时，将实际问题的变量进行编码形成染色体，随机产生一定数目的个体，即种群，并计算每个个体的适应度值，然后通过终止条件判断该初始解是否是最优解，若是则停止计算输出结果，若不是则通过遗传算子操作产生新的一代种群，回到计算群体中每个个体的适应度值的部分，然后转到终止条件判断。这一过程循环执行，直到满足优化准则，最终产生问题的最优解。图1-1给出了遗传算法的基本过程。 1.2 遗传算法的特点 1.2.1 遗传算法的优点 遗传算法具有十分强的鲁棒性，比起传统优化方法，遗传算法有如下优点： 1. 遗传算法以控制变量的编码作为运算对象。传统的优化算法往往直接利用控制变量的实际值的本身来进行优化运算，但遗传算法不是直接以控制变量的值，而是以控制变量的特定形式的编码为运算对象。这种对控制变量的编码处理方式，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地处理各种变量和应用遗传操作算子。 2. 遗传算法具有内在的本质并行性。它的并行性表现在两个方面，一是遗传

遗传算法基本原理111

第二章遗传算法的基本原理 2.1 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S作为搜索空间，f：S—>R为目标函数，全局优化问题作为任务给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值称为一个全局最大值，当且仅当成立时，被称为一个全局最大值点（全局最 大解）。 局部极大值与局部极大值点（解）的定义： 假设在S上给定了某个距离度量，如果对，，使得对， ，则称x’为一个局部极大值点，f(x’)为一个局部极大 值。当目标函数有多个局部极大点时，被称为多峰或多模态函数（multi-modality function）。 主要考虑两类搜索空间： 伪布尔优化问题：当S为离散空间B L={0,1}L,即所有长度为L且取值为0或1的二进制位串的集合时，相应的优化问题在进化计算领域称为伪布尔优化问题。 连续参数优化问题：当取S伪n维实数空间R n中的有界集合，其中，i = 1, 2, … , n时，相应的具有连续变量的优化问题称为连续参数优化问题。 对S为B L={0,1}L，常采用的度量时海明距离，当时，常采用的度量就是欧氏距离。 2.1.2 遗传算法的基本流程

遗传算法的基本步骤如下： 1）选择编码策略，把参数集合X和域转换为位串结构空间S； 2）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。 2.1.3 遗传编码 由于GA计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA个体的表现型集合做组成的空间称为问题（参数）空间，由GA基因型个体所组成的空间称为GA编码空间。遗传算子在GA

遗传算法的特点及其应用

遗传算法的特点及其应用 上海复旦大学附属中学张宁 目录 【关键词】 【摘要】 【正文】 §1遗传算法的基本概念 §2简单的遗传算法 1．选择 2．交换 3．变异 §3简单的遗传算法运算示例 1．计算机公司的经营策略优化问题 2．函数优化问题 §4遗传算法应用举例 1．子集和问题 2．TSP（旅行商）问题 §5结束语 【附录】 1．子集和问题源程序 2．TSP（旅行商）问题源程序 【参考文献】

【关键词】 遗传算法遗传变异染色体基因群体 【摘要】 遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。 文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于NP-完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。 文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。 【正文】 遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得我们进行深入的讨论。 要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。 §1遗传算法的基本概念 遗传算法（Genetic Algorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它

遗传算法的基本原理

遗传算法的基本原理 遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。这就是遗传算法的基本原理。 下面就是遗传算法思想： (1) 初始化群体; (2) 计算群体上每个个体的适应度值; (3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体; (4) 按概率PX进行交叉操作; (5) 按概率PM进行突变操作; (6) 没有满足某种停止条件，则转第(2)步，否则进入(7)。 (7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。 程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。 根据遗传算法思想可以画出如右图所示的简单遗传算法框图： 图 3.22 简单遗传算法框图 遗传算法的选择算子 选择即从当前群体中选择适应值高的个体以生成交配池的过程. 遗传算法中最常用的选择方式是轮盘赌(Roulette Wheel)选择方式, 也称比例选择或复制. 在该方法中, 各个个体被选择的概率和其适应度值成比例. 设群体规模大小为N, 个体i 的适应度值为Fi , 则这个个体

(完整版)遗传算法的基本原理

遗传算法的基本原理和方法 一、编码 编码：把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法。 解码（译码）：遗传算法解空间向问题空间的转换。 二进制编码的缺点是汉明悬崖（Hamming Cliff），就是在某些相邻整数的二进制代码之间有很大的汉明距离，使得遗传算法的交叉和突变都难以跨越。 格雷码（Gray Code）：在相邻整数之间汉明距离都为1。 （较好）有意义的积木块编码规则：所定编码应当易于生成与所求问题相关的短距和低阶的积木块；最小字符集编码规则，所定编码应采用最小字符集以使问题得到自然的表示或描述。 二进制编码比十进制编码搜索能力强，但不能保持群体稳定性。 动态参数编码（Dynamic Paremeter Coding）：为了得到很高的精度，让遗传算法从很粗糙的精度开始收敛，当遗传算法找到一个区域后，就将搜索现在在这个区域，重新编码，重新启动，重复这一过程，直到达到要求的精度为止。 编码方法：

1、二进制编码方法 缺点：存在着连续函数离散化时的映射误差。不能直接反映出所求问题的本身结构特征，不便于开发针对问题的专门知识的遗传运算算子，很难满足积木块编码原则 2、格雷码编码：连续的两个整数所对应的编码之间仅仅只有一个码位是不同的，其余码位都相同。 3、浮点数编码方法：个体的每个基因值用某一范围内的某个浮点数来表示，个体的编码长度等于其决策变量的位数。 4、各参数级联编码：对含有多个变量的个体进行编码的方法。通常将各个参数分别以某种编码方法进行编码，然后再将他们的编码按照一定顺序连接在一起就组成了表示全部参数的个体编码。 5、多参数交叉编码：将各个参数中起主要作用的码位集中在一起，这样它们就不易于被遗传算子破坏掉。评估编码的三个规范：完备性、健全性、非冗余性。 二、选择 遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取那些个体遗传到下一代群体中的一种遗传运算，用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。 常用的选择算子： 1、轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。

遗传算法搜索最优解

实验一：基于遗传算法的函数优化 1、实验目的 1) 掌握Matlab子函数的编写与调用。 2) 理解基本遗传算法的原理，并利用程序实现利用遗传算法优化非线性函数的解。 2、实验内容与实验要求 1) 掌握基本遗传算法方法原理。 2) 掌握matlab子函数的编写方法及调用方法。 3) 根据基本遗传算法方法原理，编写Matlab程序，优化非线性函数的解。 4) 设f(x) = -x^2 - 4x + 1，求max f(x), x [-2, 2],解的精度保留二位小数 3、遗传算法原理 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

4、主程序及子函数： 主函数: clear clc my_scale=80; %种群规模 gen_len=22; %基因长度 M=100; %迭代次数 pc=0.7; %交叉概率 pm=0.05; %变异概率 new_scale=produscale(my_scale,gen_len); %产生初始种群 fitfit=[]; fittimer=[]; best_f1=[]; best_x1=[]; for i=1:M my_f=cal_my_f(new_scale); %计算函数值 my_fit=cal_my_fit(my_f); %计算适应度值 next_scale=my_sellect(new_scale,my_fit); %采用赌轮盘法选择 cross_scale=my_cross(next_scale,pc); %按概率交叉 mut_scale=my_mutat(cross_scale,pm); %按概率变异 %寻找每一代中的最优适应度值所对应的个体 best_fit=my_fit(1); [sx,sy]=size(new_scale); for j=2:length(my_fit) if best_fit