tspga.cpp

旅行商问题求解 旅行商问题求解 旅行商问题求解 旅行商问题求解

}

string randomPath() {
    string cityPool;
    int randPool[20];

    cityPool.resize ( cityCount );

    for ( int i = 0;i < cityCount;i++ ) {
        cityPool[i] = cities[i];
        randPool[i] = rand();
    }

    for ( int i = 0;i < cityCount;i++ ) {
        for ( int j = i;j < cityCount;j++ ) {
            if ( randPool[i] > randPool[j] ) {
                int randTemp = randPool[j];
                randPool[j] = randPool[i];
                randPool[i] = randTemp;

                char cityTemp = cityPool[j];
                cityPool[j] = cityPool[i];
                cityPool[i] = cityTemp;
            }
        }
    }

    return cityPool;
}

void printCurGroup() {
    for ( int i = 0;i < groupSize;i++ ) {
        cout << groupMember[i] << endl;
    }
}

void calcGroupF() {
    for ( int i = 0; i < groupSize;i++ ) {
        groupF[i] = pow ( getTotalDistance ( groupMember[i] ), 2 ) ;
    }
}

void printCurGroupWithF() {
    for ( int i = 0;i < groupSize;i++ ) {
        cout << groupMember[i] << "\t" << groupF[i] << endl;
    }
}

void printBestMember() {
    double best = ( double ) INT_MAX;
    int id = -1;

    for ( int i = 0;i < groupSize;i++ ) {
        if ( groupF[i] < best ) {
            best = groupF[i];
            id = i;
        }
    }

    cout << "Current best result is " << groupF[id] << " of " << groupMember[id] << endl;
}

void getBestMember ( double& bestF, int& bestId ) {
    double best = ( double ) INT_MAX;
    int pos = -1;

    for ( int i = 0;i < groupSize;i++ ) {
        if ( groupF[i] < best ) {
            best = groupF[i];
            pos = i;
        }
    }

    bestF = best;

    bestId = pos;
}

void selectMember() {
    //计算适应度值和
    double sigmaF = 0;

    for ( int i = 0;i < groupSize;i++ )
        sigmaF += groupF[i];

    //计算期望次数,选择次数清零

    for ( int i = 0;i < groupSize;i++ ) {
        expectedSelectedTimes[i] = groupF[i] / sigmaF * groupSize;
        selectedTimes[i] = 0;
    }

    //计算选择次数
    //先选期望大于等于1次的
    int spaceRemain = groupSize;

    for ( int i = 0;i < groupSize;i++ ) {
        selectedTimes[i] = ( int ) ( expectedSelectedTimes[i] );
        spaceRemain -= ( int ) ( expectedSelectedTimes[i] );
    }

    //计算期望次数与选择次数差
    int idPool[groupSize];

    for ( int i = 0;i < groupSize;i++ ) {
        idPool[i] = i ;
        deltaSel[i] = expectedSelectedTimes[i] - selectedTimes[i];
    }

    //排序

    for ( int i = 0;i < groupSize;i++ ) {
        for ( int j = i;j < groupSize;j++ ) {
            if ( deltaSel[i] > deltaSel[j] ) {
                double deltaTemp = deltaSel[j];
                deltaSel[j] = deltaSel[i];
                deltaSel[i] = deltaTemp;

                int idTemp = idPool[j];
                idPool[j] = idPool[i];
                idPool[i] = idTemp;
            }
        }
    }

    //选满groupSize个染色体

    for ( int i = 0;i < spaceRemain;i++ ) {
        selectedTimes[idPool[i]]++;
    }
}

void printCurGroupWithSelTimes() {
    for ( int i = 0;i < groupSize;i++ ) {
        cout << groupMember[i] << "\t" << selectedTimes[i] << endl;
    }
}

