基于遗传算法的蚁群优化算法

来源：互联网   发布日期：2011-10-01 11:45:11   浏览：125824次  

基于遗传算法的蚁群优化算法 (2010-10-24 15:35:32)

标签： 遗传算法 蚁群算法 qos web服务选择 混合智能 杂谈 分类： 技术

遗传算法有一个最大的特点就是能狗进行快速的全局搜索，所以遗传算法收敛速度快，进化时间段，但是遗传算法没有正反馈和负反馈机制，以至于遗传算法在进行金华市有很长时间都只在做无用的进化和验算。蚁群算法具有正反馈机制，能够机制的将进化的信息反馈到下一轮的进化中，但是缺点就是收敛速度慢，而且全局搜索能力较差，如果将这两种进化算法结合寄来既能够使用遗传算法的全局搜索能力又能够使用蚁群算法的正反馈机制，是否可惜呢？

答案是肯定的。

一般情况下，遗传和蚁群的混合分为两种情况，一种是以遗传为主题的算法，另一种是以蚁群算法为主体的算法，博主正在做Web服务选择的问题，所以想到了使用这种混合的算法去解决打过摸得Web服务选择问题，因为蚁群算法中的alpha、beta和rou直接影响到转移galveston和下一步赢得进化情况，所以这三个参数的选取显得至关重要，在传统的蚁群算法中，这三个参数的选区是依照经验的，没有什么精确地方法去确定这三个值，博主使用遗传算法去优化者三个参数，取得了Web服务选择问题中的优良效果，下面是博主的算法源程序和效果对比图：

package gaaca;

import java.text.DecimalFormat;
import java.util.Random;

 

