shortcut.java

JAVA+MO(for JAVA)开发的基于遗传算法的最短路径源代码

package BestRoadGA;

import java.util.ArrayList;

/**
 * Created by IntelliJ IDEA.
 * User: 乔连军
 * Date: 2005-7-4
 * Time: 13:45:56
 * To change this template use File | Settings | File Templates.
 */
public class shortCut {

    //定义一个个体类，用于保存其相关信息
    private class individual
    //内部类，个体（路径）
    {
        int chrom[] = new int[pNum]; //保存染色体
        int geneNum = 0; //保存该染色体中基因的个数
        double geneWeight[] = new double[pNum]; //保存路径的权重值
    }
    private class HashArray {
        int value[] = new int[pNum]; //保存值
        int valueNum; //保存值的个数
    }
    private class AdjArray
    {
        int FirstCollection[] = new int[15]; //保存值
        int SecondCollection[] = new int[15]; //保存值
        int ThirdCollection[] = new int[15]; //保存值
        int FirstNum; //第一个方向中，集合的个数
        int SecondNum; //第二个方向中，集合的个数
        int ThirdNum; //第三个方向中，集合的个数
        int AllNum; //点的总个数
        boolean hasEndPoint;//所有邻接点中是否有终点,默认为“false”。即：邻接点中，没有终点
    }
    private class IsAdj {
        double weight; //保存值两个点之间的权值
        boolean isAdj; //是否相邻接
    }
    private class SubArray {
        public SubArray(int arrayNum) {
            this.valueNum = arrayNum;
        }
        int valueNum; //保存值的个数
        int value[] = new int[valueNum]; //保存值
    }
    private class CommonPointArray {
        int commonPointIndex1[] = new int[pNum]; //保存公共点在第一个染色体中的索引
        int commonPointIndex2[] = new int[pNum]; //保存公共点在第二个染色体中的索引
        int ArrayNum; //保存数组的个数
    }

    private int originPointID[]; //初始的点ID集
//    private ArrayList originPointID_array=new ArrayList();
    private LineBean originLine[]; //初始的线
    private boolean outerTabooTable[]; //保存通过外部设置的禁忌表
    private boolean tabooTable[]; //禁忌表，避免一个点被多次选中。值为“FALSE”表示该点不可被选中，
    // 为“TRUE”，该点可被选中。
    private com.esri.mo2.cs.geom.Point pointCoord[];
    private boolean adjacencyTable[][]; //存储点与线的邻接表关系，如果线中包含点，则值为1；不包含，为0。
    //数组第一个下标表示点的位置，第二个下标表示线的位置。
    private int pNum = 0; //存储网络图中点集的个数
    private int lNum = 0; //存储网络图中线集的个数
//    private int pointID[];      //存储初始的点集
//    private int pidIndex[];     //建立重排后的点集和原始点集的索引关系

    private int startPointID; //保存所求的最优路径中起点的ID
    private int startPointIndex; //保存所求的最优路径中起点在点集中的索引
    private int endPointID; //保存所求的最优路径中终点的ID
    private int endPointIndex; //保存所求的最优路径中终点在点集中的索引
    private int directionTag;

    private final double Pc = 1; //交叉概率
    private final double Pm = 0.4; //一次变异概率
    private final double Pr = 1; //二次矫正变异概率
    private int POP_SIZE=100; //每代的人口数
    private int Max_Generation; //最大的代
    private int sortIndex[];
    private int generation; //第几代
    private individual population[];

    private int bestroadNum = 0;

    public void setLine(LineBean[] Line)
    //设置初始的线集
    {
        lNum = Line.length;
        this.originLine = new LineBean[lNum];
        for (int i = 0; i < lNum; i++) {
            this.originLine[i] = new LineBean();
        }
        this.originLine = Line;
    }

    public void addObstructPointByIndex(int pointindex)
    //根据点在点集中的下标,增加一个障碍点
    {
        outerTabooTable[pointindex] = false;
    }

    public void addObstructPointByID(int pointid)
    //根据点的ID,增加一个障碍点
    {
        int index = indexOfValue(pointid, pNum, originPointID);
        outerTabooTable[index] = false;
    }

    public void removeObstructPointByIndex(int pointindex)
    //根据点在点集中的下标,去除一个障碍点，改为可选
    {
        outerTabooTable[pointindex] = true;
    }

    public void removeObstructPointByID(int pointid)
    //根据点的ID,去除一个障碍点，改为可选
    {
        int index = indexOfValue(pointid, pNum, originPointID);
        outerTabooTable[index] = true;
    }

    public void setStartAndEndPointID(int startPointid, int endPointid)
    //设置起点和终点
    {
        this.startPointID = startPointid;
        this.endPointID = endPointid;
        startPointIndex = indexOfValue(startPointID, pNum, originPointID);
        endPointIndex = indexOfValue(endPointID, pNum, originPointID);
    }

