遗传算法基本理论实例

目录

_

一、遗产算法的由来 (2)

二、遗传算法的国内外研究现状 (3)

三、遗传算法的特点 (5)

四、遗传算法的流程 (7)

五、遗传算法实例 (12)

六、遗传算法编程 (17)

七、总结 ......... 错误!未定义书签。附录一：运行程序.. (19)

遗传算法基本理论与实例

一、遗产算法的由来

遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。20世纪40年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型，以及模拟进化过程的算法进行了长期的开拓性的探索和研究。John H.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向。

遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。，直至消亡。达尔文把这一过程和现象叫做“自然选择，适者生存”。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的

基本规律。

遗传算法由美国的John H.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。

二、遗传算法的国内外研究现状

遗传算法的鼻祖是美国Michigan大学的Holland教授及其学生。他们受到生物模拟技术的启发，创造了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术——遗传算法。1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码方法。Holland教授用遗传算法的思想对自然和人工自适应系统进行了研究，提出了遗传算法的基本理论——模式定理（Schema Theorem）并于1957年出版了第一本系统论述遗传算法和人工自适应系统的专著《Adaptation in Natural and Artificial Systems》。20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统，开创了遗传算法的机器学习的新概念。1975年，De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。1989年，Goldberg出版了《Genetic Algorithm in Search，Optimization and Machine Learning》一书，系统地总

结了遗传算法的主要研究成果，全面完整的论述了遗传算法的基本原理及其应用。1991年，David出版了《Handbook of Genetic Algorithms》一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程（Genetic Programming，简称GP）的概念。在控制系统的离线设计方面遗传算法被众多的使用者证明是有效的策略。例如，Krishnakumar和Goldberg以及Bramlette和Gusin已证明使用遗传优化方法在太空应用中导出优异的控制器结构比使用传统方法如LQR和Powell（鲍威尔）的增音机设计所用的时间要少（功能评估）。Porter和Mohamed展示了使用本质结构分派任务的多变量飞行控制系统的遗传设计方案。与此同时，另一些人证明了遗传算法如何在控制器结构的选择中使用。

从遗传算法的整个发展过程来看，20世纪70年代是兴起阶段，20世纪80年代是发展阶段，20世纪90年代是高潮阶段。遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起国内外学者的高度重视。

近些年来，国内外很多学者在遗传算法的编码表示、适应度函数、遗传算子、参数选择、收敛性分析、欺骗问题和并行遗传算法上做出了大量的研究和改进。还有很多学者将遗传算法和其他只能算法结合，进一步提高局部搜索能力。在遗传算法的应用上也有很多改进。由于遗传算法具有全局并行搜索、简单通用、鲁棒性强等优点，使得遗传算法广泛地应用于计算机科学、自动控制、人工智能、工程设计、制造业、生物工程和社会科学等领域。针对遗传算法的一些问题，还有一些问题需要进一步的探究，将大大促进遗传算法理论和应用的发展，遗传算法必将在智能计算领域中展现出更加光明的前景。

三、遗传算法的特点

遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法。它与传统的算法不同，大多数古典的优化算法是基于一个单一的度量函数（评估函数）的梯度和较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖梯度信息，而是通过模拟自然进化进程来搜索最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的群体的进化过程。遗传算法通过有组织的、随机的信息交换来重新组合那些适应性好的串，生成新的串的群体。

遗传算法有以下优点：

（1）对可行解表示的广泛性。遗传算法的处理对象不是参数本身，而是针对那些通过参数集进行编码的基因个体，此编码操作使得遗传算法可以直接对结构对象进行操作。所谓结构对象，泛指集合、序列、矩阵、树、链、表等各种一维或二维甚至多维结构形式的对象。这一特点使得遗传算法具有广泛的应用领域。比如通过对连接矩阵的操作，遗传算法可用来对神经网络或自动机的结构或参数加以优化；通过对集合的操作，遗传算法可实现对规则集合和知识库的精炼而达到高质量的机器学习目的；通过对树结构的操作，用遗传算法可得到用于分类的最佳决策树；通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理，可自动构造顺序控制系统。

（2）群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。相反，遗传算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。这一特点使遗传算法具有较好的全局搜索性能，也使得算法本身易于并行化。

（3）不需要辅助信息。遗传算法仅用适应度函数来的数值来评估基因个体，并在此基础上尽心遗传操作。更重要的是，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，编码必须与可行解空间对应，不能有死码。由于限制条件的缩小，使得遗传算法的应用范围大大扩展。

