精华内容
下载资源
问答
  • 遗传算法进制编码 matlab实现

    千次阅读 2020-03-31 18:17:09
    问题1:遗传算法第一步就是要解决编码问题,常用二进制编码,用过matlab的都知道有自带的十进制转换二进制的API,但是生成的char类型变量却不方便完成后续计算适应度、交叉、变异等操作; 问题2:常见实现编码方式为...

    问题介绍

    • 问题1:遗传算法第一步就是要解决编码问题,常用二进制编码,用过matlab的都知道有自带的十进制转换二进制的API,但是生成的char类型变量却不方便完成后续计算适应度、交叉、变异等操作;
    • 问题2:常见实现编码方式为先确定精度,根据目标精度反推最低需要的二进制编码位数然后编码,但是存在的问题是假如函数搜索范围是[-1,2],需要0.001的精度,那么就是3000个数,需要12位二进制编码,但是完整的12位二进制编码可以表示到4096,如果直接用12位编码,那么将会在交叉及变异过程中,生成超出3000的数字,即超出搜索范围;

    解决思路

    • 针对问题1,必须将二进制编码转化为数组形式,才能实现单点交叉 变异等操作;
    • 针对问题2,只能以补满位数为前提,即12位编码,在[-1,2]上分4096个数,精度即为0.0007;
    • 本文拿解决如下函数,编码为例,理论求得最大值3.850
      在这里插入图片描述在这里插入图片描述

    具体实现

    • 首先根据设定的编码位数,生成完整的二进制编码矩阵,利用matlab自带的dec2bin,然后根据转换出来的二进制的length与编码位数对比,将其补0满足设定的编码位数,以下是matlab代码实现
      % 将函数定义域转化为二进制,转化的实数按区间映射   
      % chromosome_size:设定的编码位数,例如本例采用12
      % problem_size:完整二进制编码位数能表示的数值,如12位,能表示到2^12-1=4095
      % problemDB:二进制编码矩阵
      function[] =  ProblemDB_create()
      global problem_size;
      global chromosome_size;
      global problemDB;
      for i = 1:problem_size
          arr = dec2bin(i);
          for j = 1:length(arr)
              problemDB(i,chromosome_size-length(arr)+j) = str2num(arr(1,j));
          end    
      end
      end
      
    • 生成如下矩阵在这里插入图片描述
    • 生成了完整的编码,应该将其对应到函数的搜索区间上去,为了让代码可以复用,应该封装一个函数,可以提供输入区间起始和终止值,根据传入的基因编码计算对应在区间上的真值;具体思路也很简单,将二进制转换为10进制,计算其与完整二进制编码位数最大值的比例即可得知其映射在搜索区间上的真值;
      % 将二进制编码表示的个体转化为函数搜索区间上的实数值   
      % problem_size:同上
      % indiv:个体的二进制编码数组
      % from:搜索区间的起始值
      % to:搜索区间的终止值
      function[val] = realValue(indiv, from, to)
      global problem_size;
      dec = 0;
      for i = 1:length(indiv)
          if(indiv(1,i) == 1)
              dec = dec + 2^(length(indiv)-i);
          end
      end
      val = from + dec/problem_size*(to-from);
      end
      
      在这里插入图片描述

    总结

    • 以上仅仅介绍了遗传算法解函数时的编码部分,交叉变异等其他步骤可以参考我上一篇博客,除了编码部分,修改下适应度函数和变异,其他基本相同,因此变量名都还是组卷的;
    • 由于matlab里循环及数组索引需要从1开始,因此编码及搜索时并没有将0编进去,需要处理此问题的记得修改一下;
    展开全文
  • 基于单点交叉采用串表示,n(≥2)点交叉与均匀交叉采用环表示的方式,推导出十进制编码遗传算法的模式理论,避免了二进制遗传算法模式理论中把交叉点的选取看作是相互独立的和忽视交叉对染色体生成作用的两点不足,得出了...
  • 遗传算法的二进制编码

    千次阅读 2020-06-01 20:08:34
    假设我们要用遗传算法求解某个函数的最大值,x的取值范围是[-3.0,12.1],那么我们现在就是要从这个取值范围内取出一些x来作为种群的个体,要取出多少个x这取决于你想要种群有多少个体,即种群规模。 如果我们用...

    假设我们要用遗传算法求解某个函数的最大值,x的取值范围是[-3.0,12.1],那么我们现在就是要从这个取值范围内取出一些x来作为种群的个体,要取出多少个x这取决于你想要种群有多少个体,即种群规模。

    如果我们用十进制去表示种群中的个体,并且如果设定种群规模为10个个体,那么很简单,只要在-3.0到12.1这个区间随机选择10个非重复的实数即可。但是现在我们想用一个二进制去表示种群中的一个个体,该怎么做呢?

    首先一个直观的想法是直接找到十进制对应的二进制,但是如果是那样做就涉及到有符号的二进制数了。

    所以我们换个思路,使用无符号的二进制数,虽然无符号的二进制数只能表示正数,但是我们可以将这些正数转换到我们想要的区间。

    前面说了,只要在-3.0到12.1这个区间随机选择10个非重复的实数即可,但是这里有个精度的问题,如果精度为1的话,那么-3到12大概只有15个数,从15个数中随机选择10个数,那也太不随机了吧,假设我的种群规模是100呢,怎么从15个数中随机选择100个数?因此要增加精度,比如说,如果精度为10000话,那么原先的一个单位长度就被切分成10000份,原先精度为1的区间只有15.1个数,而现在精度为10000的区间就有151000个数,即15.1*10^4。

    那么我们使用二进制编码跟使用实数编码道理一样,如果我们需要精度为10000,那么也就需要151000个数来表示这个区间,实数编码你要根据你需要的精度将连续的区间离散化,然后再从离散的数据中随机抽取。二进制编码也是一样,也就是说现在你需要151000个二进制数来表示这个区间内离散的数,然后如果你种群规模是100,那就是从151000个二进制数里面随机抽取100个二进制数成为你的种群。

    二进制的位数越多能表示的数越多,所以我们必要先计算一下使用多少位数的二进制。其实对于一个[L,U]的区间,如果精度设定为10^4,需要满足:

    2^(n-1) < (U-L)*10^4 <= 2^n  -1

    我觉得这样表示也可以:2^(n-1) < (U-L)*10^4 < 2^n  

    这是什么意思呢?首先我们要知道对于一个n位的无符号二进制数能表示0~2^n - 1,比如说8位二进制数能表示的数是0-255,也就是说总共能表示256个数,这并不难记,因为10000 0000 就是2^8,而这个数上一个数就是1111 1111,这正好是8位二进制数能表示的最大的数,即255,所以我们很容易能记住一个n位的无符号二进制数能表示0~2^n - 1。

    一个n位的无符号二进制数最多能表示2^n个数,所以说不能超过2^n,同理可得,不能低于2^(n-1),因为如果你低于2^(n-1),那么你为什么不直接用(n-1)位表示呢,却要浪费位数呢?

    由于2^18 = 262144, 2^17 = 131072, 151000正好介于这两个数之间,所以应该使用18位二进制数。我们可以顺便验证一下,如果使用16位二进制数,16位二进制数最多只能表示2^16 = 65535个数,而我们现在需要151000个数,如果使用19位二进制数,19位二进制数最多只能表示2^19 = 524288,显然没有必要浪费位数,我们不需要那么高精度。

    于是接下来我们要从这0-262143这个范围内抽取一定的数作为种群的个体,假设种群规模是100,那就是从中抽取100个个体,值得一提的是其实我们只要151000个数来表示这个区间就已经满足我们的精度了,然而现在却有262144个数,这没有关系,因为一方面多多益善,越多数精度越高,另一方面二进制的位数能表示的数就是这样。

    假设种群规模是100,前面我们已经说了,从262144个二进制数里面抽取100个二进制数作为我们的种群(随机生成100个18位二进制数的方式),那么问题又来了,得到的这100个二进制数如何转换到[-3,12.1]这个区间?首先我们要知道,这262144个二进制数转成十进制数是0-262143,我们要从这里面随机抽取100个数。

    于是我们就必须要思考:从0-262143中抽取1个数,如何将这个数转换到属于[-3,12.1]的一个数?

    其实我们可以利用占比。

    假设抽出的二进制数转换成十进制是5417,0-26143这个区间可以划分为26143份,5417在这个区间的占比就是:

    5417/262143 = 0.02066

    也就是说转换到0-1区间里占比0.02066

    转换到0-15.1区间里占比 15.1*0.02066 = 0.311966

    但是现在的区间是从-3开始的,所以-3+0.311966= -2.688。

    其实我们应该连着算比较精确:5417/262143 * 15.1 -3 = -2.687969

    总结一下就是 先把二进制000001010100101001转换成十进制的5417,再将它除以2^n - 1, 再乘以区间长度15.1,在加上区间的开始值-3。

    ===================================================================================

    后来,我在学进化规划的时候,发现又出现了一个做法,虽然我不知道这个做法是不是对算法有利的。就是想把种群的个体平均分布在区间内的操作。

    比如说,种群里有100个个体,而区间是在[-3,12.1],区间长度是15.1,如果你想把种群的每个个体平均分布在区间内,

    可以用15.1/100 = 0.151,也就是说每个个体大概可以占这么长,也就是说规定每个个体都只能在各自被规定的小区间内活动,

    在小区间内自由活动,可以乘以一个概率,即0.151*rand(1),就随机生成了它的位置。

    于是为了让第一个个体在第一个小区间内,第二个个体在第二个小区间内........

    很容易得出某个个体应该处于哪个位置,比如第三个个体应该是在第三个小区间内随机生成的位置。同时要加上-3这个起始点。

    所以假设当前是在计算第i个个体,那么它的位置就是:

    -3 + (i-1)*(15.1/100) + (15.1/100)*rand(1),其中i从1到100迭代,rand(1)是生成0-1的随机数。

    展开全文
  • 采用十进制编码遗传算法求解一个函数极小值问题。目标函数是一个含有30维变量的复杂型超越函数,使用MATLAB7.0下的遗传函数工具箱来寻找函数最小值。
  • 遗传算法求三元函数极值(python)-采用二进制编码 本文的遗传算法采用二进制编码求三元函数极值 所求函数为 要想使用遗传算法,首要任务是进行编码 传统的 GA 中, DNA 我们能用一串二进制来表示, 比如: DNA1 = [1...

    想看实数编码编码的
    博客地址遗传算法求三元函数极值(python)-采用实数编码
    *

    遗传算法求三元函数极值(python)-采用二进制编码

    本文的遗传算法采用二进制编码求三元函数极值
    所求函数为
    在这里插入图片描述
    要想使用遗传算法,首要任务是进行编码

    传统的 GA 中, DNA 我们能用一串二进制来表示, 比如:
    DNA1 = [1, 1, 0, 1, 0, 0, 1]
    DNA2 = [1, 0, 1, 1, 0, 1, 1]
    这里,我们仍然使用二进制编码,但是如何与我们的问题对应起来呢?
    为什么会要用二进制编码, 我们之后在下面的内容中详细说明这样编码的好处. 但是长成这样的 DNA 并不好使用. 如果要将它解码, 我们可以将二进制转换成十进制, 比如二进制的 11 就是十进制的 3. 这种转换的步骤在程序中很好执行. 但是有时候我们会需要精确到小数, 其实也很简单, 只要再将十进制的数浓缩一下就好. 比如我有 1111 这么长的 DNA, 我们产生的十进制数范围是 [0, 15], 而我需要的范围是 [-1, 1], 我们就将 [0, 15] 缩放到 [-1, 1] 这个范围就好.
    我们知道二进制很容易转十进制,再区间压缩以下,这样一个DNA和一个解一一映射。

    def translateDNA(pop):
        return pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2**DNA_SIZE-1) * X_BOUND[1]
    

    例如,1 0 1 0 1 0 0 1 0 0 => (4+32+128+256)/(1024-1)*(5-0)=3.3
    上面针对的单变量的编码,求解单变量的函数极值
    其完整代码如下,这里照搬了别人的代码,后面我会给出引用地址,
    用它主要是参考,并修改为求解三元函数极值的代码
    单变量求函数极值:

    """
    Visualize Genetic Algorithm to find a maximum point in a function.
    可视化遗传算法去找到一个函数的最高点
    """
    import numpy as np
    import matplotlib.pyplot as plt
     
    DNA_SIZE = 10            # DNA length
    POP_SIZE = 100           # population size,种群中个体数目
    CROSS_RATE = 0.8         # mating probability (DNA crossover)0.8的概率进行交叉配对
    MUTATION_RATE = 0.003    # mutation probability,变异强度
    N_GENERATIONS = 200      #迭代次数
    X_BOUND = [0, 5]         # x upper and lower bounds,指定x的取值范围
     
     
    def F(x):
        return np.sin(10*x)*x + np.cos(2*x)*x     # to find the maximum of this function
     
     
    # find non-zero fitness for selection
    #我们都需要一个评估好坏的方程, 这个方程通常被称为 fitness适应度.
    #为了找到下面这个曲线当中的最高点. 那么这个 fitness 方程可以定义为高度, 越高的点, fitness 越高.
    def get_fitness(pred):
        return pred + 1e-3 - np.min(pred)#因为如果直接返回pred可能是负值,而我们在计算概率的时候不能为负值。
        #要进行处理,np.min表示取最小,为最大的负数,可以使全部只变成正的;1e-3为了让float进行相除防止小数点后的数被省略
     
     
    # convert binary DNA to decimal and normalize it to a range(0, 5)
    #对基因的翻译,如这里函数,x轴是实数,这里解释了如何将遗传01序列翻译成实数。用十进制二进制转换
    #pop (population)是一个储存二进制 DNA 的矩阵, 他的 shape 是这样 (pop_size, DNA_size)
    #这里DNA_SIZE,X_BOUND是超参数
    def translateDNA(pop):
        return pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2**DNA_SIZE-1) * X_BOUND[1]
        #dot()函数是矩阵乘,*则表示逐个元素相乘
    	#np.arange()函数返回一个有终点和起点的固定步长的排列
    	#pop.dot(2 ** np.arange(DNA_SIZE)[::-1])已经转换成十进制
    	#但是需要归一化到0~5,如有1111这么长的DNA,要产生的十进制数范围是[0, 15], 而所需范围是 [-1, 1],就将[0,15]缩放到[-1,1]这个范围
    	#a[::-1]相当于 a[-1:-len(a)-1:-1],也就是从最后一个元素到第一个元素复制一遍。所以你看到一个倒序
    	#np.arange(DNA_SIZE)[::-1]得到10,9,8,...,0
     
    #这里进行优胜劣汰的选择步骤
    #适者生存的 select() 很简单, 我们只要按照适应程度 fitness 来选 pop 中的 parent 就好. fitness 越大, 越有可能被选到.
    def select(pop, fitness):    # nature selection wrt pop's fitness
        idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,p=fitness/fitness.sum())
    	#这里概率不能为负,所以pred要进行非负处理
    	#replace表示抽样后是否放回,这里为True表示有放回,则可能会出现相同的索引值
        # p 就是选它的比例,按比例来选择适应度高的,也会保留一些适应度低的,因为也可能后面产生更好的变异
        #np.random.choice表示从序列中取值  np.arange()函数返回一个有终点和起点的固定步长的排列
        return pop[idx]
     
    #繁衍,交叉父母的基因
    def crossover(parent, pop):     # mating process (genes crossover)
        if np.random.rand() < CROSS_RATE: #这里是0.8的概率父亲会选择一个母亲进行交叉配对
            i_ = np.random.randint(0, POP_SIZE, size=1)                           #select another individual from pop选择母亲索引一个
            cross_points = np.random.randint(0, 2, size=DNA_SIZE).astype(np.bool) #得到一行[01001100]也是01为了选择哪些点进行交叉;然后进行布尔化
            parent[cross_points] = pop[i_, cross_points]
    		#布尔型数组可以用于数组索引,布尔型数组长度必须跟被索引的轴长度一致
    		#生成布尔数组可以组合应用多个布尔条件,使用&(),|()之类的布尔算数运算符,python的关键字and和or在布尔型数组中无效
    		#parent[cross_points]即parent列表中取出cross_points为True地方的值&&&&&!!!!
    		#【母亲是pop的i_索引行DNA,选出母亲对应在cross_points为TRUE的地方的值】赋给【父亲DNA对应在cross_points选出为TRUE的地方的值】。
        return parent
     
    #繁衍,有变异的基因会出现
    #将某些 DNA 中的 0 变成 1, 1 变成 0
    def mutate(child):
        for point in range(DNA_SIZE):
            if np.random.rand() < MUTATION_RATE:
                child[point] = 1 if child[point] == 0 else 0
        return child
     
    #产生离散均匀分布的整数,若high不为None时,取[low,high)之间随机整数,否则取值[0,low)之间随机整数。
    pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE))   # initialize the pop DNA
    #pop = np.=random.randint(0,2,(1,DNA_SIZE).repeat(POP_SIZE,axis=0))这里是生成了一样的DNA,后面也可以随着变异变成不一样的
     
    #[[01001100],
    # [10111100],
    # ...]
    plt.ion()       # something about plotting开启图像交互模式
     
    x = np.linspace(*X_BOUND, 200)
    #linspace(start, stop, num=50, endpoint=True, retstep=False, dtype=None)
    #X_BOUND = [0, 5],要产生200个样本点
    #返回固定间隔的数据。他将返回num个等间距的样本,在区间[start,stop]中。其中,区间的结束端点可以被排除在外(用endpoint标识)
    plt.plot(x, F(x))
     
    for _ in range(N_GENERATIONS):
        F_values = F(translateDNA(pop))    # compute function value by extracting DNA传入到F函数
     
        # something about plotting
        if 'sca' in globals(): sca.remove()
        sca = plt.scatter(translateDNA(pop), F_values, s=200, lw=0, c='red', alpha=0.5); plt.pause(0.05)#plt.pause表示显示秒数
     
        # GA part (evolution)
        fitness = get_fitness(F_values) #计算适应度
        print("Most fitted DNA: ", pop[np.argmax(fitness), :])
        pop = select(pop, fitness)#这里选出了另外一种population
        pop_copy = pop.copy()# 备个份
        for parent in pop: #这里parent为遍历pop,一次为其中一行,而这里的pop是从原pop中按适应度概率有放回的选出了POP_SIZE行
            child = crossover(parent, pop_copy)#繁衍
            child = mutate(child) #进行变异
            parent[:] = child       # parent is replaced by its child# 宝宝变大人
     
    plt.ioff(); plt.show()
     
    #在使用matplotlib的过程中,不能像matlab一样同时开几个窗口进行比较,可以采用交互模式,但是放在脚本里运行一闪而过,图像并不停留
    #python可视化库matplotlib有两种显示模式:阻塞(block)模式&交互(interactive)模式
    #在交互模式下:plt.plot(x)或plt.imshow(x)是直接出图像,不需要plt.show()
    #如果在脚本中使用ion()命令开启了交互模式,没有使用ioff()关闭的话,则图像不会常留。防止这种情况,需要在plt.show()之前加上ioff()命令。
    #在阻塞模式下:打开一个窗口以后必须关掉才能打开下一个新的窗口。这种情况下,默认是不能像Matlab一样同时开很多窗口进行对比的
    #plt.plot(x)或plt.imshow(x)是直接出图像,需要plt.show()后才能显示图像
    
    

    关于三元函数代码的修改:
    我的想法是这样的,不知道对不对,不对的话,请大佬留言指出,首先要改的是种群pop产生的矩阵,我的代码是这样的:

     pop = np.random.randint(0,2, size=(POP_SIZE, DNA_SIZE*3)) #matrix (POP_SIZE, DNA_SIZE*3)
    

    第一个参数表示产生0-2范围的随机整数,不包括2

    为了说明方便,这里先假设POP_SIZE=10,DNA_SIZE=4,则DNA_SIZE*3=12,因为有三个变量x,y,z,每个变量占一个DNA_SIZE,则DNA总长度是12位,
    即[010011011010],
    则上面产生的种群矩阵为
    [[1 0 0 0 1 0 0 1 0 0 0 0]
    [0 1 1 1 1 1 1 1 1 0 1 1]
    [0 0 1 0 1 1 1 1 0 1 1 0]
    [1 1 0 0 1 1 1 0 1 1 0 0]
    [0 0 1 1 0 1 1 1 1 0 0 1]
    [1 0 0 1 0 1 1 0 1 0 0 0]
    [0 0 1 0 1 1 0 1 0 0 1 0]
    [1 1 1 1 0 1 1 0 0 1 1 0]
    [0 1 0 0 0 0 1 0 1 1 1 1]
    [1 1 1 1 1 1 1 0 1 1 0 0]]

    共10行,一行表示一个二进制编码表示的DNA,
    矩阵的行数为种群数目
    在上面的种群矩阵中,一行表示一个个体,而每个个体是有x,y,z三个基因片段所组成的,在这里
    取前DNA_SIZE=4列表示x
    所以x_pop为
    [[1 0 0 0]
    [0 1 1 1]
    [0 0 1 0]
    [1 1 0 0]
    [0 0 1 1]
    [1 0 0 1]
    [0 0 1 0]
    [1 1 1 1]
    [0 1 0 0]
    [1 1 1 1]],
    然后依次类推,中间4列表示y,最后4列表示z
    初始种群的个体即使都一样也无所谓,因为后面会通过交叉,配对等会变得不一样。
    在translateDNA这块修改如下,
    代码如下:

    def translateDNA(pop): #pop表示种群矩阵,一行表示一个二进制编码表示的DNA,矩阵的行数为种群数目
        x_pop = pop[:,0:DNA_SIZE]#取前DNA_SIZE个列表示x
        y_pop = pop[:,DNA_SIZE:DNA_SIZE*2]#取中间DNA_SIZE个列表示y
        z_pop = pop[:,DNA_SIZE*2:]#取后DNA_SIZE个列表示z
        #print(x_pop)
        #print(y_pop)
        #print(z_pop)
        #print("\n")
    
        '''pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1)'''#二进制--->十进制
        x = x_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(X_BOUND[1]-X_BOUND[0])+X_BOUND[0]
        y = y_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(Y_BOUND[1]-Y_BOUND[0])+Y_BOUND[0]
        z = z_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(Z_BOUND[1]-Z_BOUND[0])+Z_BOUND[0]
        #print(x,z)
        return x,y,z
    

    有两种求解三元函数极值的代码,
    第一种是按照我自己的想法,在select操作中,关于概率的修改。
    下面是我的求解三元函数极值的完整代码:

    
    # x1*x2-x1*x2+x3
    import numpy as np
    import random
    
    
    DNA_SIZE = 24
    POP_SIZE = 100
    CROSSOVER_RATE = 0.8
    MUTATION_RATE = 0.015
    N_GENERATIONS = 100
    X_BOUND = [3.0,5.0]#x1
    Y_BOUND = [2.1,6.7]#x2
    Z_BOUND = [1.2,9.6]#x3
    
    
    def F(x, y,z):
       val=x*x-x*y+z
       #print(val)
       '''
       for index in range(len(val)):
          if val[index] <0.2:
             val[index]=0.2
             '''
       return val
    
    
    
    def get_fitness(pop): 
        x,y ,z= translateDNA(pop)
        pred = F(x, y,z)
        return pred
    
    def translateDNA(pop): #pop表示种群矩阵,一行表示一个二进制编码表示的DNA,矩阵的行数为种群数目
        x_pop = pop[:,0:DNA_SIZE]#取前DNA_SIZE个列表示x
        y_pop = pop[:,DNA_SIZE:DNA_SIZE*2] ##取中间DNA_SIZE个列表示y
        z_pop = pop[:,DNA_SIZE*2:]取后DNA_SIZE个列表示z
        #print(x_pop)
        #print(y_pop)
        #print(z_pop)
        #print("\n")
    
        '''pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1)'''#二进制--->十进制
        x = x_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(X_BOUND[1]-X_BOUND[0])+X_BOUND[0]
        y = y_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(Y_BOUND[1]-Y_BOUND[0])+Y_BOUND[0]
        z = z_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(Z_BOUND[1]-Z_BOUND[0])+Z_BOUND[0]
        #print(x,z)
        return x,y,z
    
    
    def mutation(child, MUTATION_RATE=0.003):
    	if np.random.rand() < MUTATION_RATE: 				#以MUTATION_RATE的概率进行变异
    		mutate_point = np.random.randint(0, DNA_SIZE*3)	#随机产生一个实数,代表要变异基因的位置
    		child[mutate_point] = child[mutate_point]^1 	#将变异点的二进制为反转
    		
    def crossover_and_mutation(pop, CROSSOVER_RATE = 0.8):
    	new_pop = []
    	for father in pop:		#遍历种群中的每一个个体,将该个体作为父亲
    		child = father		#孩子先得到父亲的全部基因(这里我把一串二进制串的那些01称为基因)
    		if np.random.rand() < CROSSOVER_RATE:			#产生子代时不是必然发生交叉,而是以一定的概率发生交叉
    			mother = pop[np.random.randint(POP_SIZE)]	#再种群中选择另一个个体,并将该个体作为母亲
    			cross_points = np.random.randint(low=0, high=DNA_SIZE*3)	#随机产生交叉的点
    			child[cross_points:] = mother[cross_points:]		#孩子得到位于交叉点后的母亲的基因
    		mutation(child)	#每个后代有一定的机率发生变异
    		new_pop.append(child)
    
    	return new_pop
    
    
    
    def select(pop, fitness):    # nature selection wrt pop's fitness
        #idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
        fitnew = fitness
        for index in range(len(fitnew)):
            if fitnew[index] <0:
               fitnew[index]=0
          
        p=(fitnew)/(fitnew.sum())
    
        idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
                               p=p)
        #print(idx)
        return pop[idx]
    
    def print_info(pop):
    	fitness = get_fitness(pop)
    	max_fitness_index = np.argmax(fitness)
    	print("max_fitness:", fitness[max_fitness_index])
    	x,y,z = translateDNA(pop)
    	print("最优的基因型:", pop[max_fitness_index])
    	print("(x, y, z):", (x[max_fitness_index], y[max_fitness_index],z[max_fitness_index]))
    
    
    if __name__ == "__main__":
       pop = np.random.randint(0,2, size=(POP_SIZE, DNA_SIZE*3)) #matrix (POP_SIZE, DNA_SIZE)
       #print(pop)
       for _ in range(N_GENERATIONS):#迭代N代
          x,y,z = translateDNA(pop)
          pop = np.array(crossover_and_mutation(pop, CROSSOVER_RATE))
          fitness = get_fitness(pop)
          pop = select(pop, fitness) #选择生成新的种群
    
    	
       print_info(pop)
    
    
    

    第二种方法是按照网上的意思:关于函数值:因为如果直接返回pred可能是负值,而我们在计算概率的时候不能为负值。
    # 要进行处理,np.min表示取最小,为最大的负数,可以使全部只变成正的;1e-3为了让float进行相除防止小数点后的数被省略
    其完整代码如下:

    # x1*x2-x1*x2+x3
    import numpy as np
    import random
    
    DNA_SIZE = 24
    POP_SIZE = 100
    CROSSOVER_RATE = 0.8
    MUTATION_RATE = 0.015
    N_GENERATIONS = 100
    X_BOUND = [3.0, 5.0]  # x1
    Y_BOUND = [2.1, 6.7]  # x2
    Z_BOUND = [1.2, 9.6]  # x3
    
    
    def F(x, y, z):
        val = x * x - x * y + z
        return val
    
    
    def get_fitness(pop):
        x, y, z = translateDNA(pop)
        pred = F(x, y, z)
        return pred + 1e-3 - np.min(pred)  # 因为如果直接返回pred可能是负值,而我们在计算概率的时候不能为负值。
        # 要进行处理,np.min表示取最小,为最大的负数,可以使全部只变成正的;1e-3为了让float进行相除防止小数点后的数被省略
    
    
    def translateDNA(pop):  # pop表示种群矩阵,一行表示一个二进制编码表示的DNA,矩阵的行数为种群数目
        x_pop = pop[:, 0:DNA_SIZE]  # 取前DNA_SIZE个列表示x
        y_pop = pop[:, DNA_SIZE:DNA_SIZE * 2]  # 取中间DNA_SIZE个列表示y
        z_pop = pop[:, DNA_SIZE * 2:]  # 取后DNA_SIZE个列表示z
    
    
        '''pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1)'''  # 二进制--->十进制
        x = x_pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2 ** DNA_SIZE - 1) * (X_BOUND[1] - X_BOUND[0]) + X_BOUND[0]
        y = y_pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2 ** DNA_SIZE - 1) * (Y_BOUND[1] - Y_BOUND[0]) + Y_BOUND[0]
        z = z_pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2 ** DNA_SIZE - 1) * (Z_BOUND[1] - Z_BOUND[0]) + Z_BOUND[0]
        # print(x,z)
        return x, y, z
    
    
    def mutation(child, MUTATION_RATE=0.003):
        if np.random.rand() < MUTATION_RATE:  # 以MUTATION_RATE的概率进行变异
            mutate_point = np.random.randint(0, DNA_SIZE * 3)  # 随机产生一个实数,代表要变异基因的位置
            child[mutate_point] = child[mutate_point] ^ 1  # 将变异点的二进制为反转
    
    
    def crossover_and_mutation(pop, CROSSOVER_RATE=0.8):
        new_pop = []
        for father in pop:  # 遍历种群中的每一个个体,将该个体作为父亲
            child = father  # 孩子先得到父亲的全部基因(这里我把一串二进制串的那些01称为基因)
            if np.random.rand() < CROSSOVER_RATE:  # 产生子代时不是必然发生交叉,而是以一定的概率发生交叉
                mother = pop[np.random.randint(POP_SIZE)]  # 再种群中选择另一个个体,并将该个体作为母亲
                cross_points = np.random.randint(low=0, high=DNA_SIZE * 3)  # 随机产生交叉的点
                child[cross_points:] = mother[cross_points:]  # 孩子得到位于交叉点后的母亲的基因
            mutation(child)  # 每个后代有一定的机率发生变异
            new_pop.append(child)
    
        return new_pop
    
    
    def select(pop, fitness):  # nature selection wrt pop's fitness
        idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
                               p=fitness/fitness.sum())
        # print(idx)
        return pop[idx]
    
    
    def print_info(pop):
        fitness = get_fitness(pop)
        max_fitness_index = np.argmax(fitness)
        # print("max_fitness:", fitness[max_fitness_index])
        x, y, z = translateDNA(pop)
        print("(x, y, z):", (x[max_fitness_index], y[max_fitness_index], z[max_fitness_index]))
        x=x[max_fitness_index]
        y=y[max_fitness_index]
        z=z[max_fitness_index]
        print("函数极值:", F(x,y,z))
    
    
    if __name__ == "__main__":
        pop = np.random.randint(0, 2, size=(POP_SIZE, DNA_SIZE * 3))  # matrix (POP_SIZE, DNA_SIZE)
        # print(pop)
        for _ in range(N_GENERATIONS):  # 迭代N代
            x, y, z = translateDNA(pop)
            pop = np.array(crossover_and_mutation(pop, CROSSOVER_RATE))
            fitness = get_fitness(pop)
            pop = select(pop, fitness)  # 选择生成新的种群
    
        print_info(pop)
    
    
    

    参考文献:
    https://blog.csdn.net/yyyxxxsss/article/details/82464736
    https://morvanzhou.github.io/tutorials/machine-learning/evolutionary-algorithm/2-01-genetic-algorithm/
    https://www.cnblogs.com/lfri/p/12240355.html
    https://blog.csdn.net/zxxxxxxy/article/details/105287743?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.nonecase

    展开全文
  • 遗传算法应用 一、问题概述 求 y=10sin(5x)+7*|x-5|+10 最大值。 二、问题解决 1.产生初始种群 用随机数生成器分别产生8、16、32个随机数(由于给出的函数定义域是全体实数,所以我们先取一个小范围定义域,如 [0,10...

    遗传算法应用

    [1]、[2]、[3]在文章的最后用图像进行说明。

    一、问题概述

        求 y=10sin(5x)+7*|x-5|+10 最大值。函数图像如图:
           

    二、问题解决
    1.产生初始种群

      用随机数生成器分别产生8、16、32[1]随机数作为初始种群。
      由于给出的函数定义域是全体实数,且rand()函数只能生成[0,1]的随机数,我们取一个范围(如 [0,10])作为倍率,以产生大于1的数

      代码如下:

    %% 设置变量
    N=32;%初始群体大小,即产生N个在(a,b)范围内的随机数
    a=0;%自变量取值下界
    b=10;%自变量取值上界
    
    %% 1.产生初始群体
    initalGroup10=a+(b-a).*rand([N 1]);%初始群体,十进制编码
    2.编码与解码

      采用二进制编码,matlab默认编码位数。matlab中十进制转二进制函数dec2bin()默认会取最合适的编码位数。如果指定了编码位数,则多余部分会补零。
    需要注意的是,matlab中的dec2bin()只能转换整数部分,小数部分会被自动省去。下面链接介绍了一种能将十进制小数转换为二进制的方法。这里我们先用dec2bin()。
    matlab实现十进制小数转换为二进制

    3.确定适应度

       将初始种群带入目标函数,目标函数的值定为适应度。

        %% 2.求初始群体的适应度
        %适应度函数,即为目标函数
        adaptLevel = objectFun(initalGroup10);
        %将初始种群和适应度组合
        initalGroup = [initalGroup10 adaptLevel];

      其中,objectFun() 代码如下:

    function y = objectFun(x)
        y = 10.*sin(5.*x)+7.*abs(x-5)+10;
    end
    4.复制

      采用轮盘赌的方法确定复制个体。

        %% 3.确定复制个体
        %确定需要复制的个体的序号
        copyIndex=trochalDisk(initalGroup,N);
        %copyIndex返回的序号是对initalGroup排序后的序号,因此对适应度值升序排序
        sortrows(initalGroup,-2);
        %复制后的种群
        copyGroup10=[];
        for i=1:size(copyIndex)
            copyGroup10=[copyGroup10 initalGroup(copyIndex(i),1)];
        end

      其中,trochalDisk()是轮盘赌实现函数,代码如下:

    function index =trochalDisk(pk,N)
    %pk 轮盘每一份的值 
    %N  轮盘的份数
        %排序
        sortrows(pk,-2);
        pk=pk(:,2);
        %确定轮盘法则的区间trochal
        trochal=cumsum(pk(:));
        
        %随机产生N个数,并确定在轮盘的哪个区间
        tc=trochal(1)+(trochal(end)-trochal(1)).*rand([N 1]);
        index=[];
        for i=1:size(tc)
            t=find(trochal>=tc(i));
            index=[index;t(1)];
        end
    end
    5.交叉和变异

      需要依次确定交叉和变异中的几个随机。
    1)交叉中有三个随机:个体随机、概率可调、编码位置随机。

    • 随机数生成器确定发生交叉的个体序号。
    • 交叉概率为50%~80%[2],可以上下浮动。采用人为输入
    • 随机数生成器确定发生交叉的编码位置(产生一个或多个,这里以多个为例)。

    2)变异中有三个随机:个体随机、哪位变异随机、变异几位随机。

    • 随机数生成器确定发生变异的个体序号。
    • 变异概率为0.1%~1%[3],可以上下浮动。采用人为输入
    • 随机数生成器确定发生变异的编码位置(产生一个或多个,用随机数决定)。

      代码如下:

    crossProbility=0.07;%交叉概率50%~80%,可以上下浮动
    variationProbility=0.001;%变异概率0.1%~1%,可以上下浮动
    crossGroup = cross(crossProbility,copyGroup10);
    variationGroup = variation(variationProbility,crossGroup);

      其中,cross()是交叉实现函数,variation()是变异实现函数。

    function crossGroup = cross(probility,group)
    %crossGroup 交叉后的种群
    %probility 交叉概率
    %group 复制后的种群
    
    %确定几个个体发生交叉,让每两个相邻个体发生交叉,因此定为偶数个
    crossNumber=floor(probility*size(group,2));
    if rem(crossNumber,2)~=0
        crossNumber = crossNumber+1;
    end
    %随机产生个体交叉的序号
    crossIndex=floor(1+(size(group,2)-1).*rand([crossNumber 1]));
    %随机产生个体交叉的位置,范围:1-二进制长度
    group2=dec2bin(group);
    crossPos=floor(1+(size(group2,2)-1).*rand([crossNumber/2 1]));
    
    %交叉
    for i=1:2:crossNumber
    %下面这段代码和C语言中最基本的swamp()函数效果一样
        temp=group2(crossIndex(i),crossPos:end);
        group2(crossIndex(i),crossPos:end)=group2(crossIndex(i+1),crossPos:end);
        group2(crossIndex(i+1),crossPos:end)=temp;
    end
    %2进制变为10进制
    crossGroup=bin2dec(group2);
    end
    function variationGroup = variation(probility,group)
    %variationGroup 变异后的种群
    %probility 变异概率
    %group 变异后的种群
    
    %确定几个个体发生变异
    variationNumber=floor(probility*size(group,2));
    %随机产生个体变异的序号
    variationIndex=floor(1+(size(group,2)-1).*rand([variationNumber 1]));
    group2=dec2bin(group);
    %确定发生变异的位置的个数
    variationPosNum=floor(1+(size(group2,2)-1));
    %随机产生个体变异的位置,1-二进制长度
    variationPos=floor(1+(size(group2,2)-1).*rand([variationPosNum 1]));
    
    %变异
    for i=1:variationNumber
        for j=1:variationPosNum
            if group2(variationIndex(i),variationPos(j))==0
                group2(variationIndex(i),variationPos(j))='1';
            else
                group2(variationIndex(i),variationPos(j))='0';
            end
        end
    end
    
    variationGroup=bin2dec(group2);
    end
    6.适应度验算

      以本次迭代和上一次迭代适应度值改变量是否小于给定精度,决定是否终止循环。

    下面给出主函数

    clear,clc
    %% 设置变量
    N=32;%初始群体大小,即产生N个在(a,b)范围内的随机数
    a=0;%自变量取值下界
    b=10;%自变量取值上界
    esp=0.0001;%精度
    
    crossProbility=0.7;%交叉概率50%~80%,可以上下浮动
    variationProbility=0.005;%变异概率0.1%~1%,可以上下浮动
    
    maxX=[];
    maxAdapt=[];
    count=0;%记录迭代次数
    
    %% 1.编码,产生初始群体
    initalGroup10=a+(b-a).*rand([N 1]);%初始群体,十进制编码
    while true
        count=count+1;
        %% 2.求初始群体的适应度
        %适应度函数,即为目标函数
        adaptLevel=objectFun(initalGroup10);
        initalGroup=[initalGroup10 adaptLevel];
        
        %% 5.适应度验算
        %对initalGroup适应度值升序排序
        sortrows(initalGroup,-2);
        
        %画图用
        index=find(initalGroup(:,2)==max(initalGroup(:,2)));
        maxX=[maxX initalGroup(index(1),1)];
        %最大适应度,如果求的是目标函数的最小值,就保留最小值
        maxAdapt=[maxAdapt initalGroup(index(1),2)];
    
        if size(maxX,2)~=1
            if abs(maxX(end)-maxX(end-1))<esp
                break;
            end
        end
        
        %% 3.确定复制个体
        copyIndex=trochalDisk(initalGroup,N);
        copyGroup10=[];
        for i=1:size(copyIndex)
            copyGroup10=[copyGroup10 initalGroup(copyIndex(i),1)];
        end
        
        %% 4.交叉与变异
        %交叉中的随机:个体随机、交叉位置随机、概率可调
        %变异中的随机:个体随机、哪位变异随机、变异几位随机
        crossGroup = cross(crossProbility,copyGroup10,a,b,esp);
        variationGroup = variation(variationProbility,crossGroup',a,b,esp);
        
        %% 为下次循环准备
        %交叉和变异过程中难免会出大于给定范围的值
        %将所有超出范围的值设成最大值
        %因为下面还会给每个数加上小数部分,所以最大值取范围上界-1
        variationGroup(find(variationGroup>=(b-1)))=b-1;
        %前面说到dec2bin只会编码整数部分,所以我们在这里加一个小数部分。
        %可以尝试一下去掉会是什么样子
        initalGroup10=variationGroup+rand([N 1]);
    end

    下面是一些实验结果图和分析过程

      各个图参数如下:

    N=32;%初始群体大小,即产生N个在(a,b)范围内的随机数
    a=0;%自变量取值下界
    b=10;%自变量取值上界
    esp=0.0001;%精度
    crossProbility=0.7;%交叉概率50%~80%,可以上下浮动
    variationProbility=0.005;%变异概率0.1%~1%,可以上下浮动
       [1]:在图1所用参数的基础上,选择不同种群大小,发现种群越大,迭代次数越少,越容易能达到全局最优
       [2]:在图1所用参数的基础上,选择不同交叉概率。做了30多次实验。。。才疏学浅,实在发现不了任何关系。。。
       [3]:在图1所用参数的基础上,选择不同变异概率。同样,也没发现任何关系。。。

       [4]:在图1所用参数的基础上,采用十进制小数转换为二进制的编码方式。一定要提高变异概率

       采用含小数的二进制后,二进制编码位数会加长,需要提高变异概率。
       如 9.9283,dec2bin() 编码只考虑整数部分,编码结果是 ‘1001’ ,每次变异产生差为1的概率是1/16 = 6.25%;而考虑到小数后编码结果为 ‘10011110110110100’(整数部分占4位,小数部分占13位),每次变异产生差为1的概率是24/217 = 0.012%。
       综上,采用含小数的二进制后,变异概率为编码方式为dec2bin()的变异概率的100倍左右,才会产生比较好的结果。

    左图是变异概率为0.1%时的结果,右图是变异概率为10%时的结果。

    到这里这道题就结束啦!
    如果哪里有错误还请大家批评指正呀~~~
    或者有哪位发现了交叉概率和变异概率取值的意义,烦请评论区留言呀,不胜感激!

    展开全文
  • 遗传算法是根据自然界物竞天择,适者生存现象提出的一种随机搜索算法。首先进行编码,形成染色体,然后交配、变异等等。另外本代码也包括二进制十进制转换等等。
  • 针对高校排课问题的特点, 引入遗传算法来加以解决, 设计了多种改进方案, 包括: 十进制编码方案、初始种群生成方案、适应度函数设计方案、免疫策略、 自适应交叉概率和自适应变异概率设计方案. 仿真结果表明该算法...
  • ]分析遗传算法的二进制、实数、十进制编码策略实现方法,根据各编码的特点,设计 相应的改进遗传策略.以前馈神经网络权值优化问题为例,用计算机仿真实验的方法研究三种 编码策略对各遗传算法性能的影响.研究结果...
  • 遗传算法编码机制研究 其中讲的遗传算法的二进制编码和十进制编码的区别和比较
  • 遗传算法中的编码机制进行了研究,分析了二进制与十进制编码在搜索能力和保 持种群稳定性上的区别.得出的结论是在种群数目相同的情况下,二进制编码的搜索能力比十进制编码强;但二进制编码对变异操作不能保证种群的...
  • 在使用遗传算法的时候,需要对数据进制二进制编码,所以改的这个浮点数不同进制之间转换的一个代码 直接上代码 #二进制转化为十进制浮点数 def todecimal(n): ''' 把一个带小数的二进制数n转换成十进制 小数点...
  • 遗传算法

    2018-06-15 00:07:56
    遗传算法使用群体搜索技术,将种群代表一组问题解,通过对当前种群施加选择、交叉和变异等一系列遗传操作来产生...遗传编码:把优化变量(实数值或者序列顺序)转化为基因的组合表示形式,如二进制编码、十进制编码 ...
  • 最优指标的选取同十进制编码遗传算法的PID整定。遗传算法中使用的样本个数为Size=30,交叉概率和变异概率分别为:Pc =0.60,Mu =0.001-[1:1:Size]×0.001/Size。参数kP的取值范围为[0,20],ki,kD的取值范围为[0...
  • 标准遗传算法,解决y=x1^2+x2^2+x3^2的最小值,每个变量位二进制编码
  • 遗传算法求解优化问题 ...1.1.2十进制编码 1.2初始化群体的设定 1.3适应度函数的设定 1.4遗传操作设计 1.4.1选择 1.4.2交叉 1.4.3变异 1.5控制参数设定 2.遗传算法的验证 2.1参数编码 2.2初始化群体的
  • 遗传算法求解TSP问题

    2019-09-23 23:50:51
    一、导论 演化算法是一类模拟自然界遗传进化规律的仿生学算法,它不是一个具体的算法,而是一个算法簇。遗传算法是演化算法的一个分支,由于遗传算法的...(2)采用十进制编码:直接用城市的编号进行编码,染色体{...
  • 人工智能-遗传算法

    2021-05-16 10:25:25
    1.编码 采用的是二进制编码,用一个二进制编码序列表示一条染色体。..., (设二进制编码对应的十进制整数为x) 解码代码如下: double decoding(int *a) //解码 { double x = 0; for (int i..
  • 用Matlab编写的遗传算法的程序

    热门讨论 2010-07-11 19:43:16
    用Matlab编写的遗传算法的程序: (用matlab编写的十进制遗传算法程序)实数编码遗传算法; 基于Matlab的函数优化遗传算法程序; 基于实数编码遗传算法的函数极植优化程序; 。。。
  • 应用一种基于自然选择和生物遗传机理的全局搜索学习算法──遗传算法的思想和方法,解决最优决策中一类仅含权值约束的最优化问题.采用十进制编码,给出了具体的求解步骤和编码方法.
  • 在给定的多关节焊接机器入焊接点中插入点,对这些点的坐标统一进行十进制编码,应用遗传算法进行轨迹规划,寻找三维空间下的最优轨迹。通过仿真,验证了该算法的可行性。与传统的优化方法相比,具有较强的鲁棒性。
  • 文章目录二进制7.1 标准遗传算法1 GA简介2 生物学背景3 标准遗传算法(1)编码(2)初始种群的生成 二进制 将十进制数13化成二进制数 7.1 标准遗传算法 1 GA简介 是进化计算技术中的一种 进化计算起源于1960s,是...
  • 为改进网格计算中任务调度的低效问题,采用十进制的实数编码规则产生初始抗体群,由免疫遗传算法经过克隆和变异算子生成资源集合中的蚁群信息素,进而利用蚁群算法的并行性展开全局搜索,通过CloudSim仿真平台进行模拟,...
  • 遗传算法来源和计算步骤1来源2步骤 模拟自然进化遗传-变异-选择适者生存优胜劣汰编码自然进化初始种群适应度计算人工进化如GA选择交叉变异新种群的生成否是否达到目标是解决实际问题二关键操作1适应度计算及标定2...
  • # 二进制基因编码十进制 def conv_2_10(x): val = 0 for v in range(len(x)): if x[-1*(v+1)] == 1: val += 2 ** v return val # 十进制转二进制基因编码 def conv_10_2(x): ...
  • 并且研究了利用十进制编码遗传算法及其具体的遗传操作过程,实现了滤波器参数λ的优化自整定,从而避免了二进制编码所导致的影射误差。仿真结果表明,对于在控制过程中过程模型变化或过程模型与预估模型失配时,...
  • 遗传算法与差分进化算法总结比较

    万次阅读 2017-01-15 09:25:18
    遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法,它是模拟基因重 组与进化的自然过程,把待解决问题的参数编成二进制码或十进制码(也可编成其他进制码)即基因,若干基因组成一个染色体(个体),...

空空如也

空空如也

1 2 3 4
收藏数 78
精华内容 31
关键字:

遗传算法十进制编码