ant.java

java实现的基本蚁群算法

package ant;
import java.awt.*;
import java.applet.*;
import java.util.Vector;

public class ant{
	Point nowPt;//当前点坐标
	int VR;//速度，每次蚂蚁能走动的最大长度
 	int id;//标识
 	Point lastPt;//上一点坐标
	Color color;//蚂蚁的颜色
	Color back_color;//背景的严肃
	int height,width;//世界的尺寸
        int Phe;//每次释放信息素的数值
	Antcolony local_colony;//主程序的指针
        Vector HistoryPoint;//记录一次觅食过程历史上的所有点
        double Main_direct;//主方向
        Point FoodPt;//记录的食物点，是否找到时候判断用
        Point OriginPt;//窝的坐标
        Point AimPt;//目标点，是窝或者食物
        Point StartPt;//起始点，是窝或者食物
        int FoundTimes;//找到食物或者窝的次数
        int Max_Pheromone;//最大能够释放的信息素
        int Pheromone_count;//当前还拥有的信息素的总量
        boolean Judged=false;//判断寻找目标点的工作是否已经进行了
        double mistake;//犯错误的概率
        int memory;//记忆走过点的数目
        double Count_distance;//走过的总路程,为单程的路程，也就是说找到食物或者窝就从新计数了。
        public double Min_distance;//当前这只蚂蚁再没次往返的时候的最小总距离
	public ant(Point nowpt,int vr,int idd,Antcolony colony,Color c,double mist,int mem){
		nowPt=new Point(nowpt.x,nowpt.y);
                OriginPt=new Point(nowpt.x,nowpt.y);
                FoodPt=new Point(nowpt.x,nowpt.y);
                StartPt=new Point(nowpt);
                AimPt=new Point(nowpt);
                lastPt=nowPt;
		VR=vr;
		id=idd;
		color=c;
		back_color=Antcolony.BACK_COLOR;
		height=Antcolony.height;
		width=Antcolony.width;
		local_colony=colony;
                Phe=200;
                mistake=mist;
                HistoryPoint=new Vector();
                Main_direct=-1;
                FoundTimes=0;
                Max_Pheromone=local_colony.Max_Pheromone;
                Pheromone_count=Max_Pheromone;
                memory=mem;
                Count_distance=0;
                Min_distance=-1;
	}
        public void init(){
          nowPt=new Point(OriginPt);
          lastPt=new Point(OriginPt);
          FoodPt=new Point(OriginPt);
          AimPt=new Point(OriginPt);
          StartPt=new Point(OriginPt);
          HistoryPoint.removeAllElements();
          Main_direct=-1;
          FoundTimes=0;
          Pheromone_count=Max_Pheromone;
          Count_distance=0;
          Min_distance=-1;
        }
	public void Draw(Graphics g) {
          //把蚂蚁在屏幕上画出来，先擦除上次画的点，然后再画蚂蚁现在的点。
		g.setColor(back_color);
		g.fillOval((int) lastPt.x,(int)lastPt.y,1,1);
		g.setColor(color);
		g.fillOval((int) nowPt.x, (int) nowPt.y,1,1);
	}
	public void Process(){
        //这个函数是蚂蚁进行决策的主程序，首先判断蚂蚁是否已经找到了目标点
        //（目标点在没找到食物的时候是食物点，找到以后是自己的窝）
        //然后计算蚂蚁的主方向，也就是让蚂蚁的爬动有一个惯性，当没有信息素作指导的时候蚂蚁按照主方向运动
        //开始搜索自己周围的空间信息，包括有多少信息素，是否有障碍物。最后根据信息素的大小决定移动到那个点
        //根据决策的目标进行真实的移动，其中包括了避障的行为，洒下信息素。



        if(Judged==false){
          //如果已经判断完结束与否了就不进行再一次的判断了，也就是说目前蚂蚁已经到了目标点，
          //如果再判断，它就会在目标点原地不动了，因此这是候不判断，让蚂蚁走起来
          if(JudgeEnd()){
              //判断，如果找到了目标点那么就退出该程序
              Judged=true;
              return;
          }
        }
        Judged=false;
        //如果没找到，就选择一个方向，这个方向是主方向加上一个随机扰动得到的，有SelectDirect函数完成
        double direct=SelectDirect();

        //下面是如果根据计算的移动方向得到蚂蚁的下一点，即deltx,delty
        int deltx=0,delty=0;
        //direct是方向角，根据方向计算位移
        deltx=(int)(VR*Math.cos(direct));
        delty=(int)(VR*Math.sin(direct));

        //kind表示当前蚂蚁是在找食物还是在找窝，如果是找窝就是1，找食物就是0。
        int kind=FoundTimes%2;

        //计算当前点的信息素，注意，如果获得的信息素总跟kind变量相反，
        //也就是说，如果当前蚂蚁找食物呢，那么它所关心的信息素就是找我的蚂蚁留下的，反之亦然。
        int here=local_colony.Pheromone_grid[1-kind][nowPt.x][nowPt.y];

        //记录搜索的环境中找到的最大的信息素
        int maxphe=here;

        //记住根据主方向角得到的位移，如果信息素并不能告诉蚂蚁应该往那里走，那么就要根据主方向角决定了
          int deltx1,delty1;
          deltx1=deltx;delty1=delty;

        //开始搜索环境，搜索的空间是以当前点为中心，VR为半径的四方形内，即VR/2*VR/2的正方形
          for(int x=-VR;x<=VR;x++){
             for(int y=-VR;y<=VR;y++){
                //xx,yy表示搜索到哪一个点了，+width然后再%width是为了让坐标循环起来，
                //在这个程序中，坐标是循环的，也就是在一个球面上
                int xx=(nowPt.x+x+width)%width;
                int yy=(nowPt.y+y+height)%height;

                //循环的时候要除去当前点。
                if(x!=0||y!=0){
                  //的到要搜寻的点的信息素
                  int phe=local_colony.Pheromone_grid[1-kind][xx][yy];

                  //如果搜索点的信息素比已经找到过的信息素多
                  if(maxphe<phe){

                      //如果当前点的信息素是0，没说的，赶紧上正轨，否则，就要根据随机数
                      //以mistake来决定蚂蚁犯错误的概率，即如果犯错误，它就不按信息素最大的方向走
                      double ra=Math.random();
                      if(here==0||ra>mistake){
                          boolean found=false;
                          //查一下内存最近走过的memory的点数，从而避免当地转圈
                          int size=HistoryPoint.size();
                          int minsize=memory;
                          if(size<memory)minsize=size;
                          for(int i=size-1;i>=size-minsize;i--){
                             Point pt=(Point)(HistoryPoint.elementAt(i));
                             if(pt.x==xx&&pt.y==yy){
                                found=true;
                                break;
                             }
                          }
                          if(!found){
                            //如果没有原地转圈，那么记录信息素。
                            maxphe=local_colony.Pheromone_grid[1-kind][xx][yy];
                            deltx=x;
                            delty=y;
                          }
                      }//end here==0||ra>0.001
                    }//end maxphe<here
                }//end if x!=0
            }//end for y
        }//end for x
        Point pt;

        //根据获得的信息的来的位移deltx,delty，来具体的进行移位
        pt=Evade_obs(deltx,delty);

        //如果卡住了，就根据主方向来确定位移，如果主方向也卡住了，那蚂蚁就会随机变换自己的主方向！
        if(pt.x==nowPt.x&&pt.y==nowPt.y){
          pt=Evade_obs(deltx1,delty1);
        }

        //播撒信息素
        Scatter();

        //记录走过的距离
        Count_distance+=Distance(lastPt,nowPt);

        //改变当前点位置
        lastPt=new Point(nowPt.x,nowPt.y);

        //根据memory的大小记录走过的点，并忘掉memory以前的点
        HistoryPoint.insertElementAt(lastPt,HistoryPoint.size());
        if(HistoryPoint.size()>memory){
          HistoryPoint.removeElementAt(0);
        }
        nowPt=new Point(pt.x,pt.y);
     }


