Keywords

1 Introduction

Differential evolution (DE) is known as one of the most competitive, reliable and versatile evolutionary algorithm for optimization on the continuous spaces [1]. DE has shown successful results in a variety of ranges of optimization problems including multi-objective [2], multi-modal [3], large-scale [4], expensive [5], constrained [6] and dynamic optimization problems [7, 8]. Among these, constrained optimization problems have a great importance, since in the real world problems, most of the optimization problems have inequality and/or equality constraints. Constrained optimization problems are usually harder to tackle than unconstrained ones, and evolutionary algorithms require a constrained handling technique to deal with the constraints. A review of the different constraint handling techniques can be found in [9].

Another area that have attracted researcher’s attention in recent years is dynamic optimization and DE has been regarded as a high performing algorithm in this area [7, 10, 11]. Considering constraints and dynamism simultaneously (known as dynamic constrained optimization problems: DCOPs) has been even more challenging for an algorithm, as it will be harder to track the global optimum solution when the constraints or the objective function change overtime. The algorithms that solve these kind of problems need to incorporate some mechanisms to deal with the changes in the environment. Different mechanisms have been proposed in the literature on DCOPs including change detection (re-evaluation of solutions, and decreasing the quality of solutions) [12], introducing diversity (increase the mutation) [13], maintaining diversity (adding random solutions called random immigrants) [14], memory-based approaches [15], and the population-based approaches [16].

In order to handle the constraints in these problems, different constraint handling techniques have been applied including penalty functions [13, 17], feasibility rules [8], and repair methods [7, 11, 18]. The last technique has not only been suitable to deal with the constraints, but also has been able to improve the algorithm performance when has been used in dynamic environments. The reason is because this technique is not only choosing between the solutions in the selection, but also moves the solution toward the feasible region by the repair operator. Indeed, the main idea of a repair method is to convert infeasible solutions into feasible ones. Based on the competitive results that these methods have shown, we carry out investigations on the behaviour of these repair methods for DCOPs.

Based on the literature on the current repair methods applied in DCOPs, four types of repair methods including (i) reference-based repair [19], (ii) offspring-repair [7, 20], (iii) mutant-repair [11, 21] and (iv) gradient-based repair [18] have been distinguished. (i) uses reference solutions in order to convert an infeasible solution to a feasible one. In (ii) the repair method is similar to (i), the only difference between these two methods is that choosing the feasible reference solution in (i) is completely random, while in (ii) the nearest feasible reference solution is selected. (iii) is a repair method which does not require feasible solutions to operate, and is inspired by the differential mutation operator. (iv) is based on gradient information derived from the constraint set to systematically repair infeasible solutions.

Our main focus is to investigate the specifications of each of these methods on a recent benchmark set for DCOPs [19] when applying DE. For the comparison of the effectiveness of each method, the offline error [19] and two newly proposed measures are used. The analysis shows that the gradient-based method outperforms other repair methods based on almost of the measures. However, this method can not be used like a black-box, since it should be known if the constraints have derivative. On the contrary, based on offline error, the worst method seem to be mutant repair method, but this method repairs the solutions very fast after only a few tries. Although, these small number of tries for repairing a solution in this method is mostly because in this benchmark, most of the problems have a huge feasible area. Finally, based on the analysis, the benefits and drawbacks of each method are pointed out and directions for future work are given.

The rest of this paper is organized as follows. In Sect. 2, we define our notion of dynamic constrained optimization problems and provide an introduction into differential evolution together with the different repair methods investigated in this paper. In Sect. 3, the experimental investigations regarding the effectiveness of repair methods with respect to different performance measures are described and the experimental results are divided in offline error analysis and success rate analysis and are presented in Sect. 4 and Sect. 5 respectively. Finally, we finish with some conclusions and directions for future work.

2 Preliminaries

In this section, first we define the problem statement for DCOPs, then we give a brief description of DE algorithm and the mechanism that we have added to it in order to deal with the changes in the environment (called dynamic DE) and finally we present different repair methods that have been applied.

