# A Plant Propagation Algorithm for Constrained Engineering Optimisation Problems

Authors: Muhammad Sulaiman; Abdellah Salhi; Birsen Irem Selamoglu; Omar Bahaaldin Kirikchi
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Optimisation problems arising in industry are some of the hardest, often because of the tight specifications of the products involved. They are almost invariably constrained and they involve highly nonlinear, and non-convex functions both in the objective and in the constraints. It is also often the case that the solutions required must be of high quality and obtained in realistic times. Although there are already a number of well performing optimisation algorithms for such problems, here we consider the novel Plant Propagation Algorithm (PPA) which on continuous problems seems to be very competitive. It is presented in a modified form to handle a selection of problems of interest. Comparative results obtained with PPA and state-of-the-art optimisation algorithms of the Nature-inspired type are presented and discussed. On this selection of problems, PPA is found to be as good as and in some cases superior to these algorithms.


---

## Body

## 1. Introduction

Optimisation problems in design engineering are often highly nonlinear, constrained and involving continuous as well as discrete variables [1–5]. It is also often the case that some of the constraints are active at the global optimum [6]. This means that feasible approximate solutions are that much harder to find. There is a variety of algorithms for these problems, some exact, and others approximate. In the exact category, one can name Branch-and-Bound, [7], Recursive Quadratic Programming, [8], the Cutting Plane Algorithm [9], Bender’s decomposition [10]. Of the approximate variety, one can name Simulated Annealing, [11–13], the Genetic Algorithm [14–16], and the Particle Swarm Optimisation algorithm, [17, 18], to name a few. The latter category is often referred to as the metaheuristic algorithms. In general, they are characterised by two aspects of the search: exploration of the overall search space and exploitation of good areas in order to find local optima, [19–22].A new metaheuristic, the Plant Propagation Algorithm (PPA), has recently been introduced [23]. PPA is nature inspired [19, 23, 24]; it emulates the way plants, in particular the strawberry plant, propagate. A basic PPA has been described and tested on single objective as well as multiobjective continuous optimization problems in [23]. The test problems, though standard, were of low dimension. The results showed that PPA has merits and deserves further investigation on higher dimensional problem instances as well as problems arising in practice, for these are often very challenging. PPA is attractive because, among other things, it is simple to describe and implement; it also involves only few parameters that need arbitrary setting unlike most other metaheuristics. Here, it will be tested on constrained optimisation problems arising in engineering. The paper is organised as follows. Section 2 describes PPA. Section 3 presents a modified version to handle constrained problems. Section 4 records the results obtained with PPA and a number of other heuristics. In Section 5 a conclusion and ideas for further investigation are given. The paper includes appendices that describe the problems considered.


## 2. The Strawberry Algorithm as PPA

