遗传算法学习心得体会

遗传算法 概念

遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它既能在搜索中自动获取和积累有关空间知识，并自适应地控制搜索过程以求得最优解遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近视最优方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近视解。这个过程导致种群中个体的进化，得到的新个体比原个体更适应

环境，就像自然界中的改造一样。 应用

遗传算法在人工智能的众多领域具有广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如tsp、背包问题）、函数的最大值以及图像处理和信号处理等等。遗传算法多用应与复杂函数的优化问题中。 原理

遗传算法模拟了自然选择和遗传中发生的复制、交叉、和变异等现象，从任一初始种群出发，通过随机选择、交叉、变异操作，产生一群更适合环境的个体，使群体进行到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适合环境的个体求得问题的最优解。

算法流程 1. 编码：解空间中的解数据x，作为作为遗传算法的表现型形式。从表现 型到基本型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传

空间的基本型串结构数据，这些串结构数据的不同的组合就构成了不同的点。 2. 初始种群的形成：随机产生n个初始串数据，每个串数据称为一个个体， n个串数据构成了一个群体。遗传算法以这n个串结构作为初始点开始迭代。设置进化

代数计数器t 0;设置最大进行代数t；随机生成m个个体作为初始群体p(0)。 3. 适应度检测：适应度就是借鉴生物个体对环境的适应程度,适应度函数 就是对问题中的个体对象所设计的表征其优劣的一种测度。根据具体问题计算p(t)的适应度。

4. 选择：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到 下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的

适应度评估基础上的。

5. 交叉：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结 构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 6. 变异：将变异算子作用于群体。即是对群体中的个体串的某些基因座上 的基因值作变动。

群体p(t)经过选择、交叉、变异运算之后得到下一代群体p(t+1)。 7. 终止条件判断:若t<=t,则t=t+1，转到第3步，否则以进化过程中所得 到的具有最大适应度个体作为最优解输出，终止计算。 遗传算法流程图如下图所示： 遗传算法

下几种：适应度比例方法、随机遍历抽样法、局部选择法。 其中轮盘赌选择法是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率，为遗传算法

2、交叉：在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分

结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。 交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，

期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法： b)二进制交叉（binary valued crossover） 1)单点交叉（single-point crossover） 2)多点交叉（multiple-point crossover） 3)均匀交叉（uniform crossover） 4)洗牌交叉（shuffle crossover） 5)缩小代理交叉（crossover with reduced surrogate）。 3、变异

变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编

码表示方法的不同，可以有以下的算法： a)实值变异 b)二进制变异。

一般来说，变异算子操作的基本步骤如下： a)对群中所有个体以事先设定的编译概率判断是否进行变异 b)对进行变异的个体随机选择变异位进行变异。 例：简单一元函数优化 求下面函数的最大值：

f(x)=xsin(10*pi*x)+2.0, -1<=x<=2; 程序： figure(1);

fplot(variable.*sin(10*pi*variable)+2.0,[-1,2]); %画出函数曲线 %定义遗传算法参数

nind=40; %个体数目(number of individuals) maxgen=25; %最大遗传代数(maximum number of generations) preci=20; %

变量的二进制位数(precision of variables) ggap=0.9; %代沟(generation gap) trace=zeros(2, maxgen); %寻优结果的初始值 fieldd=[20;-1;2;1;0;1;1]; %区域描述器(build field descriptor) chrom=crtbp(nind, preci); %初始种群 gen=0; %代计数器 variable=bs2rv(chrom, fieldd); %计算初始种群的十进制转换

objv=variable.*sin(10*pi*variable)+2.0; %计算目标函数值 while gen<maxgen

fitnv=ranking(-objv); %分配适应度值(assign fitness values) selch=select(sus, chrom, fitnv, ggap); %选择 selch=mut(selch); %变异 variable=bs2rv(selch, fieldd); %子代个体的十进制转换 objvsel=variable.*sin(10*pi*variable)+2.0; %计算子代的目标函数值 [chrom objv]=reins(chrom, selch, 1, 1, objv, objvsel); %重插入子代的新种群 variable=bs2rv(chrom, fieldd);