2.1 Problem Statement

A dynamic constrained optimization problem (DCOP) is an optimization problem where the objective function and/or the constraints can change over time [19, 22]. Formally, a DCOP can be defined as follows.

Find \({\varvec{x}}\), at each time t, which:

$$\begin{aligned} \min _{{\varvec{x}}\in F_t\subseteq [L, U]} f({\varvec{x}}, t) \end{aligned}$$
(1)

where \(f:S \rightarrow \mathbb {R}\) is a single objective function, \({\varvec{x}} \in \mathbb {R}^D \) is a solution vector and \(t \in N^+\) is the current time,

$$\begin{aligned}{}[L, U]= \left\{ {\varvec{x}} = (x_{1},x_{2},...,x_{D}) \mid L_i \le x_i \le U_i, i = 1 \ldots D\right\} \end{aligned}$$
(2)

is called the search space (S), where \(L_i\) and \(U_i\) are the lower and upper boundaries of the ith variable,

subject to:

$$\begin{aligned} \begin{array}{l} F_{t}=\{ {\varvec{x}} \mid {\varvec{x}} \in [L,U], g_i ({\varvec{x}},t) \le 0, i = 1, \ldots , m,\\ h_j ({\varvec{x}},t) = 0, j = 1, \ldots , p\} \\ \end{array} \end{aligned}$$
(3)

is called the feasible region at time t, where m is the number of inequality constraints and p is the number of equality constraints at time t.

\(\forall {\varvec{x}} \in F_t\) if there exists a solution \({\varvec{x}}^* \in F_t\) such that \(f({\varvec{x}}^*,t)\le f({\varvec{x}},t)\), then \({\varvec{x}}^*\) is called a feasible optimal solution and \(f({\varvec{x}}^*,t)\) is called the feasible optima value at time t. The objective function and the constrains can be linear or nonlinear.

2.2 Dynamic Differential Evolution

Differential evolution (DE) was first introduced in [23] as a stochastic search algorithm that is simple, reliable and fast. Each vector \({\varvec{x}}_{i, G}\) in the current population (called at the moment of the reproduction as target vector) generates one trial vector \({\varvec{u}}_{i, G}\) by using a mutant vector \({\varvec{v}}_{i,G}\). The mutant vector is created applying \({\varvec{v}}_{i,G}= {\varvec{x}}_{r0,G} + F ({\varvec{x}}_{r1,G} - {\varvec{x}}_{r2,G})\), where \({\varvec{x}}_{r0,G}\), \({\varvec{x}}_{r1,G}\), and \({\varvec{x}}_{r2,G}\) are vectors chosen at random from the current population (\(r0 \ne r1 \ne r2 \ne i\)); \({\varvec{x}}_{r0,G}\) is known as the base vector and \({\varvec{x}}_{r1,G}\), and \({\varvec{x}}_{r2,G}\) are the difference vectors and \(F>0\) is a parameter called scale factor. Then the trial vector is created by the recombination of the target vector and mutant vector using a probability crossover \(CR \in [0,1]\).

In this paper DE/rand/1/bin variant is adopted [24], where “rand” indicates how the base vector is chosen (at random in our case), “1” represents how many vector differences (vector pairs) will contribute in differential mutation, and “bin” is the type of crossover (binomial in our case).

In a DCOP an important task is to verify that the solutions’ information is correct during the search process. Because when a new change occurs in the environment, the values of the objective function and/or the constraints may change. For this reason a change detection mechanism is required to detect the changes in the objective function and/or the constraints [11, 12]. A general overview of DDE algorithm is presented in Algorithm 1.

figure a

2.3 Repair Methods