（4）内在启发式随机搜索特性。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。概率不仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动的。虽然看起来它是一种盲目搜索方法，实际上它有明确的搜索方向，具有内在的并行搜索机制。

（5）遗传算法在搜索过程中不容易陷入局部最优，即时在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。

（6）遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困难的问题。

（7）遗传算法具有固有的并行性和并行计算的能力。

（8）遗传算法具有可扩展性，易于同别的技术混合使用。

遗传算法作为一种优化算法，也有它自身的局限性：

（1）编码不规范及编码存在表示的不准确性。

（2）单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。

（3）遗传算法通常的效率比其他传统的优化方法低。

（4）遗传算法容易出现过早收敛。

（5）遗传算法对算法的精度、可信度、计算复杂性等方面，还没有有效的定量分析方法。

遗传算法的基本内容如下：

个体和种群。个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若干个体组成的群体，它一般是整个搜索空间的一个很小的子集。

适应度与适应度函数。适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。适应度函数（fitness function）就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。

染色体与基因。染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如个体上9，染色体的表示形式是1001，0和1是染色体上的基因。

遗传操作。也称为遗传算子，就是关于染色体的运算。遗传算法中有三种遗传操作：选择-复制，交叉和变异。

四、遗传算法的流程

遗传算法在整个进化过程中的遗传操作是随机的，但它所呈现出的特性并不是完全搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集。这样一代代的不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算法所涉及的五大要素是：参数编码、初始种群的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。流程如图1所示。

图1 遗传算法基本流程

简单遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作内容和基本步骤如下：

1）选择编码策略，把参数集合X和域转换为位串结构空间S。

2）定义适应度函数。

3）确定遗传策略，包括选择群体大小n，选择、交叉、变异方法，以及确定交叉概率、变异概率等遗传参数。

4）随机初始化生成种群P。

5）计算群体中个体位串解码后的适应度值。

6）按照遗传策略，运用选择、交叉和变异算子作用与群体，形成下一代群体。

7）判断群体性能是否满足某一目标，或者已完成预定迭代次数，不满足则

返回步骤6），或者修改遗传策略再返回步骤6）。

下面对基本步骤进行分解，进一步详细介绍流程中一些细节。

编码表示。在许多问题求解中，编码是遗传算法中首要解决的问题，对算法的性能有很重要的影响。Holland 提出的二进制编码是遗传算法中最常用的一种编码方法，它采用最小字符编码原则， 编/解码操作简单易行，利于交叉、变异操作的实现，也可以采用模式定理对算法进行理论分析。但二进制编码用于多维、高精度数值问题优化时，不能很好地克服连续函数离散化时的映射误差；不能直接反映问题的固有结构，精度不高，并且个体长度大、占用内存多。针对二进制编码存在的不足，人们提出了多种改进方法，比较典型的有以下几种：

（1）格雷码编码。为了克服二进制编码在连续函数离散化时存在的不足，人们提出了用格雷码进行编码的方法，它是二进制编码的变形。格雷码不仅具有二进制编码的一些优点，而且能够提高遗传算法的局部搜索能力。假设有一个二进制编码为121m m X x x x x -=???，其对应的格雷码为121m m Y y y y y -=???，则 m m y x = 1,2,,1i m m =--???

1i i i y x x +=⊕

（2）实数编码。该方法适合于遗传算法中表示范围较大的数，使遗传算法更接近问题空间，避免了编码和解码的过程。它便于较大空间的遗传搜索，提高了遗传算法的精度要求；便于设计专门问题的遗传算子；便于算法与经典优化方法的混合作用，改善了遗传算法的计算复杂性，提高了运算效率。

（3）十进制编码。该方法利用十进制编码控制参数，缓解了“组合爆炸”和遗传算法的早熟收敛问题。

（4）非数值编码。染色体编码串中的基因值取一个仅有代码含义而无数值含义的符号集，这些符号可以是数字也可以是字符。非数值编码的优点是在遗传算法中可以利用所求问题的专门知识及相关算法。对于非数值编码，问题的解和染色体的编码要注意染色体的可行性、染色体的合法性和映射的惟一性。

