基于精英选择策略的遗传算法

admin1

/*由Parrot改进的遗传算法求解TSP
*
*选择操作使用转赌轮算法
*变异算子采用逆转变异算法
*交叉时先使用顺序编码，单点交叉，然后解码
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include<unordered_map>
#include<utility>
#include <time.h>
#include <assert.h>
using namespace std;

unsigned int cityNum=20; //城市数目
double** dist;  //两两城市之间距离
const unsigned int generation = 5000;         //迭代次数
const unsigned int populationSize = 50;  //染色体数目
unsigned int chromLen = cityNum;   //单条染色体序列长度，在这里为城市数目cityNum

const double mutationRate = 0.07;  //基因突变概率
const double crossoverRate = 0.95;         //两条染色体交叉概率
const int select_chromPair = 30; //选择染色体交叉对的次数
//等级选择+轮盘赌算法
//无条件保留最优的5条解，其余的分成5个等级，选择rank[5,10)的概率为2%
//选择rank[10,20)的概率为10%, 选择rank[20,30)的概率为18%
//选择rank[30,40)的概率为30%，选择rank[40,50)的概率为40%
//每个等级内部则根据其适应函数按轮盘赌算法选择

//轮盘赌算法，用于等级算法的第二次选择
int roulette_select(const double *fitness,int p,int r)
{
        int i;
        double* stage=new double[r-p+1];
        stage[0] = fitness[p];
        for (i=1;i<r-p+1;i++){
                stage[i]=stage[i-1] + fitness[p+i];
        }
        double d = (rand()*1.0/RAND_MAX) * stage[r-p];
        i=0;
        while(d>stage[i]) i++;
        delete[] stage;
        return p+i;
}

int rank_select(const double* fitness,int sz)
{
        int i;
        //第一次选择等级区间
        int rand_num = rand()%100;
        if(rand_num<2) return roulette_select(fitness,5,9);
        if(rand_num<12) return roulette_select(fitness,10,19);
        if(rand_num<30) return roulette_select(fitness,20,29);
        if(rand_num<60) return roulette_select(fitness,30,39);
        return roulette_select(fitness,40,49);
}

//生成[0,n-1]的随机序列,保存到randorder中
void rand_int_order(vector<int>& randorder,const int n)   
{   
        assert(n>1);  

        randorder.clear();
        randorder.resize(n);
        vector<int> recoder;
        for (int i=0;i<n;i++){
                recoder.push_back(i);       
        }
        for(int i=0;i<n;i++){
                int sel=rand()%recoder.size();
                randorder[i]=recoder[sel];
                recoder.erase(recoder.begin()+sel);
        }
        //assertion
        assert(randorder.size()==n);
}

//编码函数
void sequence_encode(vector<int>& chromosome)
{
        vector<int> standard;
        for (int i=0;i<chromosome.size();i++){
                standard.push_back(i);
        }
        vector<int>::iterator ite;
        for (int i=0;i<chromosome.size();i++){
                ite=find(standard.begin(),standard.end(),chromosome[i]);
                assert(ite!=standard.end());
                chromosome[i]=ite-standard.begin();
                standard.erase(ite);
        }

}
//解码函数
void sequence_decode(vector<int>& chromosome)
{
        vector<int>standard;
        for (int i=0;i<chromosome.size();i++){
                standard.push_back(i);
        }
        for (int i=0;i<chromosome.size();i++){       
                int t=chromosome[i];
                chromosome[i]=standard[t];
                standard.erase(standard.begin()+t);
        }

}

//计算可行路径的适应函数值
double caculate_fit(const vector<int> &path)
{
        double sum=0;
        for(int i=1;i<=chromLen;i++) sum+=dist[path[i-1]][path[i%chromLen]];
        return sum;
}

//初始化各城市之间的距离
void init(){
        fstream fin("input_data.txt",ios::in);
        dist=new double*[cityNum];
        for (int i=0;i<cityNum;i++)        dist[i]=new double[cityNum];
        int data;
        for (int i=0;i<cityNum;i++){               
                for (int j=i;j<cityNum;j++){
                        fin>>data;
                        if(i!=j) dist[i][j]=dist[j][i]=data;
                        else dist[i][j]=0;
                }
        }
        fin.close();
}

void run()
{       
        fstream fout("output.txt",ios::out);
        int curTime=int(time(0));

        srand((unsigned)time(NULL));

        // 染色体数组
        vector<vector<int> > population; //第0代

        //随机化染色体序列
        for (int i=0;i<populationSize;i++){
                vector<int> chromo;
                rand_int_order(chromo,chromLen); //随机产生一个可行解（用chromo表示）
                population.push_back(chromo);
        }

        double glob_best_len = INT_MAX;  //整个进化过程中得到的最优路径的长度
        vector<int> glob_best_path; //整个进化过程中得到的最优路径

        //开始进化
        for (int g=0;g<generation;g++){       
                double *fitness = new double[populationSize];        //适应函数（可行路径的长度）
                for(int i=0;i<populationSize;i++) fitness[i]=0;
                //计算当前每条染色体的适应度函数（路径的长度）
                for (int s=0;s<populationSize;s++) fitness[s]=caculate_fit(population[s]);
                       
                vector<vector<int> > parent;   //parent为population按适应函数插入排序后得到的染色体组
                for(int i=0;i<population.size();i++){
                        int j=0;  
                        while(j<parent.size() && fitness[i]>=fitness[j]) j++;  //插入位置
                        parent.insert(parent.begin()+j,population[i]);
                        double tmp = fitness[i];
                        for(int k=i;k>=j+1;k--) fitness[k]=fitness[k-1];    //同时更改fitness
                        fitness[j]=tmp;  
                }

                population.clear(); //清空population，用以保存下一轮染色体
                fout<<"**************************************************************************\n";
                fout<<"第 "<<g<<" 轮进化\n";
                for(int i=0;i<populationSize;i++){
                        fout<<"路径"<<i<<":"<<fitness[i]<<"(长度）\n";
                        for(int j=0;j<chromLen;j++) fout<<parent[i][j]<<"-->";
                        fout<<"\n\n";
                }
                fout<<"**************************************************************************\n";

                if(glob_best_len>fitness[0]){ glob_best_len=fitness[0]; glob_best_path = parent[0];}

                //选择25对交叉的染色体序号，去掉重复的
                unordered_map<int,int> tab;   //交叉对
                for(int i=0;i<select_chromPair;i++){
                        int rs1 = rank_select(fitness,populationSize-1),rs2=rs1;
                        while(rs2==rs1) rs2 = rank_select(fitness,populationSize-1);
                        if(tab.find(rs1)==tab.end() && tab.find(rs2)==tab.end()){
                                tab[rs1] = rs2; tab[rs2] = rs1;
                        }
                }
               
                //将当前代没有被选择作为交叉对的直接加入到下一代
                for(int i=0;i<populationSize;i++){
                        if(tab.find(i)==tab.end()){
                                vector<int> baby = parent[i];
                                if(rand()*1.0/RAND_MAX < mutationRate){ //进行变异
                                        int p1 = rand()%chromLen, p2 = p1;
                                        while(p1==p2) p2=rand()%chromLen;

                                        //逆转baby染色体的某一段
                                        reverse(baby.begin()+ min(p1,p2),baby.begin()+ max(p1,p2));
                                }
                                //精英策略，若是比当前代更差，则不保留baby
                                if(caculate_fit(baby)<fitness[i]) population.push_back(baby);
                                else population.push_back(parent[i]);
                               
                        }
                }
                //按交叉概率决定选出来的交叉对是否交叉
                while(population.size()<populationSize){

                        unordered_map<int,int>::iterator it = tab.begin();
                        int k1 = it->first, k2 = it->second;
                        vector<int> baby1 = parent[k1], baby2 = parent[k2];
                        tab.erase(k1);
                        tab.erase(k2);
                        if (rand()*1.0/RAND_MAX<crossoverRate){ //染色体交叉
                                //编码
                                sequence_encode(baby1);
                                sequence_encode(baby2);

                                //将编码后的两条染色体单点交叉
                                int crs = rand()%chromLen;
                                swap(baby1[crs],baby2[crs]);

                                //解码,解码后的染色体可能是连续交叉
                                sequence_decode(baby1);
                                sequence_decode(baby2);       
                        }

                        //根据变异概率让baby1,baby2变异
                        for(int b=0;b<=1;b++){
                                if(rand()*1.0/RAND_MAX < mutationRate){
                                        int p1 = rand()%chromLen, p2 = p1;
                                        while(p1==p2) p2=rand()%chromLen;

                                        //逆转baby1,baby2染色体的某一段
                                        if(b==0) reverse(baby1.begin()+ min(p1,p2),baby1.begin()+ max(p1,p2));
                                        else reverse(baby2.begin()+ min(p1,p2),baby2.begin()+ max(p1,p2));
                                }
                        }
                       
                        if(caculate_fit(baby1)<fitness[k1]) population.push_back(baby1);
                        else population.push_back(parent[k1]);
                        if(caculate_fit(baby2)<fitness[k2]) population.push_back(baby2);
                        else population.push_back(parent[k2]);       
                }       
                delete fitness;
        }

        fout<<"\n\n\n历史最优路径长度: "
                <<glob_best_len<<endl                       
                <<"历史最优路径:\n";
        for (int i=0;i<cityNum;i++){
                fout<<glob_best_path[i]<<" ";
        }
        fout<<endl;
        curTime=int(time(0))-curTime;
        fout<<"总共用时:"<<curTime<<"ms\n";
        fout.close();
}

int main(){
        cout<<"running..."<<endl;
        init();
        run();
        for (int i=0;i<cityNum;i++){ delete[] dist[i];}       
        delete[] dist;
        cout<<"done!"<<endl;
        return 0;
}