新建文本文档.txt

遗传算法的程序 遗传 算 法 (GeneticA lgorithm,G A)是一种大规模并行搜索优化算法

#pragma once
#include <vector>
#include <memory>
#include <cstdlib>
#include <iterator>
#include <ctime>

//Cross policy for crossing two DNA, using the average value of the sections in two DNA
class AvgCrossPolicy 
{
public:
    template<class InputIter, class OutputIter>
    static void birth(InputIter beg1, InputIter end1, InputIter beg2, InputIter end2, OutputIter beg)
    {
        for (;beg1 != end1; ++beg1, ++beg2, ++beg)
        {
            *beg = (*beg1 + *beg2) / 2;
        }
    }
};

//Default random policy for random number, using srand and rand.
class DefaultRandomPolicy
{
public:
    static void seed()
    {
        std::srand( (unsigned)std::time(NULL) );
    }
    static int rand()
    {
        return std::rand();
    }
    static const int precision = 10000;
};

//Reverse variation policy, transform t to -t as variation.
class ReverseVariationPolicy
{
public:
    template<class T>
    static T Variate(const T& t)
    {
        return -t;
    }
};

template<class T = double                                                  //the value in the DNA
 vector
            , class CrossPolicy = AvgCrossPolicy                           //Determine how to
 cross from two different DNAs
            , class RandomPolicy = DefaultRandomPolicy                     //Determine how to
 generate random number
            , class VariationPolicy = ReverseVariationPolicy>              //Determine how to
 Variate.
class Gene 
    : private AvgCrossPolicy
    , RandomPolicy
    , VariationPolicy
{
public:
    Gene()
    {
        clear();
    }

    void set_number(int hidden, int out, int input) throw()     // set nerve network structure, and
 times to iterate.
    {
        hidden_num = hidden;
        out_num = out;
        total = input;
    }

    void set_gene(int gener, int repre, int amino) throw()       // set inheritance property
    {
        gener_num = gener;
        repre_len = repre;
        amino_num = amino;
        in_num = ( amino_num * 2 + 1 ) * repre_len;
    }

    void set_probability(double p, double up, int choose) throw()    // set probability of variate
 and number to choose
    {
        prob = p;
        upper = up;
        choose_num = choose;
    }

    template<class OutIter>
    void generate(OutIter iter)                                 
    {
        int min = 0;                                         
        double min_rate = INT_MAX;                         
        length = in_num * hidden_num + hidden_num * out_num;

        generate_parents();                                  

        for(int i = 0; i < total; ++i)
        {                                                    
            change();
            cross();
        }

        for(int i = 0; i < gener_num; ++i)        
        {
            double rate = (*rating)(sons[i]);
            if( min_rate > rate)
            {
                min = i;
                min_rate = rate;
            }
        }

        for(int i = 0; i < length; ++i)            
            *(iter++) = sons[min][i];
    }

    void clear() //clear all data and return two its initial state
    {
        upper = prob = in_num = hidden_num = out_num = gener_num = repre_len = amino_num =
 choose_num = total = length = 0;
        sons.clear();
        rating.release();
    }

    template<class Functor>
    void set_rater(Functor rater) //set the rating functor.
    {
        rating.reset( new concrete_holder<Functor>(rater));
    }

private:

    class functor_holder
    {
    public:
        virtual double operator()(const std::vector<T>& v) = 0;
    };

    template<class Functor>
    class concrete_holder : public functor_holder
    {
    public:
        concrete_holder(Functor func) : functor(func)
        {
        }

        virtual double operator()(const std::vector<T>& v)
        {
            return functor(v);
        }

    private:
        Functor functor;
    };

    static double random()                              // get random number satisfying [0,1)
    {
        return static_cast<double>(RandomPolicy::rand() % RandomPolicy::precision) /
 RandomPolicy::precision;
    }
    void generate_parents()                             // generate the first generation
    {
        RandomPolicy::seed();
        sons.resize(gener_num);
        for(int i = 0; i < gener_num; ++i)
        {
            sons[i].resize(length);
            for( int j = 0; j < length; ++j)
                sons[i][j] = (random() - 0.5 ) * 2 * upper;
        }
    }

    void cross()                                       
    {
        static container_type children;              
        static std::vector<double> rate;               
        double sum, temp;
        static std::vector<double> probability;

        rate.resize(choose_num);
        probability.resize(choose_num);
        children.resize(choose_num);

        sum = temp = 0;
        
        for( int i = 0; i < choose_num; ++i)
        {
            int son1, son2;                            // choose mother and father

            children[i].resize(length);
            son1 = random(0, gener_num);
            son2 = random(0, gener_num);
            CrossPolicy::birth(sons[son1].begin()
                , sons[son1].end()
                , sons[son2].begin()
                , sons[son2].end()
                , children[i].begin());
            rate[i] = (*rating)(children[i]);
        }

        for(int i = 0; i < choose_num; ++i)
        {
            sum += 1 / rate[i];
        }
        for(int i = 0; i < choose_num; ++i)
        {
            temp += 1 / rate[i];
            probability[i] = temp / sum;
        }
        for(int i = 0; i < gener_num; ++i)
        {                                              // choose good child to survive.
            double temp_pro;
            int flag = 0;

            temp_pro = random();
            while(temp_pro > probability[flag]) 
            {
                ++flag;
            }
            for(int j = 0; j < length; ++j)            
            {
                sons[i][j] = children[flag][j];
            }
        }
    }

    void change()                                      // variation
    {
        int times;                                     
        int total_num;                                 
        total_num = length * gener_num;
        times = (int) (static_cast<double>(total_num) * prob);
        for(int i = 0; i < times; ++i)
        {
            int son, position;                         // variation point
            son = random(0, gener_num);
            position = random(0, length);
            sons[son][position] = VariationPolicy::Variate(sons[son][position]);  
        }
    }

    static int random(int begin, int end)               // get random integer between [begin, end]
    {
        return RandomPolicy::rand() % (end - begin) + begin;
    }

    
    int in_num, hidden_num, out_num;                    // input/hidden/output numbers;
    int gener_num;        //children count;
    int repre_len;        //length of representation
    int amino_num;        //length of DNA
    int choose_num;        //total child generated
    double prob, upper; // probability to variation
    int total;            // iteration count
    int length;            //length of child
    typedef std::vector<std::vector<T> > container_type;
    container_type sons;//a set inside the child
    std::auto_ptr<functor_holder> rating;

};