适应度函数。在遗传算法中，适应度是描述个体性能的主要指标，根据适应度的大小对个体进行优胜劣汰。对于求解有约束的优化问题时，一般采用罚函数方法将目标函数和约束条件建立成一个无约束的优化目标函数；然后再将目标函数作适当处理，建立适合遗传算法的适应度函数。将目标函数转换成适应度函数一般应遵循两个原则：适应度必须非负；优化过程中目标函数的变化方向应与群体进化过程中适应度函数变化方向一致。在使用遗传算法求解具体问题时，适应度函数的选择对算法的收敛性以及收敛速度的影响较大，针对不同的问题需根据经验或算法来确定相应的参数。

遗传算子。在遗传算法中通过一系列算子来决定后代，算子对当前群体中选定的成员进行重组和变异。

（1）选择算子选择操作通过适应度选择优质个体而抛弃劣质个体，体现了“适者生存”的原理。

常见的选择操作主要有以下几种：a）轮盘赌选择。选择某假设的概率是通过这个假设的适应度与当前群体中其他成员的适应度的比值而得到。此方法是基于概率选择的，存在统计误差，因此可以结合最优保存策略以保证当前适应度最优的个体能够进化到下一代而不被遗传操作的随机性破坏，保证算法的收敛性。b）排序选择。对个体适应度取正值或负值以及个体适应度之间的数值差异程度无特殊要求，对群体中的所有个体按其适应度大小进行排序，根据排序来分配各

个体被选中的概率。c）最优个体保存。父代群体中的最优个体直接进入子代群体中。该方法可保证在遗传过程中所得到的个体不会被交叉和变异操作所破坏，它是遗传算法收敛性的一个重要保证条件；它也容易使得局部最优个体不易被淘汰，从而使算法的全局搜索能力变强。d）随机联赛选择。每次选取N个个体中适应度最高的个体遗传到下一代群体中。具体操作如下：从群体中随机选取N 个个体进行适应度大小比较，将其中适应度最高的个体遗传到下一代群体中；将上述过程重复执行M（为群体大小）次，则可得到下一代群体。

（2）交叉算子交叉是指对两个相互交叉的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。它是产生新个体的主要方法，决定了遗传算法的全局搜索能力，在遗传算法中起关键作用。几种常用的适用于二进制编码或实数编码方式的交叉算子如下：a）单点交叉。在个体编码串中随机设置一个交叉点后在该点相互交换两个配对个体的部分基因。b）两点交叉。在相互配对的两个个体编码串中随机设置两个交叉点，并交换两个交叉点之间的部分基因。c）均匀交叉。两个相互配对个体的每一位基因都以相同的概率进行交换，从而形成两个新个体。d）算术交叉。由两个个体的线性组合而产生出新的个体。

（3）变异算子变异是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。它是产生新个体的辅助方法，决定了遗传算法的局部搜索能力。变异算子与交叉算子相互配合，可以共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法以良好的搜索性能完成最优化问题的寻优过程。在遗传算法中使用变异算子主要有以下两个目的: 改善遗传算法的局部搜索能力；维持群体的多样性，防止出现早熟现象。下面是几种常用的变异操作：a）基本位变异。对个体编码串以变异概率P随机指

遗传算法求解实例

