CSMOn
Convergence Stabilization Modeling operating in Online mode
CSMOn.cpp
1 /*
2  * Copyright (c) 2017, Peter Frank Perroni (pfperroni@gmail.com)
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to deal
6  * in the Software without restriction, including without limitation the rights
7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  * copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * Additionally, if used for any scientific purpose, the following reference
15  * must be cited:
16  *
17  * Peter Frank Perroni, Daniel Weingaertner, and Myriam Regattieri Delgado.
18  * 2017. Estimating Stop Conditions of Swarm Based Stochastic Metaheuristic
19  * Algorithms. In Proceedings of GECCO '17, Berlin, Germany, July 15-19, 2017,
20  * pg 43-50. DOI: http://dx.doi.org/10.1145/3071178.3071326
21  *
22  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
25  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
28  * THE SOFTWARE.
29  */
30 
31 #include "CSMOn.hpp"
32 
43 CSMOn::CSMOn(ISearch *search, int M, double R, double minEstimatedFit) {
44  this->search = search;
45  this->M = M;
46  this->minEstimatedFit = minEstimatedFit;
47  if(R < 0){
48  autoRelaxation = true;
49  this->R = abs(R);
50  }
51  else{
52  autoRelaxation = false;
53  this->R = R;
54  }
55 
56  search->startup();
57 
58  s = -1;
59 }
60 
61 CSMOn::~CSMOn() {}
62 
63 ISearch::~ISearch() {}
64 
68 void CSMOn::run() {
69  int pT = -1, pS = -1;
70  double r = (autoRelaxation ? 0.99 : R);
71  getBest(1);
72  do{
73  r = (autoRelaxation ? max(r*r, R) : r);
74  if(pS == -1)
75  pT = adjustExp(r);
76  if(pT > 0)
77  pS = adjustLog(r, pT);
78  }while(getNEvals() < M && (r > R || pS == -1));
79 }
80 
81 int CSMOn::adjustExp(double r) {
82  int sPrev = s;
83  getBest(2);
84  if(s-sPrev < 2) return -1;
85  int pB = -1;
86  double alpha1, alpha2;
87  while(getNEvals() < M){
88  if(decayE() < r && decayL() < r){
89  if(pB == -1){
90  pB = s-2;
91  alpha2 = alphaE(pB, s);
92  }
93  else{
94  alpha1 = alpha2;
95  alpha2 = alphaE(pB, s);
96  if(alpha2 < alpha1) return s;
97  }
98  }
99  else pB = -1;
100  getBest(1);
101  }
102  return -1;
103 }
104 
105 int CSMOn::adjustLog(double r, int pT) {
106  int sPrev = s;
107  getBest(3);
108  if(s-sPrev < 3) return -1;
109  double alpha1 = alphaP(pT, s-1);
110  double alpha2 = alphaP(pT, s);
111  while(alpha2 >= alpha1 && getNEvals() < M){
112  if(decayE() >= r || decayL() >= r) return -1;
113  getBest(1);
114  alpha1 = alpha2;
115  alpha2 = alphaP(pT, s);
116  }
117  return s;
118 }
119 
120 void CSMOn::getBest(int nBest) {
121  for(int i=0; i < nBest && search->getNEvals() < M; i++){
122  search->next(M);
123  gb.push_back(t_point(search->getNEvals(), search->getFitness()));
124  s++;
125  }
126 }
127 
128 double CSMOn::decayE() {
129  return fabs(1 - (gb[s].y-minEstimatedFit) / (gb[s-1].y-minEstimatedFit));
130 }
131 
132 double CSMOn::decayL() {
133  return fabs(1 - (gb[s].y-gb[s-1].y) / (gb[s-1].y-gb[s-2].y));
134 }
135 
136 double CSMOn::alphaE(int p1, int p2) {
137  int i, n = p2 - p1 + 1;
138  double yAvg = 0, yAvgLn, ySumLn = 0, xSum = 0, xAvg, S1 = 0, S2 = 0, aux;
139  for(i=p1; i <= p2; i++){
140  xSum += gb[i].x;
141  yAvg += gb[i].y;
142  ySumLn += log(gb[i].y);
143  }
144  xAvg = xSum / n;
145  yAvg /= n;
146  yAvgLn = ySumLn / n;
147  for(i=p1; i <= p2; i++){
148  aux = (gb[i].x - xAvg);
149  S1 += aux * (gb[i].y - yAvgLn);
150  S2 += aux * aux;
151  }
152  return (ySumLn - (S1 / S2) * xSum) / n;
153 }
154 
155 double CSMOn::alphaP(int p1, int p2) {
156  int i, n = p2 - p1 + 1;
157  double yAvgLog, ySumLog = 0, xAvgLog, xSumLog = 0, S1 = 0, S2 = 0, aux;
158  for(i=p1; i <= p2; i++){
159  xSumLog += log10(gb[i].x);
160  ySumLog += log10(gb[i].y);
161  }
162  xAvgLog = xSumLog / n;
163  yAvgLog = ySumLog / n;
164  for(i=p1; i <= p2; i++){
165  aux = (log10(gb[i].x) - xAvgLog);
166  S1 += aux * (log10(gb[i].y) - yAvgLog);
167  S2 += aux * aux;
168  }
169  return (ySumLog - (S1 / S2) * xSumLog) / n;
170 }
171 
179  return search->getFitness();
180 }
181 
189  return search->getNEvals();
190 }
191 
198 int CSMOn::getBestPos(double *x) {
199  return search->getBestPos(x);
200 }
CSMOn(ISearch *search, int M, double R, double minEstimatedFit)
Class for CSMOn.
Definition: CSMOn.cpp:43
A point representing the number of evaluations and the respective fitness value.
Definition: CSMOn.hpp:61
virtual void startup()=0
Startup the search method.
The interface that the search methods must to implement.
Definition: ISearch.hpp:40
int getBestPos(double *x)
Get the final optimized result (position).
Definition: CSMOn.cpp:198
virtual double getFitness()=0
Get the best fitness value found up to the moment.
void run()
Call this method to execute the search.
Definition: CSMOn.cpp:68
virtual void next(int M)=0
Obtain the next improvement.
virtual int getNEvals()=0
Get the number of fitness function evaluations performed up to the moment.
double getFitness()
Get the final fitness value.
Definition: CSMOn.cpp:178
void search(char *method, Param *inParam, Param *outParam, double *outPos, callback_t fitnessFunction)
The wrapper function for Python calls.
virtual int getBestPos(double *_x)=0
Get the best result obtained up to the moment.
int getNEvals()
Get the actual number of evaluations executed.
Definition: CSMOn.cpp:188