遗传算法 订阅
遗传算法(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,可见本文实现的遗传算法表现还不算太差。

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

    展开全文
  • 详解遗传算法(含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

     

    展开全文
  • 遗传算法详解

    万次阅读 多人点赞 2018-07-18 21:18:48
    1.遗传算法基本原理 1.1遗传算法基础 1.2遗传算法实现步骤 1.编码 2.解码 3.交配 4.突变 5.倒位 6.个体适应度评估 7.复制 2.遗传算法的MATLAB程序设计 2.1程序设计流程及参数选取 1.伪代码 2.遗传算法的参数...

    所有博文已迁移至个人网站:https://www.ravenxrz.ink,请勿再留言评论

    新链接:https://www.ravenxrz.ink/archives/8df54bf5.html

    1.遗传算法基本原理

    1.1遗传算法基础

    种群是生物进化的基本单位的,生物进化的实质是种群基本频率的改变。基因突变和基因重组、自然选择以及隔离是物种形成过程中的三个基本环节,通过他们的综合作用,种群产生分化,最终导致新物种的形成。

    1.2遗传算法实现步骤

    1.编码

    遗传算法的编码有浮点编码和二进制编码两种。这里介绍为禁止编码。设某一参数的取值范围为L,U(L,U),使用长度为k的二进制编码表示改参数,则它共有2k2^k中不同的编码,每相邻的编码的两个编码的间隔是Δ\Delta,容易知道

    Δ=(UL)(2k1)\Delta= \frac{(U-L)}{(2^k-1)}

    2.解码

    解码的目的就是将不直观的二进制数据串还原成十进制。

    遗传算法的编码和解码在宏观上可以对应生物的基因型和表现型,在围观上可以对应DNA的转录和翻译两个过程。

    3.交配

    “交配运算”是使用单点或者多点进行交叉的算子。首先用随机数产生一个或者多个叫叫配电的位置,然后两个个题在叫配电位置互换部分基因码,形成两个子个体。如下图:

    交配运算.png

    两个基因在"/"处进行了交换

    4.突变

    “突变运算”是使用基本位进行基因突变 。例如,将染色体S=11001101第3位上的0变为1,即S = 11101101=S’.S’可以被看做是原染色S的子代染色体。

    5.倒位

    将染色体基因的一部分进行逆序排列。例如:S = 100/1100/11,倒位以后为S’ = 100/0011/11.

    6.个体适应度评估

    遗传算法依照与个体适应度成正比的几率决定当前种群中各个个体遗传都下一代群体中的机会。通常求目标函数最大值的问题可以直接把目标函数作为检测个体适应度大小的函数

    7.复制

    复制运算时根据个体适应度大小决定其下代遗传的可能性。弱设种群中个体总数为N,个体i的适应度为fi,则个体i被选取的几率为:
    Pi=fiPi = \frac{f_i}{总适应度}

    2.遗传算法的MATLAB程序设计

    2.1程序设计流程及参数选取

    1.伪代码
     % 遗传算法的伪代码
     BEGIN
        t = 0;  %遗传代数
        初始化P(t);%初始化种群或者染色体
        计算P(t)的适应值;
        while(不满足停止准则) do
            begin
            t = t+1;
            从P(t-1)中选择P(t); %选择
            重组P(t);
            计算P(t)的适应值;
             end
        end
     END
    
    2.遗传算法的参数设计原则

    1.种群的规模
    种群不宜过大也不宜过小。种群规模的一个建议值为0-100

    2.变异概率
    变异概率也不宜过大或者过小。一般取值为0.0001-0.2

    3.交配概率
    同上,不宜过大或者过小。一般取值 为0.4-0.99

    4.进化代数
    同上,不宜过大或者过小。一般取值为100-500

    5.种群初始化
    初始种群的生成是随机的。在出是种群的赋予之前,尽量进行一个大概的区间估计,避免初始种群分布在远离最优解的编码空间,导致遗传算法的搜索范围受到限制。

    3.遗传算法适应度函数设计

    1.遗传算法和直接搜索工具箱中的函数ga是求解目标函数的最小值,所以如果目标函数为求解最小值,则直接令目标函数为适应度函数即可。编写的适应度函数,语法如下:

    function f = fitnesscn(x)
    f = f(x);
    end
    

    2.如果有约束条件(包括自变量的取值范围),对于求解函数的最小值问题,语法如下:

    function f = fitnessfcx(x)
        if x<=-1||x>3
            f = inf;
        else
            f = f(x);
        end
    end
    

    3.如果有约束条件(包括自变量的取值范围),对于求解函数的最大值问题,语法如下:

    function f = fitnessfcx(x)
        if x<=-1||x>3
            f = inf;
        else
            f = -f(x);
        end
    end
    

    注意:最后求解出来的目标函数为-fval而不是fval

    3.遗传算法应用案例

    这里给出三个案例。
    案例一:无约束目标函数的最大值
    求解maxf(x)=200e(0.05x)sinx;x[2,2]max f(x) = 200*e^{(-0.05x)}*sinx ;x∈[-2,2]

    % 案例一:无约束目标函数的最大值
    % 求解maxf(x)=200*e(−0.05x)*sinx; x∈[−2,2]
    %主程序:用遗传算法求解y=200*exp(-0.05*x).*sin(x)在[-2 2]区间上的最大值
    clc;
    clear ;
    close all;
    global BitLength
    global boundsbegin
    global boundsend
    bounds=[-2 2];%一维自变量的取值范围
    precision=0.0001; %运算精度
    boundsbegin=bounds(:,1);
    boundsend=bounds(:,2);
    %计算如果满足求解精度至少需要多长的染色体
    BitLength=ceil(log2((boundsend-boundsbegin)' ./ precision));
    popsize=50; %初始种群大小
    Generationnmax=12;  %最大代数
    pcrossover=0.90; %交配概率
    pmutation=0.09; %变异概率
    %产生初始种群
    population=round(rand(popsize,BitLength));
    %计算适应度,返回适应度Fitvalue和累积概率cumsump
    [Fitvalue,cumsump]=fitnessfun(population);
    Generation=1;
    while Generation<Generationnmax+1
        for j=1:2:popsize
            %选择操作
            seln=selection(population,cumsump);
            %交叉操作
            scro=crossover(population,seln,pcrossover);
            scnew(j,:)=scro(1,:);
            scnew(j+1,:)=scro(2,:);
            %变异操作(在原交叉基础上有进行变异)
            smnew(j,:)=mutation(scnew(j,:),pmutation);
            smnew(j+1,:)=mutation(scnew(j+1,:),pmutation);
        end
        population=smnew;  %产生了新的种群
        %计算新种群的适应度
        [Fitvalue,cumsump]=fitnessfun(population);
        %记录当前代最好的适应度和平均适应度
        [fmax,nmax]=max(Fitvalue);
        fmean=mean(Fitvalue);
        ymax(Generation)=fmax;
        ymean(Generation)=fmean;
        %记录当前代的最佳染色体个体
        x=transform2to10(population(nmax,:));
        %自变量取值范围是[-2 2],需要把经过遗传运算的最佳染色体整合到[-2 2]区间
        xx=boundsbegin+x*(boundsend-boundsbegin)/(power((boundsend),BitLength)-1);
        xmax(Generation)=xx;
        Generation=Generation+1
    end
    Generation=Generation-1;
    Bestpopulation=xx
    Besttargetfunvalue=targetfun(xx)
    %绘制经过遗传运算后的适应度曲线。一般地,如果进化过程中种群的平均适应度与最大适
    %应度在曲线上有相互趋同的形态,表示算法收敛进行得很顺利,没有出现震荡;在这种前
    %提下,最大适应度个体连续若干代都没有发生进化表明种群已经成熟。
    figure(1);
    hand1=plot(1:Generation,ymax);
    set(hand1,'linestyle','-','linewidth',1.8,'marker','*','markersize',6)
    hold on;
    hand2=plot(1:Generation,ymean);
    set(hand2,'color','r','linestyle','-','linewidth',1.8,...
        'marker','h','markersize',6)
    xlabel('进化代数');ylabel('最大/平均适应度');xlim([1 Generationnmax]);
    legend('最大适应度','平均适应度');
    box off;hold off;
    
    %子程序:新种群交叉操作,函数名称存储为crossover.m
    function scro=crossover(population,seln,pc)
    BitLength=size(population,2);
    pcc=IfCroIfMut(pc);  %根据交叉概率决定是否进行交叉操作,1则是,0则否
    if pcc==1
        chb=round(rand*(BitLength-2))+1;  %在[1,BitLength-1]范围内随机产生一个交叉位
        scro(1,:)=[population(seln(1),1:chb) population(seln(2),chb+1:BitLength)];
        scro(2,:)=[population(seln(2),1:chb) population(seln(1),chb+1:BitLength)];
    else
        scro(1,:)=population(seln(1),:);
        scro(2,:)=population(seln(2),:);
    end
    end
    
    %子程序:计算适应度函数, 函数名称存储为fitnessfun
    function [Fitvalue,cumsump]=fitnessfun(population)
    global BitLength
    global boundsbegin
    global boundsend
    popsize=size(population,1);   %有popsize个个体
    for i=1:popsize
        x=transform2to10(population(i,:));  %将二进制转换为十进制
        %转化为[-2,2]区间的实数
        xx=boundsbegin+x*(boundsend-boundsbegin)/(power((boundsend),BitLength)-1);
        Fitvalue(i)=targetfun(xx);  %计算函数值,即适应度
    end
    %给适应度函数加上一个大小合理的数以便保证种群适应值为正数
    Fitvalue=Fitvalue'+230;
    %计算选择概率
    fsum=sum(Fitvalue);
    Pperpopulation=Fitvalue/fsum;
    %计算累积概率
    cumsump = cumsum(Pperpopulation);
    cumsump=cumsump';
    end
    %子程序:新种群变异操作,函数名称存储为mutation.m
    function snnew=mutation(snew,pmutation)
    BitLength=size(snew,2);
    snnew=snew;
    pmm=IfCroIfMut(pmutation);  %根据变异概率决定是否进行变异操作,1则是,0则否
    if pmm==1
        chb=round(rand*(BitLength-1))+1;  %在[1,BitLength]范围内随机产生一个变异位
        snnew(chb)=abs(snew(chb)-1);   %进行一个0-1,1-0的反转
    end
    end
    
    %子程序:判断遗传运算是否需要进行交叉或变异, 函数名称存储为IfCroIfMut.m
    function pcc=IfCroIfMut(mutORcro)
    % 生成一个长为100的序列,随机选中一个点,该点前面的所有数为1,后面为1,
    % 然后又随机生成一个数进行判断是1还是0.
    test(1:100)=0;
    l=round(100*mutORcro);
    test(1:l)=1;
    n=round(rand*99)+1;
    pcc=test(n);
    end
    
    %子程序:新种群选择操作, 函数名称存储为selection.m
    function seln=selection(population,cumsump)
    %从种群中选择两个个体
    for i=1:2
        r=rand;  %产生一个随机数
        prand=cumsump-r;
        j=1;
        while prand(j)<0
            j=j+1;
        end
        seln(i)=j; %选中个体的序号
    end
    end
    %子程序:将2进制数转换为10进制数,函数名称存储为transform2to10.m
    function x=transform2to10(Population)
    BitLength=size(Population,2);
    x=Population(BitLength);
    for i=1:BitLength-1
        x=x+Population(BitLength-i)*power(2,i);
    end
    end
    
    %子程序:对于优化最大值或极大值函数问题,目标函数可以作为适应度函数
    %函数名称存储为targetfun.m
    
    function y=targetfun(x) %目标函数
    y=200*exp(-0.05*x).*sin(x);
    end
    
    

    程序结果:

    
    Bestpopulation =
    
       1.575677119096666
    
    
    Besttargetfunvalue =
    
         1.848457326200009e+02
    

    image.png

    案例二:多约束非线性规划问题
    在这里插入图片描述

    %主程序:本程序采用遗传算法接力进化,
    %将上次进化结束后得到的最终种群作为下次输入的初始种群
    clc;
    close all;
    clear all;
    %进化的代数
    T=100;
    optionsOrigin=gaoptimset('Generations',T/2);
    [x,fval,reason,output,final_pop]=ga(@ch14_2f,2,optionsOrigin);
    %进行第二次接力进化
    options1=gaoptimset('Generations',T/2,'InitialPopulation',final_pop,...
        'PlotFcns',@gaplotbestf);
    [x,fval,reason,output,final_pop]=ga(@ch14_2f,2,options1);
    Bestx=x
    BestFval=fval
    
    
    %子函数:适应度函数同时也是目标函数,函数存储名称为ch14_2f.m
    function f=ch14_2f(x)
    g1=1.5+x(1)*x(2)-x(1)-x(2);
    g2=-x(1)*x(2);
    if (g1>0||g2>10)
        f=100;
    else
        f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);
    end
    end
    

    程序结果:

    Optimization terminated: maximum number of generations exceeded.
    Optimization terminated: maximum number of generations exceeded.
    
    Bestx =
    
      -9.026449478668987   1.105769708316651
    
    
    BestFval =
    
       0.035051699473142
    
    >> 
    

    案例三:经典TSP问题
    假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

    % 利用遗传算法,解决TSP问题模板
    tic
    clc,clear
    sj = load('yichuansuanfadata.txt'); %加载敌方100 个目标的数据
    x=sj(:,1:2:8);x=x(:);
    y=sj(:,2:2:8);y=y(:);
    sj=[x y];
    figure(1);
    plot(x,y);
    d1=[70,40];
    sj0=[d1;sj;d1];
    %距离矩阵d
    sj=sj0*pi/180;
    d=zeros(102);
    for i=1:101
        for j=i+1:102
            temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
            d(i,j)=6370*acos(temp);
        end
    end
    d=d+d';L=102;w=50;dai=100;
    %通过改良圈算法选取优良父代A
    for k=1:w
        c=randperm(100);
        c1=[1,c+1,102];
        flag=1;
        while flag>0
            flag=0;
            for m=1:L-3
                for n=m+2:L-1
                    if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1))
                        flag=1;
                        c1(m+1:n)=c1(n:-1:m+1);
                    end
                end
            end
        end
        J(k,c1)=1:102;
    end
    J=J/102;
    J(:,1)=0;J(:,102)=1;
    rand('state',sum(clock));
    %遗传算法实现过程
    A=J;
    for k=1:dai %产生0~1 间随机数列进行编码
        B=A;
        c=randperm(w);
        %交配产生子代B
        for i=1:2:w
            F=2+floor(100*rand(1));
            temp=B(c(i),F:102);
            B(c(i),F:102)=B(c(i+1),F:102);
            B(c(i+1),F:102)=temp;
        end
        %变异产生子代C
        by=find(rand(1,w)<0.1);
        if length(by)==0
            by=floor(w*rand(1))+1;
        end
        C=A(by,:);
        L3=length(by);
        for j=1:L3
            bw=2+floor(100*rand(1,3));
            bw=sort(bw);
            C(j,:)=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);
        end
        G=[A;B;C];
        TL=size(G,1);
        %在父代和子代中选择优良品种作为新的父代
        [dd,IX]=sort(G,2);temp(1:TL)=0;
        for j=1:TL
            for i=1:101
                temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));
            end
        end
        [DZ,IZ]=sort(temp);
        A=G(IZ(1:w),:);
    end
    path=IX(IZ(1),:)
    long=DZ(1)
    toc
    xx=sj0(path,1);yy=sj0(path,2);
    %plot(xx,yy,'-o',)
    figure(2);
    plot(xx,yy,'-o')
    

    其中"yichuansuanfadata.txt"为各点之间的经纬坐标,数据如下:

    53.7121   15.3046	51.1758    0.0322	46.3253   28.2753	30.3313    6.9348
    56.5432   21.4188	10.8198   16.2529	22.7891   23.1045	10.1584   12.4819
    20.1050   15.4562	1.9451    0.2057	26.4951   22.1221	31.4847    8.9640
    26.2418   18.1760	44.0356   13.5401	28.9836   25.9879	38.4722   20.1731
    28.2694   29.0011	32.1910    5.8699	36.4863   29.7284	0.9718   28.1477
    8.9586   24.6635	16.5618   23.6143	10.5597   15.1178	50.2111   10.2944
    8.1519    9.5325	22.1075   18.5569	0.1215   18.8726	48.2077   16.8889
    31.9499   17.6309	0.7732    0.4656	47.4134   23.7783	41.8671    3.5667
    43.5474    3.9061	53.3524   26.7256	30.8165   13.4595	27.7133    5.0706
    23.9222    7.6306	51.9612   22.8511	12.7938   15.7307	4.9568    8.3669
    21.5051   24.0909	15.2548   27.2111	6.2070    5.1442	49.2430   16.7044
    17.1168   20.0354	34.1688   22.7571	9.4402    3.9200	11.5812   14.5677
    52.1181    0.4088	9.5559   11.4219	24.4509    6.5634	26.7213   28.5667
    37.5848   16.8474	35.6619    9.9333	24.4654    3.1644	0.7775    6.9576
    14.4703   13.6368	19.8660   15.1224	3.1616    4.2428	18.5245   14.3598
    58.6849   27.1485	39.5168   16.9371	56.5089   13.7090	52.5211   15.7957
    38.4300    8.4648	51.8181   23.0159	8.9983   23.6440	50.1156   23.7816
    13.7909    1.9510	34.0574   23.3960	23.0624    8.4319	19.9857    5.7902
    40.8801   14.2978	58.8289   14.5229	18.6635    6.7436	52.8423   27.2880
    39.9494   29.5114	47.5099   24.0664	10.1121   27.2662	28.7812   27.6659
    8.0831   27.6705	9.1556   14.1304	53.7989    0.2199	33.6490    0.3980
    1.3496   16.8359	49.9816    6.0828	19.3635   17.6622	36.9545   23.0265
    15.7320   19.5697	11.5118   17.3884	44.0398   16.2635	39.7139   28.4203
    6.9909   23.1804	38.3392   19.9950	24.6543   19.6057	36.9980   24.3992
    4.1591    3.1853	40.1400   20.3030	23.9876    9.4030	41.1084   27.7149
    
    

    其中奇数列为经度,偶数列为纬度

    求解结果如下:

    
    path =
    
      1 至 19 列
    
         1    17     3    36    43    93    46    59   100    98    51    80    50    15    42    20    30    74    83
    
      20 至 38 列
    
        87    92     2    45    67    82    48    72    14    27    10    84    18    40    79    77    31    97    85
    
      39 至 57 列
    
        65    64    11    76    69    94    70    19    63    62    26    29    34    66    90    86     8    39    78
    
      58 至 76 列
    
        47    23    58    81    22    71    37     7    68    25    49    28    57    88    61    16    91    41     4
    
      77 至 95 列
    
        73    13    24    32    12    53    33    75     5    60     9    38    44    54    55    96    89     6    56
    
      96 至 102 列
    
        21    99   101    52    95    35   102
    
    
    long =
    
         4.087894090467779e+04
    
    时间已过 8.865015 秒。
    >> 
    

    image.png

    image.png

    展开全文
  • 用简单遗传算法求解8皇后问题,每次输出一代染色体中最好和最差个体的适应度,当求的解时便将解输出,解依次为0到7行哪一列放棋子,只是简单的熟悉一下遗传算法,代码没有写注释,如果有问题与我讨论就发邮件吧,...
  • 遗传算法原理及算法实例

    万次阅读 多人点赞 2017-11-26 09:42:19
    遗传算法原理解析 遗传算法(GA)是一种元启发式自然选择的过程,属于进化算法(EA)大类。遗传算法通常是利用生物启发算子,如变异、交叉和选择来生成高质量的优化和搜索问题的解决方案。 借鉴生物进化理论,遗传...

    遗传算法原理解析

    遗传算法(GA)是一种元启发式自然选择的过程,属于进化算法(EA)大类。遗传算法通常是利用生物启发算子,如变异、交叉和选择来生成高质量的优化和搜索问题的解决方案。

    借鉴生物进化理论,遗传算法将问题模拟成一个生物进化过程,通过遗传、交叉、突变、自然选择等操作产生下一代的解,并逐步淘汰适应度函数值低的解,增加适应度函数高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。

    与遗传算法有关的生物学概念:

    (1)染色体(chromosome)
    生物是由细胞组成,每一个细胞中都有一套相同的染色体。一条染色体由若干基因(gene) 组成,每个基因控制一种特定的蛋白质,从而决定生物的某种特征。所有染色体合称为基因组(genome)。基因组完全决定了一个生物个体。该个体在微观(基因)层次的表现称为基因型 (genotype),在宏观(特征)层次的表现称为显型 (phenotype)。在简单的遗传算法中,将基因组中的若干条染色体看作一整条染色体。
    (2) 个体复制
    在复制的过程中,父母的染色体通过交叉(crossover)产生子女的染色体。染色体还可以以一定的小概率变异(mutate)。

    遗传算法本质上是一种搜索算法,搜索算法的共同特征为:

    1. 首先组成一组候选解
    2. 依据某些适应性条件测算这些候选解的适应度
    3. 根据适应度保留某些候选解,放弃其他候选解
    4. 对保留的候选解进行某些操作,生成新的候选解

      
    交叉(Crossover):2条染色体交换部分基因,来构造下一代的2条新的染色体。
    交叉前:
    00000|011100000000|10000
    11100|000001111110|00101
    交叉后:
    00000|000001111110|10000
    11100|011100000000|00101
    染色体交叉是以一定的概率发生的,这个概率记为Pc 。
    变异(Mutation):在繁殖过程,新产生的染色体中的基因会以一定的概率出错,称为变异。变异发生的概率记为Pm 。
    变异前:
    000001110000000010000
    变异后:
    000001110000100010000
    适应度函数 ( Fitness Function ):用于评价某个染色体的适应度,用f(x)表示。有时需要区分染色体的适应度函数与问题的目标函数。例如:0-1背包问题的目标函数是所取得物品价值,但将物品价值作为染色体的适应度函数可能并不一定适合。适应度函数与目标函数是正相关的,可对目标函数作一些变形来得到适应度函数。

    遗传算法伪代码

    基本遗传算法伪代码
    /*
    * Pc:交叉发生的概率
    * Pm:变异发生的概率
    * M:种群规模
    * G:终止进化的代数
    * Tf:进化产生的任何一个个体的适应度函数超过Tf,则可以终止进化过程
    */
    初始化Pm,Pc,M,G,Tf等参数。随机产生第一代种群Pop
     
    do
    { 
      计算种群Pop中每一个体的适应度F(i)。
      初始化空种群newPop
      do
      {
        根据适应度以比例选择算法从种群Pop中选出2个个体
        if ( random ( 0 , 1 ) < Pc )
        {
          对2个个体按交叉概率Pc执行交叉操作
        }
        if ( random ( 0 , 1 ) < Pm )
        {
          对2个个体按变异概率Pm执行变异操作
        }
    将2个新个体加入种群newPop中
    } until ( M个子代被创建 )
    用newPop取代Pop
    }until ( 任何染色体得分超过Tf, 或繁殖代数超过G )

    遗传算法优化方法:

    (1)精英主义(Elitist Strategy)选择:是基本遗传算法的一种优化。为了防止进化过程中产生的最优解被交叉和变异所破坏,可以将每一代中的最优解原封不动的复制到下一代中。
    (2)插入操作:可在3个基本操作的基础上增加一个插入操作。插入操作将染色体中的某个随机的片段移位到另一个随机的位置。

    遗传算法实例

    这里选用参考3中的实例:计算函数

    的最小值,其中每个变量的取值区间都是[-1, +1]。

    首先,确定适应度的函数:

    function y = my_fitness(population)
    % population是随机数[0,1]矩阵,下面的操作改变范围为[-1,1]
    population = 2 * (population - 0.5); 
    y = sum(population.^2, 2); % 行的平方和
    遗传算法实现:
    function [best_fitness, elite, generation, last_generation] = my_ga( ...
        number_of_variables, ...    % 求解问题的参数个数
        fitness_function, ...       % 自定义适应度函数名
        population_size, ...        % 种群规模(每一代个体数目)
        parent_number, ...          % 每一代中保持不变的数目(除了变异)
        mutation_rate, ...          % 变异概率
        maximal_generation, ...     % 最大演化代数
        minimal_cost ...            % 最小目标值(函数值越小,则适应度越高)
    )
    
    % 累加概率
    % 假设 parent_number = 10
    % 分子 parent_number:-1:1 用于生成一个数列
    % 分母 sum(parent_number:-1:1) 是一个求和结果(一个数)
    % 分子 10     9     8     7     6     5     4     3     2     1
    % 分母 10+9+...+1=55
    % 相除 0.1818    0.1636    0.1455    0.1273    0.1091    0.0909    0.0727    0.0545    0.0364    0.0182
    % 累加(cumsum) 0.1818    0.3455    0.4909    0.6182    0.7273    0.8182    0.8909    0.9455    0.9818    1.0000
    % 运算结果可以看出: 累加概率函数是一个从0到1增长得越来越慢的函数
    cumulative_probabilities = cumsum((parent_number:-1:1) / sum(parent_number:-1:1)); % 1个长度为parent_number的数列
    best_fitness = ones(maximal_generation, 1);% 记录每一代最佳适应度,先初始化为1
    elite = zeros(maximal_generation, number_of_variables);% 记录每一代的最优解,初始化为0
    
    % 子女数量=种群数量 - 父母数量(父母即每一代中不发生改变的个体)
    child_number = population_size - parent_number; % 每一代子女的数目
    
    % population_size 对应矩阵的行,每一行表示1个个体,行数=个体数(种群数量)
    % number_of_variables 对应矩阵的列,列数=参数个数(个体特征由这些参数表示)
    population = rand(population_size, number_of_variables);% 初始化种群
    last_generation = 0; % 记录跳出循环时的代数
    
    for generation = 1 : maximal_generation % 演化循环开始
        
        % feval把数据带入到一个定义好的函数句柄中计算
        % 把population矩阵带入fitness_function函数计算
        cost = feval(fitness_function, population); % 计算所有个体的适应度(population_size*1的矩阵)
    
        % index记录排序后每个值原来的行数
        [cost, index] = sort(cost); % 将适应度函数值从小到大排序
    
        % index(1:parent_number) 
        % 前parent_number个cost较小的个体在种群population中的行数
        % 选出这部分(parent_number个)个体作为父母,其实parent_number对应交叉概率
        population = population(index(1:parent_number), :); % 先保留一部分较优的个体
        % population矩阵是不断变化的
        % cost在经过前面的sort排序后,矩阵已经改变为升序的
        % cost(1)即为本代的最佳适应度
        best_fitness(generation) = cost(1); % 记录本代的最佳适应度
    
        % population矩阵第一行为本代的最优解(精英)
        elite(generation, :) = population(1, :); % 记录本代的最优解(精英)
    
        % 若本代的最优解已足够好,则停止演化
        if best_fitness(generation) < minimal_cost; 
            last_generation = generation;
            break; 
        end
        
        % 交叉变异产生新的种群,染色体交叉开始
        for child = 1:2:child_number % 步长为2是因为每一次交叉会产生2个孩子
            
            % cumulative_probabilities 长度为 parent_number
            % 从中随机选择2个父母出来  (child+parent_number)
            mother = find(cumulative_probabilities > rand, 1); % 选择一个较优秀的母亲
            father = find(cumulative_probabilities > rand, 1); % 选择一个较优秀的父亲
            
            % ceil:向上取整
            % rand 生成一个随机数
            % 即随机选择了一列,这一列的值交换
            crossover_point = ceil(rand*number_of_variables); % 随机地确定一个染色体交叉点
            
            % 假如crossover_point=3, number_of_variables=5
            % mask1 = 1     1     1     0     0
            % mask2 = 0     0     0     1     1
            mask1 = [ones(1, crossover_point), zeros(1, number_of_variables - crossover_point)];
            mask2 = not(mask1);
            
            % 获取分开的4段染色体
            mother_1 = mask1 .* population(mother, :); % 母亲染色体的前部分
            mother_2 = mask2 .* population(mother, :); % 母亲染色体的后部分
            
            father_1 = mask1 .* population(father, :); % 父亲染色体的前部分
            father_2 = mask2 .* population(father, :); % 父亲染色体的后部分
            
            % 得到下一代
            population(parent_number + child, :) = mother_1 + father_2; % 一个孩子
            population(parent_number+child+1, :) = mother_2 + father_1; % 另一个孩子
            
        end % 染色体交叉结束
        
        
        % 染色体变异开始,变异种群
        mutation_population = population(2:population_size, :); % 精英不参与变异,从2开始    
        number_of_elements = (population_size - 1) * number_of_variables; % 全部基因数目
        number_of_mutations = ceil(number_of_elements * mutation_rate); % 变异的基因数目(基因总数*变异率)
        
        % rand(1, number_of_mutations) 生成number_of_mutations个随机数(范围0-1)组成的矩阵(1*number_of_mutations)
        % 数乘后,矩阵每个元素表示发生改变的基因的位置(元素在矩阵中的一维坐标)
        mutation_points = ceil(number_of_elements * rand(1, number_of_mutations)); % 确定要变异的基因
        
        % 被选中的基因都被一个随机数替代,完成变异
        mutation_population(mutation_points) = rand(1, number_of_mutations); % 对选中的基因进行变异操作
        population(2:population_size, :) = mutation_population; % 发生变异之后的种群
        % 染色体变异结束
    end % 演化循环结束
    函数测试:
    clc,clear all,close all;
    
    % 调用 my_ga 进行计算
    % 求解问题的参数个数         10
    % 自定义适应度函数名         my_fitness
    % 种群规模                  100
    % 每一代中保持不变的数目     50 (即交叉率0.5)
    % 变异概率                  0.1 (1/10的个体发生变异)
    % 最大演化代数              10000 10000代
    % 最小目标值                1.0e-6 个体适应度函数值 < 0.000001结束
    [best_fitness, elite, generation, last_generation] = my_ga(10, 'my_fitness', 100, 50, 0.1, 10000, 1.0e-6);
    
    % 输出后10行
    disp(last_generation); 
    i_begin = last_generation - 9;
    disp(best_fitness(i_begin:last_generation,:));
    % disp(best_fitness(9990:10000,:));
    % disp(elite(9990:10000,:))
    % 不要写成这样,因为GA常常在中间就跳出循环了
    
    % 将elite值转化为问题范围内
    my_elite = elite(i_begin:last_generation,:);
    my_elite = 2 * (my_elite - 0.5);
    disp(my_elite);
    
    % 最佳适应度的演化情况
    figure
    loglog(1:generation, best_fitness(1:generation), 'linewidth',2)
    xlabel('Generation','fontsize',15);
    ylabel('Best Fitness','fontsize',15);
    set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);
    
    % 最优解的演化情况
    figure
    semilogx(1 : generation, 2 * elite(1 : generation, :) - 1)
    xlabel('Generation','fontsize',15);
    ylabel('Best Solution','fontsize',15);
    set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);
    

    参考:
    http://blog.jobbole.com/110913/
    http://blog.csdn.net/dazhong159/article/details/7908531

    http://blog.sciencenet.cn/blog-3102863-1029280.html

    https://github.com/Shuai-Xie/genetic-algorithm

    https://github.com/yanshengjia/artificial-intelligence/tree/master/genetic-algorithm-for-functional-maximum-problem/src


    展开全文
  • 遗传算法(一)遗传算法的基本原理 1.概述 遗传算法(Genetic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,借鉴了达尔文的进化论和...
  • 遗传算法 求解旅行商 TSP 问题,matlab代码

    万次阅读 多人点赞 2016-11-02 01:24:11
    其中,遗传算法可以用来求解该问题。遗传算法是一种进化算法,由于其启发式算法的属性,并不能保证得到最优解。求解效果与初始种群选取,编码方法,选择方法,交叉变异规则有关。 上课时,老师不知从哪里找了一个...
  • 遗传算法(二)改进:自适应、遗传退火算法

    万次阅读 多人点赞 2017-08-25 13:51:31
    笔记(二) 遗传算法的优化改进 自适应遗传算法and模拟退火遗传算法
  • 非常经典的遗传算法的学习资料。 非常经典的遗传算法的学习资料。
  • 优化算法——遗传算法

    万次阅读 多人点赞 2015-05-10 17:09:28
    遗传算法的第一次接触 遗传算法的基本概念 基本定义 遗传算法的基本流程 遗传算法过程中的具体操作 参数的编码 二进制编码 Gray编码 实数编码 有序编码 初始群体的设定 适应度函数的计算 遗传操作设计 选择...
  • 1.1 遗传算法的生物学基础 1.2 遗传算法简介 1.3 遗传算法的特点 1.4 遗传其法的发展 1.5 遗传算法的应用 第二章基本遗传算法 Z.1 基乍遗传算法描述 2.2 基本遗传算法的实现 2.3 基本遗传算法应用举例 第...
  • 遗传算法的matlab实现

    万次阅读 多人点赞 2017-06-23 18:14:07
    遗传算法是一种全局最优化算法,是运用了进化论优胜劣汰原理的随机化搜索方法。 前些日子,在进行毕业设计的相关研究中,我接触到了遗传算法,用其对一个五元非线性函数进行最优化搜索。仿真平台使用的是matlab,...
  • 基于遗传算法的BP神经网络优化算法

    万次阅读 多人点赞 2016-04-10 20:22:41
    遗传算法优化BP神经网络分为BP神经网络结构确定、遗传算法优化和 BP神经网络预测3个部分。其中,BP神经网络结构确定部分根据拟合函数输入输出参数个数确定 BP神经网络结构,这样就可以确定遗传算法的优化参数个数,...

空空如也

1 2 3 4 5 ... 20
收藏数 13,662
精华内容 5,464
关键字:

遗传算法