shortcut.java

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

        if(n>0)
        {
            int firstNum = 0;
            int startPointInd, endPointInd;
            for (int i = 0; i < n; i++) {
                startPointInd = line[i].startIndex;
                endPointInd = line[i].endIndex;
                if(startPointInd==this.endPointIndex || endPointInd==this.endPointIndex)
                {
                    pointArray.hasEndPoint=true;
                    pointArray.AllNum=1;
                    return pointArray;
                }
                if (tabooTable[startPointInd]) {
                    pointArray.FirstCollection[firstNum] = startPointInd;
                    firstNum++;
                }
                if (tabooTable[endPointInd]) {
                    pointArray.FirstCollection[firstNum] = endPointInd;
                    firstNum++;
                }
            }
            pointArray.AllNum = firstNum;
            pointArray.FirstNum=firstNum;
        }
        else  //n<=0   没有相邻点
        {
            pointArray.AllNum = 0;
        }
        return pointArray;
    }
    /**
     *  得到某一个点相邻接的的NODE节点在初始点集中的的索引号
     * @param line  线集
     * @return  某一个点相邻接的的NODE节点在初始点集中的的索引号，用数组列表保存
     */
    private ArrayList getAdjNode(LineBean line[])
    {
        int n=line.length;
        ArrayList pointArray=new ArrayList();
        int startPointInd,endPointInd;
        for(int i=0;i<n;i++)
        {
            startPointInd=line[i].startIndex;
            endPointInd=line[i].endIndex;
            if(tabooTable[startPointInd])
            {
                pointArray.add(new Integer(startPointInd));
            }
            if(tabooTable[endPointInd])
            {
                pointArray.add(new Integer(endPointInd));
            }
        }
        return pointArray;
    }
    /**
     * 随机产生一个[a,b]之间的整数
     * @param a  左范围边界
     * @param b  右范围边界
     * @return   [a,b]之间的一个整数
     */
    private int random(int a, int b)
    //随机产生一个[a,b]之间的整数
    {
        int ran;
        double dran = Math.random(); //随即产生一个（0－1）之间的小数
        dran = a + dran * (b - a);
        ran = (int) dran;
        if ((dran - ran) > 0.5) {
            ran = ran + 1;
        }
        return ran;
    }

    /**
     * 计算一个染色体（路径）所有基因点的权重值
     * @param indiv  染色体个体（一条路径）
     */
    private void calWeight(individual indiv)
    {
        int cNum = indiv.geneNum;
        int chrom[] = new int[cNum];
        endowArray(cNum, chrom, indiv.chrom);
        int pInd1, pInd2;
        double pweight = 0;
        cNum = cNum - 1;
        indiv.geneWeight[0] = 0;
        for (int i = 0; i < cNum; i++) {
            pInd1 = indiv.chrom[i];
            pInd2 = indiv.chrom[i + 1];
            pweight = pweight + getIndWeight(pInd1, pInd2);
            indiv.geneWeight[i + 1] = pweight;
        }
    }

    /**
     * 得到起点到终点的权重值
     * @param startPointInd  起点的索引
     * @param endPointInd  终点的索引
     * @return  权重值
     */
    private double getIndWeight(int startPointInd, int endPointInd) {
        double weight1 = 0.0;
        int n = this.originLine.length;
        for (int i = 0; i < n; i++) {
            if (adjacencyTable[startPointInd][i] == true &&
                adjacencyTable[endPointInd][i] == true) {
                weight1 = this.originLine[i].weight;
                break;
            }
        }
        return weight1;
    }

    /**
     * 计算所有个体（路径）的权值，保存在其变量“value”中
     * @param indiv 所有个体（路径）
     */
    private void calAllWeight(individual indiv[])
    {
        int n = indiv.length;
        for (int i = 0; i < n; i++) {
            calWeight(indiv[i]);
        }
    }

    /**
     * 搜索某个点ID是否在点集中
     * @param searchValue  待搜索的点
     * @param arrayNum  数组个数
     * @param array   点集数组
     * @return  该点在点集中索引，如果不在点集中，则返回“-1”
     */
    private int indexOfValue(int searchValue, int arrayNum, int array[])
    {
        int index = -1;
        int Num = arrayNum - 1;
        if (Num > 1) {
            for (int i = 1; i < Num; i++) {
                if (array[i] == searchValue) {
                    index = i;
                    break;
                }
            }
        }
        return index;
    }

    /**
     * 个体（路径）中是否存在两个以上相同的基因（经过点）
     * @param indiv 个体
     * @return  如果存在两个以上相同的基因（经过点），则返回“true”；否则，返回"false"
     */
    private boolean repeatable(individual indiv) {
        boolean repeat = false;
        int arrayNum = indiv.geneNum;
        int end=arrayNum-1;
        for (int i = 0; i < end; i++) {
            for (int j = i + 1; j < arrayNum; j++) {
                if (indiv.chrom[i] == indiv.chrom[j]) {
                    repeat = true;
                    break;
                }
            }
        }
        return repeat;
    }

    /**
     * 数组的拷贝
     * @param arrayNum 数组个数
     * @param array  目的数组变量
     * @param value  源数组变量
     */
    private void endowArray(int arrayNum, int array[], int value[]) {
        for (int i = 0; i < arrayNum; i++) {
            array[i] = value[i];
        }
    }

    /**
     * 数组的拷贝
     * @param arrayNum  数组个数
     * @param array   目的数组变量
     * @param value  源数组变量
     */
    private void endowArray(int arrayNum, double array[], double value[]) {
        for (int i = 0; i < arrayNum; i++) {
            array[i] = value[i];
        }
    }

    /**
     * 对个体按照权重大小，进行排序
     * @param indiv  个体变量
     */
    private void sort(individual indiv[])
    //
    {
        int n = indiv.length;
        for(int i=0;i<POP_SIZE;i++)
        {
            sortIndex[i]=i;
        }
        int end=n-1;
        for (int i = 0; i < end; i++) {
            int end1, end2;
            end1 = indiv[i].geneNum - 1;
            for (int j = i + 1; j < n; j++) {
                end2 = indiv[j].geneNum - 1;
                if (indiv[j].geneWeight[end2] <indiv[i].geneWeight[end1] ) { //排序，按路径长度由小到大排列个体
                    int temp=sortIndex[i];
                    sortIndex[i]=sortIndex[j];
                    sortIndex[j]=temp;
                }
            }
        }
    }

    /**
     * 得到两个个体的公共基因信息（路径中的相同经过点）
     * @param indiv1 个体
     * @param indiv2 个体
     * @return  两个个体的公共基因信息（路径中的相同经过点）
     */
    private CommonPointArray getCommonPointInd(individual indiv1, individual indiv2)
    //判断两组染色体是否存在公共点，并且保证在该公共点处，进行交叉操作不会出现重复点，并返回公共点在初始点的索引号
    {
        CommonPointArray commonPointArray = new CommonPointArray();
        int num, numIndiv1, numIndiv2;
        numIndiv1 = indiv1.geneNum;
        numIndiv2 = indiv2.geneNum;
        int chrom1[] = new int[numIndiv1];
        int chrom2[] = new int[numIndiv2];
        endowArray(numIndiv1, chrom1, indiv1.chrom);
        endowArray(numIndiv2, chrom2, indiv2.chrom);
        int maxnum = Math.max(numIndiv1, numIndiv2);
        int commonPointIndex1[] = new int[maxnum];
        int commonPointIndex2[] = new int[maxnum];

        int commonPointNum = 0;
        int tag = 0;

        if (numIndiv1 < numIndiv2) {
            num = numIndiv2;
            tag = 1;
        } else {
            num = numIndiv1;
        }
        num = num - 1;
        if (num > 1) {
            for (int i = 1; i < num; i++) { //只比较除去首尾点之后的点，因此此处从1开始比较，界限数也须减去1
                if (tag == 0) {
                    int index = indexOfValue(chrom1[i], numIndiv2, chrom2);
                    if (index !=-1)
                    {
                        commonPointIndex1[commonPointNum] = i;
                        commonPointIndex2[commonPointNum] = index;
                        commonPointNum++;
                    }
                } else {
                    int index = indexOfValue(chrom2[i], numIndiv1, chrom1);
                    if (index !=-1)
                    {
                        commonPointIndex1[commonPointNum] = index;
                        commonPointIndex2[commonPointNum] = i;
                        commonPointNum++;
                    }
                }
            } //获取公共点结束
        }
        commonPointArray.ArrayNum = commonPointNum;
        //检验公共点是否能够保证在该点做交叉操作后，不存在重复点，并且保存这些点。
        if (commonPointNum > 1) {
            num = commonPointNum - 1;