遗传算法(GA)_sga和ga算法-程序员宅基地

技术标签: 算法  python  

遗传算法概述

1.智能优化算法

遗传算法是根据达尔文的进化论衍生出来的一种智能优化算法。

智能优化算法又称为现代启发式算法,是一种具有全局优化性能,通用性强,且适合于并行处理的算法。这种算法一般具有严密的理论一句,而不是单纯凭借专家经验(这里要点名AHP),理论上可以在一定的时间内找到最优解或者近似最有解。

启发式算法有很多种,像A*算法(之前有所提及),粒子群算法蚁群算法模拟退火算法等,此处不赘述。

2.基本遗传算法

基本遗传算法(SGA),即简单或标准遗传算法,其遗传进化操作过程简单,容易理解,是其他一些遗传算法的雏形和基础。

3.遗传算法特点

  1. 群体搜索,易于并行处理
  2. 不是i盲目穷举,而是启发式搜素
  3. 适应度函数不受连续、可微等条件的约束,适用范围很广

遗传算法原理

在开始我们的代码之前,先简要说明一下进化论的流程:
生物的进化就是物种基因的重组与变异过程,父辈的基因重组或者变异产生下一代个体,然后进行自然选择,不满足自然选择的就被淘汰,剩下个体即符合条件,重复上述过程N次迭代后,物种达到一个比较优秀的水准。

我们首先看一下遗传算法的基本流程
算法基本流程

看完了遗传算法基本流程,我们来解释一下上图中出现的一些名词和相关操作的解释:

什么是自适应度(Fitness)?
要用计算机模拟自然选择,就要给计算机一个反馈,用来指导算法朝着目标前进,这是将你要选择的个体的特征表现出来,也就是量化。比如我们要求遗传字符数组,值为"helloworld",我们需要让计算机通过几次迭代,猜出该字符串。我们要通过算法告诉计算机,每一轮猜的结果怎么样,是否达到了目标,如何衡量猜测的结果和实际的差异?举个简单的栗子,比如现在我们让计算机随机初始化生成一串长度为10的char数组"hesaddfsds",显然,只有第一位和我们目标一致,那么Fitness=1,进行下一次迭代(选择、交叉、变异、计算适应度)。
直到都猜对了,或者达到预设的迭代次数时,停止迭代,程序终止。

父代如何产生子代?
第一步:用轮盘赌法选择上一代个体,这些个体进行杂交(即交叉),也就是基因部分的交换,对轮盘赌法有相关了解的应该知道,轮盘赌法是概率选取,即在此处是对那些适应度较好的个体有更大的概率被选中,这样也符合自然规律和人类认知,即:对环境适应性强的个体大部分保留,但也有小部分适应性差的并未被淘汰。
轮盘赌算法大致有三种,其性能优劣和局限性在此不做过多说明。

什么是基因?
基因是描述一个个体特征的抽象出来的值,可以是一串二进制数,或者是一串格雷码,在此处就是char[10]数组。

为什么要变异?
变异是为了种群有更多可能和选择,设想一下,如果种群基因中原本就不存在想要的基因片段,经过数千次的迭代也只能达到局部最优解,根本没有达到全局最优解的可能和条件。变异有好有坏,好的会给下一代带来更多可能,获得基因片段也会经过迭代逐渐淘汰。变异也符合人类对生物学基本的认知。

遗传算子的改进

  1. 排序选择:
    (1)对群体中的所有个体按其适应度进行降序排序;
    (2)根据具体求解问题,设计一个概率分布表,将哥哥概率值按照上述排列次序分配给各个个体;
    (3)基于这些概率用轮盘赌法来选择下一代群体;
  2. 均匀交叉:
    (1)随机尝试一个与个体编码(基因)长度相同的二进制屏蔽字段P[W1W2W3…Wn]
    (2)按照下列规则从A、B两个父代中产生两个新的个体X、Y,若Wi=0,则X的第i个基因继承A的对应基因,Y的第i个基因继承B的对应基因;否则两个个体的第i个基因相互交换。
  3. 逆序变异:
    (1)选定一段要变异的基因片段
    (2)对此片段进行逆序处理:如2019变为9102

遗传算法应用

废话不多说,我们通过一个简单的例子来展示一下:
由于基因交叉择优要用到轮盘赌算法
这个例子中没有基因交叉过程,即对单个个体进行不断优化“变异”

