diff_evo_adapt.h
Go to the documentation of this file.
1 /*
2  -------------------------------------------------------------------
3 
4  Copyright (C) 2010-2014, Edwin van Leeuwen
5 
6  This file is part of O2scl.
7 
8  O2scl is free software; you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version.
12 
13  O2scl is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with O2scl. If not, see <http://www.gnu.org/licenses/>.
20 
21  -------------------------------------------------------------------
22 */
23 #ifndef O2SCL_DIFF_EVO_ADAPT_H
24 #define O2SCL_DIFF_EVO_ADAPT_H
25 
26 /** \file diff_evo_adapt.h
27  \brief File defining \ref o2scl::diff_evo_adapt
28 */
29 
30 #include <vector>
31 #include <algorithm>
32 
33 #include <o2scl/rng_gsl.h>
34 #include <o2scl/mm_funct.h>
35 
36 #include <o2scl/diff_evo.h>
37 
38 #ifndef DOXYGEN_NO_O2NS
39 namespace o2scl {
40 #endif
41 
42  /** \brief Multidimensional minimization by the differential
43  evolution method
44 
45  This class minimizes a function using differential evolution.
46  This method is a genetic algorithm and as such works well for
47  non continuous problems, since it does not rely on a gradient of
48  the function that is being mind.
49 
50  This is an adaptive version of \ref diff_evo as described in
51  \ref Brest06 .
52  */
53  template<class func_t=multi_funct11,
55  class init_funct_t=mm_funct11>
56  class diff_evo_adapt : public diff_evo<func_t, vec_t, init_funct_t>
57  {
58 
59  public:
60 
62 
63  /// Probability of adjusting f (default 0.1)
64  double tau_1;
65  /// Probability of adjusting cr (default 0.1)
66  double tau_2;
67 
68  /// \name Lower bound and range of F (defaults 0.1 and 0.9)
69  //@{
70  double fl, fr;
71  //@}
72 
73  diff_evo_adapt() : diff_evo<func_t, vec_t, init_funct_t>() {
74  tau_1 = 0.1;
75  tau_2 = 0.1;
76  fl = 0.1;
77  fr = 0.9;
78  }
79 
80  /** \brief Calculate the minimum \c fmin of \c func w.r.t the
81  array \c x of size \c nvar.
82  */
83  virtual int mmin(size_t nvar, vec_t &x0, double &fmin,
84  func_t &func) {
85 
86  // Keep track of number of generation without better solutions
87  int nconverged = 0;
88  if (this->pop_size==0) {
89  // Automatically select pop_size dependent on dimensionality.
90  this->pop_size = 10*nvar;
91  }
92 
93  initialize_population( nvar, x0 );
94  fmins.resize(this->pop_size);
95 
96  // Set initial fmin
97  for (size_t x = 0; x < this->pop_size; ++x) {
98  vec_t agent_x;
99  agent_x.resize(nvar);
100  for (size_t i = 0; i < nvar; ++i) {
101  agent_x[i] = this->population[x*nvar+i];
102  }
103  double fmin_x = 0;
104  fmin_x=func(nvar,agent_x);
105  fmins[x]=fmin_x;
106  if (x==0) {
107  fmin = fmin_x;
108  for (size_t i = 0; i<nvar; ++i)
109  x0[i] = agent_x[i];
110  //x0 = agent_x;
111  } else if (fmin_x<fmin) {
112  fmin = fmin_x;
113  for (size_t i = 0; i<nvar; ++i)
114  x0[i] = agent_x[i];
115  //x0 = agent_x;
116  }
117 
118  }
119 
120  int gen = 0;
121  while (gen < this->ntrial && nconverged <= ((int)this->nconv)) {
122  ++nconverged;
123  ++gen;
124 
125  // For each agent x in the population do:
126  for (size_t x = 0; x < this->pop_size; ++x) {
127 
128  std::vector<int> others;
129 
130  // Create a copy agent_x and agent_y of the current agent vector
131  vec_t agent_x, agent_y;
132  agent_x.resize(nvar);
133  agent_y.resize(nvar);
134  for (size_t i = 0; i < nvar; ++i) {
135  agent_x[i] = this->population[x*nvar+i];
136  agent_y[i] = this->population[x*nvar+i];
137  }
138  // Value of f and cr for this agent
139  double f_x, cr_x;
140  if (this->gr.random() >= tau_1) {
141  f_x = variables[x*2];
142  } else {
143  f_x = fl+this->gr.random()*fr;
144  } if (this->gr.random() >= tau_2) {
145  cr_x = variables[x*2+1];
146  } else {
147  cr_x = this->gr.random();
148  }
149 
150  // Pick three agents a, b, and c from the population at
151  // random, they must be distinct from each other as well
152  // as from agent x
153  others = this->pick_unique_agents( 3, x );
154 
155  // Pick a random index R {1, ..., n}, where the highest
156  // possible value n is the dimensionality of the problem
157  // to be optimized.
158  size_t r = floor(this->gr.random()*nvar);
159 
160  for (size_t i = 0; i < nvar; ++i) {
161  // Pick ri~U(0,1) uniformly from the open range (0,1)
162  double ri = this->gr.random();
163  // If (i=R) or (ri<CR) let yi = ai + F(bi - ci),
164  // otherwise let yi = xi
165  if (i == r || ri < cr_x) {
166  agent_y[i] = this->population[others[0]*nvar+i] +
167  f_x*(this->population[others[1]*nvar+i]-
168  this->population[others[2]*nvar+i]);
169  }
170  }
171  // If (f(y) < f(x)) then replace the agent in the
172  // population with the improved candidate solution, that is,
173  // set x = y in the population
174  double fmin_y;
175 
176  fmin_y=func(nvar,agent_y);
177  if (fmin_y<fmins[x]) {
178  for (size_t i = 0; i < nvar; ++i) {
179  this->population[x*nvar+i] = agent_y[i];
180  fmins[x] = fmin_y;
181  }
182 
183  variables[x*2] = f_x;
184  variables[x*2+1] = cr_x;
185 
186  if (fmin_y<fmin) {
187  fmin = fmin_y;
188  for (size_t i = 0; i<nvar; ++i) {
189  x0[i] = agent_y[i];
190  }
191  nconverged = 0;
192  }
193  }
194 
195  }
196  if (this->verbose > 0) {
197  this->print_iter( nvar, fmin, gen, x0 );
198  }
199  }
200  if(gen>=this->ntrial) {
201  std::string str="Exceeded maximum number of iterations ("+
202  itos(this->ntrial)+") in diff_evo::mmin().";
203  O2SCL_CONV_RET(str.c_str(),exc_emaxiter,this->err_nonconv);
204  }
205  return 0;
206  };
207 
208  /** \brief Print out iteration information.
209 
210  */
211  virtual void print_iter( size_t nvar, double fmin,
212  int iter, vec_t &best_fit ) {
213  std::cout << "Generation " << iter << std::endl;
214  std::cout << "Fmin: " << fmin << std::endl;
215  std::cout << "Parameters: ";
216  for (size_t i=0; i<nvar; ++i) {
217  std::cout << best_fit[i] << " ";
218  }
219  std::cout << std::endl;
220  std::cout << "Population: " << std::endl;
221  for (size_t i=0; i<this->pop_size; ++i ) {
222  std::cout << i << ": ";
223  for (size_t j = 0; j<nvar; ++j ) {
224  std::cout << this->population[i*nvar+j] << " ";
225  }
226  std::cout << "fmin: " << fmins[i] <<
227  " F: " << variables[i*2] <<
228  " CR: " << variables[i*2+1] << std::endl;
229  }
230  }
231 
232 
233 #ifndef DOXYGEN_INTERNAL
234 
235  protected:
236 
237  /**
238  * \brief Vector containing the tunable variable F and CR
239  */
240  vec_t variables;
241 
242  /// Vector that keeps track of fmins values
243  ubvector fmins;
244 
245  /**
246  * \brief Initialize a population of random agents
247  */
248  virtual int initialize_population( size_t nvar, vec_t &x0 ) {
249  if (this->rand_init_funct==NULL) {
250  O2SCL_ERR("No initialization function provided.",
251  exc_ebadfunc );
252 
253  }
254  this->population.resize(nvar*this->pop_size );
255  variables.resize(2*this->pop_size );
256  for (size_t i = 0; i < this->pop_size; ++i) {
257  vec_t y(nvar);
258  (*this->rand_init_funct)( nvar, x0, y );
259  for (size_t j = 0; j < nvar; ++j) {
260  this->population[ i*nvar+j ] = y[j];
261 
262  }
263 
264  variables[i*2] = fl + this->gr.random()*fr;
265  variables[i*2+1] = this->gr.random();
266  }
267  return 0;
268  }
269 
270  private:
271 
275  (const diff_evo_adapt<func_t,vec_t,init_funct_t>&);
276 
277 #endif
278 
279  };
280 
281 #ifndef DOXYGEN_NO_O2NS
282 }
283 #endif
284 
285 #endif
size_t nconv
The number of generations without a better fit before we assume that the algorithm has converged (def...
Definition: diff_evo.h:86
double tau_2
Probability of adjusting cr (default 0.1)
The main O<span style=&#39;position: relative; top: 0.3em; font-size: 0.8em&#39;>2</span>scl O$_2$scl names...
Definition: anneal.h:42
#define O2SCL_CONV_RET(d, n, b)
Set a "convergence" error and return the error value.
Definition: err_hnd.h:292
Multidimensional minimization by the differential evolution method.
Definition: diff_evo.h:66
std::function< int(size_t, const boost::numeric::ublas::vector< double > &, boost::numeric::ublas::vector< double > &) > mm_funct11
Array of multi-dimensional functions typedef.
Definition: mm_funct.h:43
exceeded max number of iterations
Definition: err_hnd.h:73
double tau_1
Probability of adjusting f (default 0.1)
double random()
Return a random number in .
Definition: rng_gsl.h:82
size_t pop_size
Population size (default 0)
Definition: diff_evo.h:81
Multidimensional minimization by the differential evolution method.
ubvector fmins
Vector that keeps track of fmins values.
bool err_nonconv
If true, call the error handler if the routine does not "converge".
Definition: mmin.h:209
virtual int mmin(size_t nvar, vec_t &x0, double &fmin, func_t &func)
Calculate the minimum fmin of func w.r.t the array x of size nvar.
virtual int initialize_population(size_t nvar, vec_t &x0)
Initialize a population of random agents.
virtual void print_iter(size_t nvar, double fmin, int iter, vec_t &best_fit)
Print out iteration information.
#define O2SCL_ERR(d, n)
Set an error with message d and code n.
Definition: err_hnd.h:273
init_funct_t * rand_init_funct
Function that is used to produce random init variables.
Definition: diff_evo.h:311
virtual std::vector< int > pick_unique_agents(int nr, size_t x)
Pick number of unique agent id&#39;s.
Definition: diff_evo.h:343
problem with user-supplied function
Definition: err_hnd.h:69
vec_t variables
Vector containing the tunable variable F and CR.
vec_t population
Vector containing the population.
Definition: diff_evo.h:302
std::function< double(size_t, const boost::numeric::ublas::vector< double > &)> multi_funct11
Multi-dimensional function typedef.
Definition: multi_funct.h:45
rng_gsl gr
Random number generator.
Definition: diff_evo.h:314
std::string itos(int x)
Convert an integer to a string.
int ntrial
Maximum number of iterations.
Definition: mmin.h:197

Documentation generated with Doxygen. Provided under the GNU Free Documentation License (see License Information).