当前位置:   article > 正文

遗传算法学习与C语言实现(函数极值)_遗传算法c语言

遗传算法c语言

1概念:

遗传算法是进化算法的一种,用来解决最优化的搜索算法。一般用于函数优化,组合优化(NP完全问题如0-1背包问题,最短路径问题等)。其核心思想是达尔文优胜劣汰适者生存的思想,一个种群在自然界中不断繁衍,将适合环境的优良性状保留下来,而因为小概率发生的基因突变而出现的优秀性状也能保留至下一代。

运用在解决问题的时候,便可参照这种思想:首先随机生成若干对解,使用一个符合问题的评价标准来检验这些解,选择适应度高的解,衍生出适应度更高的解,如此反复,直到得到近似最优解。

2算法设计:

遗传算法需要具备,一个基本函数:适度函数;三个基本操作:选择,交叉,突变。其流程具体如下:初始化种群->循环(评价种群中个体的适应度->以比例原则选择产生下一个种群->改变该种群即交叉和变异)->直到停止循环的条件满足。

3遗传算法名词:

群体规模:种群中染色体个体的数目

编码:对问题集进行转化,最常用的编码技术是二进制编码,具有简单易行,符合最小字符集编码原则,便于用模式定理分析的有点。

适应度函数:用来评价个体的优劣,求个体的适应度,需要根据具体问题进行构造。

算子选择:在挑选个体的时候遵循的方法,有“轮盘法”、“竞标赛法”、“线性排序法”。其中“线性排序法”容易只挑选当前群体中分数最高的个体,会使收敛速度太快,造成“早熟”现象,从而得出区域最优解而不是全局最优解。而“轮盘法”和“竞标赛法”属于按比例原则选择下一代的方法,效果较好。

交叉:常用的是单点交叉,即随机选择两个染色体当中某段基因进行交换,形成新的染色体。模拟自然界当中的染色体交叉互换。

交叉率:控制交叉操作的使用频率,交叉操作可以加速收敛,达到最优解区域,因此一般取较大的交叉率,但交叉率太大容易造成过早收敛。

变异:随机选择某条染色体的某个基因进行改变,二进制编码下的方法为0à1,1à0的操作。模拟自然界的基因突变。

变异率:控制变异操作的概率,一般比较低。

终止条件:结束迭代的条件。一般有,进化次数限制、计算耗费的资源限制、一个个体已经满足最优值得条件、不再有新的个体产生等。


简单实例编码实现:

函数为y=x2+5的最大值,0<=x<=31。

  • 编码及初始种群的产生

编码采用二进制编码,初始种群采用矩阵的形式,每一行表示一个染色体,每一个染色体由若干个基因组成。关于染色体的长度,可以根据具体情况而定,问题中x的取值为32个数,所以染色体的长度可以取5位,即25=32。若是所取得染色体长度越长,表示解空间搜索范围越大,对应的是待搜索的X范围越大。代码中btod()函数为二进制转十进制函数。初始种群采用随机的方式生成四个染色体,结构如下图:

No

0

1

2

3

4

Value

1

0

1

0

0

1

9

2

1

0

1

1

0

22

3

1

0

1

0

0

20

4

1

1

1

1

0

30

其中第一列为染色体编号,第二列到第六列为随机产生的0和1组成的二进制编码,第七列为二进制编码代表的十进制的值。

  • 适应度函数

一般情况下,染色体(也叫个体,或一个解)的适应度函数为目标函数的线性组合。本文直接以目标函数作为适应度函数。即每个染色体的适应度值就是它的目标函数值,f(x)=x2 + 5。

  • 选择算子

初始种群产生后,要从种群中选出若干个体进行交叉、变异,那么如何选择这些个体呢?选择方法就叫做选择算子。一般有轮盘赌法、锦标赛选择法、排序法等。本文采用轮盘赌法来选择,步骤如下:(1)计算出每个染色体的适应度f(i=1,2,…,N),N为染色体总数;(2)计算出每个染色体被遗传到下一代的概率:Pxi=f(xi)j=0nf(xj); (3)计算出每个染色体的累计概率:Qi=i=1nPxi; (4)在[0,1]区间内产生一个均匀分布的随机数r;(5)若r<q[1],则选择个体1,否则,选择个体k,使得:q[k-1]<r≤q[k] 成立;(6)重复(4)(5)共N次。

染色体

适应度

选择概率

累计概率

选中次数

01001

86

0.045623

0.045623

0

10110

489

0.259417

0.305040

1

10100

405

0.214851

0.519894

1

11110

905

0.480106

