遗传算法应用的分析与研究
福州八中钱自强
【摘要】
随着科技水平的不断发展，人们在生产生活中遇到的问题也日益复杂，这些问题常常需要在庞大的搜索空间内寻找最优解或近似解，应用传统算法求解已经显得相当困难。而近年来，生物学的进化论被广泛地应用于工程技术、人工智能等领域中，形成的一类有效的随机搜索算法——进化算法，有效的解决了诸多生产生活中的难题而显得越来越流行。
本文的首先将介绍进化算法的原理以及历史使大家对进化算法有一个初步的了解，其次将详细介绍应用遗传算法解题的步骤，并提出有效改进和应用建议。紧接着通过一个NP难题的优化实例让大家对遗传算法有更深刻的了解，最后通过数据分析证明其方法的有效性。
【关键词】
人工智能；进化算法；遗传算法（GA）；多目标最小生成树
目录
一、进化算法理论
1．1进化算法概述－ 2－
1．2遗传算法介绍－ 2－
二、遗传算法
2．1遗传算法基本流程－ 3－
2．2遗传算法中各重要因素分析－ 3－
2．3重要参数设置－ 6－
三、遗传算法在多目标最小生成树问题中的应用
3．1多目标最小生成树－ 7－
3．2应用遗传算法解决多目标最小生成树－ 9－
3．3测试－11－
四、结束语－15－
附录－16－
一. 进化算法理论
1．1进化算法概述
从远古时代单细胞开始，历经环境变迁的磨难，生命经历从低级到高级，从简单到复杂的演化历程。生命不断地繁衍生息，产生出具有思维和智能的高级生命体。人类得到生命的最佳结构与形式，它不仅可以被动地适应环境，更重要的是它能够通过学习，模仿与创造，不断提高自己适应环境的能力。
进化算法就是借鉴生物自然选择和遗传机制的随机搜索算法。进化算法通过模拟“优胜劣汰，适者生存”的规律激励好的结构，通过模拟孟德尔的遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。作为随机优化与搜索算法，进化算法具有如下特点：进化算法不是盲目式的乱搜索，也不是穷举式的全面搜索，它根据个体生存环境即目标函数来进行有指导的搜索。进化算法只需利用目标的取值信息而不需要其他信息，因而适用于大规模、高度非线性的不连续、多峰函数的优化，具有很强的通用性；算法的操作对象是一组个体，而非单个个体，具有多条搜索轨迹。
1．2遗传算法
遗传算法（Genetic Algorithm）是进化算法的一个重要分支。它由John Holland提出，最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近来，遗传算法作为问题求解和最优化的有效工具，已被非常成功地应用与解决许多最优化问题并越来越流行。
遗传算法的主要特点是群体搜索策略和群体中个体之间的信息互换,它实际上是模拟由个体组成的群体的整体学习过程,其中每个个体表示问题搜索空间中的一个解点.遗传算法从任一初始的群体出发,通过随机选择，交叉和变异等遗传操作,使群体一代代地进化到搜索空间中越来越好的区域,直至抵达最优解点.
遗传算法和其它的搜索方法相比,其优越性主要表现在以下几个方面：首先,遗传算法在搜索过程中不易陷入局部最优,即使在所定义的适应度函数非连续.不规则也能以极大的概率找到全局最优解,其次,由于遗传算法固有的并行性,使得它非常适合于大规模并行分布处理,此外,遗传算法易于和别的技术(如神经网络.模糊推理.混沌行为和人工生命等)相结合,形成性能更优的问题求解方法.
二. 遗传算法
2．1遗传算法的基本流程
一个串行运算的遗传算法通常按如下过程进行：
(1) 对待解决问题进行编码；t:=0
(2) 随机初始化群体X(0):=()n x
,
,
x,
x
；
1
2
(3) 对当前群体X(t)中每个染色体
x计算其适应度F ()i x，适应度表示了
i
该个体对环境的适应能力，并决定他们在遗传操作中被抽取到的概
率；
(4) 对X(t)根据预定概率应用各种遗传算子，产生新一代群体X(t+1)，
这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想；
(5) t:=t+1(新生成的一代群体替换上一代群体)；如果没有达到预定终止
条件则继续(3)。
2．2 遗传算法中各重要因素分析
▲编码理论
遗传算法需要采用某种编码方式将解空间映射到编码空间（可以是位串、实数、有序串）。类似于生物染色体结构，这样容易用生物遗传理论解释，各种遗传操作也易于实现。编码理论是遗传算法效率的重要决定因素之一。二进制编码是最常用的编码方式，算子处理的模式较多也较易于实现。但是，在具体问题中，根据问题的不同，采用适合解空间的形式的方式进行编码，可以有效地直接在解的表现型上进行遗传操作，从而更易于引入相关启发式信息，往往可以取得比二
进制编码更高的效率。
▲染色体
每个编码串对应问题的一个具体的解，称为染色体或个体。一个染色体可以通过选用的编码理论与问题的一个具体的解相对应，一组固定数量的染色体则构成一代群体。群体中染色体可重复。
▲随机初始化
随机或者有规律（如从一个已知离解较近的单点，或者等间隔分布地生成可行解）生成第一代群体。一次遗传算法中有目的采用多次初始化群体会使算法拥有更强的搜索全局最有解的能力
▲适应度
一个染色体的适应度是对一个染色体生存能力的评价，它决定了该染色体在抽取操作中被抽取到的概率。估价函数是评价染色体适应度的标准，常见的估价函数有：直接以解的权值（如01背包问题以该方案装进背包物品的价值作为其适应度），累计二进制串中1/0的个数（针对以二进制串为编码理论的遗传算法），累加该染色体在各个目标上的得分（针对多目标最优化问题，另外，对于此类问题，本文提出了一种更有效的估价函数）。
▲遗传算子
遗传算子作为遗传算法的核心部分，其直接作用于现有的一代群体，以生成下一代群体，因此遗传算子的选择搭配，各个算子所占的比例直接影响遗传算法的效率。一个遗传算法中一般包括多种遗传算子，每种算子都是独立运行，遗传算法本身只指定每种算子在生成下一代过程中作用的比例。算子运行时从当前这代群体中抽取相应数量的染色体，经过加工，得到一个新的染色体进入下一代群体。
下面列出几种常见的遗传算子：
● 保持算子：抽取1个染色体，直接进入下一代。该算子使算法能够收敛。 ● 交配算子：抽取2个染色体，交换其中的某些片段，选择适应度高的（或
者都选），进入下一代群体。该算子使得遗传算法能够利用现有的解寻求更优的解。
● 变异算子：抽取1个染色体，对其进行随机的改变，进入下一代群体。
该算子使得算法可以跳出局部最优解，拥有更强搜索全局最有解的能力，防止陷入局部搜索，该算子的概率不可过高，否则将引起解的发散，使得算法无法收敛。
▲ 抽取
抽取操作是遗传算法中一个重要基本操作，作用是按照“优胜劣汰”的原则根据各个染色体的适应度从当前这代群体中挑选用于遗传算子的染色体。通常采用的手段是偏置转盘：
设算法中群体数量为population ，首先计算当代群体的各染色体适应度之
和∑==
population
i i
x F t S 1
)()(。将
1～)(t S 内的整数划分成population 个区间段，每个
染色体所占的区间段的长度既是它的适应度。这样，随机产生一个1～
)(t S 的整数，抽取该点所属区间段
相对应的染色体，就可以保证任意一个染色体x i 在抽取操作中被抽取到的概率为)
()
(t S x F i 。
▲ 终止条件
遗传算法的终止条件用于防止遗传算法无止境的迭代下去，一般限制条件可以设为达到指定的迭代次数后终止，或当解的收敛速度低于一定值时自动终止。当遗传算法达到终止条件时，遗传算法结束，并按照要求返回中途最优的一个染色体（或所有满足条件的非劣最优解）
2．3重要参数设置
在应用遗传算法解决问题的时候，往往需要根据实际情况的不同，对不同问题使用不同的遗传参数。在大规模的问题上，一次遗传算法的不同时期也可以设置不同的遗传参数。对遗传算法效率影响较大的参数如下：
群体大小：一代群体中染色体的数量，群体大小越大所能容纳的染色体品种也越多，越有利于搜索全局最有解，但是会下降收敛的速度，所
需的时间也更多。
迭代次数：最多更新群体的次数，迭代次数的增加可以使得解收敛更精确但是所需的时间也越多，如果时间允许，采用多次初始化群体的操
作要比设置很大的迭代次数来得更高效些。
保持率：保持算子所占的比例，通常不超过70%
交配率：交配算子所占的比例，通常不超过50%
变异率：变异算子所占的比例，通常不超过1%
三. 遗传算法在多目标最小生成树问题中的应用
生活中的很多问题，例如道路铺设，电网架设，网络构设等，其实都可以归结到最小生成树模型，经典的Prim算法和Kruskal算法都可以解决该问题，算法的时间复杂度都是线形的，但是现实生活中的问题往往没有那么简单，一条边上可能不只带一个权，例如一条公路的铺设道路长度还要考虑环境和人文因素，电网架设时除了考虑线路费用还要考虑架设难度，一个网络连接除了考虑网络延时还要考虑传输稳定性和安全性等，于是问题就转化为求解多目标的最小生成树问题的非劣最优解，这个问题是NP难的，Prim算法，Kruskal算法等常规算法就显得无能为力，搜索算法的复杂度却又过高。
3．2 应用遗传算法解决多目标最小生成树问题
3．2．1 编码设计
Cayley证明了对于一个完全图G，连接所有n个顶点的树有n n-2棵。为此Prüfer建立了一个这些树与从n个数取n-2个数的所有组合之间的一一对应关系，即如果对完全图中所有顶点从1到n开始编号，则任意一个在从1到n的n个数中取n-2个数的组合都与唯一的一棵生成树相对应。
本文对生成树的编码采用基于以上的一一对应建立起来的Prüfer数编码机制，把每一棵树与一个长度为n-2的数字串对应，而对于任意一个长度为n-2的数字串也与唯一的一棵生成树相对应，生成树到数字串的编码与数字串到生成树的解码的详细证明可参考相关文献，本文这里只作简要描述。
★编码过程
▲编码串初始为空串
▲令j为树中编号最小的叶节点；
▲ 找到唯一于j 相邻的点i ，把i 加入编码串的最右端
▲ 把j 以及连接i 和j 的边从树中删除，这时候树只有n -1个顶点 ▲ 重复以上3个步骤直到树中只剩下一条边这时候得到的编码串即为相应树的Prüfer 编码 ★解码过程
▲设P 为编码串，P 为图的顶点编号不出现在P 中的顶点的集合；
▲设i 为P 中编号最小的顶点，j 为P 中最左端的顶点，则将连接i 和j 的边加入到树中，然后分别把i 和j 从P 和P 中删除，如果P 中不在出现顶点
j 则把j 加入到P 中
▲重复以上步骤，直到P 为空；
▲当P 为空串时，P 中刚好剩下两个顶点，将连接这两个顶点的边加入到树中，最后构成的树即为与最初P 对应的生成树。
例如，图3-1则为一棵生成树以及其相对应的Prüfer 编码图3-2。
显然Prüfer 编码是生成树的一个有效表示方式，应用该编码方式，可以很容易地随机生成一棵生成树，而且Prüfer 数编码串的每个位置的信息量又相对均匀因此很适合遗传操作。
3．2．2 估价函数设置
定义估价函数g(x)为???
?
???????? ???∑=k i i x f i 12
100)(]min[，
)(x f i 表示当前的染色体在目标图3-1
图3-2
i的费用情况，min[i]表示截止到上一代为止，产生的所有染色体在目标i的费用的最小值。
本文提出的这样定义比起常见的直接累加各目标上的权值的好处在于，其不仅很好的体现了一个染色体在各个目标上的优势，与此同时还避免了由于每个目标的取值范围不同或者取值的整体趋势不同而造成的某些个体在某些目标的优势无法被体现，使得算法能够适应现实生活中各类问题。
3．2．3 遗传操作定义
★交配算子
随机在两个染色体中抽取等位的，片段进行互换，然后选择适应度较高的进入下一代，具体操作方法如下图所示：
小片段等位交叉算子示意图
★变异算子
变异算子采用常规的单点变异，即随机生成一个数替换编码串中的某一位，如图所示。
图3-4单点变异示意图
可以看出单点变异也可以很大程度上保留了原染色体的性质。
3．3测试
我们将保持率定为80%，交配率定为80%，变异率定为1%，并且根据数据不同对迭代次数和群体大小进行调整
3．3．1小规模经典测试数据列表
3．3．2中规模随机测试数据列表
四．结束语
本文主要运用遗传算法的一些基本知识解决加油占选址的问题，通过测试结果看到了遗传算法在解决选址问题有着和其他算法无法比拟的强大优势。它的特点就是可以在较短的时间内，得到比较令人满意的解，而且算法相对简明。对于现实生活中的大量常规算法无法解决问题，遗传算法都有着良好的应用前景。
参考文献
Heuristic algorithms for siting alternative-fuel stations using the
Flow-Refueling Location Model,Seow Lim, Michael Kuby
MATLAB遗传算法工具箱及应用,雷英杰,西安电子科技大学出版社
数据结构,张千帆,科学出版社
毕业设计 遗传算法的研究及应用 摘要 本文分为三部分：第一部分：遗传算法的概述。主要介绍了遗传算法的基本思想、遗传算法的构成要素、遗传算法的特点、遗传算法的基本模型、遗传算法的应用情况及今后的研究方向等等的内容。第二部分：基于Matlab 7.0下的遗传算法求解函数最值问题。遗传算法作为一种新的优化方法，广泛地用于计算科学、模式识别和智能故障诊断等方面，它适用于解决复杂的非线性和多维空间寻优问题，近年来也得到了较为广阔的应用。本人选择了函数优化这个应用领域，按照遗传算法的步骤，即编码、解码、计算适应度（函数值）、选择复制运算、交叉运算和变异运算，对函数进行求解最值。第三部分：对遗传算法求函数最值问题的改进。这部分主要针对本文第二部分进行改进，通过改变基本遗传算法运行参数值，如改变交叉概率Pc值和变异概率Pm值，从而使最优值更加接近相对标准下函数的最值。 关键词：遗传算法适应度交叉概率变异概率
目录 1 前言 (1) 2 遗传算法概述 (1) 2.1生物进化理论和遗传学的基本知识 (1) 2.2遗传算法的基本思想 (3) 2.3遗传算法的构成要素 (3) 2.3.1 染色体编码方法 (3) 2.3.2 适应度函数 (4) 2.3.3 遗传算子 (4) 2.3.4 基本遗传算法运行参数 (5) 2.4遗传算法的特点 (6) 2.5遗传算法的基本模型 (7) 2.6遗传算法的应用 (8) 2.7遗传算法今后的研究方向 (10) 3 基于MATLAB 7.0下的遗传算法求解函数最值问题 (11) 3.1遗传算法的标准函数 (11) 3.2解题步骤说明 (12) 3.2.1 编码问题 (12) 3.2.2 选择运算 (12) 3.2.3 交叉运算 (13) 3.2.4 变异运算 (13) 3.3运行参数说明 (14) 3.4对遗传算法求得的最值的分析 (14) 3.5运行程序以及对其解释 (14) 3.6从数学的角度求解函数最优值 (18) 3.6.1 自变量x以0.2为步进单位 (18) 3.6.2 自变量x以0.1为步进单位 (19) 3.6.3 自变量x以更精确的数为步进单位 (21)
遗传算法属于进化算法( Evolutionary Algorithms) 的一种, 它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子: 选择、交叉和变异. 。数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。 生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法( GA)。算法中称遗传的生物体为个体( individual )，个体对环境的适应程度用适应值( fitness )表示。适应值取决于个体的染色体(chromosome),在算法中染色体常用一串数字表示，数字串中的一位对应一个基因 (gene)。一定数量的个体组成一个群体(population )。对所有个体进 行选择、交叉和变异等操作,生成新的群体,称为新一代( new generation )。遗传算法计算程序的流程可以表示如下［3］：第一步准备工作 (i)选择合适的编码方案，将变量(特征)转换为染色体(数字串，串长为m。通常用二 进制编码。 (2 )选择合适的参数，包括群体大小(个体数M)、交叉概率PC和变异概率Pm (3、确定适应值函数f (x、。f (x、应为正值。 第二步形成一个初始群体(含M个个体)。在边坡滑裂面搜索问题中，取已分析的可能滑裂 面组作为初始群体。 第三步对每一染色体(串)计算其适应值fi ,同时计算群体的总适应值。 第四步选择 计算每一串的选择概率Pi=fi/F 及累计概率。选择一般通过模拟旋转滚花轮 ( roulette ,其上按Pi大小分成大小不等的扇形区、的算法进行。旋转M次即可选出M个串来。在计算机 上实现的步骤是：产生［0,1］间随机数r，若r 遗传算法应用的分析与研究 福州八中钱自强 【摘要】 随着科技水平的不断发展，人们在生产生活中遇到的问题也日益复杂，这些问题常常需要在庞大的搜索空间内寻找最优解或近似解，应用传统算法求解已经显得相当困难。而近年来，生物学的进化论被广泛地应用于工程技术、人工智能等领域中，形成的一类有效的随机搜索算法——进化算法，有效的解决了诸多生产生活中的难题而显得越来越流行。 本文的首先将介绍进化算法的原理以及历史使大家对进化算法有一个初步的了解，其次将详细介绍应用遗传算法解题的步骤，并提出有效改进和应用建议。紧接着通过一个NP难题的优化实例让大家对遗传算法有更深刻的了解，最后通过数据分析证明其方法的有效性。 【关键词】 人工智能；进化算法；遗传算法（GA）；多目标最小生成树 目录 一、进化算法理论 1．1进化算法概述－ 2－ 1．2遗传算法介绍－ 2－ 二、遗传算法 2．1遗传算法基本流程－ 3－ 2．2遗传算法中各重要因素分析－ 3－ 2．3重要参数设置－ 6－ 三、遗传算法在多目标最小生成树问题中的应用 3．1多目标最小生成树－ 7－ 3．2应用遗传算法解决多目标最小生成树－ 9－ 3．3测试－11－ 四、结束语－15－ 附录－16－ 一. 进化算法理论 1．1进化算法概述 从远古时代单细胞开始，历经环境变迁的磨难，生命经历从低级到高级，从简单到复杂的演化历程。生命不断地繁衍生息，产生出具有思维和智能的高级生命体。人类得到生命的最佳结构与形式，它不仅可以被动地适应环境，更重要的是它能够通过学习，模仿与创造，不断提高自己适应环境的能力。 进化算法就是借鉴生物自然选择和遗传机制的随机搜索算法。进化算法通过模拟“优胜劣汰，适者生存”的规律激励好的结构，通过模拟孟德尔的遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。作为随机优化与搜索算法，进化算法具有如下特点：进化算法不是盲目式的乱搜索，也不是穷举式的全面搜索，它根据个体生存环境即目标函数来进行有指导的搜索。进化算法只需利用目标的取值信息而不需要其他信息，因而适用于大规模、高度非线性的不连续、多峰函数的优化，具有很强的通用性；算法的操作对象是一组个体，而非单个个体，具有多条搜索轨迹。 1．2遗传算法 遗传算法（Genetic Algorithm）是进化算法的一个重要分支。它由John Holland提出，最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近来，遗传算法作为问题求解和最优化的有效工具，已被非常成功地应用与解决许多最优化问题并越来越流行。 遗传算法的主要特点是群体搜索策略和群体中个体之间的信息互换,它实际上是模拟由个体组成的群体的整体学习过程,其中每个个体表示问题搜索空间中的一个解点.遗传算法从任一初始的群体出发,通过随机选择，交叉和变异等遗传操作,使群体一代代地进化到搜索空间中越来越好的区域,直至抵达最优解点. 遗传算法和其它的搜索方法相比,其优越性主要表现在以下几个方面：首先,遗传算法在搜索过程中不易陷入局部最优,即使在所定义的适应度函数非连续.不规则也能以极大的概率找到全局最优解,其次,由于遗传算法固有的并行性,使得它非常适合于大规模并行分布处理,此外,遗传算法易于和别的技术(如神经网络.模糊推理.混沌行为和人工生命等)相结合,形成性能更优的问题求解方法. 龙源期刊网 https://www.doczj.com/doc/d15152428.html, 遗传算法的研究及应用 作者：彭志勇邓世权 来源：《计算机光盘软件与应用》2013年第07期 摘要：遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式，它可以应用与生活中的很多领域。 关键词：遗传算法；函数优化；生产调度；自动控制 中图分类号：TP183文献标识码：A文章编号：1007-9599 (2013) 07-0000-02 遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式。与传统的数学模型进行比较，遗传算法有很多的不同的地方，因为它能够解决很多复杂的问题，而传统的数学模型却没办法做到。 1遗传算法的理论研究 1.1遗传算法的由来。美国密西根大学的霍兰德（Holland）将该算法应用于自然和人工系统的自适应行为的研究之中，并且在二十世纪七十年代中期，出版他的第一部著作《自然与人工系统中的适应》。随后，Holland与他的学生们将该算法进行了大力的推广，并把它应用到优化及机器学习等问题之中，而且正式定名为遗传算法。 1.2遗传算法的发展。遗传算法的兴起于20世纪70年代，而到了20世纪80年代的时 候，它正好属于一个发展中的过程，到了20世纪90年代时，它已经发展到了颠疯时刻。为一种实用性较强而又很有效率的优化技术，遗传算法的发展还是非常迅速，在国内外已经造成了非常大的影响力。 1.3遗传算法的基本思想。遗传算法是从一个种群（population）开始的，而这个种群代表问题可能潜在解集的，一个种群是由经过基因（gene）编码（coding）的一定数目的个体（individual）所组成。染色体是遗传物质的主要载体，它是由多个基因的集合，其内部表现是某种基因组合决定的。自从初始种群产生以后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小来挑选（selection）个体，遗传算法是采纳了选择、交叉、变异、迁移、局域 与邻域等自然进化模型，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），从而产生出代表新的解集的种群。 遗传算法和传统搜索算法有很大的不同，它是通过一组随机产生的初始解开始搜索过程。染色体是类似于二进制串的一串符号，对于染色体的测量，我们通常是用适应度来它的好坏 遗传算法的基本理论 一、起源： 早在20世纪50年代和60年代，就有少数人几个计算机科学家独立地进行了所谓的“人工进化系统”研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏形，如大多数系统都遵循“适者生存”的仿自然法则，有些系统采用了基于群体（population）的设计方案，并且加入了自然选择与变异操作，还有一些系统对生物染色体编码进行了抽象处理，应用二进制编码。由于缺乏一种通用的编码方案，人们只能依赖变异而非交叉来产生新的基因结构，早期的算法收敛甚微。20世纪60年代中期，美国Michigan大学的John Holland在A.S.Fraser和H.J.Bremermann等人工作的基础上提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉（即杂交）操作。并且强调将交叉作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了其开创性著作“Adaption in Natural and Artificial System”。以后，Holland等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作作为其广泛、成功地应用奠定了基础。Holland早期有关遗传算法的许多概念一直沿用至今，可见Holland对遗传算法的贡献之大。他认为遗传算法本质上是适应算法，应用最多的是系统最优化的研究。 二、发展： 年份贡献者内容 1962Holland程序漫游元胞计算机自适应系统框架 1968Holland模式定理的建立 1971Hollstein具有交配和选择规则的二维函数优化 1972Bosworth、Foo、Zeigler提出具有复杂变异、类似于遗传算法的基因操作1972Frantz位置非线性和倒位操作研究 1973Holland遗传算法中试验的最优配置和双臂强盗问题 1973Martin类似遗传真法的概率算法理论 1975De Jong用于5个测试函数的研究基本遗传算法基准参数 1975Holland 出版了开创性著作《Adaptation in Natural and Artificial System》 1981Bethke应用Walsh函数分析模式 1981Brindle研究遗传算法中的选择和支配问题 1983Pettit、Swigger遗传算法应用于非稳定问题的粗略研究1983Wetzel用遗传算法解决旅行商问题(TSP) 1984Mauldin基本遗传算法小用启发知识维持遗传多样性1985Baker试验基于排序的选择方法 1985Booker建议采用部分匹配计分、分享操作和交配限制法1985Goldberg、Lingle TSP问题个采用部分匹配交叉 1985Grefenstette、Fitzpattrick对含噪声的函数进行测试 1985Schaffer多种群遗传算法解决多目标优化问题1986Goldberg最优种群大小估计 1986Grefenstette元级遗传算法控制的遗传算法 1987Baker选择中随机误差的减少方法 1987Goldberg复制和交叉时最小欺骗问题(MDP) 1987Goldberg、Richardson借助分享函数的小生境和物种归纳法 遗传算法理论及其应用研究进展 摘要：本文阐述了遗传算法的基本原理以及求解问题的一般过程，讨论了遗传算 法存在的不足和针对其不足采取的弥补措施，概述了遗传算法常见的应用领域。最后，讨论了遗传算法的未来研究方向。 关键词：遗传算法；算子；优化 Development on Genetic Algorithm Theory And Its Application Liu Jun (201320620181) (College of Mecha ni cal Engin eeri ng of Un iversity of South Chi na Hen gya ng Hunan 421001) Abstract: This paper stated the basic theory of Genetic Algorithm (GA) and the process of sol ving the problem, discussed the weak ness of gen etic algorithm and the impro ving measures about gen etic algorithm. Then summarized the com mon applicati on fields of gen etic algorithm. Fin ally, poin ted out the gen etic algorithm ' research direct ions in the future. Keywords: gen etic algorithm (GA); operator; optimizati on 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。遗传算法是模拟自然界生物进化过程与机制求解极值问题的一类自组织、自适应人工智能技术，其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法，具有坚实的生物学基础；它提供从智 能生成过程观点对生物智能的模拟，具有鲜明的认知学意义；它适合于无表达或有表达的任何类函数，具有可实现的并行计算行为；它能解决任何种类实际问题，具有广泛的应用价值。因此，遗传算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学等领域，适用于解决复杂的非线性和多维 2016年第17期 科技创新科技创新与应用 遗传算法的应用研究 赵夫群 （咸阳师范学院，陕西咸阳712000） 1概述 遗传算法（Genetic Algorithms，GA）一词源于人们对自然进化系统所进行的计算机仿生模拟研究，是以达尔文的“进化论”和孟德尔的“遗传学原理”为基础的，是最早开发出来的模拟遗传系统的算法模型。遗传算法最早是由Fraser提出来的，后来Holland对其进行了推广，故认为遗传算法的奠基人是Holland。 随着遗传算法的不断完善和成熟，其应用范围也在不断扩大，应用领域非常广泛，主要包括工业控制、网络通讯、故障诊断、路径规划、最优控制等。近几年，出现了很多改进的遗传算法，改进方法主要包括：应用不同的交叉和变异算子；引入特殊算子；改进选择和复制方法等。但是，万变不离其宗，都是基于自然界生物进化，提出的这些改进方法。 2遗传算法的原理 遗传算法是从某一个初始种群开始，首先计算个体的适应度，然后通过选择、交叉、变异等基本操作，产生新一代的种群，重复这个过程，直到得到满足条件的种群或达到迭代次数后终止。通过这个过程，后代种群会更加适应环境，而末代种群中的最优个体，在经过解码之后，就可以作为问题的近似最优解了。 2.1遗传算法的四个组成部分 遗传算法主要由四个部分组成[1]：参数编码和初始群体、适应度函数、遗传操作和控制参数。编码方法中，最常用的是二进制编码，该方法操作简单、便于用模式定理分析。适应度函数是由目标函数变换而成的，主要用于评价个体适应环境的能力，是选择操作的依据。遗传操作主要包括了选择、交叉、变异等三种基本操作。控制参数主要有：串长Z，群体大小size，交叉概率Pc，变异概率Pm等。目前对遗传算法的研究主要集中在参数的调整中，很多文献建议的参数取值范围一般是：size取20~200之间，Pc取0.5~1.0之间，Pm取0~0.05之间。 2.2遗传算法的基本操作步骤 遗传算法的基本操作步骤为： （1）首先，对种群进行初始化；（2）对种群里的每个个体计算其适应度值；（3）根据（2）计算的适应度，按照规则，选择进入下一代的个体；（4）根据交叉概率Pc，进行交叉操作；（5）以Pm为概率，进行变异操作；（6）判断是否满足停止条件，若没有，则转第（2）步，否则进入（7）；（7）得到适应度值最优的染色体，并将其作为问题的满意解或最优解输出。 3遗传算法的应用 遗传算法的应用领域非常广泛，下面主要就遗传算法在优化问题、生产调度、自动控制、机器学习、图像处理、人工生命和数据挖掘等方面的应用进行介绍。 3.1优化问题 优化问题包括函数优化和组合优化两种。很多情况下，组合优化的搜索空间受问题规模的制约，因此很难寻找满意解。但是，遗传算法对于组合优化中的NP完全问题非常有效。朱莹等[2]提出了一种结合启发式算法和遗传算法的混合遗传算法来解决杂货船装载的优化问题中。潘欣等[3]在化工多目标优化问题中应用了并行遗传算法，实验结果表明该方法效果良好。王大东等[4]将遗传算法应用到了清运车辆路径的优化问题求解中，而且仿真结果表明算法可行有效。 3.2生产调度 在复杂生产调度方面，遗传算法也发挥了很大的作用。韦勇福等[5]将遗传算法应用到了车间生产调度系统的开发中，并建立了最小化完工时间目标模型，成功开发了车间生产调度系统模块，并用实例和仿真验证了该方法的可行性。张美凤等[6]将遗传算法和模拟退火算法相结合，提出了解决车间调度问题的混合遗传算法，并给出了一种编码方法以及建立了相应的解码规则。 3.3自动控制 在自动控制领域中，遗传算法主要用于求解的大多也是与优化相关的问题。其应用主要分为为两类，即离线设计分析和在线自适应调节。GA可为传统的综合设计方法提供优化参数。 3.4机器学习 目前，遗传算法已经在机器学习领域得到了较为广泛的应用。邢晓敏等[7]提出了将遗传算子与Michigan方法和基于Pitt法的两个机器学习方法相结合的机器学习方法。蒋培等[8]提出了一种基于共同进化遗传算法的机器学习方法，该方法克服了学习系统过分依赖于问题的背景知识的缺陷，使得学习者逐步探索新的知识。 3.5图像处理 图像处理是一个重要的研究领域。在图像处理过程中产生的误差会影响图像的效果，因此我们要尽可能地减小误差。目前，遗传算法已经在图像增强、图像恢复、图像重建、图像分形压缩、图像分割、图像匹配等方面应用广泛，详见参考文献[9]。 4结束语 遗传算法作为一种模拟自然演化的学习过程，原理简单，应用广泛，已经在许多领域解决了很多问题。但是，它在数学基础方面相对不够完善，还有待进一步研究和探讨。目前，针对遗传算法的众多缺点，也相继出现了许多改进的算法，并取得了一定的成果。可以预期，未来伴随着生物技术和计算机技术的进一步发展，遗传算法会在操作技术等方面更加有效，其发展前景一片光明。 参考文献 [1]周明，孙树栋.遗传算法原理及应用[M].国防工业出版社，1999，6. [2]朱莹，向先波，杨运桃.基于混合遗传算法的杂货船装载优化问题[J].中国船舰研究，2015：10（6）：126-132. [3]潘欣，等.种群分布式并行遗传算法解化工多目标优化问题[J].化工进展，2015：34（5）：1236-1240. [4]王大东，刘竞遥，王洪军.遗传算法求解清运车辆路径优化问题[J].吉林师范大学学报（自然科学版），2015（3）：132-134. [5]韦勇福，曾盛绰.基于遗传算法的车间生产调度系统研究[J].装备制造技术，2014（11）：205-207. [6]黄巍，张美凤.基于混合遗传算法的车间生产调度问题研究[J].计算机仿真，2009，26（10）：307-310. [7]邢晓敏.基于遗传算法的机器学习方法赋值理论研究[J].软件导刊[J].2009，8（11）：80-81. [8]蒋培.基于共同进化遗传算法的机器学习[J].湖南师范大学自然科学学报，2004，27（3）：33-38. [9]田莹，苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报，2007，12（3）：389-396. [10]周剑利，马壮，陈贵清.基于遗传算法的人工生命演示系统的研究与实现[J].制造业自动化，2009，31（9）：38-40. [11]刘晓莉，戎海武.基于遗传算法与神经网络混合算法的数据挖掘技术综述[J].软件导刊，2013，12（12）：129-130. 作者简介：赵夫群（1982，8-），女，汉族，籍贯：山东临沂，咸阳师范学院讲师，西北大学在读博士，工作单位：咸阳师范学院教育科学学院，研究方向：三维模型安全技术。 摘要：遗传算法是一种非常重要的搜索算法，特别是在解决优化问题上，效果非常好。文章首先介绍了遗传算法的四个组成部分，以及算法的基本操作步骤，接着探讨了遗传算法的几个主要应用领域，包括优化、生产调度、机器学习、图像处理、人工生命和数据挖掘等。目前遗传算法以及在很多方面的应用中取得了较大的成功，但是它在数学基础方面相对还不够完善，因而需要进一步研究和完善。 关键词：遗传算法；优化问题；数据挖掘 67 -- 遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机 论文 题目：遗传应用算法 院系：计算机工程系 专业：网络工程 班级学号： 学生姓名： 2014年10月23日 摘要: 遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处理复杂的非线性问题,因此有着广阔的应用前景。 关键词: 遗传算法; 化学计量学; 优化 THEORY AND APPL ICATION OF GENETIC AL GORITHM ABSTRACT: Genetic Algo rithm( GA) is a kind of recursive computational procedure based on the simulation of principle principles of evaluati on of living organisms in nature1Based on brief int roduction of the principle ,the beginning and development of the algorithms ,the pape r reviewed its applications in the fields of optimization ,fitting an d calibration,structure analysis and spectra interpretation variable selection ,and it s usage in combination with othersThe application o f GA needs no initiating knowledge of the system ,and therefore is a comprehensive optimization method with extensive application in terms of processing complex nonlinear problems。 KEY WORDS : Genetic Algorithm( GA) Chemometrics Optimization 遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法，它于1962年被提出，直到1989年才最终形成基本框架。遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 由美国J. H. Ho llad教授提出, 其主要特点是群体搜索策略和群体中个体之间的信息交换。该算法尤其适用于处理传统搜索方法难以解决的复杂和非线性问题, 可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。 顾名思义,遗传算法(Genetic Algorithm ,GA)是模拟自然界生物进化机制的一种算法 ,即遵循适者生存、优胜劣汰的法则 ,也就是寻优过程中有用的保留 ,无用的则去除。在科学和生产实践中表现为 ,在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法 ,即找出一个最优解。这种算法是 1960 年由 基本遗传算法及应用举例 遗传算法(Genetic Algorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。遗传算法是多学科相互结合与渗透的产物。目前它已发展成一种自组织、自适应的多学科技术。 针对各种不同类型的问题，借鉴自然界中生物遗传与进化的机理，学者们设计了不同的编码方法来表示问题的可行解，开发出了许多不同环境下的生物遗传特征。这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。但这些遗传算法有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。基于此共同点，人们总结出了最基本的遗传算法——基本遗传算法。基本遗传算法只使用选择、交叉、变异三种基本遗传操作。遗传操作的过程也比较简单、容易理解。同时，基本遗传算法也是其他一些遗传算法的基础与雏形。 1．1．1 编码方法 用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。 编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L 称为染色体的长度或称为符号串的长度。一般染色体的长度L 为一固定的数，如 X=1010100 表示一个个体，该个体的染色体长度L=20。 二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a ，b]，我们用长度为L 的二进制编码符号串来表示该参数，总共能产生L 2种不同的编码，若参数与编码的对应关系为 00000000000……00000000=0 →a 00000000000……00000001=1 →a+δ ? ? ? ……=L 2-1→b 则二进制编码的编码精度1 2--= L a b δ 假设某一个个体的编码是kl k k k a a a x 21=，则对应的解码公式为 )2(121 ∑=---+=L j j L kj L k a a b a x 例如，对于x ∈[0,1023],若用长度为10的二进制编码来表示该参数的话，则下述符号串： 基于数据挖掘的遗传算法 xxx 摘要:本文定义了遗传算法概念和理论的来源，介绍遗传算法的研究方向和应用领域，解释了遗传算法的相关概念、编码规则、三个主要算子和适应度函数，描述遗传算法计算过程和参数的选择的准则，并且在给出的遗传算法的基础上结合实际应用加以说明。 关键词：数据挖掘遗传算法 Genetic Algorithm Based on Data Mining xxx Abstract：This paper defines the concepts and theories of genetic algorithm source, Introducing genetic algorithm research directions and application areas, explaining the concepts of genetic algorithms, coding rules, the three main operator and fitness function，describing genetic algorithm parameter selection process and criteria，in addition in the given combination of genetic algorithm based on the practical application. Key words: Data Mining genetic algorithm 前言 遗传算法(genetic algorithm，GAs)试图计算模仿自然选择的过程，并将它们运用于解决商业和研究问题。遗传算法于20世界六七十年代由John Holland[1]发展而成。它提供了一个用于研究一些生物因素相互作用的框架，如配偶的选择、繁殖、物种突变和遗传信息的交叉。在自然界中，特定环境限制和压力迫使不同物种竞争以产生最适应于生存的后代。在遗传算法的世界里，会比较各种候选解的适合度，最适合的解被进一步改进以产生更加优化的解。 遗传算法借助了大量的基因术语。遗传算法的基本思想基于达尔文的进化论和孟德尔的遗传学说，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。生物在自然界的生存繁殖，显示对其自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机制研究和行为模拟。通过仿效生物的进化与遗传，根据“生存竞争”和“优胜劣汰”的原则，借助选择、交叉、变异等操作，使所要解决的问题从随机初始解一步步逼近最优解。现在已经广泛的应用于计算机科学、人工智能、信息技术及工程实践。[2]在工业、经济管理、交通运输、工业设计等不同领域，成功解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。遗传算法作为一类自组织于自适应的人工智能技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。 1.遗传算法的应用领域和研 究方向 1.1遗传算法的特点 遗传算法作为一种新型、模拟生物进化过程的随机化搜索方法，在各类结 构对象的优化过程中显示出比传统优 化方法更为独特的优势和良好的性能。 它利用其生物进化和遗传的思想，所以 它有许多传统算法不具有的特点[3]： ※搜索过程不直接作用在变量上，而是 作用于由参数集进行了编码的个体 上。此编码操作使遗传算法可以直接 对结构对象进行操作。 ※搜索过程是从一组解迭代到另一组 解，采用同时处理群体中多个个体的 方法，降低了陷入局部最优解的可能 性，易于并行化。 第七章 遗传算法应用举例 遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域。随着对遗传算法技术的不断研究，人们对遗传算法的实际应用越来越重视，它已经广泛地应用于函数优化、组合优化、自动控制、机器人学、图象处理、人工生命、遗传编码、机器学习等科技领域。遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等多方面的应用取得了成功。本章通过一些例子，介绍如何利用第五章提供的遗传算法通用函数，编写MATLAB 程序，解决实际问题。 7.1 简单一元函数优化实例 利用遗传算法计算下面函数的最大值： ()sin(10) 2.0[1,2]f x x x x π=?+∈-， 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9，最大遗传代数为25。 下面为一元函数优化问题的MA TLAB 代码。 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 = recombin ('xovsp',SelCh,0.7); % 重组 SelCh = mut(SelCh); % 变异 variable=bs2rv(SelCh,FieldD); % 子代个体的十进制转换 ObjVSel =variable.*sin(10*pi*variable)+2.0; % 计算子代的目标函数值 [Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV ,ObjVSel); % 重插入子代的新种群 gen = gen+1; % 代计数器增加 % 输出最优解及其序号，并在目标函数图象中标出，Y 为最优解，I 为种群的序号 [Y,I]=max(ObjV),hold on; plot (variable (I),Y , 'bo'); trace (1,gen)=max (ObjV); %遗传算法性能跟踪 基本遗传算法应用实例。用基本遗传算法求下面函数的最大值 10090060)(23++-=x x x x f 300≤≤x 个体数目取50，最大进化代数取100，离散精度取0.001，杂交概率取0.9，变异概率取0.004 1、在editor 中建立基本遗传算法函数：GA 程序如下： function[xv,fv]=GA(fitness,a,b,NP,NG,pc,pm,eps) %待优化的目标函数:fitness %自变量下界:a %自变量上界:b %种群个体数:NP %最大进化代数:NG %杂交概率:pc %自变量概率:pm %自变量离散精度:eps %目标函数取最小值时的自变量值：xm %目标函数的最小值:fv L=ceil(log2((b-a)/eps+1)); %根据离散精度，确定二进制编码需要的码长 x=zeros(NP,L); for i=1:NP x(i,:)=Initial(L);%种群初始化 fx(i)=fitness(Dec(a,b,x(i,:),L)); %个体适应值 end for k=1:NG sumfx=sum(fx); %所有个体适应值之和 px=fx/sumfx; %所有个体适应值的平均值 ppx=0; ppx(1)=px(1); for i=2:NP %用于轮盘赌策略的累加 ppx(i)=ppx(i-1)+px(i); end for i=1:NP sita=rand(); for n=1:NP if sita<=ppx(n) SelFather=n; %根据轮盘赌策略确定的父亲 break; end end Selmother=floor(rand()*(NP-1))+1; %随机选择母亲 posCut=floor(rand()*(L-2))+1; %随机选择交叉点 r1=rand(); if r1<=pc %交叉 遗传算法的特点及其应用 上海复旦大学附属中学张宁 目录 【关键词】 【摘要】 【正文】 §1遗传算法的基本概念 §2简单的遗传算法 1．选择 2．交换 3．变异 §3简单的遗传算法运算示例 1．计算机公司的经营策略优化问题 2．函数优化问题 §4遗传算法应用举例 1．子集和问题 2．TSP（旅行商）问题 §5结束语 【附录】 1．子集和问题源程序 2．TSP（旅行商）问题源程序 【参考文献】 【关键词】 遗传算法遗传变异染色体基因群体 【摘要】 遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。 文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于NP-完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。 文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。 【正文】 遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得我们进行深入的讨论。 要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。 §1遗传算法的基本概念 遗传算法（Genetic Algorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它大学课件--遗传算法应用的分析与研究-
遗传算法的研究及应用
遗传算法
遗传算法理论及其研究进展
遗传算法的应用研究_赵夫群
遗传算法及其在TSP问题中的应用
遗传算法应用论文
基本遗传算法及应用举例
基于数据挖掘的遗传算法
第七章遗传算法应用举例
matlab基本遗传算法应用实例
遗传算法的特点及其应用
相关主题
文本预览