gen=gen+1; %代计数器增加 %输出最优解及其序号，并在目标函数图像中标出，y为最优解,i为种群的序号 [y, i]=max(objv);hold on; plot(variable(i), y, bo); trace(1, gen)=max(objv); %遗传算法性能跟踪 trace(2,

gen)=sum(objv)/length(objv); end

variable=bs2rv(chrom, fieldd);%最优个体的十进制转 hold on, grid;

plot(variable,objv,b*); figure(2);

plot(trace(1,:)); hold on;

plot(trace(2,:),-.);grid

legend(解的变化,种群均值的变化)篇二：遗传算法学习心得 基本概念 遗传算法(genetic algorithms, ga)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。 它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)

对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 ga的组成:

（1）编码（产生初始种群） （2）适应度函数

（3）遗传算子（选择、交叉、变异） （4）运行参数 编码

基因在一定能够意义上包含了它所代表的问题的解。基因的编码方式有很多，这也取决

于要解决的问题本身。常见的编码方式有： （1） 二进制编码，基因用0或1表示（常用于解决01背包问题） 如：基因a：

00100011010 (代表一个个体的染色体) （2） 互换编码（用于解决排序问题，如旅行商问题和调度问题） 如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城

市中，先经过城市2，再经过城市3，依此类推。 （3） 树形编码（用于遗传规划中的演化编程或者表示） 如,问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数

把每个输入尽可能近地映射为输出。 编码方法：基因就是树形结构中的一些函数。 （4） 值编码 （二进制编码不好用时，解决复杂的数值问题） 在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，

字符或者其他一些更复杂的东西。 适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设

计应结合求解问题本身的要求而定。 如tsp问题，遍历各城市路径之和越小越好，这样可以用可能的最大路径长度减去实际

经过的路径长度，作为该问题的适应度函数。 遗传算子——选择 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作

的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。 sga（基本遗传算法）中采用轮盘赌选择方法。 轮盘赌选择又称比例选择算子，基本思想：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为 fi，则个体i 被选中遗传到下一代群体的

概率为： 遗传算子——交叉 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分

基因，从而形成两个新的个体。交叉运算在ga中起关键作用，是产生新个体的主要方法。 1. 单交叉点法 （用于二进制编码） 选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外

一个父代基因那里得到。 如：交叉前：

00000|01110000000010000 11100|00000111111000101 交叉后：

00000|00000111111000101 11100|01110000000010000

2. 双交叉点法 （用于二进制编码） 选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因. 如：交叉前： 01 |0010| 11 11 |0111| 01 交叉后： 11 |0010| 01 01 |0111| 11

3. 基于“ 与/或 ”交叉法 （用于二进制编码） 对父代按位与”逻辑运算产生一子代a;按位”或”逻辑运算产生另一子代b。该交叉策

略在解背包问题中效果较好 . 如：交叉前： 01001011 11011101 交叉后： 01001001 11011111

4. 单交叉点法 （用于互换编码） 选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中

扫描，如果某个位点在子代中没有，就把它添加进去。

如：交叉前： 87213 | 09546 98356 | 71420 交叉后：

87213 | 95640 98356 | 72104

5. 部分匹配交叉（pmx）法（用于互换编码） 先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。

父代a：872 | 130 | 9546

父代b：983 | 567 | 1420 变为： temp a: 872 | 567 | 9546 temp b: 983 | 130 | 1420 对于 temp a、temp ｂ中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>５ ３<——>６ ７<——>０ 子代ａ：802 | 567 | 9143

子代ｂ：986 | 130 | 5427

6. 顺序交叉法(ox) （用于互换编码） 从父代ａ随机选一个编码子串，放到子代ａ的对应位置；子代ａ空余的位置从父代ｂ中按ｂ的顺序选取（与己有编码不重复）。同理可得子代ｂ。 父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：

子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904

7. 循环交叉（cx）法（用于互换编码） cx同ox交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：ox中来自第一个亲代的编码子串是随机产生的，而cx却不是，它是根据两

