未必孤独网 > 如何通俗易懂地解释遗传算法?有什么例子?

如何通俗易懂地解释遗传算法?有什么例子?

【sjyan的回答(174票)】:

大三的时候上了一门人工智能,其中有一次作业就用到了遗传算法,问题是这样的:

求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0,9]的最大值。这个函数大概长这样:

那么如何应用遗传算法如何来找到这个奇怪的函数的最大值呢?

事实上,不管一个函数的形状多么奇怪,遗传算法都能在很短的时间内找到它在一个区间内的(近似)最大值。

相当神奇,不是吗?

接下来围绕这个问题,讲讲我对遗传算法的一些理解。实现代码以及在Matlab中使用遗传算法的小教程都附在最后。

1.介绍

遗传算法(Genetic Algorithm)遵循『适者生存』、『优胜劣汰』的原则,是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。

遗传算法模拟一个人工种群的进化过程,通过选择(Selection)、交叉(Crossover)以及变异(Mutation)等机制,在每次迭代中都保留一组候选个体,重复此过程,种群经过若干代以后,理想情况下其适应度达到***近似最优***的状态。

自从遗传算法被提出以来,其得到了广泛的应用,特别是在函数优化、生产调度、模式识别、神经网络、自适应控制等领域,遗传算法发挥了很大的作用,提高了一些问题求解的效率。

2.遗传算法组成

  • 编码 - 创造染色体
  • 个体 - 种群
  • 适应度函数
  • 遗传算子
    • 选择
    • 交叉
    • 变异
  • 运行参数
    • 是否选择精英操作
    • 种群大小
    • 染色体长度
    • 最大迭代次数
    • 交叉概率
    • 变异概率

2.1 编码与解码

实现遗传算法的第一步就是明确对求解问题的编码和解码方式。

对于函数优化问题,一般有两种编码方式,各具优缺点

  • 实数编码:直接用实数表示基因,容易理解且不需要解码过程,但容易过早收敛,从而陷入局部最优
  • 二进制编码:稳定性高,种群多样性大,但需要的存储空间大,需要解码且难以理解

对于求解函数最大值问题,我选择的是二进制编码。

以我们的目标函数 以我们的目标函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x), x∈[0,9] 为例。

假如设定求解的精度为小数点后4位,可以将x的解空间划分为 (9-0)×(1e+4)=90000个等分。

2^16900002^17,需要17位二进制数来表示这些解。换句话说,一个解的编码就是一个17位的二进制串。

一开始,这些二进制串是随机生成的。

一个这样的二进制串代表一条染色体串,这里染色体串的长度为17。

对于任何一条这样的染色体chromosome,如何将它复原(解码)到[0,9]这个区间中的数值呢?

对于本问题,我们可以采用以下公式来解码:

x = 0 + decimal(chromosome)×(9-0)/(2^17-1)decimal( ): 将二进制数转化为十进制数

一般化解码公式:

f(x), x∈[lower_bound, upper_bound]x = lower_bound + decimal(chromosome)×(upper_bound-lower_bound)/(2^chromosome_size-1)lower_bound: 函数定义域的下限

upper_bound: 函数定义域的上限

chromosome_size: 染色体的长度

通过上述公式,我们就可以成功地将二进制染色体串解码成[0,9]区间中的十进制实数解。

2.2 个体与种群

『染色体』表达了某种特征,这种特征的载体,称为『个体』。

对于本次实验所要解决的一元函数最大值求解问题,个体可以用上一节构造的染色体表示,一个个体里有一条染色体。

许多这样的个体组成了一个种群,其含义是一个一维点集(x轴上[0,9]的线段)。

2.3 适应度函数

遗传算法中,一个个体(解)的好坏用适应度函数值来评价,在本问题中,f(x)就是适应度函数。

适应度函数值越大,解的质量越高。

适应度函数是遗传算法进化的驱动力,也是进行自然选择的唯一标准,它的设计应结合求解问题本身的要求而定。

2.4 遗传算子

我们希望有这样一个种群,它所包含的个体所对应的函数值都很接近于f(x)在[0,9]上的最大值,但是这个种群一开始可能不那么优秀,因为个体的染色体串是随机生成的。

如何让种群变得优秀呢?

不断的进化。

每一次进化都尽可能保留种群中的优秀个体,淘汰掉不理想的个体,并且在优秀个体之间进行染色体交叉,有些个体还可能出现变异。

种群的每一次进化,都会产生一个最优个体。种群所有世代的最优个体,可能就是函数f(x)最大值对应的定义域中的点。

如果种群无休止地进化,那总能找到最好的解。但实际上,我们的时间有限,通常在得到一个看上去不错的解时,便终止了进化。

