[アルゴリズム]遺伝アルゴリズム局所最値を求める

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <cmath>

#include <ctime>

using namespace std;

void decode(double xBegin, double yBegin,pair<string, string> sample,double& x, double& y);

double targetFun(double xBegin, double yBegin,pair<string, string>& sample);

void randomInit(double xBegin,double xEnd, double yBegin, double yEnd,vector< pair<string,string> > &group,unsigned int nGroup, double error=0.125);

double maxOfGroup(vector< pair<string, string> >&group, pair<string, string>& solution, double xBegin, double yBegin,double& sum);

void genPopulation(vector< pair<string, string> >&group,double sum,double xBegin, double yBegin,double matingProb = 1.0,double mutateProb = 0.001);

void singularMating(pair<string, string>& sample1,pair<string, string>& sample2);

void mutate(pair<string, string>& sample);

void groupMating(vector< pair<string, string> >&group,double matingProb = 1.0);

void groupMutate(vector< pair<string, string> >&group,double mutateProb = 0.001);

int main()

{

    vector< pair<string,string> > group;

    pair<string,string> solution,tempSolution;

    double sum,epsilon = 0.01,matingProb = 1.0, mutateProb = 0.001;

    //sum           ,epsilon       ,matingProb    ，mutateProb    

    double xBegin = 1, xEnd = 2, yBegin = 1, yEnd = 2;

    unsigned int nGroup = 16;

    randomInit(xBegin,xEnd,yBegin,yEnd,group,nGroup);

    double preMax = maxOfGroup(group,solution,xBegin,yBegin,sum);

    genPopulation(group,sum,xBegin,yBegin);

    double currentMax = maxOfGroup(group,tempSolution,xBegin,yBegin,sum);

    unsigned int i = 0;

    while (abs(preMax-currentMax) > epsilon && i++ < nGroup*nGroup)

    {

        if (currentMax > preMax)

        {

            preMax = currentMax;

            solution = tempSolution;

        }

        genPopulation(group,sum,xBegin,yBegin);

        currentMax = maxOfGroup(group,tempSolution,xBegin,yBegin,sum);

    }

    cout<<"    ："<<preMax<<endl;

    cin.get();

    return 0;

}



void decode(double xBegin, double yBegin,pair<string, string> sample,double& x, double& y)

{

    x = xBegin,y = yBegin;

    double base= 0.5;

    string first,second;

    first = sample.first;

    second = sample.second;

    for (unsigned int i = 0; i < first.size(); ++i)

    {

        if ('1' == first.at(i))

        {

            x += base;

        }

        base /=2;

    }

    base = 0.5;

    for (unsigned int i = 0; i < second.size(); ++i)

    {

        if ('1' == second.at(i))

        {

            y += base;

        }

        base /=2;

    }

}



double targetFun(double xBegin, double yBegin,pair<string, string>& sample)

{

    const double matingProb = 1.0;

    const double mutateProb = 0.001;

    double x,y;

    decode(xBegin,yBegin,sample,x,y);

    return x*sin(6*y)+y*cos(8*x);

}



void randomInit(double xBegin,double xEnd, double yBegin, double yEnd,vector< pair<string,string> > &group,unsigned int nGroup, double error)

{

    unsigned int xLen, yLen;

    xLen = ceil(log((xEnd-xBegin)/error + 1)/log(2));

    yLen = ceil(log((yEnd-yBegin)/error + 1)/log(2));

    string x, y;

    pair<string, string> sample;

    srand(unsigned (time(0)));

    for (unsigned int i = 0; i < nGroup ;++i)

    {

        for (unsigned int j = 0; j < xLen; ++j)

        {

            x.push_back(rand()%2 + '0');

        }

        for (unsigned int k = 0; k < xLen; ++k)

        {

            y.push_back(rand()%2 + '0');

        }

        sample.first = x;

        sample.second = y;

        group.push_back(sample);

        x.clear();

        y.clear();

    }    

}



void singularMating(pair<string, string>& sample1,pair<string, string>& sample2)