The Strawberry algorithm is an exemplar PPA which can be seen as a multipath following algorithm unlike Simulated Annealing (SA) [13, 25], for instance, which is a single path following algorithm. It can, therefore, be perceived as a generalisation of SA and other path-following algorithms [26].Exploration and exploitation are properties that effective global optimisation algorithms have [19, 24, 26]. Exploration refers to the property of covering the search space, while exploitation refers to the property of searching nearer to good solutions for local optima.Consider what a strawberry plant and possibly any plant which propagates through runners will do to optimize its survival. If it is in a good spot of the ground, with enough water, nutrients, and light, then it is reasonable to assume that there is no pressure on it to leave that spot to guarantee its survival. So, it will send many short runners that will give new strawberry plants and occupy the neighbourhood as best they can. If, on the other hand, the mother plant is in a spot that is poor in water, nutrients, light, or any one of these necessary for a plant to survive, then it will try to find a better spot for its offspring. Therefore, it will send few runners further afield to explore distant neighbourhoods. One can also assume that it will send only a few, since sending a long runner is a big investment for a plant which is in a poor spot. We may further assume that the quality of the spot (abundance of nutrients, water, and light) is reflected in the growth of the plant. With this in mind and the following notation, PPA can be described as follows.A plantpi is in spot Xi in dimension n. This means Xi={xi,j,forj=1,…,n}. Let NP be the number of strawberry plants to be used initially, and the PPA algorithm described in pseudo-code Algorithm 1, relies on the following strategy [23].(i)
Strawberry plants which are in good spots propagate by generating many short runners.(ii)
Those in poor spots propagate by generating few long runners.Algorithm 1:Pseudocode of PPA, [23].
(1) Initialization: Generate a populationP={Xi,i=1,…,NP};
(2)g←1;
(3)for  g=1: gmax⁡  do
(4)  ComputeNi=f(Xi),∀Xi∈P;
(5)  SortP in ascending order of N (for minimization);
(6)  Create new populationΦ;
(7)for each Xi,i=1,…,NP  do
(8)αi← set of runners where both the size of the set and the distance for each runner (individually)
are proportional to Ni, the normalized objective value
(9)Φ←Φ∪αi  {append to population};
(10)end for
(11)P←Φ  {new population};
(12)end for
(13)Return  P, the population of solutions.It is clear that, in the above description, exploitation is implemented by sending many short runners by plants in good spots, while exploration is implemented by sending few long runners by plants in poor spots.The parameters used in PPA are the population sizeNP which is the number of strawberry plants, the maximum number of generations gmax⁡, and the maximum number of possible runners nmax⁡ per plant. gmax⁡ is effectively the stopping criterion in this initial version of PPA. The algorithm uses the objective function value at different plant positions Xi, i=1,…,NP, in a normalised form Ni, to rank them as would a fitness function in a standard genetic algorithm (note that, unlike in the GA, individuals in PPA are clones of the mother plant; they do not improve from generation to generation). The number of plant runners nαi, calculated according to (1) below, has length dxi calculated using the normalised form of the objective value at Xi, each giving a dxi∈(-1,1)n, as calculated with (2) below. After all individuals/plants in the population have sent out their allocated runners, new plants are evaluated and the whole increased population is sorted. To keep the population constant, individuals with lower growth are eliminated. The number of runners allocated to a given plant is proportional to its fitness as in
(1)nαi=⌈nmax⁡Niα⌉,α∈(0,1).
Every solution Xi generates at least one runner and the length of each such runner is inversely proportional to its growth as in (2) below:
(2)dxji=2(1-Ni)(α-0.5),forj=1,…,n,
where n is the problem dimension. Having calculated dxi, the extent to which the runner will reach, the search equation that finds the next neighbourhood to explore is
(3)yi,j=xi,j+(bj-aj)dxji,forj=1,…,n.If the bounds of the search domain are violated, the point is adjusted to be within the domain[aj,bj], where aj and bj are lower and upper bounds delimiting the search space for the jth coordinate.


## 3. An Effective Implementation of PPA for Constrained Optimization

In this implementation of PPA, the initial population is crucial; we run the algorithm a number of times from randomly generated populations. The best individual from each run forms a member of the initial population. The number of runs to generate the initial population isNP; therefore, the population size is r=NP. In the case of mixed integer problems, the integer variable values are fixed when they are showing a trend to converge to some values. This trend is monitored by calculating the number of times their values have not changed. When this number is greater than a certain threshold, the variables are fixed for the rest of the run. This strategy seems to work on the problems considered. Let pop be a general matrix containing the population of a given run. Its rows correspond to individuals. The following equation is used to generate a random population for each of the initial runs:
(4)xi,j=aj+(bj-aj)α,j=1,…,n,
where xi,j∈[aj,bj] is the jth entry of solution Xi and aj and bj are the jth entries of the lower and upper bounds describing the search space of the problem and α∈(0,1).In the main body of the algorithm, before updating the population we create a temporary populationΦ to hold new solutions generated from each individual in the population. Then we implement three rules with fixed modification parameter Pm, chosen here, as Pm=0.8. The first two rules are implemented if the population is initialized randomly. Rule 01 uses the following equation to update the population:
(5)xi,j*=xi,j(1+β),j=1,…,n,
where β∈[-1,1] and xi,j*∈[aj,bj].The generated individualXi* is evaluated according to the objective function and is stored in Φ. In rule 02 another individual is created with the same modification parameter Pm=0.8 as in the following equation:
(6)xi,j*=xi,j+(xl,j-xk,j)β,j=1,…,n,
where β∈[-1,1], xi,j*∈[aj,bj]. l, k are mutually exclusive indices and are different from i.The generated individualXi* is evaluated according to the objective function and is stored in Φ. The first two rules are applicable for r≤NP the number of runs. For r>NP the algorithm also tries to recognise entries which are settling to their final values through a counter IN. If the jth entry in current population has a low IN value, then it is modified by implementing (7); otherwise it is left as it is. The value (for IN) that is suggested by experimentation over a number of problems is 4. The following equation is used when modification is necessary:
(7)xi,j*=xi,j+(xi,j-xk,j)β,j=1,…,n,
where β∈[-1,1], xi,j*∈[aj,bj], and k is different from i. To keep the size of the population constant, the extra plants at the bottom of the sorted population are eliminated.


