遗传算法启发式优化算法

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

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

GA流程图
Created with Rapha?l 2.1.0 初始化个体评价选择、交叉、变异是否满足终止条件? End yes no GA算法基本过程

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

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

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

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

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

其中单点交叉是最常用的交叉算法。在操作时首先设定一个交叉点，将两个个体在该点之后的基因结构进行互换，从而形成两个新的个体。例如：
个体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 新个体
变异

实值变异
二进制变异

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

遗传算法的初始解设置为一个群体，搜索覆盖面广，不易陷入局部最优；
变异部分使得算法有一定概率跳出局部最优；
遗传算法可同时对多个可行解进行实用性评估，算法容易并行；
具有自组织、自适应、自学习性。算法利用自身组织架构进行搜索，适应度大的个体具有较高存活率，指导了最优解的搜索方向。

算法的经典应用

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

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

#include #include #include #include#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); //转换为int gbest = *(best_fit_index+1); //最优适应度 gbest_index = 0; //取得最优适应度的迭代次数，初始为0 average_best[0] = sum(fitness)/num_pop; //初始化平均适应度 for(int i = 0; i < len_chrom; i++){//将初始时的具有最优适应度的个体的位置传给gbest_pos gbest_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; }