遗传算法探索

偏执的太偏执、 2023-07-03 10:46 14阅读 0赞

### 遗传算法探索 ###

*  遗传算法
 *   *  关于遗传算法的实现细节
     *  c语言代码

# 遗传算法 #

适者生存。”适“的是什么？是我们身边的环境还是上帝的指引？  
自然界的生物不管情愿与否都被刻画着。有一条无形的手指引着人类前进的方向。  
遗传算法，一个程序员自己刻画世界的方式。遗传算法通过模拟自然界的交叉变异，保证了问题的搜索空间。通过适应度函数刻画程序员自己的世界。

--------------------

遗传算法本身是神经网络的前身。遗传算法的适应度函数和神经网络的损失函数本质一样。都是描述正解和现在得到解的差别。前期的神经网络就是通过遗传算法当作损失函数的。

## 关于遗传算法的实现细节 ##

--------------------

一般的遗传算法都有一个交配概率（又称为交叉概率），范围一般是0.6~1，这个交配概率反映两个被选中的个体进行交配的概率。例如，交配概率为0.8，则80%的“夫妻”会生育后代。每两个个体通过交配产生两个新个体，代替原来的“老”个体，而不交配的个体则保持不变。–维基百科

## c语言代码 ##

#include <stdio.h>
    #include <stdlib.h>
    
    struct Population{ 
        int gene[11];//基因为0，1组成
        double x;//基因型转化为表现型
        double y;
    };
    /* 求y=x*x的最小值，x取值范围为【-1,1】精度为0.001,所以基因位为11 */
    //初始种群
    void initPopulation(struct Population *population,int populationNum){ 
        srand((unsigned)time(NULL));
        for(int i=0;i<populationNum;i++){ 
          population[i].x=-1;
          for(int j=0;j<11;j++){ 
            population[i].gene[j]=rand()%2;//随机数
          }
          printf("init gene[%d]=",i);
          for(int j=0;j<11;j++){ 
            printf("%d",population[i].gene[j]);
          }
          printf("\n");
        }
    }
    
    //基因型转化为表现型
    void bitToNum(struct Population *population,int populationNum){ 
        for(int i=0;i<populationNum;i++){ 
                population[i].x=-1;
                int count=1;//进位符
            for(int j=10;j>=0;j--){ 
                population[i].x+=population[i].gene[j]*count*0.001;
                count*=2;
            }
            //printf("x=:%lf\n",population[i].x);
        }
        printf("\n");
    }
    
    //计算适应度函数
    void fitness(struct Population *population,int populationNum){ 
        for(int i=0;i<populationNum;i++){ 
            population[i].y=population[i].x*population[i].x;//y=x*x
            printf("y=:%lf\n",population[i].y);
        }
    }
    
    //选择
    void selection(struct Population *population,struct Population *crossoverPopulation,int populationNum){ 
    
    /*使用轮盘赌算法进行选择，因为该遗传算法是求最小值，所以不能直接对fitness轮盘赌，通过一顿花里胡哨的倒数归一化操作，*/
        double total=0,sum=0;
        for(int i = 0;i<populationNum;i++){ 
            total+=((double)population[i].y);
        }
        for(int i = 0;i<populationNum;i++){ 
            sum+=(total/population[i].y);
        }
        double num,temp,rate;
        for(int i=0;i<2*populationNum;i++){ 
            num = 0;
            temp = (rand()%100000)*0.00001;
            for(int j=0;j<populationNum;j++){ 
                num+=(total/population[j].y);
    
                double rate = (double)num/sum;
                if(temp <=rate){ 
                    for(int k=0;k<11;k++){ 
                        crossoverPopulation[i].gene[k]=population[j].gene[k];
                    }
                    break;
                }
            }
        }
    }
    //交叉
    void crossover(struct Population *population,struct Population *crossoverPopulation,int populationNum,double pc){ 
        int probability,pos;
        for(int i = 0;i<populationNum;i++){ 
            probability = rand()%100;
            if(probability<=pc*100){ 
                pos == rand()%11;
                for(int k=0;k<11;k++){ 
                    if(k<=pos){ 
                        population[i].gene[k]=crossoverPopulation[i].gene[k];
                    }else{ 
                        population[i].gene[k]=crossoverPopulation[i+populationNum].gene[k];
                    }
                }
            }
        }
    }
    //变异
    void mutation(struct Population *population,int populationNum,double pm){ 
        int probability,pos;
        for(int i=0;i<populationNum;i++){ 
            probability = rand()%100;
            if(probability<pm*100){ 
                pos=rand()%10;
                if(population[i].gene[pos]==1){ 
                    population[i].gene[pos]=0;
                }else{ 
                    population[i].gene[pos]=1;
                }
            }
        }
    }
    
    int main()
    { 
        int populationNum=10;//初始种群大小
        double pc=0.8;//交叉概率
        double pm=0.03;//变异概率
        int generationNum=1000;//训练代数
        struct Population population[populationNum];
        struct Population crossoverPopulation[2*populationNum];
        initPopulation(population,populationNum);
        for(int i=0;i<generationNum;i++){ 
            bitToNum(population,populationNum);
            fitness(population,populationNum);
            selection(population,crossoverPopulation,populationNum);
            crossover(population,crossoverPopulation,populationNum,pc);
            mutation(population,populationNum,pm);
            printf("\n");
        }
        printf("train finishing!!!");
        return 0;
    }