yj1.m ：简单一元函数优化实例，利用遗传算法计算下面函数的最大值 0.2)*10sin()(+=x x x f π，∈x [-1, 2] 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9， 最大遗传代数为25 译码矩阵结构：?????????? ??????? ???? ?=ubin lbin scale code ub lb len FieldD 译码矩阵说明： len – 包含在Chrom 中的每个子串的长度，注意sum(len)=length(Chrom)； lb 、ub – 行向量，分别指明每个变量使用的上界和下界； code – 二进制行向量，指明子串是怎样编码的，code(i)=1为标准二进制编码， code(i)=0则为格雷编码； scale – 二进制行向量，指明每个子串是否使用对数或算术刻度，scale(i)=0为算术 刻度，scale(i)=1则为对数刻度； lbin 、ubin – 二进制行向量，指明表示范围中是否包含每个边界，选择lbin=0或 ubin=0，表示从范围中去掉边界；lbin=1或ubin=1则表示范围中包含边界； 注：增加第22行：variable=bs2rv(Chrom, FieldD);否则提示第26行plot(variable(I), Y, 'bo'); 中variable(I)越界 yj2.m ：目标函数是De Jong 函数，是一个连续、凸起的单峰函数，它的M 文件objfun1包含在GA 工具箱软件中，De Jong 函数的表达式为： ∑ == n i i x x f 1 2 )(， 512512≤≤-i x 这里n 是定义问题维数的一个值，本例中选取n=20，求解 )(min x f ，程序主要变量： NIND （个体的数量）：＝40； MAXGEN （最大遗传代数）：=500； NV AR （变量维数）：=20； PRECI （每个变量使用多少位来表示）：=20； GGAP （代沟）：=0.9 注：函数objfun1.m 中switch 改为switch1，否则提示出错，因为switch 为matlab 保留字，下同！ yj3.m ：多元多峰函数的优化实例，Shubert 函数表达式如下，求)(min x f 【shubert.m 】

基本遗传算法及应用举例

基本遗传算法及应用举例 遗传算法(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的二进制编码来表示该参数的话，则下述符号串：

遗传算法实例

遗传算法实例.txt懂得放手的人找到轻松，懂得遗忘的人找到自由，懂得关怀的人找到幸福！女人的聪明在于能欣赏男人的聪明。生活是灯，工作是油，若要灯亮，就要加油！相爱时，飞到天边都觉得踏实，因为有你的牵挂；分手后，坐在家里都觉得失重，因为没有了方向。遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。 对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法 % % 求下列函数的最大值 % % f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] % % 将 x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为 (10-0)/(2^10-1)≈0.01 。 % % 将变量域 [0,10] 离散化为二值域 [0,1023], x=0+10*b/1023, 其中 b 是 [0,1023] 中的一个二值数。 % % % %--------------------------------------------------------------------------------------------------------------% %--------------------------------------------------------------------------------------------------------------% % 编程 %----------------------------------------------- % 2.1初始化(编码) % initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)， % 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元为 {0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 % 2.2 计算目标函数值 % 2.2.1 将二进制数转化为十进制数(1) %遗传算法子程序 %Name: decodebinary.m %产生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制 function pop2=decodebinary(pop) [px,py]=size(pop); %求pop行和列数 for i=1:py

遗传算法经典MATLAB代码

遗传算法经典学习Matlab代码 遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。 对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法 % % 求下列函数的最大值 % % f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] % % 将 x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为 (10-0)/(2^10-1)≈0.01。 % % 将变量域 [0,10] 离散化为二值域 [0,1023], x=0+10*b/1023, 其 中 b 是 [0,1023] 中的一个二值数。 % % % %--------------------------------------------------------------------------------------------------------------% %--------------------------------------------------------------------------------------------------------------% % 编程 %----------------------------------------------- % 2.1初始化(编码) % initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)，

% 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元 为 {0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 % 2.2 计算目标函数值 % 2.2.1 将二进制数转化为十进制数(1) %遗传算法子程序 %Name: decodebinary.m %产生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制function pop2=decodebinary(pop) [px,py]=size(pop); %求pop行和列数 for i=1:py pop1(:,i)=2.^(py-i).*pop(:,i); end pop2=sum(pop1,2); %求pop1的每行之和 % 2.2.2 将二进制编码转化为十进制数(2) % decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置

第七章遗传算法应用举例

第七章 遗传算法应用举例 遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域。随着对遗传算法技术的不断研究，人们对遗传算法的实际应用越来越重视，它已经广泛地应用于函数优化、组合优化、自动控制、机器人学、图象处理、人工生命、遗传编码、机器学习等科技领域。遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等多方面的应用取得了成功。本章通过一些例子，介绍如何利用第五章提供的遗传算法通用函数，编写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); %遗传算法性能跟踪

(实例)matlab遗传算法工具箱函数及实例讲解

matlab遗传算法工具箱函数及实例讲解 核心函数： (1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始种群的生成函数 【输出参数】 pop--生成的初始种群 【输入参数】 num--种群中的个体数目 bounds--代表变量的上下界的矩阵 eevalFN--适应度函数 eevalOps--传递给适应度函数的参数 options--选择编码形式(浮点编码或是二进制编码)[precision F_or_B], 如 precision--变量进行二进制编码时指定的精度 F_or_B--为1时选择浮点编码，否则为二进制编码,由precision指定精度) (2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,... termFN,termOps,selectFN,selectOps,xOverFNs,xOverO ps,mutFNs,mutOps)--遗传算法函数 【输出参数】 x--求得的最优解 endPop--最终得到的种群 bPop--最优种群的一个搜索轨迹 【输入参数】 bounds--代表变量上下界的矩阵 evalFN--适应度函数 evalOps--传递给适应度函数的参数 startPop-初始种群 opts[epsilon prob_ops display]--opts(1:2)等同于initializega 的options参数，第三个参数控制是否输出，一般为0。如[1e-6 1 0] termFN--终止函数的名称,如['maxGenTerm'] termOps--传递个终止函数的参数,如[100] selectFN--选择函数的名称,如['normGeomSelect'] selectOps--传递个选择函数的参数,如[0.08] xOverFNs--交叉函数名称表，以空格分开，如['arithXover heuristicXover simpleXover'] xOverOps--传递给交叉函数的参数表，如[2 0;2 3;2 0] mutFNs--变异函数表，如['boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation'] mutOps--传递给交叉函数的参数表,如[4 0 0;6 100 3;4 100 3;4 0 0]

