网站模板包含哪些内容,网站建设和维护视频,南昌网站建设公司市场,天元建设集团有限公司上班时间文章目录 前言遗传算法算法思想生物的表示初始种群的生成下一代种群的产生适应度函数轮盘赌交配变异混合产生新种群 停止迭代的条件遗传算法在01背包中的应用01背包问题介绍01背包的其它解法01背包的遗传算法解法生物的表示初始种群的生成下一代种群的产生适应度函数轮盘赌交配… 文章目录 前言遗传算法算法思想生物的表示初始种群的生成下一代种群的产生适应度函数轮盘赌交配变异混合产生新种群 停止迭代的条件遗传算法在01背包中的应用01背包问题介绍01背包的其它解法01背包的遗传算法解法生物的表示初始种群的生成下一代种群的产生适应度函数轮盘赌交配变异混合产生新种群 停止迭代的条件 一个优化代码 遗传算法的优缺点优点可以全局搜索适用范围广 缺点参数调节困难可能陷入局部最优 遗传算法的时间复杂度 总结 前言
遗传算法是美国教授Holland于1975年提出的一种基于模仿生物遗传学的优化算法。这种算法很难得到问题的精确答案但是能够在允许的时间复杂度内得到一个较优的答案。常用来解决一些目前不存在多项式算法的问题如旅行商问题TSP问题背包问题。
遗传算法
算法思想
我们假设在自然界中存在一个种群。根据达尔文的生物进化论生物会进行交配和变异从而慢慢进化。而我们的目标就是让这群生物往我们希望的方向进化进化得越来越优秀。而通过数代进化之后最优秀的那个个体就是我们问题的解。
生物的表示
在实际问题中我们用一个n位的01二进制串来表示一个生物。每一位取0或1表示一个信息。比如在01背包问题中一共有n个物品。可以用第i位取1表示取第i个物品取0表示不取第i个物品。这样一个方案就可以用一个生物来表示。一个种群包含很多个生物于是一个种群可以理解为很多个方案。而我们的目标就是要选出最优的一个方案。
初始种群的生成
初始种群的生成可以用随机数来生成。每一位随机取0或1就可以生成初始种群。当然这样生成的初始生物可能不太好我们可以通过贪心思想等生成一些较为优良的初始生物以提升算法准确度。
下一代种群的产生
生成完初始种群之后我们需要生成下一代种群。为了比较生物的优劣我们需要定义适应度函数。
适应度函数
适应度函数是根据实际问题自己定义的一个函数较优的方案具有较高的适应度较差的方案拥有较低的适应度。本文用 f ( x i ) f(x_i) f(xi)表示第i个生物的适应度。
轮盘赌
为了产生下一代我们需要选择两个生物作为父母使其进行交配。那么如何选择生物呢常用的一个方法是轮盘赌。即第i个生物被选中的概率为 f ( x i ) ∑ i 1 n f ( x i ) \frac{f(x_i)}{\sum_{i1}^{n}{f(x_i)}} ∑i1nf(xi)f(xi)。为什么这个方法被称为轮盘赌呢是因为其指导思想是将每个生物按照其适应度在轮盘上分配位置适应度越大分配到的位置越大。然后转动轮盘指针指到哪里就抽到哪个生物。这样做的有点在于适应度越高的生物被选中的概率越大越有可能保留优良基因。让优秀的基因传承下去才能使得种群总体适应度越来越高。
交配
我们通过轮盘赌选择了两个生物现在要让它们生成一个新的生物。也就是说我们要用两个长度为n的01串 x i x_i xi和 x j x_j xj生成一个新的长度为n的01串。我们的做法是产生一个1~n-1的随机数记为y。用 x i x_i xi的1~y位和 x j x_j xj的y1~n位组成一个新的01串。这个新的01串就是 x i x_i xi和 x j x_j xj的孩子。
变异
由于初始种群的随机度较高可能无法通过交配产生一些生物。为了丰富生物多样性我们需要以适当的概率对生物进行变异。通常采用的变异方法是以固定的变异率对生物的某一位进行取反操作。一般变异率保持在0.2左右。
混合产生新种群
通过交配和变异我们产生了一个新个体。下一代的新种群由这一代的部分个体和下一代的新个体按某种比例混合产生。一般是由20%的这一代生物和80%的新产生 的生物组成。
停止迭代的条件
随着一代一代的新种群产生生物的总体适应度也将越来越高。我们需要一个停止迭代的条件一般有两种。第一种是按照固定的迭代次数进行比如10000次。第二种是比较相邻两代中的平均适应度如果平均适应度的增加小于一个我们规定的值那么就可以停止迭代了。我们选取最后一代中最优秀的生物作为我们的最终方案。
遗传算法在01背包中的应用
我们举个具体的例子来看一看遗传算法在实际问题中的应用。
01背包问题介绍
假设背包的容量为m有n个物品第i物品的重量为 w [ i ] w[i] w[i]价值为 v [ i ] v[i] v[i]我们要从中选取一些物品放入背包在不超过背包容量的前提下使装入背包的物品总价值最高。
01背包的其它解法
01背包的标准解法是利用动态规划算法进行解决时间复杂度为 O ( n m ) O(nm) O(nm)空间复杂度为 O ( m ) O(m) O(m)。但是使用动态规划算法的前提是 m m m为整数且 w [ i ] w[i] w[i]均为整数。对于更一般的01背包问题目前没有找到多项式时间的解法是一个NP难问题。而对于这样一类问题遗传算法就非常适用。遗传算法虽然不能给出一个精确解但是能在可接受的时间范围内给出一个较优的答案。
01背包的遗传算法解法
通过遗传算法可以让算法的时间复杂度与背包容量 m m m无关。并且可以应对 m m m不是整数的情况。
生物的表示
我们用 c [ i ] c[i] c[i]表示一个01串代表第i个生物。 c [ i ] [ j ] c[i][j] c[i][j]表示第i个生物的第j位是1还是0。对应到01背包问题就表示第i种方案的第j个物品选或不选。
初始种群的生成
我们首先对于所有物品按照性价比即 v [ i ] / w [ i ] v[i]/w[i] v[i]/w[i])从高到低进行排序。然后我们随机生成一个长度为n的01串。由于随机生成0和1的方案不一定能满足背包容量的要求。所以我们基于贪心思想把一个随机01串改造成符合背包容量的01串。在产生的随机方案的基础上从性价比最高的物品开始如果随机方案选了且选择之后背包容量没有超则选取该物品否则不选该物品。但是通过这种方式背包可能有剩余容量于是我们再次从性价比最高的物品开始如果我们的方案没有选择它且选择它之后没有超出背包容量那么我们就把它加入背包。通过这种基于贪心的选择方式可以生成一系列较优的初始方案。这些方案组成了初始种群。
下一代种群的产生
适应度函数
每个生物的适应度应该与该方案的总价值相关总价值越大适应度越高。我们一般有几种不同的适应度函数。第一种直接用总价值来表示适应度即 f ( x i ) ∑ j 1 n c [ i ] [ j ] ∗ v [ j ] f(x_i)\sum_{j1}^{n}{c[i][j]*v[j]} f(xi)∑j1nc[i][j]∗v[j]。第二种为了使后面的轮盘赌能更大程度区分优秀方案和劣质方案用该方案的总价值减去这一代方案中最低的总价值来表示适应度即 f ( x i ) ∑ j 1 n c [ i ] [ j ] ∗ v [ j ] − m i n { ∑ j 1 n c [ i ] [ j ] ∗ v [ j ] } f(x_i)\sum_{j1}^{n}{c[i][j]*v[j]}-min\{\sum_{j1}^{n}{c[i][j]*v[j]}\} f(xi)∑j1nc[i][j]∗v[j]−min{∑j1nc[i][j]∗v[j]}。
轮盘赌
我们通过轮盘赌的方法选取两个方案来产生下一个方案。在轮盘赌中每个方案被选择的概率为 f ( x i ) ∑ i 1 n f ( x i ) \frac{f(x_i)}{\sum_{i1}^{n}{f(x_i)}} ∑i1nf(xi)f(xi)。通过生成随机数来选择两个方案。
交配
通过轮盘赌选择了两个方案假设为第 a a a个和第 b b b个方案假设新产生的方案为d在1~n-1中产生的随机数为 z z z那么 d [ j ] { c [ a ] [ j ] 1 ≤ j ≤ z c [ b ] [ j ] z 1 ≤ j ≤ n d[j]\begin{cases} c[a][j] 1\leq j \leq z \\ c[b][j] z1 \leq j \leq n \end{cases} d[j]{c[a][j]c[b][j]1≤j≤zz1≤j≤n 如果该方案不满足背包容量的要求就重新用轮盘赌选择两个方案重新生成新的方案。
变异
我们设定变异率为一个常数对新产生的方案进行变异。我们生成一个0~1的随机数若这个随机数小于变异率那么就进行变异。我们再生成一个1~n的随机数 z z z表示对新方案的第 z z z位进行取反操作。即 d [ j ] { d [ j ] j ̸ z 1 − d [ j ] j z d[j]\begin{cases} d[j] j\notz \\ 1-d[j] jz \end{cases} d[j]{d[j]1−d[j]jzjz
混合产生新种群
我们通过轮盘赌将20%的这一代的方案和80%的新产生的方案混合在一起组成新一代的方案。值得说明的是需要将每一代产生的最优方案记录下来。
停止迭代的条件
我们固定一个迭代次数运行完之后我们记录的最优秀的方案就是我们程序的运行结果。由于程序的随机性较高所以一般重复多次运行程序取最优结果作为我们的最终答案。对于迭代次数、变异率、种群大小等常数需要根据实际情况灵活选取在保证准确率的情况下使得程序运行效率较高。
一个优化
由于算法随机性较高有一些非常优秀的方案可能不一定能够保存下来。所以我们采用优先队列人为把每一代中最优秀的两个方案保存下来放到下一代中。对于这个问题也有很多人在研究可能也存在很多更合理的优化。这里只是选取了一个能够大大提升算法准确性的优化。
代码
下面是我用遗传算法写的01背包问题的C代码
#includecstdio
#includeiostream
#includestdlib.h
#includetime.h
#includequeue
#includevector
using namespace std;
int n,m,w[10005],v[10005];
vectorbool c[105];
double d[105];
const int populationSize 20;//设定种群大小为20
const int generations 10000;//设定迭代次数为10000
double mutationRate 0.3;//设定变异率为0.3
vectorbool q;
int num0;
bool check(vectorbool a)//对于一个方案验证其是否超过背包容量
{int s0;for (int i0;in;i) sa[i]*w[i];return sm;
}
double jisuan(vectorbool a)//计算给定方案的总价值
{if (!check(a)) return 0;//若该方案超出背包容量则价值为0 double s0,t0;for (int i0;in;i) {sa[i]*v[i];ta[i]*w[i];}return s;
}
vectorbool jiaocha(vectorbool a,vectorbool b)//对于两个方案进行交叉
{int xrand()%n;vectorbool t;for (int i0;ix;i) t.push_back(a[i]);for (int ix;in;i) t.push_back(b[i]);return t;
}
void bianyi(vectorbool a)//对于一个方案进行变异
{double xrand()/double(RAND_MAX);double y; if (xmutationRate) {yrand()%n;a[y]!a[y];}
}
int lunpandu()//通过轮盘赌选出一个方案的编号
{double xrand()/double(RAND_MAX);for (int i1;ipopulationSize;i){if (d[i]x) return i;}return populationSize;
}
struct Compare { //根据方案价值的高低来在优先队列中排序 bool operator()(vectorbool a,vectorbool b) { return jisuan(a) jisuan(b); }
};
int main()
{srand(time(NULL));cinmn;//m表示背包容量n表示物品数量 for (int i0;in;i){cinw[i]v[i];//w[i]表示物品重量v[i]表示物品价值 }for (int i0;in;i)//对所有物品关于性价比从高到低进行排序 {for (int j0;jn-i;j){if ((double)v[j]/w[j](double)v[j1]/w[j1]){int tv[j];v[j]v[j1];v[j1]t;tw[j];w[j]w[j1];w[j1]t;}}}int ans0;for (int k1;k10;k) //程序重复运行10次 {num0; srand(time(NULL));for (int i1;ipopulationSize;i)//生成初始种群 {c[i].clear();for (int j0;jn;j) c[i].push_back(rand()%2);//生成随机01串 int weight0;for (int j0;jn;j) {if (weightc[i][j]*w[j]m) weightc[i][j]*w[j];//若加入该物品后背包重量没有超就加入该物品 else c[i][j]0;}for (int j0;jn;j)//背包还有剩余空间可以再加入一些物品 {if (c[i][j]0weightw[j]m) {c[i][j]1;weightw[j];}}}priority_queuevectorbool, vectorvectorbool , Compare p;//定义优先队列 vectorbool x;for (int i1;igenerations;i){while (!p.empty()) p.pop();//清空优先队列 double s0,zuixiaozhi1000000;bool b0;for (int j1;jpopulationSize;j) {if (j1) //把上一代最优的方案加入优先队列 {p.push(c[j]);b1;}if (b1c[j]!p.top()) //把上一代次优的方案加入优先队列 {p.push(c[j]); b0;}d[j]jisuan(c[j]);if (d[j]zuixiaozhi) zuixiaozhid[j];sd[j];}s-zuixiaozhi*populationSize;for (int j1;jpopulationSize;j) d[j]d[j-1](d[j]-zuixiaozhi)/s;//d[j]表示第j个方案在轮盘赌中被选中的概率 for (int j1;jpopulationSize;j)//产生下一代 {int x1lunpandu(),x2lunpandu();//根据轮盘赌选择两个方案 xjiaocha(c[x1],c[x2]);//两个方案进行交叉 bianyi(x);//对新得到的方案进行变异 p.push(x);//把新得到的方案加入优先队列 }for (int j1;jpopulationSize!p.empty();j)//把较优的一些方案作为下一代从而继续产生下下代 {c[j]p.top();p.pop();}}for (int i1;ipopulationSize;i)//把最优的方案记录下来 {if (check(c[i])){coutk jisuan(c[i])\n;//输出第k次的最优值 if (jisuan(c[i])ans) ansjisuan(c[i]);break;}}}coutans;//输出10次的最优值
}遗传算法的优缺点
优点
可以全局搜索
由于遗传算法的多样性搜索性质它可以在搜索空间内找到许多可能的解于是可以在较短时间内全局最优或近似最优的解。
适用范围广
作为一种优化算法它的适用范围非常广可以基于初始解产生近似最优解。而且可以人为定义适应度可以应用于一些难以定量的问题。
缺点
参数调节困难
该算法中有多个参数比如种群大小迭代次数变异率等。如何通过修改参数使得能取得更优秀的解是一个比较困难的问题。
可能陷入局部最优
若父代的相似度较高则产生的子代相似度也很可能较高从而使得陷入局部最优。
遗传算法的时间复杂度
设迭代次数为G种群规模为P01串长度为n则不加任何优化的遗传算法的时间复杂度为 O ( G P n ) O(GPn) O(GPn)。G和P都是人为控制的参数。通过这种方法把原来的 O ( 2 n ) O(2^n) O(2n)的时间复杂度降为了关于n的线性表达式这已经是一个极大的进步了。
总结
遗传算法主要应用于一些不存在多项式算法的问题使得在较短时间内能够得到较优的答案。但要得到真正最优的解还是有一定困难的。遗传算法在数学建模方面也有着广泛的应用比如用于函数的求最值等问题。
