初识遗传算法(Genetic Algorithm)

2023-12-24 19:08

本文主要是介绍初识遗传算法(Genetic Algorithm),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法简介

遗传算法(Genetic Algorithm)是由美国的J.Holland教授于1975年首先提出。它是模拟达尔文进化理论和自然界优胜劣汰的机制进行全局最优解搜索的启发式优化算法。遗传算法从问题的一个种群(可行解)开始,种群中的每个个体都具有基因编码,代表了个体的特征,也决定了个体在自然界中的表现,也就是个体的适应度。自然界中的基因编码与组合十分复杂,在遗传算法用于实际问题的求解中我们往往对基因的编码过程进行简化,例如进行二进制编码。在产生初代种群后,GA根据个体的适应度模拟自然选择,并通过个体间基因的交叉和变异产生新的种群。这个过程的不断迭代更新保证后产生的种群将比之前的种群具有更高的适应度,最终产生的具有最高适应度的个体通过解码就将作为问题的近似解。


算法特点

  1. 直接对结构对象进行操作,无需函数求导和连续性的限定
  2. 全局搜索能力强
  3. 自适应的调整搜索方向和搜索空间
  4. 可并行

算法流程图


算法基本过程

  1. 初始化:设置最大迭代进化次数T,随机生成M个个体作为初始种群P(0);
  2. 个体评价:计算当前种群P(t)中的个体适应度;
  3. 选择:在个体评价之后,对群体进行选择操作目的是将优秀个体的基因通过组合配对交叉遗传到下一代种群中;
  4. 交叉:遗传算法中的核心部分;
  5. 变异:在个体基因的基础上进行变动,模拟自然界的基因突变,其变异结果的好坏不定;
  6. 终止条件:若迭代次数达到预先设定的T,将迭代过程中具有最优适应度的个体作为问题的解输出。

具体步骤分析

遗传算法的核心是个体之间的组合交叉变异部分。个体之间的组合交叉变异方式众多,不同的交叉变异方式将对算法的效率产生巨大的影响。

选择

  • 适应度比例方法,例如轮盘赌选择算法
  • 随机遍历抽样
  • 局部选择

       其中轮盘赌选择算法是最简单也是最常用的选择算法之一。该方法中各个个体被选择的概率和其适应度成正比。个体的适应度越高,其被选择到的概率越大。

交叉

  • 实值重组:离散重组、中间重组、线性重组、扩展线性重组
  • 二进制交叉:单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉

       其中单点交叉是最常用的交叉算法。在操作时首先设定一个交叉点,将两个个体在该点之后的基因结构进行互换,从而形成两个新的个体。例如: 
个体A:1 0 0 1 ↑ 1 1 1 → 1 0 0 1 0 0 0 新个体 
个体B:0 0 1 1 ↑ 0 0 0 → 0 0 1 1 1 1 1 新个体

变异

  • 实值变异
  • 二进制变异

       遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时,利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然,此种情况下的变异概率应取较小值,否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性,以防止出现未成熟收敛现象。此时收敛概率应取较大值。


 经典应用

  1. 旅行商问题(Traveling Salesman Problem,TSP):TSP是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。
  2. 指派问题(Assignment problem):在满足特定指派要求条件下,使指派方案总体效果最佳。如:有若干项工作需要分配给若干人(或部门)来完成。
  3. 单车间调度问题(Job-shop scheduling problem, JSP)是最基本最著名的调度问题,也是NP难问题,无最优解精确算法。一般类型的JSP问题可表达为:n个工件在m台机器上加工,每个工件有特定的加工工艺,每个工件加工的顺序及每道工序所花时间给定,安排工件在每台机器上工件的加工顺序,使得某种指标最优。
  4. 运输问题:为了把某种产品从若干个产地调运到若干个销地,已知每个产地的供应量和每个销地的需求量,如何在许多可行的调运方案中,确定一个总运输费或总运输量最少的方案。
  5. 背包问题(Transportation problem):给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。
  6. 设施选址问题(Facility Location Problem):指在给定的若干位置中选择一些来建立设施使得所有顾客的需求得到满足,且总体费用最小。
  7. 图划分问题(Graph Partitioning Problem):将图中的节点划分为数量大致相等的若干个分区,使得两个顶点分别在不同分区的边的数量最小化。
  8. 图着色问题。对于n个顶点的无环图G,要求对其各个顶点进行着色,使得任意相邻的顶点都有不同的颜色,且所用颜色种类最少。

