devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

遗传算法入门例子和总结_遗传算法的ccons是什么

作者：小惠珠哦 | 2024-07-08 09:19:02

赞

踩

遗传算法的ccons是什么

目录:

  一.写在前面

  二.遗传算法概述

  三.一个简单问题描述

  四.C语言实现

 ---------------------------------------------------------------------

  一.写在前面

 下面的列子是摘自《遗传算法原理与应用》一书，具体PDF下载：http://download.csdn.net/source/1615358  我看了一遍，通俗易懂，很适合入门，有需要的朋友可以下载来看看 ：）,希望这篇文章对初学者有益 ,转载请注明出处

 二.遗传算法概述

遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解

基本组成为:

   a.编码(产生初始种群)

   b.适应度函数

   c.遗传算子(selection, crossover, mutation)

   d.运行参数

 

三.一个简单问题描述

为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各
    个主要执行步骤。
  
     例：求下述二元函数的最大值：

    (1) 个体编码
           遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种
       符号串。本题中，用无符号二进制整数来表示。
           因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它
       们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可
       行解。
           例如，基因型 X＝101110 所对应的表现型是：x＝[ 5，6 ]。
           个体的表现型x和基因型X之间可通过编码和解码程序相互转换。

(2) 初始群体的产生
          遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始
      群体数据。
         本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机
     方法产生。
          如：011101，101011，011100，111001
         
 (3) 适应度汁算
          遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传
       机会的大小。
          本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接
       利用目标函数值作为个体的适应度。

 (4)  选择运算
          选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代
      群体中。                   
本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中
     的数量。其具体操作过程是：
         •  先计算出群体中所有个体的适应度的总和  fi  ( i=1.2,…,M );
         •  其次计算出每个个体的相对适应度的大小 fi / fi ，它即为每个个体被遗传
             到下一代群体中的概率，
         •  每个概率值组成一个区域，全部概率值之和为1；
         •  最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区
             域内来确定各个个体被选中的次数。

(5)  交叉运算
        交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某
    两个个体之间的部分染色体。
       本例采用单点交叉的方法，其具体操作过程是：
       • 先对群体进行随机配对；
       • 其次随机设置交叉点位置；
       • 最后再相互交换配对染色体之间的部分基因。

(6)  变异运算
         变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进
     行改变，它也是产生新个体的一种操作方法。
        本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：
        • 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，
          其中的数字表示变异点设置在该基因座处；
        • 然后依照某一概率将变异点的原有基因值取反。

对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。

从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得
    到了明显的改进。事实上，这里已经找到了最佳个体“111111”。       
[注意]      
        需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，
   我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中
   有可能需要一定的循环次数才能达到这个最优结果。

 

 

 四.C语言实现

 

 

