首页 > 代码库 > 基于实数编码（离散杂交+自适应变异），线性排名选择的遗传算法（附代码）
基于实数编码（离散杂交+自适应变异），线性排名选择的遗传算法（附代码）
我们来看一个很简单的小问题f=x1+x2+x3+x4,x1、x2、x3、x4是大于等于10小于等于100的实数，求f的最大值。
这个小学生就能解决的问题我今天打算用遗传算法来解决，你可能说这不是智障吗？但是其实这只是一个小例子，因为用同样的方法，你可以解决f=x1^x2*x3^x4/x2^x1*x4^x3甚至是更复杂的问题，下面就来详细讲一讲。
基于对遗传算法的一般性了解，我就不再赘述详细过程（其实是因为上一篇写过了懒得再写一遍），只谈谈实数编码和线性排名选择策略。
实数编码顾名思义就是用实数进行编码，实数来做染色体的基因，实数构成染色体，他的本质其实是用问题的一个解空间来做一个染色体，比如{20.5658.15.2385，89.0000,56.4400}，就是上面小问题的一个解空间，就可以把它作为一个染色体用于进化，其中的每一个x1,x2都是一个基因，那些交叉，变异都是基于这样的设定的。
在这里插一句，实数编码和整数编码的思想是极为类似的，但是实数编码的解空间更大更复杂。
现在来讲讲实数编码的交叉和变异
1、交叉
实数编码的杂交方式有离散杂交，算数杂交等等，本例只讲解离散杂交。
离散杂交和二进制的杂交是十分类似的，（可以）选定一个基因位，然后将选定的两个染色体在这个位置之后的基因进行交换（注意基因的定义区间是不变的）。
注意，在实数编码中，交叉的作用不是很大。
2、变异
实数编码的变异包括均匀性变异、正态性变异、非一致性变异、自适应变异、多级变异等，本例只讲解自适应变异和非一致性变异。
（1）非一致性变异
在传统的遗传算法中，突变的情况是与代数无关的。但是进化刚开始时，就是需要向各个方向大步发展进行尝试，进化到了后期，解已经相对较优了，进行局部搜索可能更有利于找到更好的解。显然传统的方法是不行的，必须找到一种将变异幅度和代数相联系的策略。
所以给出如下方法：s={v1,v2,v3,v4……},vk被选中进行变异，它的定义区间为{ak,bk},
vk1=vk+h(t,bk-vk); vk2=vk-h(t,vk-ak);
（t为代数，h（t,y）=y*(1-r^(1-t/T)^p),r是0~1的随机数，T为最大代数，p式一个参数，一般取值为2~5）
新的vk随机在vk1和vk2中进行选取，这样就实现了之前提出要求。
（2）自适应性变异
非一致性变异加强了局部搜索能力，但是与解的好坏无关，但是我们可能希望的是好的解搜索范围较小，坏的解搜索范围较大这样，所以在非一致性变异上进行一些修正。
我们只需要将h(t,y)中的t换为T，T是一个与解的质量有关的数，
T=1-f(s)/fmax
f(s)是某个体的适应值，fmax是所解问题的最优结果，当然fmax不太好确定，所以找一个近似替代就可以了，比如当代最优解或是历史最优解。
3、线性排名选择策略
基于适应值比例的算法（轮盘赌、繁殖池）比较容易陷入过早收敛和停滞现象，排名选择策略可以避免这个问题。
我们只介绍线性排名选择策略。
顾名思义，排名策略嘛，就是要所有的解按照适应值进行排排坐，各自都有一个排名，然后我们按照大家的排名制定一个被选中的概率（然后根据这个概率进行轮盘赌），这就避免了某些个体很多就可以在轮盘赌中获得很大优势，变成了强的更有机会，但是弱者的生存机会也没被剥夺。
被选中的概率为pi=(a-b/(n+1))/n，n为排名，a，b有个一般取值，1≤a≤2，一般取1.1,b=2a-2.
接下来是代码部分。
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <vector> 5 #include <math.h> 6 using namespace std; 7 8 9 //种群总数 10 const int popSize=1000; 11 //执行代数 12 const int maxGen=200; 13 //染色体长度 14 const int chromSize=4; 15 //交叉概率 16 const double Pc=0.7; 17 //变异概率 18 const double Pm=0.3; 19 //线性排名选择参数1 20 const double Pa=1.1; 21 //线性排名选择参数2 22 const double Pb=0.2; 23 //变量定义上限 24 const double up=100; 25 //变量定义下限 26 const double down=10; 27 28 29 30 //遗传个体类 31 class indivadual 32 { 33 public: 34 //构造函数 35 void indivadula(){}; 36 //染色体 37 vector<double> chrom; 38 //目标值 39 double objectValue; 40 //适应值 41 double fitValue; 42 }; 43 44 45 //进化处理类 46 class Evalution 47 { 48 private: 49 //种群 50 vector <indivadual> Population; 51 //最好个体 52 indivadual Best; 53 //最好个体下标 54 int BestIndex; 55 //最坏个体 56 indivadual Worst; 57 //最坏个体下标 58 int WorstIndex; 59 //历史最佳 60 indivadual HistoryBest; 61 //平均适应值 62 double Avg; 63 //初始化种群 64 void Initialization(); 65 //选择算子 66 void SeletPop(); 67 //交叉算子 68 void CrossPop(); 69 //变异算子 70 void VaryPop(); 71 //优化 72 void OptimizePop(); 73 //排序辅助函数 74 //bool compare(indivadual a,indivadual b); 75 public: 76 //构造函数，调用初始化函数 77 Evalution(); 78 //评价函数 79 void Evaluate(); 80 //生成下一代函数 81 void NextPopulation(); 82 //输出 83 void OutPut(); 84 //代数 85 int gen; 86 }; 87 88 Evalution::Evalution() 89 { 90 Initialization(); 91 } 92 93 //初始化种群 94 void Evalution::Initialization() 95 { 96 int i=0,j=0; 97 Population.resize(popSize); 98 for(i=0;i<popSize;i++) 99 { 100 Population[i].chrom.resize(chromSize); 101 for(j=0;j<chromSize;j++) 102 { 103 //随机值范围为10-100 104 double r=(rand()%9000)/100.0+10.01; 105 Population[i].chrom[j]=r; 106 } 107 } 108 Best=Population[0]; 109 Best.fitValue=http://www.mamicode.com/0; 110 Worst=Population[0]; 111 Worst.fitValue=http://www.mamicode.com/1000; 112 BestIndex=0; 113 WorstIndex=0; 114 gen=0; 115 Avg=0; 116 } 117 118 //评价适应值，目标值，最好个体，最坏个体，历史最佳个体 119 void Evalution::Evaluate() 120 { 121 122 int i=0,j=0; 123 vector<double> value; 124 value.resize(chromSize); 125 for(i=0;i<popSize;i++) 126 { 127 for (j=0;j<chromSize;j++) 128 { 129 value[j]=Population[i].chrom[j]; 130 } 131 //评估函数为f=(a/b+c/d)/(b/a+d/c); 132 //Population[i].objectValue=http://www.mamicode.com/Population[i].fitValue=(value[0]/value[1]+value[2]/value[3])/(value[1]/value[0]+value[3]/value[2]);>133 //评估函数为f=a+b+c+d 134 Population[i].objectValue=http://www.mamicode.com/Population[i].fitValue=value[0]+value[1]+value[2]+value[3]; 135 if (Population[i].fitValue>Best.fitValue) 136 { 137 Best=Population[i]; 138 BestIndex=i; 139 } 140 if (Population[i].fitValue<Worst.fitValue) 141 { 142 Worst=Population[i]; 143 WorstIndex=i; 144 } 145 } 146 if (Best.fitValue>HistoryBest.fitValue) 147 { 148 HistoryBest=Best; 149 } 150 for (i=0;i<popSize;i++) 151 { 152 Avg+=Population[i].fitValue; 153 } 154 Avg/=popSize; 155 } 156 157 158 //生成新一代个体 159 void Evalution::NextPopulation() 160 { 161 SeletPop(); 162 CrossPop(); 163 VaryPop(); 164 Evaluate(); 165 OptimizePop(); 166 } 167 168 //输出 169 void Evalution::OutPut() 170 { 171 cout<<"当前代数"<<++gen<<" 平均值"<<Avg<<" 最好个体适应值"<<Best.fitValue<<"最好个体基因"; 172 int i=0; 173 for (i=0;i<chromSize;i++) 174 { 175 cout<<Best.chrom[i]<<" "; 176 } 177 cout<<endl; 178 } 179 180 //sort函数的辅助函数 181 bool compare(indivadual a,indivadual b) 182 { 183 if (a.fitValue>b.fitValue) 184 { 185 return true; 186 } 187 if (a.fitValue>b.fitValue) 188 { 189 return false; 190 } 191 return false; 192 } 193 194 //线性排名选择 195 void Evalution::SeletPop() 196 { 197 sort(Population.begin(),Population.end(),compare); 198 double p[popSize],selection[popSize]; 199 indivadual newPopulation[popSize]; 200 double FitSum=0; 201 int i=0,j=0,index=0,popindex=0; 202 //计算分配概率 203 for (i=0;i<popSize;i++) 204 { 205 j=i+1; 206 p[i]=(Pa-Pb/(j+1))/j; 207 } 208 //求分配概率的总和 209 for(index=0;index<popSize;index++) 210 { 211 FitSum+=p[index]; 212 } 213 214 //确定轮盘分布 215 for(index=0;index<popSize;index++) 216 { 217 selection[index]=p[index]/FitSum; 218 } 219 for(index=1;index<popSize;index++) 220 { 221 selection[index]=selection[index]+selection[index-1]; 222 } 223 //用轮盘进行随机选取，形成新的种群 224 for(popindex=0;popindex<popSize;popindex++) 225 { 226 double n= (rand()%100)/100.0; 227 index=0; 228 while(n>selection[index]) 229 index++; 230 newPopulation[popindex]=Population[index]; 231 } 232 //将刚产生的群体替换为系统的群体 233 for(index=0;index<popSize;index++) 234 { 235 Population[index]=newPopulation[index]; 236 } 237 } 238 239 240 241 242 //杂交算子,离散杂交 243 void Evalution::CrossPop() 244 { 245 int index=0,position=0,i=0,temp=0,t=0; 246 for(;index<popSize;index++) 247 { 248 indivadual temp; 249 int r=rand()%popSize; 250 temp=Population[index]; 251 Population[index]=Population[r]; 252 Population[r]=temp; 253 } 254 for(index=0;index<popSize;index+=2) 255 { 256 t=rand()%1000/1000.0; 257 if (t<Pc) 258 { 259 position=rand()%chromSize; 260 for (i=position+1;i<chromSize;i++) 261 { 262 temp=Population[index+1].chrom[i]; 263 Population[index+1].chrom[i]=Population[index].chrom[i]; 264 Population[index].chrom[i]=temp; 265 266 } 267 268 } 269 270 } 271 } 272 273 274 //变异算子,自适应性变异 275 void Evalution::VaryPop() 276 { 277 int i=0,j=0; 278 for (i=0;i<popSize;i++) 279 { 280 for (j=0;j<chromSize;j++) 281 { 282 double r=rand()%1000/1000.0; 283 if (r<Pm) 284 { 285 double t=1-Population[i].fitValue*0.9999/Best.fitValue; 286 //突变区间 287 double u=(1-pow(r,pow(t,2)))*(up-Population[i].chrom[j]); 288 if (u>up) 289 { 290 u=up; 291 } 292 if (u<down) 293 { 294 u=down; 295 } 296 double l=(1-pow(r,pow(t,2)))*(Population[i].chrom[j]-down); 297 if (l>up) 298 { 299 l=up; 300 } 301 if (l<down) 302 { 303 l=down; 304 } 305 306 int p=rand()%2; 307 if (p==0) 308 { 309 Population[i].chrom[j]=u; 310 } 311 else 312 Population[i].chrom[j]=l; 313 } 314 } 315 } 316 } 317 318 //优化 319 void Evalution::OptimizePop() 320 { 321 Population[WorstIndex] = HistoryBest; 322 } 323 324 int main() 325 { 326 Evalution eva; 327 eva.Evaluate(); 328 eva.OutPut(); 329 while(eva.gen<maxGen) 330 { 331 eva.NextPopulation(); 332 eva.Evaluate(); 333 eva.OutPut(); 334 } 335 }
这个代码中是有个问题的，就是优化函数的策略是把历史最佳替代当代最差，这个可能会容易陷入局部最优。目前想到的更好的策略是如果连续三代的历史最佳都不变，就对历史最佳以一个很小的概率进行突变。
然后说点vector，如果想不初始化就用，就用resize函数定义一个大小，那么会初始化这个大小的空间，然后就可以随便使用了。
基于实数编码（离散杂交+自适应变异），线性排名选择的遗传算法（附代码）