diff_evo_adapt.h
Go to the documentation of this file.
1  /*
2  -------------------------------------------------------------------
3 
4  Copyright (C) 2010-2020, Edwin van Leeuwen and Andrew W. Steiner
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 require the gradient
48  of the function to be minimized.
49 
50  This is an adaptive version of \ref diff_evo as described in
51  \ref Brest06 .
52  */
53  template<class func_t=multi_funct,
55  class init_funct_t=mm_funct>
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  }
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  }
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 
201  this->last_ntrial=gen;
202 
203  if (gen>=this->ntrial) {
204  std::string str="Exceeded maximum number of iterations ("+
205  itos(this->ntrial)+") in diff_evo_adapt::mmin().";
206  O2SCL_CONV_RET(str.c_str(),exc_emaxiter,this->err_nonconv);
207  }
208  return 0;
209  };
210 
211  /** \brief Print out iteration information
212  */
213  virtual void print_iter(size_t nvar, double fmin,
214  int iter, vec_t &best_fit) {
215 
216  std::cout << "Generation " << iter << std::endl;
217  std::cout << "Fmin: " << fmin << std::endl;
218  std::cout << "Parameters: ";
219  for (size_t i=0; i<nvar; ++i) {
220  std::cout << best_fit[i] << " ";
221  }
222  std::cout << std::endl;
223  std::cout << "Population: " << std::endl;
224  for (size_t i=0; i<this->pop_size; ++i ) {
225  std::cout << i << ": ";
226  for (size_t j = 0; j<nvar; ++j ) {
227  std::cout << this->population[i*nvar+j] << " ";
228  }
229  std::cout << "fmin: " << fmins[i] <<
230  " F: " << variables[i*2] <<
231  " CR: " << variables[i*2+1] << std::endl;
232  }
233  if (this->verbose>1) {
234  char ch;
235  std::cin >> ch;
236  }
237  return;
238  }
239 
240 
241 #ifndef DOXYGEN_INTERNAL
242 
243  protected:
244 
245  /** \brief Vector containing the tunable variable F and CR
246  */
247  vec_t variables;
248 
249  /// Vector that keeps track of fmins values
251 
252  /** \brief Initialize a population of random agents
253  */
254  virtual int initialize_population( size_t nvar, vec_t &x0 ) {
255  this->population.resize(nvar*this->pop_size);
256  variables.resize(2*this->pop_size);
257  if (this->rand_init_funct==0) {
258  for(size_t i=0;i<this->pop_size;i++) {
259  for(size_t j=0;j<nvar;j++) {
260  double stepj=this->step[j%this->step.size()];
261  this->population[i*nvar+j]=x0[j]-stepj/2.0+stepj*this->gr.random();
262  }
263  variables[i*2] = fl + this->gr.random()*fr;
264  variables[i*2+1] = this->gr.random();
265  }
266  } else {
267  for (size_t i = 0; i < this->pop_size; ++i) {
268  vec_t y(nvar);
269  (*this->rand_init_funct)(nvar,x0,y);
270  for (size_t j = 0; j < nvar; ++j) {
271  this->population[ i*nvar+j ] = y[j];
272  }
273  variables[i*2] = fl + this->gr.random()*fr;
274  variables[i*2+1] = this->gr.random();
275  }
276  }
277  return 0;
278  }
279 
280  private:
281 
286 
287 #endif
288 
289  };
290 
291 #ifndef DOXYGEN_NO_O2NS
292 }
293 #endif
294 
295 #endif
o2scl::diff_evo< multi_funct, boost::numeric::ublas::vector< double >, mm_funct >::pop_size
size_t pop_size
Population size (default 0)
Definition: diff_evo.h:91
o2scl::diff_evo_adapt
Multidimensional minimization by the differential evolution method.
Definition: diff_evo_adapt.h:56
boost::numeric::ublas::vector< double >
o2scl
The main O<span style='position: relative; top: 0.3em; font-size: 0.8em'>2</span>scl O$_2$scl names...
Definition: anneal.h:42
o2scl::mmin_base< multi_funct, multi_funct, boost::numeric::ublas::vector< double > >::ntrial
int ntrial
Maximum number of iterations.
Definition: mmin.h:197
o2scl::mmin_base< multi_funct, multi_funct, boost::numeric::ublas::vector< double > >::last_ntrial
int last_ntrial
The number of iterations for in the most recent minimization.
Definition: mmin.h:206
o2scl::exc_emaxiter
@ exc_emaxiter
exceeded max number of iterations
Definition: err_hnd.h:73
o2scl::diff_evo_adapt::mmin
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.
Definition: diff_evo_adapt.h:83
o2scl::diff_evo< multi_funct, boost::numeric::ublas::vector< double >, mm_funct >::population
boost::numeric::ublas::vector< double > population
Vector containing the population.
Definition: diff_evo.h:333
o2scl::diff_evo_adapt::variables
vec_t variables
Vector containing the tunable variable F and CR.
Definition: diff_evo_adapt.h:247
o2scl::diff_evo_adapt::tau_1
double tau_1
Probability of adjusting f (default 0.1)
Definition: diff_evo_adapt.h:64
o2scl::rng_gsl::random
double random()
Return a random number in .
Definition: rng_gsl.h:82
o2scl::diff_evo_adapt::initialize_population
virtual int initialize_population(size_t nvar, vec_t &x0)
Initialize a population of random agents.
Definition: diff_evo_adapt.h:254
o2scl::diff_evo< multi_funct, boost::numeric::ublas::vector< double >, mm_funct >::pick_unique_agents
virtual std::vector< int > pick_unique_agents(int nr, size_t x)
Pick number of unique agent id's.
Definition: diff_evo.h:384
o2scl::diff_evo_adapt::tau_2
double tau_2
Probability of adjusting cr (default 0.1)
Definition: diff_evo_adapt.h:66
o2scl::multi_funct
std::function< double(size_t, const boost::numeric::ublas::vector< double > &)> multi_funct
Multi-dimensional function typedef in src/base/multi_funct.h.
Definition: multi_funct.h:45
o2scl::diff_evo< multi_funct, boost::numeric::ublas::vector< double >, mm_funct >::step
std::vector< double > step
Step size for initialization.
Definition: diff_evo.h:348
o2scl::diff_evo< multi_funct, boost::numeric::ublas::vector< double >, mm_funct >::nconv
size_t nconv
The number of generations without a better fit before we assume that the algorithm has converged (def...
Definition: diff_evo.h:96
o2scl::mmin_base< multi_funct, multi_funct, boost::numeric::ublas::vector< double > >::verbose
int verbose
Output control.
Definition: mmin.h:194
O2SCL_CONV_RET
#define O2SCL_CONV_RET(d, n, b)
Set a "convergence" error and return the error value.
Definition: err_hnd.h:297
o2scl::itos
std::string itos(int x)
Convert an integer to a string.
o2scl::mm_funct
std::function< int(size_t, const boost::numeric::ublas::vector< double > &, boost::numeric::ublas::vector< double > &) > mm_funct
Array of multi-dimensional functions typedef in src/base/mm_funct.h.
Definition: mm_funct.h:43
o2scl::diff_evo< multi_funct, boost::numeric::ublas::vector< double >, mm_funct >::rand_init_funct
mm_funct * rand_init_funct
Function that is used to produce random init variables.
Definition: diff_evo.h:342
o2scl::diff_evo< multi_funct, boost::numeric::ublas::vector< double >, mm_funct >::gr
rng_gsl gr
Random number generator.
Definition: diff_evo.h:345
o2scl::diff_evo
Multidimensional minimization by the differential evolution method.
Definition: diff_evo.h:76
o2scl::diff_evo_adapt::print_iter
virtual void print_iter(size_t nvar, double fmin, int iter, vec_t &best_fit)
Print out iteration information.
Definition: diff_evo_adapt.h:213
o2scl::diff_evo_adapt::fmins
ubvector fmins
Vector that keeps track of fmins values.
Definition: diff_evo_adapt.h:250

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