个双亲相应位置的编码而确定的。 父代ａ：1 2 3 4 5 6 7 8 9 | | | | |

父代ａ：5 4 6 9 2 3 7 8 1 可得循环基因：1->5->2->4->9->1 用循环的基因构成子代ａ，顺序与父代ａ一样 1 2 4 5 9

用父代ｂ剩余的基因填满子代ａ： 1 2 6 4 5 3 7 8 9 子代ｂ的编码同理。（循环基因 5->1->9->4->2->5） 遗传算子——变异 变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。ga中的变异运算是产生新个体的辅助方法，它决定了ga的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。

注：变异概率pm不能太小，这样降低全局搜索能力；也不能太大，pm > 0.5，这时

ga退化为随机搜索。篇三：计算智能学习心得体会 计算智能学习心得体会 本学期我们水利水电专业开了“计算智能概论”这门课，有我们学院的金菊良教授给我们授课，据说这门课相当难理解，我们课下做了充分的准备，借了计算智能和人工智能相关方面的书籍，并提前了解了一点相关知识，我感觉看着有点先进，给我们以往学的课程有很大区别，是一种全新的概念和理论，里面的遗传算法、模糊集理论、神经网络更是闻所未闻，由于课前读了一些书籍，我以为课堂上应该能容易理解一点，想不到课堂上听着还是相当玄奥，遗传算法还好一点，因为高中学过生物遗传，遗传算法还能理解一点。像模糊集理论神经网络便不知所云了。虽然金老师讲课生动形象，幽默风趣，而且举了好多实际的例子，但

有一些理论有点偏难。 多关于ci的解释。 虽然有好多计算智能理论还不太清楚，但是我对新知识还是相当渴望的，因为我本身比较爱学习，且喜欢读书。我感觉学到了许多知识：计算智能是一门经验科学，它研究自然的或人工的智能行为形成之原理以“推理即计算”为基本假设，开发某种理论、说明某项智能可以算法化，从而可以用机器模拟和实现；寻求和接受自然智能之启迪，但不企图完全仿制

人类智能，其中心工程目标是研究设计和建立智能计算系统的方法。 由于我们只有16课时，所以我们学的面并不广，金老师主要教了一些计算智能方面的经典理论，我们所学的计算智能所涉及的领域主要包括以下三方面：遗传算法、人工神经网络方法和模糊集理论。

遗传算法最早由美国michigan大学john h. holland教授提出， 按照生物进化过程中的自然选择（selection）、父代杂交（crossover）和子代变异（mutation）的自然进化（natural evolution）方式，编制的计算机程序，能够解决许多复杂的优化问题，这类新的优化方法称之为遗传算法（genetic algorithm，ga）[7]。ga模拟生物进化过程中的主要特征有：（1）生物个体的染色体（chromosomes）的结构特征，即基因码序列（series of genetic code）决定了该个体对其生存环境的适应能力。（2）自然选择在生物群体（population）进化过程中起着主导作用，它决定了群体中那些适应能力（adaptability）强的个体能够生存下来并传宗接代，体现了“优胜劣汰”的进化规律。（3）个体繁殖（杂交）是通过父代个体间交换基因材料来实现的，生成的子代个体的染色体特征

可能与父代的相似，也可能与父代的有显著差异，从而有可能改变个体适应环境的能力。 （4）变异使子代个体的染色体有别于其父代个体的染色体，从而也改变了子代个体对其环境的适应能力。（5）生物的进化过程，从微观上看是生物个体的染色体特征不断改善的过

程，从宏观上看则是生物个体的适应能力不断提高的过程。 作为利用自然选择和群体遗传机制进行高维非线性空间寻优的一类通用方法，遗传算法（ga）不一定能寻得最优（optimal）点，但是它可以找到更优（superior）点，这种思路与人类行为中成功的标志是相似的。例如不必要求某个围棋高手是最优的，要战胜对手只需他（她）比其对手更强即可。因此，ga可能会暂时停留在某些非最优点上，直到变异发生使它

