遗传算法_遗传算法matlab - CSDN
遗传算法 订阅
遗传算法(Genetic Algorithm,GA)最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。 [1] 展开全文
遗传算法(Genetic Algorithm,GA)最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。 [1]
信息
基本概念
是一类借鉴生物界的进化规律设计的算法 [1]
特    点
模拟自然进化搜索最优解 [1]
基本操作算子
选择、杂交、变异 [1]
中文名
遗传算法
应    用
组合优化、人工生命等 [1]
外文名
Genetic Algorithm [1]
遗传算法简介
遗传算法的起源可追溯到20世纪60年代初期。1967年,美国密歇根大学J. Holland教授的学生 Bagley在他的博士论文中首次提出了遗传算法这一术语,并讨论了遗传算法在博弈中的应用,但早期研究缺乏带有指导性的理论和计算工具的开拓。1975年, J. Holland等提出了对遗传算法理论研究极为重要的模式理论,出版了专著《自然系统和人工系统的适配》,在书中系统阐述了遗传算法的基本理论和方法,推动了遗传算法的发展。20世纪80年代后,遗传算法进入兴盛发展时期,被广泛应用于自动控制、生产计划、图像处理、机器人等研究领域。 [1] 
收起全文
  • matlab遗传算法案例6讲

    千人学习 2019-10-10 10:36:27
     matlab遗传算法案例6讲
  • 遗传算法详解

    万次阅读 多人点赞 2019-02-23 10:27:47
    三:遗传算法 照例先给出科学定义: 遗传算法(Genetic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,借鉴了达尔文的进化论和孟德尔...

    转载:https://blog.csdn.net/u010451580/article/details/51178225

    三:遗传算法

    照例先给出科学定义:

    遗传算法(Genetic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法,能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最佳解。

    再给出相关术语:(各位看看就好,后面都会涉及到,再细说)

    基因型(genotype):性状染色体的内部表现;

    表现型(phenotype):染色体决定的性状的外部表现,或者说,根据基因型形成的个体的外部表现;

    进化(evolution):种群逐渐适应生存环境,品质不断得到改良。生物的进化是以种群的形式进行的。

    适应度(fitness):度量某个物种对于生存环境的适应程度。

    选择(selection):以一定的概率从种群中选择若干个个体。一般,选择过程是一种基于适应度的优胜劣汰的过程。

    复制(reproduction):细胞分裂时,遗传物质DNA通过复制而转移到新产生的细胞中,新细胞就继承了旧细胞的基因。

    交叉(crossover):两个染色体的某一相同位置处DNA被切断,前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交;

    变异(mutation):复制时可能(很小的概率)产生某些复制差错,变异产生新的染色体,表现出新的性状。

    编码(coding):DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。

    解码(decoding):基因型到表现型的映射。

    个体(individual):指染色体带有特征的实体;
    种群(population):个体的集合,该集合内个体数称为种群的大小。

    遗传算法的有趣应用很多,诸如寻路问题,8数码问题,囚犯困境,动作控制,找圆心问题(在一个不规则的多边形中,寻找一个包含在该多边形内的最大圆圈的圆心),TSP问题,生产调度问题,人工生命模拟等。下面我以袋鼠为例子讲讲遗传算法。(因为袋鼠会跳)

    遗传算法中每一条染色体,对应着遗传算法的一个解决方案,一般我们用适应性函数(fitness function)来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。可以这样想象,这个多维曲面里面有数不清的“山峰”,而这些山峰所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的,那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰,而不是陷落在一些小山峰。(另外,值得注意的是遗传算法不一定要找“最高的山峰”,如果问题的适应度评价越小越好的话,那么全局最优解就是函数的最小值,对应的,遗传算法所要找的就是“最深的谷底”)

    这里写图片描述

    问题的提出与解决方案:

    让我们先来考虑考虑下面这个问题的解决办法。

    已知一元函数:f(x) = xsin(10pi*x)+2
    这里写图片描述

    现在要求在既定的区间内找出函数的最大值
    “袋鼠跳”问题

    既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠,我们希望它们不断的向着更高处跳去,直到跳到最高的山峰(尽管袋鼠本身不见得愿意那么做)。所以求最大值的过程就转化成一个“袋鼠跳”的过程。

    作为对比下面简单介绍“袋鼠跳”的几种方式。

    1. 爬山法(最速上升爬山法):

    从搜索空间中随机产生邻近的点,从中选择对应解最优的个体,替换原来的个体,不断重复上述过程。因为爬山法只对“邻近”的点作比较,所以目光比较“短浅”,常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题,通过一个简单的迭代找出全局最优解的机会非常渺茫。(在爬山法中,袋鼠最有希望到达最靠近它出发点的山顶,但不能保证该山顶是珠穆朗玛峰,或者是一个非常高的山峰。因为一路上它只顾上坡,没有下坡。)

    2… 模拟退火:

    这个方法来自金属热加工过程的启发。在金属热加工过程中,当金属的温度超过它的熔点(Melting Point)时,原子就会激烈地随机运动。与所有的其它的物理系统相类似,原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变迁过程中,开始时,温度非常高, 使得原子具有很高的能量。随着温度不断降低,金属逐渐冷却,金属中的原子的能量就越来越小,最后达到所有可能的最低点。利用模拟退火的时候,让算法从较大的跳跃开始,使到它有足够的“能量”逃离可能“路过”的局部最优解而不至于限制在其中,当它停在全局最优解附近的时候,逐渐的减小跳跃量,以便使其“落脚 ”到全局最优解上。(在模拟退火中,袋鼠喝醉了,而且随机地大跳跃了很长时间。运气好的话,它从一个山峰跳过山谷,到了另外一个更高的山峰上。但最后,它渐渐清醒了并朝着它所在的峰顶跳去。)

    3. 遗传算法:

    模拟物竞天择的生物进化过程,通过维护一个潜在解的群体执行了多方向的搜索,并支持这些方向上的信息构成和交换。是以面为单位的搜索,比以点为单位的搜索,更能发现全局最优解。(在遗传算法中,有很多袋鼠,它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年,就在一些海拔高度较低的地方射杀一些袋鼠,并希望存活下来的袋鼠是多产的,在它们所处的地方生儿育女。)(或者换个说法。从前,有一大群袋鼠,它们被莫名其妙的零散地遗弃于喜马拉雅山脉。于是只好在那里艰苦的生活。海拔低的地方弥漫着一种无色无味的毒气,海拔越高毒气越稀薄。可是可怜的袋鼠们对此全然不觉,还是习惯于活蹦乱跳。于是,不断有袋鼠死于海拔较低的地方,而越是在海拔高的袋鼠越是能活得更久,也越有机会生儿育女。就这样经过许多年,这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上,可是在所有的袋鼠中,只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。)

    遗传算法的实现过程

    遗传算法的实现过程实际上就像自然界的进化过程那样。首先寻找一种对问题潜在解进行“数字化”编码的方案。(建立表现型和基因型的映射关系)然后用随机数初始化一个种群(那么第一批袋鼠就被随意地分散在山脉上),种群里面的个体就是这些数字化的编码。接下来,通过适当的解码过程之后(得到袋鼠的位置坐标),用适应性函数对每一个基因个体作一次适应度评估(袋鼠爬得越高,越是受我们的喜爱,所以适应度相应越高)。用选择函数按照某种规定择优选择(我们要每隔一段时间,在山上射杀一些所在海拔较低的袋鼠,以保证袋鼠总体数目持平。)。让个体基因变异(让袋鼠随机地跳一跳)。然后产生子代(希望存活下来的袋鼠是多产的,并在那里生儿育女)。遗传算法并不保证你能获得问题的最优解,但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。(你不必去指导袋鼠向那边跳,跳多远。)而只要简单的“否定”一些表现不好的个体就行了。(把那些总是爱走下坡路的袋鼠射杀,这就是遗传算法的精粹!)

    所以我们总结出遗传算法的一般步骤:
    这里写图片描述

    开始循环直至找到满意的解。

    1.评估每条染色体所对应个体的适应度。

    2.遵照适应度越高,选择概率越大的原则,从种群中选择两个个体作为父方和母方。

    3.抽取父母双方的染色体,进行交叉,产生子代。

    4.对子代的染色体进行变异。

    5.重复2,3,4步骤,直到新种群的产生。

    结束循环。

    接下来,我们将详细地剖析遗传算法过程的每一个细节。

    编制袋鼠的染色体----基因的编码方式

    受到人类染色体结构的启发,我们可以设想一下,假设目前只有“0”,“1”两种碱基,我们也用一条链条把他们有序的串连在一起,因为每一个单位都能表现出 1 bit的信息量,所以一条足够长的染色体就能为我们勾勒出一个个体的所有特征。这就是二进制编码法,染色体大致如下:

    010010011011011110111110

    上面的编码方式虽然简单直观,但明显地,当个体特征比较复杂的时候,需要大量的编码才能精确地描述,相应的解码过程(类似于生物学中的DNA翻译过程,就是把基因型映射到表现型的过程。)将过分繁复,为改善遗传算法的计算复杂性、提高运算效率,提出了浮点数编码。染色体大致如下:

    1.2 –3.3 – 2.0 –5.4 – 2.7 – 4.3

    (注:还有一种编码方式叫符号编码)

    那么我们如何利用这两种编码方式来为袋鼠的染色体编码呢?因为编码的目的是建立表现型到基因型的映射关系,而表现型一般就被理解为个体的特征。比如人的基因型是46条染色体所描述的却能解码成一个眼,耳,口,鼻等特征各不相同的活生生的人。所以我们要想为“袋鼠”的染色体编码,我们必须先来考虑“袋鼠”的“个体特征”是什么。也许有的人会说,袋鼠的特征很多,比如性别,身长,体重,也许它喜欢吃什么也能算作其中一个特征。但具体在解决这个问题的情况下,我们应该进一步思考:无论这只袋鼠是长短,肥瘦,黑白只要它在低海拔就会被射杀,同时也没有规定身长的袋鼠能跳得远一些,身短的袋鼠跳得近一些。当然它爱吃什么就更不相关了。我们由始至终都只关心一件事情:袋鼠在哪里。因为只要我们知道袋鼠在那里,我们就能做两件必须去做的事情:

    (1)通过查阅喜玛拉雅山脉的地图来得知袋鼠所在的海拔高度(通过自变量求适应函数的值。)以判断我们有没必要把它射杀。

    (2)知道袋鼠跳一跳(交叉和变异)后去到哪个新位置。

    如果我们一时无法准确的判断哪些“个体特征”是必要的,哪些是非必要的,我们常常可以用到这样一种思维方式:比如你认为袋鼠的爱吃什么东西非常必要,那么你就想一想,有两只袋鼠,它们其它的个体特征完全同等的情况下,一只长得黑,另外一只长得不是那么黑。你会马上发现,这不会对它们的命运有丝毫的影响,它们应该有同等的概率被射杀!只因它们处于同一个地方。(值得一提的是,如果你的基因编码设计中包含了袋鼠黑不黑的信息,这其实不会影响到袋鼠的进化的过程,而那只攀到珠穆朗玛峰的袋鼠黑与白什么的也完全是随机的,但是它所在的位置却是非常确定的。)

    以上是对遗传算法编码过程中经常经历的思维过程,必须把具体问题抽象成数学模型,突出主要矛盾,舍弃次要矛盾。只有这样才能简洁而有效的解决问题。

    既然确定了袋鼠的位置作为个体特征,具体来说位置就是横坐标。那么接下来,我们就要建立表现型到基因型的映射关系。就是说如何用编码来表现出袋鼠所在的横坐标。由于横坐标是一个实数,所以说透了我们就是要对这个实数编码。回顾我们上面所介绍的两种编码方式,最先想到的应该就是,对于二进制编码方式来说,编码会比较复杂,而对于浮点数编码方式来说,则会比较简洁。恩,正如你所想的,用浮点数编码,仅仅需要一个浮点数而已。而下面则介绍如何建立二进制编码到一个实数的映射。

    明显地,一定长度的二进制编码序列,只能表示一定精度的浮点数。譬如我们要求解精确到六位小数,由于区间长度为2 – (-1) = 3 ,为了保证精度要求,至少把区间[-1,2]分为3 × 106等份。又因为 221<3×〖10〗6<2^22

    所以编码的二进制串至少需要22位。

    把一个二进制串(b0,b1,…bn)转化位区间里面对应的实数值通过下面两个步骤。
    (1)将一个二进制串代表的二进制数转化为10进制数:
    这里写图片描述
    2)对应区间内的实数:
    这里写图片描述

    这里写图片描述

    好了,目前为止我们把袋鼠的染色体给研究透了,让我们继续跟进袋鼠的进化旅程

    物竞天择--适应性评分与及选择函数。

    1.物竞――适应度函数(fitness function)

    自然界生物竞争过程往往包含两个方面:生物相互间的搏斗与及生物与客观环境的搏斗过程。但在我们这个实例里面,你可以想象到,袋鼠相互之间是非常友好的,它们并不需要互相搏斗以争取生存的权利。它们的生死存亡更多是取决于你的判断。因为你要衡量哪只袋鼠该杀,哪只袋鼠不该杀,所以你必须制定一个衡量的标准。而对于这个问题,这个衡量的标准比较容易制定:袋鼠所在的海拔高度。(因为你单纯地希望袋鼠爬得越高越好。)所以我们直接用袋鼠的海拔高度作为它们的适应性评分。即适应度函数直接返回函数值就行了。

    2.天择――选择函数(selection)

    自然界中,越适应的个体就越有可能繁殖后代。但是也不能说适应度越高的就肯定后代越多,只能是从概率上来说更多。(毕竟有些所处海拔高度较低的袋鼠很幸运,逃过了你的眼睛。)那么我们怎么来建立这种概率关系呢?下面我们介绍一种常用的选择方法――轮盘赌(Roulette Wheel Selection)选择法。

    比如我们有5条染色体,他们所对应的适应度评分分别为:5,7,10,13,15
    所以累计总适应度为:
    这里写图片描述
    所以各个个体被选中的概率分别为:
    这里写图片描述

    你可以想象一下,我们转动轮盘,轮盘停下来的时候,指针会随机地指向某一个个体所代表的区域,那么非常幸运地,这个个体被选中了。(很明显,适应度评分越高的个体被选中的概率越大。)

    遗传变异――基因重组(交叉)与基因突变。

    应该说这两个步骤就是使得子代不同于父代的根本原因(注意,我没有说是子代优于父代,只有经过自然的选择后,才会出现子代优于父代的倾向。)。对于这两种遗传操作,二进制编码和浮点型编码在处理上有很大的差异,其中二进制编码的遗传操作过程,比较类似于自然界里面的过程,下面将分开讲述。

    1.基因重组/交叉(recombination/crossover)

    (1)二进制编码

    二进制编码的基因交换过程非常类似高中生物中所讲的同源染色体的联会过程――随机把其中几个位于同一位置的编码进行交换,产生新的个体。
    这里写图片描述

    (2)浮点数编码

    如果一条基因中含有多个浮点数编码,那么也可以用跟上面类似的方法进行基因交叉,不同的是进行交叉的基本单位不是二进制码,而是浮点数。而如果对于单个浮点数的基因交叉,就有其它不同的重组方式了,比如中间重组:随机产生就能得到介于父代基因编码值和母代基因编码值之间的值作为子代基因编码的值。比如5.5和6交叉,产生5.7,5.6。

    考虑到“袋鼠跳”问题的具体情况――袋鼠的个体特征仅仅表现为它所处的位置。可以想象,同一个位置的袋鼠的基因是完全相同的,而两条相同的基因进行交叉后,相当于什么都没有做,所以我们不打算在这个例子里面使用交叉这一个遗传操作步骤。(当然硬要这个操作步骤也不是不行的,你可以把两只异地的袋鼠捉到一起,让它们交配,然后产生子代,再把它们送到它们应该到的地方。)

    2.基因突变(Mutation)

    (1)二进制编码

    基因突变过程:基因突变是染色体的某一个位点上基因的改变。基因突变使一个基因变成它的等位基因,并且通常会引起一定的表现型变化。正如上面所说,二进制编码的遗传操作过程和生物学中的过程非常相类似,基因串上的“ 0”或“ 1”有一定几率变成与之相反的“ 1”或“ 0”。例如下面这串二进制编码:

    101101001011001

    经过基因突变后,可能变成以下这串新的编码:

    001101011011001

    (2)浮点型编码

    浮点型编码的基因突变过程一般是对原来的浮点数增加或者减少一个小随机数。比如原来的浮点数串如下:

    1.2,3.4,5.1, 6.0, 4.5

    变异后,可能得到如下的浮点数串:

    1.3,3.1,4.9, 6.3, 4.4

    当然,这个小随机数也有大小之分,我们一般管它叫“步长”。(想想“袋鼠跳”问题,袋鼠跳的长短就是这个步长。)一般来说步长越大,开始时进化的速度会比较快,但是后来比较难收敛到精确的点上。而小步长却能较精确的收敛到一个点上。所以很多时候为了加快遗传算法的进化速度,而又能保证后期能够比较精确地收敛到最优解上面,会采取动态改变步长的方法。其实这个过程与前面介绍的模拟退火过程比较相类似。

    到此为止,基因编码,基因适应度评估,基因选择,基因变异都一一实现了,剩下来的就是把这些遗传过程的“零件”装配起来了。(写成代码)

    import math
    import random
    import operator
    
    class GA():
        def __init__(self, length, count):
            self.length = length #染色体长度
            self.count = count #种群中染色体数量
            self.population = self.gen_population(length, count) #随机生成初始种群
    
        def evolve(self,retain_rate = 0.2, random_select_rate = 0.5, mutation_rate = 0.01):
            """
            进化,对当前一代种群一次进行选择,交叉并产生新一代种群,然后对新一代种群进行变异
            """
            parents = self.selection(retain_rate, random_select_rate)
            self.crossover(parents)
            self.mutation(mutation_rate)
    
        def gen_chromosome(self, length):
            """
            随机生成长度为length的染色体,每个基因的取值是0或1
            用一个bit表示一个基因
            """
            chromosome = 0
            for i in range(length):
                chromosome |= (1 << i) * random.randint(0,1)
            return chromosome
    
        def gen_population(self,length,count):
            """
            获取初始种群(一个含有count个长度为length的染色体列表)
            """
            return [self.gen_chromosome(length) for i in range(count)]
    
        def fitness(self, chromosome):
            """
        计算适应度,将染色体解码在0-9之间的数字,带入函数计算
        因为是求最大值,所以数值越大,适应度越高
            """
            x = self.decode(chromosome)
            return x + 10*math.sin(5*x) + 7*math.cos(4*x)
    
        def selection(self, retain_rate, random_select_rate):
            """
            选择
            先对适应度从大到小排序,选出存活的染色体
            在进行随机选择,选出适应度虽然小,但是幸存下来的个体
            """
            #对适应度从大到小排序
            graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
            graded = [x[1] for x in sorted(graded, reverse = True)]
            #选出适应性强的染色体
            retain_length = int(len(graded) * retain_rate)
            parents = graded[:retain_length]
            #选出是是影响不强,但是幸存的染色体
            for chromosome in graded[retain_length:]:
                if random.random() < random_select_rate:
                    parents.append(chromosome)
            return  parents
    
        def crossover(self,parents):
            """
            染色体的交叉,反之,生成新一代的种群
            """
            #新出生的孩子,最终会被加入存活下来的父母之中,形成新一代的种群
            children = []
            #需要繁殖的孩子的量
            target_count = len(self.population) - len(parents)
            #开始根据需要的量进行繁殖
            while len(children) < target_count:
                male = random.randint(0, len(parents)-1)
                female = random.randint(0, len(parents)-1)
                if male != female:
                    #随机选取交叉点
                    cross_pos = random.randint(0, self.length)
                    #生成掩码,方便位操作
                    mask = 0
                    for i in range(cross_pos):
                        mask |= (1 << i)
                    male = parents[male]
                    female = parents[female]
                    #孩子将获得父亲在交叉点前的基因和母亲在交叉点后(包括交差点)的基因
                    child = ((male & mask) | (female & ~mask)) & ((1<<self.length) - 1)
                    children.append(child)
                    #经过繁殖后,孩子和父母的数量与原始种群数量相等,可以更新种群
            self.population = parents + children
    
        def mutation(self, rate):
            """
            变异,对种群的所有个体,随机改变某个个体中的某个基因
            """
            for i in range(len(self.population)):
                if random.random() < rate:
                    j = random.randint(0, self.length-1)
                    self.population[i] ^= 1 << j
    
        def decode(self,chromosome):
            """
            解码染色体,将二进制转或成属于【0,9】的实数
            """
            return chromosome * 9.0 / (2**self.length-1)
    
        def result(self):
            """
             获得当前代的最优值,这里取的是函数取最大值时候的x的值
            """
            graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
            graded = [x[1] for x in sorted(graded, reverse = True)]
            return ga.decode(graded[0])
    
    if __name__ == '__main__':
            #染色体长度为17,种群数量为300
        ga = GA(10,30)
    
            #200次迭代
        for x in range(90):
            ga.evolve()
        print (ga.result())
    

    总结:

    1.选择的作用:优胜劣汰,适者生存;

    2 交叉的作用:保证种群的稳定性,朝着最优解的方向进化;

    3变异的作用:保证种群的多样性,避免交叉可能产生的局部收敛。

    展开全文
  • 详解遗传算法(含MATLAB代码)

    万次阅读 多人点赞 2019-05-29 11:32:48
    一、遗传算法概述 二、遗传算法的特点和应用 三、遗传算法的基本流程及实现技术 3.1 遗传算法的基本流程 3.2 遗传算法的实现技术 1.编码 2.适应度函数 3.选择算子 4.交叉算子 5.变异算子 6.运行参数 四、...

    目录

    一、遗传算法概述

    二、遗传算法的特点和应用

    三、遗传算法的基本流程及实现技术

    3.1 遗传算法的基本流程

    3.2 遗传算法的实现技术

    1.编码

    2.适应度函数

    3.选择算子

    4.交叉算子

    5.变异算子

    6.运行参数

    四、遗传算法的基本原理

    4.1 模式定理

    4.2 积木块假设

    五、遗传算法编程实例(MATLAB)


    一、遗传算法概述

            遗传算法(Genetic Algorithm,GA)是进化计算的一部分,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法简单、通用,鲁棒性强,适于并行处理。

    二、遗传算法的特点和应用

       遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法,与传统的优化算法相比,具有以下特点:

    1. 以决策变量的编码作为运算对象。

        传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算,但遗传算法是使用决策变量的某种形式的编码作为运算对象。这种对决策变量的编码处理方式,使得我们在优化计算中可借鉴生物学中染色体和基因等概念,可以模仿自然界中生物的遗传和进化激励,也可以很方便地应用遗传操作算子。

    2. 直接以适应度作为搜索信息。

        传统的优化算法不仅需要利用目标函数值,而且搜索过程往往受目标函数的连续性约束,有可能还需要满足“目标函数的导数必须存在”的要求以确定搜索方向。

        遗传算法仅使用由目标函数值变换来的适应度函数值就可确定进一步的搜索范围,无需目标函数的导数值等其他辅助信息。直接利用目标函数值或个体适应度值也可以将搜索范围集中到适应度较高部分的搜索空间中,从而提高搜索效率。

    3. 使用多个点的搜索信息,具有隐含并行性

        传统的优化算法往往是从解空间的一个初始点开始最优解的迭代搜索过程。单个点所提供的搜索信息不多,所以搜索效率不高,还有可能陷入局部最优解而停滞;

        遗传算法从由很多个体组成的初始种群开始最优解的搜索过程,而不是从单个个体开始搜索。对初始群体进行的、选择、交叉、变异等运算,产生出新一代群体,其中包括了许多群体信息。这些信息可以避免搜索一些不必要的点,从而避免陷入局部最优,逐步逼近全局最优解。

    4. 使用概率搜索而非确定性规则。

       传统的优化算法往往使用确定性的搜索方法,一个搜索点到另一个搜索点的转移有确定的转移方向和转移关系,这种确定性可能使得搜索达不到最优店,限制了算法的应用范围。

       遗传算法是一种自适应搜索技术,其选择、交叉、变异等运算都是以一种概率方式进行的,增加了搜索过程的灵活性,而且能以较大概率收敛于最优解,具有较好的全局优化求解能力。但,交叉概率、变异概率等参数也会影响算法的搜索结果和搜索效率,所以如何选择遗传算法的参数在其应用中是一个比较重要的问题

    综上,由于遗传算法的整体搜索策略和优化搜索方式在计算时不依赖于梯度信息或其他辅助知识,只需要求解影响搜索方向的目标函数和相应的适应度函数,所以遗传算法提供了一种求解复杂系统问题的通用框架。它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于各种领域,包括:

    • 函数优化
    • 组合优化生产调度问题
    • 自动控制
    • 机器人学
    • 图像处理(图像恢复、图像边缘特征提取......)
    • 人工生命
    • 遗传编程
    • 机器学习

    三、遗传算法的基本流程及实现技术

       基本遗传算法(Simple Genetic Algorithms,SGA)只使用选择算子、交叉算子和变异算子这三种遗传算子,进化过程简单,是其他遗传算法的基础。

    3.1 遗传算法的基本流程

    1.  通过随机方式产生若干由确定长度(长度与待求解问题的精度有关)编码的初始群体;
    2. 通过适应度函数对每个个体进行评价,选择适应度值高的个体参与遗传操作,适应度低的个体被淘汰;
    3. 经遗传操作(复制、交叉、变异)的个体集合形成新一代种群,直到满足停止准则(进化代数GEN>=?);
    4. 将后代中变现最好的个体作为遗传算法的执行结果。

                                                       

    其中,GEN是当前代数;M是种群规模,i代表种群数量。

    3.2 遗传算法的实现技术

    基本遗传算法(SGA)由编码、适应度函数、遗传算子(选择、交叉、变异)及运行参数组成。

    1.编码

    (1)二进制编码

    二进制编码的字符串长度与问题所求解的精度有关。需要保证所求解空间内的每一个个体都可以被编码。

    优点:编、解码操作简单,遗传、交叉便于实现

    缺点:长度大

    (2)其他编码方法

    格雷码、浮点数编码、符号编码、多参数编码等

    2.适应度函数

    适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。

    3.选择算子

    通过选择算子模拟“优胜劣汰”,适应度高的个体被遗传到下一代的概率较大,适应度低的算子被遗传到下一代的概率较小。

    常用的选择算法:轮盘赌选择法,即令\sum f_i表示群体的适应度函数值的总和,f_i表示群体中第i个染色体的适应度值,则它产生后代的能力刚好为其适应度值所占的份额\frac{f_i}{\sum f_i}

    4.交叉算子

    • 交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因,从而形成两个新的个体;
    • 交叉运算是遗传算法区别于其他进化算法的重要特征,是产生新个体的主要方法。

    在交叉之前需要将群体中的个体进行配对,一般采取随机配对原则。

    常用的交叉方式:

    • 单点交叉
    • 双点交叉(多点交叉,交叉点数越多,个体的结构被破坏的可能性越大,一般不采用多点交叉的方式)
    • 均匀交叉
    • 算术交叉

    5.变异算子

    遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换,从而形成一个新的个体。

    就遗传算法运算过程中产生新个体的能力方面来说,交叉运算是产生新个体的主要方法,它决定了遗传算法的全局搜索能力;而变异运算只是产生新个体的辅助方法,但也是必不可少的一个运算步骤,它决定了遗传算法的局部搜索能力。交叉算子与变异算子的共同配合完成了其对搜索空间的全局搜索和局部搜索,从而使遗传算法能以良好的搜索性能完成最优化问题的寻优过程。

    6.运行参数

    • 编码长度。编码长度取决于问题解的精度,精度越高,编码越长;
    • 种群规模。规模小,收敛快但降低了种群的多样性,N=20-200
    • 交叉概率。较大的交叉概率容易破坏种群中已形成的优良结构,使搜索具有太大随机性;较小的交叉概率发现新个体的速度太慢,一般取值为P_c=0.4-0.99
    • 变异概率。变异概率太小,则变异操作产生新个体的能力和抑制早熟现象的能力会较差;变异概率过高随机性过大,一般建议取值范围为0.005~0.01
    • 终止进化代数。算法运行结束的条件之一,一般取100~1000

    四、遗传算法的基本原理

    4.1 模式定理

    定义1:模式H是由{0,1,*}中的元素组成的一个编码串,其中“*”表示通配符,既能被当作0,也能被当作1。e.g. H=10**1

    定义2:模式的阶,是指模式中所含有0,1的数量,记作O(H)  e.g. O(11*00**)=4

    定义3:模式的矩,即模式的长度,是指模式中从左到右第一个非*位和最后一个非*位之间的距离,记作\delta (H)

              e.g. \delta (01**1)=3;\delta (**0*1)=2;\delta (***1**)=1

    定义4:模式的适应度值,是群体中所包含的全部个体的适应度值的平均值。

    定义5:在选择、交叉、变异遗传算子的作用下,低阶、长度短、超过群体平均适应值的模式的生存数量,将随迭代次数以指数规律增长。

    模式定理不仅说明基因块的样本呈指数增长,也说明用遗传算法寻求最优样本的可能性,但它并未指出遗传算法一定能够寻求到最优解,积木块假设说明了遗传算法的寻找最优解的能力。

    4.2 积木块假设

    具有低阶、定义长度短,且适应度值高于群体平均适应度值的模式称为基因块或积木块。

    积木块假设:个体的基因块通过选择、交叉、变异等遗传算子的作用,能够相互拼接在一起,形成适应度更高的个体编码串。

    积木块假设说明了用遗传算法求解各类问题的基本思想,即通过积木块直接相互拼接在一起能够产生更好的解。

    五、遗传算法编程实例(MATLAB)

    https://github.com/strawberry-magic-pocket/Genetic-Algorithm.git

     

    展开全文
  • 看过最好的遗传算法和程序(没有之一)

    万次阅读 多人点赞 2018-09-05 13:20:54
    看过最好的遗传算法和程序(没有之一) 摘自http://www.cnblogs.com/hxsyl/p/5240905.html 1、遗传算法介绍 遗传算法,模拟达尔文进化论的自然选择和遗产学机理的生物进化构成的计算模型,一种不断选择优良个体的...

    看过最好的遗传算法和程序(没有之一)

    摘自http://www.cnblogs.com/hxsyl/p/5240905.html

    1、遗传算法介绍

    遗传算法,模拟达尔文进化论的自然选择和遗产学机理的生物进化构成的计算模型,一种不断选择优良个体的算法。谈到遗传,想想自然界动物遗传是怎么来的,自然主要过程包括染色体的选择,交叉,变异(不明白这个的可以去看看生物学),这些操作后,保证了以后的个基本上是最优的,那么以后再继续这样下去,就可以一直最优了。

    2、解决的问题

    先说说自己要解决的问题吧,遗传算法很有名,自然能解决的问题很多了,在原理上不变的情况下,只要改变模型的应用环境和形式,基本上都可以。但是遗传算法主要还是解决优化类问题,尤其是那种不能直接解出来的很复杂的问题,而实际情况通常也是这样的。

    本部分主要为了了解遗传算法的应用,选择一个复杂的二维函数来进行遗传算法优化,函数显示为y=10*sin(5*x)+7*abs(x-5)+10,这个函数图像为:

    这里写图片描述

    怎么样,还是有一点复杂的吧,当然你还可以任意假设和编写,只要符合就可以。那么现在问你要你一下求出最大值你能求出来吗?(这个貌似可以,很容易写出来—-如果再复杂一点估计就不行了)这类问题如果用遗传算法或者其他优化方法九很简单了,为什么呢?说白了,其实就是计算机太笨了同时计算速度又超快,举个例子吧,我把x等分成100万份,再一下子都带值进去算,求出对应的100万个y的值,再比较他们的大小找到最大值不就可以了吗,很笨吧,人算是不可能的,但是计算机可以。而遗传算法也是很笨的一个个搜索,只不过加了一点什么了,就是人为的给它算的方向和策略,让它有目的的算,这也就是算法了。

    3、如何开始?

    不明白遗传算法的会问怎么开始呢?恩,其实每个算法都有自己的开始方式,遗传算法也是,首先是选择个体了。我们知道一个种群中可能只有一个个体吗?不可能吧,肯定很多人才对,这样相互结合的机会才多,产生的后代才会多种多样,才会有更好的优良基因,有利于种群的发展。那么算法也是如此,当然个体多少是个问题,一般来说20-100之间我觉得差不多了。那么个体究竟是什么呢?在我们这个问题中自然就是x值了。其他情况下,个体就是所求问题的变量,这里我们假设个体数选100个,也就是开始选100个不同的x值,不明白的话就假设是100个猴子吧。好了,现在有了100个猴子组成的一个种群,那么这个种群应该怎么发展才能越来越好?说到这,我们想想,如何定义这个越来越好呢?这个应该有一个评价指标吧。在我们的这个问题中,好像是对应的y值越大越好是吧。我们甚至可以给他们排个名来决定哪些好哪些不好。我们把这个叫做对于个体的适应度,这应该算是算法的后半部分才对。

    4、编码

    首先明白什么是编码?为什么要编码?如何编码?

    好,什么是编码?其实编码就是把自变量(x)换一下形式而已,在这个形式下,更容易操作其他过程(比如交叉,变异什么的)而已。举个例子吧,加入我们取x=1, 2, 3,我们可以把x 编码成x=a, b, c,我就说123对应就是abc,为什么要这样做呢?比如问题里面你能够获取的都是abc的组合之类的,那么这样编码以后,你就可以再返回去成123来操作了。一般的编码都是些什么呢?二进制编码,自然数编码,矩阵编码。。等等,很多,不详细写了。而用的最多的可以说是二进制编码,感觉这和人体DNA,基因的排列很相似。想想DNA怎么排的?不就是在两条长链上一对一排的吗?那么什么是二进制编码?很简单,就是1,0,1,0对应的来回组合排列而已。比如:1100100010, 0011001001等等,这些都是位数长度为10的二进制编码。再想想1在计算机的二进制形式是什么?如果八位来表示的话,是不是就是0000 0001;8是不是就是0000 1000;以此类推,那么我们这里也是这样,把对应的x值换算成这种编码形式,我们这里可以看到x的范围是0-5吧,如何按照计算机这样的方式是不是到0000 0101这里就完事了?想想这样多短,前面五位都没有用上多浪费呀,那么要想都用上怎么办呢?也很简单,我们把0000 0001不认为是1不就可以了吗?因为1111 1111是255,那么如果说每一份为1/255的话,那么0000 0001不就是1/255了吗?这个时候1怎样表示了?不就是1111 1111吗?好了我们把范围扩大一些吧,每一份不是1/255,而是1/255*5,那么这个时候最大值是多少?是不是5,恩,这样x编码的范围不就在0-5之间了吗?这里就又有问题了,想想这样做的话,x的最小精度是多少?就是1/255*5.虽然很小,但是在0-1/255*5之间的数你能不能取到?无论如何都取不到吧。那么就又来一个问题,怎样去扩大这个精度呢?如果要保持0-5不变的话,只能增加位数了,把9位编码编程10位,20位,100位,哇,够大了吧,变成100个0,1组合,很恐怖吧,事实上,究竟是多少要视情况而定,一般20位左右感觉就可以了,虽然说越大越好,但是太大了消耗内存,速度慢了,不值。本题中,我们设置它为一个变量,先暂时取为10来实验,好了,如果还不明白为什么要编码看下面的吧。知道了交叉与变异,你就知道了。

    5、关于交叉与变异

    先说变异,什么是变异?简单,基因发生突变就叫变异,有了编码的概念,那就在编码基础上来说变异。首先就讲最简单的变异,但个点的变异。现在以10位长的编码来说,比如把x=3编码一下,随便假设为11000 10010吧,好了,在变异操作时,假设第5位变异了(说一下变异就是一位或者多位1或0变成0或1,也只能0,1之间变,没办法啊),那么这个时候变成什么了?是不是11001 10010再反编码回去成x是多少呢?那肯定不是3了,变了呀,是多少是肯定可以反算回去的,这里懒得算了,就假设为3.213吧,发没发现,这样一来,x是不是变了?既然变了就好啊,带到原函数(适应度函数)里面比较这两个x值对应的哪个y值大一写,如果后面变异后的大一些是不是就是说产生了好的变异啊,就可以在下一次个体选择的时候选择它了。那么想想很多x来一起变异会怎么样呢?肯定会生成很多很多的解吧,反复这么做会怎么样呢?只要每次都保留最优解的话,我来个循环100万次,也总能找到解吧,当然这么多次得花多久,也不太合适,这还只是一个点位在进行变异,若果每次我让多个点位变异呢?哇,又不可思议了,变化更大了吧。当然,变异不止如此,更多的去看专业的论文吧。知道了变异是干什么的,剩下的都好说了,好了,这还是变异,想想自然界遗传中除了变异还有什么?交叉吧,那么交叉又是什么?

    学过生物的都知道,动物交配时,部分染色体干什么了?是不是交叉了?就是把相应部分的基因交换了,你的给我,我的给你,很有爱吧。再以编码为例,比如现在随便从100个x值中选取两个吧,鸡舍正好选中了x=3和4,对应的编码假设是11001 10101 和00101 01011,那么怎么交叉呢?我们知道每次交叉的染色体通常是一块一块的,恩,这里在算法设计上也来一块一块的吧。比如说就把位置在2,3,4号的编码给整体交叉了,那么x=3对应的位置是100吧,x=4对应的位置是010吧,好,交换以后x=3对应的位置就变成了010,x=4对应的位置就变成100,加回去就变成什么了?x=3是不是就是10101 10101,x=4是不是就是01001 01011了。而现在,把他们再反编码回去还是x=3和x=4吗?显然又不是了吧(当然也有小概率是一样的吧,很小)。那是什么?不想算,还是假设吧,假设为3.234和4.358吧,好了新的个体是不是又来了?恩,同理,带到适应度函数里面去吧,再取优秀个体,完事。同样,有些专门研究这种算法的开发出来各种各样的交叉方式,什么一个个体的钱3个与后一个个体的后三个交叉,中间几位来交叉等等,总之就是生产新个体。而这样做的目的在哪呢?无非是三个字,随机性,充分保证生产新个体具有随机性,你说你的x=3变异后为3.2,3.2什么的距离3那么近,在一些存在局部最优解的问题上就永远跳不出局部最优解,相反,你的x=1一下子变异成了x=5,哇,好大的变化,一下从这头到了那头,这对于算法的广阔搜索能力来说是非常好的。

    讲完了这部分,现在知道了为什么要编码了吧?如果你不编码,你说你想要你的x=3怎么去变异?怎么去交叉?当然也不是没有方法,比如你生成一个小的随机数加到x=3上,但是你想想这两种方法哪一个更具有随机性、普遍性?显然的。而更多的时候交叉预编译是在一起操作的,先交叉,再变异是普遍遗传算法的操作步骤。

    6、关于选择的问题

    说完了上面的部分,再说说选择吧,选择是什么?就是优胜劣汰。好的留下来,差的走人,在自然界中直接gg了是吧。不停地选择是的种群一直吵着较好的方向行走。

    对应到本问题来说,遗传算法的选择是什么样子?在前面说到,每次交叉或者变异是不是产生了新的个体?如果这些个体都保留下来的话,种群是要爆炸的,第一次循环可能有100个x,第二次循环就200个个体,再来那么10万次,哇哦,多少了,好多。显然不可能吧。而且在算法里面,我们还规定的是每次循环都必须保证都是100个个体。那么必须在200个个体中剔除100个吧。好了,问题来了,如何剔除呢?有人说很简单,排名吧,取前100号x不就可以了吗?排名这个东西真的好吗?我就不信,凭什么差一点的不能选上,搞不好在下一次变异中一下子冲到了第一呢?这个问题在选择上也有一些对应的规则,最通用的就是轮盘赌法,简单来说就是一种概率选择法(当然还有许多其他的方法,感兴趣的自己搜相关的文献吧,我也没用过)。什么是轮盘赌法呢?就是把对应所有y值(适应度函数值)加起来,在用各自的y值去除以这个sum值,这样是不是谁的概率大谁的概率小就很清楚了?然后再随机生成一个0-1的概率值p,谁在p的范围里面是不是就选择谁,比如说x=3时在100个x中y的值最大,那么选择它的概率是不是就最大,比如说是0.1(0.1小吗?不小了好吧,想想其他的会是什么,都比0.1小,那么从概率上讲,选100次的话,是不是就有10次宣导x=3,其他的都不足10次是吧,那么在下一次100个种群个体中就有10个x=3了,再来一回可能就有20个x=3的个体了。再就是30个,最后就只剩下100个x=3的个体了,它自己在哪里交叉变异已经没有意义了,如果到了这个时候就意味着这个算法可以结束了)。再详细点,如下图所示吧:现在要在下面三个大类中选取100个x个体,轮盘赌转100次以后,是不是个艺术落在s3中的个体多一些,选择的原理就是这样,再不明白直接后面的程序吧。

    这里写图片描述

    7、还差点什么呢

    至此,感觉也差不多了吧,选择完后在重复上述步骤交叉,变异等等,那么什么时候是个头了?很简单,办法就是迭代次数,迭代10次看一下结果,20次,看一下结果,30次,40次,100次,当次数达到一定程度以后,优秀的个体越来越多,大都集中在最优解附近,即使变异或者交叉了也是在这个最优解附近,没有影响的。在下一次选择就又变回来了,那么至此就真的结束了。比如说先来结果吧,该问题按我的思路做完后,迭代100次变成什么样子了?看图:

    这里写图片描述

    下面看代码:

    (1)首先看主函数

    function main()
    clear;
    clc;
    %种群大小
    popsize=100;
    %二进制编码长度
    chromlength=10;
    %交叉概率
    pc = 0.6;
    %变异概率
    pm = 0.001;
    %初始种群
    pop = initpop(popsize,chromlength);

    for i = 1:100
    %计算适应度值(函数值)
    objvalue = cal_objvalue(pop);
    fitvalue = objvalue;
    %选择操作
    newpop = selection(pop,fitvalue);
    %交叉操作
    newpop = crossover(newpop,pc);
    %变异操作
    newpop = mutation(newpop,pm);
    %更新种群
    pop = newpop;
    %寻找最优解
    [bestindividual,bestfit] = best(pop,fitvalue);
    x2 = binary2decimal(bestindividual);
    x1 = binary2decimal(newpop);
    y1 = cal_objvalue(newpop);
    if mod(i,10) == 0
    figure;
    fplot(‘10*sin(5*x)+7*abs(x-5)+10’,[0 10]);
    hold on;
    plot(x1,y1,’*’);
    title([‘迭代次数为n=’ num2str(i)]);
    %plot(x1,y1,’*’);
    end
    end
    fprintf(‘The best X is —>>%5.2f\n’,x2);
    fprintf(‘The best Y is —>>%5.2f\n’,bestfit);

    (2)下面看二进制种群生成的方法

    %初始化种群大小
    %输入变量:
    %popsize:种群大小
    %chromlength:染色体长度–>>转化的二进制长度
    %输出变量:
    %pop:种群
    function pop=initpop(popsize,chromlength)
    pop = round(rand(popsize,chromlength));
    %rand(3,4)生成3行4列的0-1之间的随机数
    % rand(3,4)
    %
    % ans =
    %
    % 0.8147 0.9134 0.2785 0.9649
    % 0.9058 0.6324 0.5469 0.1576
    % 0.1270 0.0975 0.9575 0.9706
    %round就是四舍五入
    % round(rand(3,4))=
    % 1 1 0 1
    % 1 1 1 0
    % 0 0 1 1
    %所以返回的种群就是每行是一个个体,列数是染色体长度

    (3)下面看如何把二进制返回对应的十进制

    %二进制转化成十进制函数
    %输入变量:
    %二进制种群
    %输出变量
    %十进制数值
    function pop2 = binary2decimal(pop)
    [px,py]=size(pop);
    for i = 1:py
    pop1(:,i) = 2.^(py-i).*pop(:,i);
    end
    %sum(.,2)对行求和,得到列向量
    temp = sum(pop1,2);
    pop2 = temp*10/1023;

    输入的是100组0,1编码的二进制,输出的是x值,开始取一下种群大小,size(pop),显然这里py是10了,借着对每一位求和,就是pop1(:,i)=2.^(py-i).*pop(:,i);这里省略用了冒号,,什么依稀呢?就是对所有行都有这个操作,冒号意思就是胸1到100了,那么就其中一个个体来说吧,假设为11001 10010,那么先进性这么一个操作就是什么呢?是不是就是对应的为0或1乘以2的对应次幂,如果1就是管用,是0就不管用。那么这个值就是(2^0)*1+(2^1)*1+0+0+(2^4)*1+….这样就算出了一个值,因为是10位编码,所以这个数是结余0-2^9即0-1023.那么最大为多少?1023吧。temp = sum(pop1,2)是对行求和吧,2表示行,1表示列,最后一行是吧它转化为100组0-10之间的数值了。

    (4)下面看计算适应度函数:

    %计算函数目标值
    %输入变量:二进制数值
    %输出变量:目标函数值
    function [objvalue] = cal_objvalue(pop)
    x = binary2decimal(pop);
    %转化二进制数为x变量的变化域范围的数值
    objvalue=10*sin(5*x)+7*abs(x-5)+10;

    (5)如何选择新的个体

    上面所有个体的函数值都计算出来了,存在objvalue中,此时它是不是也是100组y值啊,恩,那么对于现有的随机生成的100组x,怎么来再选择100组新的更好的x呢?这里我们把选择放在了交叉与变异之间了,都可以,如何选择,就要构造概率的那个轮盘了,谁的概率大,是不是选择的个体就会多一些?也就是现在的选择就是100中100个,最后出现的就够就是以前的100个中最优的x有一个的话,选择完后,可能就变成5个这个x了,多余的4个是不是相当于顶替了以前的不好的4个x值,这样才能达到x总数100不变啊。

    %如何选择新的个体
    %输入变量:pop二进制种群,fitvalue:适应度值
    %输出变量:newpop选择以后的二进制种群
    function [newpop] = selection(pop,fitvalue)
    %构造轮盘
    [px,py] = size(pop);
    totalfit = sum(fitvalue);
    p_fitvalue = fitvalue/totalfit;
    p_fitvalue = cumsum(p_fitvalue);%概率求和排序
    ms = sort(rand(px,1));%从小到大排列
    fitin = 1;
    newin = 1;
    while newin<=px
    if(ms(newin))

    展开全文
  • 遗传算法解决的问题 通过模拟自然进化过程搜索最优解的方法。 也即是说,解决的问题是最优化问题,所以在解决实际问题中要看实际问题是否能转换为求解最优化问题的模型。 遗传算法的求解过程将导致种群像...

    遗传算法解决的问题


    通过模拟自然进化过程搜索最优解的方法。
    也即是说,解决的问题是最优化问题,所以在解决实际问题中要看实际问题是否能转换为求解最优化问题的模型。
    遗传算法的求解过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。

    遗传算法的过程


    过程其实很简单:是一个通过循环迭代获取最优解的过程。简易的过程如下图:
    这里写图片描述
    其间完整的过程解释:确定编码方式,对问题的解进行编码;初始化种群(种群中每一个个体均编码完成);评价种群中的个体(采用适应度函数进行评估,位串的解码值,目标函数值,目标函数值向适应值映射,适应值调整);判断是否满足要求(满足结束迭代,获取最优解,不满足继续进行迭代过程);进行遗传操作:选择、交叉、变异;产生新的一代种群;继续进行评价种群的个体……

    1- 编码


    二进制编码

    定义:二进制编码方法是使用二值符号集{0,1},它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。
    举例:0≤x≤1023,精度为1,m表示二进制编码的长度。则有建议性说法:使 2m-1≤1000(跟精度有关)≤2m-1。取m=10。例如:X:0010101111就可以表示一个个体,它所对应的问题空间的值是x=175。
    优点:编码、解码操作简单易行;交叉、变异等遗传操作便于实现;合最小字符集编码原则;利用模式定理对算法进行理论分析。
    缺点:对于一些连续函数的优化问题,由于其随机性使得其局部搜索能力较差,如对于一些高精度的问题,当解迫近于最优解后,由于其变异后表现型变化很大,不连续,所以会远离最优解,达不到稳定。

    格雷码

    定义:格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的,其余码位完全相同。它是二进制编码方法的一种变形。
      十进制数0—15之间的二进制码和相应的格雷码分别编码如下。
      二进制编码为:0000,0001,0010,001 1,0100。0101,0110,0111,
      1000,1001,1010,1011,1100,1101,1110,1111;
      格雷码编码为:0000,0001,0011,0010,0110,0111,0101,0100,
      1100,1101,1111,1110,1010,1011,1001,1000。
    举例:对于区间[0。1023]中两个邻近的整数X1=175和X2=176,若用长度为10位的二进制编码,可表示为X11:0010101111和X12 0010110000,而使用同样长度的格雷码,它们可分别表示为X21:0010101111和X22:0010101000。
    优点:便于提高遗传算法的局部搜索能力;交叉、变异等遗传操作便于实现;符合最小字符集编码原则;便于利用模式定理对算法进行理论分析。

    浮点数(实数)编码

    定义:浮点数编码是指个体的每个基因值用某一范围内的一个浮点数来表示,而个体的编码长度等于其决策变量的个数。因为这种编码方法使用的决策变量的真实值,也称之为真值编码方法。
    对于一些多维、高精度要求的连续函数优化问题,使用二进制编码来表示个体时将会有一些不利之处。
    二进制编码存在着连续函数离散化时的映射误差。个体长度较知时,可能达不到精度要求,而个体编码长度较长时,虽然能提高精度,但却使遗传算法的搜索空间急剧扩大。
    浮点法,是指个体的每个基因值用某一范围内的一个浮点数来表示。在浮点数编码方法中,必须保证基因值在给定的区间限制范围内,遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。
    优点:适用于在遗传算法中表示范围较大的数;适用于精度要求较高的遗传算法;便于较大空间的遗传搜索;改善了遗传算法的计算复杂性,提高了运算交率;便于遗传算法与经典优化方法的混合使用;便于设计针对问题的专门知识的知识型遗传算子;便于处理复杂的决策变量约束条件。

    符号编码法

    定义:符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如{A,B,C…}。
    优点:符合有意义积术块编码原则;便于在遗传算法中利用所求解问题的专门知识;便于遗传算法与相关近似算法之间的混合使用。
    缺点:但对于使用符号编码方法的遗传算法,一般需要认真设计交叉、变异等遗传运算的操作方法,以满足问题的各种约束村求,这样才能提高算法的搜索性能。

    2- 适应度函数


    定义:适应度函数(Fitness Function)的选取直接影响到遗传算法的收敛速度以及能否找到最优解,因为遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群每个个体的适应度来进行搜索.因为适应度函数的复杂度是遗传算法复杂度的主要组成部分,所以适应度函数的设计应尽可能简单,使计算的时间复杂度最小。

    有关适应度函数和适应度的分配,这里摘选了一篇比较好的内容来学习。

    1
    2
    3
    4
    5
    6

    3- 选择算子


    作用:对群体进行优胜劣汰造作,使适应度较高的个体被遗传到下一代群体中的概率较大,使适应度较小的个体被遗传到下一代群体中的概率较小。

    常见的选择方法:

    1.轮盘赌选择(Roulette Wheel Selection):是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。

    2.随机竞争选择(Stochastic Tournament):每次按轮盘赌选择一对个体,然后让这两个个体进行竞争,适应度高的被选中,如此反复,直到选满为止。

    3.最佳保留选择:首先按轮盘赌选择方法执行遗传算法的选择操作,然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。

    4.无回放随机选择(也叫期望值选择Excepted Value Selection):根据每个个体在下一代群体中的生存期望来进行随机选择运算。方法如下:
    (1) 计算群体中每个个体在下一代群体中的生存期望数目N。
    (2) 若某一个体被选中参与交叉运算,则它在下一代中的生存期望数目减去0.5,若某一个体未 被选中参与交叉运算,则它在下一代中的生存期望数目减去1.0。
    (3) 随着选择过程的进行,若某一个体的生存期望数目小于0时,则该个体就不再有机会被选中。
    5.确定式选择:按照一种确定的方式来进行选择操作。具体操作过程如下:
    (1) 计算群体中各个个体在下一代群体中的期望生存数目N。
    (2) 用N的整数部分确定各个对应个体在下一代群体中的生存数目。
    (3) 用N的小数部分对个体进行降序排列,顺序取前M个个体加入到下代群体中。至此可完全确定出下一代群体中M个个体。
    6.无回放余数随机选择:可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中,因而选择误差比较小。

    7.均匀排序:对群体中的所有个体按期适应度大小进行排序,基于这个排序来分配各个个体被选中的概率。

    8.最佳保存策略:当前群体中适应度最高的个体不参与交叉运算和变异运算,而是用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。

    9.随机联赛选择:每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。

    10.排挤选择:新生成的子代将代替或排挤相似的旧父代个体,提高群体的多样性。

    其中轮盘赌选择法 (roulette wheel selection)是最简单也是最常用的选择方法。在该方法中,各个个体的选择概率和其适应度值成比例。设群体大小为n,其中个体i的适应度为,则i 被选择的概率,为遗传算法这里写图片描述缺点:随机操作原因,误差比较大,有时连适应度较高的个体都选不上。

    4- 交叉算子


    作用:交叉算子根据交叉率将种群中的两个个体随机地交换某些基因,能够产生新的基因组合,期望将有益基因组合在一起。

    根据编码表示方法的不同,可以有以下的交叉方法:

    实值重组(real valued recombination)

    1)离散重组(discrete recombination)
    2)中间重组(intermediate recombination)
    3)线性重组(linear recombination)
    4)扩展线性重组(extended linear recombination)。

    二进制交叉(binary valued crossover)

    1)单点交叉(single-point crossover)
    2)多点交叉(multiple-point crossover)
    3)均匀交叉(uniform crossover)
    4)洗牌交叉(shuffle crossover)
    5)缩小代理交叉(crossover with reduced surrogate)

    最常用的交叉算子为单点交叉(one-point crossover)。具体操作是:在个体串中随机设定一个交叉点,实行交叉时,该点前或后的两个个体的部分结构进行互换,并生成两个新个体。下面给出了单点交叉的一个例子:
    个体A:1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新个体
    个体B:0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新个体

    5- 变异算子


    定义:是指将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换,从而形成新的个体。

    例如下面这串二进制编码:

    101101001011001

    变异后:

    001101011011001

    常用的变异方法(适用于二进制编码和浮点数编码的个体):

    基本位变异(Simple Mutation):对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。

    均匀变异(Uniform Mutation):分别用符合某一范围内均匀分布的随机数,以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。(特别适用于在算法的初级运行阶段)

    边界变异(Boundary Mutation):随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。

    非均匀变异:对原有的基因值做一随机扰动,以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后,相当于整个解向量在解空间中作了一次轻微的变动。

    高斯近似变异:进行变异操作时用符号均值为P的平均值,方差为P**2的正态分布的一个随机数来替换原有的基因值。

    6- 终止规则


    当最优个体的适应度达到给定的阈值,或者最优个体的适应度和群体适应度不再上升时,或者迭代次数达到预设的代数时,算法终止。预设的代数一般设置为100-500代。

    总结


    文章是遗传算法的整个流程图和6个关键点的个人理解和结合其他资料的总结。不足之处请指出,博主正在学习GA的内容,目的是完成一个具有约束条件的优化问题,如果能顺利完成,后续会在博客中贴出实际问题、实际问题的转换模型以及实现的方案。

    展开全文
  • 遗传算法

    万次阅读 多人点赞 2019-03-29 22:45:03
    对于求解这类优化问题,遗传算法是一种不错的选择。接下来,我将分享给大家我对于遗传算法的一些拙见,如有不足之处,请大家多多指正。 遗传算法,顾名思义就是根据生物界的遗传进化行为而得名的,其核心思想就是...
  • 遗传算法(GA)

    万次阅读 2018-04-14 15:22:40
    遗传算法(Genetic Algorithm) 一个讲得很清楚的博客:非常好理解的遗传算法的例子 简单理解: 用计算机模拟人类进化,适应环境(符合条件)的继续繁衍后代,不适应环境(不符合条件)的淘汰,从而逐步找到最...
  • 10分钟搞懂遗传算法

    万次阅读 多人点赞 2018-01-24 20:57:27
    大自然有种神奇的力量,它能够将优良的基因保留下来,从而...本文先跟大家介绍遗传算法的基本思想,然后用遗传算法来解决一个实际问题,最后给出遗传算法的代码实现和解析。废话不多说,现在就开始吧~ 遗传算法
  • 想要快速的了解一个算法,最好的方式便是拿个例子手动进行实现算一遍。这里借鉴了网络上的一个例子,求解如下的一个函数: f(x)=x∗sin(10∗π∗x)+2x∈[−1,2]f(x) = x*sin(10*\pi*x)+2 \\ x \in[-1, 2] 其函数...
  • 本文是去年课题组周报中的一个专题讲解,详细讲了GA,由于是周报,所以十分详细。文章综合参考了一些互联网资料。发博客以备忘!
  • 非常好的理解遗传算法的例子

    万次阅读 多人点赞 2009-10-16 15:11:00
    遗传算法的手工模拟计算示例为更好地理解遗传算法的运算过程,下面用手工计算来简单地模拟遗传算法的各 个主要执行步骤。 例:求下述二元函数的最大值: (1) 个体编码 遗传算法的运算对象是表示个体的符号串,...
  • 一个非常好的理解遗传算法的例子 强烈推荐入门

    万次阅读 多人点赞 2017-03-29 11:08:43
    遗传算法的手工模拟计算示例 为更好地理解遗传算法的运算过程,下面用手工计算来简单地模拟遗传算法的各  个主要执行步骤。    例:求下述二元函数的最大值:  (1) 个体编码  遗传算法的运算对象是表示...
  • 遗传算法原理及算法实例

    万次阅读 多人点赞 2017-11-26 09:42:13
    遗传算法原理解析 遗传算法(GA)是一种元启发式自然选择的过程,属于进化算法(EA)大类。遗传算法通常是利用生物启发算子,如变异、交叉和选择来生成高质量的优化和搜索问题的解决方案。 借鉴生物进化理论,遗传...
  • 遗传算法的matlab实现

    万次阅读 多人点赞 2017-06-23 23:04:56
    遗传算法是一种全局最优化算法,是运用了进化论优胜劣汰原理的随机化搜索方法。 前些日子,在进行毕业设计的相关研究中,我接触到了遗传算法,用其对一个五元非线性函数进行最优化搜索。仿真平台使用的是matlab,...
  • 遗传算法入门到掌握(一)

    万次阅读 多人点赞 2016-03-01 16:24:38
    博主前言:此文章来自一份网络资料,原作者不明,是我看过的最好的一份遗传算法教程,如果你能耐心看完他,相信你一定能基本掌握遗传算法。  遗传算法的有趣应用很多,诸如寻路问题,8数码问题,囚犯困境,动作...
  • 基于遗传算法的BP神经网络优化算法

    万次阅读 多人点赞 2020-04-22 14:37:38
    遗传算法优化BP神经网络分为BP神经网络结构确定、遗传算法优化和 BP神经网络预测3个部分。其中,BP神经网络结构确定部分根据拟合函数输入输出参数个数确定 BP神经网络结构,这样就可以确定遗传算法的优化参数个数,...
  • 遗传算法 求解旅行商 TSP 问题,matlab代码

    万次阅读 多人点赞 2019-08-17 01:32:55
    其中,遗传算法可以用来求解该问题。遗传算法是一种进化算法,由于其启发式算法的属性,并不能保证得到最优解。求解效果与初始种群选取,编码方法,选择方法,交叉变异规则有关。 上课时,老师不知从哪里找了一个...
  • 1.遗传算法及其应用(经典的书籍) 2.遗传算法及其应用(经典的书籍) 3.遗传算法及其应用(经典的书籍) 4.演化程序——遗传算法和数据编码的结合 5.遗传算法的数学基础 6.遗传算法及其应用 7.遗传算法——理论、...
  • 遗传算法最通俗的讲解案例

    万次阅读 多人点赞 2016-09-07 09:33:15
    遗传算法 遗传算法求全局最优解或者近似优解。 遗传算法GA可以用到数据挖掘领域,由于缺少一些详细的例子,导致难以理解,以下是一个大牛的遗传算法的详细例子 遗传算法的有趣应用很多,诸如寻路问题,8数码问题,...
  • matlab中遗传算法求最优解

    万次阅读 2018-08-29 17:46:48
    首先什么是遗传算法:一个非常好的理解遗传算法的例子 强烈推荐入门  遗传算法的手工模拟计算示例 为更好地理解遗传算法的运算过程,下面用手工计算来简单地模拟遗传算法的各  个主要执行步骤。    例:求...
1 2 3 4 5 ... 20
收藏数 31,451
精华内容 12,580
关键字:

遗传算法