遗传算法论文范文
遗传算法论文范文第1篇
论文关键词：遗传算法
1 引言
“物竞天择，适者生存”是达尔文生物进化论的基本原理，揭示了物种总是向着更适应自然界的方向进化的规律。可见，生物进化过程本质上是一种优化过程，在计算科学上具有直接的借鉴意义。在计算机技术迅猛发展的时代，生物进化过程不仅可以在计算机上模拟实现，而且还可以模拟进化过程，创立新的优化计算方法，并应用到复杂工程领域之中，这就是遗传算法等一类进化计算方法的思想源泉。
2 遗传算法概述
遗传算法是将生物学中的遗传进化原理和随[1]优化理论相结合的产物，是一种随机性的全局优算法。遗传算法不但具有较强的全局搜索功能和求解问题的能力，还具有简单通用、鲁棒性强、适于并行处理等特点数学建模论文，是一种较好的全局优化搜索算法。在遗传算法的应用中，由于编码方式和遗传算子的不同，构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同点，Holland的遗传算法常被称为简单遗传算法（简记SGA），简单遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，这种改进的或变形的遗传算法，都是以其为基础[1]。
2.1遗传算法几个基本概念
个体(IndividualString)：个体是遗传算法中用来模拟生物染色体的一定数目的二进制串，该二进制串用来表示优化问题的满意解。
种群(population)：包含一组个体的群体，是问题解的集合。
基因模式(Sehemata)：基因模式是指二进制位串表示的个体中，某一个或某些位置上具有相似性的个体组成的集合，也称模式。
适应度(Fitness)：适应度是以数值方式来描述个体优劣程度的指标，由评价函数F计算得到。F作为求解问题的目标函数，求解的目标就是该函数的最大值或最小值。
遗传算子(genetic operator)：产生新个体的操作，常用的遗传算子有选择、交叉和变异。
选择(Reproduetion)：选择算子是指在上一代群体中按照某些指标挑选出的，参与繁殖下一代群体的一定数量的个体的一种机制龙源期刊。个体在下一代种群中出现的可能性由个体的适应度决定，适应度越高的个体，产生后代的概率就越高。
交叉(erossover)：交叉是指对选择后的父代个体进行基因模式的重组而产生后代个体的繁殖机制。在个体繁殖过程中，交叉能引起基因模式的重组，从而有可能产生含优良性能的基因模式的个体。交叉可以发生在染色体的一段基因串或者多段基因串。交叉概率（Pc）决定两个个体进行交叉操作的可能性数学建模论文，交叉概率太小时难以向前搜索，太大则容易破坏高适应度的个体结构，一般Pc取0.25~0.75
变异(Mutation)：变异是指模拟生物在自然的遗传环境中由于某种偶然因素引起的基因模式突变的个体繁殖方式。在变异算子中，常以一定的变异概率（Pm）在群体中选取个体，随机选择个体的二进制串中的某些位进行由概率控制的变换（0与1互换）从而产生新的个体[2]。如果变异概率太小，就难以产生新的基因结构，太大又会使遗传算法成了单纯的随机搜索，一般取Pm=0.1~0.2。在遗传算法中，变异算子增加了群体中基因模式的多样性，从而增加了群体进化过程中自然选择的作用，避免早熟现象的出现。
2.2基本遗传算法的算法描述
用P(t)代表第t代种群，下面给出基本遗传算法的程序伪代码描述：
基本操作：
InitPop（）
操作结果：产生初始种群，初始化种群中的个体，包括生成个体的染色体值、计算适应度、计算对象值。
Selection（）
初始条件：种群已存在。
操作结果：对当前种群进行交叉操作。
Crossover（）
初始条件：种群已存在。
操作结果：对当前种群进行交叉操作。
Mutation（）
初始条件：种群已存在。
对当前种群进行变异操作。
PerformEvolution（）
初始条件：种群已存在且当前种群不是第一代种群。
操作结果：如果当前种群的最优个体优于上一代的最优本，则将其赋值给bestindi，否则不进行任何操作。
Output（）
初始条件：当前种群是最后一代种群。
操作结果：输出bestindi的表现型以及对象值。
3 遗传算法的缺点及改进
遗传算法有两个明显的缺点：一个原因是出现早熟往往是由于种群中出现了某些超级个体，随着模拟生物演化过程的进行，这些个体的基因物质很快占据种群的统治地位，导致种群中由于缺乏新鲜的基因物质而不能找到全局最优值；另一个主要原因是由于遗传算法中选择及杂交变异等算子的作用，使得一些优秀的基因片段过早丢失，从而限制了搜索范围，使得搜索只能在局部范围内找到最优值，而不能得到满意的全局最优值[3]。为提高遗传算法的搜索效率并保证得到问题的最优解，从以下几个方面对简单遗传算法进行改进。
3.1编码方案
因实数编码方案比二进制编码策略具有精度高、搜索范围大、表达自然直观等优点数学建模论文，并能够克服二进制编码自身特点所带来的不易求解高精度问题、不便于反应所求问题的特定知识等缺陷，所以确定实数编码方案替代SGA中采用二进制编码方案[4]。
3.2 适应度函数
采用基于顺序的适应度函数，基于顺序的适应度函数最大的优点是个体被选择的概率与目标函数的具体值无关，仅与顺序有关[5]。构造方法是先将种群中所有个体按目标函数值的好坏进行排序，设参数β∈(0,1)，基于顺序的适应度函数为：
（1）
3.3 选择交叉和变异
在遗传算法中，交叉概率和变异概率的选取是影响算法行为和性能的关键所在，直接影响算法的收敛性。在SGA中，交叉概率和变异概率能够随适应度自动调整，在保持群体多样性的同时保证了遗传算法的收敛性。在自适应基本遗传算法中，pc和pm按如下公式进行自动调整：
（2）
（3）
式中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f′为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；此处，只要设定k1、k2、k3、k4为（0，1）之间的调整系数，Pc及Pm即可进行自适应调整。本文对标准的遗传算法进行了改进，改进后的遗传算法对交叉概率采用与个体无关，变异概率与个体有关。交叉算子主要作用是产生新个体，实现了算法的全局搜索能力。从种群整体进化过程来看，交叉概率应该是一个稳定而逐渐变小，到最后趋于某一稳定值的过程；而从产生新个体的角度来看，所有个体在交叉操作上应该具有同等地位，即相同的概率，从而使GA在搜索空间具有各个方向的均匀性。对公式（2)和（3）进行分析表明，适应度与交叉率和变异率呈简单的线性映射关系。当适应度低于平均适应度时，说明该个体是性能不好的个体数学建模论文，对它就采用较大的交叉率和变异率；如果适应度高于平均适应度，说明该个体性能优良，对它就根据其适应度值取相应的交叉率和变异率龙源期刊。
当个体适应度值越接近最大适应度值时，交叉概率和变异概率就越小；当等于最大适应度值时，交叉概率和变异概率为零。这种调整方法对于群体处于进化的后期比较合适，这是因为在进化后期，群体中每个个体基本上表现出较优的性能，这时不宜对个体进行较大的变化以免破坏了个体的优良性能结构；但是这种基本遗传算法对于演化的初期却不利，使得进化过程略显缓慢[6]。因为在演化初期，群体中较优的个体几乎是处于一种不发生变化的状态，而此时的优良个体却不一定是全局最优的，这很容易导致演化趋向局部最优解。这容易使进化走向局部最优解的可能性增加。同时，由于对每个个体都要分别计算Pc和Pm，会影响程序的执行效率，不利于实现。
对自适应遗传算法进行改进，使群体中具有最大适应度值的个体的交叉概率和变异概率不为零，改进后的交叉概率和变异概率的计算公式如式（4）和（5）所示。这样，经过改进后就相应地提高了群体中性能优良个体的交叉概率和变异概率，使它们不会处于一种停滞不前的状态，从而使得算法能够从局部最优解中跳出来获得全局最优解[7]。
(4)
(5)
其中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f′为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；pc1为最大交叉概率；pm1为最大变异概率。
3.4 种群的进化与进化终止条件
将初始种群和产生的子代种群放在一起，形成新的种群，然后计算新的种群各个体的适应度，将适应度排在前面的m个个体保留，将适应度排在后面m个个体淘汰数学建模论文，这样种群便得到了进化[8]。每进化一次计算一下各个个体的目标函数值，当相邻两次进化平均目标函数之差小于等于某一给定精度ε时，即满足如下条件：
(6)
式中，为第t+1次进化后种群的平均目标函数值，为第t次进化后种群的平均目标函数值，此时，可终止进化。
3.5 重要参数的选择
GA的参数主要有群里规模n，交叉、变异概率等。由于这些参数对GA性能影响很大，因此参数设置的研究受到重视。对于交叉、变异概率的选择，传统选择方法是静态人工设置。现在有人提出动态参数设置方法，以减少人工选择参数的困难和盲目性。
4 结束语
遗传算法作为当前研究的热点，已经取得了很大的进展。由于遗传算法的并行性和全局搜索等特点，已在实际中广泛应用。本文针对传统遗传算法的早熟收敛、得到的结果可能为非全局最优收敛解以及在进化后期搜索效率较低等缺点进行了改进，改进后的遗传算法在全局收敛性和收敛速度方面都有了很大的改善，得到了较好的优化结果。
参考文献
[1]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999:66-68.
[2]王小平,曹立明.遗传算法理论[M].西安交通大学出版社,2002:1-50,76-79.
[3]李敏强,寇纪淞,林丹,李书全.遗传算法的基本理论与应用[M].科学出版社, 2002:1-16.
[4]涂承媛,涂承宇.一种新的收敛于全局最优解的遗传算法[J].信息与控制,2001,30(2):116-138
[5]陈玮,周激,流程进,陈莉.一种改进的两代竞争遗传算法[J].四川大学学报:自然科学版,2003.040(002):273-277.
[6]王慧妮,彭其渊,张晓梅.基于种群相异度的改进遗传算法及应用[J].计算机应用,2006,26(3):668-669.
[7]金晶,苏勇.一种改进的自适应遗传算法[J].计算机工程与应用,2005,41(18):64-69.
[8]陆涛,王翰虎,张志明.遗传算法及改进[J].计算机科学,2007,34(8):94-96
遗传算法论文范文第2篇
论文关键词：遗传算法
1 引言
“物竞天择，适者生存”是达尔文生物进化论的基本原理，揭示了物种总是向着更适应自然界的方向进化的规律。可见，生物进化过程本质上是一种优化过程，在计算科学上具有直接的借鉴意义。在计算机技术迅猛发展的时代，生物进化过程不仅可以在计算机上模拟实现，而且还可以模拟进化过程，创立新的优化计算方法，并应用到复杂工程领域之中，这就是遗传算法等一类进化计算方法的思想源泉。
2 遗传算法概述
遗传算法是将生物学中的遗传进化原理和随[1]优化理论相结合的产物，是一种随机性的全局优算法。遗传算法不但具有较强的全局搜索功能和求解问题的能力，还具有简单通用、鲁棒性强、适于并行处理等特点数学建模论文，是一种较好的全局优化搜索算法。在遗传算法的应用中，由于编码方式和遗传算子的不同，构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同点，Holland的遗传算法常被称为简单遗传算法（简记SGA），简单遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，这种改进的或变形的遗传算法，都是以其为基础[1]。
2.1遗传算法几个基本概念
个体(IndividualString)：个体是遗传算法中用来模拟生物染色体的一定数目的二进制串，该二进制串用来表示优化问题的满意解。
种群(population)：包含一组个体的群体，是问题解的集合。
基因模式(Sehemata)：基因模式是指二进制位串表示的个体中，某一个或某些位置上具有相似性的个体组成的集合，也称模式。
适应度(Fitness)：适应度是以数值方式来描述个体优劣程度的指标，由评价函数F计算得到。F作为求解问题的目标函数，求解的目标就是该函数的最大值或最小值。
遗传算子(genetic operator)：产生新个体的操作，常用的遗传算子有选择、交叉和变异。
选择(Reproduetion)：选择算子是指在上一代群体中按照某些指标挑选出的，参与繁殖下一代群体的一定数量的个体的一种机制龙源期刊。个体在下一代种群中出现的可能性由个体的适应度决定，适应度越高的个体，产生后代的概率就越高。
交叉(erossover)：交叉是指对选择后的父代个体进行基因模式的重组而产生后代个体的繁殖机制。在个体繁殖过程中，交叉能引起基因模式的重组，从而有可能产生含优良性能的基因模式的个体。交叉可以发生在染色体的一段基因串或者多段基因串。交叉概率（Pc）决定两个个体进行交叉操作的可能性数学建模论文，交叉概率太小时难以向前搜索，太大则容易破坏高适应度的个体结构，一般Pc取0.25~0.75
变异(Mutation)：变异是指模拟生物在自然的遗传环境中由于某种偶然因素引起的基因模式突变的个体繁殖方式。在变异算子中，常以一定的变异概率（Pm）在群体中选取个体，随机选择个体的二进制串中的某些位进行由概率控制的变换（0与1互换）从而产生新的个体[2]。如果变异概率太小，就难以产生新的基因结构，太大又会使遗传算法成了单纯的随机搜索，一般取Pm=0.1~0.2。在遗传算法中，变异算子增加了群体中基因模式的多样性，从而增加了群体进化过程中自然选择的作用，避免早熟现象的出现。
2.2基本遗传算法的算法描述
用P(t)代表第t代种群，下面给出基本遗传算法的程序伪代码描述：
基本操作：
InitPop（）
操作结果：产生初始种群，初始化种群中的个体，包括生成个体的染色体值、计算适应度、计算对象值。
Selection（）
初始条件：种群已存在。
操作结果：对当前种群进行交叉操作。
Crossover（）
初始条件：种群已存在。
操作结果：对当前种群进行交叉操作。
Mutation（）
初始条件：种群已存在。
对当前种群进行变异操作。
PerformEvolution（）
初始条件：种群已存在且当前种群不是第一代种群。
操作结果：如果当前种群的最优个体优于上一代的最优本，则将其赋值给bestindi，否则不进行任何操作。
Output（）
初始条件：当前种群是最后一代种群。
操作结果：输出bestindi的表现型以及对象值。
3 遗传算法的缺点及改进
遗传算法有两个明显的缺点：一个原因是出现早熟往往是由于种群中出现了某些超级个体，随着模拟生物演化过程的进行，这些个体的基因物质很快占据种群的统治地位，导致种群中由于缺乏新鲜的基因物质而不能找到全局最优值；另一个主要原因是由于遗传算法中选择及杂交变异等算子的作用，使得一些优秀的基因片段过早丢失，从而限制了搜索范围，使得搜索只能在局部范围内找到最优值，而不能得到满意的全局最优值[3]。为提高遗传算法的搜索效率并保证得到问题的最优解，从以下几个方面对简单遗传算法进行改进。
3.1编码方案
因实数编码方案比二进制编码策略具有精度高、搜索范围大、表达自然直观等优点数学建模论文，并能够克服二进制编码自身特点所带来的不易求解高精度问题、不便于反应所求问题的特定知识等缺陷，所以确定实数编码方案替代SGA中采用二进制编码方案[4]。
3.2 适应度函数
采用基于顺序的适应度函数，基于顺序的适应度函数最大的优点是个体被选择的概率与目标函数的具体值无关，仅与顺序有关[5]。构造方法是先将种群中所有个体按目标函数值的好坏进行排序，设参数β∈(0,1)，基于顺序的适应度函数为：
（1）
3.3 选择交叉和变异
在遗传算法中，交叉概率和变异概率的选取是影响算法行为和性能的关键所在，直接影响算法的收敛性。在SGA中，交叉概率和变异概率能够随适应度自动调整，在保持群体多样性的同时保证了遗传算法的收敛性。在自适应基本遗传算法中，pc和pm按如下公式进行自动调整：
（2）
（3）
式中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f′为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；此处，只要设定k1、k2、k3、k4为（0，1）之间的调整系数，Pc及Pm即可进行自适应调整。本文对标准的遗传算法进行了改进，改进后的遗传算法对交叉概率采用与个体无关，变异概率与个体有关。交叉算子主要作用是产生新个体，实现了算法的全局搜索能力。从种群整体进化过程来看，交叉概率应该是一个稳定而逐渐变小，到最后趋于某一稳定值的过程；而从产生新个体的角度来看，所有个体在交叉操作上应该具有同等地位，即相同的概率，从而使GA在搜索空间具有各个方向的均匀性。对公式（2)和（3）进行分析表明，适应度与交叉率和变异率呈简单的线性映射关系。当适应度低于平均适应度时，说明该个体是性能不好的个体数学建模论文，对它就采用较大的交叉率和变异率；如果适应度高于平均适应度，说明该个体性能优良，对它就根据其适应度值取相应的交叉率和变异率龙源期刊。
当个体适应度值越接近最大适应度值时，交叉概率和变异概率就越小；当等于最大适应度值时，交叉概率和变异概率为零。这种调整方法对于群体处于进化的后期比较合适，这是因为在进化后期，群体中每个个体基本上表现出较优的性能，这时不宜对个体进行较大的变化以免破坏了个体的优良性能结构；但是这种基本遗传算法对于演化的初期却不利，使得进化过程略显缓慢[6]。因为在演化初期，群体中较优的个体几乎是处于一种不发生变化的状态，而此时的优良个体却不一定是全局最优的，这很容易导致演化趋向局部最优解。这容易使进化走向局部最优解的可能性增加。同时，由于对每个个体都要分别计算Pc和Pm，会影响程序的执行效率，不利于实现。
对自适应遗传算法进行改进，使群体中具有最大适应度值的个体的交叉概率和变异概率不为零，改进后的交叉概率和变异概率的计算公式如式（4）和（5）所示。这样，经过改进后就相应地提高了群体中性能优良个体的交叉概率和变异概率，使它们不会处于一种停滞不前的状态，从而使得算法能够从局部最优解中跳出来获得全局最优解[7]。
(4)
(5)
其中：fmax为群体中最大的适应度值；fave为每代群体的平均适应度值；f′为待交叉的两个个体中较大的适应度值；f为待变异个体的适应度值；pc1为最大交叉概率；pm1为最大变异概率。
3.4 种群的进化与进化终止条件
将初始种群和产生的子代种群放在一起，形成新的种群，然后计算新的种群各个体的适应度，将适应度排在前面的m个个体保留，将适应度排在后面m个个体淘汰数学建模论文，这样种群便得到了进化[8]。每进化一次计算一下各个个体的目标函数值，当相邻两次进化平均目标函数之差小于等于某一给定精度ε时，即满足如下条件：
(6)
式中，为第t+1次进化后种群的平均目标函数值，为第t次进化后种群的平均目标函数值，此时，可终止进化。
3.5 重要参数的选择
GA的参数主要有群里规模n，交叉、变异概率等。由于这些参数对GA性能影响很大，因此参数设置的研究受到重视。对于交叉、变异概率的选择，传统选择方法是静态人工设置。现在有人提出动态参数设置方法，以减少人工选择参数的困难和盲目性。
4 结束语
遗传算法作为当前研究的热点，已经取得了很大的进展。由于遗传算法的并行性和全局搜索等特点，已在实际中广泛应用。本文针对传统遗传算法的早熟收敛、得到的结果可能为非全局最优收敛解以及在进化后期搜索效率较低等缺点进行了改进，改进后的遗传算法在全局收敛性和收敛速度方面都有了很大的改善，得到了较好的优化结果。
参考文献
[1]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999:66-68.
[2]王小平,曹立明.遗传算法理论[M].西安交通大学出版社,2002:1-50,76-79.
[3]李敏强,寇纪淞,林丹,李书全.遗传算法的基本理论与应用[M].科学出版社, 2002:1-16.
[4]涂承媛,涂承宇.一种新的收敛于全局最优解的遗传算法[J].信息与控制,2001,30(2):116-138
[5]陈玮,周激,流程进,陈莉.一种改进的两代竞争遗传算法[J].四川大学学报:自然科学版,2003.040(002):273-277.
[6]王慧妮,彭其渊,张晓梅.基于种群相异度的改进遗传算法及应用[J].计算机应用,2006,26(3):668-669.
[7]金晶,苏勇.一种改进的自适应遗传算法[J].计算机工程与应用,2005,41(18):64-69.
[8]陆涛,王翰虎,张志明.遗传算法及改进[J].计算机科学,2007,34(8):94-96
遗传算法论文范文第3篇
论文摘要：TSP是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(GB—MGA),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际TSP库中多个实例的测试,结果表明:算法(GB—MGA)加快了遗传算法的收敛速度,也加强了算法的寻优能力。
论文关键词：旅行商问题遗传算法基因库多重搜索策略
TSP(travelingsalesmanproblem)可以简述为:有n个城市1,2,…,n,一旅行商从某一城市出发,环游所有城市后回到原出发地,且各城市只能经过一次,要求找出一条最短路线。TSP的搜索空间是有限的,如果时间不受限制的话,在理论上这种问题终会找到最优解,但对于稍大规模的TSP,时间上的代价往往是无法接受的。这是一个典型的组合最优化问题,已被证明是NP难问题,即很可能不存在确定的算法能在多项式时间内求到问题的解[1]。由于TSP在工程领域有着广泛的应用,如货物运输、加工调度、网络通讯、电气布线、管道铺设等,因而吸引了众多领域的学者对它进行研究。TSP的求解方法种类繁多,主要有贪婪法、穷举法、免疫算法[2]、蚂蚁算法[3]、模拟退火算法、遗传算法等。
遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息[4]。遗传算法主要包括选择、交叉和变异3个操作算子,它是一种全局化搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。遗传算法虽然不能保证在有限的时间内获得最优解,但随机地选择充分多个解验证后,错误的概率会降到可以接受的程度。
用遗传算法求解TSP能得到令人满意的结果,但是其收敛速度较慢,而且种群在交叉算子作用下,会陷入局部解。采用局部启发式搜索算法等,虽然能在很短的时间内计算出小规模城市的高质量解,一旦城市规模稍大就容易陷入局部最优解。因此,为了能够加快遗传算法的收敛速度,又能得到更好的近似最优解,该文采纳了文[5]中杨辉提出的基因库的想法,并结合文[6]中Cheng-FaTsai提出的多重搜索策略思想,使用单亲演化与群体演化相结合的方式来求解TSP问题。该文根据文[7]中最小生成树MST(minimumcostspanningtree)的应用,由MST建立TSP的基因库,保存有希望成为最优解的边,利用基因库提高初始群体的质量进行单亲演化,然后利用改进后的交叉算子和的多重搜索策略进行群体演化。
1单亲演化过程
现有的大多数演化算法在整个演化过程中所涉及的基因,大多来源于个体本身,个体质量的高低决定了算法的全局性能,如果群体中初始个体的适应度都较差,肯定要影响算法的收敛速度,对于规模稍大的TSP尤其明显[8]。该文为了克服上述弱点,首先利用普里姆算法求出TSP中最小生成树,并将各个MST中的每一条边都保存在一个n*(n-1)方阵里面,就构成了一个基因库,在生成初始群体的时候尽量使用基因库中的基因片段,来提高整个初始群体的适应度,从而提高算法的效率。
1.1TSP编码表示
设n个城市编号为1,2,…,n,为一条可行路径,Pk=Vk1Vk2…Vkn为一条可行路径,它是1,2,…,n的一个随机排列,其含意是第k条路径起点城市是Vk1,最后一个城市是Vkn,则第k条环路的总长度可以表示为:
其中,d(Vki,Vkj)表示城市Vki与城市Vkj之间的距离。在算法中环路Pk的总长d(Pk)用来评价个体的好坏[9]。适应度函数取路径长度d(Pk)的倒数,f(Pk)=1/d(Pk)。
1.2构建TSP基因库
对n个编号为1,2,…,n的城市,根据它们的坐标计算各城市之间的欧氏距离d(i,j),i,j=1,2,…,n,得到一个n*n的方阵D={d(i,j)}。然后利用普里姆算法求得该TSP的一棵MST,并将这棵MST中的每一条边e(i,j)对应地存储在一个n*(n-1)的方阵M={e(i,j)},即该文的基因库。由于一个TSP可能有多棵MST,操作可以重复多次,这样生成的基因库中的基因就更多,增强了初始群体的全局性。具体算法如下:
VoidMiniSpanTree—PRIM(MGraphG,VertexTypeu){
Struct{
VertexTypeadjvex;
VRTypelowcost;
}closedge[MAX—VERTEX—NUM];
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j)
if(j!=k)closedge[j]={u,G.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=0;i<G.vexnum;++i){
k=minimum(closedge);
printf(closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
1.3单亲演化算法
单亲演化算法是利用遗传算法的优胜劣汰的遗传特性,在单个染色体内以基因重组的方式,使子代在满足TSP问题的限定条件下进行繁衍,然后保留适应度高的染色体种群,达到优化的目的。单亲演化算法的基因重组操作包括基因换位、基因段错位和基因段倒转三种操作来实现。基因换位操作是将亲代的染色体基因进行对换后,形成子代,其换位又分为单基因换位和基因段换位两种方式。基因段错位操作是随机确定基因段,也随机选定错位位置,整段错移。基因段倒转操作则是随机地确定倒转基因段的起止位置,倒转操作是对该段内基因按中垂线作镜面反射,若段内基因数为奇数时,则中位基因不变。单亲演化时可以是单个操作用于单个父代,也可以是几种操作同时采用。为了编程方便,文中采用基因段倒转操作。
2群体演化过程
在单亲演化算法求得的初始群体基础上,再利用多重搜索策略并行地进行群体演化,这样在保证算法的快速收敛的同时也注重了搜索空间的全局性。
2.1交叉算子
该文算子采用一种与顺序交叉OX(ordercrossover)法类似的交叉方法[11],即随机在串中选择一个区域,例如以下两个父串及区域选定为:
P1=(12|3456|789)P2=(98|7654|321)
将P2的区域加到P1的前面或后面,P1的区域加到P2的前面或后面,得
M1=(7654|123456789)
M2=(3456|987654321)
在M1中自区域后依次删除与区域相同的城市码,得到最终的两个子串:
S1=(765412389)S2=(345698721)
同时为了能更好地增强算子的全局搜索能力,对该算子作了如下的改进。子代个体的新边来自:随机生成和群体中其他个体,其选择比例由随机数p和阈值P来决定。如果随机数p小于阈值P,则子代个体的新边来自随机生成,否则就来自群体中的其他个体。
这种改进后的交叉算子在父串相同的情况下仍能产生一定程度的变异效果,这对维持群体的多样化特性有一定的作用。实验结果也证实了这种改进算子对于种群的全局搜索能力有一定的提高,避免搜索陷入局部解。
2.2局部启发式算子
为了增强遗传算法的局部搜索性能,在算法中引入2-Opt局部搜索算子[12]。该算子通过比较两条边并交换路径以提升算法的局部搜索性能,示例见图2。
比较子路径ab+cd和ac+bd,如果ab+cd>ac+bd则交换,否则就不交换。考虑到程序的运行效率,不可能对每对边都做检查,所以选取染色体中的一定数量的边进行比较。2-Opt搜索算子实际上进行的相当于变异操作,同时又不仅仅是简单的变异,而是提高算法的局部搜索性能的变异操作。
2.3选择机制和收敛准则
为了限制种群的规模[13],该文采用了联赛选择法的淘汰规则。联赛选择法就是以各染色体的适应度作为评定标准,从群体中任意选择一定数目的个体,称为联赛规模,其中适应度最高的个体保存到下一代。这个过程反复执行,直到保存到下一代的个体数达到预先设定的数目为止。这样做可能导致种群过早收敛,因此在收敛准则上要采取苛刻的要求来保证搜索的全局性。
遗传算法求TSP问题如果不设定终止条件,其演化过程将会无限制地进行下去。终止条件也称收敛准则,因为多数最优化问题事先并不了解最优的目标函数值,故无法判断寻优的精度。该文采用如下两条收敛准则:在连续K1代不再出现更优的染色体;优化解的染色体占种群的个数达K2的比例以上。当两准则均满足时,则终止运算,输出优化结果和对应的目标函数值。由数值实验表明,添加第2条准则之后,全局最优解的出现频率将大为提高。
2.4基于多重搜索策略的群体演化算法
由于基因库的引入,可能降低初始种群的多样性,为避免算法陷入局部最优解,因此在群体演化中采取多重搜索策略。由Cheng-FaTsai提出的多重搜索策略[6],就是把染色体集中的染色体分成保守型和探索型两种不同类型的集合,然后针对不同类型的染色体集合根据不同的交叉、变异概率分别进行交叉变异操作,对保守型染色体集合就采用比较低的交叉变异概率,而对探索型染色体集合就采用比较高的交叉变异概率。这种策略对保守型染色体集合的操作最大限度地保留了父代的优秀基因片段,另一方面对探索型染色体集合的操作又尽可能地提高了算法的全局搜索能力。为了提高算法的收敛速度,初始染色体集合该文采用了前面单亲演化的结果中的染色体集合,交叉算子则利用的是前面介绍的改进后的算子,改进后的多重搜索策略见下。
3实验结果与分析
该文的GB—MGA算法由C#编程实现,所有的结果都是在P42.0G微机上完成,并进行通用的TSP库实验,选用了具有一定代表性的TSP实例,并把该算法和其他算法做了一个对比。为了减少计算量,程序中的数据经过四舍五入整数化处理,与实数解有一定的偏差,下面给出图Kroa100的示例。
为了证明该文提出的GB—MGA算法的有效性,将该文算法与典型的遗传算法GA、单亲遗传算法PGA以及文[5]中杨辉提出的Ge—GA(genepoolgeneticalgorithm)算法和文[12]中提出的MMGA(modifiedmultiple-searchinggeneticalgorithm)算法都进行了一个对比。
实验结果证明,该文算法的求解质量要优于GA、PGA、MMGA算法,而求解速度方面则优于Ge—GA算法,特别是对于大规模城市的TSP问题求解效果尤其明显,具有快速收敛的特性。Ge—GA算法对于中等城市规模的TSP实例求解,其运算时间就大幅度增加,如果把该算法用于求解大规模和超大规模TSP问题,那么时间上的代价就让人无法忍受。而该文的GB—MGA算法在单亲遗传演化中就使用了基因库中的优质基因,使得单个个体的进化速度大大提高,从而为进一步的演化提供了条件,群体演化过程的选择机制和收敛准则的恰当选取使得算法在注重了求解质量的同时兼顾了算法的效率。
4结束语
遗传算法论文范文第4篇
关键词：遗传算法，混沌，图像分割
0引言
遗传算法是一种全局优化搜索算法，它使用了群体搜索技术，用种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新的一代种群，并逐渐使种群进化到包含最优解或近似最优解的状态。近几年来借助于混沌改进遗传算法的性能是遗传算法领域研究的热点之一，遗传算法和混沌优化的组合,可以使遗传算法的全局寻优能力，搜索精度，搜索速度等几方面得到较明显的改进。
1混沌的特征和虫口方程
混沌是存在于非线形系统中的一种较为普遍的现象，具有遍历性、随机性等特点，混沌运动能在一定的范围内按照其自身的规律不重复地遍历所有状态。因此，如果利用混沌变量进行优化搜索，无疑会比随机搜索更具有优越性。科技论文。
描述生态学上的虫口模型Logistic映射自May于1976年开始研究以来，受到了非线形科学家的高度关注，Logistic映射是混沌理论发展史上不可多得的典范性的混沌模型，如下式所示：
2混沌遗传算法
基于混沌遗传算法的二维最大熵算法基本步骤如下：
1.设置混沌遗传算法的种群规模以及最大进化代数；
2.生成初始群体。随机产生S 和T ,其中, S ,T ∈(0 ,1) 。然后利用式
计算每个个体的适应值。式（2-1）中的s 和t 分别由以下公式确定：s =(int)( S*255) ，t = (int)(T*255) 。对初始种群执行混沌扰动，如果在C1 步之内找到更优个体，则替换原来的个体，否则保留原个体。科技论文。混沌扰动方式按式(1-1)进行。
3.如果当前进化代数大于G，转步骤5，否则执行变异操作。变异方式按如下公式进行：
其中，fRandom()产生（0,1）之间的随机数，如果变异后的个体具有更优的适应值,则把该个体加入当前种群；
4.执行混沌操作。如果在C2 步之内找到更优解,则替代原来的个体, 否则保留原个体。混沌扰动按公式(1-1)进行。结束后转步骤6。
5. 在较小范围内执行混沌扰动。扰动方式：
其中m1,m2为混沌变量，且m1,m2∈（0,1）。如果变异后的个体具有更优的适应值, 则替换原来的个体,否则保留原个体。
6.按规定的种群规模直接选择最优个体进入下一代。
7.如果满足终止条件, 返回最优解, 否则从步骤3重复上述过程。
8.利用最优解分割图像。
3实验结果与分析
为了检验本算法的效果，用文中提出的基于混沌遗传算法（以下简称为B算法） 和基于传统遗传算法的二维最大熵算法（以下简称为A算法）对Couple.bmp 图像进行了实验比较。科技论文。当文中算法和基于传统遗传算法的二维最大熵算法中各取最大进化代数为10 时,分割效果如图3、4所示。
图1 Couple 原图图2 Couple图像直方图
图3 A算法结果图图4 B算法结果图
4结论
混沌遗传算法是混沌思想与遗传算法思想的结合，比传统遗传算法具有更好的群体多样性、更强的全局寻优能力。文中将混沌遗传算法与二维最大熵图像分割算法结合，应用于图像分割，对比于基于传统遗传算法的二维最大熵算法，文中算法具有更强的稳定性,更快的执行速度，分割效果好。
参考文献
[1]吴薇，邓秋霞，何曰光．基于免疫遗传算法的图像阈值分割．纺织高校基础科学学报，2004，17(2)：160-163
[2]薛景浩，章毓晋，林行刚．二维遗传算法用于图像动态分割．自动化学报，2000，26(5)：685-689
[3]王小平，曹立明．遗传算法－理论、应用与软件实现．西安交通大学出版社．2002
遗传算法论文范文第5篇
关键词：遗传算法，混沌，图像分割
0引言
遗传算法是一种全局优化搜索算法，它使用了群体搜索技术，用种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新的一代种群，并逐渐使种群进化到包含最优解或近似最优解的状态。近几年来借助于混沌改进遗传算法的性能是遗传算法领域研究的热点之一，遗传算法和混沌优化的组合,可以使遗传算法的全局寻优能力，搜索精度，搜索速度等几方面得到较明显的改进。
1混沌的特征和虫口方程
混沌是存在于非线形系统中的一种较为普遍的现象，具有遍历性、随机性等特点，混沌运动能在一定的范围内按照其自身的规律不重复地遍历所有状态。因此，如果利用混沌变量进行优化搜索，无疑会比随机搜索更具有优越性。科技论文。
描述生态学上的虫口模型Logistic映射自May于1976年开始研究以来，受到了非线形科学家的高度关注，Logistic映射是混沌理论发展史上不可多得的典范性的混沌模型，如下式所示：
2混沌遗传算法
基于混沌遗传算法的二维最大熵算法基本步骤如下：
1.设置混沌遗传算法的种群规模以及最大进化代数；
2.生成初始群体。随机产生S 和T ,其中, S ,T ∈(0 ,1) 。然后利用式
计算每个个体的适应值。式（2-1）中的s 和t 分别由以下公式确定：s =(int)( S*255) ，t = (int)(T*255) 。对初始种群执行混沌扰动，如果在C1 步之内找到更优个体，则替换原来的个体，否则保留原个体。科技论文。混沌扰动方式按式(1-1)进行。
3.如果当前进化代数大于G，转步骤5，否则执行变异操作。变异方式按如下公式进行：
其中，fRandom()产生（0,1）之间的随机数，如果变异后的个体具有更优的适应值,则把该个体加入当前种群；
4.执行混沌操作。如果在C2 步之内找到更优解,则替代原来的个体, 否则保留原个体。混沌扰动按公式(1-1)进行。结束后转步骤6。
5. 在较小范围内执行混沌扰动。扰动方式：
其中m1,m2为混沌变量，且m1,m2∈（0,1）。如果变异后的个体具有更优的适应值, 则替换原来的个体,否则保留原个体。
6.按规定的种群规模直接选择最优个体进入下一代。
7.如果满足终止条件, 返回最优解, 否则从步骤3重复上述过程。
8.利用最优解分割图像。
3实验结果与分析
为了检验本算法的效果，用文中提出的基于混沌遗传算法（以下简称为B算法） 和基于传统遗传算法的二维最大熵算法（以下简称为A算法）对Couple.bmp 图像进行了实验比较。科技论文。当文中算法和基于传统遗传算法的二维最大熵算法中各取最大进化代数为10 时,分割效果如图3、4所示。
图1 Couple 原图图2 Couple图像直方图
图3 A算法结果图图4 B算法结果图
4结论
混沌遗传算法是混沌思想与遗传算法思想的结合，比传统遗传算法具有更好的群体多样性、更强的全局寻优能力。文中将混沌遗传算法与二维最大熵图像分割算法结合，应用于图像分割，对比于基于传统遗传算法的二维最大熵算法，文中算法具有更强的稳定性,更快的执行速度，分割效果好。
参考文献
[1]吴薇，邓秋霞，何曰光．基于免疫遗传算法的图像阈值分割．纺织高校基础科学学报，2004，17(2)：160-163
[2]薛景浩，章毓晋，林行刚．二维遗传算法用于图像动态分割．自动化学报，2000，26(5)：685-689
[3]王小平，曹立明．遗传算法－理论、应用与软件实现．西安交通大学出版社．2002
遗传算法论文范文第6篇
关键词:遗传算法,分类器,分类优化,集成学习
中图分类号:TP18文献标识码:A文章编号:1009-3044(2009)33-9615-02
Discuss the Method of Classification with Genetic Algorithm
WANG Xin-Xin
(Software College, MinJiang University, FuZhou 350011, China)
Abstract: In the classifier system, applied genetic algorithm(GA) to optimized the classifier system which is use a single classify method or multiple classify methods. For the first classifier system, GA make the better precision; and for the other one, GA can make the classifier system to be more precise and apprehensive.
Key words: genetic algorithm(GA); classifier system; classify optimization; ensemble learning
分类问题是集成学习的基本研究问题,即对一个分类器输入一个实例的特征集,然后对这些特征进行判断,对这个样本进行归类并输出。在医疗诊断、语音识别、数据挖掘、人像识别等领域都有广泛的应用。
J.H.Holland于1975年出版了《Adaptation in Natural and Artificial Systems》[1],标志着遗传算法的正式产生。遗传算法是一种概率搜索算法,利用编码技术作用于被称为是染色体的二进制数串,其基本思想是模拟这些串组成的群体的进化过程。遗传算法通过有组织的然而是随机的信息交换来重新组合那些适应性好的串,在每一代中,利用上一代串结构中适应性好的位和串来生成一个新的串的群体。这是一类随机算法,但不是简单地随机走动,而是利用已有的信息来搜寻那些有希望改善质量的串,这个过程类似于自然进化。[2]
1 遗传算法的特点
与其他传统的优化算法相比,遗传算法在搜索的过程中采用群体搜索方式,有利于达到全局最优。依据个体相对优劣的适应度指标进行搜索,即使所定义的适应函数存在不连续、不规则或有噪声等情况,也可进行处理。通过在遗产算法中使用杂交算子,可将算法的注意力更多地集中到搜索空间中期望值高的那部分;同时,为了避免局部最优,在遗传算法中引入变异,这样既可在当前附近找到更好的解得同时保持群体多样性,有利于群体的继续优化。[2]
但是,由于进化的过程具有随机性,遗传算法搜索的结果具有一定的不稳定性,因此,与传统的优化算法相比,遗传算法的优化效率相对较低。[3]
2 基于遗传算法的分类优化方法
文献[4]中提出了一种基于遗传算法的分类优化方法。该方法针对两种分类器进行优化。一种分类器采用一种分类方法,使用遗传算法对分类结果进行优化。另一种是在分类器中使用几种不同的分类方法,使用遗传算法作为综合方法对分类结果进行综合优化。在一套训练集上使用一种方法,由此产生一个唯一的模型,不同的方法在同一套训练集上产生的模型也不一定相同。有些方法在某一类任务上的性能很好,但是在另外一类任务上的性能则较差,它们的预测结果有可能是错的,因此使用遗传算法可以将多种分类方法结合起来提高精度。
2.1 数据和算法集的定义
数据集合L={xn,yn},n=1,…,N},其中,xi是输入属性,yi是输出属性,N是例子数目。设有M个学习算法,分别用A1,A2,…,AM表示。A(R,S),其中A是算法,R是算法空间,S是算法搜索的空间。算法对数据集合进行学习,得到不同的学习结果,利用遗传算法对这些结果进行结合,得到一个综合结果。
2.2 基于遗传算法的组合方法框架
在L0层中,每个算法对输入的训练集数据进行训练,各自生成一套对分类问题的表示,利用规则产生器对将L0层中关于分类问题的表达转换为规则,然后作为L1层的输入。在L1层中使用遗传算法对规则集进行综合,生成最终分类器。这种方法综合各分类器的优点,其结果精度高于各单个分类器,用规则集表示其结果。
2.3 如何使用遗传算法对规则进行优化
1) 编码表示
GlodBerg在上个世纪80年代对遗传算法进行归纳,在文献[5]中总结了遗传算法的基本框架。根据该算法,一个个体代表问题的一组解,每一个个体含有表达全部解的一组规则集。规则由条件和结论组成:“if (x1,y1) and (x2,y2),…,and (xn,yn) then Cj”每一个规则用一个染色体表示。
2) 适应函数
适应函数由匹配值和不匹配值两个参数组成,当分类器能对规则进行正确识别并与结果匹配,则增加匹配值;若不能,则增加不匹配值;如果条件无法识别,则这两个参数都不变。
3) 选择策略
利用遗传算法来产生新的规则,采用限制策略,对于同类规则,可进行进化,而对于结论相同的规则,则只在其条件部分进行进化。对于结论相同的规则只在条件部分进行进化的目的是为了防止出现不收敛的情况。
4) 遗传算子
选择算子:选择算子从群体中选择优秀的个体,淘汰劣质的个体,将适应度高的候选解遗传到下一代。在选择的过程中以适应度为依据进行选择,独立于编码方式。
杂交算子:杂交是按照一定的概率将两个父代个体的部分结构加以交换重组,然后产生新的个体。在本文中,个体间同类规则的相同基因位进行交叉。
图2对遗传算法的交叉算子进行描述。
变异算子:变异算子使个体中某些基因发生突变,遗传算法中的变异运算通过位的取反操作实现。在本文中,通过对属性边界值进行突变实现。图3描述了变异算子。
5) 终止规则
遗传算法循环执行计算适应值,选择复制和应用杂交和变异算子几个步骤,直到找到满足条件的解。
3 优化结果讨论
3.1 对使用一种分类方法的分类器进行优化
文献[4]表明,遗传算法优化后的精度优于使用单个算法的精度。对于属性值十分接近的分类目标,使用单一属性生成的规则进行区分是很难实现的,而只有采用属性值的组合才能实现这类分类目标的区分。
3.2 对使用多种分类方法的分类器进行优化
在文献[4]中,使用遗传算法对基于C5.0和神经网络的规则集进行优化。优化后,得到两套规则集,基于C5.0的规则集边界值发生改变,新的规则在精度上比原来更高。而基于神经网络的规则集在形式上没有发生改变。对两种规则集进行比较,发现基于C5.0的规则集和基于神经网络的规则集均具有较高的精度,但是从理解性的方面考虑,基于C5.0的规则集既有较好的可理解度。
4 小结
该文讨论了一种基于遗传算法的分类器优化方法,在分类技术中结合遗传算法可以得到更好的分类效果,得到的分类结果更精确、易于理解。用分类技术处理原始数据集从而得到初步的规则集,而遗传算法通过优化规则条件的部分边界值提高了分类的精度。这种方法具有较好的鲁棒性和可延展性,当给定的边界值与其正确的位置相距很远,也可通过遗传算法对全局进行搜索得到解空间的最优解;如果在分类器中采用新的分类方法,可将分类的结果转化为规则集作为遗传算法输入,这些新的规则集与已有的规则集一起进行演化,从而得到更好的结果。
参考文献:
[1] Holland J H. Adaptation in Natural and Artificial Systems[M]. MIT Press,1992.
[2] 刘勇,康立山,陈毓屏.非数值并行算法遗传算法[M].2册.北京:科学出版社,1995.
[3] 孙瑞祥,屈梁生.进化计算的过去、现在与未来[C]//进化计算研究生论坛论文集.西安:西安交通大学,2001.
遗传算法论文范文第7篇
【关键词】自动控制；遗传算法；应用
遗传算法是自然选择的基础上，基于基因遗传原理的随机的搜索算法，是在微型的计算机上进行模拟生物进化而产生的一门新兴的专业。随着计算机技术和现代控制学的不断发展，工程控制师面临着越来越多的挑战，对优化自动化控制的处理算法提出了要求。而遗传算法作为一种仿生算法，具有成熟度极高的鲁棒性和适用性，得到了控制工程师的青睐。近年来，将遗传算法应用在自动控制化的领域里的工程师越来越多，如，鲁棒、滑模、神经网络、PID控制等等许多方面都得到了广泛的应用。本文将会对几种遗传算法在自动控制中的应用进行分析。
1.遗传算法概论
遗传算法是基于达尔文的自然选择理论衍生出来的。达尔文认为，自然界的一切生物都是通过自身物种的演化来不断适应新的生存环境，遗传算法正是这种理论上，通过现代计算机的模拟而发展出的，它吸取了达尔文的物竞天择适者生存的观点，使得遗传算法能够为系统提供一种在复杂空间进行随机搜索的方法，并且从这些方法中优化出最适应的解决途径。遗传算法在串之间进行有组织但是又很随机的信息交换，随着算法的进行，好的优良的部分会被不断地传承下来，而坏的部分会被不断的淘汰，因而受到很多工程控制师的喜爱将它应用在自动控制的领域里。
2.遗传算法在自动控制领域的应用
遗传算法于自动控制的领域里的应用主要可以分为两种，一是在线自适应调节，二是离线设计分析。其中离线应用还可以被分为两种，即直接涉及法、间接设计法。在第一个直接设计法里，遗传算法是被用来当作优化和搜索的引擎，像是对于一个已知被控对象来选择一个合适他的控制的结构或者是优化一个特定的控制器参数的设置来满足它在性能指标上的要求。在第二个间接设计法例，用传统方法做其他部分，而遗传算法为这个系统提供优化参数。遗传算法在线自适应调节中的应用主要也可分为两类，一种是直接用遗传算法优化控制器参数，构成了有遗传算法作为自适应控制器的自适应优化的机制；一种是把遗传算法作为一种可以辨识未知和时变的特征参数的学习机制，调整自适应控制器。
2.1最优控制
遗传的算法于最优控制的方面得到较广泛的应用。控制的大多数问题都可以解释为寻找在不同的系统当中所对应的一组最优的控制。传统的方法都存在对输入的初始值敏感，收敛速度慢，易陷入局部很小的缺点。而遗传算法在这方面比传统的方法表现好的多。在对离散时间的最优控制的问题上的研究表明，遗传算法在这个问题上的结果比传统算法好很多。在手推车问题、收获问题等问题上的成功证明遗传算法在最优控制上具有很大的潜力，未来遗传算法也将更多地在最优控制这个问题上更好地表现。
2.2模糊控制系统
不论是经典的还是现代的控制理论都能够很好的处理精确的数学模型的系统，但在实际的应用当中，每个系统不可能样样都精确，存在很多模糊值，操作的难度十分大。模糊推理方法是在控制系统没有模型估计的基础上建立起来的控制系统的有效工具之一，这是基于规则的系统把模糊的语言变量输入规则集合之中，来对人的经验和方法进行建模。传统中，这种方法例的模糊规则的制定和调整都要有专家来，这样非常耗时和困难。科学家就将遗传算法应用到模糊控制里，大大的提高了效率。遗传算法对于提升模糊控制器静态和动态的性能起了很大的推动作用，应用性十分强，在模糊控制应用的领域遗传算法的前景很广。
2.3非线性控制
控制系统设计里，有许多控制的问题可以算入优化的大框架中。在实际问题中问题往往比较约束和呈非线性，不同的参数的组合却有可能会得到相同的控制作用。传统方法中对于初次输入的值很敏感，容易陷入困境。而遗传算法由于不用指数函数微分，所以用遗传算法设计出来的自动化方法可以考虑实际中系统很多的性能方面的要求，并且可以直接设计出非线性对象线性控制器，这是传统方法做不到的，基于这个优点，在非线性控制中，遗传算法得到了推广。
3.结语
随着人类科技的发展，自动化技术的应用越来越广泛，而遗传算法作为优化自动化控制的重要方法，应该得到广大控制工程师的重视，不断地发展和改进遗传算法，使其能够更好的应用到自动化控制的领域中。使用遗传算法优化自动化控制是大势所趋，因为它的计算都是在计算机的辅助下完成，减少了人为因素的影响，使得设计的自动化程度得到了提高，所以遗传算法是工程设计师们设计系统的一个不错选择。
【参考文献】
[1]张绍红，毛尚旭，宁书年.模拟退火法和遗传算法联合优化技术及在反演解释中的应用[J].煤炭学报，2007（01）.
遗传算法论文范文第8篇
关键词：高层建筑；传感器优化布设；遗传算法
随着社会的不断发展、人口的增加、土地的减少，高层建筑越来越受到人们的重视和普及。由于高层建筑结构在长期的外界条件（例如地震，台风等）作用下，会给结构造成很大的变形。因此，建筑结构的抗震显得极其重要。近年来，在传感器配置上，王龙玲，何福添[1]提出了基于改进模态应变能法对传感器进行优化布设；金中凡[2]等通过振型贡献率和遗传算法确定传感器的数量和位置，实现传感器的优化布置。
1 模态置信度MAC矩阵
要进行传感器的优化配置，首先要确定合理并能反映设计要求的优化配置准则。因为振型直接关系着结构在地震作用下的变形特征，所以在选择合理的测点位置时，应该首先考虑振型的影响。在目前的研究中，通常是选取模态置信度矩阵非对角元素最大值作为目标函数。
2 改进自适应遗传算法
遗传算法[3]是Holland教授提出来的，其基本思想是模拟生物进化的方法，优胜劣汰的原则，求解复杂的优化问题。
2.1 遗传算法编码
采用二维数组对遗传算法的解群体进行编码。二位数组的行数代表了可行解群的数量，列数则代表了可行解每个个体的长度，每个元素是对应的传感器位置。
2.2 适应度函数
遗传算法在搜索进化的过程中直接用适应度来评估解的优劣，并以此作为遗传算法的依据。本文力求使MAC矩阵的最大非对角元极小化作为目标函数转化为适应度函数的最大化问题来求解。MAC矩阵非对角元的最大值为1，因此构造的适应度函数为：
2.3 自适应交叉和变异
交叉概率Pc和变异概率Pm对遗传算法的性能有着重要影响。为了克服传统遗传算法早熟、收敛慢等不足，本文采用自适应遗传算法。其计算公式分别为[4]：
式中：取
2.4 遗传算子及最优保存策略
交叉操作用于组合出新的种群。这里采用自适应部分匹配交叉策略（PMX），PMX操作只针对个体的上行附加码，交叉操作完成后即可生成两个子个体。
变异操作通过随机改变种群中某些个体的某些基因而产生新个体，本文采用自适应逆位操作，首先是在个串上随机的选择两个点，位串染色体被分成三段，将中间段的左右顺序倒转过来与另两段相连，形成新的个串。在遗传过程中选择出个体适应度强的操作叫做选择。本文采用赌方式进行选择，并采取最优保存策略来保留最有个体。
3 算例
本文以某高层建筑混凝土框架结构传感器布置为例，验证本文提出的改进遗传算法的可行性。该建筑结构为20层，层高4m，楼板和层盖厚度200mm，框架柱截面尺寸为0.5m×0.5m，横梁截面尺寸为0.3m×0.6m。利用有限元分析软件ANSYS 14.0建立有限元模型，进行了模态分析。
考虑到结构的低阶模态具有较大的振型参与系数，且损伤诊断以低阶模态为依据。因此只选择前5阶模态作为优化的目标，频率和振型描述分别如下：1.7725、1.9044、2.007、2.2257、2.3445。
本文遗传算法的循环次数为20，遗传种群规模取100，最大进化代数为100，通过遗传算法的优化计算，最终求得的适应度最大值为0.99963，即模态置信度矩阵（MAC）最大非对角元值为0.0082，其结果表明该算法有很好的优化效果，具有极大的可行性。
4 结论
为了解决高层建筑结构中的传感器优化布置问题，本文采用改进自适应遗传算法，得到以下主要结论：⑴在构造初始种群编码时，只保留可行解，解决了传感器数目固定的约束问题，以最经济的传感器数量，确保结构抗震控制监测造价。⑵采用部分匹配交叉和逆位变异，确保新产生的个体均为可行解；同时采用自适应的交叉概率和变异概率，在保持群体多样性的同时又保证了遗传算法的收敛性，避免出现过早收敛的现象，确保布置结果收敛于全局最优解。
[参考文献]
[1]王龙玲，何福添.基于改进模态应变能法的传感器布置分析[J].科协论坛，2012（3）：103-104.
[2]金中凡.基于振型贡献率和遗传算法的传感器布设研究[J].武汉工程大学，2010.32（12）：52-55.
遗传算法论文范文第9篇
关键词：智能桁架；振动控制；模糊控制器；模糊规则；遗传算法
中图分类号：TU323.4文献标识码： A 文章编号：
引言：
近年来，大型智能桁架结构在航空航天领域得到越来越多的应用。其模型具有不确定性，模型结构和参数在很大范围内变化，基于精确模型的传统控制理论和现代控制理论都有局限性[1]。模糊控制不依赖于被控系统的精确数学模型，而是通过对系统动态特征的定性认识、直接推理、在线确定或变换控制策略，以达到对复杂的、非线性的、不确定性的被控系统的控制，这种方法容易实现，也更加易于保证其实时性。2005年，赵国伟等[2]将PID和LQG成功的应用于大型空间复杂智能桁架结构的振动主动控制上，2009年，张京军等[3]将模糊控制应用于智能悬臂梁的控制当中。本文基于对智能桁架结构模型的认识与分析，设计出相应的模糊控制器，并采用遗传算法对其控制规则进行优化，然后通过一实例仿真验证该方法的有效性。
1智能桁架结构有限元模型
设智能桁架结构中共有个压电主动杆，考虑压电主动杆的机电耦合特性，基于有限元法，建立智能桁架结构的运动方程: （1）
式中，、、分别为质量矩阵、阻尼矩阵和刚度矩阵、、分别为加速度矢量、速度矢量和位移矢量；是由主动杆的方向余弦组成的向量矩阵；为外部节点力矢量；是维主动杆产生的控制力向量。
为简化结构的仿真模型，对智能桁架结构的动力学模型做模态截断处理,则其独立模态空间的动力学方程及观测方程为：
（2）
（3）
式中，、、，，为第阶振动的固有频率，为第阶的模态阻尼比，为外界干扰力，为维模态控制力，其中为模态向量矩阵，为对角阵，为第个作动器单位压电作用下产生的控制力，为对角阵，为第个主动杆等效刚度，为模态坐标，为作动电压。
2.模糊控控制器的设计
目前振动控制中常用的模糊控制器多为双输入-单输出的结构形式。本文采用的也是这种结构模式，其输入输出变量分别为智能桁架的结构位移、速度和对其施加的控制反力。这三个变量都要从物理论域量化到整数论域上，然后再在整数论域上给出若干语言变量值，从而实现整个论域元素的模糊化过程。本文将位移和速度作为误差和误差变化率。设量化值、有统一论域，的论域为。为表达控制规则需先确定输入变量、输出变量的词集，为了简化设计过程，设计量化后的误差、误差变化、控制量的词集均为：负大（NB）、负中（NM）、负小（NS）、零（ZO）、正小（PS）、正中（PM）、正大（PB）。在模糊化时，输入变量选择三角形和梯形的隶属函数，输出变量选择三角形隶属函数。模糊控制规则直接影响到控制系统的性能，本文根据桁架的位移、速度和控制力之间的关系，总结出用语言值表示的二维控制规则表，见表1.
表1 二维模糊控制器控制规则表
模糊推理采用Mandain法，清晰化采用重心法。
3.遗传算法优化控制规则
利用遗传算法进行优化求解时，首先要对控制规则进行编码，然后选择合适的适应度函数，通过复制、交叉、变异等遗传操作，获取最佳种群，。该种群中最优个体为优化问题的解，即为最优模糊规则。
3.1 遗传编码
遗传算法中常见的编码方法有二进制编码和十进制编码。本文将采用十进制编码方法对模糊控制规则进行编码，用数字集{1,2,3,4,5,6,7}来依次表示模糊语言集{ NB，NM，NS，0，PS，PM，PB }，即对设计的控制规则进行数值化，按从左到右，从上至下的顺序把控制规则展开成一维形式，这样便形成了遗传算法所需要的个体。前面设计的控制器含有49条控制规则，即是含有49个待寻优参数，这样每个染色体就包含有49个遗传基因，每个染色体长度也就是49位。对其进行数字化处理后可以表示为染色体表2
表2 染色体表
3.2 适应度函数选择
要想利用遗传算法对控制规则进行优化，首先要解决种群个体的评估问题。本文研究的是智能桁架结构的模糊控制，其控制目标是在激励荷载作用下使得桁架结构的振幅达到最小、衰减随度达到最快。本文以模糊规则表的49个模糊语言集作为设计变量，以智能桁架结构的自由端最大挠度作为评价控制器性能指标的目标函数。其表达式为：
（4）
因为遗传算法要求个体适应度越大越优，故需将目标函数转化为最大值问题后作为目标函数，转换函数为：
（5）
3.3遗传操作
3.3.1 选择
选择算子是遗传算法中对群体中个体进行优胜劣汰的操作，本文采用适应度比例选择 ，设群体大小为，个体的适应度值为，则个体被选择的概率表示为：
（6）
3.3.2 交叉
交叉运算是两个配对染色体按照某种方式相互交换其部分遗传基因，从而产生两个新的个体。为了保证交叉运算后产生的新一代染色体个体的规则总数量不变，本文采用对位交叉算法。
3.3.3 变异
变异是指将个体染色体编码串中的某些基因位串上的基因值用该位串的其他等位基因来替换，从而产生新的个体。本文在进行变异操作时，是对个体染色体的49个基因，随机选择一位或多位基因值进行变异，随机变异所选用的基因用1-7之间的随机数值来代替
3.4遗传算法实现
首先，确定遗传算法的相关参数：本文的设计变量49个，取种群个数为15个，最大迭代次数取20次。然后，用遗传算法对控制规则进行优化，
4 实例仿真
本文所选桁架是由普通杆和由粘贴有压电片的主动杆构成，其结构尺寸为，共有83根杆件，普通杆是由铝合金材料构成，弹性模量为，密度，泊松比，杆件直径为。主动杆压电片采用压电陶瓷材料，传感器/作动器同位布置，布置在固定端端部，设该桁架结构的模态阻尼比为，顶端节点所受作用力，作用时间为0.01s。
将设计的模糊控制器和在遗传算法优化控制规则后设计的控制器分别作用于智能桁架结构，通过算法程序的运行可以得到
桁架架结构的仿真图：
仿真图中，红色线代表遗传算法优化模糊控制规则后的模糊控制器的控制效果，黄色线表示没有使用遗传算法的普通模糊控制器的控制效果。从仿真图中我们可以看出，遗传算法优化后的模糊控制器比普通模糊控制器有更好的控制效果，每阶的位移曲线最大位移都有明显的较小，智能桁架结构振动的衰减速度也有所加快。
5结论
本文对遗传算法做改进，然后作用在模糊控制器的控制规则优化上的方法是可行有效的，同时也说明了控制规则对于控制器的控制效果起着至关重要的作用。
参考文献
李东旭,陈卫东.大挠性航天桁架结构动力学及其主动控制研究进展[J]，力学进展，2009,38（2）：167-176
遗传算法论文范文第10篇
1遗传算法
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，启迪于达尔文的“物竞天择，优胜劣汰”规律和孟德尔的“遗传变异”学说，其本质是一种求解问题的高效并行搜索方法［3］。该算法将问题求解过程转化为染色体的适者生存过程，通过染色体的选择、交叉及变异不断进化从而收敛到最适应环境的个体，求得问题的最优解。该算法是一种群体型操作，该操作以群体中的所有个体为对象，这使得它可以同时搜索解空间内的多个区域，且特别适合于大规模并行，可用于复杂系统优化计算的鲁棒搜索算法［4］。
2基于改进遗传算法的故障时别算法设计
2．1算法改进
遗传算法具有全局搜索能力，但在应用中主要有两大缺陷：①对某些问题，遗传算法求解速度太慢；②遗传算法容易产生早熟现象。遗传算法是一种随机搜索算法，但在解决具体问题时，影响算法的几种参数取值很难确定其最优值及最优组合，往往要根据经验和试验来自行确定，另外，对不同的问题也要选择合适的编码方案，不同的编码方案也会影响算法的执行效率［5］。早熟收敛是遗传算法的另一个重要问题。通过染色体的交叉和变异，种群已经很难产生优于父本的子代个体时，就会发生早熟。用遗传算法解具体问题时，当到达局部最优解时，遗传算法有时会出现进化停滞不前的现象，使得种群中的个体始终在局部最优解附近徘徊，新个体的适应度不再增加，随着迭代的进行得不到全局最优解［6］。在经典最优化方法中，拟牛顿法的收敛速度、计算量、适用范围等性能是最佳的，而BFGS算法最为著名。本文提出将BFGS算法融入基本遗传算法，对基于BFGS的遗传算法进行性能分析和数值模拟，应用到数控机床故障识别系统。采用基于簇号的编码，样本个数为染色体长度，每一位自然编号为一个样本号，每一位基因上的数为此样本所属簇号。首先根据簇数m产生初始种群，采用随机产生m的序列保证至少每个簇内有一个样本，剩余n－m个基因随机产生m以内的自然数。
2．2改进遗传算法流程
1）首先确定初始种群数目M，成员码串长度l，终止代数T，pc和pm等参数，随机选出M个成员代表初始种群P（t），t＝0；2）破解编码串并按一定概率复制；3）对复制得来的子代群体进行交叉运算；4）对交叉得来的子代群体进行变异运算并得到新一代群体P（t＋1）；5）关键的一步，是否跳转BFGS算法用以下条件判定：确定所要优化的函数的梯度荦f（Xt）及其范数f（Xt），如果所要优化的函数式离散型的，那么必须采用差商代换之；如果所要优化的函数满足荦f（Xt）＜ε或荦f（Xt）＜ε时，那么程序转入下一步，否则转入第2）步；6）采取BFGS算法对所要优化的函数进行寻优运算；7）最后一步输出所要优化的目标函数的近似最优解或最优值。
3实例仿真
为了分析基于BFGS的遗传算法的性能，本文利用基于BFGS的遗传算法、经典遗传算法和粒子群算法对Shaffer＇sF6函数进行优化模拟测试，分析并比较三种算法的收敛速度，得出基于BFGS的遗传算法的性能，进而将该改进遗传算法与文献［7］中的遗传算法和文献［8］中的蚁群算法应用于某化学反应器故障诊断实例进行仿真对比，然后将三种算法应用于数控机床常见的齿轮箱故障诊断实例仿真，并比较三种算法的误差平方和、簇内距和簇间距。
3．1基于BFGS遗传算法与经典遗传算法、粒子群算法优化模拟测试
本文采用Shaffer＇sF6函数进行优化模拟测试：从图1中可以看出此函数具有无穷多个局部极大值点，其中（0，0）是全局最大值点，其值是1。当优化结果大于0．995时，认为算法是收敛的。遗传算法参数设为pm＝0．01，pc＝0．25，粒子群算法适应度函数取目标函数，领域结构采取全局领域结构，惯性权重为0．9，c1＝c2＝2，最大速度为3。收敛结果如图2所示。从图2中可以看出，无论种群规模为20还是50，随着迭代次数的增加，三种算法都能逐渐搜索到全局最优解附近，但改进遗传算法收敛性最强，收敛性能显著高于遗传算法和粒子群算法。这表明改进遗传算法在充分继承了遗传算法全局收敛性强这一优点的基础上，由于BFGS算法的引入，使得局部收敛性能得到了很好的提升。
3．2与遗传算法、蚁群算法的实例1仿真对比
该实例取自文献［7］中某化学反应器故障诊断，16组三维过程样本数据，对应不同的故障状态，算法评价对比如表1所示。种群规模分别为50和100，迭代次数100，随机10次遗传算法收敛如图3所示。从表1可以看出，基于BFGS的遗传算法具有较小的误差平方和，簇内距和簇间距也是优于文献［7］中的遗传算法和文献［8］中的蚁群算法。从图3中可以看到无论种群大小为50还是100，基于BFGS的遗传算法的收敛性均略优于文献［7］中的遗传算法和文献［8］中的蚁群算法。
3．3齿轮箱故障诊断
遗传算法论文范文第11篇
关键词： 遗传算法；交叉；变异；选择；应用
中图分类号：TP18文献标识码：A文章编号：1009-3044(2008)34-1874-03
Application and Theory of Genetic Algorithm
HUANG Shao-rong
(Department of Information Management, Guangdong Justice Police Vocational College, Guangzhou 510520, China)
Abstract: Genetic algorithm (GA) is an intelligent optimization algorithm that has been used the most extensively, and has the most influential effect. This paper introduces the GA’s history of the development and the process of operation, sums up its characteristics and introduces its application in various fields in detail.
Key words: genetic algorithm; crossover; mutation; selection; application
1 引言
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰）演化而来的一种自适应全局优化概率搜索方法，它以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。
近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用方面，取得了一些令人信服的结果，使其成为一个多领域、多学科的重要研究方向。
2 遗传算法的发展
遗传算法起源于本世纪40年代对生物系统所进行的计算机模拟研究，从生物学的角度进行生物的进化过程模拟、遗传过程模拟等操作。60年代，美国的Holland教授认识到生物的遗传和自然进化现象与人工自适应系统的相似性，提出研究人工自适应系统时，可借鉴生物的遗传机制以群体的方法进行自适应搜索。1975年Holland出版了《自然系统和人工系统的适配》[1]系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式定理，这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。与此同时，De Jong基于遗传算法的思想并结合模式定理在计算机上进行了大量的纯数值函数优化计算机实验，并提出了诸如代沟等新的遗传操作技术，树立了遗传算法的工作框架[2]，Holland和De Jong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。80年代由Goldberg进行归纳总结，对遗传算法的基本原理及其应用进行了全面而完整的论述，奠定了现代遗传算法的科学基础[3]。
进入80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题，尤其是遗传算法的应用领域也不断扩大。
3 基本遗传算法
遗传算法是一种迭代的算法，它首先随机生成一个初始种群，这个初始种群由经过基因编码的一定数目的个体组成。这个初始种群按照一定的操作规则，如选择，复制，交叉，变异等，不断地演化出新的一代。并根据个体的适应度，按适者生存和优胜劣汰的原则，引导搜索过程向最优解逼近，末代种群的最优个体经过解码，可以作为问题近似最优解。
3.1 遗传算法的步骤
Holland提出的遗传算法常被称为“简单遗传算法（SGA）”，主要步骤如下：
1) 初始化群体；
2) 计算群体上每个个体的适应度值；
3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体；
4) 按概率Pc进行交叉操作；
5) 按概率Pm进行变异操作；
6) 没有满足某种停止条件，则转第2)步，否则进入7)。
7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。
根据上述算法思想可得其算法框图如图1所示。
1) 编码
遗传算法中，种群中的每个个体（染色体）是由基因构成的，所以个体要与优化问题的解如何对应，就需要通过基因来表示，即对个体进行正确编码。遗传算法的进化过程是建立在编码机制基础上的，编码对于算法的性能影响很大。常用的编码技术有[4]：
二进制编码：
使用固定长度的0，1二进制字符串来表示一个染色体，例如：
X=（110110111）
就可以表示一个染色体，该个体的染色体长度为n=7。
浮点数编码：
个体的基因值用某一范围内的一个浮点数来表示，个体的染色体长度等于其决策变量的个数。例如某优化问题含有4个变量xi（i=1,2,3,4），xi∈[0,10]，则：
X=（3.2,8.7,6.4,2.1）
就可以表示一个染色体，该个体的染色体长度为n=4。
二进制编码优点是编码解码简单，交叉，变异等遗传操作便于实现，而且易于运用理论（如模式定理等）进行分析。浮点编码则在变异操作上能够保持更好的种群多样性，不过，其搜索能力比二进制要弱一些。后来，又提出了格雷编码、符号编码、整数编码、树编码等编码策略。
2) 初始群体的生成
遗传算法是一种基于群体寻优的方法，算法运行时是以一个种群在搜索空间进行搜索，一般采用随机法产生一个初始种群，即随机产生N个初始串结构数据，每个串结构数据称为一个个体， N个个体构成了一个群体。
3) 适应性评估检测
为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，称适应度。适应度是群体中个体生存机会的唯一确定性指标，表明个体或解的优劣性，其选取直接影响到遗传算法的收敛速度以及能否找到最优解，基本上依据优化的目标函数来确定。
4) 选择
从当前群体中选择适应度高的个体以生成池。选择原则是适应性强的个体为下一代贡献一个或多个后代的概率大，选择之前必须计算每个个体的适应度。常用选择算法有：
赌选择：是最知名的选择方式，基本原理是根据每个染色体适应度的比例来确定该个体的选择概率或生存概率。个体适应度按比例转化为选中概率，为了选择个体，需要进行多轮选择。每一轮产生一个[0，1]的均匀随机数，将该随机数作为选择指针来确实被选个体。
锦标赛选择：随机地从种群中挑选一定数目的个体，然后将最好个体选做父个体，重复这个过程直至得到足够的个体。
另外，还有一些其他的选择方法，如随机遍历抽样法、（μ+λ）选择、稳态选择、排序与比例变换、随机剩余选择、基因池选择、分裂选择等。
5) 交叉
是最主要的遗传操作，同时对两个染色体进行操作，组合两者的特性产生新的后代。算法性能很大程度上取决于采用的交叉运算，双亲的染色体是否进行交叉由交叉率来控制交叉一般可分为实值替换和二进制交叉两种：
实值替换：包括离散重组，中间重组和线性重组。
二进制交叉重组：最简单的二进制交叉是单点交叉，它的交叉原理如下：
父个体p1：01110011010
父个体p2：10101100101
交叉点的位置为5，则交叉后产生的两个子个体为：
子个体q1：01110│100101
子个体q2：10101│011010
除了单点交叉，还有两点交叉、多点交叉和均匀交叉等。
6) 变异
在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。变异使算法具有一定的局部的随机搜索能力，也可防止发生因遗漏最优值而无法再找到最优解的情况，保持了算法的有效性和种群的多样性，是算法的一个重要操作过程。染色体是否变异由变异率来控制。常用的变异有：
二进制变异：
对每个个体染色体上的二进制编码串进行操作，每一位以很小的概率从1变为0，或从0变为1。比如有如下二进制编码表示：
■
其码长为8，随机产生一个1至8之间的数K，假如现在K=5，对从右往左的第5位进行变异操作，将原来的0变为1，得到如下数码串（第四个1是被变异操作后出现的）：
■
向梯度方向变异：
对于目标函数可微的最大化问题，可采用如下变异操作：
Z=X+f(X).α α∈U(0,a)
其中，f(X)是目标函数在X处的梯度。
对于最小化问题，则采用如下变异：
Z=X-f(X).α α∈U(0,a)
另外，还有实值变异、基本位变异、均匀变异、边界变异、非均匀变异以及高斯变异等。
7) 参数控制
遗传算法有4个运行参数需要提前设定，并且实际应用中，需要多次测试后才能确定这些参数合理的取值：
M：种群大小。它对算法的效率有明显的影响，规模太小不利于进化，而规模太大将导致程序运行时间过长。不同问题，种群规模不同，通常为20～100。
T：终止进化代数。一般取100～500。
Pc：交叉概率。并不是所有被选择的染色体都要进行交叉或变异操作，而是以一定的概率进行。在程序设计中交叉发生的概率要比变异发生的概率选取得大若干个数量级，一般取0.4～0.99。
Pm：变异概率。一般取0.0001～0.1。
8) 中止条件控制
遗传算法的终止条件通常可以从两方面进行控制：一个是预先设定最大的进化代数，另一个是当算法在规定的代数内还没有找到更优解则终止算法。
3.2 遗传算法的特点
遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为： ① 首先组成一组候选解； ② 依据某些适应性条件测算这些候选解的适应度； ③ 根据适应度保留某些候选解，放弃其他候选解； ④ 对保留的候选解进行某些操作，生成新的候选解。遗传算法将上述特征组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。此外，还具有以下特点：
1) 搜索过程从一群初始点开始，而不是单一的初始点。覆盖面大，可有效防止陷入局部最优，利于全局择优。
2) 仅用适应度来评估个体并在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定，大大扩展了其应用范围。
3) 使用概率搜索技术，而非确定性规则。
4) 具有潜在的并行性。采用种群的方式组织搜索，可同时搜索多个有效区域并相互交流信息，能以较少的计算获得较高的效率。
5) 具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。
6) 结构简单明了，容易与其他方法结合，而且算法内在的并行性使它适合大规模的运算，可以有效对复杂系统进行模拟和优化。
4 遗传算法的应用
由于遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类具有很强的鲁棒性，前面描述是简单的遗传算法模型，可以在这一基本型上加以改进，使其在科学和工程领域得到广泛应用。下面列举了一些遗传算法的应用领域[5]：
1)优化
优化问题在运筹学、管理学和工程设计中处于非常重要的地位，遗传算法在优化问题的上应用包括：
① 函数优化问题：是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。
② 组合优化问题：组合优化问题的本质可归纳为下列类型之一[6]：
确定与问题相关的某些项的排列（如资源约束的项目调度问题、车辆路径和调度问题等）
确定某些项的组合（如集覆盖问题和群体问题等）
确定某些项的排列和组合（如并行机器调度问题等）
任何带有约束的上述类型
组合优化理论上可通过牧举法找到最优解，但随着问题规模的增大，探索空间也急剧增大，在目前的计算机上很难求出最优解。遗传算法作为复杂问题优化方法的潜质已经受到了普遍的关注，实践证明，遗传算法对于组合优化中的NP完全问题非常有效。
③ 多目标优化
该类问题存在多个目标需要同时优化，由于目标之间的无法比较和矛盾等现象，导致不一定存在使所有目标最优的解。由于遗传算法具有多方向和全局搜索特点，在解决这类问题上具有优势。
2) 自动控制
对大规模控制系统进行综合设计并建立数学模型，在对数学模型的优化上，遗传算法具有其它进化算法无法比拟的优点，已取得一定成绩。例如用遗传算法对自动控制系统数学模型寻优、用遗传算法优化PID控制系统、遗传算法在加工过程智能最优自适应控制的应用、基于遗传算法的模糊控制器的优化设计等。
3) 人工生命
人工生命是用计算机模拟自然界的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，与遗传算法有密切关系。遗传算法已经在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力。
4) 图像处理和模式识别
遗传算法可以对图像进行优化，使图像处理中产生的一些误差达到最小。目前已经图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用。
5) 机器人智能控制
是遗传算法的一个重要应用领域，已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到了应用。（下转第1882页）
（上接第1876页）
6) 程序设计
遗传算法可以用于某些特殊任务的计算机程序设计。
7) 机器学习
遗传算法可用于许多机器学习的应用，包括分类问题和预测问题等，特别是分类器系统，在很多领域中都得到了应用。
8) 经济学与社会经济问题
应用遗传算法对经济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。
9) 免疫系统
应用遗传算法可以对自然界中免疫系统的多个方面建立模型，研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。
10) 进化现象和学习现象
遗传算法可以用来研究个体是如何学习生存技巧的，一个物种的进化对其他物种会产生何种影响等等。
5 结论
遗传算法作为强有力且应用广泛的随机搜索和优化方法，无论是理论研究还是应用研究都成了十分热门的课题，尤其是遗传算法的应用研究显得格外活跃。本文首先介绍遗传算法的发展与操作步骤，并总结出遗传算法的特点，最后详细介绍了遗传算法的各个应用领域。
参考文献：
[1] Holland J H.Adaptation in Nature and Artificial Systems[M].MIT Press,1992.
[2] De Jong K A.An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph. D Dissertation[D].University of Michigan,No.76-9381,1975.
[3] Goldberg D E.Genetic Algorithms in Search, Optimization and Machine Learning[M].Addison-Wesley,1989.
[4] 汪定伟.智能优化方法[M].北京:高等教育出版社,2007:21-23.
遗传算法论文范文第12篇
关键字：遗传算法；机器学习；人工生命；人工神经网络；神经网络拓扑结构
中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)27-2040-03
The Application of Genetic Algorithm to the Artificial Intelligence
WANG Hui
(Xinjiang Petroleum Institute, Urumqi 830000, China)
Abstract: In this paper the author introduces the basic conception of genetic algorithm(GA for short),the feature of GA and the calculation steps. We can also get a general idea of the development in the machine learning, Parallel Processing, artificial Life, and the integration of evolutionary rules and strategies. At last, the application of GA to artificial neural networks is discussed, especially the application of GA to the study of neural networks weight and the neural network topology.
Key words: genetic algorithm; machine learning; artificial life;artificial neural networks; neural network topology
1 遗传算法简介
遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，与传统数学模型截然不同，它为那些难以找到传统数学模型的难题找出了一个解决方法。遗传算法借鉴了生物科学中达尔文的物竞天择、适者生存的进化准则，1975年，Michigan大学Holland教授根据这一规律首次提出了遗传算法（genetic algorithm，简称GA），其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性。这是一种新型的全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定等数学问题，鲁棒性强、随机性、全局性以及适于并行处理，已广泛应用于神经网络、计算机科学、优化调度、运输问题、组合优化、机器学习、信号处理、自适应控制和人工生命等领域，并且遗传算法在实际应用中也取得了巨大成功。
2 基本遗传算法
遗传算法的工作过程本质上就是模拟生物的进化过程。首先，要规定一种编码方法，使得你的问题的任何一个潜在可行解都能表示成为一个“数字”染色体。然后，创建一个由随机的染色体组成的初始群体（每个染色体代表了一个不同的候选解），并在一段时期中，以培育适应性最强的个体的办法，让它们进化，在此期间，染色体的某些位置上要加入少量的变异。
遗传算法是一种基于空间搜索的算法，它的求解可以看成是最优化过程。遗传算法的最大优点就是，你不需要知道怎么去解决一个问题，你需要知道的仅仅是用什么样的方式对可行解进行编码，使得它能被遗传算法机制所利用。遗传算法并不能保证所得到的解是最优解，但可以将误差控制在容许的范围内。遗传算法具有以下特点：
1） 遗传算法是对参数集合的编码而非针对参数本身进行优化；
2） 遗传算法是从问题解的编码组开始而非从单个解开始搜索；
3） 遗传算法利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索；
4） 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。
那么下面对基本遗传算法给出一个求解步骤：
1） 定义一个目标函数；
2） 将可行解群体在一定的约束条件下初始化，每一个可行解用一个向量x来编码，称为一条染色体，向量的分量代表基因，它对应可行解的某一决策变量；
3） 计算群体中每条染色体xi(i＝1，2，…，n)所对应的目标函数值，并以此计算适应值Fi，按Fi的大小来评价该可行解的好坏；
4） 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的好坏，按概率随机选择，进行繁殖，形成新的群体；
5） 通过杂交和变异的操作，产生子代。杂交是随机选择两条染色体（双亲），将某一点或多点的基因互换而产生两个新个体，变异是基因中的某一点或多点发生突变；
6） 对子代群体重复步骤(3)～(5)的操作，进行新一轮遗传进化过程，直到迭代收敛（适应值趋稳定）即找到了最优解或准最优解。
3 遗传算法的发展动向
GA在应用方面的取得了较丰硕的成果，其主要应用领域在于函数优化，机器人学，设计，组合优化，信号处理，人工生命等，此外遗传算法还有几个引人注目的新动向。
3.1 基于GA的机器学习
这一新的研究方向把GA从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法，这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望，GA作为一种搜索算法从一开始就与机器学习有密切联系。分类器系统是第一个基于GA的机器学习系统。基于GA的概念学习是近几年机器学习领域的一个较为引人注目的研究方向。还有一些嵌入领域知识的基于GA的机器学习的研究。
3.2 并行处理的GA
并行处理的GA的研究不仅是GA本身的发展，而且对于新一代智能计算机体现结构的研究都是十分重要的，GA在操作上具有高度的并行性，许多研究人员都正在搜索在并行机上高效执行GA的策略。近几年也发表了不少这方面的论文，研究表明，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程，即使不使用并行计算机，我们也能提高算法的执行效率。在并行GA的研究方面，一些并行GA可以分为两类：一是粗粒度并行GA，它主要开发群体间的并行性，如Coboon分析了在并行计算机上解图划分问题的多群体GA的性能；另一类是细粒度并行GA，它主要开始一个群体中的并行性，如Kosak将群体中的每个个体映射到一个连接机的处理单元上，并指出了这种方法对网络图设计问题的有效性。
3.3 GA与人工生命的渗透
人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。人工生命与GA有密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础，虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。
3.4 GA与进化规则及进化策略的结合
GA，进化规则及进化策略是进化计算的三个主要分支，这三种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象，所以三者之间有较大的相似性，但三种算法又是从不完全相同的角度出发来模拟生物的进化过程，分别是依据不同的生物进化背景，不同的生物进化机制而开发出来的，所以又有差异。但在进化计算领域内更重要的工作是生物的进化机制，构造性能更加优良且适应性更加广泛的进化算法。
4 基于遗传算法优化神经网络的应用研究
神经网络和遗传算法目标相近而方法各异。因此，将这两种方法相互结合，必能达到取长补短的作用。近年来,在这方面已经取得了不少研究成果，形成了以遗传算法与神经网络相结合的进化神经网络(ENN)。遗传算法在神经网络中的应用主要是用遗传算法学习神经网络的权重和学习神经网络的拓扑结构两个部分。
4.1 遗传算法学习神经网络的权重
而最主要的是学习神经网络的权重，也就是用遗传算法来取代一些传统的学习算法 。目前广泛研究的前馈网络中采用的是Rumel hart等人推广的误差反向传播（BP）算法，BP算法具有简单和可塑的优点，但是BP算法是基于梯度的方法，这种方法的收敛速度慢，且常受局部极小点的困扰，采用遗传算法则可把神经网络的结构优化和权值学习合并起来一起求解，克服了BP算法的缺陷，是神经网络权值学习的有效方法。
遗传算法学习神经网络权值的算法步骤如下：
1） 随机产生一组分布，采用某种编码方案对该组中的每个权值（或阈值）进行编码，进而构造出一个个码链（每个码链代表网络的一种权值分布），在网络结构和学习算法已定的前提下，该码链就对应一个权值和阈值取特定值的一个神经网络；
2） 对所产生的神经网络计算它的误差函数，从而确定其适应度函数值，误差与适应度成反比关系；
3） 选择若干适应度函数值最大的个体，直接遗传给下一代（精英保护策略）；
4） 利用交叉和变异等遗传操作算子对当前一代群体进行处理，产生下一代（新一代）群体；
5） 重复步骤2～4，使初始确定的一组权值分布得到不断的进化，直到训练目标得到满足或者迭代次数达到预设目标为止。
4.2 遗传算法学习神经网络的拓扑结构
神经网络结构包括网络的拓扑结构（连接方式）和接点转移函数两方面。利用遗传算法设计神经网络可根据某些性能评价准则如学习速度，泛化能力或结构复杂程度等搜索结构空间中满足问题要求的最佳结构。利用遗传算法设计神经网络的关键问题之一仍然是如何选取编码方案。
遗传算法学习神经网络结构的算法步骤如下:
1） 随机产生若干个不同结构的神经网络，对每个结构编码，每个码链对应一个网络结构，N个码链构成种群。
2） 利用多种不同的初始连接权值分别对每个网络进行训练。
3） 计算在每个对应码链下神经网络的误差函数，利用误差函数或其他策略（如网络的泛化能力或结构复杂度）确定每个个体的适应度函数。
4） 选择若干适应度函数值最大的个体构成父本。
5） 利用交叉，变异等遗传操作算子对当前一代群体进行处理，产生新一代群体。
6） 重复上述2）-5）步骤，直到群体中的某个个体（对应一个网络结构）能满足要求为止。
5 结束语
遗传算法作为一种新型的全局优化搜索算法，由于其直接对结构对象进行操作，不存在求导和函数连续性的限定，又具有鲁棒性强、随机性、全局性以及适于并行处理的优点，在人工神经网络的应用上展现了它的独特魅力与优势，但同时，它在理论和应用技术上也存在着许多不足和缺陷，比如相对鲜明的生物基础，其数学基础显得极为薄弱，尤其是缺乏深刻且具有普遍意义的理论分析。随着理论研究的深入，可以肯定，作为一种高效并行的全局搜索方法，遗传算法以其特有的算法特点使其在许多实际问题中的应用会越来越广；同时，广泛的数学方法和强大的计算机模拟工具的出现，必将使遗传算法的研究取得长足的进展。
参考文献：
[1] 蔡自兴. 人工智能及其应用[M]. 3版.北京：清华大学出版社，2003.
[2] 王风琴. 基于遗传算法的神经网络优化[J].燕山大学学报，2001，25（3）：234-239.
[3] 陈国良. 遗传算法及其应用[M].北京：人民邮电出版社，1999.
[4] 陈颖琪. 进化计算与神经网络的结合[J].红外与激光工程，1999，（4）：8-11，35.
[5] Kretnovich v.Qmtana C and Puentes O.Genetnc Algorithms-What Fitness Scaling is Optimal. Ctberm and System 1993.24.
[6] S W Mathfoud.Genetic drift in sharing methods. 0-7803-I899-4/94.1994 IEEE
[7] V Petrochs.S Kazarns. Varying quality function Gengentic algorithms and the cutting problem. 0-7803-I899-4/94.1994 IEEE
[8] 杨旭东，张彤. 遗传算法应用于系统在线识别研究[J].哈尔滨工业大学学报， 2000，32（1）：102-104.
[9] Pham D T，Jin G. Genetic algorithms using gradient-like ren reduction operator. Electronics Letters. 1995 .31.
[10] Nover D，Baskaran S，Scbuster P. Understanding genetic algorithms dynamics using harvesting strategies. Physics D 79, 1994.
[11] Kao T, Hwang S Y. A genetic algorithm with sruptive selection[J]. IEEE Transcations on System, Man. And Cybernetris-Part B: Cybernetics 1996,26.
遗传算法论文范文第13篇
关键词：气动参数辨识；残差平方和最小；遗传算法
引言
许多学者在气动参数辨识的方法上进行了深入的研究，获得的许多成果已广泛应用于工程实际中，其中基于灵敏度的极大似然法和广义Kalman滤波法应用最广泛。但在工程实际应用中，这两种方法在求解辨识参数时都存在矩阵求逆的过程，经常存在因为矩阵求逆而引起的不稳定问题，参数辨识结果很容易发散。本文针对基于灵敏度的极大似然法和广义Kalman滤波法存在的不足，在残差平方和最小准则下提出最小二乘法与遗传算法结合的算法进行气动参数辨识。下面给出辨识实现的步骤，采用最小二乘算法确定气动参数初值、遗传算法调整气动参数，最后，运用纵向运动的三自由度仿真证明了该方法的有效性和可行性。
1. 在残差平方和最小准则下最小二乘算法与遗传算法相结合的气动力参数辨识方法
导弹气动力参数辨识过程是根据辨识准则和试验数据求取模型中的待定参数的过程，因此一般气动参数辨识的过程主要分成七个步骤：
步骤一：弹道重构数据输入；
步骤二：确定气动参数初值；
步骤三：计算弹道数据；
步骤四：计算目标函数；
步骤五：判断目标函数是否最小，是转到步骤七，否转到步骤六；
步骤六：调整气动参数，回到步骤三；
步骤七：输出气动参数辨识结果。
上述的气动参数辨识过程中步骤一、三、五对不同的辨识算法而言是基本一致的，就如前面所说辨识算法的不同主要体现在步骤二、四、六上，辨识算法的辨识结果的有效性和收敛性主要取决于这三个步骤。本文针对广义Kalman滤波算法和极大似然法的缺陷，提出了在残差平方和最小准则下应用最小二乘法与遗传算法结合的算法进行气动参数辨识，这个算法主要特点在于：步骤二：气动参数初值的确定采用最小二乘算法；步骤四：目标函数的选取采用残差平方和最小准则；步骤六：气动参数的调整采用遗传算法。
2. 最小二乘法确定气动参数初值
在气动参数寻优的过程中需要各待估参数的取值范围，所以在辨识之前需要事先估计参数的初值，根据经验按照初值给定范围。
其中
（2）
解上面方程组，即可得出回归系数。
3. 残差平方和最小准则选取目标函数
为了避免矩阵求逆的问题，本文选择残差平方和最小作为目标函数：
（3）
4. 遗传算法调整气动参数
遗传算法直接以目标函数作为搜索信息。遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围。
下面是遗传算法调整气动参数的流程图（如图1所示），及遗传算法调整气动参数的具体过程：
5. 纵向运动的三自由度仿真
为了验证在残差平方和最小准则下最小二乘算法与遗传算法相结合的算法在导弹气动参数辨识中的有效行和可行性，本文给定了导弹的一组理论气动参数，在给定理论气动参数的基础上进行导弹三自由度的仿真计算导弹的理论航迹，以导弹的理论航迹作为辨识算法的输入，辨识导弹的气动参数。
选取气动模型状态方程组：
由上面的辨识结果表1可知，气动参数的辨识值与真值之间的相对误差最大为1.9%。该算法的目标函数逐渐趋近于零，即观测量与其在积分程序中的计算值的残差的平方和趋近于零。由图4、图5可知，vx、vy的拟合效果非常好，几乎重合。说明，在残差平方和最小准则下，应用该算法进行气动力参数辨识是有效的。
遗传算法论文范文第14篇
【摘要】最优特征子集选择即是从大量已知的文本特征集合中选择出最能代表文本分类模式的特征的过程。但是由于遗传算法固有的一些属性，使得遗传算法在应用过程中存在一些问题.例如，初始设置参数值的不合理以及参数值不能随着搜索过程而的进行变化。为此本文引入模糊逻辑控制遗传参数设置的思想，实验证明，使用模糊控制器进行参数控制对寻找最优特征子集是可行的。
【关键词】最优特征子集；遗传算法；模糊逻辑
1 引言
随着网络信息在各种领域的不断发展，各种各样的网络信息使人们应接不暇。这就需要我们对网络进行过滤和选择，去除一些不良信息和垃圾信息，净化网络空间。网络信息过滤是解决这一问题的有效方法之一。
由于遗传算法在初始设置参数（交叉率、变异率、种群规模）时存在盲目性和不合理性，导致不能正确找到最优特征子集。为解决这一问题，本文提出了基于模糊理论思想的模糊遗传算法（Fuzzy-GA）。设计给出了一种模糊遗传算法，并将其应用于最优特征子集选择。
2 最优特征子集问题
最优特征子集问题（OFSS）实质上就是对原始特征空间进行降维，特征子集越小，对分类贡献就越大，就越能代表分类问题，这样就可以大大提高了分类精度，使搜索能力得到显著提高。
3 模糊遗传算法求解文本最优特征子集的关键技术
遗传算法是一种的搜索策略，从代表问题的可能潜在解集的一个种群开始的，而一个种群则由经过基因和编码的一定数目的个体组成，然后经过遗传操作选择、交叉和变异产生出新的解集种群，使后生代种群比前代更加适应于环境，然后再把末代种群中的最优个体进行解码输出，即可得到问题的最优解。
4 基于模糊逻辑的遗传算法
4.1 基于模糊逻辑的遗传算法介绍。遗传参数当中的交叉率，变异率及种群规模是实现遗传算法搜索的重要参数。因此他们的设置是否合理直接影响到遗传算法搜索的性能。
4.2 模糊控制器设计思想。由于遗传参数在遗传算法优化过程中非常重要，代表了遗传进程的好坏以及是否能够达到最优解。 交叉率和变异率的变化受多种因素的影响，在进化早期，由于种群数量低 ，可适当的增大变异率，以保持种群的多样性。
一个模糊逻辑控制器一般四部分组成：规则库、模糊化环节、推理机、反模糊化环节，如下图所示：
图： 模糊逻辑控制器一般结构
在其中模糊控制规则是模糊控制器的核心。根据已有的知识与经验将分析归纳后的输入、输出变量用模糊语言来进行描述，得到的模糊语言集合就是模糊控制规则。模糊控制规则的生成有以下四种方法：
1）根据专家经验或过程控制知识生成；
2）根据过程模糊建模生成；
3）根据对手工控制操作的系统观察和测量生成；
4）根据学习算法生成。
根据它们之间的关联就能简要的得出这三种因素控制交叉率和变异率的控制语言描述：
1）遗传环境，则交叉率，变异率
2）遗传环境，则交叉率，变异率
3）种群数量，则交叉率 ，变异率
4）种群数量，则交叉率 ，变异率
5）适应度 ，则交叉率 ，变异率
6）适应度 ，则交叉率 ，变异率
其中 表示增大或优良； 表示降低或恶劣
5 实验结果分析
针对以上提出的模糊遗传思想，为证明其有效性，根据其算法思想我们进行了一般遗传算法和模糊遗传之间的试验比较。首先选择使用的文本库，共选择2000篇文本，从中随机选择1000篇文本作为训练集，再选出500篇作为测试集，，使用查全率与准确率来评价算法的有效性，在实验中处理的是经过切词（去掉停用词，低频词，无用词）以后的原始特征向量空间，，比较结果如下：
算法比较 查全率 准确率
GA 85.32% 85.02%
FGA 90.31% 93.20%
6 结论
本文根据遗传算法进化特点及各种操作的性质，将遗传操作与文本特征选择进行结合，并将模糊逻辑思想应用到遗传操作中，设计出基于模糊运算思想的模糊控制器来动态调节交叉率和变异率——即模糊遗传算法。经试验结果表明，使用模糊遗传操作进行文本的特征选择要比传统遗传算法的收敛性能要更加优良，提高了在进化过程中遗传参数环境的能力。
参考文献
[1] 李欣，王科俊，李国斌，金鸿章.模糊遗传算法综述.黑龙江自动化技术与应用[J].1998，3：16-19.
[2] 王兴成，郑紫薇，贾欣乐.模糊遗传算法及其应用研究.计算机技术与自动化[J]2000，19（2）：5-9.
遗传算法论文范文第15篇
关键词:计算智能;人工神经网络;模糊系统;遗传算法;免疫算法
中图分类号:TP18 文献标识码:A文章编号:1009-3044(2010)09-2207-04
Overview of the Main Algorithm for Intelligent Computing
ZHOU Hong-mei
(Huaihua Technical School, Huaihua 418000, China)
Abstract: In order to resolve some problems that the traditional intelligent method can not breakthrough,and promote the process of intelligentizing machines, Computational Intelligence is presented.The development of Computational Intelligence has given rise to considerable concerns in the machine intelligence field.This paper summarizes several main Computational Intelligence algorithms'developing process,analyzes its'basic theories,and simply introduces its'characters and practical applications.At last,the paper looks ahead the direction of Computational Intelligence's advance.
Key words: computational intelligence; artificial neural network; fuzzy system; genetic algorithm; immune algorithm
众所周知,人们对于生活中遇到的各种复杂的情况可以不假思索的做出决策判断,然而这对于先进的电子计算机却相当的困难,这是由于电子计算机的体系结构所决定的。要想使电子计算机具有较强的形象思维能力,必须突破冯・诺依曼的体系结构,另辟蹊径。近年来,随着人工智能应用领域的不断扩展,传统的基于符号处理机制的人工智能方法碰到的问题越来越突出,特别是在知识表示、处理模式信息及解决组合爆炸等方面[5]。因此,寻求一种适合大规模并行且具有智能特征如自适应、自学习、自组织等的算法已经成为有关学科的一个研究目标。计算智能(CI,Computational Intelligence)在这种背景下应运而生。
早在1988年,计算智能这个概念是加拿大的一本刊物的名字。1992年,美国学者James C.Bezdek在论文《计算智能》中将智能分为生物智能(BI,Biological Intelligence)、人工智能(AI,Artificial Intelligence)和计算智能(CI,Computational Intelligence)三个层次,并讨论了人工智能与计算智能的区别[1]。CI的主要处理对象是应用人员提供的数据材料,包括数字、信号等,它并不依赖于知识;而AI则必须用知识进行处理各种数据信息。计算智能的目标是模仿人的智能,包括模拟人脑的结构和模仿人脑的逻辑思维。
目前主要的计算智能方法有人工神经网络(ANN,Artificial Neural Network)、模糊逻辑(FL,Fuzzy Logic)、进化算法(EA,Evolution Algorithm)、免疫算法(IA,Immune Algorithm)、人工内分泌系统(AES,Artificial Endocrine System)、模拟退火、禁忌搜索算法、粒子群算法、蚁群算法等。其中进化算法又包括遗传算法(GA, genetic algorithm)、进化规划(EP, evolution plan)、进化策略(ES, evolution strategy)。本文分别从算法的产生和发展、算法的基本原理、算法的特点及其应用和发展趋势等方面对几种具有代表性的计算智能算法进行了总结和分析,希望能让读者对计算智能的发展有一个大致的了解。
1 人工神经网络
1.1 人工神经网络的发展
人工神经网络(Artificial Neural Network,ANN)是脑科学、神经心理学和信息科学等多学科的交叉研究领域,是近年来高科技领域的一个研究热点。它的研究目标是通过研究人脑的组成机理和思维方式,进而通过模拟人脑的结构和工作模式使机器具有类似人类的智能。人工神经网络的发展已有60多年的历史。早在1943年,美国心理学家McCulloch和数学家Pitts联合提出了形式神经元的数学模型,即经典的M-P模型,从此开创了神经科学理论的新纪元。其后,Rosenblatt、Widrow和Hoff等学者又先后提出了感知器模型[1,3],使得人工神经网络技术得以蓬勃发展。20世纪六七十年代是人工神经网络发展的低谷期,直到1982年加州大学的物理学家Hopfield提出了Hopfield网络模型并用电路实现,人工神经网络的研究重新进入了兴盛时期。
1.2 人工神经元的工作过程
人工神经网络是由大量处理单元经广泛互连而组成的人工网络,用来模拟人脑神经系统的结构和功能。而这些处理单元称为人工神经元。人工神经元的形式化模型种类很多,最常见的有M-P模型、线性加权模型和阈值逻辑模型。下面通过M-P模型来简单的介绍人工神经元的工作过程。图1为M-P神经元模型图。
人工神经网络中的每一个神经元都可以接受一组来自该网络中其他神经元的输入信号,并且每个输入信号有一定的强度,用连接权值来表示,所有输入信号的加权和决定该神经元的激活状态。假设来自其他处理单元(神经元)i的输入信息为xi,它们与该处理单元的相互作用强度即连接权值为wi(i=0,1,...,n-1),处理单元的内部阈值为θ 。那么该处理单元的输入为:,输出为:。此式中f 称为激发函数或作用函数,它决定了神经元的输出。该输出为1或0取决于其输入和大于或小于内部阈值θ 。激发函数一般具有非线性特性。常用的非线性激发函数有阈值型、分段线性型、Sigmoid函数型(简称S型)和双曲正切型[3]。
1.3 人工神经网络的应用
人工神经网络能较好的模拟人的形象思维,对信息具有很好的隐藏性,还具有容错性强、鲁棒性强和自学习性强等特点,是一个大规模自组织、自适应且具有高度并行协同处理能力的非线性动力系统。人工神经网络理论的应用已经渗透到各个领域[2]。
信息处理领域:包括信号处理、模式识别和数据压缩等方面的应用。
自动化领域:包括系统辨识、神经控制器和智能检测等方面的应用。
工程领域:包括在汽车工程、军事工程、化学工程和水利工程等方面的应用。
经济领域:包括在微观经济领域的应用、在宏观经济领域的应用、在证券市场中的应用、在金融领域的应用和在社会经济发展评价和辅助决策中的应用。
医学领域:包括检测数据分析、生物活性研究和医学专家系统等应用。
2 模糊系统
2.1 模糊理论的发展
模糊概念在生活中普遍存在,如“高”,“大”等。这些模糊概念蕴含了许多不确定信息,人脑可以很容易的通过这些不完整不精确信息做出判断和决策。然而,对于精确的电子计算机而言,处理含糊不清的信息却是相当困难的。基于这个原因,美国控制论专家扎德(Zadeh.L.A)于1965年提出了模糊集合的概念,发表了开创性论文《模糊控制论(Fuzzy sets)》,为模糊系统的研究奠定了坚实的基础。1973年,扎德教授又提出了模糊逻辑(Fuzzy Logic)的理论,并积极倡导将模糊理论向人工智能方向发展。经过众多研究者的不断努力,模糊逻辑理论已经得到进一步发展,并在专家系统不确定推理模型的设计中显示了很强的生命力。另一方面,模糊理论在学术界也得到了普遍的认同和重视。1992年IEEE召开了第一届关于模糊系统的国际会议(FUZZ-IEEE),1993年IEEE创办了专刊IEEE Transaction on Fuzzy System。当前,模糊理论和应用正在向深度和广度进一步发展,发展的速度越来越快,涌现出了大量的研究成果,已经成为了世界各国高科技竞争的重要领域之一。
2.2 模糊系统的原理
模糊系统(Fuzzy System, FS)基于模糊数学理论,能够对事物进行模糊处理。模糊数学基础包括模糊集合、模糊逻辑、模糊规则、模糊推理和隶属度等。在模糊系统中,元素与模糊集合之间的关系是不确定的,即在传统集合论中元素与集合“非此即彼”的关系不适合模糊逻辑。元素与模糊集合的隶属关系是通过隶属度函数来度量的。当一个元素确定属于某个模糊集合,则这个元素对该模糊集合的隶属度为1;当这个元素确定不属于该模糊集合时,则此时的隶属度值为0;当无法确定该元素是否属于该模糊集合时,隶属度值为一个属于0到1之间的连续数值。在模糊系统中,知识是以模糊规则的形式存储的,如:IF E THEN H (CF, λ ),其中E表示模糊规则的条件,H表示模糊规则的结论,它们都是模糊的。CF表示这个规则的可信度,它既可以是一个确定值,也可以是模糊数或语言值,λ 是阈值,用于确定这条知识是否能被应用。模糊推理引擎运用这些模糊规则进行模糊逻辑推理,完成对不确定性问题的求解。图2是模糊系统的基本结构图。
2.3 模糊系统的应用
模糊系统能够很好处理人们生活中的模糊概念,清晰地表达知识,而且善于利用学科领域的知识,具有很强的推理能力。模糊系统主要应用在自动控制、模式识别和故障诊断等领域并且取得了令人振奋的成果,但是大多数模糊系统都是利用已有的专家知识,缺乏自学习能力,无法对自动提取模糊规则和生成隶属度函数。针对这一问题,可以通过与神经网络算法、遗传算法等自学习能力强的算法融合来解决[9,16]。目前,很多学者正在研究模糊神经网络和神经模糊系统,这是对传统算法研究和应用的创新。
3 遗传算法
3.1遗传算法的基本原理
遗传算法(Genetic Algorithm,GA)是在20世纪六七十年代由美国Michigan大学的Holland教授及其学生和同事共同发展起来的,是一种模拟生物界的自然进化规律而形成的一种基于全局的直接优化搜索算法,是一种进化算法。
遗传算法的基本思想源于达尔文(C.R.Darwin)的进化论和孟德尔(G.J.Mendel)的遗传学说。达尔文进化论的最基本原理是适者生存。在生物进化的过程中,只有那些能适应环境的一些个体特征才能得以保留。遗传学说的最基本原理是基因遗传原理,遗传以基因的形式包含在染色体中,每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可以产生更适应于环境的后代。经过存优去劣的自然选择,适应性高的基因结构得以保存[3]。
遗传算法用“染色体”来表示问题的解。在执行遗传算法之前,首先给定一个“染色体”群,称为假设解。然后,把这些假设解置于问题的“环境”之中,通过适者生存原则,选择对环境适应度高的“染色体”进行复制,交换和突变等操作。如此逐代进化,最后算法收敛到一个适应度最高的“染色体”,此为问题的最优解。图3为遗传算法的基本流程图。
3.2 遗传算法的特点
遗传算法是一个不断寻找最优点的过程,它始终让整个群体保持进化状态。与传统优化方法比较,遗传算法主要有以下几个特点。
智能性:遗传算法具有自适应、自组织和自学习性等。在求解问题时,在确定编码方案、适应度函数和遗传算子之后,算法将根据自然选择的策略自组织进行搜索。
并行性:遗传算法的操作对象是一个可行解集合,而非单个可行解。它采用同时处理多个可行解,基于全局搜索优化[14]。这使得遗传算法减少了陷入局部最优解的可能性,同时体现了遗传算法良好的并行性。
不确定性:遗传算法的主要步骤都含有随机性,如交换操作、突变操作等,因此在算法的搜索方向具有很大的不确定性[4]。
通用性:遗传算法的处理对象不是参数本身,而是对参数集进行了编码的个体。这种编码操作,使得遗传算法可直接对结构对象进行操作[15];同时,该算法只需要适应度函数来评估个体,无需其他辅助信息。以此,它几乎可以处理任何问题。
作为一种搜索算法,遗传算法在各种问题求解和应用中展现出了它的特点和魅力,同时也暴露出了不足和缺陷。由于遗传算法的处理对象是编码的个体,因此编码方式很大程度上影响了算法的效率和结果;算法本身参数的设置无法定量表示;对于数量较大的群体,算法的收敛速度慢等。目前出现了很多基于上述问题的遗传算法的改进算法[10],如一种快速收敛的遗传算法,通过改变初始化群体的生成方式,较好地解决了算法收敛速率的问题。
3.3 遗传算法的应用
由于遗传算法具有的优点众多,因此其应用范围也极其广泛。遗传算法主要应用于神经网络、模式识别、组合优化、机器学习、图形处理等。下面介绍遗传算法作为一种机器学习技术在分类系统中的应用。
遗传算法在分类系统中主要是对分类系统中的分类器[3],即规则进行学习,用以产生更好的分类规则。其主要步骤如下:
1)根据分类器(规则)的适应度成正比的概率,选择复制出N个规则。
2)对选出的规则,利用遗传算法中的遗传操作(交叉、突变),重新生成N个新规则。
3)用产生的“后代”(新规则)取代分类器中适应度小的规则。
当一次遗传算法学习过程结束之后,如果得到群体中的规则和其父代完全相同,且各规则的适应度值已连续多次保持不变,则认为算法收敛,学习过程结束。
4 免疫算法
4.1 免疫算法的发展
1974年,诺贝尔奖得主,生物学家、医学家、免疫学家Jerne提出了免疫系统的第一个数学模型,为免疫算法的研究奠定了基础。之后Farmer,Perelson,Bersini,Varela等学者先后于1986年,1989年和1990年发表了相关论文,为免疫算法在实际工程中的应用做出了突出贡献,同时他们的研究工作为建立基于免疫理论的计算系统和智能系统开辟了道路。目前,免疫算法已经成为国际智能计算领域关注的热点和前沿课题。2002年,IEEE Transaction on Evolution Computation首次出专刊报到了有关人工免疫系统(Artificial Immune System)的研究进展。在国内,免疫优化算法的理论研究和应用具有鲜明的特色。中国科学技术大学王煦法教授在国内较早开展对免疫优化算法方面的研究,并把它应用到了人工生命和硬件领域。西安电子科技大学焦李成教授提出了比较完备的免疫克隆算法的理论基础以及一些改进算法,并较早地在国际上创造性地提出了免疫算法与遗传算法的结合――免疫遗传算法[6,13]。免疫算法正以朝气蓬勃的姿态发展。
4.2 免疫算法基本原理
免疫是生物体的特异性生理反应。生物免疫系统由具有免疫功能的器官、组织、细胞和免疫效应分子及其基因组成,通过分布在全身的各类淋巴细胞识别和清除侵入生物体的抗原性异物。当抗原入侵生物免疫系统时。首先与抗原亲和力高的抗体受刺激产生克隆和高频变异,生成新抗体种类,然后亲和力更高的抗体结合抗原后引起更强的反应,经过不断循环筛选出匹配抗体。人工免疫系统就是研究、借鉴和利用生物免疫系统的原理和机制发展起来的处理各种工程问题和信息计算问题的智能系统。免疫算法是基于免疫系统的学习算法,它具有良好的应答性和主动性,善于学习记忆,具有较强的模式分类能力。尤其在处理多模态问题时体现出了较高的智能性和鲁棒性。下面简单介绍一般免疫算法的原理。
首先,要对所求问题进行分析,找出待求解的目标函数,把它看成是生物免疫系统中的抗原,把问题的优化解看成是生物系统中的抗体,问题解的正确性或匹配性用抗体和抗原的亲和力来表示。亲和力指抗原和抗体的识别程度或者两个抗体之间的相似度,一般亲和力的公式为:,其中tk为抗体与抗原的结合强度,结合强度可以有各种距离公式求得,如欧几里得距离(ED,Euclidean distance),曼哈坦距离(MD,Manhattan distance)和明考斯基(MD,Minkowski distance)等。
免疫算法的流程如图4所示。免疫算法的步骤如下:
1)抗原的识别,免疫系统确定是否抗原入侵;
2)产生初始化抗体,同时激活记忆细胞,利用先前记忆的抗体消除先前出现过的抗原;
3)计算亲和力。计算所有抗体与入侵抗原的亲和力,选择亲和力最大的抗体,即它对入侵抗原的抵抗力最强,这是一个选择过程;
4)记忆细胞分化,把亲和力最大的抗体加给记忆细胞,以便抵御相同的抗原再次入侵;
5)抗体的促进和抑制;
6)抗体的产生,也就是问题优化解的产生。
4.3 免疫算法的应用进展
免疫系统是一种新型仿生智能算法,综合了分类器、神经网络和机器推理等学习系统的优点,是一种突现计算。免疫算法具有全局优化、鲁棒性强、并行性高和智能度高等特点[7],主要应用于计算机网络安全、智能控制和优化计算等领域[12]。此外,免疫算法在数据挖掘与分析、机器学习和异常与故障检测等方面取得了很大进展。尽管如此,目前对于免疫算法的研究只是处于起步阶段,理论研究和实际应用的深度还不够,而且免疫机理复杂,系统庞大,免疫学家对一些免疫现象也无法清楚的表述,而且免疫算法可以借鉴的成果也不多,所以免疫算法的研究存在着一定的困难。免疫算法和神经网络算法,进化算法一样都是模拟生物智能的算法,因此免疫算法的研究可以参照神经网络算法和进化算法的研究方法,借助其相关研究成果,这将是研究免疫算法的一个新方向。
5 结束语
目前关于计算智能的研究和应用处于蓬勃发展时期,其应用范围遍及各个科学领域。虽然计算智能是一门新兴的综合型学科,而且各种智能方法的发展历史也不是很长,但是其发展却是相当迅猛。当前除了对单一的算法进行研究和应用之外,很多学者开始对各种算法的融合进行研究,针对各个算法的特点,有目的的进行取长补短的算法综合。典型的融合方案有:人工神经网络与模糊逻辑、人工神经网络与免疫算法、人工神经网络与遗传算法、模糊逻辑与免疫算法、模糊逻辑与遗传算法和遗传算法与免疫算法[11]。融合之后的算法可以提高算法的性能,增强了算法的适应性,同时还克服了算法选择的盲目性。另外,还有学者提出了计算智能的新框架――生物网络结构,即神经内分泌免疫网络(NEIN, neuro-endocrine-immune networks)。它由人工神经网络(ANN)、人工内分泌系统(AES)和人工免疫系统(AIS)组成[8]。新框架的提出为人们研究其理论和应用技术提供了新平台。这些研究都为计算智能今后的发展指明了方向。
参考文献:
[1] 周春光,梁艳春.计算智能[M].长春:吉林大学出版社,2009:3-9.
[2] 韩力群.人工神经网络理论,设计与应用[M],北京:化学化工出版社,2007:16-18.
[3] 张仰森,黄改娟.人工智能教程[M].北京:高等教育出版社,2008:322-324.
[4] 王宏生,孟国艳.人工智能及其应用[M].北京:国防工业出版社,2009:139-141.
[5] 尹朝天.人工智能方法与应用[M].武汉:华中科技大学出版社,2007:169-175.
[6] 王磊,潘进,焦李成.免疫算法[J].电子学报,2000,28(7):74-78.
[7] 高家全,何桂霞,王雨顺.典型的人工免疫算法性能比较与分析[J].计算机工程与应用,2009,45(10):208-210.
[8] 丁永生.计算智能的新框架:生物网络结构[J].智能系统学报,2007,2(2):26-30.
[9] 罗熊,孙增圻.计算智能方法优化设计模糊控制系统:现状与展望[J].控制与决策,2007,22(9):961-966.
[10] 董聪,郭晓华.计算智能中若干热点问题的研究与进展[J].控制理论与应用,2000,17(5):691-698.
[11] 苏建元.智能计算主要算法的比较与融合[J].中国电子科学研究院学报,2007,2(1):52-56.
[12] 胡风新,郭红瑾,孙运芳.免疫算法理论及应用研究[J].计算机与数字工程,2009,37(7):46-49.
[13] 高彬彬,杨孔雨.免疫算法研究[J].计算机技术与发展,2009,19(7):249-252.
[14] 王煦法.遗传算法及其应用[J].小型微型计算机系统,1995,16(2):59-64.
- 上一篇：宪法论文范文
- 下一篇：大学毕业设计论文范文