[cpp]  view plain copy
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <time.h>  
  4.   
  5.   
  6.   
  7. /The definiton of user data  
  8. #define Cmax 100   //certain maximal value  
  9. #define Cmin 0   //certain minimum value  
  10.   
  11. #define LENGHT1  3  //the chromosome length of 1st variable  
  12. #define LENGHT2  3  //the chromosome length of 2nd variable  
  13.   
  14. //总染体长度  
  15. #define CHROMLENGTH LENGHT1+LENGHT2   
  16. const int MaxGeneration = 100;  //最大代数  
  17. const int PopSize = 10;  //样本大小  
  18. const double Pc = 0.6; //交叉概率  
  19. const double Pm = 0.001; //变异概率  
  20.   
  21.   
  22.   
  23. // 数据结构定义///  
  24. struct Individual{  
  25.     char chrom[CHROMLENGTH + 1];  //一个个体的染色体  
  26.     double value;  //目标值  
  27.     double fitness;  //适应度  
  28. };  
  29.   
  30. int generation ;  //进化次数  
  31. int bestIndex;  //最好个体的下标  
  32. int worstIndex;  //最坏个体的游标  
  33.   
  34. Individual bestIndividual ;  //当前一代中的最好个体  
  35. Individual worstIndividual ;  ///当前一代中的坏个体  
  36. // best individual by now   
  37. Individual currentBest ;// 到目前为止的最好个体  
  38. Individual  population [PopSize]  ;//样本  
  39.   
  40.   
  41. ///  
  42. void generateInitialPopulation();  
  43. void generateNextPopulation();  
  44. void evalutePopulation();  
  45. long decomdeChromosome(char*, int, int);  
  46. void calculateObjectValue();  
  47. void calculateFitnessValue();  
  48. void findBestAndWorstIndividual();  
  49. void performEvolution();  
  50. void selectionOperator();  
  51. void crossoverOperator();  
  52. void mutationOperator();  
  53. void outputTextReport();  
  54. //  
  55.   
  56.   
  57. int main(){  
  58.     generation = 0;  
  59.     generateInitialPopulation();  
  60.     evalutePopulation();  
  61.     while (generation < MaxGeneration) {  
  62.         generation++;  
  63.         generateNextPopulation();  
  64.         evalutePopulation();  
  65.         performEvolution();  
  66.         outputTextReport();  
  67.     }  
  68.     return 0;  
  69. }  
  70.   
  71.   
  72. //  
  73.   
  74. //产生第一代样本/  
  75. void generateInitialPopulation() {  
  76.     int i, j;  
  77.     srand((unsigned)time(NULL));  
  78.     for (i = 0; i < PopSize; i++) {  
  79.         for (j = 0; j < CHROMLENGTH; j++) {  
  80.             population[i].chrom[j] = ((rand() % 10) < 5) ? '0' : '1';  
  81.         }  
  82.         population[i].chrom[CHROMLENGTH] = '/0';  
  83.     }  
  84.   
  85. }  
  86.   
  87.   
  88. 产生下一代样本 //  
  89. void generateNextPopulation() {  
  90.     selectionOperator();  
  91.     crossoverOperator();  
  92.     mutationOperator();  
  93. }  
  94.   
  95. //变异算子//  
  96. void mutationOperator() {  
  97.     int i, j;  
  98.     double p;  
  99.     // bit mutation  
  100.     for (i = 0; i < PopSize; i++) {  
  101.         for (j = 0; j < CHROMLENGTH; j++) {  
  102.             p = rand() % 1000 / 1000.0;  
  103.             if (p < Pm) {  
  104.                 population[i].chrom[j] = (population[i].chrom[j] == '0') ? '1': '0';  
  105.             }  
  106.         }  
  107.     }  
  108.   
  109. }  
  110.   
  111. //交叉算子///  
  112. void crossoverOperator() {  
  113.     int i, j;  
  114.     int index[PopSize];  
  115.     int point, temp;  
  116.     double p;  
  117.     char ch;  
  118.     for (i = 0; i < PopSize; i++) {  
  119.         index[i] = i;  
  120.     }  
  121.     for (i = 0; i < PopSize; i++) {  
  122.   
  123.         point = rand() %(PopSize - i);  
  124.         temp = index[i];  
  125.         index[i] = index[point + i];  
  126.         index[point + i] = temp;  
  127.     }  
  128.     for (i = 0; i < PopSize - 1; i+=2) {  
  129.         p = rand() % 1000 / 1000.0;  
  130.         if (p < Pc) {  
  131.             point = rand()% (CHROMLENGTH - 1) + 1;  
  132.             for (j = point; j < CHROMLENGTH; j++) {  
  133.                 ch = population[index[i]].chrom[j];  
  134.                 population[index[i]].chrom[j] = population[index[i + 1]].chrom[j];  
  135.                 population[index[i + 1]].chrom[j] = ch;  
  136.             }  
  137.         }  
  138.     }  
  139. }  
  140.   
  141. ///选择算子/  
  142. void selectionOperator() {  
  143.     int i, index;  
  144.     double p, sum = 0.0;  
  145.     double cfitness[PopSize];  
  146.     Individual newpopulation[PopSize];  
  147.     for (i = 0; i < PopSize; i++) {  
  148.         sum += population[i].fitness;  
  149.     }  
  150.     for (i = 0; i < PopSize; i++) {  
  151.         cfitness[i] = population[i].fitness / sum;  
  152.     }  
  153.     // calculate cumulative fitness   
  154.     for (i = 1; i < PopSize; i++) {  
  155.         cfitness[i] = cfitness[i] + cfitness[i - 1];  
  156.     }  
  157.     for (i = 0; i < PopSize; i++) {  
  158.         p = rand() % 1000 / 1000.0;  
  159.         index = 0;  
  160.         while (p > cfitness[index]) {  
  161.             index++;  
  162.         }  
  163.         newpopulation[i] = population[index];  
  164.     }  
  165.     for (i = 0; i < PopSize; i++) {  
  166.         population[i] = newpopulation[i];  
  167.     }  
  168. }  
  169.   
  170.   
  171. /依据某些公式对样本进行评价  
  172. void evalutePopulation() {  
  173.     calculateObjectValue();  
  174.     calculateFitnessValue();  
  175.     findBestAndWorstIndividual();  
  176. }  
  177.   
  178.   
  179.   
  180. //找出到目前为止最好的个体//  
  181. void findBestAndWorstIndividual() {  
  182.   
  183.     int i;  
  184.     double sum = 0.0;  
  185.     bestIndividual = population[0];  
  186.     worstIndividual = population[0];  
  187.     for (i = 0; i < PopSize; i++) {  
  188.         if (population[i].fitness > bestIndividual.fitness) {  
  189.             bestIndividual = population[i];  
  190.             bestIndex = i;  
  191.         } else if (population[i].fitness < worstIndividual.fitness) {  
  192.             worstIndividual = population[i];  
  193.             worstIndex = i;  
  194.         }  
  195.         sum += population[i].fitness;  
  196.     }  
  197.     if (generation == 0) {  
  198.         currentBest = bestIndividual;  
  199.     } else {  
  200.         if (bestIndividual.fitness > currentBest.fitness) {  
  201.             currentBest = bestIndividual;  
  202.         }  
  203.     }  
  204.   
  205. }  
  206.   
  207. //计算适应度///  
  208. void calculateFitnessValue() {  
  209.     int i;  
  210.     long temp1, temp2;  
  211.     double x1, x2;  
  212.     for (i = 0; i < PopSize; i++) {  
  213.         temp1 = decomdeChromosome(population[i].chrom, 0, LENGHT1);  
  214.         temp2 = decomdeChromosome(population[i].chrom, LENGHT1, LENGHT2);  
  215.         x1 = temp1 * temp1;  
  216.         x2 = temp2 * temp2;  
  217.         population[i].fitness = x1+x2;  
  218.     }  
  219.   
  220. }  
  221.   
  222. //计算目标值  
  223. //目标函数为f(x) = x1* x1 +  x2*x2  
  224. void calculateObjectValue() {  
  225.     int i;  
  226.     long temp1, temp2;  
  227.     double x1, x2;  
  228.     for (i = 0; i < PopSize; i++) {  
  229.         temp1 = decomdeChromosome(population[i].chrom, 0, LENGHT1);  
  230.         temp2 = decomdeChromosome(population[i].chrom, LENGHT1, LENGHT2);  
  231.         x1 = temp1 * temp1;  
  232.         x2 = temp2 * temp2;  
  233.         population[i].value = x1 + x2;  
  234.     }  
  235.   
  236. }  
  237.   
  238. //把二进制转化为十进制  
  239. long decomdeChromosome(char* string, int point, int length) {  
  240.     int i;  
  241.     long decimal = 0L;  
  242.     char * pointer;  
  243.     for(i = 0, pointer=string+point; i < length;i++,pointer++){  
  244.         decimal += (*pointer - '0') << (length - 1 - i);  
  245.     }  
  246.     return decimal;  
  247. }  
  248.   
  249.   
  250. //进经同时把最坏个体用目前最好个人替代///  
  251. void performEvolution() {  
  252.     if (bestIndividual.fitness > currentBest.fitness) {  
  253.         currentBest = population[bestIndex];  
  254.     } else {  
  255.         population[worstIndex] = currentBest;  
  256.     }  
  257. }  
  258.   
  259.   
  260. //打印当前样本信息///  
  261. void outputTextReport() {  
  262.     int i;  
  263.     double sum;  
  264.     double average;  
  265.   
  266.     sum = 0.0;  
  267.     for (i = 0; i < PopSize; i++) {  
  268.         sum += population[i].value;  
  269.     }  
  270.     average = sum / PopSize;  
  271.     printf("gen=%d, avg=%f, best=%f",generation, average,currentBest.value);  
  272.     printf(" chromosome=");  
  273.     for(  i = 0; i < CHROMLENGTH; i++){  
  274.         printf("%c", currentBest.chrom[i]);  
  275.     }  
  276.     printf("/n");  
  277.   
  278. }  

 