{

    unsigned matingPoint = rand()%(sample1.first.size()+sample1.second.size()-1)+1;

    string temp;

    if (matingPoint <= sample1.first.size())

    {

        temp = sample1.second;

        sample1.second = sample2.second;

        sample2.second = temp;

        temp.clear();

        temp.assign(sample1.first.begin()+matingPoint,sample1.first.end());

        sample1.first.insert(sample1.first.begin()+matingPoint,sample2.first.begin()+matingPoint,sample2.first.end());

        sample1.first.resize(sample2.first.size());

        sample2.first.insert(sample2.first.begin()+matingPoint,temp.begin(),temp.end());

        sample2.first.resize(sample1.first.size());

    }

    else

    {

        matingPoint -= sample1.first.size();

        temp.assign(sample1.second.begin()+matingPoint,sample1.second.end());

        sample1.second.insert(sample1.second.begin()+matingPoint,sample2.second.begin()+matingPoint,sample2.second.end());

        sample1.second.resize(sample2.second.size());

        sample2.second.insert(sample2.second.begin()+matingPoint,temp.begin(),temp.end());

        sample2.second.resize(sample1.second.size());

    }

}



void groupMating(vector< pair<string, string> >&group,double matingProb)

{

    unsigned int i = 0;

    while (i < group.size()-1)

    {

        if (rand()/(double)RAND_MAX < matingProb)

        {

            singularMating(group.at(i),group.at(i+1));

        }

        i += 2;

    }

}

void groupMutate(vector< pair<string, string> >&group,double mutateProb)

{

    vector< pair<string, string> >::iterator iter = group.begin();

    while (group.end() != iter)

    {

        if (rand()/double(RAND_MAX) < mutateProb)

        {

            mutate(*iter);

        }

        ++iter;

    }

}

void mutate(pair<string, string>& sample)

{

    unsigned mutatePoint = rand() % (sample.first.size() + sample.second.size());

    if (mutatePoint < sample.first.size())

    {

        if (sample.first.at(mutatePoint) == '0')

        {

            sample.first.at(mutatePoint)='1';

        }

        else

        {

            sample.first.at(mutatePoint)='0';

        }

    }

    else

    {

        mutatePoint -= sample.first.size();

        if (sample.second.at(mutatePoint) == '0')

        {

            sample.second.at(mutatePoint) = '1';

        } 

        else

        {

            sample.second.at(mutatePoint) = '0';

        }

    }

}



double maxOfGroup(vector< pair<string, string> >&group, pair<string, string>& solution, double xBegin, double yBegin,double& sum)

{

    vector< pair<string, string> >::iterator iter = group.begin();

    double currentMax = targetFun(xBegin,yBegin,*iter),temp; 

    sum = currentMax;

    solution = *iter;

    ++iter;

    while (group.end() != iter)

    {

        temp = targetFun(xBegin,yBegin,*iter);

        sum += temp;

        if (temp > currentMax)

        {

            currentMax = temp;

            solution = *iter;

        }

        ++iter;

    }

    return currentMax;

}



void genPopulation(vector< pair<string, string> >&group,double sum,double xBegin, double yBegin,double matingProb,double mutateProb)

{

    unsigned int n = group.size();

    double* ProbSection = new double[n+1];//       

    unsigned int* individual = new unsigned int[n];//         

    ProbSection[0] = 0.0;

    unsigned int i = 0;

    while (i < n)

    {

        ProbSection[i+1] = ProbSection[i] + targetFun(xBegin,yBegin,group.at(i))/sum;

        individual[i] = 0;

        ++i;

    }

    i = 0;

    double r;

    unsigned int times;

    while (i < n)

    {

        times = 0;

        r = rand()/(double)RAND_MAX;

        for (unsigned int j = 0; j < n; ++j)

        {

            if (r > ProbSection[j])

            {

                ++times;

            }

        }

        ++individual[times-1];

        ++i;

    }

    i = 0;

    while (i < n)

    {

        while (individual[i]-- > 0)

        {

            group.push_back(group.at(i));

        }

        ++i;

    }

    reverse(group.begin(),group.end());

    group.resize(n);

    delete ProbSection;

    delete individual;

}