arXiv:1506.08867v1 [cs.MS] 26 Jun 2015

Java Implementation of a Parameter-less
Evolutionary Portfolio
José C. Pereira

Fernando G. Lobo

CENSE and DEEI-FCT

CENSE and DEEI-FCT

Universidade do Algarve

Universidade do Algarve

Campus de Gambelas

Campus de Gambelas

8005-139 Faro, Portugal

8005-139 Faro, Portugal

unidadeimaginaria@gmail.com

fernando.lobo@gmail.com

Abstract
The Java implementation of a portfolio of parameter-less evolutionary algorithms is presented. The Parameter-less Evolutionary Portfolio implements a heuristic that performs adaptive selection of parameter-less evolutionary algorithms in accordance with performance criteria that are measured during running time. At present time, the portfolio includes three
parameter-less evolutionary algorithms: Parameter-less Univariate Marginal Distribution Algorithm, Parameter-less Extended Compact Genetic Algorithm, and Parameter-less Hierarchical Bayesian Optimization Algorithm. Initial experiments showed that the parameter-less
portfolio can solve various classes of problems without the need for any prior parameter setting
technique and with an increase in computational effort that can be considered acceptable.

1

Introduction

The Parameter-less Evolutionary Portfolio (P-EP) implements a heuristic that performs adaptive
selection of parameter-less evolutionary algorithms (P-EAs) in accordance with performance criteria that are measured during running time. This heuristic is inspired by the parameter-less genetic
algorithm (P-GA) (Harik and Lobo, 1999) and was first proposed by Lobo and Lima (2010). We direct the interested reader to these papers for a more general and detailed description of the heuristic
itself.
The main goal of this technical report is to present a Java implementation of the Parameterless Evolutionary Portfolio (P-EPJava) whose source code is available for free download at
https://github.com/JoseCPereira/2015ParameterlessEvolutionaryPortfolioJava.
The remainder of this paper is organized as follows. In Section 2 we briefly describe the
main concept of the Parameter-less Evolutionary Portfolio. In Section 3 we discuss the P-EPJava
implementation itself and provide detailed instructions on how to use it and how to implement new
problems with it.

1

2

The Parameter-less Evolutionary Algorithm

The Parameter-less Evolutionary Portfolio always includes P-EAs that can be informally, but quantifiably, ordered by their increasing “complexity”. The more complex P-EAs should be capable of
tackling more difficult problems, usually at the expense of using an increased cost in model building. Following this order, the P-EP alternates between each algorithm on a continuous loop, giving
the same amount of CPU time to all P-EAs in each iteration. Starting with a chosen initial time, T0 ,
the allowed CPU time is updated at each loop iteration to at least match the maximum time spent
in one generation by any of the P-EAs. At the same time, because they are able to advance further
in the search due to faster model building, simpler P-EAs are eliminated from the loop as soon as
their current best average fitness is lower than the best average fitness of a more complex P-EA.
The use of parameter-less algorithms allows P-EP to work as a black-box algorithm, without
the need for any prior parameter settings. Additionally, P-EP is designed to run forever, physical
constraints aside, because in practice the quality of the optimal solution is often unknown for many
problems, making it impossible to distinguish, for instance, when an algorithm has reached the
optimum result from when it simply got “stuck” in some plateau of the search space. Therefore,
P-EP leaves to the user the decision when to stop the computation, based on the quality of the
solutions already found and on the time and resources that she or he is willing to spend.

3

A Java Implementation of the Parameter-less Evolutionary
Portfolio

At present time, the Java implementation of the Parameter-less Evolutionary Portfolio (PEPJava) includes three P-EAs: Parameter-less Univariate Marginal Distribution Algorithm
(P-UMDA)1 , Parameter-less Extended Compact Genetic Algorithm (P-ECGA) (Lobo, 2000),
and Parameter-less Hierarchical Bayesian Optimization Algorithm (P-HBOA) (Pelikan et al.,
2007). As presented in detail in another arXiv report from the same authors, these three
P-EAs (plus the P-GA) are also implemented in Java as independent algorithms. The
source and binary files of those Java implementations are available for free download at
https://github.com/JoseCPereira/2015ParameterlessEvolutionaryAlgorithmsJava.
All algorithms integrated in the evolutionary portfolio must be parameter-less in the sense that
they use the population sizing method employed by the Parameter-less Genetic Algorithm (Harik
and Lobo, 1999). In addition, each P-EA must satisfy the following two constraints in order to be
integrated in the P-EPJava:
1. The algorithm represents possible solutions (individuals) as strings of zeros and ones.
2. All individuals have the same string size.
1 See,