对于给定的种群,如何赋予它进化的能力呢?

  • 首先是选择(selection)
    • 选择操作是从前代种群中不断选择2个较优个体,让这些较优个体(父母)将它们的基因传递到下一代,直到填满种群数量上限
    • 在选择操作前,将种群中个体按照适应度从小到大进行排列
    • 采用轮盘赌选择方法(当然还有很多别的选择方法),各个个体被选中的概率与其适应度函数值大小成正比
    • 轮盘赌选择方法具有随机性,在选择的过程中可能会丢掉较好的个体,所以可以使用精英机制,将前代最优个体直接选择
  • 其次是交叉(crossover)
    • 两个待交叉的不同的染色体(父母)根据交叉概率(cross_rate)按某种方式交换其部分基因
    • 采用单点交叉法,也可以使用其他交叉方法
  • 最后是变异(mutation)
    • 染色体按照变异概率(mutate_rate)进行染色体的变异
    • 采用单点变异法,也可以使用其他变异方法

一般来说,交叉概率(cross_rate)比较大,变异概率(mutate_rate)极低。像求解函数最大值这类问题,我设置的交叉概率(cross_rate)是0.6,变异概率(mutate_rate)是0.01。

因为我们相信2条优秀的父母染色体交叉更有可能产生优秀的后代,而变异的话产生优秀后代的可能性极低,不过也有存在可能一下就变异出非常优秀的后代。这也是符合自然界生物进化的特征的。

3.遗传算法流程

在matlab下写了个测试程序。在matlab下写了个测试程序。

附上代码github.com/yanshengjia/

测试结果

  • 最优个体:00011111011111011
  • 最优适应度:24.8554
  • 最优个体对应自变量值:7.8569
  • 达到最优结果需要的迭代次数:45

迭代次数与平均适应度关系曲线(横轴:迭代次数,纵轴:平均适应度)

有现成的工具可以直接使用遗传算法,比如Matlab。

最后就再介绍一下如何在Matlab中使用遗传算法。

在MATLAB中使用GA

1. 打开 Optimization 工具,在 Solver 中选择 ga - genetic algorithm,在 Fitness function 中填入 @target

2. 在你的工程文件夹中新建 target.m,注意MATLAB的当前路径是你的工程文件夹所在路径

3. 在 target.m 中写下适应度函数,比如

function [ y ] = target(x)y = -x-10*sin(5*x)-7*cos(4*x);end*MATLAB中的GA只求解函数的(近似)最小值,所以先要将目标函数取反。

4. 打开 Optimization 工具,输入 变量个数(Number of variables) 和 自变量定义域(Bounds) 的值,点击 Start,遗传算法就跑起来了。最终在输出框中可以看到函数的(近似)最小值,和达到这一程度的迭代次数(Current iteration)和最终自变量的值(Final point)

5. 在 Optimization - ga 工具中,有许多选项。通过这些选项,可以设置下列属性

  • 种群(Population)
  • 选择(Selection)
  • 交叉(Crossover)
  • 变异(Mutation)
  • 停止条件(Stopping criteria)
  • 画图函数(Plot functions)

【章程的回答(18票)】:

alteredqualia.com/visua

我来补一个js实现,第一名也就是弹弹弹球已经说的很好了。

楼主可以简单看一下代码

【heartszh的回答(1票)】:

楼上说了很多了,只举个没提到的例子。感觉这个例子更容易懂。

大学时搞过一个机器学习机器人,用的就是神经网络+遗传算法。

假设你要做一个机器人,目的是自动盯紧另一个乱串的机器人并想办法抓住他。你的输入是各种传感器读数,你的输出是轮子马达的转速(左右可以速率不同实现转向)。

设计一个简单的神经网络(图片来自网络),

但是权值是什么才能达到目的呢?需要training。我们就用遗传算法。

你可以开始random一组权值,测试一下能不能抓到?然后再random一组权值,测试一下能不能抓到?即使抓不到,是不是离对方很近?(就是楼上提到的fitness function评估)。

把评估结果好的留下,不好的扔掉,然后交叉繁殖。即一部分权值取爸爸的,另一部分权值取妈妈的,看看小孩结果怎样?

最后,还要有变异,因为不变异,只靠random一些解来进行交叉繁殖,是很容易近亲繁殖只找到次优解。变异就是某些权值(随机一下)突然变了,不再继承爸爸妈妈了。

经过若干轮的遗传+变异之后呢,你确实可以看到机器人在不同地形会演化出各种策略抓捕哦,例如绕圈从旁边绕到前面抓捕,等等。

【刘腾达的回答(1票)】:

可以看看《复杂》一书,里面有关于遗传算法的介绍。

【牛阿的回答(14票)】:

大三软件工程学生,以前只听过遗传算法这个名字,但是真正是怎么一回事没有了解过。今天刚好看到 @sjyan 的回答,想起这学期正好选了人工智能这堂课,就觉得想试着码一下这个算法,算是提前预习一下。于是花了两个小时把这个算法大概搞懂了,把思路写一遍,也算是自己再熟悉一遍(如果哪里搞错了请大神们轻喷

理解这个算法首先要理解一些术语。下图(来自Genetic Algorithms Fundamentals)把术语之间的关系表示的很清楚。

遗传算法就是通过不断地进化,将种群里面我们最想要的染色体保留下来。进化多次之后,种群里的大部分染色体都会是比较优势的染色体(我们想要的解),所以我们可以通过这个算法获取多个较优解。

ps: 关于基因和等位基因的区别:基因(gene)是指染色体上的特定位置,而等位基因(allele)则是当前染色体在该基因处的值。

知道一些术语之间的关系之后,可以试着尝试搞懂算法了。拿@sjyan刚刚这道题做例子。

求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0,9]的最大值。