public class GAACASelect {

 
 public static int var_num=3;//带求解的变量个数
 public static double alpha_Max=2.0;//蚁群算法中启发因子alpha的最大值，值区间(1.0,4.0]
 public static double beta_Max=4.0;//蚁群算法中期望因子beta的最大值，值区间(1.0,4.0]
 public static double rou_Max=0.01;//蚁群算法中挥发rou的最大值，值区间(0.0,1.0)
 public static int popution=10;//遗传算法中，种群大小
 public static String []pop=new String[popution];//存储染色体的编码
 public static double []var_value=new double[3];//在解码时存储变量的值
 public static double [][]initpop=new double[var_num][popution];//存储种群的初始化值
 public static double [][]result=new double[var_num][popution];//种群代表的结果
 public static double []fitness=new double[popution];//用于存储染色体的适应度值
 public static double []best_var=new double[3];//存储最优组合
 public static double pc=0.35;//交叉概率
 public static double pm=0.08;//变异概率
 public static Random random=new Random();//程序中所有随机数都由它产生
    public static double[]p=new double[popution];//轮盘赌方法个体适应度概率(按比例的适应度分配)选择概率
    public static double[]q=new double[popution];//q[i]是前n项p之和（累积概率）
 public static int[][]class1={//服务类1的决策矩阵
     {12 ,16 ,12 ,15 ,15 ,11 ,17 ,16 ,20 ,7 },
     {6 ,21 ,3 ,16 ,22 ,9 ,9 ,20 ,22 ,4 },
     {6 ,9 ,3 ,5 ,15 ,15 ,18 ,11 ,15 ,5 },
     {6 ,21 ,16 ,4 ,16 ,19 ,11 ,17 ,19 ,5 },
     {8 ,11 ,18 ,18 ,21 ,4 ,15 ,6 ,22 ,6 }
     };
 public static int[][]class2={//服务类2的决策矩阵
     {9 ,9 ,17 ,12 ,21 ,12 ,22 ,9 ,21 ,9 ,7 ,20 ,3 ,14 ,6 ,5 ,21 ,14 ,16 ,19 },
     {3 ,21 ,9 ,4 ,3 ,8 ,5 ,6 ,4 ,7 ,8 ,11 ,18 ,8 ,15 ,19 ,17 ,4 ,3 ,7 },
     {17 ,6 ,12 ,6 ,19 ,20 ,18 ,19 ,19 ,11 ,4 ,16 ,22 ,3 ,19 ,18 ,6 ,3 ,17 ,11 },
     {8 ,15 ,12 ,7 ,5 ,7 ,17 ,16 ,19 ,5 ,18 ,16 ,4 ,8 ,13 ,8 ,17 ,3 ,14 ,21 },
     {9 ,21 ,17 ,19 ,12 ,3 ,12 ,11 ,3 ,9 ,20 ,19 ,5 ,6 ,20 ,6 ,8 ,22 ,14 ,6 }
     };
    public static int[][] class3={//服务类3的决策矩阵
     {8 ,19 ,4 ,3 ,19 ,22 ,11 ,9 ,18 ,11 ,14 ,18 ,14 ,21 ,15 ,13 ,14 ,18 ,19 ,9 ,21 ,16 ,16 ,5 ,21 ,4 ,12 ,22 ,12 ,18 },
     {22 ,11 ,11 ,16 ,7 ,13 ,21 ,15 ,16 ,5 ,13 ,7 ,15 ,14 ,9 ,12 ,12 ,7 ,6 ,17 ,7 ,22 ,21 ,6 ,3 ,16 ,13 ,7 ,5 ,5 },
     {6 ,6 ,7 ,5 ,10 ,19 ,4 ,21 ,6 ,22 ,22 ,20 ,22 ,18 ,4 ,14 ,7 ,22 ,14 ,22 ,17 ,17 ,6 ,4 ,9 ,4 ,17 ,17 ,3 ,10 },
     {3 ,7 ,5 ,4 ,8 ,6 ,17 ,7 ,4 ,13 ,14 ,3 ,9 ,15 ,7 ,16 ,8 ,14 ,16 ,20 ,14 ,5 ,21 ,3 ,18 ,14 ,17 ,22 ,13 ,7 },
     {16 ,11 ,6 ,18 ,13 ,15 ,8 ,9 ,4 ,14 ,13 ,16 ,4 ,19 ,4 ,22 ,13 ,12 ,15 ,10 ,20 ,13 ,20 ,21 ,12 ,18 ,10 ,22 ,21 ,8 }
     };
    public static int[][]class4={//服务类4的决策矩阵
     {14 ,20 ,20 ,18 ,17 ,14 ,8 ,3 ,15 ,12 ,20 ,5 ,18 ,10 ,7 ,3 ,22 ,7 ,12 ,22 ,11 ,15 ,22 ,4 ,7 ,12 ,7 ,7 ,18 ,14 ,19 ,17 ,14 ,10 ,22 ,9 ,10 ,22 ,3 ,16 },
     {15 ,7 ,6 ,18 ,14 ,20 ,13 ,16 ,6 ,7 ,3 ,11 ,6 ,18 ,17 ,18 ,3 ,8 ,5 ,4 ,19 ,5 ,22 ,13 ,3 ,16 ,10 ,21 ,15 ,17 ,12 ,4 ,15 ,4 ,9 ,5 ,7 ,13 ,14 ,8 },
     {20 ,21 ,20 ,22 ,22 ,9 ,9 ,13 ,13 ,14 ,3 ,21 ,20 ,14 ,9 ,15 ,11 ,3 ,3 ,5 ,4 ,22 ,3 ,11 ,17 ,22 ,3 ,17 ,20 ,6 ,5 ,5 ,19 ,17 ,9 ,19 ,13 ,17 ,3 ,9 },
     {11 ,4 ,21 ,21 ,8 ,12 ,5 ,4 ,18 ,18 ,20 ,17 ,14 ,18 ,15 ,17 ,11 ,13 ,6 ,22 ,12 ,11 ,7 ,6 ,8 ,3 ,9 ,7 ,10 ,14 ,21 ,5 ,7 ,13 ,11 ,21 ,8 ,4 ,22 ,14 },
     {14 ,20 ,11 ,13 ,4 ,4 ,20 ,5 ,18 ,21 ,4 ,17 ,4 ,11 ,15 ,22 ,11 ,20 ,16 ,10 ,18 ,7 ,11 ,11 ,10 ,21 ,13 ,12 ,22 ,22 ,3 ,17 ,5 ,19 ,3 ,19 ,6 ,17 ,7 ,21 }
     };
    public static int antcount=3;//蚂蚁数量
    public static double initpheromone=0.1;//初始信息素浓度素
    public static int num[]={class1[0].length,class2[0].length,class3[0].length,class4[0].length};//用于简化记录每个服务类中原子服务的个数
    public static double [][]tao01=new double[1][num[0]];//开始结点与1#服务类之间的信息素矩阵
    public static double [][]tao12=new double[num[0]][num[1]];//1#服务类与2#服务类之间的信息素矩阵
    public static double [][]tao23=new double[num[1]][num[2]];//2#服务类与3#服务类之间的信息素矩阵
    public static double [][]tao34=new double[num[2]][num[3]];//3#服务类与4#服务类之间的信息素矩阵
    public static Ants []ants=new Ants[antcount];//蚂蚁
    //public static double rou=0.001;//信息素挥发因子
    public static double Q=0.1;//信息素强度
    public static double bestlength;//初始的最优路径长度
    public static int []bestpath={0,0,0,0};//用于记录最优路径
    public static int generation;//发现最优解的迭代次数
    public static long time;//进化耗时
    public static long endtime;
    public static DecimalFormat df=new DecimalFormat("0.00000");//double型数据的精度控制
 public static double[][] initpopution(){//遗传算法初始化种群，产生随机的alph beta和rou
  
  for(int i=0;i<popution;i++){
   initpop[0][i]=Double.parseDouble(df.format(Math.random()*alpha_Max));
   initpop[1][i]=Double.parseDouble(df.format(Math.random()*beta_Max));
   initpop[2][i]=Double.parseDouble(df.format(Math.random()*rou_Max));
  }
  return initpop;
 }
 public GAACASelect(double [][]initpop){
  for(int i=0;i<var_num;i++){
   for(int j=0;j<popution;j++){
    result[i][j]=initpop[i][j];
   }
  }
 }
 public static void init() {//蚁群算法，参数初始化
  // TODO Auto-generated method stub
  for(int i=0;i<num[0];i++){
   tao01[0][i]=initpheromone;
  }
  for(int i=0;i<num[0];i++){
   for(int j=0;j<num[1];j++){
    tao12[i][j]=initpheromone;
   }
  }
  for(int i=0;i<num[1];i++){
   for(int j=0;j<num[2];j++){
    tao23[i][j]=initpheromone;
   }
  }
  for(int i=0;i<num[2];i++){
   for(int j=0;j<num[3];j++){
    tao34[i][j]=initpheromone;
   }
  }
  for(int i=0;i<antcount;i++){
   ants[i]=new Ants();
   for(int j=0;j<5;j++){ 
    ants[i].path[j]=0;
   }
  }
   bestlength=Integer.MAX_VALUE;
   generation=0;
   time=0;
 }
 