    /**
     *  初始化禁忌表，默认值为“true”，表示该点可选
     */
    private void initOuterTabooTable()
    {
        for (int i = 0; i < pNum; i++) {
            outerTabooTable[i] = true;
        }
    }
    /**
     * 初始化禁忌表
     */
    private void initTabooTable()
    //初始化禁忌表，默认值为“true”，表示该点可选
    {
        for (int i = 0; i < pNum; i++) {
            tabooTable[i] = outerTabooTable[i];
        }
    }

    /**
     * 设置禁忌表，提供给外部的接口
     * @param tabooTable 禁忌表数组
     */
    public void setTabooTable(boolean tabooTable[]) {
        this.outerTabooTable = tabooTable;
    }

    /**
     * 返回某个点相连接的点集在初始点中的索引号，用数组形式返回
     * @param pointIndex  点在点集中的索引
     * @return   与传入点相邻的所有点
     */
    private AdjArray getAdjacencyPointIndex(int pointIndex)
    {
        AdjArray adjactpIndex = new AdjArray();
        int adLineindex[] = new int[15];
        int adLineindexNum = 0;
        for (int i = 0; i < lNum; i++) {
            if (adjacencyTable[pointIndex][i] == true) {
                adLineindex[adLineindexNum] = i;
                adLineindexNum++;
            }
        }
        LineBean curLine[] = new LineBean[adLineindexNum];
        for (int i = 0; i < adLineindexNum; i++) {
            curLine[i] = originLine[adLineindex[i]];
        }
        adjactpIndex = getAdjNode(pointIndex,curLine);
        return adjactpIndex;
    }
    /**
     * 返回某个点相连接的点集在初始点中的索引号，用数组形式返回
     * @param pointIndex  点在点集中的索引
     * @return   与传入点相邻的所有点
     */
    private AdjArray getAdjacencyPointIndexInGaTwo(int pointIndex)
    {
        AdjArray adjactpIndex = new AdjArray();
        int adLineindex[] = new int[15];
        int adLineindexNum = 0;
        for (int i = 0; i < lNum; i++) {
            if (adjacencyTable[pointIndex][i] == true) {
                adLineindex[adLineindexNum] = i;
                adLineindexNum++;
            }
        }
        LineBean curLine[] = new LineBean[adLineindexNum];
        for (int i = 0; i < adLineindexNum; i++) {
            curLine[i] = originLine[adLineindex[i]];
        }
        //adjactpIndex = getAdjNode(pointIndex,curLine);
        adjactpIndex = getAdjNodeInGaTwo(pointIndex,curLine);
        return adjactpIndex;
    }

    /**
     *  得到某个点相连接的点集在初始点中的索引号
     * @param pointIndex  传入点的索引
     * @return   返回某个点相连接的点集在初始点中的索引号，用数组形式返回
     */
    private ArrayList getAdjacencyPointIndex1(int pointIndex)
    {
        ArrayList adjactpIndex=new ArrayList();
        ArrayList adLineindex=new ArrayList();
        boolean pe[]=new boolean[lNum];
        pe=(boolean[])adjacencyTable[pointIndex].clone();
        for(int i=0;i<lNum;i++)
        {
            if(pe[i]==true)
            {
                adLineindex.add(new Integer(i));
            }
        }
        int num=adLineindex.size();
        LineBean curLine[]=new LineBean[num];
        for(int i=0;i<num;i++)
        {
            int indexLine=Integer.parseInt(adLineindex.get(i).toString());
            curLine[i]=originLine[indexLine];
        }
        adjactpIndex=getAdjNode(curLine);
        return adjactpIndex;
    }

    /**
     * 判断point2相对point1所在的象限，并做相应的变量设置（directionTag为“1”，表示第一象限；“2”：第二象限；“3”：第三象限；“4”第四象限）
     * @param point1  当前路径所走到的点
     * @param point2   路径的终点
     */
    private void judgeDirection(com.esri.mo2.cs.geom.Point point1,com.esri.mo2.cs.geom.Point point2)
    {
        double x1=point1.x;
        double y1=point1.y;
        double x2=point2.x;
        double y2=point2.y;
        if(x1<=x2)
        {
            if(y1>=y2)  //第一象限为主集
            {
                directionTag = 1;
            }
            else //y1<y2  第二象限为主集
            {
                directionTag = 2;
            }
        }
        else //x1>x2
        {
            if(y1>=y2)  //第三象限为主集
            {
                directionTag = 3;
            }
            else //y1<y2  第四象限为主集
            {
                directionTag = 4;
            }
        }
    }

    /**
     * 设置初始的点集，赋予全局数组变量originPointID[]，同时把它转化为数组列表，方便查询
     * @param pointID  点集的ID数组
     */
    public void setPointID(int[] pointID)
    // 用全局变量array_originPointID保存为ArrayList的形式，方便程序的中间处理。