用遗传算法解这道题的过程, 他说得很清楚,主要是三个阶段:

初始化阶段

  1. 确定染色体的形式。先选择一种方式对x进行编码,使其从实际的解空间(phenotype space)被映射到编码空间(genotype space),也就是把实数x变成一条染色体。在这道题中我沿用了@sjyan的编码方式,即把解空间划分为

    等份,然后通过一个17个bit的染色体来表达解空间的实数值。

  2. 确定好染色体形式之后,我们便可以拿它生成一个初始的种群。

进化迭代阶段

接下来会进行不停地进化迭代,每次迭代主要由三个阶段组成:选择、交叉、变异。

  1. 选择阶段。选择阶段经历了适应性选择和随机选择。在适应性选择中,我们通过适应性函数(fitness function)对种群中的每一条染色体进行适应性评估,按评估结果对染色体进行排序。筛选出适应性最好的一定数量(可以通过参数调节)的染色体,作为下一代的父母加入存货列表。而在随机选择中,我们会随机挑选一些没有通过适应性选择的个体也加入存活列表,这样做是为了使得一些拥有潜在价值基因但适应性很差的个体得以生存下来。

  2. 交叉阶段。每一代染色体的数量是一定的,我们淘汰了一部分染色体,就要生成新的染色体来补足空缺。从上一代中,我们保留了一部分存活的染色体,它们之间将会进行交叉。交叉是指随机从存活列表中抽取两个染色体,将这两条染色体进行融合从而生成新的染色体(就是取一部分父染色体的基因,再在母染色体取在父染色体没有取到的基因,把这些基因合成一条新的染色体),把新的染色体加入种群中。交叉操作会一直持续,直到种群数量跟之前的种群数量相同。

  3. 变异阶段。对于种群中的每一条染色体,使其一定几率地发生随机变异(在这个例子下就是反转染色体上某一个bit的值)。

验收阶段

经过很多代的进化之后,种群里面的染色体基本上符合最优化的要求了。这时就可以去对里面的染色体进行解码(decode),将其转化为实际的解。

python实现

代码写的挺渣的,不过标了很多注释。

#encoding=utf-8import mathimport randomimport operatorclass 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 xrange(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 xrange(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 xrange(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 xrange(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(17, 300) # 200次进化迭代 for x in xrange(200): ga.evolve() print ga.result()

简陋的)运行结果,很接近

总结

遗传算法可以产出一组相对较优的解,而且不需要根据具体问题去进行过多的逻辑推演,速度也相对较快。缺点就是不能保证解是最优的。

【叶小伦的回答(35票)】:

补充几个关于遗传算法的说明:

  • 现实问题转换到遗传算法是一个难点,也就是现实问题的解如何映射到遗传算法的个体上,完成了这一步,后面的三个算子操作就按部就班了(也要根据实际问题做调整)。
  • 将现实问题的解映射到遗传算法中的个体之后,接下来就要确定一个评估函数(也叫适应度函数),这个评估函数能够定量地评估某个个体的好坏,从而指导整个进化过程朝着使群体适应度增加的方向进化,这样一来,最终的群体中才会有较优解。
  • 遗传算法中最重要的就是几个算子,包括选择算子,交叉算子,变异算子,每一种算子在解决问题的时候都需要根据实际情况仔细考究,比如交叉算子是单点还是双点,交叉点怎么确定?选择算子中是轮盘赌选择还是锦标赛选择?这些算子是遗传算法最重要的地方。而前面所说的适应度函数也在这里使用,怎么使用呢,简单地说,就是适应度大的个体更有机会把基因遗传给下一代,注意,这里说的是更有机会,也就是说适应度小的个体基因也有一定机会往下一代遗传,避免了出现寻优只寻到局部最优的情况(如果适应度小的没有任何机会,那么寻优过程就变成了爬坡,爬到一个山头发现还有一个更高的山头,但这个时候已经下不去了,详细过程看下文吧)。
  • 遗传算法中有很多参数,比如说初始种群的数量,交叉概率,变异概率,进化代数等等,这些参数影响算法的收敛速度和收敛值。
  • 遗传算法是一种仿生算法,类似这样的算法还有粒子群和蚁群算法,这类算法得益于自然界现象的启发,而不是像确定性算法那样的数学论证。

------------以下是原答案------------

通俗地讲,遗传算法是一种最优化方法,很多书上介绍说,它是一种“软”算法,软算法是相对于严格,确定,精确的硬算法而言的,显然遗传算法这种模拟自然界进化行为的计算属于“软”计算,扯远了,既然遗传算法是一种求解最优化问题的方法,那么本质上,它是一种寻优算法,下面讲一个例子,来说明它的寻优过程。

这个例子来自《复杂》这本书,书中讲了一个大概,我用C语言实现了一遍这个例子,加上了我自己的理解,可能更好懂些。

