fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>
  5. #include <time.h>
  6. #include <iostream>
  7.  
  8. using namespace std;
  9.  
  10. #define GeneNumber        4                 // 基因長度
  11. #define PopulationSize    10                // 母群數量
  12. #define MaxGeneration     100               // 迭代次數
  13. #define CrossoverRate     0.7               // 交配率
  14. #define MutationRate      0.1               // 突變率
  15.  
  16. class parent{
  17. public: 
  18.         int genes[GeneNumber];
  19.         double fitness;
  20.         double dec_value;
  21. };
  22.  
  23. // PositionRand(): 隨機取得(交配點/突變位置)
  24. #define PositionRand()           (rand()%GeneNumber)
  25. // BinaryRand():  隨機產生0~1整數(無小數)for(產生基因)
  26. #define BinaryRand()            (rand()%2)
  27. // PointRand():   隨機產生0~1 的亂數(有小數)for(交配/突變率)
  28. #define PointRand()             ((double)rand()/(double)RAND_MAX)
  29.  
  30. // =====================================================
  31.  
  32. // 進行初始化
  33. void initialize();           
  34. // 輪盤式選擇(隨機式)
  35. void CrossoverPool();   
  36. // 交配, 交配池中的個體進行交配(兩點交配)
  37. void crossover();           
  38. // 突變, 逐一bit 慢慢確認突變
  39. void mutation();
  40. // 計算基因所對應之適應值
  41. void cal_fitness(parent *x);     
  42. // 計算基因對應之進制值
  43. void cal_Decimal(parent *x);     
  44. // 讓交配點的第二點永遠比第一點大
  45. void swap(int *x,int *b);
  46.  
  47.  
  48. // =====================================================
  49.  
  50. parent population[PopulationSize];      // 母體數量
  51. parent pool[PopulationSize];            // 交配池
  52. parent best_gene;                       // 從以前到現在最好的基因
  53.  
  54.  
  55. // binary 2 dec，將染色體中的二進位(genes) ，轉為十進位(dec_value)
  56. void cal_Decimal(parent *x)
  57. {
  58.         int i,j = 0;
  59.         double dec = 0;
  60.         for(i=GeneNumber-1; i >= 0; i--){
  61.                 dec += x->genes[i]*pow((double)2,j);
  62.                 j++;
  63.         }
  64.         x->dec_value = dec;
  65. }
  66.  
  67. //計算適應值 適應函數為31i-i*i
  68. void cal_fitness(parent *x)
  69. {    
  70.      double i = x->dec_value;
  71.      x->fitness = 31*i - i*i;
  72. }
  73.  
  74. //將a,b兩數互換，讓起始數永遠比終點數小
  75. void swap(int *a,int *b)
  76. {
  77.         int x;
  78.         x = *a;
  79.         *a = *b;
  80.         *b = x;
  81. }
  82.  
  83. //初始化
  84. void initialize()
  85. {
  86.      int i, j,x,y;
  87.          for(i=0; i<PopulationSize; i++){
  88.                  for(j=0; j<GeneNumber; j++){
  89.                          // 每個母體的基因都是隨機給/1
  90.                          population[i].genes[j] = BinaryRand();
  91.                  }
  92.          }
  93.  
  94.          // 計算母體基因之進制值
  95.          for(x = 0; x < PopulationSize; x++){
  96.                  cout <<x <<" : bin = ";
  97.                  for(y = 0; y < GeneNumber; y++){
  98.                          cout << population[x].genes[y];
  99.                  }
  100.  
  101.                  cout << '\n';
  102.                  //計算十進位之值並輸出
  103.                  cal_Decimal(&population[x]);
  104.                  cout << "Dec = " << population[x].dec_value << '\n';
  105.                  //計算適應並變輸出
  106.                  cal_fitness(&population[x]);
  107.                  cout << "Fitness = "<< population[x].fitness << '\n';
  108.                  //更新最佳基因
  109.                  if(x==0)
  110.                                  best_gene = population[0];
  111.                  else if(population[x].fitness > best_gene.fitness)
  112.                          best_gene = population[x];
  113.                  cout << "best_gene = "<< best_gene.fitness << '\n';
  114.                  cout << "======================================="<< '\n';
  115.  
  116.          }
  117. }
  118. //輪盤式選擇
  119. void CrossoverPool()
  120. {
  121.         int i,j;
  122.         double FitnessSum = 0;//適應值總和
  123.         double Fitness_percent[PopulationSize];//每個基因的適應值所占整體的比例
  124.         double Fitness_percent_total=0;
  125.         int pickup;//抽取個體 
  126.         //計算適應值總和並輸出
  127.         for(i=0; i < PopulationSize; i++){
  128.                 FitnessSum += population[i].fitness;
  129.         }
  130.         cout << "FitnessSum = "<< FitnessSum <<'\n';
  131.         //計算每個基因的適應值佔總合多少比例並輸出
  132.         for(i=0; i < PopulationSize; i++){
  133.                 Fitness_percent[i] = population[i].fitness / FitnessSum;
  134.                 cout << "Fitness_percent = " << Fitness_percent[i]<< '\n';
  135.                 Fitness_percent_total+=Fitness_percent[i];
  136.         }        
  137.         cout << "Fitness_percent_total = " << Fitness_percent_total << '\n';
  138.         //選擇基因丟入交配池
  139.         for(i=0; i < PopulationSize; i++){
  140.                 pickup = rand()%PopulationSize;
  141.                 cout << i << " : Pool = ";
  142.                 for(j=0; j < GeneNumber; j++){
  143.                         pool[i].genes[j] = population[pickup].genes[j];
  144.                         cout << pool[i].genes[j];
  145.                 }
  146.                 cout << '\n';
  147.         }  
  148. }
  149. //兩點交配
  150. void crossover()
  151. {
  152.         int i,j;
  153.         int PartOfComplete=0;//完成數目
  154.         int p1,p2;//交配池中的隨機兩組基因
  155.         int pos1=0,pos2=0;//交換點由pos1~pos2
  156.         double CrossoverProbability;//交配機率
  157.  
  158.  
  159.  
  160.         //重複執行直到交配完10組個體
  161.         while(PartOfComplete < PopulationSize){
  162.                 //隨機選擇兩個個體
  163.                 p1 = rand() % PopulationSize;
  164.                 do{ p2 = rand() % PopulationSize;}while(p2 == p1);
  165.                 CrossoverProbability=PointRand();       
  166.                 cout << "CrossoverProbability = " << CrossoverProbability << '\n';
  167.  
  168.                 //交配
  169.                 if(CrossoverProbability < CrossoverRate){
  170.                         pos1=PositionRand();            
  171.                         do{
  172.                                 pos2=PositionRand();
  173.                         }while(pos2 == pos1 || ((pos1 == 0 || pos1 == GeneNumber-1) && (pos1+pos2 == GeneNumber-1)));
  174.                         //↑↑↑↑↑判斷機制pos1:pos1與pos2不可為同值且pos1與pos2不可同時為第一點與最後一點↑↑↑↑↑
  175.                         cout << "pos1 = "<< pos1 <<" pos2 = "<< pos2 << '\n';                   
  176.                         //強制由左往右做區域的選取
  177.                         if(pos1>pos2)
  178.                                 swap(&pos1,&pos2);
  179.                         cout << "pos1 = " << pos1 <<" pos2 = " << pos2 << '\n';
  180.                         cout << "p1 = " << p1 <<" p2 = " << p2 << '\n';
  181.  
  182.                         //第一階段交配
  183.                         for(i=0; i<pos1; i++){
  184.                                 population[PartOfComplete].genes[i]=pool[p1].genes[i];
  185.                                 population[PartOfComplete+1].genes[i]=pool[p2].genes[i];
  186.                         }
  187.                         //第二階段交配
  188.                         for(i=pos1; i<=pos2; i++){
  189.                                 population[PartOfComplete+1].genes[i]=pool[p1].genes[i];
  190.                                 population[PartOfComplete].genes[i]=pool[p2].genes[i];
  191.                         }
  192.                         //第三階段交配
  193.                         for(i=pos2+1; i<GeneNumber; i++){
  194.                                 population[PartOfComplete].genes[i]=pool[p1].genes[i];
  195.                                 population[PartOfComplete+1].genes[i]=pool[p2].genes[i];
  196.                         }
  197.                         //輸出交配後的二進制之值
  198.                         for(i = 0; i < PopulationSize; i++){
  199.                                 cout <<i <<" : bin = ";
  200.                                 for(j = 0; j < GeneNumber; j++){
  201.                                         cout << population[i].genes[j];
  202.                                 }
  203.                                 cout << '\n';
  204.                         }
  205.                         //進行下面兩個個體的交配
  206.                         PartOfComplete+=2;
  207.                 }
  208.         }
  209. }
  210. //突變
  211. void mutation()
  212. {
  213.         int i,j;
  214.         int pos;//突變點
  215.         double MutationProbability;//突變機率
  216.         for(i = 0; i < PopulationSize; i++){
  217.                 MutationProbability = PointRand();
  218.                 cout << "MutationProbability = "<< MutationProbability <<'\n';
  219.                 //是否發生突變
  220.                 if(MutationProbability < MutationRate){
  221.                         //突變點
  222.                         pos = PositionRand();
  223.                         //做突變點的突變處理
  224.                         population[i].genes[pos] = !population[i].genes[pos];
  225.                         cout<<"pos = "<< pos <<'\n';
  226.                 }
  227.                 cout << i <<" : bin = ";
  228.                 for(j = 0; j < GeneNumber; j++){
  229.                         cout << population[i].genes[j];
  230.                 }
  231.                 cout << '\n';
  232.                 //計算十進制之值並輸出
  233.                 cal_Decimal(&population[i]);
  234.                 cout << "Dec = " << population[i].dec_value << '\n';
  235.                 //計算適應值並輸出
  236.                 cal_fitness(&population[i]);
  237.                 cout << "Fitness = "<< population[i].fitness << '\n';
  238.                 //更新最佳基因
  239.                 if(population[i].fitness > best_gene.fitness)
  240.                         best_gene = population[i];
  241.                 cout << "best_gene = "<< best_gene.fitness << '\n';
  242.                 cout << "======================================="<< '\n';
  243.         }       
  244. }
  245.  
  246.  
  247. int main()
  248. {
  249.         srand((unsigned)time(NULL));
  250.         initialize();            // 初始化
  251.                 cout<<'\n';
  252.         CrossoverPool();                //分配式選擇
  253.                 cout<<'\n'; 
  254.         crossover();                    //兩點交配
  255.                 cout<<'\n';
  256.         mutation();                             //突變
  257.                 cout<<'\n';
  258.                                 cout << "best_gene = "<< best_gene.fitness << '\n';
  259.  
  260.         system("pause");
  261. }
  262.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin 