for example, Mühlenbein and Paaß (1996) for a description of the original, non parameter-less version of the

UMDA.

2

3.1

How to use the P-EPJava

The P-EPJava is a Java application developed with the Eclipse2 IDE. The available code is already
compiled and can be executed using the command line.
Run the P-EAJava from a command line
1. Unzip the source file 2015ParameterlessPortfolio.zip to any directory.
2. Open your favourite terminal and execute the command
cd [yourDirectory]/2015ParameterlessEvolutionaryPortfolio/bin
where [yourDirectory] is the name of the directory chosen in step 1.
3. Execute the command
java com/z PORTFOLIO/PORTFOLIO ./PortParameters.txt
The argument “PortParameters.txt” is in fact the name of the file containing all the options
concerning the portfolio settings and can be changed at will.
After each execution of a single or multiple runs, the P-EPJava produces one output file –
PORTFOLIO * *.txt – that records how each run progressed in terms of time allowed to each
algorithm, which algorithms were deactivated and when, number of fitness calls performed by
each algorithm, best individual and average fitnesses, the evolution of the population sizes, among
other relevant information. All this information is also displayed on the screen during execution
time.
At present time, the P-EPJava version made available with this paper already includes the
following set of test problems:
ZERO Problems
0→
1→
2→
3→
4→
5→
6→

ZeroMax
Zero Quadratic
Zero 3-Deceptive
Zero 3-Deceptive Bipolar
Zero 3-Deceptive Overlapping
Zero Concatenated Trap-k
Zero Uniform 6-Blocks

ONE Problems
10 →
11 →
12 →
13 →
14 →
15 →
16 →

OneMax
Quadratic
3-Deceptive
3-Deceptive Bipolar
3-Deceptive Overlapping
Concatenated Trap-k
Uniform 6-Blocks

Hierarchical Problems
21 →
22 →

Hierarchical Trap One
Hierarchical Trap Two

The Zero problems always have the string with all zeros as their best individual. The One
problems are the same as the Zero problems but their best individual is now the string with all
2 Version:

Kepler Service Release 2

3

ones. A description of these problems can be found, for instance, in Pelikan et al. (2000). The
Hierarchical problems are thoroughly described in Pelikan (2005).
It is also possible to define a noisy version for any of the previous problems. This is done by
adding a non-zero Gaussian noise term to the fitness function.
The source code that implements all the problems mentioned in this section can be found in the
file src/com/z PORTFOLIO/Problem.java.
As mentioned previously, all options concerning the evolutionary portfolio are in the file
PortParameters.txt. In particular, it is in this file that are made the choices for the problem to
be solved.
To choose a particular problem the user must set the value of the following three options:
Line 81: problemType
Line 90: stringSize
Line 107: sigmaK
(defines the noise component)
All other options are set to default values and their role in the behaviour or the portfolio
is explained with detail in the file’s comments. This is also true for the parameters specific to
the parameter-less strategy and to each of the implemented parameter-less algorithms which are
defined in four separate files:
PARAMETER-LESS: ParParameters.txt
UMDA: UMDAParameters.txt
ECGA: ECGAParameters.txt
HBOA: HBOAParameters.txt
Note that the default settings defined in these four files were chosen to ensure a robust behavior
of the corresponding algorithms, in accordance with current theory. Therefore, the user is advised
to proceed with caution when performing any changes in those settings. In fact, the whole idea behind the portfolio and the parameter-less strategy is to eliminate the need of such fine tuning when
solving a particular problem. After choosing a problem to be solved and a particular algorithm to
solve it, the user has only to press the start button and wait until the P-EPJava finds a solution with
good enough quality.

3.2

How to implement a new problem with P-EAJava

The P-EPJava uses the design pattern strategy (Gamma et al., 1995) to decouple the implementation of a particular problem from the remaining portfolio structure (see Figure 1). As a consequence, to plug in a new problem to the framework it is only necessary to define one class that
implements the interface IProblem and change some input options to include the new choice. The
interface IProblem can be found in the file src/com/z PORTFOLIO/Problem.java.
In the following let us consider that we want to solve a new problem called NewProblem with
one of the parameter-less algorithms. To plug in this problem it is necessary to:

4



  

  


  






  

   


  



Figure 1: The P-EPJava uses the design pattern strategy (Gamma et al., 1995) to allow an easy
implementation of new problems to be solved by the framework.
1. Define a class called NewProblem in the file src/com/z PORTFOLIO/Problem.java. The
signature of the class will be