迁移到另一更优点上。遗传算法随编码 方式、遗传操作算子的不同而表现为不同形式，因此难以象传统的共轭梯度法那样从形式上给以明确定义，它的识别标志在于它是否具有模拟生物的自然选择和群体遗传机理这一内在特征。目前国内外普遍应用的实施方案是标准遗传算法（simple genetic algorithm，sga）。 bp神经网络 bp神经网络是用反向传播学习算法（back-propagation algorithm，bp算法）训练的一种多层前馈型非线性映射网络，网络中各神经元接受前一级的输入，并输出到下一级，网络中没有反馈联接。bp神经网络通常可以分为不同的层（级），第j层的输入仅与第j–1层的

输出联接。由于输入层节点和输出层节点可与外界相连，直接接受环境的影响，所以称为可见层，而其它中间层则称为隐层（hidden layer）。决定一个bp神经网络性质的要素有三个：网络结构、神经元作用函数和学习算法，对这三个要素的研究构成了丰富多彩的内容，尤其是后者被研究得最多。bp算法是目前应用最为广泛且较成功的一种算法，它解决了多层前馈网络的学习问题，从而使该网络在各方面获得了广泛应用。它利用梯度搜索技术（gradient

search technique）使代价函数（cost function）最小化。 bp算法把一组样本的输入输出问题归纳为一非线性优化问题，它使用了最优化方法中最常用的负梯度下降算法。用迭代运算求解网络权重和阈值对应于网络的学习记忆过程，加入

隐层节点使得优化问题的可调参数增加，从而可得到更精确的解。 模糊集理论 模糊集理论（又称模糊数学，fuzzy mathematics）就是应用模糊集这一模拟人脑模糊思维的数学工具，来描述、分析、识别、分类、判断、推理、决策和控制各种模糊事物所形成的一门现代应用数学分支学科。经典数学仅考虑现实世界的数量而抛弃现实世界的质量，而模糊集理论则反映了现实世界数量与质量的统一性，是对经典数学的一种补充和完善。定义模糊集、模糊关系的不同运算（目前主要是代数运算），就可得到相应的不同模糊数学方法。目前已研究成熟并广为应用的模糊数学方法主要有模糊模式识别、模糊聚类分析、模糊综合评价、模糊推理、模糊控制等方法。在现代科学技术体系中定性因素和主观因素定量化处理的方法至今仍很少，而模糊数学方法正是其中的典型代表，目前已在各科学和工程领域得到了广泛的成功应用，其主要原因在于它异于其它方法的一些显著特点：（1）模糊集的引入改善了二值逻辑中硬性的分类方法，是普通集合的推广，使模糊数学方法更加接近于广泛存在模糊性和不精确性的现实世界，也更加接近于人类思维方式。这些真实性使得模糊数学方法能很好地平衡系统的复杂性与描述系统的精确性，也有助于模糊数学方法充分提取各种专家经验信息和其它人类语言信息。（2）当系统为多输入多输出、强非线性、定性信息与定量信息混杂的动态系统时，系统的数学模型非常复杂或根本就不存在确定性数学模型，常规方法难以或不能有效处理这样的复杂系统，而模糊数学方法可以用建立在语言型经验之上的模糊集及其运算就可以简便有效地处理，有时甚至不需要辅以确定的数学模型。（3）模糊数学方

法可以直接利用人类语言型概念及其运算，篇四：遗传算法总结 遗传算法总结 遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局自适应概率搜索算法。

一、遗传算法流程图 图1 遗传算法流程图 二、遗传算法的原理和方法 1） 染色体编码 把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为

编码。 de jong曾提出了两条操作性较强的实用编码原则：编码原则一：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案；编码原则二：应使用能使问题得

到自然表示或描述的具有最小编码字符集的编码方案。 编码方法主要有以下几种：二进制编码方法、格雷码编码方法、浮点数编码方法、符号

编码方法、参数级联编码方法、多参数交叉编码方法。 2） 适应值计算 由解空间中某一点的目标函数值f(x)到搜索空间中对应个体的适应度函数值 fit(f(x))的转换方法基本上有一下三种： a． 直接以待解的目标函数值f(x)转化为适应度函数值fit(f(x))，令