Repair methods have shown competitive results compared to other constraint handling methods in constrained optimization. The main idea of a repair method is to use a transformation process to convert an infeasible solution into a feasible one. Although, there is no need for special operators or any modifications of the fitness function in this method like other constraint handling methods, in some repair methods, reference feasible solutions are required [7, 19, 20, 25]. However, the repair methods presented in [11, 18] does not require feasible reference solutions. Repair methods used in dynamic constrained optimization problems have had an important role in the algorithm’s recovery after a change since they help to move the infeasible solutions toward feasible region. Basically on the related literature of dynamic constrained optimization problems, there have been four repair methods utilized for constraint handling as follows.

Reference-based repair method: This method was originally proposed in [25], and [19] utilized this method with a simple genetic algorithm for solving DCOPs. In this method, firstly, a reference feasible population (R) is created. If an individual of the search population (S) is infeasible, a new individual is generated on the straight line joining the infeasible solution and a randomly chosen member of R. This process will continue until the infeasible solution is repaired or a repair limit (RL = 100) attempts are computed. If the new feasible solution has better fitness value, it will be replaced by the selected reference individual. An overview of this method used for our investigations is presented in Algorithm 2, however the boldface part is only used for offspring-repair method.

Offspring-repair method: This method was applied in DCOPs in [7, 20]. In this method, a reference feasible population (R) is generated. For any infeasible solution of the search population (S), a new individual is generated on the straight line joining the infeasible solution and the nearest member of the reference population R based on Euclidean distance. This process will continue until the infeasible solution is repaired or a repair limit (RL = 100) attempts are computed. If the new feasible solution has better fitness value, it will be replaced by the selected reference individual. This method is similar to the reference-based repair method [19]. The only difference is in the process of selecting the reference solution. An overview of this method is presented in Algorithm 2.

figure b

Mutant-repair method: The mutant-repair method (see Algorithm 3) is based on the differential mutation operator, and does not require reference solutions [11]. For each infeasible solution, three new and temporal solutions are generated at random and a differential mutation operator similar to the one used in DE is applied. This repair method is applied until the infeasible solution is repaired or a specific number of unsuccessful trials to obtain a feasible solution have been carried out (RL).

Gradient-based repair method: The gradient-based repair method (see Algorithm 4) was first applied into a simple GA [26] to handle constraints in a static optimization problem and in [18] was applied for solving DCOPs. In this method, the gradient information of the constraints are utilized to repair the infeasible solutions [26]. For this purpose the gradient of the constraints based on the solution vector (that represent the rate of change of constraints based on each variable) will be calculated. At the next step the constraint violations are calculated and based on this amount and the vector of gradient, the solutions will move toward the feasible region with the proportional quantity. The constraints that are non-violated are not considered in these calculations. In this method the main idea is to only change the effective variables over the constraints that have a violation. More detail about this method can be found in [18].

figure c
figure d

3 Experimental Investigations

In this section, the utilized test problems, the performance measures and the experimental setup are presented.

3.1 Test Problems and Performance Measures

The chosen benchmark problem originally has 18 functions [19], however in this work, 10 functions among them were used for the experiments. The reason for this selection was that part of these functions were not constrained and part of them did not have derivative for the constraints and could not be applied in Gradient-based method. The test problems in this benchmark consist a variety of characteristics like (i) disconnected feasible regions (1–3), (ii) the global optima at the constraints’ boundary or switchable between disconnected regions, or (iii) the different shape and percentage of feasible area. In the experiments, for the objective function, only medium severity is considered (\(k=0.5\)), while different change severities are considered for the constraints (\(S=10\), 20 and 50). Based on the definition of the constrains in this benchmark [19], \(S=10\) represents for large severity, \(S=20\) for medium severity and \(S=50\) for the small severity of changes on the constraints. The frequency of change (\(f_c\)) is considered equal to 1000 evaluations (only in the objective function). Worth to mention that, in the repair methods, the constraints evaluations are not considered as extra evaluations when using for DCOPs [21]. More details on the benchmark can be found in [19].

For the purpose of comparing the effectiveness of each repair method, the following performance measures were used:

Offline error (\(\text {off}\_e\)) [27]: This measurement is equal to the average of the sum of errors in each generation divided by the total number of generations. The zero value of offline error indicates a perfect performance [22]. This measure is defined as:

