octave_packages/ga-0.10.0/ga.m

   1 ## Copyright (C) 2008, 2010, 2012 Luca Favatella <slackydeb@gmail.com>
   2 ##
   3 ## This program is free software; you can redistribute it and/or modify
   4 ## it under the terms of the GNU General Public License as published by
   5 ## the Free Software Foundation; either version 2 of the License, or
   6 ## (at your option) any later version.
   7 ##
   8 ## This program is distributed in the hope that it will be useful,
   9 ## but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 ## GNU General Public License for more details.
  12 ##
  13 ## You should have received a copy of the GNU General Public License
  14 ## along with this program; If not, see <http://www.gnu.org/licenses/>.
  15
  16 ## -*- texinfo -*-
  17 ## @deftypefn{Function File} {@var{x} =} ga (@var{fitnessfcn}, @var{nvars})
  18 ## @deftypefnx{Function File} {@var{x} =} ga (@var{fitnessfcn}, @var{nvars}, @var{A}, @var{b})
  19 ## @deftypefnx{Function File} {@var{x} =} ga (@var{fitnessfcn}, @var{nvars}, @var{A}, @var{b}, @var{Aeq}, @var{beq})
  20 ## @deftypefnx{Function File} {@var{x} =} ga (@var{fitnessfcn}, @var{nvars}, @var{A}, @var{b}, @var{Aeq}, @var{beq}, @var{LB}, @var{UB})
  21 ## @deftypefnx{Function File} {@var{x} =} ga (@var{fitnessfcn}, @var{nvars}, @var{A}, @var{b}, @var{Aeq}, @var{beq}, @var{LB}, @var{UB}, @var{nonlcon})
  22 ## @deftypefnx{Function File} {@var{x} =} ga (@var{fitnessfcn}, @var{nvars}, @var{A}, @var{b}, @var{Aeq}, @var{beq}, @var{LB}, @var{UB}, @var{nonlcon}, @var{options})
  23 ## @deftypefnx{Function File} {@var{x} =} ga (@var{problem})
  24 ## @deftypefnx{Function File} {[@var{x}, @var{fval}] =} ga (@dots{})
  25 ## @deftypefnx{Function File} {[@var{x}, @var{fval}, @var{exitflag}] =} ga (@dots{})
  26 ## @deftypefnx{Function File} {[@var{x}, @var{fval}, @var{exitflag}, @var{output}] =} ga (@dots{})
  27 ## @deftypefnx{Function File} {[@var{x}, @var{fval}, @var{exitflag}, @var{output}, @var{population}] =} ga (@dots{})
  28 ## @deftypefnx{Function File} {[@var{x}, @var{fval}, @var{exitflag}, @var{output}, @var{population}, @var{scores}] =} ga (@dots{})
  29 ## Find minimum of function using genetic algorithm.
  30 ##
  31 ## @strong{Inputs}
  32 ## @table @var
  33 ## @item fitnessfcn
  34 ## The objective function to minimize. It accepts a vector @var{x} of
  35 ## size 1-by-@var{nvars}, and returns a scalar evaluated at @var{x}.
  36 ## @item nvars
  37 ## The dimension (number of design variables) of @var{fitnessfcn}.
  38 ## @item options
  39 ## The structure of the optimization parameters; can be created using
  40 ## the @code{gaoptimset} function. If not specified, @code{ga} minimizes
  41 ## with the default optimization parameters.
  42 ## @item problem
  43 ## A structure containing the following fields:
  44 ## @itemize @bullet
  45 ## @item @code{fitnessfcn}
  46 ## @item @code{nvars}
  47 ## @item @code{Aineq}
  48 ## @item @code{Bineq}
  49 ## @item @code{Aeq}
  50 ## @item @code{Beq}
  51 ## @item @code{lb}
  52 ## @item @code{ub}
  53 ## @item @code{nonlcon}
  54 ## @item @code{randstate}
  55 ## @item @code{randnstate}
  56 ## @item @code{solver}
  57 ## @item @code{options}
  58 ## @end itemize
  59 ## @end table
  60 ##
  61 ## @strong{Outputs}
  62 ## @table @var
  63 ## @item x
  64 ## The local unconstrained found minimum to the objective function,
  65 ## @var{fitnessfcn}.
  66 ## @item fval
  67 ## The value of the fitness function at @var{x}.
  68 ## @end table
  69 ##
  70 ## @seealso{gaoptimset}
  71 ## @end deftypefn
  72
  73 ## Author: Luca Favatella <slackydeb@gmail.com>
  74 ## Version: 6.0.1
  75
  76 function [x fval exitflag output population scores] = \
  77       ga (fitnessfcn_or_problem,
  78           nvars,
  79           A = [], b = [],
  80           Aeq = [], beq = [],
  81           LB = [], UB = [],
  82           nonlcon = [],
  83           options = gaoptimset ())
  84   if ((nargout > 6) ||
  85       (nargin < 1) ||
  86       (nargin == 3) ||
  87       (nargin == 5) ||
  88       (nargin == 7) ||
  89       (nargin > 10))
  90     print_usage ();
  91   else
  92
  93     ## retrieve the problem structure
  94     if (nargin == 1)
  95       problem = fitnessfcn_or_problem;
  96     else
  97       problem.fitnessfcn = fitnessfcn_or_problem;
  98       problem.nvars = nvars;
  99       problem.Aineq = A;
 100       problem.Bineq = b;
 101       problem.Aeq = Aeq;
 102       problem.Beq = beq;
 103       problem.lb = LB;
 104       problem.ub = UB;
 105       problem.nonlcon = nonlcon;
 106       problem.randstate = rand ("state");
 107       problem.randnstate = randn ("state");
 108       problem.solver = "ga";
 109       problem.options = options;
 110     endif
 111
 112     ## call the function that manages the problem structure
 113     [x fval exitflag output population scores] = __ga_problem__ (problem);
 114   endif
 115 endfunction
 116
 117
 118 ## number of input arguments
 119 %!shared f, nvars
 120 %! f = @rastriginsfcn;
 121 %! nvars = 2;
 122 %!error x = ga ()
 123 %!error x = ga (f)
 124 %!error x = ga (f, nvars, [])
 125 %!error x = ga (f, nvars, [], [], [])
 126 %!error x = ga (f, nvars, [], [], [], [], [])
 127 %!error x = ga (f, nvars, [], [], [], [], [], [], @(x) [[], []], gaoptimset (), [])
 128
 129 ## number of output arguments
 130 # TODO
 131
 132 ## type of arguments
 133 %!function f = ff (nvars)
 134 %!  f = @(x) sum (x(:, 1:nvars) .** 2, 2);
 135 %!error x = ga (ff (3), 2);
 136 # TODO
 137 # TODO: test that each field in the user-specified "problem" structure is checked
 138
 139
 140 ## flawless execution with right arguments
 141 %!shared f, nvars
 142 %! f = @rastriginsfcn;
 143 %! nvars = 2;
 144 %!function [C, Ceq] = nonlcon (x)
 145 %!  C = [];
 146 %!  Ceq = [];
 147 %!test x = ga (f, nvars);
 148 %!test x = ga (f, nvars, [], []);
 149 %!test x = ga (f, nvars, ones (3, nvars), ones (3, 1));
 150 %!test x = ga (f, nvars, [], [], [], []);
 151 %!test x = ga (f, nvars, [], [], ones (4, nvars), ones (4, 1));
 152 %!test x = ga (f, nvars, [], [], [], [], [], []);
 153 %!test x = ga (f, nvars, [], [], [], [], - Inf (1, nvars), Inf (1, nvars));
 154 %!test x = ga (f, nvars, [], [], [], [], - ones (1, nvars), ones (1, nvars));
 155 %!test x = ga (f, nvars, [], [], [], [], [], [], @(x) [[], []]);
 156 %!test x = ga (f, nvars, [], [], [], [], [], [], @nonlcon);
 157 %!test x = ga (f, nvars, [], [], [], [], [], [], @(x) [[], []], gaoptimset ());
 158 %!test # TODO: convert to error after implementing private ga-specific createOptimProblem. All fields in the user-specified structure should be checked
 159 %! problem = struct ("fitnessfcn", @rastriginsfcn,
 160 %!                   "nvars", 2,
 161 %!                   "options", gaoptimset ());
 162 %! x = ga (problem);
 163
 164 ## flawless execution with any nvars
 165 %!function f = ff (nvars)
 166 %!  f = @(x) sum (x(:, 1:nvars) .** 2, 2);
 167 %!test
 168 %! nvars = 1;
 169 %! x = ga (ff (nvars), nvars);
 170 %!test
 171 %! nvars = 2;
 172 %! x = ga (ff (nvars), nvars);
 173 %!test
 174 %! nvars = 3;
 175 %! x = ga (ff (nvars), nvars);
 176
 177 ## flawless execution with any supported optimization parameter
 178 ## different from the default value
 179 %!shared f, nvars, default_options
 180 %! f = @rastriginsfcn;
 181 %! nvars = 2;
 182 %! default_options = gaoptimset ();
 183 %!function [C, Ceq] = nonlcon (x)
 184 %!  C = [];
 185 %!  Ceq = [];
 186 %!test
 187 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, default_options);
 188 %!test # TODO: use non-default value
 189 %! options = gaoptimset ("CreationFcn", @gacreationuniform);
 190 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 191 %!test # TODO: use non-default value
 192 %! options = gaoptimset ("CrossoverFcn", @crossoverscattered);
 193 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 194 %!test
 195 %! options = gaoptimset ("CrossoverFraction", rand);
 196 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 197 %!test
 198 %! ps = getfield (default_options, "PopulationSize");
 199 %! options = gaoptimset ("EliteCount", randi ([0, ps]));
 200 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 201 %!test
 202 %! options = gaoptimset ("FitnessLimit", 1e-7);
 203 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 204 %!test # TODO: use non-default value
 205 %! options = gaoptimset ("FitnessScalingFcn", @fitscalingrank);
 206 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 207 %!test
 208 %! g = getfield (default_options, "Generations");
 209 %! options = gaoptimset ("Generations", g + 1);
 210 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 211 %!test
 212 %! ps = getfield (default_options, "PopulationSize");
 213 %! ## Initial population can be partial
 214 %! options_w_full_ip = \
 215 %!     gaoptimset ("InitialPopulation", rand (ps,         nvars));
 216 %! partial_ip = randi ([0, ps - 1]);
 217 %! options_w_partial_ip = \
 218 %!     gaoptimset ("InitialPopulation", rand (partial_ip, nvars));
 219 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options_w_full_ip);
 220 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options_w_partial_ip);
 221 %!test
 222 %! ps = getfield (default_options, "PopulationSize");
 223 %! ## Initial scores needs initial population
 224 %!
 225 %! options_w_full_ip_full_is = \
 226 %!     gaoptimset ("InitialPopulation", rand (ps, nvars),
 227 %!                 "InitialScores",     rand (ps, 1    ));
 228 %! partial_ip = randi ([2, ps - 1]);
 229 %! options_w_partial_ip_full_is = \
 230 %!     gaoptimset ("InitialPopulation", rand (partial_ip, nvars),
 231 %!                 "InitialScores",     rand (partial_ip, 1    ));
 232 %!
 233 %! ## Initial scores can be partial
 234 %! partial_is_when_full_ip    = randi ([1, ps         - 1]);
 235 %! partial_is_when_partial_ip = randi ([1, partial_ip - 1]);
 236 %! options_w_full_ip_partial_is = \
 237 %!     gaoptimset ("InitialPopulation", rand (ps,                      nvars),
 238 %!                 "InitialScores",     rand (partial_is_when_full_ip, 1    ));
 239 %! options_w_partial_ip_partial_is = \
 240 %!     gaoptimset ("InitialPopulation", rand (partial_ip,                 nvars),
 241 %!                 "InitialScores",     rand (partial_is_when_partial_ip, 1    ));
 242 %!
 243 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon,
 244 %!         options_w_full_ip_full_is);
 245 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon,
 246 %!         options_w_partial_ip_full_is);
 247 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon,
 248 %!         options_w_full_ip_partial_is);
 249 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon,
 250 %!         options_w_partial_ip_partial_is);
 251 %!test # TODO: use non-default value
 252 %! options = gaoptimset ("MutationFcn", {@mutationgaussian, 1, 1});
 253 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 254 %!test
 255 %! options = gaoptimset ("PopInitRange", [-2; 2]);
 256 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 257 %!test
 258 %! options = gaoptimset ("PopulationSize", 200);
 259 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 260 %!test # TODO: use non-default value
 261 %! options = gaoptimset ("SelectionFcn", @selectionstochunif);
 262 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 263 %!test # TODO: use non-default value
 264 %! options = gaoptimset ("TimeLimit", Inf);
 265 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 266 %!error # TODO: this should become test
 267 %! options = gaoptimset ("UseParallel", "always");
 268 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 269 %!test
 270 %! options = gaoptimset ("Vectorized", "on");
 271 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 272
 273
 274 ## error with conflicting optimization parameters: population size et al.
 275 %!shared f, nvars
 276 %! f = @rastriginsfcn;
 277 %! nvars = 2;
 278 %!function [C, Ceq] = nonlcon (x)
 279 %!  C = [];
 280 %!  Ceq = [];
 281 %!error # Elite count cannot be greater than the population size
 282 %! ps = 3;
 283 %! bad_options = gaoptimset ("PopulationSize", ps,
 284 %!                           "EliteCount",     ps + 1);
 285 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);
 286 %!error # The number of individuals in the initial population cannot be greater of the population size
 287 %! ps = 3;
 288 %! bad_options = gaoptimset ("PopulationSize",    ps,
 289 %!                           "InitialPopulation", zeros (ps + 1, nvars));
 290 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);
 291 %!error # Initial scores cannot be specified without specifying the initial population too
 292 %! bad_options = gaoptimset ("InitialScores", zeros (3, 1));
 293 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);
 294 %!error # The number of initial scores specified cannot be greater of the number of individuals in the initial population
 295 %! ip = 3;
 296 %! bad_options = gaoptimset ("InitialPopulation", zeros (ip, nvars),
 297 %!                           "InitialScores",     zeros (ip + 1, 1));
 298 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);
 299
 300 ## error with vectorized evaluation of objective function. Vectorized
 301 ## objective functions are better because can be evaluated both as
 302 ## serial and vectorized.
 303 %!shared nvars
 304 %! nvars = 2;
 305 %!function [C, Ceq] = nonlcon (x)
 306 %!  C = [];
 307 %!  Ceq = [];
 308 %!function f = ff (nvars)
 309 %!  f = @(x) sum (x(:, 1:nvars) .** 2, 2);
 310 %!function f_not_vectorized = ff_not_vectorized (nvars)
 311 %!  f_not_vectorized = @(x) sum (x(1:nvars) .** 2);
 312 %!test # A non-vectorized objective function works when no vectorization is required
 313 %! f = ff_not_vectorized (nvars);
 314 %! options = gaoptimset ("Vectorized", "off");
 315 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 316 %!error # A non-vectorized objective function does not work when vectorization is required
 317 %! f = ff_not_vectorized (nvars);
 318 %! options = gaoptimset ("Vectorized", "on");
 319 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 320 %!test # A vectorized objective function works when no vectorization is required
 321 %! f = ff (nvars);
 322 %! options = gaoptimset ("Vectorized", "off");
 323 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 324 %!test # A vectorized objective function works when vectorization is required
 325 %! f = ff (nvars);
 326 %! options = gaoptimset ("Vectorized", "on");
 327 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 328
 329 ## error with conflicting optimization parameters: parallel and
 330 ## vectorized evaluation of objective function
 331 %!shared f, nvars
 332 %! f = @rastriginsfcn;
 333 %! nvars = 2;
 334 %!function [C, Ceq] = nonlcon (x)
 335 %!  C = [];
 336 %!  Ceq = [];
 337 %!test
 338 %! options = gaoptimset ("UseParallel", "never",
 339 %!                       "Vectorized",  "off");
 340 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 341 %!error # TODO: this should become test
 342 %! options = gaoptimset ("UseParallel", "always",
 343 %!                       "Vectorized",  "off");
 344 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 345 %!error
 346 %! bad_options = gaoptimset ("UseParallel", "garbage",
 347 %!                           "Vectorized",  "off");
 348 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);
 349 %!test
 350 %! options = gaoptimset ("UseParallel", "never",
 351 %!                       "Vectorized",  "on");
 352 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, options);
 353 %!warning
 354 %! bad_options = gaoptimset ("UseParallel", "always",
 355 %!                           "Vectorized",  "on");
 356 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);
 357 %!warning
 358 %! bad_options = gaoptimset ("UseParallel", "garbage",
 359 %!                           "Vectorized",  "on");
 360 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);
 361 %!error
 362 %! bad_options = gaoptimset ("UseParallel", "never",
 363 %!                           "Vectorized",  "garbage");
 364 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);
 365 %!error
 366 %! bad_options = gaoptimset ("UseParallel", "always",
 367 %!                           "Vectorized",  "garbage");
 368 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);
 369 %!error
 370 %! bad_options = gaoptimset ("UseParallel", "garbage",
 371 %!                           "Vectorized",  "garbage");
 372 %! x = ga (f, nvars, [], [], [], [], [], [], @nonlcon, bad_options);