遗传算法染色体变长编码的实现

在基于遗传算法的路径规划问题中，先尝试了定长染色体编码，即用0/1来表示路口是否被选中，但是这样就忽视了顺序问题，假如有1->4->5->9->12以及1->5->4->7->9->12这样两条路径那么程序就很难区分染色体了，于是我决定使用变长染色体编码，直接用路口编号来表示染色体基因，以下程序为遗传个体结构以及其初始化。

#define Cmax 300
#define Cmin 0
#define num_nodes 12
#define max_pop 100
#define M 99999

double   p_cross = 0.9;                   //交叉概率
double   p_mutation = 0.03;                 //变异概率
int      MaxGeneration = 20;
int      generation;

struct individual      //定义染色体
{
vector <int> chrom;
int value;
double fitness; 
};
struct individual* Group = new struct individual[max_pop];
//初始化种群个体时随机产生当前路口的后继路口,返回此路口可到达的后继路口集合
vector <int> post(int cur){
vector <int> p ;
int i,j;
for(i=1; i<=num_nodes; i++){
if(m_distance[cur-1][i-1]<M && m_distance[cur-1][i-1]!=0)p.push_back(i);
    }
return p;
}

void GenerateInitialPopulation()         //每一个体十进制编码
{
int i,j;
int k,l,m;
int rand_ind;
bool flag[num_nodes];
vector <int> vec;
for(i = 0; i < max_pop; i++){
for(j=0; j<num_nodes; j++)flag[j]=false;              //标记位，用于防止出现环路,初始化为false指还未出现过
        Group[i].chrom.push_back(1);
        flag[0] = true;
        vec = post(1);
        j = 0;
vector<int>::iterator it_a;
while(Group[i].chrom[j]!=num_nodes){
            rand_ind = Random(0,vec.size()-1);
            k = vec[rand_ind]; 
if(k == num_nodes)
            {
                Group[i].chrom.push_back(k);
break;
            }
            it_a = vec.begin()+rand_ind;
vector <int> vec_test = post(k);
for(m=0; m<vec_test.size(); m++){              //若此路口的后继路口均出现过，则此路径去除
                l = vec_test[m];
if(flag[l-1] == true)continue;
else break;
            }
if(m == vec_test.size())
            {
                Group[i].chrom.clear();
                i--;
break;
            }
for(int m=0; m<vec.size(); m++)k_flag[m]=false;    //标记此路口的后继路口是否随机产生过*/
if(flag[k-1] == false)
                {
                    Group[i].chrom.push_back(k);
                    flag[k-1] = true;   //标记k路口已出现过
                    vec = post(k);
                    j++;
                }
else vec.erase(it_a);
        }
    }
}