?f(x) 目标函数为最大化函数 fit(fx())= ?

??f(x)目标函数为最小化函数 ?cmax?f(x) f(x)?cmax

b． 对于最小值的问题，做下列转化fit(f(x))??，其中cmax是 0 其他? f(x)的最大输入值。

c． 若目标函数为最小值问题，fit(f(x))? 1

, c?0, c?f(x)?0 1?c?f(x) 1

, c?0, c?f(x)?0 1?c?f(x)

若目标函数为最大值问题，fit(f(x))?3） 选择、交叉、变异 遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：根据每个个体的适应度值大小选择。适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体的被遗传到下一代群体中的概率较小。其中选择的方法有：轮盘赌选择、随机竞争选择、最佳保留

选择、无回放随机选择、确定式选择等。 遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉操作主要有单点交叉、两点交叉与多点交叉、均匀交叉

和算数交叉四种。 遗传算法中的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他基因来替换，从而形成一个新的个体。主要有基本位变异、均匀变异、边界变异等

几种变异操作方法。 4） 控制参数选择 交叉概率pcpm 三、算例

min f(x1,x2)?(x1?3)2?(x2?2)2 2

?g1(x1,x2)?x12?x2?5?

s.t.?h1(x1,x2)?x1?2x2?4?0?x,x?10，x?n 121? (1)

1）三种不同的遗传方法

方法一：原模型中x1、x2均为决策变量，操作如下。 a. 采用混合整数编码，对x1进行十进制编码，x2进行二进制编码； b. 适应度函数值采用fit(f(x1,x2))? 1

计算，其中 c?f(x1,x2)

c???max{0,g1(x1,x2)?5}???max{0,|h1(x1,x2)?4|}，?=?=10000； c. 采用赌轮盘选择、单点交叉和基本位变异； d. pc=0.8，pm=0.1，遗传代数为200，种群中个体数100； e. 终止条件为连续十次最

优个体保持不变或遗传代数到达200。

方法二：已知等式约束h1(x1,x2)，可得x2?(4?x1)/2，则原问题可化为 min f(x1)?(x1?3)2?(( 4?x1

)?2)22 （2） 4?x12?2

g(x)?x?()?5111? 2?s..t?0?x1?10，x1?n?4?x1?0??10 2? x

min f(x1)?(x1?3)2?(1)2 2

即等式约束简化后的模型为 4?x12?2 g(x)?x?()?5?1

s..t?112??0?x1?4，x1?n

其中a~b的操作如下，而c~e的操作同方法一。 a. 对x1进行十进制编码； b. 适应度函数值采用fit(f(x1,x2))? （3） 1

计算，其中 c?f(x1,x2)

c???max{0,g1(x1,x2)?5}，?=10000 方法三：在方法二的基础上，改变x1的编码方法，对x1进行二进制编码。由于0?x1?4，且为自然数，则二进制编码至少为3位，但3位的二进制可以表示0~7的整数，所以存在冗

余编码。则通过惩罚来排除冗余编码，即适应度函数值采用 fit(f(x1,x2))? 1

计算。 c?f(x1,x2) 其中c???max{0,g1(x1,x2)?5}???max{0,x1(i)?4}，?=10000。x1(i)表示个体解码后的x1。

2）三种方法的计算结果

方法一可得到三个不同的解： 解1：x1?2,x2?1, fit(f(x1,x2))?0.4646, f(x)?2.0000，适应度趋势图如下： 图2 方法一解1的适应度趋势图 解2：x1?0,x2?2, fit(f(x1,x2))?0.1075, f(x)?9.0000，适应度趋势图如下： 篇五：遗传算法学习作业 遗传算法学习总结 1.1 概述 遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的自适应概率性随机化迭代搜索算法。1962年霍兰德(holland)教授首次提出了ga算法的思想，它的基本思想是基于darwin进化论和mendel的遗传演说。darwin进化论最重要的是适者生存的原理，它认为每一代种群总是向着前进方向发展，越来越适应环境。每一个个体都有继承前代的特性，但不是完全继承，会产生一些新特性。最终只有适应环境的特征才能被保留下来。mendel遗传学说最重要的是基因遗传原理，它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。一条染色体中存在很多基因，每个基因有自己的位置并