1.000000

2

 

  • 交叉算子

那么接下来就要对新种群中选出的两个个体进行交叉操作,一般的交叉方法有单点交叉、两点交叉、多点交叉、均匀交叉、融合交叉。方法不同,效果不同。本文采用最简单的单点交叉。交叉点随机产生。但是交叉操作要在一定的概率下进行,这个概率称为交叉率,一般设置为0.5到0.95之间。通过交叉操作,衍生出子代,以补充被淘汰掉的个体。

No

0

1

2

3

4

Value

1

1

1

1

1

0

30

2

1

0

1

0

0

20

3

1

0

1

1

0

22

4

1

1

1

1

0

30

在第三基因位置进行交叉后,产生的新个体组成的新种群如下:

No

0

1

2

3

4

Value

1

1

1

1

1

0

30

2

1

0

1

1

0

32

3

1

0

1

1

0

22

4

1

1

1

0

0

28

 

  • 变异

变异就是对染色体的基因进行变异,使其改变原来的结构(适应值也就改变),达到突变进化的目的。变异操作也要遵从一定的概率来进行,一般设置为0到0.5之间,即以小概率进行基因突变。这符合自然规律。本文的变异方法直接采取基因位反转变异法,即0变为1,1变为0。要进行变异的基因位的选取也是随机的。

  • 终止规则

遗传算法是要一代又一代更替的,那么什么时候停止迭代呢?这个规则就叫终止规则。一般常用的终止规则有:。一般有,进化次数限制、计算耗费的资源限制、一个个体已经满足最优值得条件、不再有新的个体产生等方法。本文采用进化数来限制。