$$\begin{aligned} off\_e= \frac{1}{G_{max}} \sum _{G = 1}^{G_{max}} e(G) \end{aligned}$$
(4)

where \(G_{max}\) is the number of generations computed by the algorithm and e(G) denotes the error in the current iteration G (see 5):

$$\begin{aligned} e(G)= |f({\varvec{x}}^*,t) - f({\varvec{x}}_{best,G},t)| \end{aligned}$$
(5)

where \(f({\varvec{x}}^*,t)\) is the feasible global optimaFootnote 1 at current time t, and \(f({\varvec{x}}_{best,G},t)\) represent the best solution (feasible or infeasible) found so far at generation G at current time t.

Success rate: This measure is calculated such that considers how many of the infeasible solutions were successful to be repaired after 100 iterations. For each infeasible solution, a repair is needed and at the end of repair iteration (Maximum 100 tries), if the solution is feasible a counter is increased. In another words, it is considered a success if before achieving to the maximum number of allowed iterations for repair (100 in our case) a solution is feasible. The total number of these successful repaired solutions (s) divided by the total number of solutions that need repair (\(n_T\)) is equal to success rate percentage. Based on this, the repair methods with success rate values equals to 100%, are able to convert all the solutions.

$$\begin{aligned} s_r= \frac{s}{n_T} \end{aligned}$$
(6)

Required number of iterations: In order to distinguish the difference between the number of evaluations that each method consumes for repairing the solution, a measurement is defined called as required number of iterations (\(rn_i\)). In this way, it is possible to compare the efficiency of each repair method. The range of values of this measure is \(\in (1-100)\). The more efficient method uses lower number of evaluations in order to repair an infeasible solution. The final amount for this measurement value is the average between the number of tries taken to convert each infeasible solution into feasible one.

3.2 Experimental Setup

The experimental results are divided as (i) offline error analysis and (ii) success rate and required number of iterations. In these experiments we investigate the behaviour of different repair methods in DDE algorithm based on the previous defined measures. In the analysis, the effects of different severities on the constraints are considered for these ten test problems. We do not bring the results for changes of frequency since it does not have any effect in the behaviour of the repair methods.

The configurations for the experiments are as follows. The number of runs in the experiments are 50, and number of considered times for dynamic perspective of the test algorithm is 5/k (\(k=0.5\)). Parameters relating to DDE algorithm are as follows: DE variant is DE/rand/1/bin, population size is 20, scaling factor (F) is a random number \(\in [0.2, 0.8]\), and crossover probability is 0.2. In the experiments, four repair methods including Reference-based, Offspring, Mutant and Gradient-based as explained in Sect. 2.3 have been applied for handling the constraint in DDE algorithm.

Table 1. Average and standard deviation of offline error values obtained by all the repairs methods with \(k =0.5\), \(S=10\), 20 and 50, and \(f_c=1000\). Best results are remarked in boldface.
Full size table
Table 2. Statistical tests on the offline error values in Table 1. “X\(^{(-)}\)” means that the corresponding algorithm outperformed algorithm X. “X\(^{(+)}\)” means that the corresponding algorithm was dominated by algorithm X. If algorithm X does not appear in column Y means no significant differences between X and Y.
Full size table

4 Offline Error Analysis

The results obtained for the four repair methods using offline error are summarized in Table 1. Furthermore, for the statistical validation, the 95%-confidence Kruskal-Wallis (KW) test and the Bergmann-Hommels post-hoc test, as suggested in [28] are presented (see Table 2). Non-parametric tests were adopted because the samples of runs did not fit to a normal distribution based on the Kolmogorov-Smirnov test. Based on the results, for the constraint’s change severity \(S=10\), the gradient-based repair outperformed almost all of the other methods in nine test problems (G24_f, G24_2, G24_3, G24_3b, G24_3f, G24_4, G24_5, G24_7 and G24_8b) except one test problem (G24_1) that in which offspring-repair has similar performance. For this severity, reference-based repair and offspring-repair performed almost the same for nine test problems (G24_1, G24_f, G24_2, G24_3, G24_3b, G24_3f, G24_4, G24_5 and G24_8b) except one test problem (G24_7) where reference-based repair outperformed offspring-repair. As Table 2 illustrates, mutant-repair is the worst between all the methods for eight test problems (G24_1, G24_f, G24_3, G24_3b, G24_3f, G24_4, G24_5 and G24_8b) except two test problems in which has similar results with reference-based repair (G24_2) and offspring-repair (G24_2 and G24_7).