基于遗传算法的库位优化问题

Logistics Sci-Tech 2010.5 收稿日期：2010－02－07 作者简介：周兴建（1979-），男，湖北黄冈人，武汉科技学院经济管理学院，讲师，武汉理工大学交通学院博士研究生，研究方向：物流价值链、物流系统规划；刘元奇（1988-），男，甘肃天水人，武汉科技学院经济管理学院；李泉（1989-），男，湖北 武汉人，武汉科技学院经济管理学院。 文章编号：1002-3100(2010)05-0038-03 物流科技2010年第5期Logistics Sci-Tech No.5,2010 摘 要：应用遗传算法对邯运集团仓库库位进行优化。在充分考虑邯运集团仓库所存放的货物种类、货物数量、出入库频 率等因素的基础上进行库位预分区规划，建立了二次指派问题的数学模型。利用遗传算法对其求解，结合MATLAB 进行编程计算并得出最优划分方案。 关键词：遗传算法；预分区规划；库位优化中图分类号：F253.4 文献标识码：A Abstract:The paper optimize the storage position in warehouse of Hanyun Group based on genetic algorithm.With thinking of the factors such as goods categories,quantities and frequencies of I/O,etc,firstly,the storage district is planned.Then the model of quadratic assignment problems is build,and genetic algorithm is utilized to resolve the problem.The software MATLAB is used to program and figure out the best alternatives. Key words:genetic algorithm;district planning;storage position optimization 1 库位优化的提出 邯郸交通运输集团有限公司（简称“邯运集团”）是一家集多种业务为一体的大型综合性物流企业。邯运集团的主要业务板块有原料采购（天信运业及天昊、天诚、天恒等）、快递服务（飞马快运）、汽贸业务（天诚汽贸）及仓储配送（河北快运）等。其中，邯运集团的仓储配送业务由河北快运经营，现有仓库面积总共40000㎡，主要的业务范围为医药、日用百货、卷烟、陶瓷、化工产品的配送，其中以医药为主。邯运集团库存货物主要涉及两个方面：一个是大宗的供应商货物，如医药，化工产品等；另一方面主要是大规模的小件快递货物，如日用百货等[1]。经分析，邯运集团在仓储运作方面存在如下问题： （1）存储货物繁多而分拣速度低下。仓库每天到货近400箱，有近200多种规格，缺乏一套行之有效的仓储管理系统。（2）货架高度不当而货位分配混乱。现在采用的货架高度在2米以上，而且将整箱货物直接码垛在货架上，不严格按货位摆放。当需要往货架最上层码放货物需要借助梯子，增加操作难度且操作效率较低。货物在拣货区货架摆放是以件为单位的，分拣和搬运速度较慢。 （3）拣货货架设计不当而仓储效率低下。发货前装箱工作主要由人工协同完成，出库效率低，出错率难以控制。 （4）存储能力和分拣能力不能满足需求。根据邯运集团的业务发展现状及趋势，现有的仓库储存和分拣能力远远达不到集团公司对配送业务量的需求。 当前邯运集团的货位分配主要采用物理地址编码的方式，很少考虑货位分配对仓储管理员工作效率的影响。对其进行库位优化设计不仅直接影响到其库存量的大小、出入库的效率，还间接影响到邯运集团的整体经营效益。本文对邯运集团的仓库货位进行优化时，结合考虑仓库所存放的货物种类、货物数量、出入库频率等因素，对仓库货位进行规划，以提高仓储效率。 2库位预分区规划 在进行仓库货位规划时，作如下假设： （1）货物的存放种类已知； （2）货物每种类的单位时间内存放的数量己知； （3） 每一种货物的存取频率已知。 在仓库货位优化中一个重要的环节即预分区。所谓预分区，是指没有存放货物时的分区，分区时只考虑仓储作业人员的速基于遗传算法的库位优化问题 Optimization of Storage Position in Warehouse Based on Genetic Algorithm 周兴建1,2，刘元奇1，李泉1 ZHOU Xing-jian 1,2,LIU Yuan-qi 1,LI Quan 1 （1.武汉科技学院经济管理学院，湖北武汉430073；2.武汉理工大学交通学院，湖北武汉430063） (1.College of Economics &Management,Wuhan University of Science &Engineering,Wuhan 430073,China; 2.School of Transportation,Wuhan University of Technology,Wuhan 430063,China) !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 38

