基于实数编码（离散杂交+⾃适应变异），线性排名选择的遗传算法（附代码）版权声明：本⽂为博主原创⽂章，转载请注明出处。
我们来看⼀个很简单的⼩问题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>
6using namespace std;
7
8
9//种总数
10const int popSize=1000;
11//执⾏代数
12const int maxGen=200;
13//染⾊体长度
14const int chromSize=4;
15//交叉概率
16const double Pc=0.7;
17//变异概率
18const double Pm=0.3;
19//线性排名选择参数1
20const double Pa=1.1;
21//线性排名选择参数2
22const double Pb=0.2;
23//变量定义上限
24const double up=100;
25//变量定义下限
26const double down=10;
27
28
29
30//遗传个体类
31class indivadual
32 {
33public:
34//构造函数
35void indivadula(){};
36//染⾊体
37    vector<double> chrom;
38//⽬标值
39double objectValue;
42 };
43
44
45//进化处理类
46class Evalution
47 {
48private:
49//种
50    vector <indivadual> Population;
51//最好个体
52    indivadual Best;
53//最好个体下标
54int BestIndex;
55//最坏个体
56    indivadual Worst;
57//最坏个体下标
58int WorstIndex;
59//历史最佳
60    indivadual HistoryBest;
61//平均适应值
62double Avg;
63//初始化种
64void Initialization();
65//选择算⼦
66void SeletPop();
67//交叉算⼦
68void CrossPop();
69//变异算⼦
70void VaryPop();
71//优化
72void OptimizePop();
73//排序辅助函数
74//bool compare(indivadual a,indivadual b);
75public:
76//构造函数，调⽤初始化函数
77      Evalution();
78//评价函数
79void Evaluate();
80//⽣成下⼀代函数
81void NextPopulation();
82//输出
83void OutPut();
84//代数
85int gen;
86 };
87
88 Evalution::Evalution()
89 {
90    Initialization();
91 }
92
93//初始化种
94void Evalution::Initialization()
95 {
96int i=0,j=0;
97    size(popSize);
98for(i=0;i<popSize;i++)
99    {
100        Population[i].size(chromSize);
101for(j=0;j<chromSize;j++)
102        {
103//随机值范围为10-100
104double r=(rand()%9000)/100.0+10.01;
105            Population[i].chrom[j]=r;
106        }
107    }
108    Best=Population[0];
109    Best.fitValue=0;
110    Worst=Population[0];
111    Worst.fitValue=1000;
112    BestIndex=0;
113    WorstIndex=0;
114    gen=0;
115    Avg=0;
116 }
117
118//评价适应值，⽬标值，最好个体，最坏个体，历史最佳个体
119void Evalution::Evaluate()
120 {
121
122int i=0,j=0;
123    vector<double> value;
124    size(chromSize);
125for(i=0;i<popSize;i++)
126    {
127for (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=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=Population[i].fitValue=value[0]+value[1]+value[2]+value[3];
135if (Population[i].fitValue>Best.fitValue)
136        {
137            Best=Population[i];
138            BestIndex=i;
139        }
140if (Population[i].fitValue<Worst.fitValue)
141        {
142            Worst=Population[i];
143            WorstIndex=i;
144        }
145    }
146if (Best.fitValue>HistoryBest.fitValue)
147    {
148        HistoryBest=Best;
149    }
150for (i=0;i<popSize;i++)
151    {
152        Avg+=Population[i].fitValue;
153    }
154    Avg/=popSize;
155 }
156
157
158//⽣成新⼀代个体
159void Evalution::NextPopulation()
160 {
161    SeletPop();
162    CrossPop();
165    OptimizePop();
166 }
167
168//输出
169void Evalution::OutPut()
170 {
171    cout<<"当前代数"<<++gen<<"  平均值"<<Avg<<"  最好个体适应值"<<Best.fitValue<<"最好个体基因"; 172int i=0;
173for (i=0;i<chromSize;i++)
174    {
175        cout<<Best.chrom[i]<<"";
176    }
177    cout<<endl;
178 }
179
180//sort函数的辅助函数
181bool compare(indivadual a,indivadual b)
182 {
183if (a.fitValue>b.fitValue)
184    {
185return true;
186    }
187if (a.fitValue>b.fitValue)
188    {
189return false;
190    }
191return false;
192 }
193
194//线性排名选择
195void Evalution::SeletPop()
196 {
197    sort(Population.begin(),d(),compare);
198double p[popSize],selection[popSize];
199    indivadual newPopulation[popSize];
200double FitSum=0;
201int i=0,j=0,index=0,popindex=0;
202//计算分配概率
203for (i=0;i<popSize;i++)
204    {
205        j=i+1;
206        p[i]=(Pa-Pb/(j+1))/j;
207    }
208//求分配概率的总和
209for(index=0;index<popSize;index++)
210    {
211        FitSum+=p[index];
212    }
213
214//确定分布
215for(index=0;index<popSize;index++)
216    {
217        selection[index]=p[index]/FitSum;
218    }
219for(index=1;index<popSize;index++)
220    {
221        selection[index]=selection[index]+selection[index-1];
222    }
223//⽤进⾏随机选取，形成新的种
224for(popindex=0;popindex<popSize;popindex++)
225    {
226double n=  (rand()%100)/100.0;
227        index=0;
228while(n>selection[index])
229            index++;
230        newPopulation[popindex]=Population[index];
231    }
232//将刚产⽣的体替换为系统的体
233for(index=0;index<popSize;index++)
234    {
235        Population[index]=newPopulation[index];
236    }
237 }
238
239
240
241
242//杂交算⼦，离散杂交
243void Evalution::CrossPop()
244 {
245int index=0,position=0,i=0,temp=0,t=0;
246for(;index<popSize;index++)
247    {
248        indivadual temp;
249int r=rand()%popSize;
250        temp=Population[index];
251        Population[index]=Population[r];
252        Population[r]=temp;
253    }
254for(index=0;index<popSize;index+=2)
255    {
256        t=rand()%1000/1000.0;
257if (t<Pc)
258        {
259              position=rand()%chromSize;
260for (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//变异算⼦,⾃适应性变异
275void Evalution::VaryPop()
276 {
277int i=0,j=0;
278for (i=0;i<popSize;i++)
279    {
280for (j=0;j<chromSize;j++)
281        {
282double r=rand()%1000/1000.0;
283if (r<Pm)
284            {
287double u=(1-pow(r,pow(t,2)))*(up-Population[i].chrom[j]);
288if (u>up)
289                {
290                    u=up;
291                }
292if (u<down)
293                {
294                    u=down;
295                }
296double l=(1-pow(r,pow(t,2)))*(Population[i].chrom[j]-down);
297if (l>up)
298                {
299                    l=up;
300                }
301if (l<down)
302                {
303                    l=down;
304                }
305
306int p=rand()%2;
307if (p==0)
308                {
309                    Population[i].chrom[j]=u;
310                }
311else
312                    Population[i].chrom[j]=l;
313            }
314        }
315    }
316 }
317
resize函数c++318//优化
319void Evalution::OptimizePop()
320 {
321      Population[WorstIndex] = HistoryBest;
322 }
323
324int main()
325 {
326    Evalution eva;
327    eva.Evaluate();
328    eva.OutPut();
<maxGen)
330    {
331        eva.NextPopulation();
332        eva.Evaluate();
333        eva.OutPut();
334    }
335 }
这个代码中是有个问题的，就是优化函数的策略是把历史最佳替代当代最差，这个可能会容易陷⼊局部最优。⽬前想到的更好的策略是如果连续三代的历史最佳都不变，就对历史最佳以⼀个很⼩的概率进⾏突变。
附上这个代码的结果：
是不是觉得有点问题？这个结果不是最优结果啊，最优的结果明明是100,100，100，100，这个结果和最终的结果差距还是⽐较⼤的。
这个结果其实某种程度的体现了遗传算法的根本⽬的：遗传算法的⽬的通过⼀系列操作最终得到在适应值上更⾼的体，⽽不是为了求最优⽽存在的，它是⼀种近似最优的算法，⽽这个近似的程度和种的规模，进化的代数，进化的策略都是有关的，所以不能强求通过遗传算法⾮要得到最优解。对于实数编码来讲，解空间的范围实在是⾮常⼤，也就是说进化的⽅向是⾮常多的，在这个情况下，突变可能已经很难产⽣新的有利基因了，也就是说算法收敛了，当然这是可以通过算法进⾏调节的，但是收敛到了什么程度，也是⽐较难以判断。
附上不同规模的结果（⼤规模的遗传算法⾮常耗时）：
popsize=100
popsize=500
popsize=1000
popsize=5000

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。