For the constraint’s change severity \(S=20\), the gradient-repair excelled almost all the other methods in seven test problems (G24_1, G24_f, G24_3, G24_3f, G24_5, G24_7 and G24_8b) with exceptions including G24_2, G24_3b and G24_4, that in which offspring-repair had similar performance. For this change severity, reference-based repair and offspring-repair performed almost the same for seven test problems (G24_1, G24_f, G24_2, G24_3, G24_3f, G24_5 and G24_8b) except three test problems (G24_3b, G24_4 and G24_7). For these three problems, while in two test problems (G24_3b and G24_4) offspring-repair had better results, in one test problem (G24_7) reference-based repair outperformed the offspring-repair. Mutant-repair had the worst results between all the methods for eight test problems (G24_1, G24_f, G24_3, G24_3b, G24_3f, G24_4, G24_5 and G24_8b) except two test problems in which had similar results with reference-based repair (G24_2) and offspring-repair (G24_2 and G24_7).

For the constraint’s change severity \(S=50\), the gradient-repair excelled the other methods in six test problems (G24_f, G24_3, G24_3f, G24_5, G24_7 and G24_8b) with exceptions of having similar performance with offspring-repair (G24_1, G24_2, G24_3b and G24_4) and reference-based repair (G24_2). For this change severity, reference-based repair and offspring-repair performed almost the same for seven test problems (G24_1, G24_f, G24_2, G24_3, G24_3f, G24_5 and G24_8b) except three test problems (G24_3b, G24_4 and G24_7). For these three problems, while in two test problems (G24_3b and G24_4) offspring-repair had better results, in one test problem (G24_7) reference-based repair outperformed the offspring-repair. Mutant-repair had the worst results between all the methods for nine test problems (G24_1, G24_f, G24_3, G24_3b, G24_3f, G24_4, G24_5, G24_7 and G24_8b) except one test problem (G24_2) in which showed similar results with offspring-repair.

Gradient-repair for all severities outperformed other methods, because in this work, all of the test problems have the global optimum on the constraints’ boundaries, and since this method moves slowly toward the feasible area its less probable that loses the information of global optima in the boundaries by crossing it. Although, this method cannot be applied for the functions that do not have derivative for their constraints. For this reason, the four functions G24_6a, G24_6b, G24_6c and G24_6d (that are functions inside this set of benchmark), were not used in our experiments. Therefore, for this method an understanding about the behaviour of the constraints is specifically needed. Changes in severity do not decrease the performance of this method. Even if for severity \(S=50\), it outperformed other methods in less test problems, this is because offspring-repair performance increased for some test problems for this severity. Similar behaviour in reference-based repair and offspring-repair based on offline error for all the severities is due to the similar procedure (uniform crossover in GA) that they use for repairing the infeasible solutions. The only difference is the way that they choose the reference solution.

Table 3. Average and standard deviation of: (i) Success rate(\(s_r\)), (ii) required number of iterations (\(rn_i\)) for each of the repairs methods with \(k=0.5\), \(S=10\), 20 and 50, and \(f_c=1000\). Best results are remarked in boldface.
Full size table

5 Analysis of Success Rate and Required Number of Iterations for Repairing Solutions

Regardless of severity the total number of infeasible solutions (\(n_T\)) that needed repair for different functions were in the range between 1882 and 2981. The \(n_T\) values were increased for the functions that had dynamic constraints like G24_3, G24_3b, G24_4, G24_5 and G24_7. The reason is because, when the constraints are changing, it is more probable that some feasible solutions be converted to infeasible ones after a change occurs.