控制着外部特征；基因的产生和变异直接影响到个体的特性是否能适应环境。经过存优去劣

的自然淘汰，适应性高的基因结构得以保存下来。 遗传算法正是借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作

用机制，实现各个个体的适应性的提高。 与自然界相似，遗传算法对求解问题的本身一无所知，从代表问题可能潜在解集的一个种群(population)开始，每一个种群则由经过基因(gene)编码(coding)的一定数目的个体 (individual)构成。每个个体实际上是染色体(chromosome)带有特征的实体。把问题的解表示成染色体，并基于适应值来选择染色体，遗传算法所需要的仅是对算法所产生的每个染色体进行评价，使适应性好的染色体有更多的繁殖机会。在算法中也就是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也就是假设解。然后，把这些假设解置于问题的“环境”中，也即在一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制，淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的

新一代染色体群。对这个新种群进行下一轮进化，直到最适合环境的值。 1.2遗传算法的基本原理和特点 1.2.1 算法原理 在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群，再对这个新种群进行下

一轮进化，这就是遗传算法的基本原理。 遗传算法的主要步骤如下： 1)随机产生一个由确定长度的特征串组成的初始群体； 2)对串群体迭代地执行步骤(1)和(2)，直到满足停止准则： (1)计算群体中每个个体的适应值。 (2)应用复制、杂交和变异算子产生下一代群体。 3)把在任一代中出现的最好的个体串指定为遗传算法的执行结果。这个结果可以表示问

题的一个解(或近似解)。 基本遗传算法的流程图如图 1-1，其中gen是当前代数，m为每代种群中最大个体数。 图1-1 基本遗传算法的流程图 1.2.2 算法特点

遗传算法的特点如下： 1) 遗传算法中不包含待解决问题所持有的形态。它是从改变基因的配置来实现问题的整

体优化的，因而属于自下而上的优化方法； 2) 类似于生物的进化过程，遗传算法处理的是变量集合的编码而非变量本身。它直接 对结构对象进行操作，不存在求导和函数连续性的限定； 3) 遗传算法具有内在的隐并行性和更好的全局寻优能力； 4) 遗传算法采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整

搜索方向，不需要确定的规则。 遗传算法的这些特点已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控

制和人工生命等领域。它是现代有关智能计算中的关键技术之一。 1.3 基本遗传算法的步骤

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

x=100111001000101101就可表示一个个体，该个体的染色体长度是n=18。 （1）编码：变量x作为实数，可以视为遗传算法的表现型形式。从表现型到基因型的映

射称为编码。设某一参数的取值范围为[u1，u2]，我们用长度为k的 二进制编码符号来表示该参数，则它总共产生2k种不同的编码，可使参数编码时的对应关系为：

000000?0000=0→u1 000000?0001=1→u1+? 000000?0010=2→u1+2? ?

111111?1111=2k-1→u2 u?u其中，?=2 k1。 2?1

（2）解码：假设某一个体的编码为bkbk-1bk-2?b2b1,则对应的解码公式为 x?u1?(?bi?2i?1)?

i?1ku2?u1 ① k2?1 例如：设有参数x∈[2，4]，现用5位二进制编码对x进行编码，得25=32个二进制串（染色体）：

00000,00001,00010,00011,00100,00101,00110,00111 01000,01001,01010,01011,01100,01101,01110,01111 10000,10001,10010,10011,10100,10101,10110,10111 11000,11001,11010,11011,11100,11101,11110,11111 对于任一个二进制串，只要代入公式①，就可得到相应的解码，如x22=10101,它对应的

十进制为?bi?2i?1=1+0*2+1*22+0*23+1*24=21,则对应参数 i?15

x的值为2+21*(4-2)/(25-1)=3.3548。 1.3.2 个体适应度的检测评估 基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代群

体中的机会多少。为了正确估计这个概率，要求所有个体的适应度 必须为非负数。所以，根据不同种类的问题，需要预先确定好由目标函数值到个体适应度之间的转换规律，特别是要预先确定好当目标函数值为负数时的处理方法。例如，可选取