三个遗传算法matlab程序实例

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

遗传算法的C语言程序案例

遗传算法的C语言程序案例 一、说明 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．举个例子，输入初始变量后，用y= (x1*x1)+(x2*x2)，其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 4．程序流程图

5．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual { char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 6．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个

使用MATLAB遗传算法工具实例(详细) (1)【精品毕业设计】(完整版)

最新发布的MA TLAB 7.0 Release 14已经包含了一个专门设计的遗传算法与直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox，GADS）。使用遗传算法与直接搜索工具箱，可以扩展MATLAB及其优化工具箱在处理优化问题方面的能力，可以处理传统的优化技术难以解决的问题，包括那些难以定义或不便于数学建模的问题，可以解决目标函数较复杂的问题，比如目标函数不连续、或具有高度非线性、随机性以及目标函数没有导数的情况。 本章8.1节首先介绍这个遗传算法与直接搜索工具箱，其余各节分别介绍该工具箱中的遗传算法工具及其使用方法。 8.1 遗传算法与直接搜索工具箱概述 本节介绍MATLAB的GADS（遗传算法与直接搜索）工具箱的特点、图形用户界面及运行要求，解释如何编写待优化函数的M文件，且通过举例加以阐明。 8.1.1 工具箱的特点 GADS工具箱是一系列函数的集合，它们扩展了优化工具箱和MA TLAB数值计算环境的性能。遗传算法与直接搜索工具箱包含了要使用遗传算法和直接搜索算法来求解优化问题的一些例程。这些算法使我们能够求解那些标准优化工具箱范围之外的各种优化问题。所有工具箱函数都是MATLAB的M文件，这些文件由实现特定优化算法的MATLAB语句所写成。 使用语句 type function_name 就可以看到这些函数的MATLAB代码。我们也可以通过编写自己的M文件来实现来扩展遗传算法和直接搜索工具箱的性能，也可以将该工具箱与MATLAB的其他工具箱或Simulink结合使用，来求解优化问题。 工具箱函数可以通过图形界面或MA TLAB命令行来访问，它们是用MATLAB语言编写的，对用户开放，因此可以查看算法、修改源代码或生成用户函数。 遗传算法与直接搜索工具箱可以帮助我们求解那些不易用传统方法解决的问题，譬如表查找问题等。 遗传算法与直接搜索工具箱有一个精心设计的图形用户界面，可以帮助我们直观、方便、快速地求解最优化问题。 8.1.1.1 功能特点 遗传算法与直接搜索工具箱的功能特点如下： 图形用户界面和命令行函数可用来快速地描述问题、设置算法选项以及监控进程。 具有多个选项的遗传算法工具可用于问题创建、适应度计算、选择、交叉和变异。 直接搜索工具实现了一种模式搜索方法，其选项可用于定义网格尺寸、表决方法和搜索方法。 遗传算法与直接搜索工具箱函数可与MATLAB的优化工具箱或其他的MATLAB程序结合使用。 支持自动的M代码生成。 8.1.1.2 图形用户界面和命令行函数 遗传算法工具函数可以通过命令行和图形用户界面来使用遗传算法。直接搜索工具函数也可以通过命令行和图形用户界面来进行访问。图形用户界面可用来快速地定义问题、设置算法选项、对优化问题进行详细定义。 133

matlab基本遗传算法应用实例

基本遗传算法应用实例。用基本遗传算法求下面函数的最大值 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 %交叉

遗传算法基本理论实例

目录 _ 一、遗产算法的由来 (2) 二、遗传算法的国内外研究现状 (3) 三、遗传算法的特点 (5) 四、遗传算法的流程 (7) 五、遗传算法实例 (12) 六、遗传算法编程 (17) 七、总结 ......... 错误!未定义书签。附录一：运行程序.. (19)

遗传算法基本理论与实例 一、遗产算法的由来 遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。20世纪40年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型，以及模拟进化过程的算法进行了长期的开拓性的探索和研究。John H.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向。 遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。，直至消亡。达尔文把这一过程和现象叫做“自然选择，适者生存”。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的

遗传算法 (2)

用遗传算法优化BP神经网络的Matlab编程实例 由于BP网络的权值优化是一个无约束优化问题，而且权值要采用实数编码，所以直接利用Matlab遗传算法工具箱。以下贴出的代码是为一个19输入变量，1个输出变量情况下的非线性回归而设计的，如果要应用于其它情况，只需改动编解码函数即可。 程序一：GA训练BP权值的主函数 function net=GABPNET(XX,YY) %-------------------------------------------------------------------------- % GABPNET.m % 使用遗传算法对BP网络权值阈值进行优化，再用BP算法训练网络 %-------------------------------------------------------------------------- %数据归一化预处理 nntwarn off XX=premn mx(XX); YY=premn mx(YY); %创建网络 net=newff(minmax(XX),[19,25,1],{'tansig','tansig','purelin'},'trainlm'); %下面使用遗传算法对网络进行优化 P=XX; T=YY; R=size(P,1); S2=size(T,1); S1=25;%隐含层节点数 S=R*S1+S1*S2+S1+S2;%遗传算法编码长度 aa=ones(S,1)*[-1,1]; popu=50;%种群规模 initPpp=initializega(popu,aa,'gabpEval');%初始化种群 gen=100;%遗传代数 %下面调用gaot工具箱，其中目标函数定义为gabpEval [x,endPop,bPop,trace]=ga(aa,'gabpEval',[],initPpp,[1e-6 1 1],'maxGenTerm',gen,... 'normGeomSelect',[0.09],['arithXover'],[2],'nonUnifMutation',[2 gen 3]); %绘收敛曲线图 figure(1) plot(trace(:,1),1./trace(:,3),'r-'); hold on plot(trace(:,1),1./trace(:,2),'b-');

遗传算法

湖南理工学院 人工智能课程论文 题目：遗传算法及其应用 课程名称：人工智能及其应用 院系：计算机学院 专业班级：计科13 - 2 BJ 姓名：李中文 学号: 14132404129 课程论文成绩： 指导教师：廖军 2015 年 6 月30 日

遗传算法及其应用 摘要：遗传算法(genetic algorithms,GA)是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，非常适用于处理传统搜索方法难以解决的复杂和非线性问题。遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。遗传算法具有通用、并行、稳健、简单与全局优化能力强等突出优点，适用于解决复杂、困难的全局优化问题。遗产算法以其广泛的适应性渗透到研究与工程的各个领域，例如：组合优化、机器学习、自适应控制、规划设计和人工生命等，是21世纪有关智能计算中的重要技术之一。 文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理。第三部分着重介绍具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了一个具体问题，如何用遗传算法来解决，以及实现时的一些基本问题。 文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。 关键词：遗传算法，遗传，群体

Genetic algorithm and its application Abstract: genetic algorithm genetic algorithms (GA) is a kind of reference biology natural selection and genetic mechanism of random search algorithm, is very suitable for the complex and non-linear problems that are difficult for traditional search methods. Genetic algorithm is a new subject based on Darwin's theory of evolution, which is developed on the computer simulation of life evolution. It is based on the survival of the fittest, the survival of the fittest natural evolution rule to search algorithm and solve problems. Genetic algorithm has the advantages of general, parallel, robust, simple and global optimization, which is suitable for solving complex and difficult global optimization problems. Inheritance algorithm with its extensive adaptability penetrated into various fields of research and engineering, for example: combinatorial optimization, machine learning, adaptive control, planning and design and artificial life, is one of the most important technologies in the 21st century the intelligent calculation. The first part of the article introduces the basic concepts of genetic algorithm. The second part introduces the principle of genetic algorithm and three kinds of operations: selection, exchange, variation. The third part focuses on the specific implementation of the three operations, as well as a simple example, the main embodiment of the genetic algorithm to achieve the process. In the fourth part, the two parts are introduced, which are all the problems of NP-, how to use genetic algorithms to solve the problems, and some basic problems in the implementation of the problem. In the introduction of the principle of genetic algorithm and various operations, it also analyzes the basic problems that arise in some applications. Key words: genetic algorithm, genetic variation, population