A.- EnGA library
A.1 - Overview
The genetic algorithm proposed in this work, EnGA, has been also implemented as a general-purpose C++ library for global optimization. While the parallel structure which relies on elitism and tournament-based selection is maintained, reproduction and evaluation methods must be defined by the user according to his/her particular problem. Two operating modes are available featuring static and dynamic load-balancing, respectively. Besides, as OpenMP has been used for threading, it can be compiled either as a sequential or parallel code depending on final requirements. In this appendix, a general overview of its structure and use is given. The tool can be downloaded from http://gitlab.hpca.ual.es/ncc911/EnGA.
A.2 - Structure
The source code is divided into four core files. Next, they are commented in logical order. For the sake of simplicity, the complete signature of functions is not included. In any case, their names and code are quite descriptive and there should be no problem in understanding their purpose and usage:
-
EnGABase.h: Template class with the common methods that will be used either by the static or dynamic load-balancing version, which inherits from it. This class, whose constructor is protected, cannot be directly used. Its methods are summarized next:
- getMemory: It reserves the required memory by the whole optimization process, i.e., arrays for the population and its descendants as well as an array for the individuals selected for any next population (which is iteratively swapped with the initial one containing the population).
- selectProgenitors: It selects two progenitors, out of tournament selection, that will be ultimately used to generate two descendants.
- replace: It forms the population for the next cycle. First, the requested number of elite solutions is copied, either from the population or descendants set, to the new population. After that, the remaining individuals to keep the population size constant are selected (tournament selection is applied again). Finally, the pointers of the base population and the new one are swapped. A ticket system is applied to avoid repeated selections: once an individual has been selected, its ticket is removed.
- pickElite: Auxiliary function launched from the replace method. It iteratively selects the best candidate solution available considering both the existing population and the descendant set. Its ticket is removed once selected.
- findBestInSets: Auxiliary function launched from pickElite. It ultimately looks for the best existing candidate solution among the population sets.
- swap: It effectively swaps the pointers linked to the current and new populations.
- freeMemory: All memory initially reserved is finally freed.
Besides, an external helper function, `computeThreadLoad', is also included. It is applied by the static version and is of interest if external knowledge-input is added to the population.
-
StaticEnGA.h: This template class, which inherits from EnGABase, implements the specific parts of the optimizer aimed at a manual static load-balancing. All OpenMP sentences are correspondingly adapted to this nature. The user interested in launching a static load-balanced parallel process should instantiate and link this class to its candidate solution. Its methods are:
- optimize: It is the only public method that can be used from any instance of this class. The whole optimization procedure is launched and the best result achieved is finally returned. All parameters regarding optimization are assigned here, e.g., population size and number of cycles. The remaining methods are private.
- initialitePopulation: It launches the creation and evaluation of the static part of the initial population linked to a certain thread.
- pairAndReproduce: It forms as many pairs as required and their descendants are generated. Every thread would return the best descendant that it found its working chunk in order to update, if necessary, the best solution achieved so far (which, of course, require mutual exclusion).
- mutate: Mutation has a certain probability to be executed on any new descendant. Every thread is still kept in its operational ranges. An internal mutation probability is passed to the individual in case it is vector-based and requires an extra control parameter (it could be ignored otherwise).
-
DynamicEnGA.h: This template class, which also inherits from EnGABase, is equivalent to the StaticEnGA one in both design (methods) and usage. However, its internal implementation relies on dynamic load-balancing. Hence, its methods will not be listed again.
-
EnGAProblemContext.h: It defines an empty class which can be derived to pass additional and constant information required by the objective function, e.g., the bounds of the search-space or the size of heliostats for the problem presented in this work.
Finally, it must be highlighted that every thread creates its own local random number generator when it is started. The object-oriented MersenneTwister generator implemented by Stephan Brumme (
http://create.stephan-brumme.com/mersenne-twister/) has been used. Our gratitude to him for sharing his work is hereby expressed.
A.3 - Usage
Applying the previous tool to solve any optimization problem only requires the design of a class to be used as candidate solution. Due to its template-based design, the tool is ultimately adapted to the target problem at compilation time. A candidate solution class is responsible for controlling from random initialization to reproduction and mutation according to the target problem. Its requirements are listed next:
- Default constructor: A default constructor must be explicitly included. It is expected to assign any new individual the worst possible value depending on the problem, i.e., -∞ to ∞ for maximization and minimization, respectively.
- randomSolution: It should assign an adequate random value to a certain candidate solution (which must include the evaluation of its aptitude).
- reproduce: It should define the way in which two descendants are generated out of two progenitors. The real aptitude of every descendant must be included.
- mutate: It is in charge of altering (or, at least, attempting it) a certain descendant and updating its aptitude if necessary.
- isBetterThan: It defines the criterion of comparison between two candidate solutions.
- setValue & getValue: These methods are required only by the dynamic load-balancing version. They are simply the getter and setter methods linked to the aptitude attribute of any candidate solution.
It is also important to mention that if the created class uses instance-linked dynamic memory, appropriate copy and assignment operators should be also provided. Besides, as a class, it can include any other code required by the user. Finally, in file
Tester.cpp, a usage example is shown. It relies on the files
SampleProblem.h/cpp, which are a direct sample of the type of class that any user should write and contains useful comments. Specifically, the target optimization problem consists in obtaining the global minimum of function f(x) = (x + 47)
2 + 8.
A.4 - License
This software has been developed by N.C. Cruz, S. Salhi, J.L. Redondo, J.D. Álvarez, M. Berenguel and P.M. Ortigosa. It is distributed `as is', with the best intentions, but without any kind of warranty and/or responsibility of the authors. It can be freely used, modified and distributed by anyone interested at but it is compulsory to reference the original version included herein.