博客

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;
const int MAX_N=1000+5;
const int PI=acos(-1.0);
const int DNA_SIZE=20;

int n;
int pop[MAX_N],pop_next[MAX_N];
double fit[MAX_N];

double Rand(){
    return rand()/(RAND_MAX+1.0);
}

double f(double x,double E,double V){//正态分布函数,f(x),均值E,标准差V
    return (1/(sqrt(2*PI)*V))*exp(-1*(x-E)*(x-E)/(2*V*V));
}

void init(){
    for(int i=0;i<n;i++)pop[i]=Rand()*(1<<DNA_SIZE);
}

double decoding(int x){
    return (double)x/((1<<DNA_SIZE)-1)*6;
}

void get_fitness(){
    for(int i=0;i<n;i++)fit[i]=f(decoding(pop[i]),2,3);
    double s=0;
    for(int i=0;i<n;i++)s+=fit[i];
    for(int i=0;i<n;i++)fit[i]/=s;
}

void select(){
    for(int i=0;i<n;i++){
        double p=Rand();
        double s=0;
        pop_next[i]=pop[0];
        for(int j=0;j<n;j++){
            s+=fit[j];
            if(s>p){
                pop_next[i]=pop[j];
                break;
            }
        }
    }
    swap(pop,pop_next);
}

void crossover(double rate=0.8){
    for(int i=0;i<n;i++){
        int x=pop[i];
        if(Rand()<rate){
            int y=pop[rand()%n];
            int h=rand()%DNA_SIZE;
            int s1=(x&((1<<h)-1));
            int s2=(y&((1<<h)-1));
            x=x-s1+s2;
        }
        pop_next[i]=x;
    }
    swap(pop,pop_next);
}

void mutation(double rate=0.05){
    for(int i=0;i<n;i++){
        if(Rand()<rate){
            int h=rand()%DNA_SIZE;
            pop[i]=(pop[i]^(1<<h));
        }
    }
}

int main()
{
    n=200;
    init();

    double h=0;
    for(int j=0;j<n;j++){
        if(f(decoding(pop[j]),2,3)>f(h,2,3))h=decoding(pop[j]);
    }
    cout<<h<<endl;
    //for(int i=0;i<n;i++)cout<<decoding(pop[i])<<" ";
    //cout<<endl;
    for(int i=0;i<100;i++){

        get_fitness();
        select();

        crossover();
        mutation();

        double h=0;
        for(int j=0;j<n;j++){
            if(f(decoding(pop[j]),2,3)>f(h,2,3))h=decoding(pop[j]);
        }
        cout<<h<<endl;

        //for(int i=0;i<n;i++)cout<<(int)decoding(pop[i])<<" ";
        //cout<<endl;
        //cout<<endl;

        //for(int i=0;i<n;i++)cout<<decoding(pop[i])<<" ";
        //cout<<endl;
    }
    return 0;
}