import numpy as np
import random
import datetime

#这里我们要给出种群基因库的所有基因,变异,交叉都在此范围内
geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."

#这是我们最终要实现的目标
target = "Hello World!"

#初始化种群
#随机在基因库中抽取指定长度返回
def generate_parent(lenghth):
    genes = []
    #随机位置
    genes.extend(random.sample(geneSet, lenghth))
    #join()函数以指定分隔符对字符串数组进行连接
    return ''.join(genes)

#子代产生,这里是随机让父辈的某个基因发生变异
def mutate(parent):
	#随机生成0-len(parent)之间的整数
    index = np.random.randint(0,len(parent))
    #先将父代基因全部拷贝给子代
    childGens = [i for i in parent]
    #从基因库中随机抽出两个基因作为变异项和可选择项目,确保每次变异都不一样
    newGen,alternate = random.sample(geneSet,2)
    #相当于c++中三目运算符
    childGens[index] = alternate if childGens[index]== newGen else newGen 
    return ''.join(childGens)

#自适应度fitness函数,即告诉计算机与目标相差的"距离"
def get_fitness(guess):
    return np.sum(1 for expected, actual in zip(target, guess) if expected == actual)

#呈现每一轮猜测的fitness打分情况
def display(guess):
    fitness = get_fitness(guess)
    print("{0}\t{1}" .format(guess, fitness))

#主函数
bestParent = generate_parent(len(target))
bestFitness = get_fitness(bestParent)
display(bestParent)

while True:
    child = mutate(bestParent)  #产生子代
    childFitness = get_fitness(child) #子代的fitness得分
    if bestFitness >= childFitness:
        continue
    display(child)
    if childFitness >= len(bestParent):
        break
    bestFitness = childFitness
    bestParent = child

结果:
.kafqNZyEKch	0	
.kafqNZyEKdh	1	
.kafq ZyEKdh	2	
.kafq ZyrKdh	3	
.klfq ZyrKdh	4	
.klfq ZorKdh	5	
.elfq ZorKdh	6	
.elfq WorKdh	7	
Helfq WorKdh	8	
Helfq Worldh	9	
Hellq Worldh	10	
Hellq World!	11	
Hello World!	12	

以上代码对遗传算法进行了简化,尤其是get_fitness()函数,在此函数里将目标值与猜想值进行了绑定,使得每一位基因最多进行一次迭代就能成功达到目标值。此外上述函数由于比较简单,省去了交叉过程,也正因为这个原因,也对选择过程的一些步骤进行了缩减(如省去了轮盘赌算法)。
这个demo只是对遗传算法有了初步了解后的一个简单模拟,实际上针对不同的问题,get_fitness()函数的判定、交叉/变异的基因片段的选择要复杂许多。

基于遗传算法衍生除了很多算法:

  • 混合遗传算法
  • 免疫遗传算法
  • 小生境遗传算法
  • 单亲遗传算法
  • 并行遗传算法

等一系列算法

此处贴一个我看到的比较好理解的遗传算法代码链接供大家参考
传送门

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45436831/article/details/118941968

智能推荐

MMDeploy详解-程序员宅基地

文章浏览阅读2k次,点赞3次,收藏6次。MMDeploy理解_mmdeploy

最流行的android组件大全_android热门组件-程序员宅基地

文章浏览阅读1.3k次。原文链接:http://blog.csdn.net/smallnest/article/details/38658593/Android 是目前最流行的移动操作系统之一。 随着新版本的不断发布, Android的功能也日益强大, 涌现了很多流行的应用程序, 也催生了一大批的优秀的组件。本文试图将目前流行的组件收集起来以供参考, 如果你发现本文还没有列出的组件,欢迎在评论中贴出来,我会定_android热门组件

python小练习5:如何判断一个数能否被3整除_用python编写一个小程序,用来判断任意一个数是否能被3整除-程序员宅基地

文章浏览阅读7.7w次,点赞6次,收藏28次。题:如何判断一个数能否被3整除?(或者被其他任意一个数整除)方法一:取余 x = input("input an number:") if x % 3 == 0: print "%d 能被3整除" %(x) else: print "%d 不能被3整除"_用python编写一个小程序,用来判断任意一个数是否能被3整除