输出结果:

[c-sharp]  view plain copy
  1. gen=1, avg=51.400000, best=74.000000 chromosome=101111  
  2. gen=2, avg=58.300000, best=74.000000 chromosome=101111  
  3. gen=3, avg=66.300000, best=74.000000 chromosome=101111  
  4. gen=4, avg=71.400000, best=74.000000 chromosome=101111  
  5. gen=5, avg=75.100000, best=98.000000 chromosome=111111  
  6. gen=6, avg=83.600000, best=98.000000 chromosome=111111  
  7. gen=7, avg=88.400000, best=98.000000 chromosome=111111  
  8. gen=8, avg=90.800000, best=98.000000 chromosome=111111  
  9. gen=9, avg=93.200000, best=98.000000 chromosome=111111  
  10. gen=10, avg=98.000000, best=98.000000 chromosome=111111  
  11. gen=11, avg=98.000000, best=98.000000 chromosome=111111  
  12. gen=12, avg=98.000000, best=98.000000 chromosome=111111  
  13. gen=13, avg=98.000000, best=98.000000 chromosome=111111  
  14. gen=14, avg=98.000000, best=98.000000 chromosome=111111  
  15. gen=15, avg=98.000000, best=98.000000 chromosome=111111  
  16. gen=16, avg=98.000000, best=98.000000 chromosome=111111  
  17. gen=17, avg=98.000000, best=98.000000 chromosome=111111  
  18. gen=18, avg=98.000000, best=98.000000 chromosome=111111  
  19. gen=19, avg=98.000000, best=98.000000 chromosome=111111  
  20. gen=20, avg=98.000000, best=98.000000 chromosome=111111  
  21. gen=21, avg=98.000000, best=98.000000 chromosome=111111  
  22. gen=22, avg=98.000000, best=98.000000 chromosome=111111  
  23. gen=23, avg=98.000000, best=98.000000 chromosome=111111  
  24. gen=24, avg=98.000000, best=98.000000 chromosome=111111  
  25. gen=25, avg=98.000000, best=98.000000 chromosome=111111  
  26. gen=26, avg=98.000000, best=98.000000 chromosome=111111  
  27. gen=27, avg=98.000000, best=98.000000 chromosome=111111  
  28. gen=28, avg=98.000000, best=98.000000 chromosome=111111  
  29. gen=29, avg=98.000000, best=98.000000 chromosome=111111  
  30. gen=30, avg=98.000000, best=98.000000 chromosome=111111  
  31. gen=31, avg=98.000000, best=98.000000 chromosome=111111  
  32. gen=32, avg=98.000000, best=98.000000 chromosome=111111  
  33. gen=33, avg=98.000000, best=98.000000 chromosome=111111  
  34. gen=34, avg=98.000000, best=98.000000 chromosome=111111  
  35. gen=35, avg=98.000000, best=98.000000 chromosome=111111  
  36. gen=36, avg=98.000000, best=98.000000 chromosome=111111  
  37. gen=37, avg=98.000000, best=98.000000 chromosome=111111  
  38. gen=38, avg=98.000000, best=98.000000 chromosome=111111  
  39. gen=39, avg=98.000000, best=98.000000 chromosome=111111  
  40. gen=40, avg=98.000000, best=98.000000 chromosome=111111  
  41. gen=41, avg=98.000000, best=98.000000 chromosome=111111  
  42. gen=42, avg=98.000000, best=98.000000 chromosome=111111  
  43. gen=43, avg=98.000000, best=98.000000 chromosome=111111  
  44. gen=44, avg=98.000000, best=98.000000 chromosome=111111  
  45. gen=45, avg=98.000000, best=98.000000 chromosome=111111  
  46. gen=46, avg=98.000000, best=98.000000 chromosome=111111  
  47. gen=47, avg=98.000000, best=98.000000 chromosome=111111  
  48. gen=48, avg=98.000000, best=98.000000 chromosome=111111  
  49. gen=49, avg=98.000000, best=98.000000 chromosome=111111  
  50. gen=50, avg=98.000000, best=98.000000 chromosome=111111  
  51. gen=51, avg=98.000000, best=98.000000 chromosome=111111  
  52. gen=52, avg=98.000000, best=98.000000 chromosome=111111  
  53. gen=53, avg=98.000000, best=98.000000 chromosome=111111  
  54. gen=54, avg=98.000000, best=98.000000 chromosome=111111  
  55. gen=55, avg=98.000000, best=98.000000 chromosome=111111  
  56. gen=56, avg=98.000000, best=98.000000 chromosome=111111  
  57. gen=57, avg=98.000000, best=98.000000 chromosome=111111  
  58. gen=58, avg=98.000000, best=98.000000 chromosome=111111  
  59. gen=59, avg=98.000000, best=98.000000 chromosome=111111  
  60. gen=60, avg=98.000000, best=98.000000 chromosome=111111  
  61. gen=61, avg=98.000000, best=98.000000 chromosome=111111  
  62. gen=62, avg=98.000000, best=98.000000 chromosome=111111  
  63. gen=63, avg=98.000000, best=98.000000 chromosome=111111  
  64. gen=64, avg=98.000000, best=98.000000 chromosome=111111  
  65. gen=65, avg=98.000000, best=98.000000 chromosome=111111  
  66. gen=66, avg=98.000000, best=98.000000 chromosome=111111  
  67. gen=67, avg=98.000000, best=98.000000 chromosome=111111  
  68. gen=68, avg=98.000000, best=98.000000 chromosome=111111  
  69. gen=69, avg=98.000000, best=98.000000 chromosome=111111  
  70. gen=70, avg=98.000000, best=98.000000 chromosome=111111  
  71. gen=71, avg=98.000000, best=98.000000 chromosome=111111  
  72. gen=72, avg=98.000000, best=98.000000 chromosome=111111  
  73. gen=73, avg=98.000000, best=98.000000 chromosome=111111  
  74. gen=74, avg=98.000000, best=98.000000 chromosome=111111  
  75. gen=75, avg=98.000000, best=98.000000 chromosome=111111  
  76. gen=76, avg=98.000000, best=98.000000 chromosome=111111  
  77. gen=77, avg=98.000000, best=98.000000 chromosome=111111  
  78. gen=78, avg=98.000000, best=98.000000 chromosome=111111  
  79. gen=79, avg=98.000000, best=98.000000 chromosome=111111  
  80. gen=80, avg=98.000000, best=98.000000 chromosome=111111  
  81. gen=81, avg=98.000000, best=98.000000 chromosome=111111  
  82. gen=82, avg=98.000000, best=98.000000 chromosome=111111  
  83. gen=83, avg=98.000000, best=98.000000 chromosome=111111  
  84. gen=84, avg=98.000000, best=98.000000 chromosome=111111  
  85. gen=85, avg=98.000000, best=98.000000 chromosome=111111  
  86. gen=86, avg=98.000000, best=98.000000 chromosome=111111  
  87. gen=87, avg=98.000000, best=98.000000 chromosome=111111  
  88. gen=88, avg=98.000000, best=98.000000 chromosome=111111  
  89. gen=89, avg=98.000000, best=98.000000 chromosome=111111  
  90. gen=90, avg=98.000000, best=98.000000 chromosome=111111  
  91. gen=91, avg=98.000000, best=98.000000 chromosome=111111  
  92. gen=92, avg=98.000000, best=98.000000 chromosome=111111  
  93. gen=93, avg=98.000000, best=98.000000 chromosome=111111  
  94. gen=94, avg=98.000000, best=98.000000 chromosome=111111  
  95. gen=95, avg=98.000000, best=98.000000 chromosome=111111  
  96. gen=96, avg=98.000000, best=98.000000 chromosome=111111  
  97. gen=97, avg=98.000000, best=98.000000 chromosome=111111  
  98. gen=98, avg=98.000000, best=98.000000 chromosome=111111  
  99. gen=99, avg=98.000000, best=98.000000 chromosome=111111  
  100. gen=100, avg=98.000000, best=98.000000 chromosome=111111  
  101. 请按任意键继续. . .  

从结果可以看出,遗传算法收敛得非常快,在第5代的时候,已经达到了全局最优解.如果把初始种群扩大,收敛得会更快.

遗传算法主要应用领域:

（1）组合优化     （2）函数优化 
（3）自动控制     （4）生产调度 
（5）图像处理      （6）机器学习 
（7）人工生命      （8）数据挖掘 

------------------------------------------------------------------------------------------------------------

转载自：http://blog.csdn.net/jicheng687/article/details/5321573。对作者表示衷心的感谢~

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号