遗传算法 TSP问题 C++实现

admin1

void GenomeTSP::copulation(Individual &individual1, Individual &individual2){

    //获取变异区间
    pair<int,int> randomCopuSec=getRandomCopuSec();

    //保存第一个个体的交叉区间DNA片段
    DNA firstIndiDNASec;
    copyDNASeg(individual1._DNA,
                randomCopuSec.first,
                randomCopuSec.second,
                firstIndiDNASec);
    //保存第2个个体的交叉区间DNA片段
    DNA secIndiDNASec;
    copyDNASeg(individual2._DNA,
        randomCopuSec.first,
        randomCopuSec.second,
        secIndiDNASec);

    //去除交叉DNA片段的重复元素
    DNA uniqueFirstIndiDNASeg=removeDepuInDNA(firstIndiDNASec,secIndiDNASec);
    DNA uniqueSecIndiDNASeg=removeDepuInDNA(secIndiDNASec,firstIndiDNASec);

    //获取第二个DNA 映射到 第一个个体 的坐标
    DNA secDNAMapFirstIndividual=mapDNAToIndiPos(individual1,uniqueSecIndiDNASeg);
    //获取第一个DNA 映射到 第二个个体 的坐标
    DNA firstDNAMapSecIndividual=mapDNAToIndiPos(individual2,uniqueFirstIndiDNASeg);

    //用第二个交叉DNA替换第一个个体的交叉区间DNA
    replaceDNASeg(secIndiDNASec,
        0,
        secIndiDNASec.size()-1,
        individual1._DNA,
        randomCopuSec.first,
        randomCopuSec.second);
    //用第一个交叉DNA 替换 第二个个体的交叉区间DNA
    replaceDNASeg(firstIndiDNASec,
        0,
        firstIndiDNASec.size()-1,
        individual2._DNA,
        randomCopuSec.first,
        randomCopuSec.second);

    /*消除第一个个体因为交叉产生的DNA片段冲突,
     *因为第一个个体获得了第二个个体的部分DNA，所以可能与原来第一个个体的DNA冲突
     *所以需要保存新获得的DNA在第一个个体相同元素的对应位置，
     *再用第一个个体因为交叉而损失的DNA补充相应的位置
     */
    replaceDNASegByVec(uniqueFirstIndiDNASeg,individual1._DNA,secDNAMapFirstIndividual);
    replaceDNASegByVec(uniqueSecIndiDNASeg,individual2._DNA,firstDNAMapSecIndividual);
}


void GenomeTSP::copyDNASeg(DNA srcDNAVec, int minPos, int maxPos, DNA &destDNAVec){
    for(int i=minPos;i<=maxPos;++i){
        destDNAVec.push_back(srcDNAVec.at(i));
    }
}

//计算映射地址
vector<int> GenomeTSP::mapDNAToIndiPos(Individual &individual, DNA &DNASegVec){
    //返回vector
    DNA mapPos;
    //遍历DNASegVec，寻找每一个元素在individual。dna中对应的位置
    for(size_t i=0;i<DNASegVec.size();++i){
        for(size_t j=0;j<individual._DNA.size();++j){
            if(DNASegVec.at(i)==individual._DNA.at(j)){//找到相同元素，退出内层循环,保存位置
                mapPos.push_back(j);
                break;
            }
        }//iner-loop
    }//outer-loop
    return mapPos;
}

//生成交叉区间
pair<int,int> GenomeTSP::getRandomCopuSec(){
    //随机生成交叉位置，（交叉从0到copuPos之间的DNA片段将会被交换）
    int minPos=rand()%MAX_DNA_SIZE;
    int maxPos=rand()%MAX_DNA_SIZE;
    //保证不重复
    while (maxPos<=minPos || (maxPos-minPos)>MAX_COPULATION_SIZE){
        maxPos=rand()%MAX_DNA_SIZE;
    }
    return make_pair(minPos,maxPos);
}

//计算真正损失的DNA片段
DNA GenomeTSP::removeDepuInDNA(DNA firstDNA, DNA secDNA){
    DNA result;
    for (size_t i=0;i<firstDNA.size();++i){
        if( find(secDNA.begin(),secDNA.end(),firstDNA.at(i))==secDNA.end() ){//如果是unique元素
            result.push_back(firstDNA.at(i));
        }
    }
    return result;
}