ant.java

一个蚁群算法

           }

           //根据还剩下信息素的量调整释放信息素的数值Phe，这里为线性模型即Phe=0.0005*Pheromone_count
           //如果把剩余信息量看成数组count(n)的话，那么根据本模型，
           //count(n)满足下面的递推公式count(n)=(1-0.005)*count(n-1)
           //也就是说count(n)以几何级数的速度递减，这样，蚂蚁刚走出的地方信息素远远高于后走的地方
           //这个模型是否科学？有待研究
           Phe=(int)(0.005*Pheromone_count);

           //如果剩余信息素已经太小了，则按照等差数列递减
           if(Phe<=10)Phe=10;
        }
private boolean JudgeEnd(){
    //这个函数判断是否已经找到了目标点
    //首先获得当前蚂蚁是正在找窝还是在找食物。
    int kind=FoundTimes%2;
    if(kind==0){
        //如果是找食物，那么需要把所有的食物点坐标与当前点比较，距离小于VR就认为是找到
        int i;
        for(i=0;i<local_colony.EndPts;i++){
            if(Distance(nowPt,local_colony.EndPt[i])<=VR){
              //如果找到了食物，就直接移动到食物点
              lastPt=new Point(nowPt.x,nowPt.y);
              nowPt.x=local_colony.EndPt[i].x;
              nowPt.y=local_colony.EndPt[i].y;

              //计算最后的总距离
              Count_distance+=Distance(lastPt,nowPt);
              //比较大小，记录较小的距离
              if(Count_distance<Min_distance||Min_distance<0){
                 Min_distance=Count_distance;
              }
              //清除总距离记录
              Count_distance=0;

              //同时记录这只蚂蚁的目标点是它的窝，起始点是这个找到的食物点
              AimPt=new Point(OriginPt);
              StartPt=new Point(nowPt);
              //并把当前点标为自己找到的食物点
              FoodPt=new Point(nowPt.x,nowPt.y);

              //找到了食物就把找到次数+1
              FoundTimes++;

              //改变主方向为原来方向的镜面反方向
              Main_direct=(Math.PI+Main_direct)%(2*Math.PI);

              //重新把自己能撒的信息素置为最大值
              Pheromone_count=Max_Pheromone;

              //清空记录的所有点
              HistoryPoint.removeAllElements();

              //返回找到为真
              return true;
            }
        }
      //否则没找到
      return false;
    }
    if(kind==1){
        //如果是找窝，因为目标点已经明确，所以比较目标点和当前点的距离，小于VR表示已经找到
        if(Distance(nowPt,AimPt)<=VR){
            lastPt=new Point(nowPt.x,nowPt.y);
            //如果找到了目标，就直接移动到目标点
            nowPt.x=AimPt.x;
            nowPt.y=AimPt.y;

              //计算最后的总距离
              Count_distance+=Distance(lastPt,nowPt);
              //比较大小，记录较小的距离
              if(Count_distance<Min_distance||Min_distance<0){
                  Min_distance=Count_distance;
              }
              //清除总距离记录
              Count_distance=0;
            //把目标点定为食物点，起始点定为窝
            AimPt=new Point(FoodPt);
            StartPt=new Point(OriginPt);

            //重新置信息素
            Pheromone_count=Max_Pheromone;

            //清空历史纪录
            HistoryPoint.removeAllElements();

            //主方向反向
            Main_direct=(Math.PI+Main_direct)%(2*Math.PI);

            //找到次数+1
            FoundTimes++;
            return true;
        }
        return false;
    }
    return false;
}
        private double SelectDirect(){
                //选择方向，最后选择的方向为主方向加一个随机扰动
                double direct,e=0;
                if(Main_direct<0){
                      //如果目前还没有主方向角，就随机的选择一个
		      e=2*Math.PI*Math.random();
                      Main_direct=e;
                }
                //选择主方向角
                direct=Main_direct;

                //做一个随机模型，产生两个随机数，x,y都是[0,1]内的，这样x^2-y^2就是一个
                //[-1，1]的随机数，并且在0点附近的概率大，两边小
                double re=Math.random();
                double re1=Math.random();
                direct+=Math.PI*(re*re-re1*re1)/2;
                if(re<0.02){
                  //以小概率0.02改变主方向的值，主方向的选取为从蚂蚁记住的点中随机选一个点，计算当前点和这个点之间的方向角。
                  int size=(int)(re1*memory)+1;
                  if(HistoryPoint.size()>size){
                    Point pt=(Point)(HistoryPoint.elementAt(HistoryPoint.size()-size));
                    if(pt.x!=nowPt.x||pt.y!=nowPt.y){
                       Main_direct=GetDirection(pt,nowPt);
                    }
                  }
                }
               return direct;

        }
        private Point Evade_obs(int deltx,int delty){
              //这个函数根据决策的位移值进行敝张的判断，算出真实可以移动到的点
              //要移动到的目标点是(nowPt+delt),当前点是nowPt，那么搜索nowPt到(nowPt+delt)
              //这条直线上的所有点，看有没有障碍物！根据直线的参数方程：
              //x=p1x+(p2x-p1x)*t,y=p1y+(p2y-p1y)*t;
              //其中t是参数，取值[0,1]，步长为abs(max{p2x-p1x,p2y-p1y})，
              //p1,p2在这里分别是nowPt和nowPt+delt
              Point pt=new Point(0,0);
              int x,y;
              int delt=deltx;
              if(Math.abs(delty)>Math.abs(deltx))delt=delty;
              if(delt==0)return nowPt;
              for(double t=0;t<=1;t+=1/(double)(Math.abs(delt))){
                  x=(int)(deltx*t+nowPt.x);
                  y=(int)(delty*t+nowPt.y);
                  x=(x+width)%width;
                  y=(y+height)%height;
                  if(local_colony.obs_grid[x][y]>=0){

                     //如果移动方向发现障碍物，那么就改变目标点和主方向
                     //新目标点为障碍物前方的点，主方向随机取值
                     deltx=pt.x-nowPt.x;delty=pt.y-nowPt.y;
                     double disturb=4*Math.PI*(Math.random()-0.5);
                     Main_direct=(disturb+2*Math.PI)%(2*Math.PI);
                     break;
                  }
                  pt=new Point(x,y);
                }

                //计算得出实际能够到达的目标点
		x=(nowPt.x+deltx+width)%width;
		y=(nowPt.y+delty+height)%height;
	        return new Point(x,y);
        }
        private double GetDirection(Point pt1,Point pt2){
        //这个函数为指定两个点pt1和pt2，给出pt1-->pt2的方向角
        //此函数的难度主要在于，我们的世界是球面，因此需要从多个方向计算方向角，
        //其中方向角是所有可能的角中使得两点连线距离最短的角。
               double e;
               int deltx1=pt2.x-pt1.x;
               int deltx2;
               if(pt2.x>pt1.x)deltx2=pt2.x-pt1.x-width;
               else deltx2=pt2.x+width-pt1.x;
               int delty1=pt2.y-pt1.y;
               int delty2;
               if(pt2.y>pt1.y)delty2=pt2.y-pt1.y-height;
               else delty2=pt2.y+height-pt1.y;
               int deltx=deltx1,delty=delty1;
               if(deltx==0&&delty==0)return -1;
               if(Math.abs(deltx2)<Math.abs(deltx1)){
		  deltx=deltx2;
               }
	       if(Math.abs(delty2)<Math.abs(delty1)){
                  delty=delty2;
               }
               if(deltx!=0){
                    e=Math.atan((double)(delty)/(double)(deltx));
                    if(deltx<0){
                       if(e<0) e=e-Math.PI;
                       else e=e+Math.PI;
                    }
                }else{
                    if(delty>0)e=Math.PI/2;
                    else e=-Math.PI/2;
                }
                e=(e+Math.PI*2)%(2*Math.PI);
                return e;
        }
        private double Distance(Point pt1,Point pt2){
        //给定两点pt1,pt2，计算它们之间的距离，难点在于世界是球面，所有有坐标循环的情况，
        //这里计算的是所有可能距离中最小的
            int dx1=pt1.x-pt2.x;
            int dx2;
            int dx,dy;
            if(pt1.x>pt2.x)dx2=pt1.x+width-pt2.x;
            else dx2=pt2.x+width-pt1.x;
            int dy1=pt1.y-pt2.y;
            int dy2;
            if(pt1.y>pt2.y)dy2=pt1.y+height-pt2.y;
            dy2=pt2.y+height-pt1.y;
            if(Math.abs(dx1)<Math.abs(dx2))dx=dx1;
            else dx=dx2;
            if(Math.abs(dy1)<Math.abs(dy2))dy=dy1;
            else dy=dy2;
            return Math.sqrt(dx*dx+dy*dy);
        }
    public void clone(ant ant1){
        //把蚂蚁ant1的属性拷贝到本蚂蚁
    	nowPt=new Point(ant1.nowPt);
        OriginPt=new Point(ant1.OriginPt);
        FoodPt=new Point(ant1.FoodPt);
        StartPt=new Point(ant1.StartPt);
        AimPt=new Point(ant1.AimPt);
        lastPt=new Point(ant1.lastPt);
        VR=ant1.VR;
        id=ant1.id;
        color=ant1.color;
        back_color=ant1.back_color;
        height=ant1.height;
        width=ant1.width;
        local_colony=ant1.local_colony;
        Phe=ant1.Phe;
        mistake=ant1.mistake;
        HistoryPoint=ant1.HistoryPoint;
        Main_direct=ant1.Main_direct;
        FoundTimes=ant1.FoundTimes;
        Max_Pheromone=ant1.Max_Pheromone;
        Pheromone_count=ant1.Pheromone_count;
        memory=ant1.memory;
        Count_distance=ant1.Count_distance;
        Min_distance=ant1.Min_distance;
    }
}