我现在有一个叫做罗比的机器人,它的世界是二维的,你可以把它的世界想象成一个M乘以N的网格,它的世界里到处是废易拉罐,这些废易拉罐的分布完全是随机的,我现在要为它寻求一个策略,让它去清扫这些易拉罐,而且是快速有效地清理。

上图是罗比世界的示意图,图中散乱放着易拉罐,当然,只是示意图,MN 可以随意指定。我们假设它的世界周围是高高的墙,每个格子里面的易拉罐不多于个,罗比本身并不是很聪明,也看不远,它只能看到自己当前所在的格子和它周围的四个格子,显然,每个格子有三种状态:空的,有一个易拉罐,墙壁。比如罗比现在看到它的东边有易拉罐,北边和西边是墙,南边的格子是空的。每次罗比的动作我们规定有以下几种:

  • 向北移动

  • 向东移动

  • 向南移动

  • 向西移动

  • 随机移动

  • 不动

  • 收集罐子

为它设计了如下的计分规则:

  • 如果当前格子中有罐子而且清理了,加 10 分。

  • 如果当前格子中没有罐子却执行清理的动作,扣 1 分。

  • 如果撞到了墙,扣 5 分,并且弹回原来的格子。

当然,罗比尽可能多捡罐子,不要撞墙,没罐子的时候别去捡,得到的分数就会越多。显然,这个问题是一个最优化问题,我们的目标是让罗比取得最高的分数,问题本身也比较简单,一个M乘以N的网格,网格中随机地放上易拉罐,罗比有固定的几种动作,制定好计分规则,问题是:寻求一个最佳策略,在这个策略下,罗比能够快速地取得高分。

这个最佳策略就是我们要的最优解,用遗传算法解决问题的第一步就是确定进化的个体是什么,这里的个体对应于问题的,正如有的个体好,有的个体差一样,解也是有好有坏,我们的目的是找到一个最优解,类似于遗传进化中的优胜劣汰,我们需要的就是遗传算法给出的那个最优个体(这里不严谨,其实应该是较优个体,只保证全局较优)。

接下来我们就来确定要进化的个体到底是什么,这里的个体对应于问题的某个解,即罗比的一个策略,在这里,定义罗比的策略是K-V 形式的映射关系,其中的键是罗比当前的情况,值是罗比应该执行的动作。简单点说,就是什么情况下应该做什么动作(动作是有限的,只有七种)。

我们把每个格子的三种状态映射到整数(每个格子只有三种状态):

  • 空 -- 0

  • 有罐子 -- 1

  • 墙壁 -- 2

把罗比可以执行的动作也映射到整数:

  • 向北移动 -- 0

  • 向东移动 -- 1

  • 向南移动 -- 2

  • 向西移动 -- 3

  • 随机移动 -- 4

  • 不动 -- 5

  • 收集罐子 -- 6

给定顺序:[北,东,南,西,中],那么罗比在最开始那副图中的情况”就是 [ 2 , 1 , 0 , 2 , 0 ] ,这个“情况”对应于前面说的那个“K”,很显然,现在它应该向东移动,那么这个键对应的值就是 1(V),(好的策略是这样,坏的策略可能面对这样的情况偏偏要罗比撞墙)。

我们得对“情况”,也就是K进行数值化,对该情况下采取的"动作"(V)也得数值化,这样才能计算。

先考虑罗比所处的“情况”都有哪些,包括罗比自己当前的格子,共有五个方向,每个方向又有三种可能的状态,那么,情况一共就有 3×3×3×3×3=243 种(当然一些情况是不可能的,比如罗比当前的位置是墙,不过程序员都很懒,不想费劲找出所有不可能的情况,我们只要知道就行了)。

那么一个策略就是 243 个键值对,这个 键值表(策略表) 就是我们的策略,应该说是罗比的策略,每次罗比只要抬头四周望望(确定自身所处情况),然后根据自己当前的情况到策略表中找对应的动作(根据K查找键值表中的V),然后执行对应的动作(V),然后再抬头望望,判断一下自身情况,从策略表中找到对应的动作,然后执行,下一次再这样,它就可以根据这个策略来进行游走了。显然,好的策略表让它有高分,坏的策略表只会让它乱走,撞得头破血流,还捡不着罐子。

我们还可以把键的顺序按照一定的原则固定下来,那么只要有一个值的列表就可以了(键的位置即是索引),罗比会知道当前的情况是情况几(确定索引),然后直接查对应的值去执行动作就行,这样一来,罗比的策略就是一个有243个元素的一维数组,比如说下面的这个是它的一个策略:

[2,5,0,4,2,1,3,2,4,1,2,3,2,4,1,2,3,2,1,2,1,2,1,2,1,2,4,2,2,2,4,…,3,5,6,0]

可是这样的策略有多少种呢?一共有 72437243 种(243个元素,每个元素都有7种可能的取值),是个很大的数字,这也说明了我们的解空间是很大的,注意,这么多策略中可能90% 以上都是糟糕的策略,比如说罗比现在的北边是墙壁,某一个策略让它向北移动,那好,它一头撞在墙上,所以我们的目的是为罗比找出最优的策略,让它的得分尽可能地多。