Standard input is empty
stdout 
0 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 30
=======================================
1 : bin = 1110
Dec = 14
Fitness = 238
best_gene = 238
=======================================
2 : bin = 1000
Dec = 8
Fitness = 184
best_gene = 238
=======================================
3 : bin = 1111
Dec = 15
Fitness = 240
best_gene = 240
=======================================
4 : bin = 1101
Dec = 13
Fitness = 234
best_gene = 240
=======================================
5 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
6 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
7 : bin = 0010
Dec = 2
Fitness = 58
best_gene = 240
=======================================
8 : bin = 0111
Dec = 7
Fitness = 168
best_gene = 240
=======================================
9 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================

FitnessSum = 1242
Fitness_percent = 0.0241546
Fitness_percent = 0.191626
Fitness_percent = 0.148148
Fitness_percent = 0.193237
Fitness_percent = 0.188406
Fitness_percent = 0.0241546
Fitness_percent = 0.0241546
Fitness_percent = 0.0466989
Fitness_percent = 0.135266
Fitness_percent = 0.0241546
Fitness_percent_total = 1
0 : Pool = 1101
1 : Pool = 0001
2 : Pool = 1101
3 : Pool = 1101
4 : Pool = 1000
5 : Pool = 1110
6 : Pool = 0010
7 : Pool = 0001
8 : Pool = 0001
9 : Pool = 0001

