遗传算法 订阅
遗传算法(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] 
收起全文
精华内容
下载资源
问答
  • 遗传算法

    万次阅读 多人点赞 2019-04-06 21:41:47
    使用遗传算法求解多峰函数的最大值,是我的一项课程作业,做完之后,顺便把文档整理出来做个记录。全部内容如下: 1、问题描述 编程实现遗传算法,并求解多峰函数的最大值。多峰函数的表达式如下所示: 用MATLAB...

    使用遗传算法求解多峰函数的最大值,是我的一项课程作业,做完之后,顺便把文档整理出来做个记录。全部内容如下:

    1、问题描述

    编程实现遗传算法,并求解多峰函数的最大值。多峰函数的表达式如下所示:
    在这里插入图片描述
    用MATLAB做出函数的图像如下:
    在这里插入图片描述

    2、算法描述及实现

    2.1、遗传算法概述

    遗传算法(GA,Genetic Algorithm),也称为进化算法。遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。其主要特点是直接对结构对象进行操作,因此不同于其他求解最优解的算法,遗传算法不存在求导和对函数连续性的限定,采用概率化的寻优方法,不需要确定的规则就能自动获取和指导优化的搜索空间,自适应地调整搜索方向。

    以上是对遗传算法相对抽象的总结,为了更具体形象的解释遗传算法的一般原理,我们首先介绍一些生物学上的概念

    ①种群:不同生物个体形成的群体,生物的进化以群体的形式进行,这样的一个群体称为种群;

    ②个体:组成种群的单个生物;

    ③基因:带有遗传信息的DNA片段,可以通俗的将基因理解为一段信息,这段信息决定的生物个体的性状;

    ④表现型:根据基因形成的个体的外部表现;

    ⑤适应度:生物个体对于生存环境的适应程度,越适应那么其得以存活和繁衍的概率就越大;

    ⑥遗传:通过繁殖过程,子代将从父母双方各获取一部分基因,形成新的自己的基因,这个过程中,会发生基因的复制、交叉,也会以较低的概率发生基因突变;

    ⑦自然选择:物竞天择,适者生存的自然淘汰机制。具体为对环境适应度高的个体参与繁殖的机会比较多,后代就会越来越多。适应度低的个体参与繁殖的机会比较少,后代就会越来越少;

    ⑧进化:种群通过代际繁衍不断适应生存环境的过程,在这个过程中,以对外界环境的适应度为评判标准,生物的性状不断得到改良。

    了解了这些术语的含义,我们就可以进一步说说生物进化的过程了。由于自然选择是客观存在的,即生物只能改变自己去适应环境,那么在自然选择的过程中,适应度低的个体会被淘汰,适应度高的个体被保留,高适应度的父体与母体又有更高的概率繁衍出适应度高的子代,因此在一代又一代的繁衍之后,高适应度的个体在种群中所占的比例越来越大,种群就这样完成了进化。

    现在我们要参考生物进化的过程来设计算法解决求最优解的问题。对此,遗传算法的思路是,将要解决的问题模拟成一个生物进化的过程,通过进化来寻找最优解。以我们题目中寻找多峰函数的最大值这个问题为例

    将(x, y)这一可能的解作为一个个体;将多峰函数的函数值f(x, y)作为个体的适应度;对(x, y)进行编码作为个体的基因;以适应度为标准不断筛选生物个体;通过遗传算子(如复制、交叉、变异等)不断产生下一代。如此不断循环迭代,完成进化。最终,根据设定的迭代次数,可得到最后一代种群,该种群中的个体适应度都较高,而多峰函数的最大值就有比较大的概率存在于这一群解中,以种群中适应度最高的个体作为问题的解,则可以说该解有比较高的概率就是我们希望求得的最优解。

    文字述说终究还是不如图表好理解,因此还是看图吧(下图将本题与自然遗传联系了起来):
    在这里插入图片描述
    通过以上描述,我们不难看出,遗传算法不能保证一定能求得最优解,而只能以一定的概率求最优解。但是使用遗传算法时,我们可以不用关心具体如何去找最优解,要做的只是简单的否定一些表现不好的个体。这一优点也是遗传算法能够取得广泛应用的原因之一。

    2.2、算法的流程

    通过上文的阐述,对于如何模拟自然进化来求题中多峰函数的最优解已经比较明晰了。这里我将列出遗传算法的主要步骤,并一一解析:

    第一步:随机产生一个种群,作为问题的初代解(通常,初代解可能与最优解相差较大,这是可以容忍的,只要保证初代解是随机产生的,以确保个体基因的多样性即可);

    第二步:寻找一种合适的编码方案对种群中的个体进行编码,可以选择如浮点数编码或二进制编码等常用编码方案(需要指出的是,不同的编码方案直接影响后续遗传算子的实现细节);

    第三步:以多峰函数的函数值 作为个体的适应度,计算种群中每个个体的适应度(算出的适应度将为后续的个体选择提供依据);

    第四步:根据适应度的高低选择参与繁衍的父体与母体,选择的原则是适应度越高的个体越可能被选中(以此不断淘汰适应度低的个体);

    第五步:对被选出的父体与母体执行遗传操作,即复制父体与母体的基因,并采用交叉、变异等算子产生出子代(在较大程度保留优秀基因的基础上,变异增加了基因的多样性,从而提高找到最优解的概率);

    第六步:根据一定的准则判断是继续执行算法,还是找出所有子代中适应度最高个体作为解返回并结束程序(判断的准则可以是设定的解的阈值、指定的迭代次数等)。
    在这里插入图片描述

    2.3、算法的编码实现

    2.3.1、编码

    本文采用的是二进制编码方式,这种编码方式编解码过程简单易行,相应的交叉算子、变异算子等操作用位运算即可实现。当然,它也有一定的缺点,比如连续性不够强。为保证求解的精度,本文使用14个bit为 编码,使用11个bit为 编码,两者组合成25个bit的最终结果。不难算出,该方式的编码精度可达千分位。具体的编码操作可总结为,将 或 的取值区间映射到0~2n-1这一整数范围,其中n表示编码位数, 或 在其取值区间的某点,相应的映射到整数区间中的某点,改点即为 或 的基因编码。程序如下:

    /*
        基因编码
        gene1       输入型参数,待编码的基因段1
        gene2       输入型参数,待编码的基因段2
        gene_code   输出型参数,基因编码
    
        返回值:当输入的基因不符合要求时返回false,否则返回true
    */
    static bool gene_encode(const double gene1, const double gene2, unsigned int *gene_code)
    {
        /* 判断基因是否合法 */
        if (!is_gene_legal(gene1, gene2))
            return false;
    
        /* 若基因合法则对其进行编码 */
        unsigned int gene1_code = (gene1 - GENE1_RANGE_LEFT) * (GENE1_CODE_MAX - 1) / (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT);
        unsigned int gene2_code = (gene2 - GENE2_RANGE_LEFT) * (GENE2_CODE_MAX - 1) / (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT);
        
        /* 组合基因片段 */
        *gene_code = (gene1_code << 11) | gene2_code;
    
        return true;
    }
    

    2.3.2、解码

    解码是编码的逆过程,无需赘述,程序如下:

    /*
        基因解码
        gene_code   输入型参数,基因编码
        gene1       输出型参数,解码后的基因段1
        gene2       输出型参数,解码后的基因段2
    
        返回值:当输入的基因编码不符合要求时返回false,否则返回true
    */
    static bool gene_decode(const unsigned int gene_code, double *gene1, double *gene2)
    {
        /* 判断基因编码是否合法 */
        if (!is_gene_code_legal(gene_code))
            return false;
    
        /* 若基因编码合法则对其进行解码 */
        unsigned int gene1_code = GET_GENE1_CODE(gene_code);
        unsigned int gene2_code = GET_GENE2_CODE(gene_code);
    
        *gene1 = (double)gene1_code * (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT) / (GENE1_CODE_MAX - 1) + GENE1_RANGE_LEFT;
        *gene2 = (double)gene2_code * (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT) / (GENE2_CODE_MAX - 1) + GENE2_RANGE_LEFT;
    
        return true;
    }
    

    2.3.3、计算适应度

    适应度函数也称评价函数,通常用于区分群体中个体好坏的标准。适应度高的,也就是优秀的个体有更大的几率参与繁衍,遗传自己的基因。一般的,适应度函数根据目标函数来确定,有时候直接将目标函数值作为适应度。这里,考虑到待求解的多峰函数,尖峰分布密集而且峰的直径很窄,这不利于遗传算法的收敛,因此本文不直接将多峰函数值作为适应度,而是利用对数函数将多峰函数进行平缓,并将平缓后的函数值作为目标函数。具体做法是,将多峰函数进行两次求对数,因此,多峰函数与适应度的关系可如下表示:
    在这里插入图片描述
    用MATLAB做出适应度函数图像如下:
    在这里插入图片描述
    对比前文中的图不难看出,图像得到了有效的平缓,同时不同峰之间也保持着一定的高低之别。值得一提的是,这里更主要的是给出优化遗传算法的一个思路,即可以在适应度函数上做文章。本题的适应度函数只是对多峰函数本身做了一个简单的变换,读者不妨思考一下,就本题而言有没有什么非常好的适应度函数。

    据上文所述,适应度求值函数如下:

    /*
        多峰函数:z = 21.5 + x *sin(4 * 3.1415926 * x) + y * sin(20 * 3.1415926 * y)
        适 应 度:log(log(z))
        约    束:-3.0 <= x <= 12.1; 4.1 <= y <= 5.8
        精    度:精确到千分位
    */
    double get_fitness(const double x, const double y)
    {
        return log(log(21.5 + x * sin(4 * PI * x) + y * sin(20 * PI * y)));
    }
    

    2.3.4、选择算子

    本文的选择算法采用了非常常用的“轮盘赌算法”,赌盘算法的原理非常简单明了。创建赌盘时,我们将种群中所有个体的适应度求和,不妨将得到的结果称为总和适应度。然后,将每个个体的适应度除以总和适应度,然后将得到的商逐个累加,每加一次就得到赌盘的一个边界,累加完成后总和为1。如下的饼状图可以更形象的表明赌盘的原理:
    在这里插入图片描述
    由上文所述,赌盘创建函数可如下编写:

    /*
        创建赌盘
        ga      遗传算法器指针
    */
    static void create_roulette(GA *ga)
    {
        /* 计算赌盘中的概率 */
        ga->roulette[0] = ga->fitness[0] / ga->sum_fitness;
    
        for (int num = 1; num < ga->population_num - 1; num++)
        {
            ga->roulette[num] = ga->roulette[num - 1] + ga->fitness[num] / ga->sum_fitness;
        }
    
        ga->roulette[ga->population_num - 1] = 1.0;
    }
    

    再回到选择算子,选择算子需要赌盘作为基础,其运行时,会产生一个0到1的随机数,然后在赌盘中找到该数所在的区间,这个区间对应的个体即为被选中的个体。因此,适应度越高的个体被选中的几率越大,这是合理的。当然,也存在较小的概率选出适应度较低的个体,为了避免这种情况,本文引入了竞争机制,即一次选择的过程选出2个个体,再取其中适应度较高的那个个体,具体的程序如下:

    /*
        基因选择函数
        ga      遗传算法器指针
        返回值:返回使用轮盘赌的方式选出的个体(编号)
        说  明:选择策略为轮盘赌+随机竞争
    */
    static unsigned int select(GA *ga)
    {
        unsigned int index1 = 0, index2 = 0;
    
        /* 产生一个[0.0, 1.0]之间的浮点数 */
        double selector1 = rand() * 1.0 / RAND_MAX;
        double selector2 = rand() * 1.0 / RAND_MAX;
    
        /* 找出被选中的个体的索引 */
        for (; selector1 > ga->roulette[index1]; index1++);
        for (; selector2 > ga->roulette[index2]; index2++);
    
        return (ga->fitness[index1] > ga->fitness[index2] ? index1 : index2);
    }
    

    2.3.5、交叉算子

    遗传算法的交叉操作实质上是按某种方式交换父体和母体的部分基因,常见的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉及算术交叉等。本文选用两点交叉法,实现过程既不复杂,也有较好的随机性,该方法可由下图示意:
    在这里插入图片描述
    图中虚线指出的两个交叉点是随机产生的。具体程序如下:

    /*
        交叉函数
        ga          遗传算法器指针
        one         输出型参数,待交叉基因
        another     输出型参数,待交叉基因
        说明:
        1.对传入的基因编码执行两点交叉操作
    */
    static void cross(GA *ga, unsigned int *one, unsigned int *another)
    {
        /* 1.随机产生两个交叉点的位置 */
        unsigned char pos1 = rand() % GENE_CODE_LENGTH + 1;
        unsigned char pos2 = rand() % GENE_CODE_LENGTH + 1;
        unsigned char min_pos = min(pos1, pos2);
        unsigned char max_pos = max(pos1, pos2);
    
        /* 2.截出需要交换的基因段 */
        unsigned int one_gene_seg = get_bits(*one, min_pos, max_pos) << (min_pos - 1);
        unsigned int another_gene_seg = get_bits(*another, min_pos, max_pos) << (min_pos - 1);
        unsigned int mask = ~(get_bits(~(0U), min_pos, max_pos) << (min_pos - 1));
    
        /* 3.执行交叉操作 */
        *one = (*one & mask) | another_gene_seg;
        *another = (*another & mask) | one_gene_seg;
    }
    

    2.3.6、变异算子

    在自然界中,基因变异可以增加个体的多样性,这对于遗传算法来说是增加了个体的随机性,可以增加找到最优解的概率。本文采用的变异算子所做的操作是随机选择基因的某一位进行反转,程序如下:

    /*
        变异函数
        gene_code       输入型参数
        说明:
        1.对传入的基因编码执行变异操作
        2.随机选择基因编码中的一位做反转操作
    */
    static void mutate(unsigned int *gene_code)
    {
        unsigned int mutate_bit = 1 << (rand() % GENE_CODE_LENGTH);
        *gene_code ^= mutate_bit;
    }
    

    2.3.7、繁殖函数及进化函数

    遗传算法的主要算子都在上文中分析过了,下面要做的就是根据遗传算法的流程将这些算子整合起来以实现算法功能。在本文中,这其中涉及到两个关键的函数,即繁殖函数和进化函数。繁殖函数包括基因的复制、交叉及变异,同时本文还采用了子代竞争策略,即父代产生的两个子代个体仅保留适应度最高的,程序如下:

    /*
        繁殖函数
        ga       遗传算法器指针
        father   从种群中选出的父体
        mother   从种群中选出的母体
        返回值:  适应度最高的子代的基因编码
        说明: 
        1.一对父体与母体将繁殖出一对子代
        2.选择出适应性更好的子代返回
    */
    static unsigned int inherit(GA *ga, unsigned int father, unsigned int mother)
    {
        unsigned int son1 = ga->gene_code[father];
        unsigned int son2 = ga->gene_code[mother];
    
        /* 1.交叉 */
        cross(ga, &son1, &son2);
    
        /* 2.变异 */
        mutate(&son1);
        mutate(&son2);
    
        /* 3.子代竞争 */
        double son1_gene1, son1_gene2, son2_gene1, son2_gene2;
        gene_decode(son1, &son1_gene1, &son1_gene2);
        gene_decode(son2, &son2_gene1, &son2_gene2);
    
        return (ga->get_fitness(son1_gene1, son1_gene2) > ga->get_fitness(son2_gene1, son2_gene2)) ? son1 : son2;
    }
    

    进化函数则实现了遗传算法的一次完整的迭代过程,根据上文给出的遗传算法流程图,不难进行如下编码:

    /*
        进化函数
        ga      遗传算法器指针
    */
    static void evolve(GA *ga)
    {
        /* 1.申请暂存子代基因编码的内存 */
        unsigned int *descendants = (unsigned int *)calloc(ga->population_num, sizeof(unsigned int));
        
        /* 2.精英保留(将上一代中适应度最高的个体的基因编码保留) */
        descendants[0] = ga->gene_code[ga->best_individual];
        
        /* 3.选择合适的父体与母体 */
        unsigned int father = select(ga);
        unsigned int mother = select(ga);
    
        /* 4.繁殖(包含交叉与变异) */
        for (int num = 1; num < ga->population_num; num++)
            descendants[num] = inherit(ga, father, mother);
    
        /* 5.将子代记录到ga中并进行基因解码(使新一代的基因编码与基因对应) */
        for (int num = 0; num < ga->population_num; num++)
        {
            ga->gene_code[num] = descendants[num];
            gene_decode(ga->gene_code[num], &ga->gene[num].gene1, &ga->gene[num].gene2);
        }
        
        /* 5.更新种群适应度 */
        fit(ga);
        
        /* 6.更新赌盘 */
        create_roulette(ga);
    
        /* 7.释放之前申请的空间 */
        free(descendants);
    }
    

    3、运行结果及分析

    至此,本文已经给出了一个遗传算法的C语言实现的所有关键程序。下面就调用编写的遗传算法进行测试。本文将创建含有100个个体的种群,并进行100代迭代以求解多峰函数的最大值,一次完整的调用本文实现的遗传算法的程序如下所示:

    /* 创建遗传算法器 */
    GA *ga = create_ga(get_fitness, 100);
    
    /* 初始化遗传算法器 */
    ga->init(ga);
    
    /*迭代100代*/
    for (int i = 0; i < 100; i++)
    ga->evolve(ga);
    
    /*销毁遗传算法器*/
    delete_ga(ga);
    

    经多次调用测试,算法执行的结果较为稳定,所得的多峰函数最大值大多在38以上,多次运行结果中最好的解为38.849744,对应的坐标为(11.625331, 5.725256)。将迭代求得的最大值用MATLAB作图如下:
    在这里插入图片描述
    为验证是否找到了最优解,用MATLAB遍历求出该多峰函数在给定定义域内的最大值为38.8501,与本文求出的结果相差0.000356,可见本文实现的遗传算法表现还不算太差。

    文中给出的程序比较散,这里给出完整程序的下载链接

    展开全文
  • 遗传算法 遗传算法 遗传算法 遗传算法 遗传遗传算法算法
  • 遗传算法详解 附python代码实现

    万次阅读 多人点赞 2019-06-10 11:14:59
    遗传算法 遗传算法是用于解决最优化问题的一种搜索算法。从名字来看,遗传算法借用了生物学里达尔文的进化理论:”适者生存,不适者淘汰“,将该理论以算法的形式表现出来就是遗传算法的过程。 问题引入 上面提到...

    遗传算法

    遗传算法是用于解决最优化问题的一种搜索算法。从名字来看,遗传算法借用了生物学里达尔文的进化理论:”适者生存,不适者淘汰“,将该理论以算法的形式表现出来就是遗传算法的过程。

    问题引入

    上面提到遗传算法是用来解决最优化问题的,下面我将以求二元函数:

    def F(x, y):
    	return 3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)
    

    x ∈ [ − 3 , 3 ] , y ∈ [ − 3 , 3 ] x\in[-3, 3], y\in[-3, 3] x[3,3],y[3,3]范围里的最大值为例子来详细讲解遗传算法的每一步。该函数的图像如下图:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    通过旋转视角可以发现,函数在这个局部的最大值大概在当 x ≈ 0 , y ≈ 1.5 x \approx 0,y\approx1.5 x0,y1.5时,函数值取得最大值,这里的 x , y x,y x,y的取值就是我们最后要得到的结果。

    算法详解

    先直观看一下算法过程:

    寻找最小值:

    在这里插入图片描述

    寻找最大值
    在这里插入图片描述

    首先我们生成了200个随机的(x,y)对,将(x, y)坐标对带入要求解的函数F(x,y)中,根据适者生存,我们定义使得函数值F(x,y)越大的(x,y)对越适合环境,从而这些适应环境的(x,y)对更有可能被保留下来,而那些不适应该环境的(x,y)则有很大几率被淘汰,保留下来的点经过繁殖产生新的点,如此进化下去最后留下的大部分点都是试应环境的点,即在最高点附近。下图为算法执行结果,和上面的分析 x ≈ 0 , y ≈ 1.5 x \approx 0,y\approx1.5 x0,y1.5相近。

    在这里插入图片描述

    种群和个体的概念

    遗传算法启发自进化理论,而我们知道进化是由种群为单位的,种群是什么呢?维基百科上解释为:在生物学上,是在一定空间范围内同时生活着的同种生物的全部个体。显然要想理解种群的概念,又先得理解个体的概念,在遗传算法里,个体通常为某个问题的一个解,并且该解在计算机中被编码为一个向量表示! 我们的例子中要求最大值,所以该问题的解为一组可能的 ( x , y ) (x, y) (x,y)的取值。比如 ( x = 2.1 , y = 0.8 ) , ( x = − 1.5 , y = 2.3 ) . . . (x=2.1,y=0.8), (x=-1.5, y=2.3)... (x=2.1,y=0.8),(x=1.5,y=2.3)...就是求最大值问题的一个可能解,也就是遗传算法里的个体,把这样的一组一组的可能解的集合就叫做种群 ,比如在这个问题中设置100个这样的 x , y x,y x,y的可能的取值对,这100个个体就构成了种群。

    编码、解码与染色体的概念

    在上面个体概念里提到个体(也就是一组可能解)在计算机程序中被编码为一个向量表示,而在我们这个问题中,个体是 x , y x,y x,y的取值,是两个实数,所以问题就可以转化为如何将实数编码为一个向量表示,可能有些朋友有疑惑,实数在计算机里不是可以直接存储吗,为什么需要编码呢?这里编码是为了后续操作(交叉和变异)的方便。实数如何编码为向量这个问题找了很多博客,写的都是很不清楚,看了莫烦python的教学代码,终于明白了一种实数编码、解码的方式。


    生物的DNA有四种碱基对,分别是ACGT,DNA的编码可以看作是DNA上碱基对的不同排列,不同的排列使得基因的表现出来的性状也不同(如单眼皮双眼皮)。在计算机中,我们可以模仿这种编码,但是碱基对的种类只有两种,分别是0,1。只要我们能够将不同的实数表示成不同的0,1二进制串表示就完成了编码,也就是说其实我们并不需要去了解一个实数对应的二进制具体是多少,我们只需要保证有一个映射
    y = f ( x ) , x   i s   d e c i m a l   s y s t e m , y   i s   b i n a r y   s y s t e m y=f(x), x \ is\ decimal \ system, y \ is \ binary\ system y=f(x),x is decimal system,y is binary system
    能够将十进制的数编码为二进制即可,至于这个映射是什么,其实可以不必关心。将个体(可能解)编码后的二进制串叫做染色体染色体(或者有人叫DNA)就是个体(可能解)的二进制编码表示。为什么可以不必关心映射 f ( x ) f(x) f(x)呢?因为其实我们在程序中操纵的都是二进制串,而二进制串生成时可以随机生成,如:

    #pop表示种群矩阵,一行表示一个二进制编码表示的DNA,矩阵的行数为种群数目,DNA_SIZE为编码长度,不理解乘2的看后文
    pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE*2)) #matrix (POP_SIZE, DNA_SIZE*2)
    

    实际上是没有需求需要将一个十进制数转化为一个二进制数,而在最后我们肯定要将编码后的二进制串转换为我们理解的十进制串,所以我们需要的是 y = f ( x ) y=f(x) y=f(x)逆映射,也就是将二进制转化为十进制,这个过程叫做解码(很重要,感觉初学者不容易理解),理解了解码编码还难吗?先看具体的解码过程如下。

    首先我们限制二进制串的长度为10(长度自己指定即可,越长精度越高),例如我们有一个二进制串(在程序中用数组存储即可)
    [ 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 ] [0,1,0,1,1,1,0,1,0,1] [0,1,0,1,1,1,0,1,0,1]
    ,这个二进制串如何转化为实数呢?不要忘记我们的 x , y ∈ [ − 3 , 3 ] x,y\in[-3,3] x,y[3,3]这个限制,我们目标是求一个逆映射将这个二进制串映射到 x , y ∈ [ − 3 , 3 ] x,y\in[-3,3] x,y[3,3]即可,为了更一般化我们将 x , y x,y x,y的取值范围用一个变量表示,在程序中可以用python语言写到:

    X_BOUND = [-3, 3] #x取值范围
    Y_BOUND = [-3, 3] #y取值范围
    

    为将二进制串映射到指定范围,首先先将二进制串按权展开,将二进制数转化为十进制数,我们有 0 ∗ 2 9 + 1 ∗ 2 8 + 0 ∗ 2 7 + . . . + 0 ∗ 2 0 + 1 ∗ 2 0 = 373 0*2^9+1*2^8+0*2^7+...+0*2^0+1*2^0=373 029+128+027+...+020+120=373,然后将转换后的实数压缩到 [ 0 , 1 ] [0,1] [0,1]之间的一个小数 373 / ( 2 10 − 1 ) ≈ 0.36461388074 373 / (2^{10}-1) \approx 0.36461388074 373/21010.36461388074,通过以上这些步骤所有二进制串表示都可以转换为 [ 0 , 1 ] [0,1] [0,1]之间的小数,现在只需要将 [ 0 , 1 ] [0,1] [0,1] 区间内的数映射到我们要的区间即可。假设区间 [ 0 , 1 ] [0,1] [0,1]内的数称为num,转换在python语言中可以写成:

    #X_BOUND,Y_BOUND是x,y的取值范围 X_BOUND = [-3, 3], Y_BOUND = [-3, 3],
    x_ = num * (X_BOUND[1] - X_BOUND[0]) + X_BOUND[0] #映射为x范围内的数
    y_ = num * (Y_BOUND[1] - Y_BOUND[0]) + Y_BOUND[0] #映射为y范围内的数
    

    通过以上这些标记为蓝色的步骤我们完成了将一个二进制串映射到指定范围内的任务(解码)。

    现在再来看看编码过程。不难看出上面我们的DNA(二进制串)长为10,10位二进制可以表示 2 10 2^{10} 210种不同的状态,可以看成是将最后要转化为的十进制区间 x , y ∈ [ − 3 , 3 ] x,y\in[-3,3] x,y[3,3](下面讨论都时转化到这个区间)切分成 2 10 2^{10} 210,显而易见,如果我们增加二进制串的长度,那么我们对区间的切分可以更加精细,转化后的十进制解也更加精确。例如,十位二进制全1按权展开为1023,最后映射到[-3, 3]区间时为3,而1111111110(前面9个1)按权展开为1022, 1022 / ( 2 10 − 1 ) ≈ 0.999022 1022/(2^{10}-1) \approx 0.999022 1022/(2101)0.999022 0.999022 ∗ ( 3 − ( − 3 ) ) + ( − 3 ) ≈ 2.994134 0.999022*(3 - (-3)) + (-3)\approx2.994134 0.999022(3(3))+(3)2.994134;如果我们将实数编码为12位二进制,111111111111(12个1)最后转化为3,而111111111110(前面11个1)按权展开为4094, 4094 / ( 2 12 − 1 = 4095 ) ≈ 0.999756 4094/(2^{12}-1=4095)\approx0.999756 4094/(2121=4095)0.999756 0.999755 ∗ ( 3 − ( − 3 ) ) + ( − 3 ) ≈ 2.998534 0.999755*(3-(-3))+(-3)\approx2.998534 0.999755(3(3))+(3)2.998534;而 3 − 2.994134 = 0.005866 3-2.994134=0.005866 32.994134=0.005866 3 − 2.998534 = 0.001466 3-2.998534=0.001466 32.998534=0.001466,可以看出用10位二进制编码划分区间后,每个二进制状态改变对应的实数大约改变0.005866,而用12位二进制编码这个数字下降到0.001466,所以DNA长度越长,解码为10进制的实数越精确。

    以下为解码过程的python代码:

    这里我设置DNA_SIZE=24(一个实数DNA长度),两个实数 x , y x,y x,y一共用48位二进制编码,我同时将x和y编码到同一个48位的二进制串里,每一个变量用24位表示,奇数24列为x的编码表示,偶数24列为y的编码表示。

    def translateDNA(pop):#pop表示种群矩阵,一行表示一个二进制编码表示的DNA,矩阵的行数为种群数目
    	x_pop = pop[:,1::2]#奇数列表示X
    	y_pop = pop[:,::2] #偶数列表示y
        #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]
        return x,y
    

    适应度和选择

    我们已经得到了一个种群,现在要根据适者生存规则把优秀的个体保存下来,同时淘汰掉那些不适应环境的个体。现在摆在我们面前的问题是如何评价一个个体对环境的适应度?在我们的求最大值的问题中可以直接用可能解(个体)对应的函数的函数值的大小来评估,这样可能解对应的函数值越大越有可能被保留下来,以求解上面定义的函数F的最大值为例,python代码如下:

    def get_fitness(pop): 
        x,y = translateDNA(pop)
    	pred = F(x, y)
    	return (pred - np.min(pred)) + 1e-3 #减去最小的适应度是为了防止适应度出现负数,通过这一步fitness的范围为[0, np.max(pred)-np.min(pred)],最后在加上一个很小的数防止出现为0的适应度
    

    pred是将可能解带入函数F中得到的预测值,因为后面的选择过程需要根据个体适应度确定每个个体被保留下来的概率,而概率不能是负值,所以减去预测中的最小值把适应度值的最小区间提升到从0开始,但是如果适应度为0,其对应的概率也为0,表示该个体不可能在选择中保留下来,这不符合算法思想,遗传算法不绝对否定谁也不绝对肯定谁,所以最后加上了一个很小的正数。

    有了求最大值的适应度函数求最小值适应度函数也就容易了,python代码如下:

    def get_fitness(pop): 
    	x,y = translateDNA(pop)
    	pred = F(x, y)
    	return -(pred - np.max(pred)) + 1e-3
    

    因为根据适者生存规则在求最小值问题上,函数值越小的可能解对应的适应度应该越大,同时适应度也不能为负值,先将适应度减去最大预测值,将适应度可能取值区间压缩为 [ n p . m i n ( p r e d ) − n p . m a x ( p r e d ) , 0 ] [np.min(pred)-np.max(pred), 0] [np.min(pred)np.max(pred),0],然后添加个负号将适应度变为正数,同理为了不出现0,最后在加上一个很小的正数。

    有了评估的适应度函数,下面可以根据适者生存法则将优秀者保留下来了。选择则是根据新个体的适应度进行,但同时不意味着完全以适应度高低为导向(选择top k个适应度最高的个体,容易陷入局部最优解),因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解,我们称之为早熟。作为折中,遗传算法依据原则:适应度越高,被选择的机会越高,而适应度低的,被选择的机会就低。 在python中可以写做:

    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()) )
        return pop[idx]
    

    不熟悉numpy的朋友可以查阅一下这个函数,主要是使用了choice里的最后一个参数p,参数p描述了从np.arange(POP_SIZE)里选择每一个元素的概率,概率越高约有可能被选中,最后返回被选中的个体即可。

    交叉、变异

    通过选择我们得到了当前看来“还不错的基因”,但是这并不是最好的基因,我们需要通过繁殖后代(包含有交叉+变异过程)来产生比当前更好的基因,但是繁殖后代并不能保证每个后代个体的基因都比上一代优秀,这时需要继续通过选择过程来让试应环境的个体保留下来,从而完成进化,不断迭代上面这个过程种群中的个体就会一步一步地进化。

    具体地繁殖后代过程包括交叉和变异两步。交叉是指每一个个体是由父亲和母亲两个个体繁殖产生,子代个体的DNA(二进制串)获得了一半父亲的DNA,一半母亲的DNA,但是这里的一半并不是真正的一半,这个位置叫做交配点,是随机产生的,可以是染色体的任意位置。通过交叉子代获得了一半来自父亲一半来自母亲的DNA,但是子代自身可能发生变异,使得其DNA即不来自父亲,也不来自母亲,在某个位置上发生随机改变,通常就是改变DNA的一个二进制位(0变到1,或者1变到0)。

    需要说明的是交叉和变异不是必然发生,而是有一定概率发生。先考虑交叉,最坏情况,交叉产生的子代的DNA都比父代要差(这样算法有可能朝着优化的反方向进行,不收敛),如果交叉是有一定概率不发生,那么就能保证子代有一部分基因和当前这一代基因水平一样;而变异本质上是让算法跳出局部最优解,如果变异时常发生,或发生概率太大,那么算法到了最优解时还会不稳定。交叉概率,范围一般是0.6~1,突变常数(又称为变异概率),通常是0.1或者更小。

    python实现如下:

    def crossover_and_mutation(pop, CROSSOVER_RATE = 0.8):
    	new_pop = []
    	for father in pop:		#遍历种群中的每一个个体,将该个体作为父亲
    		child = father		#孩子先得到父亲的全部基因(这里我把一串二进制串的那些0,1称为基因)
    		if np.random.rand() < CROSSOVER_RATE:			#产生子代时不是必然发生交叉,而是以一定的概率发生交叉
    			mother = pop[np.random.randint(POP_SIZE)]	#再种群中选择另一个个体,并将该个体作为母亲
    			cross_points = np.random.randint(low=0, high=DNA_SIZE*2)	#随机产生交叉的点
    			child[cross_points:] = mother[cross_points:]		#孩子得到位于交叉点后的母亲的基因
    		mutation(child)	#每个后代有一定的机率发生变异
    		new_pop.append(child)
    
    	return new_pop
    
    def mutation(child, MUTATION_RATE=0.003):
    	if np.random.rand() < MUTATION_RATE: 				#以MUTATION_RATE的概率进行变异
    		mutate_point = np.random.randint(0, DNA_SIZE)	#随机产生一个实数,代表要变异基因的位置
    		child[mutate_point] = child[mutate_point]^1 	#将变异点的二进制为反转
    

    上面这些步骤即为遗传算法的核心模块,将这些模块在主函数中迭代起来,让种群去进化

    	pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE*2)) #生成种群 matrix (POP_SIZE, DNA_SIZE)
    	for _ in range(N_GENERATIONS):	#种群迭代进化N_GENERATIONS代
    		crossover_and_mutation(pop, CROSSOVER_RATE)	#种群通过交叉变异产生后代
    		fitness = get_fitness(pop)	#对种群中的每个个体进行评估
    		pop = select(pop, fitness) 	#选择生成新的种群
    

    附录

    完整代码

    
    import numpy as np
    import matplotlib.pyplot as plt
    from matplotlib import cm
    from mpl_toolkits.mplot3d import Axes3D
    
    DNA_SIZE = 24
    POP_SIZE = 200
    CROSSOVER_RATE = 0.8
    MUTATION_RATE = 0.005
    N_GENERATIONS = 50
    X_BOUND = [-3, 3]
    Y_BOUND = [-3, 3]
    
    
    def F(x, y):
    	return 3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)
    
    def plot_3d(ax):
    
    	X = np.linspace(*X_BOUND, 100)
    	Y = np.linspace(*Y_BOUND, 100)
    	X,Y = np.meshgrid(X, Y)
    	Z = F(X, Y)
    	ax.plot_surface(X,Y,Z,rstride=1,cstride=1,cmap=cm.coolwarm)
    	ax.set_zlim(-10,10)
    	ax.set_xlabel('x')
    	ax.set_ylabel('y')
    	ax.set_zlabel('z')
    	plt.pause(3)
    	plt.show()
    
    
    def get_fitness(pop): 
        x,y = translateDNA(pop)
    	pred = F(x, y)
    	return (pred - np.min(pred)) + 1e-3 #减去最小的适应度是为了防止适应度出现负数,通过这一步fitness的范围为[0, np.max(pred)-np.min(pred)],最后在加上一个很小的数防止出现为0的适应度
    
    
    def translateDNA(pop): #pop表示种群矩阵,一行表示一个二进制编码表示的DNA,矩阵的行数为种群数目
    	x_pop = pop[:,1::2]#奇数列表示X
    	y_pop = pop[:,::2] #偶数列表示y
    	
    	#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]
    	return x,y
    
    def crossover_and_mutation(pop, CROSSOVER_RATE = 0.8):
    	new_pop = []
    	for father in pop:		#遍历种群中的每一个个体,将该个体作为父亲
    		child = father		#孩子先得到父亲的全部基因(这里我把一串二进制串的那些0,1称为基因)
    		if np.random.rand() < CROSSOVER_RATE:			#产生子代时不是必然发生交叉,而是以一定的概率发生交叉
    			mother = pop[np.random.randint(POP_SIZE)]	#再种群中选择另一个个体,并将该个体作为母亲
    			cross_points = np.random.randint(low=0, high=DNA_SIZE*2)	#随机产生交叉的点
    			child[cross_points:] = mother[cross_points:]		#孩子得到位于交叉点后的母亲的基因
    		mutation(child)	#每个后代有一定的机率发生变异
    		new_pop.append(child)
    
    	return new_pop
    
    def mutation(child, MUTATION_RATE=0.003):
    	if np.random.rand() < MUTATION_RATE: 				#以MUTATION_RATE的概率进行变异
    		mutate_point = np.random.randint(0, DNA_SIZE*2)	#随机产生一个实数,代表要变异基因的位置
    		child[mutate_point] = child[mutate_point]^1 	#将变异点的二进制为反转
    
    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()) )
        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 = translateDNA(pop)
    	print("最优的基因型:", pop[max_fitness_index])
    	print("(x, y):", (x[max_fitness_index], y[max_fitness_index]))
    
    
    if __name__ == "__main__":
    	fig = plt.figure()
    	ax = Axes3D(fig)	
    	plt.ion()#将画图模式改为交互模式,程序遇到plt.show不会暂停,而是继续执行
    	plot_3d(ax)
    
    	pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE*2)) #matrix (POP_SIZE, DNA_SIZE)
    	for _ in range(N_GENERATIONS):#迭代N代
    		x,y = translateDNA(pop)
    		if 'sca' in locals(): 
    			sca.remove()
    		sca = ax.scatter(x, y, F(x,y), c='black', marker='o');plt.show();plt.pause(0.1)
    		pop = np.array(crossover_and_mutation(pop, CROSSOVER_RATE))
    		#F_values = F(translateDNA(pop)[0], translateDNA(pop)[1])#x, y --> Z matrix
    		fitness = get_fitness(pop)
    		pop = select(pop, fitness) #选择生成新的种群
    	
    	print_info(pop)
    	plt.ioff()
    	plot_3d(ax)
    
    展开全文
  • 详解遗传算法(含MATLAB代码)

    万次阅读 多人点赞 2019-05-29 11:30:47
    一、遗传算法概述 二、遗传算法的特点和应用 三、遗传算法的基本流程及实现技术 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

     

    展开全文
  • 遗传算法遗传算法遗传算法遗传算法遗传算法
  • 遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法
  • 提供一种改进的遗传算法程序,内含一个m文件。
  • matlab遗传算法例程,求解目标函数的最大值
  • c++遗传 遗传算法实现c++遗传 遗传算法实现c++遗传 遗传算法实现c++遗传 遗传算法实现c++遗传 遗传算法实现c++遗传 遗传算法实现c++遗传 遗传算法实现c++遗传 遗传算法实现c++遗传 遗传算法实现c++遗传 遗传算法实现...
  • 遗传算法展示,利用python演示遗传算法,更好的理解遗传算法
  • 遗传算法遗传算法

    2011-10-15 15:05:39
    遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法
  • 遗传算法在线识别全钒液流电池一阶等效电路模型参数
  • 提供了三个经典遗传算法的案例,内有源代码。欢迎大家交流,共同进步。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 55,801
精华内容 22,320
关键字:

遗传算法