void crossGen() {
    for ( int i = 0;i < groupSize*crossGenRate;i++ ) {
        //找到两个parent
        int parentA, parentB;

        while ( true ) {
            parentA = rand() % groupSize;
            parentB = rand() % groupSize;

            if ( parentA != parentB )
                break;
        }

        //备份两个parent
        string pathABackup = groupMember[parentA];

        string pathBBackup = groupMember[parentB];

        //用随机数k<m将parent分成3段
        int k = rand() % cityCount;

        int m = rand() % cityCount;

        if ( k > m ) {
            int kk = k;
            k = m;
            m = kk;
        }

        //parent间互换某一段
        int part = rand() % 3;

        switch ( part ) {

        case 0:

            for ( int bit = 0;bit < k;bit++ ) {
                char bitTemp = groupMember[parentA][bit];
                groupMember[parentA][bit] = groupMember[parentB][bit];
                groupMember[parentB][bit] = bitTemp;
            }

            break;

        case 1:

            for ( int bit = k;bit < m;bit++ ) {
                char bitTemp = groupMember[parentA][bit];
                groupMember[parentA][bit] = groupMember[parentB][bit];
                groupMember[parentB][bit] = bitTemp;
            }

            break;

        case 2:

            for ( int bit = m;bit < cityCount;bit++ ) {
                char bitTemp = groupMember[parentA][bit];
                groupMember[parentA][bit] = groupMember[parentB][bit];
                groupMember[parentB][bit] = bitTemp;
            }

            break;
        }

        //将交叉后的A,B重新转换成回路
        string nextA = "";

        string nextB = "";

        //删重复城市
        for ( int curPos = 0;curPos < cityCount;curPos++ ) {
            if ( nextA.find ( groupMember[parentA][curPos] ) == -1 ) {
                nextA = nextA + groupMember[parentA][curPos];
            }

            if ( nextB.find ( groupMember[parentB][curPos] ) == -1 ) {
                nextB = nextB + groupMember[parentB][curPos];
            }
        }

        //加缺少城市

        for ( int curPos = 0;curPos < cityCount;curPos++ ) {
            if ( nextA.find ( groupMember[parentB][curPos] ) == -1 ) {
                nextA = nextA + groupMember[parentB][curPos];
            }

            if ( nextB.find ( groupMember[parentA][curPos] ) == -1 ) {
                nextB = nextB + groupMember[parentA][curPos];
            }
        }

        //更新转换后的A,B
        groupMember[parentA] = nextA;

        groupMember[parentB] = nextB;

        //父代子代竞争
        deltaDistance = getTotalDistance ( groupMember[parentA] ) - getTotalDistance ( pathABackup );

        if ( ! ( deltaDistance < 0 ) ||
                (
                    deltaDistance > 0 &&
                    exp ( -deltaDistance ) >
                    ( double ) ( ( double ) ( rand() ) / ( double ) ( RAND_MAX )
                               ) )
           )
            groupMember[parentA] = pathABackup;

        deltaDistance = getTotalDistance ( groupMember[parentB] ) - getTotalDistance ( pathBBackup );

        if ( ! ( deltaDistance < 0 ) ||
                (
                    deltaDistance > 0 &&
                    exp ( -deltaDistance ) >
                    ( double ) ( ( double ) ( rand() ) / ( double ) ( RAND_MAX )
                               ) )
           )
            groupMember[parentB] = pathBBackup;
    }
}

void selfGen() {
    for ( int i = 0;i < groupSize*selfGenRate;i++ ) {
        //找到一个parent
        int parentA = rand() % groupSize;
        string pathABackup = groupMember[parentA];

        int k = rand() % cityCount;
        int m = rand() % cityCount;

        if ( k > m ) {
            int kk = k;
            k = m;
            m = kk;
        }

        //k<m

        //逆序交换k至m

        for ( int count = 0; count < ( m - k + 1 ) / 2;count++ ) {
            char bitTemp = groupMember[parentA][k+count];
            groupMember[parentA][k+count] = groupMember[parentA][m-count];
            groupMember[parentA][m-count] = bitTemp;
        }

        //父代子代竞争
        deltaDistance = getTotalDistance ( groupMember[parentA] ) - getTotalDistance ( pathABackup );

        if ( ! ( deltaDistance < 0 ) ||
                (
                    deltaDistance > 0 &&
                    exp ( -deltaDistance ) >
                    ( double ) ( ( double ) ( rand() ) / ( double ) ( RAND_MAX )
                               ) )
           )
            groupMember[parentA] = pathABackup;
    }
}

void clearUnselected() {
    string groupMemberCopy[groupSize];
    int pMemberCopy = 0;

    for ( int i = 0;i < groupSize;i++ ) {
        for ( int j = 0;j < selectedTimes[i];j++ ) {
            groupMemberCopy[pMemberCopy] = groupMember[i];
            pMemberCopy++;
        }
    }
}

void saveGenerationDetails() {
    string groupMemberCopy[groupSize];
    fout << "$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$" << endl;
    fout << "Generation " << generation << endl;
    fout << "-----------------------------------------------------------" << endl;
    saveCurGroupWithF();
    //输出当代最优解
    fout << "-----------------------------------------------------------" << endl;
    saveBestMember();
    fout << "$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$" << endl << endl;
}

void saveCurGroupWithF() {
    for ( int i = 0;i < groupSize;i++ ) {
        fout << groupMember[i] << "\t" << sqrt ( groupF[i] ) << endl;
    }
}

void saveBestMember() {
    double best = ( double ) INT_MAX;
    int id = -1;

    for ( int i = 0;i < groupSize;i++ ) {
        if ( groupF[i] < best ) {
            best = groupF[i];
            id = i;
        }
    }

    fout << "Current best result is " << sqrt ( groupF[id] ) << " of " << groupMember[id] << endl;
}