CrossoverProbability = 0.509405
pos1 = 2 pos2 = 3
pos1 = 2 pos2 = 3
p1 = 7 p2 = 2
0 : bin = 0001
1 : bin = 1101
2 : bin = 1000
3 : bin = 1111
4 : bin = 1101
5 : bin = 0001
6 : bin = 0001
7 : bin = 0010
8 : bin = 0111
9 : bin = 0001
CrossoverProbability = 0.0065643
pos1 = 0 pos2 = 1
pos1 = 0 pos2 = 1
p1 = 0 p2 = 6
0 : bin = 0001
1 : bin = 1101
2 : bin = 0001
3 : bin = 1110
4 : bin = 1101
5 : bin = 0001
6 : bin = 0001
7 : bin = 0010
8 : bin = 0111
9 : bin = 0001
CrossoverProbability = 0.332851
pos1 = 2 pos2 = 1
pos1 = 1 pos2 = 2
p1 = 9 p2 = 6
0 : bin = 0001
1 : bin = 1101
2 : bin = 0001
3 : bin = 1110
4 : bin = 0011
5 : bin = 0000
6 : bin = 0001
7 : bin = 0010
8 : bin = 0111
9 : bin = 0001
CrossoverProbability = 0.575129
pos1 = 3 pos2 = 1
pos1 = 1 pos2 = 3
p1 = 7 p2 = 9
0 : bin = 0001
1 : bin = 1101
2 : bin = 0001
3 : bin = 1110
4 : bin = 0011
5 : bin = 0000
6 : bin = 0001
7 : bin = 0001
8 : bin = 0111
9 : bin = 0001
CrossoverProbability = 0.264904
pos1 = 1 pos2 = 2
pos1 = 1 pos2 = 2
p1 = 7 p2 = 5
0 : bin = 0001
1 : bin = 1101
2 : bin = 0001
3 : bin = 1110
4 : bin = 0011
5 : bin = 0000
6 : bin = 0001
7 : bin = 0001
8 : bin = 0111
9 : bin = 1000

MutationProbability = 0.838391
0 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
MutationProbability = 0.423335
1 : bin = 1101
Dec = 13
Fitness = 234
best_gene = 240
=======================================
MutationProbability = 0.583697
2 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
MutationProbability = 0.32903
3 : bin = 1110
Dec = 14
Fitness = 238
best_gene = 240
=======================================
MutationProbability = 0.40248
4 : bin = 0011
Dec = 3
Fitness = 84
best_gene = 240
=======================================
MutationProbability = 0.0931016
pos = 3
5 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
MutationProbability = 0.589511
6 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
MutationProbability = 0.874645
7 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
MutationProbability = 0.224997
8 : bin = 0111
Dec = 7
Fitness = 168
best_gene = 240
=======================================
MutationProbability = 0.596075
9 : bin = 1000
Dec = 8
Fitness = 184
best_gene = 240
=======================================

best_gene = 240
https://ideone.com/WSrJv
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!