Fresa: A Plant Propagation Algorithm for Black-Box Single and Multiple Objective Optimization
Eric S Fraga*
Sargent Centre for Process Systems Engineering, Department of Chemical Engineering, University College London
*Corresponding author: Eric S Fraga, Sargent Centre for Process Systems Engineering, Department of Chemical Engineering, University College London (UCL).
Article History
Received: August 27, 2021 Accepted: September 09, 2021 Published: September 22, 2021
Citation: Fraga ES. Fresa: A Plant Propagation Algorithm for Black-Box Single and Multiple Objective Optimization. Int J Eng Tech & Inf. 2021;2(4):110‒111. DOI: 10.51626/ijeti.2021.02.00022
Abstract
Fresa implements a nature inspired plant propagation algorithm for the solution of single and multiple objective optimization problems. The method is population based and evolutionary. Treating the objective function as a black box, the implementation is able to solve problems exhibiting behaviour that is challenging for mathematical programming methods. Fresa is easily adapted to new problems which may benefit from bespoke representations of solutions by taking advantage of the dynamic typing and multiple dispatch capabilities of the Julia language. Further, the support for threads in Julia enables an efficient implementation on multi-core computers.
Keywords: Optimization; Multi-objective Optimization; Nonlinear Optimization; Non-convex Optimization; Engineering Design.
Optimization & Design
There are a number of different ways optimization methods can be categorized: mathematical programming versus direct search and deterministic versus stochastic being two examples of characterisations that may be used. Mathematical programming methods typically require the model to be represented by a set of equations, equations that could be algebraic or differential, and make use of derivatives to guide a search to an optimum. Direct search methods, otherwise known as zeroth-order methods, on the other hand, require only the objective function value itself, with possibly an indication of the feasibility of a given solution. Mathematical programming methods are usually deterministic whereas direct search methods may be deterministic [1] or stochastic, such as genetic algorithms [2], simulated annealing [3], and particle swarm optimization [4], to mention only a few.
Direct search methods, and especially those based on stochastic searches, are often necessary due to the properties of the optimization problem. Problems with discontinuities, for instance, are challenging to handle robustly, if at all, using mathematical programming approaches. Properties such as nonlinear and non-convex behaviour, in either or both of the objective functions or the search space, also challenge many solution methods as do problems with models based on ordinary differential equations, partial differential equations, or integral equations. In engineering, models may also exhibit noise. Noise can arise when the objective function is based on data from experiments but noise may also arise when the objective function requires the numerical solution of embedded differential equations, for instance. Noise in the values of the objective function creates difficulties in using derivative information for guiding the search and will, in the best case, lead to sub-optimal results.
In engineering design, many problems are inherently multi-criteria. Each design will be assessed with techno-economic, environmental, operability, and other criteria. Multiobjective optimization is therefore a desirable feature of an optimization solver. Such problems can and are frequently solved using single objective methods in a variety of ways, including the specification of a suitably modified single objective problem by combining the different criteria into a single objective through the use of weights, known as scalarization [5]. Alternatively, one criterion can be used as the objective for the optimization method with other objectives incorporated into the constraints, with an ε parameter to adjust the limit on each other objective [6]. These approaches require multiple solutions with different weights or different constraints. Multiobjective methods consider all objectives simultaneously without a priori weights or special constraints and will typically generate a trade-off set of Pareto optimal solutions as the outcome. Such methods can be potentially computationally more efficient by avoiding repeated searches.
Features of Fresa
Fresa is an example of a stochastic direct search method. Specifically, it implements a population based evolutionary procedure inspired by the propagation of plants in nature. New solutions in the search space are generated, using random numbers, by generating neighbour solutions via a methodology inspired by the propagation of runners by Straw- berry plants [7]. Solutions are selected for propagation based on their fitness. The fitness is generally a function of the values of the objective functions. The number of runners and their distance for propagation are functions of the fitness as well. Fresa supports both single and multi-objective optimization.
An advantage of the underlying algorithm is that it has few user-tunable parameters. These include the population size, the number of cycles or generations to perform, the maximum number of runners to generate, and the choice of and parameters for the fitness method used. The results obtained by this algorithm have been shown to be relatively
insensitive to the values of these parameters [8]. For multi-objective optimization, several methods are available for the assignment of fitness values to individual solutions in the population. One of these is the non-dominated sorting algorithm, exemplified by the popular NSGA-II genetic algorithm implementation [9]. In Fresa, an alternative method is the assignment of fitness values based on the Hadamard product of the rankings with respect to the individual criteria [10]. A variation on this latter method is an alternative based on the Borda sum of those individual rankings. These latter two fitness assignment methods tend to emphasise solutions found towards the ends of the Pareto frontier whereas the non-dominated sorting algorithm may lead to the ends of the frontier having less representation in the population [11,12]. The advantage of the Hadamard and Borda based fitness assignment methods is that they scale linearly with both the population size and the number of objectives whereas a non-dominance sorting approach scales as O(nq )p with 2 < q 3.
The type agnostic nature of Fresa, for both the space of solutions and their objective function values, allows for heterogeneous populations. In such populations, individuals may use different representations of potential solutions for the problem [13]. This is achieved by the combination of dynamic typing and multiple dispatch provided by the Julia language.
Fresa is in the Julia General Registry1 and so installation is straightforward, with no dependencies beyond a small number of standard Julia packages. The software is open source and available directly from github.com [14].
References
- Kelley CT (1999) Iterative methods for optimization. SIAM.
- Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning.
- Laarhoven P J V, Aarto E H (1987) Simulated annealing: Theory and applications. Kluwer Academic Publishers Dordrecht.
- Kennedy J, Eberhart R (1995) Particle swarm optimization. Proceedings of ICNN’95 – International Conference on Neural Networks 4: 1942-1948.
- Steuer R E (1985) Multiple criteria optimization: theory, computation, and applica- tion. Wiley New York.
- Mavrotas G (2009) Effective implementation of the ε-constraint method in Multi- Objective Mathematical Programming problems. Applied Mathematics and Compu tation 213(2): 455-465.
- Salhi A, Fraga ES (2011) Nature-inspired optimisation approaches and the new plant propagation algorithm. Proceedings of Icemath The International Conference on Numerical Analysis and Optimization K2:1-8.
- Jonge M d, Berg D V D (2020) Plant Propagation Parameterization: Offspring & Population Size.
- Deb K (2000) An efficient constraint handling method for genetic algorithms. Comput Methods Appl Mech Engng186(2-4): 311-338.
- Fraga ES, Amusat O (2016) Understanding the impact of constraints: a rank based fitness function for evolutionary methods. 243-254.
- Pardalos P, Zhigljavsky A, Zilinskas J (2016) Advances in Stochastic and Deterministic Global Optimization.
- Evostar (2020)The Leading European Event on Bio- Inspired Computation.
- a. Fraga ES (2021) Multiple simultaneous solution representations in a population based evolutionary algorithm.
- b. Fraga ES (2021b) ericsfraga/Fresa.jl: First public release.