 public static void fitness(int evolutionnum) {//蚁群主体程序运行
  
  System.out.println("第"+evolutionnum+"代--->");
  for(int i=0;i<popution;i++){
   double localbestpathlength=100000.0;
   for(int j=0;j<antcount;j++){
    //每一只蚂蚁的移动
    ants[j].path[0]=0;
    ants[j].path[1]=ants[j].selectNextService(1,tao01,0,result[0][i],result[1][i]);//从第1个服务类中选择选择
    ants[j].path[2]=ants[j].selectNextService(2,tao12,ants[j].path[1],result[0][i],result[1][i]);//从第2个服务类中选择选择
    ants[j].path[3]=ants[j].selectNextService(3,tao23,ants[j].path[2],result[0][i],result[1][i]);//从第3个服务类中选择选择
    ants[j].path[4]=ants[j].selectNextService(4,tao34,ants[j].path[3],result[0][i],result[1][i]);//从第4个服务类中选择选择
    //计算该蚂蚁走过的路径长度
    //System.out.println(ants[j].path[1]+"\t"+ants[j].path[2]+"\t"+ants[j].path[3]+"\t"+ants[j].path[4]+"\t");
    double pathlength=ants[j].caculatePathlength(ants[j].path);
    //System.out.println(pathlength);
    //和当前最优值比较
    if(pathlength<localbestpathlength){
     localbestpathlength=pathlength;
    }
    if(pathlength<bestlength){
     bestlength=pathlength;//用于记录最短路径长度
     best_var[0]=result[0][i];//保存最优的alpha、beta、rou组合
     best_var[1]=result[1][i];
     best_var[2]=result[2][i];
     if(evolutionnum>generation){
      generation=evolutionnum;
     }
     //System.out.println("第"+i+"代第" + j + "只蚂蚁发现最优解："+bestlength);
     for(int k=0;k<bestpath.length;k++){
      bestpath[k]=ants[j].path[k+1];//用于记录最优路径
     }
     endtime=System.currentTimeMillis();
    }
    //updatepheromone(j);
   }
   fitness[i]=localbestpathlength;
   //System.out.println(fitness[i]);
   updatepheromone(result[2][i]);
   
  }
 }

