(C/C++学习)20.基于C++改进的单目标遗传算法

说明：在学习生活中，经常会遇到各种各样的最优问题，其中最常见的就是求某个多维（多个自变量）函数在各个自变量各取何值时的最大值或最小值；例如求函数 f(x) = (x-5)²+(y-6)²+(z-7)²的最小值，当然，这个函数很简单，很容易看出来，该函数的最小值为0，分别在三个自变量取5，6，7时取得最小值。但日常学习中的函数都是很复杂的，就算通过大量的计算，也不一定能准确地算出目标值以及在何时取得该目标值，因此，本文介绍一种基于单目标的遗传算法来解决此类问题。

注意：由于封装函数较多，为了清晰，函数名一般为其英文名，因此比较长，强烈建议电脑阅读。

1.遗传算法代码实现

遗传算法的相关概念，这里不多说，网上一大堆，这里只介绍本程序的实现过程，代码如下：

a.第一部分为主函数

  1 #include <iostream>
  2 #include <genetic.h>
  3 using namespace std;
  4 
  5 int main()
  6 {
  7     Genetic M;
  8     int Iteration = 0;
  9     //种群及重要参数初始化
 10     M.initiallize(M.Initialpop,Populationsize);
 11     cout<<"
				  The Genetic Algrithm System
"<<endl;
 12     cout<<"
					The Initial Pop:
"<<endl;
 13     cout<<setw(20)<<"x"<<setw(20)<<"y"<<setw(20)<<"z"<<setw(20)<<"Fitness"<<endl<<endl;
 14     //获取种群适应度
 15     M.getfitnessofpop(M.Initialpop,Populationsize);
 16     //根据适应度排序
 17     M.sortpopbyfitness(M.Initialpop,Populationsize);
 18     //打印初始种群
 19     M.printpop(M.Initialpop,Populationsize);
 20     cout<<"

					The Iteration Begins:
"<<endl;
 21     while(Iteration <= M.Iterationtimes)
 22     {
 23         //交叉
 24         M.crossover(M.Initialpop,M.Offspring,Populationsize);
 25         //求取种群适应度
 26         M.getfitnessofpop(M.Offspring,Populationsize);
 27         //根据适应度排序
 28         M.sortpopbyfitness(M.Offspring,Populationsize);
 29         //父子代结合
 30         M.combinationpop(M.Initialpop,M.Offspring,M.Combinationpop,Populationsize);
 31         //变异
 32         M.mutation(M.Combinationpop,Populationsize*2);
 33         //求取结合种群适应度
 34         M.getfitnessofpop(M.Combinationpop,Populationsize*2);
 35         //对结合种群排序
 36         M.sortpopbyfitness(M.Combinationpop,Populationsize*2);
 37         //选择较优个体
 38         M.selectbestpop(M.Combinationpop,M.Initialpop,Populationsize);
 39         //结果微调，精确算子
 40         M.getAccurateResult(M.Initialpop,Populationsize);
 41         //打印迭代过程中出现的最优个体
 42         M.printbestindivil(M.Initialpop,Populationsize,Iteration);
 43         Iteration++;
 44     }
 45     cout<<"

"<<"The Last Population : 

"<<endl;
 46     //打印最后一代的所有个体成员及其目标值
 47     M.printpop(M.Initialpop,Populationsize);
 48     cout<<"


";
 49     return 0;
 50 }
 51 
 52

View Code

