extl/intelligence/ga/ga_base.h

   1 /* ///////////////////////////////////////////////////////////////////////
   2  * File:                ga_base.h
   3  *
   4  * Created:             08.09.14
   5  * Updated:             08.11.07
   6  *
   7  * Brief:               The Genetic Algoritm Base Class
   8  *
   9  * [<Home>]
  10  * Copyright (c) 2008-2020, Waruqi All rights reserved.
  11  * //////////////////////////////////////////////////////////////////// */
  12
  13 #ifndef EXTL_INTELLIGENCE_GA_GA_BASE_H
  14 #define EXTL_INTELLIGENCE_GA_GA_BASE_H
  15
  16 /*!\file ga_base.h
  17  * \brief The Genetic Algoritm Base Class
  18  */
  19 #ifndef __cplusplus
  20 #       error ga_base.h need be supported by c++.
  21 #endif
  22
  23 /* ///////////////////////////////////////////////////////////////////////
  24  * Includes
  25  */
  26 #include "prefix.h"
  27
  28 /* ///////////////////////////////////////////////////////////////////////
  29  * ::extl::intelligence namespace
  30  */
  31 EXTL_INTELLIGENCE_BEGIN_WHOLE_NAMESPACE
  32
  33 /*!\brief fitness_traits_base class
  34  *
  35  * \param Gt The ga_traits type
  36  *
  37  * \ingroup extl_group_intelligence
  38  */
  39 template<typename_param_k Gt>
  40 class ga_base
  41 {
  42         /// \name Types
  43         /// @{
  44         public:
  45                 typedef ga_base                                                                                                 class_type;
  46                 typedef Gt                                                                                                              ga_traits_type;
  47                 typedef typename_type_k ga_traits_type::size_type                               size_type;
  48                 typedef typename_type_k ga_traits_type::bool_type                               bool_type;
  49                 typedef typename_type_k ga_traits_type::float_type                              float_type;
  50                 typedef typename_type_k ga_traits_type::index_type                              index_type;
  51                 typedef typename_type_k ga_traits_type::int_type                                int_type;
  52                 typedef typename_type_k ga_traits_type::population_type                 population_type;
  53                 typedef typename_type_k ga_traits_type::individual_type                 individual_type;
  54         /// @}
  55
  56         /// \name Members
  57         /// @{
  58         private:
  59                 ga_traits_type                                                                                                  m_ga_traits;
  60                 population_type                                                                                                 m_pop;
  61         /// @}
  62
  63         /// \name Methods
  64         /// @{
  65         public:
  66                 /// Generates a best population
  67                 bool_type generate(population_type& pop)
  68                 {
  69                         // initialize ga_traits
  70                         ga_traits().init_traits();
  71
  72                         // invariance
  73                         EXTL_ASSERT(ga_traits().is_valid());
  74                         EXTL_ASSERT(pop.size() > 0);
  75                         if (!ga_traits().is_valid() || pop.size() <= 0) return e_false_v;
  76
  77                         // initialize child population
  78                         population_type child_pop = pop;
  79                         population_type* pchild_pop = &child_pop;
  80                         population_type* pparent_pop = &pop;
  81
  82                         size_type max_g = ga_traits().max_g();
  83                         for (index_type i = 0; i < max_g; ++i)
  84                         {
  85                                 // calculate the fitnesses of the population
  86                                 ga_traits().fitness(*pparent_pop);
  87
  88                                 // find out the best result
  89                                 if (ga_traits().is_stop(*pparent_pop)) break;
  90
  91                                 // reserve best individual
  92                                 pchild_pop->individual(0) = pparent_pop->best();
  93
  94                                 // prepare ga_traits for internal recurrence
  95                                 ga_traits().prepare(*pparent_pop);
  96
  97                                 // coverover and mutation
  98                                 size_type select_n = pchild_pop->size() - 1;
  99                                 size_type start_n = (pchild_pop->size() % 2)? 1 : (pchild_pop->individual(1) = pchild_pop->individual(0), 2);
 100                                 for (size_type j = start_n; j < select_n; ++j)
 101                                 {
 102                                         // select two individuals from the population
 103                                         pchild_pop->individual(j) = ga_traits().select(*pparent_pop);
 104                                         pchild_pop->individual(j + 1) = ga_traits().select(*pparent_pop);
 105
 106                                         // cross
 107                                         ga_traits().cross(pchild_pop->individual(j), pchild_pop->individual(j + 1));
 108
 109                                         // mutate
 110                                         ga_traits().mutate(pchild_pop->individual(j));
 111                                         ga_traits().mutate(pchild_pop->individual(j + 1));
 112                                 }
 113
 114                                 // local_search
 115                                 ga_traits().local_search(*pchild_pop);
 116
 117                                 // next generation
 118                                 pchild_pop->generation(pparent_pop->generation() + 1);
 119                                 std_swap(pchild_pop, pparent_pop);
 120                         }
 121
 122                         // update this population and return it
 123                         ga_traits().fitness(*pparent_pop);
 124                         if (pparent_pop != &pop) pop = *pparent_pop;
 125
 126                 #if defined(EXTL_INTELLIGENCE_GA_GA_TEST_ENABLE) && \
 127                                 !defined(EXTL_INTELLIGENCE_GA_UGA_TEST_ENABLE)
 128                         // report detail for debugging
 129                         report(pop);
 130                 #endif
 131
 132                         EXTL_ASSERT(ga_traits().is_valid());
 133                         return e_true_v;
 134                 }
 135
 136                 /// Generates a best population
 137                 bool_type generate()
 138                 {
 139                         // initialize population
 140                         m_pop.resize(ga_traits().pop_size());
 141                         ga_traits().init_pop(m_pop);
 142
 143                         return generate(m_pop);
 144                 }
 145         /// @}
 146
 147         /// \name Attributes
 148         /// @{
 149         public:
 150                 /// Returns const ga_traits
 151                 ga_traits_type const&   ga_traits() const       { return m_ga_traits;                           }
 152                 /// Returns ga_traits
 153                 ga_traits_type&                 ga_traits()                     { return m_ga_traits;                           }
 154
 155                 /// Returns the best individual
 156                 individual_type const&  best() const            { return population().best();           }
 157                 /// Returns the population at last generation
 158                 population_type const&  population() const      { return m_pop;                                         }
 159
 160                 /// Returns the generation of the best population
 161                 size_type const                 generation() const      { return population().generation();     }
 162         /// @}
 163
 164         private:
 165         #ifdef EXTL_INTELLIGENCE_GA_GA_TEST_ENABLE
 166                 void report(population_type const& pop)
 167                 {
 168                         EXTL_TEST_TRACE(_T("g:%d fmin:%f fmax:%f fsum:%f favg:%f"),
 169                                 pop.generation(), pop.fmin(), pop.fmax(), pop.fsum(), pop.favg());
 170
 171                         //EXTL_TEST_TRACE(_T("best: x=%f fvalue:%f"),
 172                         //      pop.best().value(0), ga_traits().fvalue(pop.best()));
 173
 174                         /*EXTL_TEST_TRACE(_T("detail:"));
 175                         for (size_type i = 0; i < pop.size(); ++i)
 176                         {
 177                                 EXTL_TEST_TRACE(
 178                                         _T("x=%f fvalue:%f fit:%f pro:%f"),
 179                                         pop.individual(i).value(0),
 180                                         ga_traits().fvalue(pop.individual(i)),
 181                                         pop.individual(i).fitness(),
 182                                         pop.individual(i).probability());
 183                         }*/
 184
 185                         EXTL_TEST_TRACE(_T("\n"));
 186                 }
 187         #endif
 188 };
 189
 190
 191 /* ///////////////////////////////////////////////////////////////////////
 192  * ::extl::intelligence namespace
 193  */
 194 EXTL_INTELLIGENCE_END_WHOLE_NAMESPACE
 195
 196 /* //////////////////////////////////////////////////////////////////// */
 197 #endif /* EXTL_INTELLIGENCE_GA_GA_BASE_H */
 198 /* //////////////////////////////////////////////////////////////////// */