## 4. Examples of Structural Engineering Optimization Problems

PPA as explained in the pseudo-code Algorithm1 is extended to cater for constrained optimisation problems to be found in the appendices [6, 27]. This extended version of PPA is fully explained in the pseudo-code Algorithm 2. Note that the penalty function approach is used to handle the constraints [19, 22]. Equations are first transformed into inequality constraints before they are taken into consideration. Table 1 records the parameter values used in the implementation. Column 4 shows the value of Pm used throughout the experiments. This value has been found through experimentation on the problem described in Appendix B. The different runs are represented in Figure 1 where for 40 trials corresponding to the 30000 function evaluations threshold, Pm=0.8 seems to be the optimal value for this parameter. Other aspects of the extended algorithm such as exploration and exploitation are investigated in Figures 2 and 3. These figures, as one expects, show that the magnitudes of the steps/perturbations of the plant positions, that is the lengths of the runners, get shorter and shorter as the search progresses. Figure 4 is a representation of the convergence of the objective values of the problems described in Appendices A and C. In both cases, these values fluctuate wildly before they settle down to very good approximate values. The numerical results of the experiments on all problems described in Appendices A, through G are compiled in Tables 2, 3, 4, 5, 6, 7, and 8.Table 1
Parameters used in PPA for seven engineering problems.
Problem
Population size
Maximum iteration
P
m
Max function evaluations
Number of runners
Runs
Welded beam
40
20
0.8
30000
3
100
Pressure vessel
40
20
0.8
30000
3
100
Spring design
40
25
0.8
30000
3
100
Speed reducer
40
20
0.8
30000
3
100
Constrained Problem I
40
20
0.8
24000
3
100
Constrained Problem II
40
20
0.8
24000
3
100
Himmelblau's function
40
25
0.8
30000
3
100Table 2
Welded beam design optimisation.
Solution vector
GA [28]
HSA [29]
HSA [30]
HHSA [31]
BDA [32]
PHS [27]
IPHS [27]
PPA
w
0.2088
0.2442
0.2057
0.2057
0.2057
0.2057
0.2057
0.2057
L
3.4205
6.2231
3.4704
3.4706
3.4704
3.4704
3.4704
3.4704
d
8.9975
8.2915
9.0366
9.0368
9.0366
9.0366
9.0366
9.0366
h
0.2100
0.2443
0.2057
0.2057
0.2057
0.2057
0.2057
0.2057
g
1
(
x
)
-
0.3378
*a
*
*
0.0
0.0
0.0
-
1.2733
E
-
11
g
2
(
x
)
-
353.9026
*
*
*
0.0
0.0
0.0
-
3.2378
E
-
11
g
3
(
x
)
-
0.0012
*
*
*
-
5.5511
E
-
17
-
5.5511
E
-
17
-
5.55
E
-
17
-
1.64
E
-
13
g
4
(
x
)
-
3.4118
*
*
*
-
3.4329
-
3.4329
-
3.4329
-
3.4329
g
5
(
x
)
-
0.0838
*
*
*
-
0.0807
-
0.0807
-
0.0807
-
0.0807
g
6
(
x
)
-
0.2356
*
*
*
-
0.2355
-
0.2355
-
0.2355
-
0.2355
g
7
(
x
)
-
363.2323
*
*
*
-
9.0949
E
-
13
-
9.0949
E
-
13
-
9.09
E
-
13
-
6.2755
E
-
11
f
(
x
)
1.7483
2.38
1.7248
1.7248
1.7248
1.7248
1.7248
1.7248
aNot available.Table 3
Pressure vessel design optimisation.
Solution vector
IP(M-5) [7]
GA [14]
HSA [29]
HSA [30]
PHS [27]
IPHS [27]
PPA
d
1
1.125
1.125
1.125
1.125
1.125
1.125
0.7781
d
2
0.625
0.625
0.625
0.625
0.625
0.625
0.3846
r
48.97
58.1978
58.2789
58.2901
58.2874
58.2901
40.3196
L
106.72
44.2930
43.7549
43.6926
43.7075
43.6927
200.0
g
1
(
x
)
-
0.1799
0.0017
-
0.0002
0.0000
-
5.2058
E
-
005
-
3.3595
E
-
7
3.627
E
-
12
g
2
(
x
)
-
0.1578
-
0.0697
-
0.0690
-
0.0689
-
0.0689
-
0.0689
1.441
E
-
12
g
3
(
x
)
-
97.760
-
974.3
-
3.7162
-
2.0150
-
0.6122
-
0.0705
1.1641
E
-
9
g
4
(
x
)
-
133.28
-
195.707
-
196.245
-
196.307
-
196.29
-
196.307
-
40.0
f
(
x
)
7980.894
7207.494
7198.433
7197.730
7197.896
7197.730
5885.3327Table 4
Minimization of the weight of a compression spring.
Solution vector
MP(M-5) [33]
EC [34]
GA [28]
BDAs [32]
PHS [27]
IPHS [27]
PPA
x
1
0.0500
0.0533
0.0519
0.0514
0.0500
0.0518
0.0515
x
2
0.3159
0.3991
0.3639
0.3513
0.3173
0.3608
0.3541
x
3
14.2500
9.1854
10.8905
11.6086
14.0375
11.0503
11.4387
g
1
(
x
)
-
0.00001
0.00001
-
0.00001
-
0.0033
-
4.7653
E
-
6
-
2.1962
E
-
6
-
5
E
-
15
g
2
(
x
)
-
0.0037
-
0.00001
-
0.00002
-
1.0970
E
-
4
-
1.8124
E
-
4
-
2.8408
E
-
7
-
1.3901
E
-
9
g
3
(
x
)
-
3.9383
-
4.1238
-
4.0613
-
4.0263
-
3.9672
-
4.0618
-
4.0487
g
4
(
x
)
-
0.7560
-
0.6982
-
0.7226
-
0.7312
-
0.7550
-
0.7248
-
0.7294
f
(
x
)
0.01283
0.01273
0.01268
0.01266
0.01272
0.01266
0.01266Table 5
Speed reducer design optimisation.
Solution vector
PSO [6]
AAI [35]
PHS [27]
IPHS [27]
PPA[μ=E5.488]
PPA[μ=E5.93101]
x
1
3.50
3.50
3.50
3.50
3.4922
3.4971
x
2
0.70
0.70
0.70
0.70
0.70
0.70
x
3
17.0
17.0
17.0
17.0
17.0
17.0
x
4
7.30
7.30
7.30
7.30
7.30
7.30
x
5
7.80
7.71
7.7159
7.7153
7.80
7.80
x
6
3.3502
3.35
3.3502
3.3502
3.3496
3.3500
x
7
5.2866
5.29
5.2869
5.2866
5.2846
5.2866
g
1
(
x
)
-
0.0739
*a
*
*
-
0.07185
-
0.07317
g
2
(
x
)
-
0.1979
*
*
*
-
0.1962
-
0.1973
g
3
(
x
)
-
0.4991
*
*
*
-
0.4988
-
0.4990
g
4
(
x
)
-
0.9014
*
*
*
-
0.9013
-
0.9014
g
5
(
x
)
0.0000
*
*
*
4.6229
E
-
4
1.667
E
-
4
g
6
(
x
)
-
5.000
E
-
16
*
*
*
1.816
E
-
3
6.564
E
-
4
g
7
(
x
)
-
0.7025
*
*
*
-
0.70250
-
0.7025
g
8
(
x
)
-
1.000
E
-
16
*
*
*
2.2248
E
-
3
8.0440
E
-
4
g
9
(
x
)
-
0.5833
*
*
*
-
0.5842
-
0.58366
g
10
(
x
)
-
0.0513
*
*
*
-
0.0514
-
0.05136
g
11
(
x
)
-
0.0108
*
*
*
-
0.01114
-
0.0108
f
(
x
)
2,996.3481
2994.4
2994.9
2994.4
2994.4449
2996.1137
aNot available.Table 6
Constrained optimization problem I.
Solution vector
GAs [36]
EP [37]
HSA [29]
PHS [27]
IPHS [27]
PPA[μ=E4]
Optimal solution
x
1
0.8080
0.8350
0.8343
0.8230
0.8229
0.8298
0.8228
x
2
0.8854
0.9125
0.9121
0.9113
0.9113
0.9098
0.9114
g
1
(
x
)
3.7
E
-
2
1
E
-
2
5
E
-
3
1.1880
E
-
4
3.8744
E
-
5
7.8953
E
-
05
7.05
E
-
9
g
2
(
x
)
5.2
E
-
2
-
7
E
-
2
5.4
E
-
3
3.5443
E
-
4
1.8967
E
-
4
9.1722
E
-
05
1.73
E
-
8
f
(
x
)
1.4339
2.3772
1.3770
1.3931
1.3932
1.3774
1.3935Table 7
Constrained optimization problem II.
Algorithms
x
1
x
2
f
(
x
)
Deb [38]
GA with PS (R=0.01)
*a
*
13.5895
GA with PS (R=1)
*
*
13.5910
GA with TS-R
*
*
13.5908
HSA [30]
2.2468
2.3818
13.5908
HSA [29]
2.2468
2.3821
13.5908
PHS [27]
2.2480
2.4066
13.6117
IPHS [27]
2.2468
2.3818
13.5908
PPA
2.2468
2.3818
13.5908
Optimal solution
2.2468
2.3818
13.5908
aNot available.Table 8
Optimal solutions for a variation on Himmelblau's function.
Solution vector
GA [38]
HSA [29]
PHS [27]
IPHS [27]
PPA
x
1
*a
78.0
78.0
78.0
78.0
x
2
*
33.0
33.0
33.0
33.0
x
3
*
29.995
30.0053
29.9953
29.9952
x
4
*
45.0
45.0
45.0
45.0
x
5
*
36.776
36.7521
36.7756
36.7758
g
1
(
x
)
*
*
91.9963
91.9999
92.0
g
2
(
x
)
*
*
98.8362
98.8404
98.8405
g
3
(
x
)
*
*
20.0
20.0
20.0
f
(
x
)
-
30665.500
-
30665.500
-
30663.845
-
30665.533
-
30665.540
aNot available.Algorithm 2:Pseudocode of PPA for constrained optimisation.
(1) Initialization:gmax⁡← Maximum number of generations; NP ← population size; r← trial run
(2)if  r≤NP  then
(3)  Create a random population of plantspop={Xi∣i=1,2,…,NP}, using (4) and gather the best solutions.
(4)end if
(5)while  r>NP  do
(6)  Use populationpopg formed by gathering all best solutions from previous runs.
Calculate INj value for each column j of popg (see Section 3).
(7)end while
(8) Evaluate the population. In case ofpopg the algorithm does not need to evaluate the population,
(9) Set number of runners,nr=3, ngen=1,
(10)while (ngen<gmax⁡) or (n_eval<max_eval) do
(11)  CreateΦ:
(12)for  i=1 to NP  do
(13)for  k=1 to nr  do
(14)if  r≤NP  then
(15)if  rand≤Pm  then
(16)      Generate a new solutionX* according to (5);
(17)       Evaluate it and store it inΦ;
(18)end if
(19)if  rand≤Pm  then
(20)      Generate a new solutionX* according to (6);
(21)       Evaluate it and store it inΦ;
(22)end if
(23)else
(24)for  j=1: n  do
(25)if (INj<4) or (rand≤Pm) then
(26)       update thejth entry of Xi, i=1,2,…,NP, according to (7);
(27)end if
(28)      Evaluate new solutionX* and store it in Φ;
(29)end for
(30)end if
(31)end for
(32)end for
(33)  AddΦ to current population;
(34)  Sort the population in ascending order of the objective values;
(35)  Update current best;
(36)end while
(37)Return: Updated population.Figure 1
Impact of the particular probabilityPm on the performance of PPA.Figure 2
Exploitation characteristic of PPA using rules2-3.Figure 3
Exploration characteristic of PPA using rule 1.Convergence plot of welded beam design and tension compression spring design optimization problems over 100 trial runs.
(a)
(b)


## 5. Conclusion

We have implemented PPA to solve seven well known difficult constrained optimization problems arising in engineering design with continuous domains. PPA found either near best known solutions or optimal ones to all of them. The results are compared to those obtained with other algorithms found in the literature, namely GA (and variants of it, here denoted EC and EP), PSO, HSA (and variants of it namely PHS and IPHS), IP, MP, and BDA. Note that some of the problems have not been solved by all algorithms. For instance, the pressure vessel design problem has not been solved with BDA or MP as far as we know. Similarly the spring compression problem has not been solved with IP and HSA. These gaps in the computational results found in the literature on the considered problems are not substantial to hinder our experimental work and conclusions. Indeed, the recorded evidence in the large majority of cases points to the overwhelming superiority of PPA. Having said that, it must be added that further improvements to PPA and testing are being carried out on a more extensive collection of test problems including discrete ones.



---

*Source: 627416-2014-05-07.xml*