 public static void updatepheromone(double rou) {//跟新蚁群算法中的路径上的信息素浓度
  
  for(int i=0;i<num[0];i++){//原有信息素的剩余部分
   tao01[0][i]*=(1-rou);
  }
  for(int i=0;i<num[0];i++){
   for(int j=0;j<num[1];j++){
    tao12[i][j]*=(1-rou);
   }
  }
  for(int i=0;i<num[1];i++){
   for(int j=0;j<num[2];j++){
    tao23[i][j]*=(1-rou);
   }
  }
  for(int i=0;i<num[2];i++){
   for(int j=0;j<num[3];j++){
    tao34[i][j]*=(1-rou);
   }
  }
  for(int k=0;k<antcount;k++){
   tao01[0][ants[k].path[1]]+=Q/ants[k].caculatePathlength(ants[k].path);//信息素增加
   tao12[ants[k].path[1]][ants[k].path[2]]+=Q/ants[k].caculatePathlength(ants[k].path);
   tao23[ants[k].path[2]][ants[k].path[3]]+=Q/ants[k].caculatePathlength(ants[k].path);
   tao34[ants[k].path[3]][ants[k].path[4]]+=Q/ants[k].caculatePathlength(ants[k].path);
  }
  
 }
 
 public static void printResult() {//打印程序结果
  //System.out.print("开始结点 --->");
  for(int i=0;i<bestpath.length;i++){
   System.out.print(bestpath[i]+" --->");
  }
  //System.out.println("结束结点");
  //System.out.println("最优解为:"+bestlength);
  System.out.println(best_var[0]+"\t"+best_var[1]+"\t"+best_var[2]);
  System.out.println(bestlength+"\t"+generation+"\t"+(endtime-time));
  
 }
 public static String[] encode(){//十进制转化为二进制，编码过程
  
  for(int i=0;i<popution;i++){
   String result1="",result2="",result3="";
   int media_data1=(int)Math.floor((result[0][i]/alpha_Max)*((Math.pow(2, 20)-1)));
   result1=Integer.toBinaryString(media_data1);
   if(result1.length()<20){//补位操作，便于解码
    int addition=20-result1.length();
    for(int j=0;j<addition;j++){
     result1="0"+result1;
    }
   }
   //System.out.print(result1);
   int media_data2=(int)Math.floor((result[1][i]/beta_Max)*((Math.pow(2, 20)-1)));
   result2=Integer.toBinaryString(media_data2);
   if(result2.length()<20){//补位操作，便于解码
    int addition=20-result2.length();
    for(int j=0;j<addition;j++){
     result2="0"+result2;
    }
   }
   //System.out.print(result2);
   int media_data3=(int)Math.floor((result[2][i]/rou_Max)*((Math.pow(2, 10)-1)));
   result3=Integer.toBinaryString(media_data3);
   if(result3.length()<10){//补位操作，便于解码
    int addition=10-result3.length();
    for(int j=0;j<addition;j++){
     result3="0"+result3;
    }
   }
   //System.out.println(result3);
   pop[i]=result1+result2+result3;
   //System.out.println(pop[i]+"\t"+pop[i].length());
  }
  return pop;
 }
 