一个适当大的正数c，使个体的适应度为目标函数值加上正数c。 1.3.3 遗传算子

基本遗传算法使用下列三种遗传算子： （1）选择运算使用比例选择算子。比例选择因子是利用比例于各个个体适应度的概率决

定其子孙的遗传可能性。若设种群数为m，个体i的适应度为fi,则个体i被选取的概率为 pi?fi/?fk k?1m

当个体选择的概率给定后，产生[0，1]之间的均匀随机数来决定哪个个体参加交配。若个体的选择概率大，则能被多次选中，它的遗传基因就会在种群中扩大；若个体的选择概率小，则被淘汰。 我们经常采用的是轮盘赌的原理，个体的选择概率是基于它们的性能进行的一些计算。实值范围——总和是所有个体期望的选择概率的总和或当前种群中所有个体原始适应度值的

总和。个体采用一对一方式

映像到范围[0，sum]的一连续区间，每一个体区间的

大小与对应个体的适应度值相匹配。如图1所示，轮 盘赌轮的周长是6个个体适应度值的总和，个体5 是最大适应度个体，它占有最大的区间。选择一个个 体，用在[0，sum]间产生随机数，看此随机数在哪个 个体的区间上，则此个体被选中。重复此过程，直到 所需数量个体被选中为止。 （2）交叉运算使用单点交叉算子。只有一个交叉点位置，任意挑选经过选择操作后种群中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因

码，形成两个子个体，如图2所示。 父个体1 父个体2 110 11 011 00 单点交叉 子个体1 子个体2 图2 单点交叉示意图 （3）变异运算使用基本位变异算子或均匀变异算子。为了避免问题 过早收敛，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0变为1，而1变为0，如图3所示。

变异 图3 变异操作示意图 1.3.4 基本遗传算法的运行参数 基本遗传算法有下列4个运行参数需要预先设定，即m,t,pc,pm。 m为群体大小，即群体中所含个体的数量，一般取为20~100； t为遗传算法的终止进化代数，一般取为100~500； pc为交叉概率，一般取为0.4~0.99; pm为变异概率，一般取为0.0001~0.1。 1.4遗传算法的应用 进入90年代后，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。 遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。如工程结构优化、计算数学、制造系

统、航空航天、交通、计算机科学、通信、电子学、材料科学等。 1)ga在数值优化上的应用 最优化问题是遗传算法经典应用领域，但采用常规方法对于大规模、多峰态函数、含离散变量等问题的有效解决往往存在许多障碍。对全局变化问题，目前存在确定性和非确定性两类方法。前者以brianin的下降轨线法、levy的隧道法和r.ge的填充函数为代表。该类

方法虽然收敛快、计算效率高，但算法复杂，求得全局极值的概率不大。 遗传算法作为现代最优化的手段，实践证明，它应用于大规模、多峰多态函数、含离散

变量等情况下的全局优化问题是合适的，在求解速度和质量上远远超过常规方法。 2)ga 在组合优化中的应用

3)遗传算法在机器学习中的应用 机器学习系统实际上是对人的学习机制的一种抽象和模拟，是一种理想的学习模型。基于符号学习的机器学习系统如监督型学习系统、条件反射学习系统、类比式学习系统、推理学习系统等，只具备一些较初级的学习能力。近年来，由于遗传算法的发展，基于进化机制遗传学习成为一种新的机器学习方法，它将知识表达为另一种符号形式—遗传基因型，通过

模拟生物的进化过程，实现专门领域知识的合理增长型学习。 4)遗传算法在并行处理中的应用

遗传算法固有的并行性和大规模并行机的快速发展，促使许多研究者开始研究遗传算法的并行化问题，研究数量更加接近自然界的软件群体将成为可能。遗传算法与并行计算的结合，能把并行机的高速性和遗传算法固有的并行性两者的长处彼此结合起来，从而也促进了并行遗传算法的研究与发展。

本文来源：https://www.bwwdw.com/article/zdnf.html