不足

  1. 算法容易过早收敛,且在GA的轮盘赌选择算法中根据个体的适应度进行基因的优选,但是如果前期存在超级个体,几乎所有的交叉产生的子代都存在这个超级个体的基因,因此失去了种群的多样性;但是在种群迭代的后期当所有的个体适应度都差不多的时候,算法接近于随机搜索,效率降低。 
    优化方案:适应度放缩。前期,当适应度差距较大的时候,将适应度适当缩小,适应度较小的个体也可以被选择,同时不存在超级个体,使得种群不那么容易“早熟”;后期,当适应度接近的时候,将适应度进行适当扩大,即扩大个体间的差异,使得算法在后期依然有选择作用。例如:f(x) \leftarrow a\cdot f(x)+b
  2. 算法的搜索效率相对于一些其他的优化算法较低。 
  3. 遗传算法对算法的精度、可行度、计算复杂性等方面,还没有有效的定量分析方法。

C++实现

 

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>#define num_pop 100      //定义初始种群数目
#define num_iter 1000    //定义迭代次数
#define p_cross 0.7      //定义交叉概率
#define p_mutate 0.2     //定义变异概率
#define len_chrom 1000   //染色体长度double pop[num_pop][len_chrom];     //种群数组
double fitness[num_pop];            //种群中个体的适应度
double fitness_prob[num_pop];       //每个个体被选中的概率(轮盘赌)
double lbest[num_iter];             //每次迭代中的最优适应度
double gbest;                       //全局最优个体的适应度
double gbest_pos[len_chrom];        //全局最优个体的位置
double average_best[num_pop + 1];   //每一代平均适应度
int gbest_index;                    //取得最优值的迭代次数序号using namespace std;//适应度函数
double fit(double a[]){double cost = 0;for(int i = 1; i < len_chrom; i++){cost += (a[i] - 0.5)*(a[i] - 0.5);
//      cost += a[i] * a[i];}return cost;
}// 求和函数
double sum(double * fitness)     //对每一代中所有个体的适应度进行求和
{double sum_fit = 0;for(int i = 0; i < num_pop; i++){sum_fit += *(fitness+i);}return sum_fit;
}// 求最小值函数
double * min(double * fitness)            //返回一个长度为2的数组,第一个为最小适应度代表的个体的指标,第二个为最小适应度
{double min_fit = *fitness;double min_index = 0;static double arr[2];for(int i = 1; i < num_pop; i++){if( *(fitness+i) < min_fit ){min_fit = *(fitness + i);min_index = i;}}arr[0] = min_index;arr[1] = min_fit;return arr;
}//种群初始化
void initial(){for(int i = 0; i < num_pop; i++){          //随机初始化种群位置for(int j = 0; j < len_chrom; j++){pop[i][j] = 1.0*rand()/RAND_MAX;}fitness[i] = fit(pop[i]);              //初始化适应度}
//    for(int i = 0; i < num_pop; i++){         
//        for(int j = 0; j < len_chrom; j++)
//            printf("%f", pop[i][j]);
//  }}//选择操作
void Select(double pop[num_pop][len_chrom]){int index[num_pop];for(int i = 0; i < num_pop; i++){double * arr = pop[i];fitness[i] = 1 / fit(arr);          //这里函数值越小,目标适应度越大   }double sum_fitness = 0;for(int i = 0; i < num_pop; i++){sum_fitness += fitness[i];          //适应度求和}for(int i = 0; i < num_pop; i++){      //轮盘赌选择中,适应度越大的个体越容易被选中fitness_prob[i] = fitness[i] / sum_fitness;}for(int i = 0; i < num_pop; i++){      //恢复原先的适应度函数值fitness[i] = 1.0 / fitness[i];            }for(int i = 0; i < num_pop; i++){      //轮盘赌选择个体double pick = 1.0*rand()/RAND_MAX;while(pick < 0.0001)pick = 1.0* rand()/RAND_MAX;for(int j = 0; j < num_pop; j++){ pick = pick - fitness_prob[j];if(pick <= 0){index[i] = j;break;}}}for(int i = 0; i < num_pop; i++){for(int j = 0; j < len_chrom; j++){pop[i][j] = pop[index[i]][j];}fitness[i] = fitness[index[i]];}
}//交叉操作
void Cross(double pop[num_pop][len_chrom]){for(int i = 0; i < num_pop; i++){              //随机选择两个个体进行交叉double pick1 = 1.0*rand()/RAND_MAX;double pick2 = 1.0*rand()/RAND_MAX;int choice1 = (int)(pick1*num_pop);        //第一个随机选取的染色体序号int choice2 = (int)(pick2*num_pop);        //第二个随机选取的染色体序号while(choice1 > num_pop - 1){              //防止选取位置过界pick1 = 1.0*rand()/RAND_MAX;choice1 = (int)(pick1*num_pop); }while(choice2 > num_pop - 1){pick2 = 1.0*rand()/RAND_MAX;choice2 = (int)(pick2*num_pop);}double pick = 1.0*rand()/RAND_MAX;   //用于判断是否进行交叉操作if(pick > p_cross)continue;pick = 1.0*rand()/RAND_MAX;int pos = (int)(pick*len_chrom);while(pos > len_chrom - 1){                 //防止越界double pick = 1.0*rand()/RAND_MAX;pos = (int)(pick*len_chrom); }double r = 1.0*rand()/RAND_MAX;       //交叉开始double v1 = pop[choice1][pos];double v2 = pop[choice2][pos];pop[choice1][pos] = r*v2 + (1-r)*v1;pop[choice2][pos] = r*v1 + (1-r)*v2;         //交叉结束}
}//变异
void Mutate(double pop[num_pop][len_chrom]){for(int i = 0; i < num_pop; i++){double pick = 1.0*rand()/RAND_MAX;  //随机选择一个染色体进行变异int choice = (int)(pick*num_pop);while(choice > num_pop - 1){                 //防止越界pick = 1.0*rand()/RAND_MAX;choice = (int)(pick*num_pop);  }pick = 1.0*rand()/RAND_MAX;          //用于决定该轮是否进行变异if(pick > p_mutate)continue;pick = 1.0*rand()/RAND_MAX;int pos = (int)(pick*len_chrom);while(pos > len_chrom-1){                  //防止越界pick = 1.0*rand()/RAND_MAX;pos = (int)(pick*len_chrom);}pop[i][pos] = 1 - pop[i][pos];             //变异规则}
}//主函数
int main(){time_t start, finish;start = clock();                    //开始时间srand((unsigned)time(NULL));        //初始化随机数种子initial();                          //种群初始化double * best_fit_index = min(fitness);     //初始时最优适应度的个体和它的适应度int best_index =(int)(*best_fit_index);     //转换为intgbest = *(best_fit_index+1);                //最优适应度gbest_index = 0;                            //取得最优适应度的迭代次数,初始为0average_best[0] = sum(fitness)/num_pop;     //初始化平均适应度for(int i = 0; i < len_chrom; i++){        //将初始时的具有最优适应度的个体的位置传给gbest_posgbest_pos[i] = pop[best_index][i];}for(int i = 0; i < num_pop; i++){       //迭代开始Select(pop);                        //选择Cross(pop);                         //交叉Mutate(pop);                        //变异for(int j = 0; j < num_pop; j++){   //计算此代的每个个体的适应度fitness[j] = fit(pop[j]);}double sum_fit = sum(fitness);      //此代个体的适应度总和average_best[i + 1] = sum_fit / num_pop;   //此代的个体平均适应度double * arr = min(fitness);        //新一代最优个体二维数组double new_best = *(arr+1);         //新一代最优值int new_best_index = (int)(*arr);   //新一代最优值序号if(new_best < gbest){               //若新一代个体最优适应度更小,那么更新gbest = new_best;for(int j = 0; j < len_chrom; j++){gbest_pos[j] = pop[new_best_index][j];}gbest_index = i + 1;}}finish = clock();                   //结束时间double duration = ((double)(finish-start))/CLOCKS_PER_SEC;    //程序运行时间,以秒为单位printf("程序计算耗时:%lf秒\n.",duration);printf("遗传算法进化了%d次,最优值为:%lf,最优值在第%d代取得,此代的平均最优值为%lf.\n",num_iter,gbest,gbest_index,average_best[gbest_index]);return 0;
}

 

这篇关于初识遗传算法(Genetic Algorithm)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/532826

相关文章

Linux操作系统 初识

在认识操作系统之前,我们首先来了解一下计算机的发展: 计算机的发展 世界上第一台计算机名叫埃尼阿克,诞生在1945年2月14日,用于军事用途。 后来因为计算机的优势和潜力巨大,计算机开始飞速发展,并产生了一个当时一直有效的定律:摩尔定律--当价格不变时,集成电路上可容纳的元器件的数目,约每隔18-24个月便会增加一倍,性能也将提升一倍。 那么相应的,计算机就会变得越来越快,越来越小型化。

docker学习系列(一)初识docker

在第一版本上线之后公司,我们决定将之前使用的开源api文档项目转移到本公司的服务器之上,之前用的是showdoc,showdoc利用的是php技术,作为java程序员表示需要快速部署php环境以及apach容器都需要时间,所以采用第二种方法,即利用docker进行快速部署(虽然学习成本也不比php少)。 一、docker简介 docker的官网是https://www.docker.com,

框架template初识

框架初识 框架就是一个别人帮我们搭好的舞台,造好了很多现成的工具供我们使用,让开发过程更快速、简洁。 Gin框架介绍 Gin 是一个用 Go (Golang) 编写的 HTTP Web 框架。 Gin是一个用Go语言编写的web框架。它是一个类似于martini 但拥有更好性能的API框架, 由于使用了 httprouter,速度提高了近40倍。 第一个Gin示例 package mai

【数据结构】--初识泛型

1. 包装类 在Java中,由于基本类型不是继承自Object,为了在泛型代码中可以支持基本类型,Java给每个基本类型都对应了一个包装类型。 1.1 基本数据类型和对应的包装类 除了 Integer 和 Character, 其余基本类型的包装类都是首字母大写。 1.2 (自动)装箱和(自动)拆箱 装箱(装包): 把 基本数据类型 变为 包装类类型 的过程 叫做装箱。 反汇编指

初识Linux · 进度条

目录 前言: 1 缓冲区和回车换行 2 进度条 前言: 我们目前学习了些许知识,已经足够支持我们写一个非常非常小的项目了,即进度条,相信大家都有过下载游戏,等待游戏更新完成的时候,那么此时就有一个进度条,代表着游戏的更新进度,那么我们今天就来模拟实现这个过程,在此之前,我们需要一些预备知识。 1 缓冲区和回车换行 回车换行?是的,你没有看错,相信不少人对换行有一定的误解,我们

Linux初识线程

前言 前面在介绍进程的时候,说过进程的内核表述是"进程是承担资源分配的基本实体",但是我们至今都没有介绍如何理解他?本期我们就会介绍! 目录 前言 一、再谈地址空间和页表 1、OS对物理内存的管理 • 为什么4KB是OS进行I/O的基本单位? 2、再谈页表 • 二级页表 • 如何找到一个变量的所有字节? • 虚拟地址是如何转为物理地址的? • 理解动态内存管理 • 为什么对

【tensorflow 使用错误】tensorflow2.0 过程中出现 Error : Failed to get convolution algorithm

如果在使用 tensorflow 过程中出现 Error : Failed to get convolution algorithm ,这是因为显卡内存被耗尽了。 解决办法: 在代码的开头加入如下两句,动态分配显存 physical_device = tf.config.experimental.list_physical_devices("GPU")tf.config.experiment

初识命名空间

1.创建两个命名空间 ip netns add host1 ip netns add host2 2.  查看命名空间 ip netns ls 3 、 创建veth ip -netns host1 link add veth0 type veth peer name host1-peer 4、 查看命名空间接口  ip -netns host1 address 5、 把hos

Linux进程初识:OS基础、fork函数创建进程、进程排队和进程状态讲解

目录 1、冯诺伊曼体系结构 问题一:为什么在体系结构中存在存储器(内存)? 存储单元总结: 问题二:为什么程序在运行的时候,必须把程序先加载到内存? 问题三:请解释,从你登录上qq开始和某位朋友聊天开始,数据的流动过程。 2、操作系统 2.1操作系统的概念: 我们首先要明白什么是管理: 2.2为什么要有操作系统? 2.3操作系统如何保证稳定和安全呢?(利用系统调用函数解决)

初识string(一)and内存管理

对类和对象的补充:缺省参数在函数定义中从右向左依次赋值,如果从右向左有一个参数没有赋值缺省参数,则左边的变量就不能在赋缺省参数,类中的变量可以赋缺省参数并且没有限制。 在类定义中我们总是看到函数后加const。这其实是调用常量类对象或类对象的意思。 一、引言 俗话说“工欲善其事,必先利其器。”一门语言创造的初衷一定是为了交流和记录重要的事。计算机语言肯定也不例外,虽然计算机语言创造的初衷单纯