        private void Scatter(){
        //释放信息素函数，每只蚂蚁有一个信息素的最大含量max_Pheromone，
        //并且，每次蚂蚁都释放Phe单位信息素，并且从总量Phe_count中减去Phe，直到用完所有的信息素。
            if(Pheromone_count<=0)return;
            //决定释放信息素的种类
            int kind=FoundTimes%2;

            //获得当前点环境已有信息素的值
            int Phec=local_colony.Pheromone_grid[kind][lastPt.x][lastPt.y];
            boolean ofound=false;
            if(Phec!=0){
                //如果当前点已经有信息素了
                for(int i=0;i<local_colony.phe.size();i++){
                    //在信息素向量中查找该点的信息
                    Pheromone ph=(Pheromone)(local_colony.phe.elementAt(i));
                    if(lastPt.x==ph.x&&lastPt.y==ph.y&&ph.kind==kind){
                        //找到了，则看看蚂蚁所在的位置是否是刚刚走过的，如果不是才撒信息素
                        int size=HistoryPoint.size();

                        //如果在表中找到信息素，则用ofound记录。
                        ofound=true;
                        boolean found=false;
                        if(size>4){
                           for(int j=size-4;j<size-1;j++){
                              Point pt=(Point)(HistoryPoint.elementAt(j));
                              if(pt.x==lastPt.x&&pt.y==lastPt.y){
                                //如果当前点重复了以前走过的路，就不释放
                                found=true;
                                break;
                              }
                            }
                        }
                        if(!found){
                        //如果当前点不重复，则开始撒
                             ph.Add(Phe);
                             local_colony.Pheromone_grid[kind][lastPt.x][lastPt.y]+=Phe;

                             //让还剩下的信息素总量减少
                             Pheromone_count-=Phe;
                        }
                        break;
                    }
                }
              }
          if(Phec==0||!ofound){
            //如果当前环境没有信息素，或者当前环境的信息素来自窝或者食物，则新建一个信息素元素放到列表中
                Pheromone ph=new Pheromone(lastPt.x,lastPt.y,local_colony.phe.size(),local_colony.Delimiter,id,local_colony,Phec,kind);
                ph.Add(Phe);
                local_colony.Pheromone_grid[kind][lastPt.x][lastPt.y]+=Phe;
                local_colony.phe.addElement(ph);
                //让还剩下的信息素总量减少
                 Pheromone_count-=Phe;
           }