Genetic algorithm is an algorithm which imitate the law of natural selection.

The main step:

Step 1:      Initialization     (Set Max evolutionary algebra and Create new individuals randomly)

Step 2:      Individual evaluation (Evaluate the fitness of each individuals using a fitness function)

Step 3:      Selection (Pick the proper individuals according to fitness)

Step 4:      Crossover (The most important part of GA)

Step 5:    Mutation (Accelerating convergence of the optimal solution)

 

         Worth mentioning, in most function, GA has to be stochastic realization. For example, in selection part, the larger an individual’s fitness is, the greater the chance of an individual to survive instead of individuals which has a larger survival rate survive certainly.

         To realize the randomness, there lots of methods we can choose. A good way is roulette wheel selection. We can first figure out the survival rate of an individual like this:

 

And then, we produce a random number and find out which part of it. Implement code:

 

Genome GenAlg:: GetChromoRoulette()            {                //产生一个0到人口总适应性评分总和之间的随机数.                //中m_dTotalFitness记录了整个种群的适应性分数总和)                double Slice = (random()) * totalFitness;                //这个基因将承载转盘所选出来的那个个体.                Genome TheChosenOne;                //累计适应性分数的和.                double FitnessSoFar = 0;                //遍历总人口里面的每一条染色体。                for (int i=0; i
     
      = Slice)                    {                        TheChosenOne = vecPop[i];                        break;                    }                }                //返回转盘选出来的个体基因                return TheChosenOne;            }
     

 

This weekend, I just learn a little of the GA, understanding the process of this algorithm. And take TSP problem as an example, simulating the process of GA roughly. Due to the lack of the main optimization algorithm, my GA code seem to be useless. My first GA code only reflect the idea of random, but not the idea of optimization and convergence. But my understanding of GA is deepen through this problem.

Here is my code:

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long LL;/************************City Set************************/string filename = "berlin52.txt";#define runs 10#define groupNum 10#define cnt 52 //城市数量const double pc = 0.65;//交配概率const double mp = 0.35;//变异概率/*********************************************************/double edge[cnt][cnt];double best_tsp = 1e7;int trace[cnt];struct City{ double x, y;}city[cnt];struct Group{ int cities[cnt]; double tsp; double fit; }group[groupNum], groupt[groupNum];void init(){ int num = 0; ifstream fin(filename); while(fin>>num){ fin>>city[num-1].x>>city[num-1].y; //cout<
            
             <<" "<
             
              <<" "<
              
               <
               
                 x ){ chosen[i] = j; break; } } } /*************************复制产生新一代种群*************************/ for(int i=0 ; i