b.第二部分为基因操作头文件

  1 #ifndef GENETIC_H
  2 #define GENETIC_H
  3 #include <time.h>
  4 #include <stdlib.h>
  5 #include <iomanip>
  6 #include <iostream>
  7 #include <math.h>
  8 using namespace std;
  9 #define Populationsize 16
 10 #define pi 3.1415926
 11 #define Accurate 0.001
 12 #define NumOfParameters 10
 13 //精度越高要求迭代次数越大
 14 
 15 class Genetic
 16 {
 17 public:
 18     Genetic();
 19     typedef struct Individual
 20     {
 21         double parameter[Populationsize];
 22         double fitness;
 23     }Individuals;
 24     Individuals Initialpop[Populationsize];
 25     Individuals Offspring[Populationsize];
 26     Individuals Combinationpop[Populationsize*2];
 27     Individuals Bestindividual;
 28     double downlimit[NumOfParameters];
 29     double uplimit[NumOfParameters];
 30     double crossoverability;
 31     double mutationproability;
 32     int NumOfParameter;
 33     int Iterationtimes;
 34 
 35     void initiallize(Individuals *Initialpop,int Populationsiz);
 36     void printpop(Individuals *Initialpop, int Populationsiz);
 37     double getfitnessofindiv(Individuals Indiv);
 38     void getfitnessofpop(Individuals *Initialpop,int Populationsiz);
 39     void sortpopbyfitness(Individuals *Initialpop,int Populationsiz);
 40     void crossover(Individuals *Initialpop,Individuals *offspring,int Populationsiz);
 41     void combinationpop(Individuals *Initialpop,Individuals *offspring,Individuals* Combinationpop,int populationsize);
 42     void mutation(Individuals *Initialpop,int population);
 43     void selectbestpop(Individuals* Combinationpo,Individuals *Initialpop,int population);
 44     void printbestindivil(Individuals* Initialpop,int populationsize, int Iteration);
 45     void getAccurateResult(Individuals* Initialpop,int population);
 46 };
 47 
 48 #endif // GENETIC_H
 49

View Code