 public static double[][] dencode(){//二进制字符串转化为十进制实数，解码过程
  
  for(int k=0;k<popution;k++){
   String src=pop[k];
   String alpha_subString=src.substring(0, 20);//截取染色体中alpha片段
   String beta_subString=src.substring(20, 40);//截取染色体中beta片段
   String rou_subString=src.substring(40, 50);//截取染色体中rou片段
   char []decode_alpha_temp=alpha_subString.toCharArray();//讲染色体片段转化为单个字符数组，便于求值
   char []decode_beta_temp=beta_subString.toCharArray();
   char []decode_rou_temp=rou_subString.toCharArray();
   int []decode_alpha=new int[decode_alpha_temp.length];//将上述字符值转化为可以计算的整数值存储
   int []decode_beta=new int[decode_beta_temp.length];
   int []decode_rou=new int[decode_rou_temp.length];
   int alpha_media=0;//解码前的中间值
   int beta_media=0;
   int rou_media=0;
   for(int i=0;i<decode_alpha_temp.length;i++){
    decode_alpha[i]=Integer.parseInt(String.valueOf(decode_alpha_temp[i]));
    decode_beta[i]=Integer.parseInt(String.valueOf(decode_beta_temp[i]));
             alpha_media+=decode_alpha[i]*Math.pow(2, (decode_alpha.length-i-1));
             beta_media+=decode_beta[i]*Math.pow(2, (decode_beta.length-1-i));
   }
   for(int i=0;i<decode_rou_temp.length;i++){
    decode_rou[i]=Integer.parseInt(String.valueOf(decode_rou_temp[i]));
    rou_media+=decode_rou[i]*Math.pow(2, (decode_rou.length-1-i));
   }
   result[0][k]=Double.valueOf(df.format(((alpha_media/(Math.pow(2, alpha_subString.length())-1))*alpha_Max)));
   result[1][k]=Double.valueOf(df.format(((beta_media/(Math.pow(2, beta_subString.length())-1))*beta_Max)));
   result[2][k]=Double.valueOf(df.format(((rou_media/(Math.pow(2, rou_subString.length())-1))*rou_Max)));
  }
  return result;
 }
 
 public static void crossover(){//交叉操作，多点交叉
  for(int i=0;i<popution;i++){
   double d=random.nextDouble();
   if(d<pc){
    int k1=random.nextInt(popution);//选择要交叉的两条染色体
    int k2=random.nextInt(popution);
       int position1=random.nextInt(20);//第一个交叉点，alpha的交叉
    int position2=random.nextInt(20);//第二个交叉点，beta的交叉
    int position3=random.nextInt(10);//第三个交叉点，rou的交叉
    String alpha1=pop[k1].substring(0, 20);//获取需要交叉的alpha字符串
    String alpha2=pop[k2].substring(0, 20);
    String beta1=pop[k1].substring(20, 40);//获取需要交叉的beta字符串
    String beta2=pop[k2].substring(20, 40);
    String rou1=pop[k1].substring(40, 50);//获取需要交叉的rou字符串
    String rou2=pop[k2].substring(40, 50);
    pop[k1]=alpha1.substring(0, position1)+alpha2.substring(position1, 20)+beta1.substring(0, position2)+beta2.substring(position2, 20)+rou1.substring(0, position3)+rou2.substring(position3, 10);
          pop[k2]=alpha2.substring(0, position1)+alpha1.substring(position1, 20)+beta2.substring(0, position2)+beta1.substring(position2, 20)+rou2.substring(0, position3)+rou1.substring(position3, 10);
   }
  }
 }
 
