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 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
0 : bin = 1110
Dec = 14
Fitness = 238
best_gene = 238
=======================================
1 : bin = 1100
Dec = 12
Fitness = 228
best_gene = 238
=======================================
2 : bin = 0011
Dec = 3
Fitness = 84
best_gene = 238
=======================================
3 : bin = 1111
Dec = 15
Fitness = 240
best_gene = 240
=======================================
4 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
5 : bin = 1000
Dec = 8
Fitness = 184
best_gene = 240
=======================================
6 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
7 : bin = 1010
Dec = 10
Fitness = 210
best_gene = 240
=======================================
8 : bin = 1100
Dec = 12
Fitness = 228
best_gene = 240
=======================================
9 : bin = 0010
Dec = 2
Fitness = 58
best_gene = 240
=======================================

FitnessSum = 1530
Fitness_percent = 0.155556
Fitness_percent = 0.14902
Fitness_percent = 0.054902
Fitness_percent = 0.156863
Fitness_percent = 0.0196078
Fitness_percent = 0.120261
Fitness_percent = 0.0196078
Fitness_percent = 0.137255
Fitness_percent = 0.14902
Fitness_percent = 0.0379085
Fitness_percent_total = 1
0 : Pool = 1000
1 : Pool = 0001
2 : Pool = 0001
3 : Pool = 0001
4 : Pool = 1000
5 : Pool = 1010
6 : Pool = 1000
7 : Pool = 0011
8 : Pool = 0011
9 : Pool = 1100

CrossoverProbability = 0.85086
CrossoverProbability = 0.927695
CrossoverProbability = 0.337228
pos1 = 3 pos2 = 1
pos1 = 1 pos2 = 3
p1 = 7 p2 = 9
0 : bin = 0100
1 : bin = 1011
2 : bin = 0011
3 : bin = 1111
4 : bin = 0001
5 : bin = 1000
6 : bin = 0001
7 : bin = 1010
8 : bin = 1100
9 : bin = 0010
CrossoverProbability = 0.600989
pos1 = 2 pos2 = 1
pos1 = 1 pos2 = 2
p1 = 8 p2 = 2
0 : bin = 0100
1 : bin = 1011
2 : bin = 0001
3 : bin = 0011
4 : bin = 0001
5 : bin = 1000
6 : bin = 0001
7 : bin = 1010
8 : bin = 1100
9 : bin = 0010
CrossoverProbability = 0.226015
pos1 = 3 pos2 = 2
pos1 = 2 pos2 = 3
p1 = 1 p2 = 5
0 : bin = 0100
1 : bin = 1011
2 : bin = 0001
3 : bin = 0011
4 : bin = 0010
5 : bin = 1001
6 : bin = 0001
7 : bin = 1010
8 : bin = 1100
9 : bin = 0010
CrossoverProbability = 0.666782
pos1 = 1 pos2 = 0
pos1 = 0 pos2 = 1
p1 = 9 p2 = 2
0 : bin = 0100
1 : bin = 1011
2 : bin = 0001
3 : bin = 0011
4 : bin = 0010
5 : bin = 1001
6 : bin = 0000
7 : bin = 1101
8 : bin = 1100
9 : bin = 0010
CrossoverProbability = 0.18548
pos1 = 3 pos2 = 2
pos1 = 2 pos2 = 3
p1 = 5 p2 = 0
0 : bin = 0100
1 : bin = 1011
2 : bin = 0001
3 : bin = 0011
4 : bin = 0010
5 : bin = 1001
6 : bin = 0000
7 : bin = 1101
8 : bin = 1000
9 : bin = 1010

MutationProbability = 0.430442
0 : bin = 0100
Dec = 4
Fitness = 108
best_gene = 240
=======================================
MutationProbability = 0.889214
1 : bin = 1011
Dec = 11
Fitness = 220
best_gene = 240
=======================================
MutationProbability = 0.78183
2 : bin = 0001
Dec = 1
Fitness = 30
best_gene = 240
=======================================
MutationProbability = 0.424205
3 : bin = 0011
Dec = 3
Fitness = 84
best_gene = 84
=======================================
MutationProbability = 0.834654
4 : bin = 0010
Dec = 2
Fitness = 58
best_gene = 84
=======================================
MutationProbability = 0.913724
5 : bin = 1001
Dec = 9
Fitness = 198
best_gene = 198
=======================================
MutationProbability = 0.761433
6 : bin = 0000
Dec = 0
Fitness = 0
best_gene = 198
=======================================
MutationProbability = 0.386191
7 : bin = 1101
Dec = 13
Fitness = 234
best_gene = 234
=======================================
MutationProbability = 0.499928
8 : bin = 1000
Dec = 8
Fitness = 184
best_gene = 234
=======================================
MutationProbability = 0.749752
9 : bin = 1010
Dec = 10
Fitness = 210
best_gene = 234
=======================================

best_gene = 234
https://ideone.com/9L6MS
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!