shortcut.java

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

            int index1, index2;
            int tempNum = 0;
            int ttag;
            for (int i = 0; i < commonPointNum; i++) {
                index1 = commonPointIndex1[i];
                index2 = commonPointIndex2[i];

                ttag = 0;
                for (int j = 0; j < commonPointNum; j++) {
                    if ((index1 < commonPointIndex1[j] && index2 < commonPointIndex2[j])
                        || (index1 > commonPointIndex1[j] && index2 > commonPointIndex2[j])) {
                        ttag++;
                    }
                }
                if (ttag == num) {
                    commonPointArray.commonPointIndex1[tempNum] = commonPointIndex1[i];
                    commonPointArray.commonPointIndex2[tempNum] = commonPointIndex2[i];
                    tempNum++;
                }
            }
            commonPointArray.ArrayNum = tempNum;
        }
        return commonPointArray;
    }
    /**
     * 产生群体
     */
    private void Initial()
    //对点集进行编码，采取自然数编码的方式，编码的值就是该点在原始点集中的位置。
    // 我们按照点集的顺序，每取一个点后，把该点从点集中清理出去，这样我们避免了重复选取同一个点；
    {
        AdjArray adjPoint = new AdjArray();
        for (int i = 0; i < POP_SIZE; i++) { //
            initTabooTable();
            population[i] = new individual();
            int populationChromNum = 0;
            int pIndex = startPointIndex;
            population[i].chrom[0] = startPointIndex; //加入起点索引号
            populationChromNum = 1;
            tabooTable[startPointIndex] = false;
            while (pIndex != endPointIndex) {
                adjPoint = getAdjacencyPointIndex(pIndex);
                //adjPoint = getAdjacencyPointIndexInGaTwo(pIndex);
                if(adjPoint.hasEndPoint)
                {
                    pIndex = this.endPointIndex;
                    population[i].chrom[populationChromNum] = pIndex;
                    populationChromNum++;
                    tabooTable[endPointIndex] = false;
                    break;
                }
                else
                {
                    int n = adjPoint.AllNum;
                    while (n == 0) { //如果没有可选的邻接结点，则删除该点，退回到上个结点
                        populationChromNum--;
                        pIndex = population[i].chrom[populationChromNum - 1];
                        tabooTable[pIndex] = false;
                        adjPoint = getAdjacencyPointIndex(pIndex);
                        //adjPoint = getAdjacencyPointIndexInGaTwo(pIndex);
                        n = adjPoint.AllNum;
                    }
                    if(adjPoint.hasEndPoint)
                    {
                        pIndex = this.endPointIndex;
                        population[i].chrom[populationChromNum] = pIndex;
                        populationChromNum++;
                        tabooTable[endPointIndex] = false;
                        break;
                    }
                    else
                    {
                        n=adjPoint.FirstNum;
                        if(n>0)
                        {
                            int ran = random(0, n - 1);
                            pIndex = adjPoint.FirstCollection[ran];
                            population[i].chrom[populationChromNum] = pIndex;
                            populationChromNum++;
                            tabooTable[pIndex] = false;
                        }
                        else //n=0
                        {
                            n=adjPoint.SecondNum;
                            if(n>0)
                            {
                                int ran = random(0, n - 1);
                                pIndex = adjPoint.SecondCollection[ran];
                                population[i].chrom[populationChromNum] = pIndex;
                                populationChromNum++;
                                tabooTable[pIndex] = false;
                            }
                            else //n=0
                            {
                                n=adjPoint.ThirdNum;  //此处n肯定大于“0”
                                int ran = random(0, n - 1);
                                pIndex = adjPoint.ThirdCollection[ran];
                                population[i].chrom[populationChromNum] = pIndex;
                                populationChromNum++;
                                tabooTable[pIndex] = false;
                            }
                        }
                    }
                }
            }
            population[i].geneNum = populationChromNum;
            calWeight(population[i]);
            //完成一个染色体的初始化*/
           //一个染色体赋值完毕后，重新初始化禁忌表，
           // 让所有的点都可选，开始另一个染色体的赋值。
        }
    }

    /**
     * 二次变异（使最短路径的结果更精确）
     */
    private void Correction()
    {
        int mutaLength,point1,point2;//存储变异点。length为变异长度,point1为起点点位,point2为终点点位
        double p;
        int limit=POP_SIZE;

        for(int i=0;i<limit;i++)
        {
            p=Math.random();
            if(p<Pr)
            {
                int popindex=sortIndex[i];
                int nchrom=population[popindex].geneNum;
                if(nchrom>8)
                {
                    point1 = random(1, nchrom/2-1); //随机产生变异点
                    mutaLength = random(0, nchrom/2-1); //随机产生变异长度
                    point2=point1+mutaLength;

                    int temp[]=new int[pNum];
                    double tempWeight[]=new double[pNum];
                    int tempNum;
                    double popWeight=population[popindex].geneWeight[point2+1]-population[popindex].geneWeight[point1-1];
                    if(mutaLength<=8)
                    {
                        boolean tag=false;
                        int tempTag=0;
                        while(tempTag<3)
                        {
                            initTabooTable();        //重新初始化禁忌表，让所有点都可选
                            for (int j = 0; j < point1; j++) { //初始化变异点point1之前(包括变异点)的所有点为禁忌状态：“false”
                                tabooTable[population[popindex].chrom[j]] = false; //初始化变异点之前(不包括变异点)的所有点为禁忌状态：“false”
                            }
                            if((point2+2)<nchrom)
                            {
                                for (int j = point2 + 2; j < nchrom; j++) { //初始化变异点point2之后的所有点为禁忌状态：“false”
                                    //System.out.print(nchrom+"---------"+population[i].chrom.size()+"-----"+j+"\n");
                                    tabooTable[population[popindex].chrom[j]] = false; //初始化变异点之前(包括变异点)的所有点为禁忌状态：“false”
                                }
                            }
                            int pIndex;
                            temp[0] = population[popindex].chrom[point1 - 1];
                            pIndex = temp[0];
                            tempWeight[0] = 0.0;
                            tempNum=1;
                            int endIndex = population[popindex].chrom[point2+1];
                            AdjArray adjPoint = new AdjArray();

                            while (pIndex != endIndex) {
                                adjPoint = getAdjacencyPointIndexInGaTwo(pIndex);
                                if(adjPoint.hasEndPoint)
                                {
                                    pIndex = this.endPointIndex;
                                    temp[tempNum] = pIndex;
                                    tabooTable[endPointIndex] = false;
                                }
                                else
                                {
                                    int n = adjPoint.AllNum;
                                    while (n == 0) { //如果没有可选的邻接结点，则删除该点，回退到上个结点
                                        tabooTable[pIndex] = false;
                                        tempNum--;
                                        pIndex = temp[tempNum - 1];
                                        adjPoint = getAdjacencyPointIndexInGaTwo(pIndex);
                                        n = adjPoint.AllNum;
                                    }
                                    if(adjPoint.hasEndPoint)
                                    {
                                        pIndex = this.endPointIndex;
                                        temp[tempNum] = pIndex;
                                        tabooTable[endPointIndex] = false;
                                    }
                                    else
                                    {
                                        n=adjPoint.FirstNum;
                                        if(n>0)
                                        {
                                            int ran = random(0, n - 1);
                                            pIndex = adjPoint.FirstCollection[ran];
                                            temp[tempNum] = pIndex;
                                            tabooTable[pIndex] = false;
                                        }
                                        else //n=0
                                        {
                                            n=adjPoint.SecondNum;
                                            if(n>0)
                                            {
                                                int ran = random(0, n - 1);
                                                pIndex = adjPoint.SecondCollection[ran];
                                                temp[tempNum] = pIndex;
                                                tabooTable[pIndex] = false;
                                            }
                                            else //n=0
                                            {
                                                n=adjPoint.ThirdNum;
                                                int ran = random(0, n - 1);
                                                pIndex = adjPoint.ThirdCollection[ran];
                                                temp[tempNum] = pIndex;
                                                tabooTable[pIndex] = false;
                                            }
                                        }
                                    }
                                }
                                tempWeight[tempNum] = tempWeight[tempNum-1] +getIndWeight(temp[tempNum - 1], pIndex);
                                tempNum++;
                                if (tempWeight[tempNum-1]+0.0001 >= popWeight) {
                                    tag=true;
                                    break;
                                }
                                else
                                {
                                    tag=false;
                                }
                            } //完成一个染色体的变异操作
                            tempTag++;
                            if (tag == false) {
                                int end=nchrom-1-point2;
                                population[popindex].geneNum=point1+(tempNum-2)+end;
                                int curChrom[]=new int[end];
                                double curWeight[]=new double[end];
                                int start=point2+1;
                                for (int j = 0; j < end; j++)
                                {
                                    curChrom[j]=population[popindex].chrom[start+j];
                                    curWeight[j]=population[popindex].geneWeight[start+j]-population[popindex].geneWeight[start];
                                }
                                start=point1-1;
                                for (int j = 1; j < tempNum; j++) {
                                    population[popindex].chrom[start+j]=temp[j];
                                    population[popindex].geneWeight[start+j]=population[popindex].geneWeight[start]+tempWeight[j];
                                }
                                start=point1+tempNum-2;
                                end=population[popindex].geneNum;
                                for (int j = point1+tempNum-1,k=1; j < end; j++,k++) {
                                    population[popindex].chrom[j]=curChrom[k];
                                    population[popindex].geneWeight[j]=population[popindex].geneWeight[start]+curWeight[k];
                                }
                                tempTag=3;
                             }
                        }
                    }
                    else//mutaLength>8
                    {
                        boolean tag=false;

                        initTabooTable();        //重新初始化禁忌表，让所有点都可选
                        for (int j = 0; j < point1; j++) { //初始化变异点point1之前(包括变异点)的所有点为禁忌状态：“false”
                            tabooTable[population[popindex].chrom[j]] = false; //初始化变异点之前(不包括变异点)的所有点为禁忌状态：“false”
                        }
                        if((point2+2)<nchrom)
                        {
                            for (int j = point2 + 2; j < nchrom; j++) { //初始化变异点point2之后的所有点为禁忌状态：“false”
                            //System.out.print(nchrom+"---------"+population[i].chrom.size()+"-----"+j+"\n");
                            tabooTable[population[popindex].chrom[j]] = false; //初始化变异点之前(包括变异点)的所有点为禁忌状态：“false”
                            }
                        }
                        int pIndex;
                        temp[0] = population[popindex].chrom[point1 - 1];
                        pIndex = temp[0];
                        tempWeight[0] = 0.0;