 public static void mutation(){
  for(int i=0;i<popution;i++){
   int mutation_alpha=random.nextInt(20);//alpha变异位置
   int mutation_beta=random.nextInt(20)+20;//beta变异位置
   int mutation_rou=random.nextInt(10)+40;//rou变异位置
   mutation(i,mutation_alpha,mutation_beta,mutation_rou);
  }
 }
 
 
 public static void mutation(int popnum,int position1,int position2,int position3){//按照alpha、beta、rou进行多点变异
  String temp=pop[popnum];
  StringBuffer sb=new StringBuffer(temp);
  if(sb.charAt(position1)=='0'){
   sb.setCharAt(position1, '1');
  }else{
   sb.setCharAt(position1, '0');
  }
  if(sb.charAt(position2)=='0'){
   sb.setCharAt(position2, '1');
  }else{
   sb.setCharAt(position2, '0');
  }
  if(sb.charAt(position3)=='0'){
   sb.setCharAt(position3, '1');
  }else{
   sb.setCharAt(position3, '0');
  }
  pop[popnum]=sb.toString();
 }
 
 public static void roulettwheel(){//使用轮盘赌进行染色体选择
  double sum=0.0;
  for(int i=0;i<popution;i++){
   sum+=fitness[i];
  }
  for(int i=0;i<popution;i++){
   p[i]=fitness[i]/sum;
   q[i]=0.0;
  }
  for(int i=0;i<popution;i++){
   for(int j=0;j<=i;j++){
    q[i]+=p[j];
   }
  }
  
  double []ran=new double[popution];
  String[] tempPop=new String[popution];
  for (int i = 0; i < ran.length; i++) {
      ran[i]=random.nextDouble();
     }
  for (int i = 0; i < ran.length; i++) {
      int k = 0;
      for (int j = 0; j < q.length; j++) {
       if(ran[i]<=q[j])
       {
        k=j;
        break;
       }
       else continue;
      }
      tempPop[i]=pop[k];
     }
     for (int i = 0; i < tempPop.length; i++) {
      pop[i]=tempPop[i];
     }
 }
 public static void run(int totalevolutiongeneration){
  for(int i=0;i< totalevolutiongeneration;i++){
   //System.out.println("第"+i+"代--->");
   evolution(i);
  }
 }
 public static void evolution(int generation){
  encode();
  crossover();
  mutation();
  dencode();
  fitness(generation);
  roulettwheel();
 }
 
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  
  System.out.println("程序开始运行...");
  System.out.println("遗传算法开始初始化...");
  initpopution();
  GAACASelect gaaca=new GAACASelect(initpop);
  System.out.println("遗传算法初始化完成！");
  System.out.println("蚁群算法开始初始化...");
  init();
  time=System.currentTimeMillis();
  System.out.println("蚁群算法初始化完成！");
  System.out.println("程序进化中...");
  run(100);
  System.out.println("程序进化完成！");
  GAACASelect.printResult();
  System.out.println("程序运行耗时:"+(System.currentTimeMillis()-time));
  System.out.println(gaaca.getClass());
 }
}

分享

顶

阅读┊ ┊ ┊┊ ┊打印┊

已投稿到：

排行榜 圈子

加载中，请稍候......

前一篇：java中double型数据精度控制

后一篇：用java实现excel数据批量导入数据库

评论 重要提示：警惕虚假中奖信息       在插画中找寻曾经的美好       关注每日最热门博客 

评论加载中，请稍候...

发评论 旅游行摄，轻品日本       是谁改变了你的博客？       关注每日最热门博客

登录名： 密码： 找回密码 注册

昵   称：

   

验证码： 请点击后输入验证码

以上网友发言只代表其个人观点，不代表新浪网的观点或立场。

< 前一篇java中double型数据精度控制

后一篇 >用java实现excel数据批量导入数据库

赞助本站