GA 算法

本贴最后更新于 1337 天前,其中的信息可能已经沧海桑田

遗传算法(genetic algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程计算模型,是一种通过模拟自然进化过程搜索最优解的方法。下面我将分享自己在做GA模型的心得与困惑。

先来整理一下 GA 的基本步骤:

  1. 随机生成一定数量的种群。
  2. 对种群的个体进行编码与评估。
  3. 选用合适的方法对现有种群中的个体做出选择。
  4. 对选择出来的个体进行“交叉”并获得新的个体。
  5. 对下一代进行”突变“操作。

第一步:随机生成一定数量的种群。首先应该构思存储个体的数据结构。我选择的是嵌套的列表(list)。一个个体的形式为[[个体],[编码],评估值],一个种群则是[[[个体1],[编码1],评估值1],[[个体2] ,[编码2],评估值2],[[个体3],[编码3],评估值3],...]。采用随机的方式生成种群/个体:

'''
popnum:单位种群中个体数量,cistern:存储单个种群的数据池,lbound,ubound:个体的取值范围
precision:取值的精度,n:问题的维度
'''
def initpop():
    cistern=[]
    for i in range(popnum):
        particle=[]
        for j in range(n):
            particle.append(round(random.uniform(lbound,ubound),precision))
        cistern.append([particle,[],None])
    return cistern

第二步:选择合适的编码方案以及评估函数。我采用的是经典的二进制编码形式,这样的编码有个好处是可以利用 Python 自带的 bin()函数快速实现,但是一般情况下各个维度的数字是需要编在一起的,而 bin()函数不能保证二进制数值的长度,往往导致在转化较小数字的时候其二进制长度过短,即便是将多个维度编码后的二进制数值简单拼接,我们也需要在拼接处设置标志位,这样才能在“交叉”过后将各维度分开,如果不设标志位而随机分割,那么将会在一定层面上导致“二次交叉”或“自我交叉”,这样便失去了“交叉”的意义,为了解决这一问题我们可以采用 format()函数,也可以对各个维度分别编码,分别“交叉”,在这里我选择后者。对于评估函数,我采用问题本身,即目标函数的函数值。

def D2B(num):  #编码(十进制2二进制)
    return bin(round((num-lbound)*(pow(2,l)-1)/(ubound-lbound)))
	
def B2D(num):  #解码(二进制2十进制)
    return round(lbound+(ubound-lbound)/(pow(2,l)-1)*int(num,2),2)
	
def trans(cistern): #对种群进行二进制编码
    for i in cistern:
        for j in range(n):
            i[1].append(D2B(i[0][j]))
    return cistern
	
def fitness(cistern): #对种群进行评估
    for i in cistern:
        i[2]=fit(i[0])
    return cistern

第三步:选用合适的方法对现有种群中的个体做出选择。个体选择的方法有很多,轮盘赌、 锦标赛选择、排名选择,等。在这里我选择最为简单的轮盘赌。由于函数对于种群池的修改是直接地 所以我将采用“一夫一妻制”,即三个父代个体不能产生两个子代个体,这也是为了避免多余“交叉”。

def select(cistern):
    reservoir=[]
    choice=[]
    resualt={}
    s=0
    for i in cistern:  #将种群中所有的适应值相加
        s=s+i[2]
    for j in cistern:  #求每个个体的占比
        reservoir.append(j[2]/s)
    for k in range(1,popnum):  #求每个个体的累计占比
        reservoir[k]=reservoir[k]+reservoir[k-1]
    reservoir.insert(0,0)   #补充轮盘的开端,设为0
    for c in range(popnum):  #选择次数为种群容量
        r=random.random()    #选择概率
        for t in range(1,len(reservoir)-1):
            if r<reservoir[t] and r>reservoir[t-1]:
                choice.append(t-1)
    for d in set(choice):   #采用字典的方式存储各个个体以及被选中的次数
        resualt[d]=choice.count(d)
    resualt=sorted(resualt.items(), key=lambda item: item[1],reverse=True) #以被选中的次数大小排序
    choice=[]
    for u in resualt:  
      choice.append(u[0])
    return choice #返回选择的结果(下标)

第四步:对选择出来的个体进行“交叉”并获得新的个体。这一步地操作,我采用对原种群直接修改的方式。 对于两个个体的编码,选择一个交叉点位并将交叉点位以及其后面的二进制位一并交换,而且也采用前面提到的分别“交叉”。

def crossover(a,b): #染色体(个体)单位
    ch=random.random()  #交叉概率
    if ch<overchance:
        length=9999999
        for i in a[1]+b[1]:  #对较小长度的二进制选择交叉位作为各个维度的交叉位
            if len(i)<length:
                length=len(i)
        r=random.randint(2,length-1) #选择交叉位
        for j in range(n):  #对二进制数值进行剪切和拼接
            temp=a[1][j][r:]
            a[1][j]=a[1][j][:r]+b[1][j][r:]
            b[1][j]=b[1][j][:r]+temp
            a[0][j]=B2D(a[1][j])  #更改十进制数值
            b[0][j]=B2D(b[1][j])
        a[2]=fit(a[0])    #重新评估函数
        b[2]=fit(b[0])

第五步:对下一代进行”突变“操作。“突变”是此算法中比较简单的流程,一般采用单点变异。

def variation(cistern):
    for i in cistern:
        c=random.random()  #变异概率
        if c<variantchance:  #达成条件进行变异
            m=99999
            for x in i[1]:  #以长度较小的二进制值选择点位
                if len(x)<m:
                    m=len(x)
            r=random.randint(2,m-1) #变异点位
            for j in range(n):    #更换点位的值
                if i[1][j][r]=='0':  
                    i[1][j]=replace_char(i[1][j],'1',r)
                    i[0][j]=B2D(i[1][j]) 
                else:
                    i[1][j]=replace_char(i[1][j],'0',r)
                    i[0][j]=B2D(i[1][j])
                i[2]=fit(i[0]) #重新评估函数
    return cistern

最后进行一下总结,第一步以树的结构存储种群中的个体,第二部采用分别编码,第三步采用“一夫一妻制”选择 并且优先选择被选中次数多的个体进行下一步的操作,第四步采用分别“交叉”,第五步简单变异。剩下还有一些特殊的函数 匹配函数,保持最优函数,目标函数和字符交叉函数。

def replace_char(string,char,index): #单字符交叉,用于“变异”
    string=list(string)
    string[index]=char
    return ''.join(string)
	
def fit(x):  #目标函数,函数值即为适应度。
    value=round(10*math.sin(5*x[0])+7*abs(x[1]-5)+10,precision)
    return value
	
def match(choice):  #匹配函数,防止选选择的个体个数为奇数。
    if len(choice)%2!=0:
        choice.pop()
    return choice
	
def best(cistern,Best):  #最优个体保持函数
    tem=sorted(cistern,key=lambda x:x[2],reverse=True)[0]
    if not Best:
        Best=copy.deepcopy(tem)
    elif tem[2]>Best[2]:
        Best=copy.deepcopy(tem)
    return Best

接下来以上面代码的目标函数对 GA 进行测试:

import math
import random
import copy
popnum=50
ubound=10
lbound=-10
precision=3 
l=0
while pow(2,l)<(ubound-lbound)/(1/pow(10,precision)): #计算所需二进制长度
    l=l+1
n=2 #2-D 
overchance=0.8
variantchance=0.3
Best=[]
a=initpop()
trans(a)
fitness(a)
for j in range(100):
    s=select(a)
    if s:
        c=match(s)
        for i in range(0,len(c),2):
            crossover(a[c[i]],a[c[i+1]])
    variation(a)
    Best=best(a,Best)
    print(Best)

QQ 截图 20200329203944.pngQQ 截图 20200329204003.png

相关帖子

回帖

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Typecho

    Typecho 是一款博客程序,它在 GPLv2 许可证下发行,基于 PHP 构建,可以运行在各种平台上,支持多种数据库(MySQL、PostgreSQL、SQLite)。

    12 引用 • 65 回帖 • 452 关注
  • 支付宝

    支付宝是全球领先的独立第三方支付平台,致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验,及转账收款/水电煤缴费/信用卡还款/AA 收款等生活服务应用。

    29 引用 • 347 回帖
  • Bootstrap

    Bootstrap 是 Twitter 推出的一个用于前端开发的开源工具包。它由 Twitter 的设计师 Mark Otto 和 Jacob Thornton 合作开发,是一个 CSS / HTML 框架。

    18 引用 • 33 回帖 • 662 关注
  • 大数据

    大数据(big data)是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

    93 引用 • 113 回帖
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 706 关注
  • Lute

    Lute 是一款结构化的 Markdown 引擎,支持 Go 和 JavaScript。

    25 引用 • 191 回帖 • 17 关注
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    12 引用 • 54 回帖 • 163 关注
  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    34 引用 • 467 回帖 • 742 关注
  • SpaceVim

    SpaceVim 是一个社区驱动的模块化 vim/neovim 配置集合,以模块的方式组织管理插件以
    及相关配置,为不同的语言开发量身定制了相关的开发模块,该模块提供代码自动补全,
    语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱
    即用的 Vim-IDE。

    3 引用 • 31 回帖 • 100 关注
  • 脑图

    脑图又叫思维导图,是表达发散性思维的有效图形思维工具 ,它简单却又很有效,是一种实用性的思维工具。

    25 引用 • 83 回帖
  • WebSocket

    WebSocket 是 HTML5 中定义的一种新协议,它实现了浏览器与服务器之间的全双工通信(full-duplex)。

    48 引用 • 206 回帖 • 347 关注
  • TensorFlow

    TensorFlow 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表示数学操作,图中的线(edges)则表示在节点间相互联系的多维数据数组,即张量(tensor)。

    20 引用 • 19 回帖 • 1 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 31 关注
  • Elasticsearch

    Elasticsearch 是一个基于 Lucene 的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于 RESTful 接口。Elasticsearch 是用 Java 开发的,并作为 Apache 许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。

    117 引用 • 99 回帖 • 223 关注
  • 友情链接

    确认过眼神后的灵魂连接,站在链在!

    24 引用 • 373 回帖 • 1 关注
  • CloudFoundry

    Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。

    5 引用 • 18 回帖 • 164 关注
  • Logseq

    Logseq 是一个隐私优先、开源的知识库工具。

    Logseq is a joyful, open-source outliner that works on top of local plain-text Markdown and Org-mode files. Use it to write, organize and share your thoughts, keep your to-do list, and build your own digital garden.

    5 引用 • 62 回帖
  • FlowUs

    FlowUs.息流 个人及团队的新一代生产力工具。

    让复杂的信息管理更轻松、自由、充满创意。

    1 引用
  • Rust

    Rust 是一门赋予每个人构建可靠且高效软件能力的语言。Rust 由 Mozilla 开发,最早发布于 2014 年 9 月。

    58 引用 • 22 回帖 • 5 关注
  • 禅道

    禅道是一款国产的开源项目管理软件,她的核心管理思想基于敏捷方法 scrum,内置了产品管理和项目管理,同时又根据国内研发现状补充了测试管理、计划管理、发布管理、文档管理、事务管理等功能,在一个软件中就可以将软件研发中的需求、任务、bug、用例、计划、发布等要素有序的跟踪管理起来,完整地覆盖了项目管理的核心流程。

    6 引用 • 15 回帖 • 127 关注
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 18 关注
  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖 • 47 关注
  • Ant-Design

    Ant Design 是服务于企业级产品的设计体系,基于确定和自然的设计价值观上的模块化解决方案,让设计者和开发者专注于更好的用户体验。

    17 引用 • 23 回帖 • 1 关注
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统,它问世于 1985 年,起初仅仅是 Microsoft-DOS 模拟环境,后续的系统版本由于微软不断的更新升级,不但易用,也慢慢的成为家家户户人们最喜爱的操作系统。

    221 引用 • 473 回帖
  • 深度学习

    深度学习(Deep Learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。

    52 引用 • 40 回帖
  • 分享

    有什么新发现就分享给大家吧!

    247 引用 • 1792 回帖 • 7 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 5 关注