c.第三部分为基因操作头文件相应的 cpp 文件

  1 #include "genetic.h"
  2 Genetic::Genetic()
  3 {
  4 
  5 }
  6 void Genetic::initiallize(Genetic::Individuals *Initialpop, int Populationsiz)
  7 {
  8     cout<<"Welcome To The Genetic Algrithm System......
";
  9     cout<<"
Pls Follow The Steps To Complete Your Compution.....

";
 10     cout<<"
Step 0: Pls Make Sure The Marked Function Have Been Modefied.....
";
 11     cout<<"
Step 1: Now Pls Input The Num Of Variations :";
 12     cin>>NumOfParameter;
 13     for(int i = 0;i<NumOfParameter;i++)
 14     {
 15         cout<<"
Step "<<2*i+2<<" : Pls Input The Downlimit Of Variation "<<i+1<<" :";
 16         cin>>downlimit[i];
 17         cout<<"
Step "<<2*i+3<<" : Pls Input The Uplimit Of Variation "<<i+1<<" :";
 18         cin>>uplimit[i];
 19     }
 20     cout<<"
Step "<<2*NumOfParameter+2<<" :Pls Input The Iteration Times:";
 21     cin>>Iterationtimes;
 22     srand(time(NULL));
 23     crossoverability = 0.8;
 24     mutationproability = 0.01;
 25     for(int i=0; i<Populationsiz; i++)
 26     {
 27         for(int j = 0;j<NumOfParameter;j++)
 28         {
 29             Initialpop[i].parameter[j] = downlimit[j] + (rand()%50)/50.0*(uplimit[j]-downlimit[j]);
 30         }
 31     }
 32 }
 33 
 34 void Genetic::printpop(Genetic::Individuals *Initialpop, int Populationsiz)
 35 {
 36     for(int i =0;i<Populationsiz;i++)
 37     {
 38         for(int j = 0;j<NumOfParameter;j++)
 39         {
 40             cout<<setw(20)<<setprecision(5)<<Initialpop[i].parameter[j];
 41         }
 42         cout<<setw(20)<<fixed<<setprecision(7)<<Initialpop[i].fitness<<endl;
 43     }
 44 }
 45 
 46 
 47 // Function 目标函数根据所求实际问题进行修改
 48 double Genetic::getfitnessofindiv(Individuals Indiv)
 49 {
 50     double result;
 51     result = -(Indiv.parameter[0]+12.5)*(Indiv.parameter[0]+12.5)-(Indiv.parameter[1]+7.6)*(Indiv.parameter[1]+7.6)
 52             -(Indiv.parameter[2]+10.3)*(Indiv.parameter[2]+10.3);
 53     return result;
 54 }
 55 //修改
 56 
 57 void Genetic::getfitnessofpop(Genetic::Individuals *Initialpop, int Populationsiz)
 58 {
 59     for(int i = 0;i<Populationsiz;i++)
 60     {
 61         Initialpop[i].fitness = getfitnessofindiv(Initialpop[i]);
 62     }
 63 }
 64 
 65 
 66 void Genetic::sortpopbyfitness(Genetic::Individuals *Initialpop, int Populationsiz)
 67 {
 68     for(int i = 0;i<Populationsiz;i++)
 69     {
 70         int idx = i;
 71         for(int j = i+1;j<Populationsiz;j++)
 72         {
 73             if(Initialpop[idx].fitness > Initialpop[j].fitness)
 74                 idx = j;
 75         }
 76         if(idx != i)
 77         {
 78             Individual temp = Initialpop[i];
 79             Initialpop[i] = Initialpop[idx];
 80             Initialpop[idx] = temp;
 81         }
 82     }
 83     Bestindividual = Initialpop[0];
 84 }
 85 
 86 void Genetic::crossover(Individuals *Initialpop,Individuals *offspring, int Populationsiz)
 87 {
 88     for(int i = 1;i<=Populationsiz;i++)
 89     {
 90         //保证适值为正
 91         Initialpop[Populationsiz-i].fitness += -Initialpop[0].fitness;
 92     }
 93     srand(time(NULL));
 94     Individuals parent[2];
 95     double temp = 0;
 96     double totalfitness = 0;
 97     double gradient[Populationsiz] = {0};
 98     for(int i = 0;i<Populationsiz;i++)
 99     {
100         totalfitness += Initialpop[i].fitness;
101     }
102     for(int i = 0;i<Populationsiz;i++)
103     {
104         temp += Initialpop[i].fitness;
105         gradient[i] = temp/totalfitness;
106     }
107     for(int i = 0;i<Populationsiz/2;i++)
108     {
109         for(int j = 0;j<2;j++)
110         {
111             double randgradient = rand()%1000/1000.0;
112             for(int k = 0;k<Populationsiz;k++)
113             {
114                 if(k == 0)
115                 {
116                     if(randgradient < gradient[0])
117                     {
118                         parent[j] = Initialpop[k];
119                     }
120                 }
121                 else
122                 {
123                     if(randgradient >= gradient[k-1] && randgradient < gradient[k])
124                     {
125                         parent[j] = Initialpop[k];
126                     }
127                 }
128             }
129         }
130         double Probability = rand()%1000/1000.0;
131         if(Probability < crossoverability)
132         {
133             double b = rand()%100/100.0;
134             if(b <= 0.5)
135             {
136                 double a = pow(2*b,1/21.0);
137                 for(int j = 0;j<NumOfParameter;j++)
138                 {
139                     offspring[2*i].parameter[j] = ((1+a)*parent[0].parameter[j]+(1-a)*parent[1].parameter[j])/2.0;
140                     offspring[2*i+1].parameter[j] = ((1-a)*parent[0].parameter[j]+(1+a)*parent[1].parameter[j])/2.0;
141                 }
142                 for(int j = 0;j<NumOfParameter;j++)
143                 {
144                     if(offspring[2*i].parameter[j] < downlimit[j] || offspring[2*i].parameter[j] > uplimit[j]
145                             || offspring[2*i+1].parameter[j] < downlimit[j] || offspring[2*i+1].parameter[j] >
146                             uplimit[j])
147                     {
148                         i--;
149                         break;
150                     }
151                 }
152             }
153             else
154             {
155                 double a = pow(2*(1-b),-1/21.0);
156                 for(int j = 0;j<NumOfParameter;j++)
157                 {
158                     offspring[2*i].parameter[j] = ((1+a)*parent[0].parameter[j]+(1-a)*parent[1].parameter[j])/2.0;
159                     offspring[2*i+1].parameter[j] = ((1-a)*parent[0].parameter[j]+(1+a)*parent[1].parameter[j])/2.0;
160                 }
161                 for(int j = 0;j<NumOfParameter;j++)
162                 {
163                     if(offspring[2*i].parameter[j] < downlimit[j] || offspring[2*i].parameter[j] > uplimit[j]
164                             || offspring[2*i+1].parameter[j] < downlimit[j] || offspring[2*i+1].parameter[j] >
165                             uplimit[j])
166                     {
167                         i--;
168                         break;
169                     }
170                 }
171             }
172         }
173         else
174         {
175             for(int j = 0;j<NumOfParameter;j++)
176             {
177                 offspring[2*i].parameter[j] = downlimit[j] + (rand()%50)/50.0*(uplimit[j]-downlimit[j]);
178                 offspring[2*i+1].parameter[j] = downlimit[j] + (rand()%50)/50.0*(uplimit[j]-downlimit[j]);
179             }
180         }
181     }
182 }
183 
184 void Genetic::combinationpop(Individuals *Initialpop,Individuals *offspring,Individuals *Combinationpop,int populationsize)
185 {
186     for(int i = 0;i<populationsize*2;i++)
187     {
188         if(i < populationsize)
189             Combinationpop[i] = Initialpop[i];
190         else
191             Combinationpop[i] = offspring[i-populationsize];
192     }
193 }
194 
195 void Genetic::mutation(Genetic::Individuals *Initialpop, int population)
196 {
197     srand(time(NULL));
198     for(int i = 0;i<population;i++)
199     {
200         double a = rand()%100/100.0;
201 
202         if(a <= mutationproability)
203         {
204             for(int j = 0;j<NumOfParameter;j++)
205             {
206                 Initialpop[i].parameter[j] = downlimit[j] + (rand()%50)/50.0*(uplimit[j]-downlimit[j]);
207             }
208         }
209     }
210 }
211 
212 void Genetic::selectbestpop(Individuals *Combinationpo,Individuals *Initialpop, int population)
213 {
214     for(int i = 0;i<population;i++)
215         Initialpop[i] = Combinationpo[population+i];
216 }
217 
218 void Genetic::printbestindivil(Genetic::Individuals *Initialpop, int populationsize,int Iteration)
219 {
220     cout<<"
";
221     cout<<""<<Iteration;
222     for(int j = 0;j<NumOfParameter;j++)
223     {
224         cout<<setw(20)<<Initialpop[populationsize-1].parameter[j];
225     }
226     cout<<setw(20)<<Initialpop[populationsize-1].fitness;
227 }
228 
229 void Genetic::getAccurateResult(Genetic::Individuals *Initialpop, int population)
230 {
231     for(int j = 0;j<population;j++)
232     {
233         for(int i = 0;i<NumOfParameter;i++)
234         {
235             Individuals temp = Initialpop[j];
236             Individuals temp1 = Initialpop[j];
237             temp.parameter[i] = temp.parameter[i]*(1+Accurate);
238             if(getfitnessofindiv(temp) > getfitnessofindiv(Initialpop[i]) && temp.parameter[i] <= uplimit[i] &&
239                     temp.parameter[i] >= downlimit[i])
240             {
241                 Initialpop[j] = temp;
242             }
243             temp1.parameter[i] = temp1.parameter[i]*(1-Accurate);
244             if(getfitnessofindiv(temp1) > getfitnessofindiv(Initialpop[i]) && temp1.parameter[i] <= uplimit[i] &&
245                     temp1.parameter[i] >= downlimit[i])
246             {
247                 Initialpop[j] = temp1;
248             }
249         }
250     }
251 }
252 
253

View Code

使用注意事项：

a.根据具体的目标函数修改评价函数方程，

b.按照程序运行提示傻瓜式的输入相应的参数即可，

c.Accurate 参数用于当目标函数趋于稳定状态时的优化，即探测此时自变量该精度变化范围内的目标函数变化情况，从而获得更为优越的目标值。应注意的是，当要求精度越高时，该参数要求尽量小，同时迭代次数应该尽可能地高。

d.本例中涉及一个任意维的单目标测试函数，使用源代码直接按照提示步骤输入相应的各个变量上下限及迭代次数即可。