如何在这么多解中找到一个较优解,是遗传算法要做的事情。

下面来介绍一下大致思路,其实为罗比寻找最佳策略的过程就是一个进化的过程,你可以想象有一个种群,这个种群中有若干个个体,每个个体代表一个策略,其实前面我们说每个策略表示为一个长度为243 的数组,这个就是编码的过程,一个这样的数组就是一个个体。不同的问题有不同的编码方式,比较多的是二进制编码,不过我们这里更加适合字符串编码方式,编码完成之后,我们让这个种群按照适者生存,物竞天择的原则进行进化,最后进化到一定的代数之后,剩下来的就是那些比较优秀的个体,也就是那些比较好的策略,从最后一代中选出一个最好的个体,OK ,这个就是我们为罗比找到的好策略。

主函数中关键的就三行,选择,重组,变异

void main(){//随机生成解int solu[POP_SIZE][SOLU_DIM];init_solu(solu);int i;double fit[POP_SIZE];//最初的解get_fitness(solu,fit);printf("当前的最高分数为:%f ",max(fit,POP_SIZE));printf("计算中........");//进化for(i = 0; i GEN_NUM;i++){ga_sel(solu); //选择ga_cross(solu); //交叉重组ga_mut(solu); //变异}//进化完毕,输出最终的解get_fitness(solu,fit);printf("最终的最高分数为:%f ",max(fit,POP_SIZE));printf("");}

这里面有几个关键的地方:

  1. 每个个体怎么表示?

  2. 如何度量一个个体的优劣程度?

  3. 种群如何不断选择重组变异?

问题一:个体和种群的表示

对于第一个问题,其实对应于遗传算法中的编码过程,也就是将现实问题的解对应到程序中的具体表示,上文中说道我们可以把罗比所能碰到的所有情形和该情形下执行的动作当成一个键值表,那么在这里,问题的一个解就是一张键值表,而这个键值表在程序中我们可以很方便的表示,为了更方便一些,我们把键出现的顺序固定下来,那么只要用一个长度为243的一维数组就可以表示了,索引表示情形(可以把每种情形映射到一个0到242的整数,下文会讲到),数组的值表示该情形下罗比该执行的动作(前文中已经编号,0到6),于是我们就可以用一个一维数组表示一个解,也就是一个策略,即一个个体,假定种群包含200个个体(200个策略,即200张键值表),我们设定种群的大小为 200 ,那么这个种群就可以用一个 200×243 的矩阵来表示,就像下面这样:

其中,每一行表示一个个体,这个矩阵表示的是一个有 200 个个体的种群。

下面说一下某一种情形如何映射到一个0~242的整数。

罗比所面对的某一种情形类似下面的形式:

  • 北 – 墙壁(2)

  • 东 – 易拉罐(1)

  • 南 – 空(0)

  • 西 – 墙壁(2)

  • 中 – 空(0)

第一列是方位,第二列是此处的状态,这种情形对应的表示就是21020,我们可以把这个数字当做三进制的数,因为每一位都有三种取值,这种情形对应的十进制值就是:

按照这种编码方式,第1种情形到第243种情形都可以用一个0到242之间的整数表示,而且顺序是唯一的,那么具体情形到整数之间的映射就完成了,我们可以用这个整数值作为数组的索引,而罗比也可以根据自己面对的情形知道其所对应的编号,立刻得到对应索引位处的整数,即动作编号,然后执行相应的动作。

下面代码用来生成一个初始种群:

/**生成初始解**/void init_solu(int solu[][SOLU_DIM]){int i,j;for(i = 0;i POP_SIZE;i++)for(j = 0;j SOLU_DIM;j++)solu[i][j] = m_round(rand_zo()*6);}

顺便说下罗比的模拟世界,我们用一个二维数组生成罗比的网格世界,然后为它建好墙壁,撒上易拉罐。

void init_world(int world[][COL],double p){int i,j;//初始每个格子为空,用0表示for(i = 0;i ROW;i++) for(j = 0;j COL;j++)world[i][j] = 0;//放置墙壁,2代表墙壁for(i = 0;i ROW;i++){world[0][i] = 2;world[i][0] = 2;world[ROW-1][i] = 2;world[i][COL-1] = 2;}//放置易拉罐for(i = 1;i ROW - 1;i++) for(j = 1;j COL - 1;j++)if(rand_zo()p) world[i][j] = 1;}

该函数接收一个二维数组和概率 p ,以这个概率在罗比的世界里放置易拉罐。

问题二:度量个体的优劣程度

对于每一个个体(策略),我们让罗比采用这个策略去清理 100 次,在每次清理过程中执行200次动作,每次清理都有一个得分,取这100 次的平均成绩作为它的最终得分,注意,100 次清理,每次清理的世界都不同(每次随机放置易拉罐) , 这样,我们就大致衡量出了每个个体的好坏。

在代码中,这个评价函数接受一个种群,也就是200 个个体,然后返回一个长度为 200的得分数组,里面的元素对应每一个个体的分数,也叫做它的适应度,为了使适应度都为正值(因为后面要求和算比率), 我给每个个体的最终得分加上了最低得分的相反数,那么每个个体的得分区间就是[0,2000]

/**适应度**/void get_fitness(int solu[][SOLU_DIM],double fitness[]){int i,j;int ST[SOLU_DIM]; //每个个体对应一张策略表for(i = 0; i POP_SIZE;i++){for(j = 0;j SOLU_DIM;j++)ST[j] = solu[i][j];double per_sum = 0;/*对于每一个个体,给它CL_TIMES机会打扫,取平均成绩做为它的适应度分数,每一次的世界都不同,但是策略表相同*/for(j = 0;j CL_TIMES;j++){int wor[ROW][COL];init_world(wor,P);per_sum += do_clean(wor,ST);}//保证适应度是正数fitness[i] = per_sum/CL_TIMES + 5*PER_DO_TIMES;}}

这段代码中用到了一个函数do_clean(),这个函数用来模拟罗比清理的过程,它接收一个脏乱的世界和一个清扫策略,然后罗比按照这个清扫策略执行动作200次,返回这一次清扫过程的得分,下面是具体过程:

/**根据策略表ST,执行清扫动作,返回对应的分数**/double do_clean(int wor[][COL],int ST[]){//约定:可以执行的动作有://向北移动 0//向东移动 1//向南移动 2//向西移动 3//随机移动 4// 不动 5//清理罐子 6//计分规则://如果罗比所在的格子中有罐子,并且打扫了罐子,+10分//如果执行打扫的动作而当前格子中没有罐子, -1分//如果撞到了墙,-5分,并且弹回原来的格子//从左上角开始打扫int pos[2] = {1,1};double sc = 0;int i;for(i = 0; i PER_DO_TIMES;i++){// 得到当前位置的情况int situ[5];situ[0] = wor[pos[0] - 1][pos[1]];situ[1] = wor[pos[0]][pos[1] + 1];situ[2] = wor[pos[0] + 1][pos[1]];situ[3] = wor[pos[0]][pos[1] - 1];situ[4] = wor[pos[0]][pos[1]];// 得到此情况下的策略编号int str_num = get_stra(situ);// 按照此策略进行行动,并对wor和sc进行对应更新int dire;int rand_num;switch(ST[str_num]){case 0://向北移动N:if(move(pos[0],pos[1],0))sc -= 5;elsepos[0]--;break;case 1://向东移动E:if(move(pos[0],pos[1],1))sc -= 5;elsepos[1]++;break;case 2://向南移动S:if(move(pos[0],pos[1],2))sc -= 5;elsepos[0]++;break;case 3://向西移动W:if(move(pos[0],pos[1],3))sc -= 5;elsepos[1]--;break;case 4://随机移动rand_num = rand_zo();if(rand_num 0.25)goto N;else if(rand_num 0.50)goto E;else if(rand_num 0.75)goto S;elsegoto W;break;case 5://不动break;case 6://清理罐子if(wor[pos[0]][pos[1]] == 1)sc += 10;elsesc -= 1;break;}}return sc;}

问题三:进化过程

现在到了最有趣的地方,就是种群如何进行选择,重组,变异,我们一个一个来说。

选择

选择,顾名思义,就是从种群中选择一批比较优良的个体,让它进行繁殖,而判断某个个体是否优良自然就是看这个个体在评估函数下的得分高低,这里我们使用比较简单的轮盘赌的方式来选择个体,想象有下面这个轮盘:

每个部分的面积不同,如果有一根指针,你旋转这个轮盘,当然指针落在面积大的那一块上的概率会大些,注意,这里是每个部分的面积不同,如果有一根指针,你旋转这个轮盘,当然指针落在面积大的那一块上的概率会大些,注意,这里是概率具有更高适应度的个体仅仅是有比较大的概率被选中,这就保证了算法具有一定的随机性,一定程度上避免落入局部最优解,因为那些适应度不高的个体也有机会被选中,而你不能说这些适应度不高的个体就没有好的基因片段遗传给下一代,但是从总体上来讲,适应度高的个体更多的机会把自己的基因遗传给下一代。在代码中,我们先计算出每个个体的被选概率,概率之和是1,然后计算累计概率,进行选择,关于为什么计算累计概率,这仅仅是种实现上的技巧,只要能够按照轮盘赌的原则进行选择就可以了,选择的结果是一个新的种群,新的种群的大小和原来的种群大小是相同的,但是已经发生了变化,因为一些适应度高的个体可能被多次选中,有一些适应度很低的个体可能一次都没有被选中,也就是被淘汰了,下面是选择的具体过程:

//选择算子void ga_sel(int old_pop[][SOLU_DIM]){int new_pop[POP_SIZE][SOLU_DIM];double pr[POP_SIZE],cum_pr[POP_SIZE];double pr_sum = 0;int i,j,k;//计算每个个体的适应度get_fitness(old_pop,pr);//计算累计概率for(i = 0;i POP_SIZE;i++)pr_sum += pr[i];for(i = 0;i POP_SIZE;i++)pr[i] = pr[i]/pr_sum;cum_pr[0] = pr[0];for(i = 1;i POP_SIZE;i++)cum_pr[i] = cum_pr[i - 1] + pr[i];//轮盘赌方法选择for(i = 0;i POP_SIZE;i++){double rand_n = rand_zo();for(j = 0; j POP_SIZE - 1;j++){if(rand_n cum_pr[0]){for(k = 0;k SOLU_DIM;k++)new_pop[i][k] = old_pop[0][k];break;}else if(rand_n = cum_pr[j] rand_n = cum_pr[j+1]){for(k = 0;k SOLU_DIM;k++)new_pop[i][k] = old_pop[j+1][k];break;}}}for(i = 0;i POP_SIZE;i++)for(j = 0;j SOLU_DIM;j++)old_pop[i][j] = new_pop[i][j];}

重组(交叉)

现在我们进入基因重组这个步骤,基因重组的概念不用多说,我们把上一步骤中选择出来的个体,以一定的概率P_CROSS进行基因重组,提一句,这个程序的有很多参数,比如说种群大小,度量适应度时罗比清理的次数,每次清理中执行的动作次数,基因重组的概率,基因变异的概率,进化的代数,网格世界的大小,这些参数是可以适当调节的,对算法的收敛速度和收敛值会有影响。回到正题,在选择出一批个体之后(这些个体有向下一代传递基因的权利),让他们两两之间进行交叉(啪啪啪),啪啪啪的结果当然就是产生了新的个体。交叉算子的具体操作有很多种,这里我们还是选择比较简单的单点交叉,如图所示

图中是以二进制来编码的,采用单点交叉,它很好地说明了单点交叉的过程。下面是代码中的交叉过程图中是以二进制来编码的,采用单点交叉,它很好地说明了单点交叉的过程。下面是代码中的交叉过程

//交叉void ga_cross(int new_pop[][SOLU_DIM]){//选择需要交叉的个体int count = 0;int need_cr[POP_SIZE];int i,j;int temp[SOLU_DIM];for(i = 0;i POP_SIZE;i++)if(rand_zo() P_CROSS){need_cr[count] = i;count++;}if(count % 2 != 0)count++;//随机决定一个不为0的交叉点int cr_point = 0;while(cr_point == 0)cr_point = m_round(rand_zo()*SOLU_DIM);//进行交叉for(i = 0;i count;i+=2 )for(j = cr_point;j SOLU_DIM;j++){temp[j] = new_pop[need_cr[i]][j];new_pop[need_cr[i]][j] = new_pop[need_cr[i+1]][j];new_pop[need_cr[i+1]][j] = temp[j];}}

变异

正如自然界中的个体一样,我们的进化过程也要考虑到变异的情况,与前面两个过程不同的是,变异针对的是某个基因,比如说我们的种群大小是200,每个个体有243个基因,那么这个种群的基因总数就是200×243,每一个基因都有变异的可能性,当然这个可能性通常来说是比较小的(就像自然界中的变异也不常发生一样),在这里我们给定每个基因变异的概率是0.005,下面是变异的具体过程

/***变异**/void ga_mut(int pop[][SOLU_DIM]){int ge_sum = POP_SIZE*SOLU_DIM;int i,j,k;for(i = 0; i ge_sum;i++){if(rand_zo() P_MUT){//定位此基因所在的染色体,此处,染色体即个体,下同int chr_loc;chr_loc = i/SOLU_DIM;//定位此基因所在染色体上的基因位int gen_loc;gen_loc = i%SOLU_DIM;//进行变异pop[chr_loc][gen_loc] = m_round(rand_zo()*6);}}}

至此,种群完成了第一次进化,选择交叉变异,我们设定让此种群进化1000代,最终幸存下来的个体就是我们所要找的好策略。

C语言运行的结果说一下,如果这个网格的大小是30×30,其中易拉罐的比例设在0.5,每次让罗比行动200步,那么,这个游戏的满分就是2000分,我自己事先按照我觉得比较好的策略给罗比用,就是向有罐子的地方移动,有罐子就捡起来,不要撞墙,罗比按照这个策略清理1000次,每次罐子的分布都随机,平均得分是1210分,遗传算法进化出来的策略平均得分是1992分,完整代码需要的话请留言,可以运行试一试。

【温酒的回答(14票)】:

来来来,我来举个实际的用法。

我爸老宅那边有个四户紧邻的人家。

A家,B家,C家,D家

A家是这样的:两个父母辈的人该吃吃该花花该用用,存款一点点,反正等动迁,也不急买房

B家是这样的:我妈运气不好养了个男娃,只好扣扣索索存钱,买了一套婚房以后,日子过舒坦了

C家是这样的:她们家一门心思就是买房子,买了20年。

D家是这样的:她们本来学着C买房,然后突然有一天脑抽了异想天开去买股票了

结果你也知道了。

A家的男娃三十好几了,还是没媳妇,因为动迁政策烂,乡下地方拿了一套房,根本找不到媳妇

B家因为买了一套房,一切走上正轨,普普通通。

C家发财了。

D家本来发财了,后来突然亏得妈都不认识

然后从小到大,四家人的娃就同时看着三个家庭走向不同阶层。

深刻明白一个道理:

有些人只会做愚蠢的决定,这些人会被时代淘汰。

有些人会因为运气做一个聪明的决定,他们的后代会不会被淘汰,得看他们后代是否能做聪明决定

有些人只会做聪明的决定,这些人后代只会越来越富足

然后,你觉得,A家B家C家D家选一个策略作为你将来的战略,

你选谁?

选A那叫破釜沉舟堵上人生

选B家那叫观望待定犹豫不决

选C家那就叫遗传算法

选D家那个叫随缘

其中,D家就是使用遗传算法的时候,变异那一步做得不好的例子。

一句话来说:

已经成功的群体,使用正确策略的几率远远大于已经失败的群体。

新闻聚焦
热门推荐
  • 低俗靡乱!喜宴竟充斥惊艳脱衣舞表演

    中新网12月7日电 据台湾《联合报》报道,桃园县内喜宴、庙会、社团、晚会充斥钢管、清凉秀、脱衣舞,县议员舒翠玲以自己参加的场合为证,当场看见辣妹和客人磨蹭,甚至指导单位是“桃园县政府”、“公所”的活动也如......

    01-13 来源:未知

    分享
  • 《我是特种兵之霹雳火》崔华盾扮演者张进个人资料及照

    《我是特种兵之霹雳火》崔华盾扮演者 本篇电视资讯由未必孤独网(www.vbgudu.com)独家整理,如有转载请注明出处。 曾经同是“特警小虎队”一员的李飞和张进这次将重新在《霹雳火》中集结,并且再度并肩作战。 由李......

    01-13 来源:未知

    分享
  • 郎永淳老婆吴萍患肿瘤赴美疗养 郎永淳近况

    郎永淳温馨全家福 央视新闻主播郎永淳虽然在电视上天天与观众见面,因播报新闻成了公众人物,并拥有了很多的粉丝。但生活中的郎永淳却十分很低调,不仅从未谈及过自己的私生活,就连他的另一半及孩子也未被曝光过。......

    01-13 来源:未知

    分享
  • 《我是特种兵之霹雳火》王星扮演者李飞个人资料及照片

    《我是特种兵之霹雳火》王星扮演者李飞 本篇电视资讯由未必孤独网(www.vbgudu.com)独家整理,如有转载请注明出处。 《我是特种兵之霹雳火》作为刘猛导演特种兵系列的第四部作品,自筹划以来就备受网友关注。承继着......

    01-13 来源:未知

    分享
  • 梦鸽:为孩子做什么都不为过 李案会造成世界影响

    梦鸽(资料图) 李某某等涉嫌强奸案从2月份发酵至今,持续半年,热度不减。作为被告李某某的监护人,梦鸽放下红色明星、部队歌唱家的尊严,发布声明、反诉、上访,走进长枪短炮的包围圈,代替独子站在第一线。 为了......

    01-13 来源:未知

    分享
  • 雷!彪悍美女竟在大街上做超不雅动作

    ......

    01-13 来源:未知

    分享
  • 孙俪微博拍卖老公邓超的爱裤,邓超与孙俪感情好不好

    今天我们来盘点一下娱乐圈的模范夫妻。孙俪和邓超是娱乐圈有名的模范夫妻,两人相爱至今都没有穿过其他的绯闻,而在邓超走向逗比之路的过程中,娘娘孙俪也开始受到影响,近日邓超在网上晒了一张与孙俪的另类合影,网......

    01-12 来源:

    分享
  • 巩俐与孙红雷谈过恋爱吗?巩俐孙红雷主演的电影是哪部

    从绯闻女友巩俐、左小青,到王骏迪,孙红雷绯闻伴随走红。在《窈窕绅士》发布会上,孙红雷大晒幸福,并直言,“我现在还不会和女友公开亮相,以免被人说我在炒作。”被问及是否有意结婚,他说,“谈婚论嫁对我来说不......

    01-12 来源:

    分享
  • 曝盛一伦喜欢骂人成瘾,盛一伦同性恋是真的吗?

    子妃升职记不仅火啦张天爱,也让男主盛一伦踏进拉娱乐圈。盛一伦被曝骂人成瘾 骂人聊天记录图片,近日,盛一伦将东家乐漾影视诉至法院,索片酬1051.5万元,朝阳法院已受理此案。12月12日,盛一伦发长文回应解约风波称......

    01-12 来源:

    分享
  • 北京学生卡坐地铁打折吗?北京现在有几条地铁?

    北京的物价使出拉名的贵,许多北漂为啦省钱想尽办法。近日,在北京部分地铁站周边,出现贩卖“”的卡贩子,100元就能办一张大,还送学生证。新京报记者探访发现,从卡贩子手中购得的,能顺利充值并可享受2.5折优惠。......

    01-12 来源:

    分享
返回列表