网桥_网桥下设备广播-程序员宅基地

文章浏览阅读925次。先装好网卡,连上网线,然后开始!设置linux让网桥运行 配置网桥我们需要让linux知道网桥,首先告诉它,我们想要一个虚拟的以太网桥接口:(这将在主机bridge上执行,不清楚的看看测试场景)root@bridge:~> brctl addbr br0其次,我们不需要STP(生成树协议)等。因为我们只有一个路由器,是绝对不可能形成一个环的。我们可以关闭这个功能。(这_网桥下设备广播

linux|tgz解压出错_linux tgz解压 失败-程序员宅基地

文章浏览阅读1.1k次。[stu01@localhost pointer]$ tar -xzvf cnn-stories.tgztar (child): cnn-stories.tgz: Cannot open: No such file or directorytar (child): Error is not recoverable: exiting nowtar: Child returned statu_linux tgz解压 失败

小小君的C语言第五课_创建一个字符串数组(内容是你周围一圈人的姓名),输出最长字符串的长度。-程序员宅基地

文章浏览阅读596次。二维数组、字符串数组、多维数组 //声明一个二维数组 // 数据类型 + 数组名[第一维长度][第二维长度] = {值1,值2, ...}; //一般第一维 叫行 第二维叫列 //需求_创建一个字符串数组(内容是你周围一圈人的姓名),输出最长字符串的长度。

随便推点

Kubernetes业务日志收集与监控-程序员宅基地

文章浏览阅读732次。随着容器技术以及容器编排技术的成熟,越来越多的中小型企业也在将服务迁移到Kubernetes中,更智能,更便捷的管理服务,降低运维成本,而在迁移过程中,业务日志的收集以及业务服务的监控,..._kubemate日志监控

前端面试题—2021年web前端开发面试题_2021年前端开发面试题-程序员宅基地

文章浏览阅读796次。【前端面试】前端面试题—2021年web前端开发面试题本文章作为2021届应届毕业生在实习面试期间所接受的前端面试的面试题。2021年最新面试题CSS盒子模型的要素 ,https://www.cnblogs.com/clearsky/p/5696286.html;CSS中常用伪元素选择符;Position属性四个值:static、fixed、absolute和relative的区别和用法 ;解释CSS样式中display中inline、block、inline-block的区别 ;var和l_2021年前端开发面试题

用函数实现两个数的加法_7)编写一个函数,参数包括两个运算数x,y以及进位,通过调用全加器计算x,y的求和结果-程序员宅基地

文章浏览阅读4.5k次,点赞6次,收藏3次。1,加法#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>int add(int x, int y){int z = x + y;return z;}int main(){int num1 = 0;int num2 = 0;int sum = 0;printf(“请输入两个操作数\n”);scanf("%d %..._7)编写一个函数,参数包括两个运算数x,y以及进位,通过调用全加器计算x,y的求和结果

对tableView的contentOffset的理解_tableview.contentoffset-程序员宅基地

文章浏览阅读4.1k次。tableView往上滚动, contentOffset.y为正,此时对于tableView内部控件而言,原点在哪里?如图所示:未开始滚动时,可以把contentOffset.y == 0看成一条分割线,随着向上滚动的进行,对于tableView内部控件而言原点已经滚动到原来contentOffset.y == 0这条分割线的上方了,而此时这个位置的分割线变成contentOffset.y ==_tableview.contentoffset

关于MyBatis读取Mapper文件的一个坑_mybatis读取resources下的mapper文件-程序员宅基地

文章浏览阅读1.9k次。最近在Idea上开发MyBatis,准备随便先写一点东西,结果一写就出了问题。Exception in thread "main" org.apache.ibatis.exceptions.PersistenceException: ### Error querying database. Cause: java.lang.IllegalArgumentException: Mapped S..._mybatis读取resources下的mapper文件

数据比你更懂用户:Tensorflow2 情感分析实战-程序员宅基地

文章浏览阅读496次。楔子达尔文曾说过,情感在人类的进化过程中起到了非常重要的作用。但他一定没有想到,有一天,机器也能读懂人类的情感了。把情感引入计算机学科,把 “主观的情感” 变得可计算,最早可追溯到上世纪..._tensorflow 分析用户收藏

推荐文章

热门文章

相关标签