2. Code the body of the function computeFitness(Individual) according to the nature of problem
newProblem. The class Individual provides all the necessary functionalities to operate with
the string of zeros and ones that represents an individual (e.g., getAllele(int)). This class can
be found in the file src/com/z PORTFOLIO/Individual.java.
3. To define the new problem option, add the line
to the switch command in line 174 of the file src/com/z PORTFOLIO/PortParameter.java.
The case number – 99 – is a mere identifier of the new problem option. The user is free to
choose other value for this purpose. The rest of the line is to be written verbatim.
4. Validate the new problem – option value 99 – by adding the case problemType == 99 to the
conditional in line 111 of the same PortParameter.java file.
Although not strictly necessary, it is also advisable to keep updated the problem menu in the
file PortParameters.txt.
5

Acknowledgements
The current version of the P-EAJava is one of the by-products of the activities performed by the
PhD fellow, José C. Pereira within the doctoral program entitled Search and Optimization with
Adaptive Selection of Evolutionary Algorithms. The work program is supported by the Portuguese
Foundation for Science and Technology with the doctoral scholarship SFRH/BD/78382/2011 and
with the research project PTDC/EEI-AUT/2844/2012.

References
Eiben, A. E. and Smith, J. E. (2003). Introduction to Evolutionary Computing. SpringerVerlag.
Gamma, E., Helm, R., Johnson, R., and Vlissides, J. (1995). Design patterns: elements of reusable
object-oriented software. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning.
Addison-Wesley, Reading, MA.
Goldberg, D. E., Deb, K., and Thierens, D. (1993). Toward a better understanding of mixing in
genetic algorithms. Journal of the Society of Instrument and Control Engineers, 32(1):10–16.
Harik, G. R. (1999). Linkage learning via probabilistic modeling in the ECGA. IlliGAL Report
No. 99010, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign,
Urbana, IL.
Harik, G. R. and Lobo, F. G. (1999). A parameter-less genetic algorithm. In Banzhaf, W. et al.,
editors, Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99,
pages 258–265, San Francisco, CA. Morgan Kaufmann.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press,
Ann Arbor, MI.
Lobo, F. G. (2000). The parameter-less genetic algorithm: Rational and automated parameter
selection for simplified genetic algorithm operation. PhD thesis, Universidade Nova de Lisboa,
Portugal. Also IlliGAL Report No. 2000030.
Lobo, F. G. and Lima, C. F. (2007). Adaptive population sizing schemes in genetic algorithms. In
Parameter Setting in Evolutionary Algorithms, pages 185–204. Springer.
Lobo, F. G. and Lima, C. F. (2010). Towards automated selection of estimation of distribution
algorithms. In Pelikan, M. and Branke, J., editors, ACM Genetic and Evolutionary Computation
Conference (GECCO-2010), Companion Material, pages 1945–1952. ACM.
Mühlenbein, H. and Paaß, G. (1996). From recombination of genes to the estimation of distributions I. Binary parameters. In Voigt, H.-M. et al., editors, Parallel Problem Solving from Nature
– PPSN IV, pages 178–187, Berlin. Kluwer Academic Publishers.

6

Pelikan, M. (2005). Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of
Evolutionary Algorithms. Springer.
Pelikan, M. and Goldberg, D. (2006). Hierarchical bayesian optimization algorithm. In Pelikan,
M., Sastry, K., and CantúPaz, E., editors, Scalable Optimization via Probabilistic Modeling,
volume 33 of Studies in Computational Intelligence, pages 63–90. Springer Berlin Heidelberg.
Pelikan, M., Goldberg, D. E., and Cantú-Paz, E. (2000). Linkage problem, distribution estimation,
and Bayesian networks. Evolutionary Computation, 8(3):311–341.
Pelikan, M., Hartmann, A., and Lin, T.-K. (2007). Parameter-less hierarchical bayesian optimization algorithm. In Parameter Setting in Evolutionary Algorithms, volume 54, pages 225–239.
Springer Berlin Heidelberg, Berlin.
Pelikan, M. and Lobo, F. G. (1999). Parameter-less genetic algorithm: A worst-case time and space
complexity analysis. IlliGAL Report No. 99014, University of Illinois at Urbana-Champaign,
Illinois Genetic Algorithms Laboratory, Urbana, IL.
Spinosa, E. and Pozo, A. (2002). Controlling the population size in genetic programming. In
Proceedings of the 16th Brazilian Symposium on Artificial Intelligence: Advances in Artificial
Intelligence, SBIA ’02, pages 345–354, London, UK, UK. Springer-Verlag.
Thierens, D. and Goldberg, D. E. (1993). Mixing in genetic algorithms. In Forrest, S., editor,
Proceedings of the Fifth International Conference on Genetic Algorithms, pages 38–45, San
Mateo, CA. Morgan Kaufmann.

7