代码如下:

  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. #include <math.h>
  6. #include <iostream>
  7. #define MAX_SIZE 5 //染色体二进制编码位数
  8. #define MAX_PAIR 4 //染色体条数
  9. typedef struct Chrom //结构体类型,为单个染色体结构
  10. {
  11. short int bit[MAX_SIZE];//一共5bit来对染色体进行编码,其中1位为符号位,取值范围0~31
  12. int fit;//适应度
  13. double rfit;//选择概率,即所占的百分比
  14. double cfit;//累计概率
  15. }chrom;
  16. //定义将会用到的函数
  17. void evpop (chrom popcurrent[MAX_PAIR]);//进行种群的初始化
  18. int btod (chrom popcurrent);//二进制->十进制
  19. int fitness (int x);//计算适应度
  20. void pickchroms_Roulette (chrom popcurrent[MAX_PAIR],chrom popnext[MAX_PAIR]);//轮盘赌法算子选择
  21. void pickchroms_Ranking (chrom popcurrent[MAX_PAIR]);//冒泡排序算子选择
  22. void pickchroms_Tournament (chrom popcurrent[MAX_PAIR]);//锦标赛法算子选择
  23. void crossover (chrom popnext[MAX_PAIR]);//交叉操作
  24. void mutation (chrom popnext[MAX_PAIR]);//突变
  25. void mian_loop (chrom popcurrent[MAX_PAIR], chrom popnext[MAX_PAIR], int loop);//循环进行选择交叉变异
  26. double uniform (double a, double b, long int* seed);//产生a~b均匀分布的随机数
  27. int main()//主函数
  28. {
  29. chrom popcurrent[MAX_PAIR];//初始种群规模
  30. chrom popnext[MAX_PAIR];//更新后种群规模
  31. int loop, Max;
  32. printf("请输入迭代数:");
  33. scanf("%d",&loop);
  34. srand(time(0));
  35. printf("\n初始化种群为:\n");
  36. evpop(popcurrent);//初始化种群
  37. mian_loop(popcurrent, popnext, loop);//进行循环
  38. Max = btod(popcurrent[0]);//期望已完成收敛
  39. printf("\n最终结果为:%d\n",Max);
  40. system("pause");
  41. return 0;
  42. }
  43. void evpop(chrom popcurrent[MAX_PAIR]) //函数:随机生成初始种群:
  44. {
  45. int i, j, value;
  46. int random;
  47. double sum=0;
  48. for(j=0; j < MAX_PAIR ;j++) //从染色体的第1个基因到第6个
  49. {
  50. for(i=0; i < MAX_SIZE; i++)
  51. {
  52. random=rand(); //产生一个随机值
  53. random=random%2; //随机产生0或1
  54. popcurrent[j].bit[i]=random; //随机产生染色体上每一个值
  55. }
  56. value=btod(popcurrent[j]); //二进制->十进制
  57. popcurrent[j].fit=fitness(btod(popcurrent[j])); //计算染色体适应度值
  58. sum = sum + popcurrent[j].fit;
  59. printf("popcurrent[%d]=%d%d%d%d%d value=%d fitness = %d\n",j,popcurrent[j].bit[0],popcurrent[j].bit[1],popcurrent[j].bit[2],popcurrent[j].bit[3],popcurrent[j].bit[4],value,popcurrent[j].fit);
  60. //输出整条染色体的编码情况
  61. }
  62. //计算适应值的百分比,改参数是在用轮盘赌选择法时需要用到的
  63. for(j = 0; j < MAX_PAIR; j++)
  64. {
  65. popcurrent[j].rfit = popcurrent[j].fit/sum;
  66. popcurrent[j].cfit = 0;//初始化
  67. }
  68. printf("\n");
  69. }
  70. int btod(chrom popcurrent) //二进制->十进制
  71. {
  72. int d = 0;
  73. for(int i = 0; i < MAX_SIZE; i++)
  74. {
  75. d = d + popcurrent.bit[i] * pow(2, MAX_SIZE-1-i);
  76. }
  77. return d;
  78. }
  79. int fitness(int x)//求个体的适应度
  80. {
  81. int fit = x * x + 5;
  82. return fit;
  83. }
  84. //基于轮盘赌法进行染色体选择(算子选择)
  85. void pickchroms_Roulette (chrom popcurrent[MAX_PAIR],chrom popnext[MAX_PAIR])//计算概率
  86. {
  87. int men;
  88. int i, j;
  89. double p; //生成4个0~1的随机值
  90. double sum = 0.0; //find the total fitness of the population
  91. long int seed = 13579;
  92. for(men = 0; men < MAX_PAIR; men++)//计算总适应度
  93. {
  94. sum = sum + popcurrent[men].fit;
  95. }
  96. for(men = 0; men < MAX_PAIR; men++)//计算选择概率
  97. {
  98. popcurrent[men].rfit = popcurrent[men].fit / sum;
  99. }
  100. //计算累计概率
  101. popcurrent[0].cfit = popcurrent[0].rfit;
  102. for( men = 1; men < MAX_PAIR; men++)
  103. {
  104. popcurrent[men].cfit = popcurrent[men-1].cfit + popcurrent[men].rfit;
  105. }
  106. for(i=0;i<MAX_PAIR;i++)//输出累计概率(调试用)
  107. {
  108. printf("popcurrent[%d].cfit=%f\n",i,popcurrent[i].cfit);
  109. }
  110. for(i = 0; i < MAX_PAIR; i++)//生成若干个0~1随机数,根据累计概率进行选择(轮盘赌法核心)
  111. {//产生0~1之间的随机数
  112. p =uniform(0, 1, &seed);//通过函数生成0~1之间均匀分布的数字
  113. //p = rand() * 1.0 / (RAND_MAX + 1.0);
  114. printf("random is %f\n",p);//输出随机数(调试用)
  115. if (p < popcurrent[0].cfit)
  116. {
  117. popnext[i] = popcurrent[0];
  118. }
  119. else
  120. {
  121. for(j = 0; j < MAX_PAIR - 1 ; j++)
  122. {
  123. if(popcurrent[j].cfit <= p && p < popcurrent[j+1].cfit)
  124. {
  125. popnext[i] = popcurrent[j + 1];
  126. }
  127. }
  128. }
  129. popnext[i].fit=fitness(btod(popnext[i]));//计算下一代染色体的适应度
  130. }
  131. for(i = 0; i < MAX_PAIR ; i++)//打印轮盘赌法选择出的下一代染色体
  132. {
  133. printf("popnext[%d]=%d%d%d%d%d fitness=%d\n",i,popnext[i].bit[0],popnext[i].bit[1],popnext[i].bit[2],popnext[i].bit[3],popnext[i].bit[4],popnext[i].fit);
  134. }
  135. }
  136. //基于冒泡排序法进行染色体选择(算子选择)
  137. void pickchroms_Ranking(chrom popcurrent[MAX_PAIR])
  138. {
  139. //
  140. }
  141. //基于锦标赛法进行染色体选择(算子选择)
  142. void pickchroms_Tournament (chrom popcurrent[MAX_PAIR])
  143. {
  144. //
  145. }
  146. //交叉操作
  147. void crossover(chrom popnext[MAX_PAIR])
  148. {
  149. double pc = 0.95;//进行交叉的概率
  150. double rpc = 0.0;//随机交叉
  151. int random;//交叉点
  152. int i;
  153. short int temp;
  154. //rpc = rand()%100*0.01;//产生0~1的两位小数
  155. //if (rpc <= 0.95)//以0.95的概率进行交叉操作
  156. //{暂时100%交叉
  157. random = rand()%5+1;//产生1~5的随机数,即交叉点位置
  158. //random = 2;
  159. //printf("\nCross point is %d\n",random);//输出交叉点,调试用
  160. for( i = MAX_SIZE - random ; i < MAX_SIZE; i++ )
  161. {
  162. //将染色体0与3号交叉
  163. temp = popnext[0].bit[i];
  164. popnext[0].bit[i] = popnext[3].bit[i];
  165. popnext[3].bit[i] = temp;
  166. temp = 0;//清零
  167. //将染色体1与2号交叉
  168. temp = popnext[1].bit[i];
  169. popnext[1].bit[i] = popnext[2].bit[i];
  170. popnext[2].bit[i] = temp;
  171. temp = 0;
  172. }
  173. //}
  174. for(i = 0; i < MAX_PAIR; i++)
  175. {
  176. popnext[i].fit=fitness(btod(popnext[i]));//更新适应度
  177. }
  178. for(i = 0; i < MAX_PAIR; i++)//输出交叉后的染色体
  179. {
  180. printf("CrossOver popnext[%d]=%d%d%d%d%d\n",i,popnext[i].bit[0],popnext[i].bit[1],popnext[i].bit[2],popnext[i].bit[3],popnext[i].bit[4]);
  181. }
  182. }
  183. //变异操作
  184. void mutation(chrom popnext[MAX_PAIR])
  185. {
  186. int random;
  187. int i, j, num;//第i个染色体的第j个基因
  188. random = rand() % 50;//产生0~49个随机数
  189. if (random == 25)//即2%的几率产生变异
  190. {
  191. i = rand() % 4;//对应某一个染色体
  192. j = rand() % 6;//对应染色体上的基因
  193. if (popnext[i].bit[j] == 0)
  194. popnext[i].bit[j] = 1;
  195. else
  196. popnext[i].bit[j] = 0;
  197. popnext[i].fit=fitness(btod(popnext[i]));//更新适应度
  198. }
  199. for(num = 0; num < 4; num++)//输出变异后的染色体
  200. {
  201. printf("chrom[%d]=%d%d%d%d%d value = %d fitness = %d\n",num,popnext[num].bit[0],popnext[num].bit[1],popnext[num].bit[2],popnext[num].bit[3],popnext[num].bit[4],btod(popnext[num]),popnext[num].fit);
  202. }
  203. }
  204. //循环函数
  205. void mian_loop (chrom popcurrent[MAX_PAIR], chrom popnext[MAX_PAIR], int loop)
  206. {
  207. int i, j;
  208. for(i = 0; i < loop; i++)
  209. {
  210. printf("第%d次迭代:\n",i);
  211. pickchroms_Roulette(popcurrent,popnext);//选择for(i = 0; i < MAX_PAIR ; i++)//打印轮盘赌法选择出的下一代染色体
  212. crossover(popnext);//交叉
  213. mutation(popnext);//变异
  214. for(j = 0; j < MAX_PAIR ; j++)//更新下一代
  215. {
  216. popcurrent[j] = popnext[j];
  217. }
  218. }
  219. }
  220. //产生a~b均匀分布的随机数
  221. double uniform (double a, double b, long int* seed)
  222. {
  223. double result;
  224. *seed = 2045 * (*seed) + 1;
  225. *seed = (*seed) % 1048576;
  226. result = (*seed) / 1048576.0;
  227. result = a + (b - a) * result;
  228. return result;
  229. }
  • 存在的问题

这次用C语言实现的代码基本完成了对遗传算法的实现,但还有改进的空间。包括:产生更加均匀的随机数,功能的模块化以降低耦合度,使代码更加通用能尽可能复用到解决其他问题的遗传算法代码中,完善其他两种算子算法的代码实现(排序法和锦标赛法)。还存在的问题包括:染色体个体数量选择太少,容易过早的达到平衡,即陷入局部最优解,即使暂时将交叉率设置为100%也无法解决。继续迭代无法再进行进化,只能寄希望于变异,但变异率一般设置的很低,代码中只有2%,就需要更大的迭代数才有可能继续进化。

本文参考:

 

https://blog.csdn.net/ljp1919/article/details/42425281

https://www.cnblogs.com/adelaide/articles/5679475.html

https://www.codeproject.com/Articles/10417/Genetic-Algorithm

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/798255
推荐阅读
相关标签
  

闽ICP备14008679号