首页 > 代码库 > 基于实数编码(离散杂交+自适应变异),线性排名选择的遗传算法(附代码)

基于实数编码(离散杂交+自适应变异),线性排名选择的遗传算法(附代码)

我们来看一个很简单的小问题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函数定义一个大小,那么会初始化这个大小的空间,然后就可以随便使用了。

基于实数编码(离散杂交+自适应变异),线性排名选择的遗传算法(附代码)