The results for the success rate (\(s_r\)) and required number of iterations (\(nr_i\)) measures are presented in Table 3. Regarding to these results, some general observations can be concluded. The number of required iterations (\(nr_i\)), was the smallest for mutant-repair with a range between 2 to 8 and in second place is gradient-repair with the range between 4 to 10. An exception of this trend was seen in the function G24_3f in all the severities, and functions G24_5 and G24_7 for the severity \(S=10\), which gradient-repair excelled mutant-repair since the percentage of feasible area in these cases were small (see Table 2 for the feasibility percentages). Overall, in mutant-repair method since the process of producing a feasible solution is completely random and in this applied benchmark functions, the percentage of feasible area is huge, so this method achieved to feasible solutions after a few tries. In another words, this method is roughly dependent to the percentage of the feasible area. As mentioned before, the second smallest values for this measure was for gradient-based method; but in this case the reason was based on this method’s wise selection and the fact that it only moves in the direction and with the amount of satisfying the constraint violations.

The worse results for this measure belonged to offspring-repair with an average number of required iterations ranging from 66 to 91 and reference-based repair with a range from 47 to 85. Compared to offspring-repair, reference-based repair required lower number of iterations, and this was because offspring-repair’s step sizes are smaller and for this reason it needed more iterations to convert the infeasible solution to a feasible one. Other drawback in these two methods is that a number of evaluations is needed to produce feasible reference population. This can be expensive in high computational complex problems [5].

Generally based on considering all the measures, offspring and reference-based repair methods in most functions had similar behaviours. This is mostly because, the process of converting the infeasible solutions to feasible ones are approximately the same in these methods, and the only difference is the way that they choose the feasible reference solution. They do not loose the information of infeasible solution completely, as they use this individual to move in the direction of one of the feasible solutions (this is more evident in offspring as it uses the nearest reference feasible solution).

Table 4. Main features of each repair method
Full size table

As regards to the third measure (success rate), although mutant-repair has the best values, but this is because in this set of benchmark, most of the functions has a huge percentage of feasible area. For this reason reaching to a feasible solution randomly after a few tries is easily possible based on this method. Obviously, for the cases of small percentage of feasible area, this method’s efficiency will decrease. This was the case for the functions G24_5 and G24_7; as can be seen from Table 1, the values for this measure dropped drastically for this method as the percentage of feasible area is small for some time periods in these two functions. Reference-based and offspring were on the second place based on the values of this measure and the results of these two methods are roughly similar. Although, gradient-based method seemed to have worse results based on this measure, the differences between these values and the values for other methods were not significant. Moreover, practically, there is no need to convert all the infeasible solutions. In Table 4 a review of the advantages and disadvantages of each method is presented.

6 Conclusion and Future Work

In this paper, an investigation on different current repair methods in DCOPs were carried out. For the comparison, three different measures called: offline error, success rate and average number of required iterations for repairing the infeasible individuals, for each method were used. The results showed regardless of the change severities, in most cases gradient-based method outperformed the other methods based on offline error. This method especially performs much better than the other methods for the problems that have the optimal solution in the boundaries of the feasible area. Indeed, this method, moves very small steps and will not lose the optimal solution in the boundaries. Although, this method can not be applied for the functions that do not have derivative of the constraints. For the other measurement criteria, the number of required repair for mutant repair was the smallest and the second rank was for gradient-based method. Finally, based on the success rate, all of the repair methods were able to repair most of the infeasible solutions; such good performance was based on the fact that the feasible region of the main static test problem (G24) [29], occupy around 79% of the whole search space [11]. For future work, a combination of different repair methods can be investigated in order to make the most of each method. In addition, other constraint handling methods like \(\epsilon \)-constrained, stochastic ranking and multi objective concepts that have not been applied in DCOPs can be applied and compared as well.