Performance improvement of a genetic algorithm using a novel restart strategy with elitism principle

Abstract

Genetic algorithm (GA) is one of the most widely used meta-heuristic optimization tools to solve a variety of problems. It is a powerful tool for global optimization. However, like other heuristic optimization techniques, it has a probabilistic guarantee to reach the globally optimum solution in a finite number of generations. In addition, a GA suffers from the poor local search capability and hence, it is slow in convergence. To overcome these disadvantages of a GA, there had been a lot of attempts made by several researchers using different techniques. One of such techniques is the restart strategy for a GA. This strategy is nothing but to start with a new population of solutions of the GA, whenever it is unable to find any better quality of solution or it satisfies some conditions pre-specified by the user. There are a few restart strategies available in the literature with their own merits and demerits. In this paper, a novel restart strategy with elitism has been proposed. It consists of mainly three different conditions, and if any of these conditions is fulfilled, the algorithm gets restarted. The proposed restart strategy has been designed in such a way that a proper balance between the exploration and exploitation can be maintained during the search. In addition, the proposed restart scheme is able to detect the premature convergence situation of a GA and it triggers out a restart of the algorithm to avoid such situation. To measure the performance of a real-coded genetic algorithm (RCGA) with the proposed restart strategy, two sets of experiments have been done on different test functions, and the results are compared with that of the RCGAs with other restart strategies available in the literature. From the experiments, it is clear that the RCGA with the proposed restart strategy is able to yield the better results compared to others.

Keywords

Genetic algorithms restart strategy elitism principle premature convergence

1. Introduction

It is important to mention that determining globally optimal solution that has been the best one to an optimization problem out of a few locally optimal ones, is significantly desirable in different spheres of applications, such as engineering design, operations research, biology, production scheduling, robotics, etc. [2, 22, 12, 1, 29, 6, 9, 36]. It is a method of searching the best feasible solution out of several possibilities. Generally, there are two categories of optimization methods, namely deterministic and stochastic ones. Each class has its own strengths and weaknesses. Deterministic methods have the guarantee to reach the globally optimum solutions for a certain problems. However, they may sometimes not be successful, when they are to tackle ill-conditioned functions and large-scale problems. Stochastic methods, on the other hand, can tackle a variety of problems, but they have a poor theoretical assurance of getting globally optimal solutions. These methods can offer the globally optimum solutions but with that of the probabilistic guarantee, which is found to be one in an infinite amount of time [17, 24]. The fact is that there does not exist any such algorithm, which is capable of yielding the globally optimum solution for solving different kinds of problems with a guarantee in finite period of time [5].

Figure 1.

Working cycle of a genetic algorithm.

There have been a large number of stochastic methods introduced till now, such as evolutionary programming [23], evolutionary strategies [13], genetic algorithms [15], differential evolution [33], cultural algorithm [32], simulated annealing [28], particle swarm optimization [31], ant colony optimization [25] etc. Genetic algorithm (GA) is one of the most popular evolutionary optimization techniques used worldwide [27]. The working cycle of a GA has been shown in Fig. 1. A GA is robust, easy to implement and applicable to solve both continuous as well as discrete optimization problems [4]. However, it is to be noted that it offers a probabilistic guarantee of achieving globally optimum solution like others stochastic approaches. In addition, a GA has poor local search capability and it is found to be slow in convergence [8]. Now, for increasing both the global and local search capabilities of a GA, one way might be to work with a large population size. However, this type of search process would be computationally far more expensive due to a very large size of the population. Many researchers had attempted to combine a local search technique, such as hill climbing, particle swarm optimization, ant colony optimization, tabu search, pattern search, simulated annealing etc., with the traditional structure of a GA for improving its overall performances [34, 26, 37]. These hybrid GAs are seen to have improved exploitation capabilities. However, the exploration capability of a hybrid GA, compared to that of a traditional GA, is found to be almost the same, as it is evolved from only one set of randomly generated initial population. Another way could be to multi-start the GA. It is nothing but to run a GA several times and the best-obtained solution among all the runs is to be considered as the globally optimum solution. There are several restart strategies available in the literature. However, there might be a chance of further improvement of these strategies.

2. Related studies

In GAs’ literature, a few restart strategies are seen to exist for global optimization. The concept of a random restart for the GA was proposed by Ghannadian et al. [10]. In their proposed structure of a GA, the mutation operator was replaced by a random restart strategy and this modified GA was implemented to solve a scheduling problem. Whenever a GA was found to be converged to a locally optimum solution, a random restart was initiated to begin a new evolution for the GA with a set of randomly generated population. Beligiannis et al. [11] suggested a method for restarting of the classical GA, in which an insertion operator was used when the condition for restarting was satisfied. The algorithm was supposed to be restarted after each predefined number of generations. During a new evolution, a certain percentage of the old population chosen randomly was transferred to the next generation. For example, if the population size and constant percentage are taken as 100 and 10%, respectively, then 90 new solutions are generated randomly and ten randomly chosen solutions from the old population are combined together and the next evolution starts with this mixed population. It was called as ‘insertion’ operation by them. Huges et al. [14] proposed a recentering-restarting evolutionary algorithm for the epidemic network to evolve and this scheme was implemented for solving TSP, ordered gene problems etc. Dao et al. [35] introduced an improved structure of a GA, in which the algorithm was restarted, if the best solution obtained so far had not been improved till a certain number of consecutive generations. During the beginning of a new evolution, the initial population was consisting of a number of elite chromosomes (which was pre-specified by the user), and the rest were randomly created solutions. The performance of the proposed strategy was measured on a two-dimensional problem and then, on a set of five multi-dimensional problems and these were not sufficient to conclude anything firmly. Suksut et al. [21] proposed a support vector machine with restarting a GA for classifying imbalanced data. In their work, a GA was found to be restarted, when the fitness value of the new generation became less than that of the old population. Das and Pratihar [3] proposed a novel restart strategy for a real-coded genetic algorithm and they claimed that this was more suitable for solving highly complex multi-modal optimization problems.

In all the restart strategies mentioned above, except in [35], the concept of transferring elite solution has not been considered. It is worth mentioning that the elite solution’s transferring strategy helps the GA to search the globally optimum solution with a high success probability [35]. Apart from this point, there is no mechanism for detecting the premature convergence state of an algorithm in all the restart strategies surveyed by the authors from the literature. Considering all these issues, a novel restart strategy with elitism principle has been proposed in this study. This proposed restart strategy is capable of determining the premature convergence state of a GA. Nevertheless, the proposed scheme can keep a proper balance between the exploration and exploitation phenomena of a GA. The remaining text has been arranged as follows. Section 3 provides a detailed description of the proposed restart strategy. Section 4 deals with the results and discussion, and the conclusions are presented in Section 5.

3. Proposed restart strategy with elitism principle

To describe the proposed restart strategy with elitism principle, we are going to take the help of a few terms and these are defined as follows:

Diversity Quotient (DQ): It is defined as the ratio of the absolute difference between the best fitness ( $f_{\textit{best}}$ ) and average fitness ( $f_{\textit{avg}}$ ) of the population to that between the best fitness and worst fitness ( $f_{\textit{worst}}$ ) values of the population.

$\displaystyle\textit{DQ}=\frac{{|f}_{\textit{best}}-f_{\textit{avg}}|}{|f_{% \textit{best}}-f_{\textit{worst}}|}$ (1)

This parameter is to be calculated in each generation and its value is found to be varied between zero and one, in general.

Maximum Diversity Quotient ( ${\textit{DQ}}_{\max}$ ): It is the maximum of all the measured values of DQ and it is also calculated in each iteration.

In a special case, where the value of DQ is found to be either greater than or equal to one, or equal to zero, or equal to infinity or a ‘NaN’ value, then it is assumed that it is a case of premature convergence of the algorithm. In this particular situation, we are going to assign the value of DQ equal to that of ${\textit{DQ}}_{\max}$ . In addition, another parameter, say flag, is assigned a value equal to one. Otherwise, the parameter flag will be assigned a value equal to zero. Nevertheless, whenever the algorithm faces this special type of situation for occurring premature convergence (i.e., $\textit{flag}=1$ ), it will get restarted and a new evolution will begin. It is to be noted that after each restart, the parameter: flag will be assigned a value equal to zero.

Threshold of Diversity Quotient ( ${\textit{DQ}}_{\textit{threshold}}$ ): It is the threshold value for the diversity quotient and is calculated using Eq. (2).

$\displaystyle{\textit{DQ}}_{\textit{threshold}}={\textit{DQ}}_{\max}\times{(1-% \textit{DQ}}_{\max}).$ (2)

The proposed restart strategy is mainly comprised of three different conditions. It is to be noted that whenever any one of these three conditions is found to be satisfied, the algorithm gets restarted. Now, these conditions are described as follows.

First condition: At the end of any generation (except the very first generation), when all the evolutionary operators have been applied and there is no improvement found of the best solution available compared to that of the previous generation, we are going to increment the value of a parameter (say, $m$ ) by one. The initial value of this parameter $m$ is set to be equal to zero at the beginning of an evolution, and whenever there will be no improvement of the best solution, it will be incremented by one. However, if any improvement is seen in the best solution in a generation, the value of $m$ will be again set equal to zero in that particular generation. Now, if in a certain condition, the value of $m$ is found to be greater than a pre-defined threshold value (say, $m_{\textit{threshold}}$ ), the algorithm will prepare itself for a restart. In a word, a GA restarts, if $m>m_{\textit{threshold}}$ .

Table 1

A set of twenty classical benchmark functions with their mathematical expressions

Name of the function	Mathematical expression	Variable boundaries
F01: Sphere	$f(x)=\sum\limits_{i=1}^{d}x_{i}^{2}$	$[-100,100]^{d}$
F02: Sum of different powers	$f(x)=\sum\limits_{i=1}^{d}{{\|x}_{i}\|^{i+1}}$	$[-100,100]^{d}$
F03: Rotated hyper-ellipsoid	$f(x)=\sum\limits_{i=1}^{d}\sum\limits_{j=1}^{i}x_{j}^{2}$	$[-65,65]^{d}$
F04: Griewank	$f(x)={\displaystyle\frac{\sum\nolimits_{i=1}^{d}x_{i}^{2}}{4000}}-\prod\limits% _{i=1}^{d}\cos(x_{i}/\sqrt{i})+1$	$[-600,600]^{d}$
F05: Trid	$f(x)=\sum\limits_{i=1}^{d}(x_{i}-1)^{2}-\sum\limits_{i=2}^{d}(x_{i}x_{i-1})$	$[-d^{2},d^{2}]^{d}$
F06:Rastrigin	$f(x)=10d+\sum\limits_{i=1}^{d}{[x_{i}^{2}-10\cos{(2\pi x_{i})]}}$	$[-5.12,5.12]^{d}$
F07: Levy	$f(x)={\sin}^{2}(\pi w_{1})+\sum\limits_{i=1}^{d-1}(w_{i}{-1)}^{2}[1+10{\sin}^{% 2}(\pi w_{i}+1)]$	$[-5.12,5.12]^{d}$
	$+(w_{d}-1)^{2}[1+10{\sin}^{2}(\pi w_{d})],\text{ where }w_{i}=1+(x_{i}-1)/4$
F08: Ackley	$f(x)=-20\exp\left(-0.2\sqrt{{\displaystyle\frac{1}{d}}\sum\limits_{i=1}^{d}x_{% i}^{2}}\right)$	$[-32,32]^{d}$
	$-\exp\left({\displaystyle\frac{1}{d}}\sum\limits_{i=1}^{d}\cos(2\pi x_{i})% \right)+20+\exp(1)$
F09: Schwefel	$f(x)=418.9829d-\sum\limits_{i=1}^{d}x_{i}\sin(\sqrt{\|x_{i}}\|)$	$[-500,500]^{d}$
F10: Rosenbrock	$f(x)=\sum\limits_{i=1}^{d-1}{[100(x_{i+1}-x_{i}^{2}})^{2}+(x_{i}-1)^{2}]$	$[-10,10]^{d}$
F11: Zakharov	$f(x)=\sum\limits_{i=1}^{d}x_{i}^{2}+\left(\sum\limits_{i=1}^{d}{0.5ix_{i}}% \right)^{2}+\left(\sum\limits_{i=1}^{d}{0.5ix_{i}}\right)^{4}$	$[-5,10]^{d}$
F12: Dixon-price	$f(x)=(x_{1}-1)^{2}+\sum\limits_{i=2}^{d}{i(2x_{i}^{2}}-x_{i-1})^{2}$	$[-10,10]^{d}$
F13: Michalewicz	$f(x)=-\sum\limits_{i=1}^{d}\sin{(x_{i})}{\sin}^{20}\left({\displaystyle\frac{% ix_{i}^{2}}{\pi}}\right)$	$[0,\pi]^{d}$
F14: Powell	$f(x)=\sum\limits_{i=1}^{d/4}[(x_{4i-3}+10x_{4i-2})^{2}+5(x_{4i-1}-x_{4i})^{2}$	$[-10,10]^{d}$
	$+(x_{4i-2}-{2x}_{4i-1})^{4}+10(x_{4i-3}+x_{4i})^{4}]$
F15: Bent ciger	$f(x)=x_{1}^{2}+{10}^{6}\sum\limits_{i=2}^{d}x_{i}^{2}$	$[-10,10]^{d}$
F16: Alpine	$f(x)=\sum\limits_{i=1}^{d}{\|x_{i}\sin({x_{i})+0.1x_{i}}\|}$	$[-10,10]^{d}$
F17: Weierstrass	$f(x)=\sum\limits_{i=1}^{d}\left(\sum\limits_{k=0}^{20}[{0.5}^{k}\cos(2\pi\cdot 3% ^{k}(x_{i}+0.5))]\right)$	$[-0.9,0.9]^{d}$
	$-d\sum\limits_{k=0}^{20}{[{0.5}^{k}\cos{(2\pi\cdot 3^{k}}}\cdot 0.5)]$
F18: Styblinski-Tang	$f(x)=0.5\sum\limits_{i=1}^{d}{(x_{i}^{4}-16x_{i}^{2}+5x_{i})+39.16599d}$	$[-10,10]^{d}$
F19: Salomon	$f(x)=1-\cos\left(2\pi\sum\limits_{i=1}^{d}x_{i}\right)+0.1\sum\limits_{i=2}^{d% }x_{i}^{2}$	$[-100,100]^{d}$
F20: Schaffer F7	$f(x)={\displaystyle\frac{1}{d-1}}\sum\limits_{i=1}^{d-1}[(x_{i}^{2}+x_{i-1}^{2% })^{0.25}+(x_{i}^{2}$	$[-100,100]^{d}$
	$+x_{i+1}^{2})^{0.25}{\sin}^{2}(50(x_{i}^{2}+x_{i+1}^{2})^{0.1})]$

The task of selecting a suitable value for $m_{\textit{threshold}}$ is difficult, as it depends on the nature of the problem. A very low value of the said parameter will lead to a frequent restart of the algorithm and consequently, the algorithm will be not able to converge to an optimal or near optimal solution. On the other side, a very high value of $m_{\textit{threshold}}$ might be the reason for a less efficient global search of the algorithm. So, the thumb rule for deciding the value of the said parameter is as follows: if the optimization problem to be solved is found to be a simple one, $m_{\textit{threshold}}$ is set to a high value and vice-versa.

Second condition: During a particular evolution, a GA is going to count the number of generations (say, $c_{\textit{gen}}$ ), where the parameter $m$ is seen to have a value more than zero. In another word, the parameter $c_{\textit{gen}}$ will be incremented by one, whenever $m$ is found to be greater than zero in an evolution. As like $m$ , the initial value for $c_{\textit{gen}}$ is to be set equal to zero during the start of an evolution. Now, in a certain generation, if $c_{\textit{gen}}$ is found to be greater than a pre-specified threshold count parameter value (say, $th\_\textit{count}$ ) and the value of DQ is also seen to be less than ${\textit{DQ}}_{\textit{threshold}}$ , then the algorithm gets restarted. This restart condition can be written as follows.

$\textit{If}\left(c_{\textit{gen}}>th\_\textit{count}∼{}\&\&∼{}\textit{DQ}<{% \textit{DQ}}_{\textit{threshold}}\right)$ the algorithm prepares for a restart. After each restart, the value of $c_{\textit{gen}}$ is again set to be equal to zero. For deciding a suitable value for $th\_\textit{count}$ , the same thumb rule, as described in case of $m_{\textit{threshold}}$ , is applicable.

In general, the parameter DQ is seen to have a large value at the initial stage of an evolution and afterward, it gradually decreases. Now, an important point is to be noted here about the implementation time of this 2 ${}^{\rm nd}$ condition for a restart. This condition is applied, only when there is a sufficient decrement in the diversity of the population. Therefore, it inherently keeps a proper balance between the exploration and exploitation capabilities of a GA and makes the search process more efficient.

Third condition: This condition has already been explained as a special case during defining the maximum diversity quotient ( ${\textit{DQ}}_{\max}$ ) term. Whenever the algorithm faces that special situation of premature convergence (i.e., $\textit{flag}=1$ ), it is going to be restarted. So, this condition of restart will help the algorithm to overcome the situation of premature convergence.

Table 2

The common parameters for all the RCGAs

RCGA’s parameters	Values
Population size	50
Maximum number fitness evaluations	1,00,000
Crossover probability	1.0
Mutation probability	0.03
User index parameter for SBX	2
User index parameter for polynomial mutation	10

It is to be noted that, whenever any one of these said conditions is fulfilled, the algorithm is restarted. During restart, one copy of the best solution or elite solution available in the last generation is transferred to the next generation and the rest of the solutions are created randomly. Here, we adopt the principle of elitism [16] in our proposed restart strategy. The significant difference of this proposed restart strategy from that of our previous work [3] is that, in this study, we take the help of elitism principle, which is nothing but the act of directly copying the elite solution to the next iteration’s population, so that the best solution available at that moment is not lost. This strategy is going to work better for the relatively simpler problems, whereas the restart strategy proposed [3] is suitable for highly complex and deceptive types of optimization problems with multi-modality.

4. Experimental results and discussion

For the performance evaluation of the proposed restart strategy, we have conducted two sets of experiments on a number of optimization problems with different properties and complexity levels. In both the experiments, we have yielded the results with four types of real-coded genetic algorithms (RCGAs), such as

•
An RCGA with the proposed restart strategy (RCGA_1).
•
An RCGA with the restart strategy suggested by Dao et al. [35] (RCGA_2).
•
An RCGA with the restart strategy introduced by Beligiannis et al. [11] (RCGA_3).
•
A standard RCGA without restart strategy (RCGA _4).

Table 3
Comparison of the results of all the RCGAs on test functions (F01–F20)

Function RCGA_1 RCGA_2 RCGA_3 RCGA_4 Avg. CPU time (in Sec.) to reach a

particular objective function value ( $f$ )

F01 Best 1.9050E-06 1.1919E-04 3.3910E-05 4.4385E-04 $f=$ 1.0E-03

Worst 1.5705E-03 3.7771E-03 2.9045E-03 6.4137E-03 RCGA_1: 2.0933

Mean 2.3686E-04 1.1018E-03 8.6056E-04 1.7229E-03 RCGA_2: 2.8555

Median 1.3820E-04 8.7802E-04 6.2653E-04 1.2083E-03 RCGA_3: 2.8413

SD 2.7447E-04 7.8524E-04 6.7200E-04 1.3347E-03 RCGA_4: 3.0356

F02 Best 8.6511E-19 3.6163E-16 5.6636E-14 4.0078E-15 $f=$ 1.0E-05

Worst 4.9664E-07 1.4169E-04 1.5691E-04 2.8415E-04 RCGA_1: 1.7603

Mean 1.6039E-08 1.0017E-05 1.1301E-05 1.5246E-05 RCGA_2: 2.3330

Median 4.4919E-12 5.1809E-09 1.4190E-07 2.1807E-07 RCGA_3: 2.5055

SD 8.1331E-08 2.6080E-05 3.3530E-05 4.7278E-05 RCGA_4: 2.4537

F03 Best 1.0931E-05 5.5907E-04 3.6989E-04 1.6582E-03 $f=$ 1.0E-02

Worst 5.4371E-03 5.0339E-02 1.9871E-01 7.0563E-02 RCGA_1: 2.1767

Mean 1.3390E-03 8.9787E-03 9.7555E-03 1.1185E-02 RCGA_2: 2.7758

Median 8.1438E-04 5.8254E-03 2.7452E-03 8.0811E-03 RCGA_3: 2.5919

SD 1.5183E-03 9.6052E-03 2.9475E-02 1.1017E-02 RCGA_4: 2.9950

F04 Best 2.7698E-06 4.8883E-05 1.5139E-04 5.3738E-04 $f=$ 1.0E-01

Worst 4.6620E-02 7.0016E-02 1.1882E-01 5.0106E-02 RCGA_1: 0.9306

Mean 8.9577E-03 1.5501E-02 1.5943E-02 1.4395E-02 RCGA_2: 1.0653

Median 6.6662E-04 1.1670E-02 1.2800E-02 1.2588E-02 RCGA_3: 1.1583

SD 1.1775E-02 1.7366E-02 1.9254E-02 1.3711E-02 RCGA_4: 0.9876

F05 Best $-$ 4.4614E+03 $-$ 4.1866E+03 $-$ 4.0137E+03 $-$ 4.5673E+03 $f=$ 1.0E+03

Worst 1.4282E+04 1.2297E+04 1.3854E+04 9.2934E+03 RCGA_1: 3.8115

Mean $-$ 2.6767E+02 $-$ 1.7548E+02 2.5434E+02 1.1584E+02 RCGA_2: 3.8755

Median $-$ 1.0031E+03 $-$ 1.3418E+03 $-$ 4.9753E+02 $-$ 7.6567E+02 RCGA_3: 4.0584

SD 3.8355E+03 3.4633E+03 3.5333E+03 3.4849E+03 RCGA_4: 3.8856

F06 Best 2.1315E-06 3.1220E-05 6.0901E-05 8.7319E-05 $f=$ 1.0E-03

Worst 2.1739E-03 2.0013E-03 4.2168E-03 3.7303E-03 RCGA_1: 2.2370

Mean 2.6606E-04 7.3881E-04 8.4513E-04 1.0970E-03 RCGA_2: 2.9611

Median 1.0630E-04 6.0043E-04 5.9045E-04 8.6264E-04 RCGA_3: 3.0623

SD 4.1096E-04 5.0850E-04 8.4161E-04 7.6756E-04 RCGA_4: 3.0845

F07 Best 4.8227E-09 1.7724E-07 4.8854E-08 1.2854E-07 $f=$ 1.0E-05

Worst 1.9634E-06 7.8225E-06 1.4829E-05 1.0862E-05 RCGA_1: 1.8181

Mean 2.4758E-07 1.7478E-06 1.4454E-06 2.0171E-06 RCGA_2: 2.5891

Median 1.0581E-07 1.2195E-06 7.4349E-07 1.5789E-06 RCGA_3: 2.2136

SD 3.3711E-07 1.6693E-06 2.2799E-06 1.9579E-06 RCGA_4: 2.6163

F08 Best 3.4471E-04 2.1016E-03 1.0627E-03 4.0560E-03 $f=$ 1.0E-02

Worst 4.6285E-03 1.5637E-02 1.3302E-02 2.0343E-02 RCGA_1: 1.8569

Mean 1.8511E-03 7.2299E-03 5.7322E-03 9.2291E-03 RCGA_2: 2.7375

Median 1.7147E-03 6.8489E-03 5.5595E-03 8.5251E-03 RCGA_3: 2.6811

SD 9.8496E-04 2.9547E-03 2.6802E-03 4.0047E-03 RCGA_4: 2.8672

F09 Best 3.5537E+02 4.7376E+02 4.7375E+02 4.7376E+02 $f=$ 1.8E+03

Worst 1.4213E+03 2.0135E+03 1.7766E+03 1.8950E+03 RCGA_1: 0.1713

Mean 9.4751E+02 1.1683E+03 1.1065E+03 1.1939E+03 RCGA_2: 0.4127

Median 9.4751E+02 1.1844E+03 1.0659E+03 1.1844E+03 RCGA_3: 0.2583

SD 2.8613E+02 3.5004E+02 3.3252E+02 3.0346E+02 RCGA_4: 1.5860

F10 Best 5.7688E-01 1.1464E+00 1.2518E+00 1.9161E+00 $f=$ 9E+01

Worst 1.4060E+02 1.3869E+02 1.4192E+02 1.4055E+02 RCGA_1: 1.1924

Mean 5.1517E+01 6.1309E+01 6.1257E+01 6.3826E+01 RCGA_2: 1.8922

Median 6.9309E+01 7.6694E+01 7.4162E+01 7.2482E+01 RCGA_3: 1.3932

SD 3.4695E+01 3.7185E+01 3.7534E+01 3.4059E+01 RCGA_4: 1.7874

F11 Best 5.5528E-01 6.4009E-01 6.7122E-01 6.6413E-01 $f=$ 2E+01

Worst 5.6423E+00 4.5333E+00 4.9241E+00 6.2209E+00 RCGA_1: 1.0785

Mean 2.2771E+00 1.8856E+00 2.3209E+00 2.0979E+00 RCGA_2: 1.0855

Median 1.9268E+00 1.6313E+00 2.1762E+00 2.0125E+00 RCGA_3: 1.2837

SD 1.2468E+00 9.0890E-01 1.0348E+00 9.8958E-01 RCGA_4: 1.0159

Table 3, continued

Function RCGA_1 RCGA_2 RCGA_3 RCGA_4 Avg. CPU time (in Sec.) to reach a

particular objective function value ( $f$ )

F12 Best 3.6327E-02 1.0598E-01 3.1432E-02 7.8345E-02 $f=$ 4E+00

Worst 5.9079E+00 4.8560E+00 5.3946E+00 4.8496E+00 RCGA_1: 1.5608

Mean 2.0332E+00 1.8079E+00 1.7118E+00 1.8560E+00 RCGA_2: 2.1144

Median 1.4092E+00 1.3100E+00 1.1062E+00 1.5591E+00 RCGA_3: 2.0134

SD 1.3807E+00 1.2952E+00 1.3309E+00 1.2734E+00 RCGA_4: 2.0737

F13 Best $-$ 2.9630E+01 $-$ 2.9630E+01 $-$ 2.9624E+01 $-$ 2.9631E+01 $f=$ - $2.9$ E+01

Worst $-$ 2.9476E+01 $-$ 2.9552E+01 $-$ 2.9512E+01 $-$ 2.9571E+01 RCGA_1: 1.0198

Mean $-$ 2.9609E+01 $-$ 2.9617E+01 $-$ 2.9607E+01 $-$ 2.9620E+01 RCGA_2: 0.9210

Median $-$ 2.9616E+01 $-$ 2.9623E+01 $-$ 2.9615E+01 $-$ 2.9622E+01 RCGA_3: 1.1371

SD 2.3645E-02 1.6409E-02 2.0377E-02 1.1022E-02 RCGA_4: 0.9106

F14 Best 4.3468E-02 5.6481E-02 5.5495E-02 5.8646E-02 $f=$ 9E-02

Worst 1.2393E-01 1.4417E-01 1.9333E-01 1.2885E-01 RCGA_1: 3.0964

Mean 7.7525E-02 9.1541E-02 1.0534E-01 9.4801E-02 RCGA_2: 3.7257

Median 7.9802E-02 8.8802E-02 1.0709E-01 9.6875E-02 RCGA_3: 3.8998

SD 1.8411E-02 2.1893E-02 2.8641E-02 1.8492E-02 RCGA_4: 3.7054

F15 Best 8.8924E-03 5.3915E-01 5.1528E-01 1.6793E+00 $f=$ 1E+01

Worst 6.2272E+00 3.9038E+01 1.2417E+02 5.3960E+01 RCGA_1: 2.0009

Mean 8.1831E-01 1.0284E+01 9.8324E+00 1.2833E+01 RCGA_2: 3.4850

Median 3.4741E-01 6.6129E+00 6.3934E+00 9.4326E+00 RCGA_3: 3.0498

SD 1.1713E+00 9.3415E+00 1.7295E+01 9.3854E+00 RCGA_4: 3.3822

F16 Best 3.4707E-06 1.3752E-04 1.7712E-04 2.3588E-04 $f=$ 1E-02

Worst 1.6094E-03 1.3403E-02 7.3205E-03 7.9811E-03 RCGA_1: 0.9171

Mean 2.6011E-04 2.2203E-03 1.4839E-03 1.5280E-03 RCGA_2: 1.2033

Median 1.2233E-04 9.8888E-04 1.0353E-03 1.0838E-03 RCGA_3: 1.2533

SD 3.4606E-04 2.8431E-03 1.3473E-03 1.4308E-03 RCGA_4: 1.0882

F17 Best 1.7289E-03 1.6871E-02 2.4440E-02 4.6613E-02 $f=$ 9E-02

Worst 9.6015E-02 1.3906E-01 1.8849E-01 1.7763E-01 RCGA_1: 17.8048

Mean 3.5551E-02 6.7995E-02 8.0440E-02 9.9018E-02 RCGA_2: 23.5558

Median 3.3012E-02 6.2236E-02 8.3177E-02 9.2054E-02 RCGA_3: 23.7144

SD 1.8597E-02 2.7310E-02 2.9857E-02 3.3882E-02 RCGA_4: 29.2414

F18 Best $-$ 5.2709E-03 $-$ 5.2609E-03 $-$ 5.2616E-03 $-$ 5.1952E-03 $f=$ 1E-03

Worst $-$ 5.1261E-03 $-$ 3.5454E-03 $-$ 4.5717E-03 $-$ 3.6379E-03 RCGA_1: 1.2867

Mean $-$ 5.2430E-03 $-$ 4.9840E-03 $-$ 5.1082E-03 $-$ 4.9330E-03 RCGA_2: 1.3393

Median $-$ 5.2495E-03 $-$ 5.0978E-03 $-$ 5.1556E-03 $-$ 5.0118E-03 RCGA_3: 1.6387

SD 2.9783E-05 3.1719E-04 1.6088E-04 2.7914E-04 RCGA_4: 1.4043

F19 Best 6.1701E-02 1.2580E-01 1.7220E-01 1.6236E-01 $f=$ 5E-01

Worst 2.0017E-01 3.5779E-01 3.8270E-01 3.5779E-01 RCGA_1: 0.8989

Mean 1.2586E-01 2.4596E-01 2.5679E-01 2.6149E-01 RCGA_2: 1.0402

Median 1.1965E-01 2.5054E-01 2.5179E-01 2.6692E-01 RCGA_3: 1.2938

SD 3.3738E-02 5.3212E-02 4.5217E-02 5.3069E-02 RCGA_4: 1.0325

F20 Best 8.2708E-02 8.6420E-02 9.8661E-02 6.5130E-02 $f=$ 5E-01

Worst 2.2819E-01 3.1357E-01 2.7186E-01 3.8097E-01 RCGA_1: 1.1123

Mean 1.4986E-01 1.7165E-01 1.7005E-01 1.7101E-01 RCGA_2: 1.4381

Median 1.4697E-01 1.6611E-01 1.6764E-01 1.6107E-01 RCGA_3: 1.2785

SD 3.3389E-02 5.4178E-02 4.0004E-02 5.9919E-02 RCGA_4: 1.1764

Figure 2.
Convergence graphs of the RCGAs for the test functions: F01–F08.

Figure 3.
Convergence graphs of the RCGAs for the test functions: F09–F16.

Table 4
List of 14 benchmark problems from CEC’05 special session on real parameter optimization [30]

Functions Bound $f_{\min}$

Unimodal functions

SF01 Shifted sphere function [ $-$ 100, 100] $-$ 450

SF02 Shifted Schwefel’s problem 1.2 [ $-$ 100, 100] $-$ 450

SF03 Shifted rotated high conditioned elliptic function [ $-$ 100, 100] $-$ 450

SF04 Shifted Schwefel’s problem 1.2 with noise in fitness [ $-$ 100, 100] $-$ 450

SF05 Schwefel’s problem 2.6 with global optimum on bounds [ $-$ 100, 100] $-$ 310

Multi-modal functions

Basic functions

SF06 Shifted Rosenbrock’s function [ $-$ 100, 100] 390

SF07 Shifted rotated Griewank’s function without bounds [0, 600] ${}^{\rm a}$ $-$ 180

SF08 Shifted rotated Ackley’s function with global optimum on bounds [ $-$ 32, 32] $-$ 140

SF09 Shifted Rastrigin’s function [ $-$ 5, 5] $-$ 330

SF10 Shifted rotated Rastrigin’s function [ $-$ 5, 5] $-$ 330

SF11 Shifted rotated Weierstrass function [ $-$ 0.5, 0.5] 90

SF12 Schwefel’s problem 2.13 [ $-\pi,\pi$ ] $-$ 460

Expanded functions

SF13 Expanded extended Griewank’s plus Rosenbrick’s function [ $-$ 3, 1] $-$ 130

SF14 Expanded rotated extended Schaffer’s F6 [ $-$ 100, 100] $-$ 300

${}^{\rm a}$ initial range.

Figure 4.
Convergence graphs of the RCGAs for the test functions: F17–F20.

The basic structures (except the restart strategies) of all the RCGAs are kept the same and these have evolutionary operators, such as tournament selection [7] with the tournament size of two, simulated binary crossover [20], polynomial mutation [19] and replacement of old population with the new ones using an efficient constraint handling technique [18]. These experiments are described, in details, below.

Figure 5.
Convergence graphs of the RCGAs for the test functions: SF01–SF08.

Figure 6.
Convergence graphs of the RCGAs for the test functions: SF09–SF14.

Table 5
Comparison of the average function errors obtained by the RCGAs

Function RCGA_1 RCGA_2 RCGA_3 RCGA_4

SF01 2.4535E-04 1.2425E-03 5.6058E-04 1.3480E-03

SF02 3.0835E+02 3.9315E+02 4.4657E+02 3.8517E+02

SF03 8.2889E+06 8.5973E+06 8.2009E+06 7.8483E+06

SF04 2.2266E+03 3.3562E+03 3.3590E+03 3.8288E+03

SF05 5.8841E+03 6.7008E+03 7.4412E+03 6.8651E+03

SF06 3.1434E+02 1.4389E+02 1.0177E+03 2.0967E+02

SF07 4.6963E+03 4.6963E+03 4.6963E+03 4.6963E+03

SF08 2.0888E+01 2.0762E+01 2.0805E+01 2.0790E+01

SF09 1.2834E-04 7.0116E-04 4.7730E-04 8.1560E-04

SF10 8.1530E+01 8.0385E+01 7.6692E+01 7.6831E+01

SF11 2.5942E+01 2.6362E+01 2.7465E+01 2.8712E+01

SF12 2.7307E+04 2.1456E+04 2.5743E+04 1.9408E+04

SF13 1.3224E+00 1.3072E+00 1.2832E+00 1.2574E+00

SF14 1.2903E+01 1.3104E+01 1.3167E+01 1.3076E+01

4.1 The first experiment

Function	RCGA_1	RCGA_2	RCGA_3	RCGA_4	Avg. CPU time (in Sec.) to reach a
F01	Best	1.9050E-06	1.1919E-04	3.3910E-05	4.4385E-04	$f=$ 1.0E-03
	Worst	1.5705E-03	3.7771E-03	2.9045E-03	6.4137E-03	RCGA_1: 2.0933
	Mean	2.3686E-04	1.1018E-03	8.6056E-04	1.7229E-03	RCGA_2: 2.8555
	Median	1.3820E-04	8.7802E-04	6.2653E-04	1.2083E-03	RCGA_3: 2.8413
	SD	2.7447E-04	7.8524E-04	6.7200E-04	1.3347E-03	RCGA_4: 3.0356
F02	Best	8.6511E-19	3.6163E-16	5.6636E-14	4.0078E-15	$f=$ 1.0E-05
	Worst	4.9664E-07	1.4169E-04	1.5691E-04	2.8415E-04	RCGA_1: 1.7603
	Mean	1.6039E-08	1.0017E-05	1.1301E-05	1.5246E-05	RCGA_2: 2.3330
	Median	4.4919E-12	5.1809E-09	1.4190E-07	2.1807E-07	RCGA_3: 2.5055
	SD	8.1331E-08	2.6080E-05	3.3530E-05	4.7278E-05	RCGA_4: 2.4537
F03	Best	1.0931E-05	5.5907E-04	3.6989E-04	1.6582E-03	$f=$ 1.0E-02
	Worst	5.4371E-03	5.0339E-02	1.9871E-01	7.0563E-02	RCGA_1: 2.1767
	Mean	1.3390E-03	8.9787E-03	9.7555E-03	1.1185E-02	RCGA_2: 2.7758
	Median	8.1438E-04	5.8254E-03	2.7452E-03	8.0811E-03	RCGA_3: 2.5919
	SD	1.5183E-03	9.6052E-03	2.9475E-02	1.1017E-02	RCGA_4: 2.9950
F04	Best	2.7698E-06	4.8883E-05	1.5139E-04	5.3738E-04	$f=$ 1.0E-01
	Worst	4.6620E-02	7.0016E-02	1.1882E-01	5.0106E-02	RCGA_1: 0.9306
	Mean	8.9577E-03	1.5501E-02	1.5943E-02	1.4395E-02	RCGA_2: 1.0653
	Median	6.6662E-04	1.1670E-02	1.2800E-02	1.2588E-02	RCGA_3: 1.1583
	SD	1.1775E-02	1.7366E-02	1.9254E-02	1.3711E-02	RCGA_4: 0.9876
F05	Best	$-$ 4.4614E+03	$-$ 4.1866E+03	$-$ 4.0137E+03	$-$ 4.5673E+03	$f=$ 1.0E+03
	Worst	1.4282E+04	1.2297E+04	1.3854E+04	9.2934E+03	RCGA_1: 3.8115
	Mean	$-$ 2.6767E+02	$-$ 1.7548E+02	2.5434E+02	1.1584E+02	RCGA_2: 3.8755
	Median	$-$ 1.0031E+03	$-$ 1.3418E+03	$-$ 4.9753E+02	$-$ 7.6567E+02	RCGA_3: 4.0584
	SD	3.8355E+03	3.4633E+03	3.5333E+03	3.4849E+03	RCGA_4: 3.8856
F06	Best	2.1315E-06	3.1220E-05	6.0901E-05	8.7319E-05	$f=$ 1.0E-03
	Worst	2.1739E-03	2.0013E-03	4.2168E-03	3.7303E-03	RCGA_1: 2.2370
	Mean	2.6606E-04	7.3881E-04	8.4513E-04	1.0970E-03	RCGA_2: 2.9611
	Median	1.0630E-04	6.0043E-04	5.9045E-04	8.6264E-04	RCGA_3: 3.0623
	SD	4.1096E-04	5.0850E-04	8.4161E-04	7.6756E-04	RCGA_4: 3.0845
F07	Best	4.8227E-09	1.7724E-07	4.8854E-08	1.2854E-07	$f=$ 1.0E-05
	Worst	1.9634E-06	7.8225E-06	1.4829E-05	1.0862E-05	RCGA_1: 1.8181
	Mean	2.4758E-07	1.7478E-06	1.4454E-06	2.0171E-06	RCGA_2: 2.5891
	Median	1.0581E-07	1.2195E-06	7.4349E-07	1.5789E-06	RCGA_3: 2.2136
	SD	3.3711E-07	1.6693E-06	2.2799E-06	1.9579E-06	RCGA_4: 2.6163
F08	Best	3.4471E-04	2.1016E-03	1.0627E-03	4.0560E-03	$f=$ 1.0E-02
	Worst	4.6285E-03	1.5637E-02	1.3302E-02	2.0343E-02	RCGA_1: 1.8569
	Mean	1.8511E-03	7.2299E-03	5.7322E-03	9.2291E-03	RCGA_2: 2.7375
	Median	1.7147E-03	6.8489E-03	5.5595E-03	8.5251E-03	RCGA_3: 2.6811
	SD	9.8496E-04	2.9547E-03	2.6802E-03	4.0047E-03	RCGA_4: 2.8672
F09	Best	3.5537E+02	4.7376E+02	4.7375E+02	4.7376E+02	$f=$ 1.8E+03
	Worst	1.4213E+03	2.0135E+03	1.7766E+03	1.8950E+03	RCGA_1: 0.1713
	Mean	9.4751E+02	1.1683E+03	1.1065E+03	1.1939E+03	RCGA_2: 0.4127
	Median	9.4751E+02	1.1844E+03	1.0659E+03	1.1844E+03	RCGA_3: 0.2583
	SD	2.8613E+02	3.5004E+02	3.3252E+02	3.0346E+02	RCGA_4: 1.5860
F10	Best	5.7688E-01	1.1464E+00	1.2518E+00	1.9161E+00	$f=$ 9E+01
	Worst	1.4060E+02	1.3869E+02	1.4192E+02	1.4055E+02	RCGA_1: 1.1924
	Mean	5.1517E+01	6.1309E+01	6.1257E+01	6.3826E+01	RCGA_2: 1.8922
	Median	6.9309E+01	7.6694E+01	7.4162E+01	7.2482E+01	RCGA_3: 1.3932
	SD	3.4695E+01	3.7185E+01	3.7534E+01	3.4059E+01	RCGA_4: 1.7874
F11	Best	5.5528E-01	6.4009E-01	6.7122E-01	6.6413E-01	$f=$ 2E+01
	Worst	5.6423E+00	4.5333E+00	4.9241E+00	6.2209E+00	RCGA_1: 1.0785
	Mean	2.2771E+00	1.8856E+00	2.3209E+00	2.0979E+00	RCGA_2: 1.0855
	Median	1.9268E+00	1.6313E+00	2.1762E+00	2.0125E+00	RCGA_3: 1.2837
	SD	1.2468E+00	9.0890E-01	1.0348E+00	9.8958E-01	RCGA_4: 1.0159

Table 3, continued
Function	RCGA_1	RCGA_2	RCGA_3	RCGA_4	Avg. CPU time (in Sec.) to reach a
						particular objective function value ( $f$ )
F12	Best	3.6327E-02	1.0598E-01	3.1432E-02	7.8345E-02	$f=$ 4E+00
	Worst	5.9079E+00	4.8560E+00	5.3946E+00	4.8496E+00	RCGA_1: 1.5608
	Mean	2.0332E+00	1.8079E+00	1.7118E+00	1.8560E+00	RCGA_2: 2.1144
	Median	1.4092E+00	1.3100E+00	1.1062E+00	1.5591E+00	RCGA_3: 2.0134
	SD	1.3807E+00	1.2952E+00	1.3309E+00	1.2734E+00	RCGA_4: 2.0737
F13	Best	$-$ 2.9630E+01	$-$ 2.9630E+01	$-$ 2.9624E+01	$-$ 2.9631E+01	$f=$ - $2.9$ E+01
	Worst	$-$ 2.9476E+01	$-$ 2.9552E+01	$-$ 2.9512E+01	$-$ 2.9571E+01	RCGA_1: 1.0198
	Mean	$-$ 2.9609E+01	$-$ 2.9617E+01	$-$ 2.9607E+01	$-$ 2.9620E+01	RCGA_2: 0.9210
	Median	$-$ 2.9616E+01	$-$ 2.9623E+01	$-$ 2.9615E+01	$-$ 2.9622E+01	RCGA_3: 1.1371
	SD	2.3645E-02	1.6409E-02	2.0377E-02	1.1022E-02	RCGA_4: 0.9106
F14	Best	4.3468E-02	5.6481E-02	5.5495E-02	5.8646E-02	$f=$ 9E-02
	Worst	1.2393E-01	1.4417E-01	1.9333E-01	1.2885E-01	RCGA_1: 3.0964
	Mean	7.7525E-02	9.1541E-02	1.0534E-01	9.4801E-02	RCGA_2: 3.7257
	Median	7.9802E-02	8.8802E-02	1.0709E-01	9.6875E-02	RCGA_3: 3.8998
	SD	1.8411E-02	2.1893E-02	2.8641E-02	1.8492E-02	RCGA_4: 3.7054
F15	Best	8.8924E-03	5.3915E-01	5.1528E-01	1.6793E+00	$f=$ 1E+01
	Worst	6.2272E+00	3.9038E+01	1.2417E+02	5.3960E+01	RCGA_1: 2.0009
	Mean	8.1831E-01	1.0284E+01	9.8324E+00	1.2833E+01	RCGA_2: 3.4850
	Median	3.4741E-01	6.6129E+00	6.3934E+00	9.4326E+00	RCGA_3: 3.0498
	SD	1.1713E+00	9.3415E+00	1.7295E+01	9.3854E+00	RCGA_4: 3.3822
F16	Best	3.4707E-06	1.3752E-04	1.7712E-04	2.3588E-04	$f=$ 1E-02
	Worst	1.6094E-03	1.3403E-02	7.3205E-03	7.9811E-03	RCGA_1: 0.9171
	Mean	2.6011E-04	2.2203E-03	1.4839E-03	1.5280E-03	RCGA_2: 1.2033
	Median	1.2233E-04	9.8888E-04	1.0353E-03	1.0838E-03	RCGA_3: 1.2533
	SD	3.4606E-04	2.8431E-03	1.3473E-03	1.4308E-03	RCGA_4: 1.0882
F17	Best	1.7289E-03	1.6871E-02	2.4440E-02	4.6613E-02	$f=$ 9E-02
	Worst	9.6015E-02	1.3906E-01	1.8849E-01	1.7763E-01	RCGA_1: 17.8048
	Mean	3.5551E-02	6.7995E-02	8.0440E-02	9.9018E-02	RCGA_2: 23.5558
	Median	3.3012E-02	6.2236E-02	8.3177E-02	9.2054E-02	RCGA_3: 23.7144
	SD	1.8597E-02	2.7310E-02	2.9857E-02	3.3882E-02	RCGA_4: 29.2414
F18	Best	$-$ 5.2709E-03	$-$ 5.2609E-03	$-$ 5.2616E-03	$-$ 5.1952E-03	$f=$ 1E-03
	Worst	$-$ 5.1261E-03	$-$ 3.5454E-03	$-$ 4.5717E-03	$-$ 3.6379E-03	RCGA_1: 1.2867
	Mean	$-$ 5.2430E-03	$-$ 4.9840E-03	$-$ 5.1082E-03	$-$ 4.9330E-03	RCGA_2: 1.3393
	Median	$-$ 5.2495E-03	$-$ 5.0978E-03	$-$ 5.1556E-03	$-$ 5.0118E-03	RCGA_3: 1.6387
	SD	2.9783E-05	3.1719E-04	1.6088E-04	2.7914E-04	RCGA_4: 1.4043
F19	Best	6.1701E-02	1.2580E-01	1.7220E-01	1.6236E-01	$f=$ 5E-01
	Worst	2.0017E-01	3.5779E-01	3.8270E-01	3.5779E-01	RCGA_1: 0.8989
	Mean	1.2586E-01	2.4596E-01	2.5679E-01	2.6149E-01	RCGA_2: 1.0402
	Median	1.1965E-01	2.5054E-01	2.5179E-01	2.6692E-01	RCGA_3: 1.2938
	SD	3.3738E-02	5.3212E-02	4.5217E-02	5.3069E-02	RCGA_4: 1.0325
F20	Best	8.2708E-02	8.6420E-02	9.8661E-02	6.5130E-02	$f=$ 5E-01
	Worst	2.2819E-01	3.1357E-01	2.7186E-01	3.8097E-01	RCGA_1: 1.1123
	Mean	1.4986E-01	1.7165E-01	1.7005E-01	1.7101E-01	RCGA_2: 1.4381
	Median	1.4697E-01	1.6611E-01	1.6764E-01	1.6107E-01	RCGA_3: 1.2785
	SD	3.3389E-02	5.4178E-02	4.0004E-02	5.9919E-02	RCGA_4: 1.1764

Functions	Bound	$f_{\min}$
Unimodal functions
SF01	Shifted sphere function	[ $-$ 100, 100]	$-$ 450
SF02	Shifted Schwefel’s problem 1.2	[ $-$ 100, 100]	$-$ 450
SF03	Shifted rotated high conditioned elliptic function	[ $-$ 100, 100]	$-$ 450
SF04	Shifted Schwefel’s problem 1.2 with noise in fitness	[ $-$ 100, 100]	$-$ 450
SF05	Schwefel’s problem 2.6 with global optimum on bounds	[ $-$ 100, 100]	$-$ 310
Multi-modal functions
Basic functions
SF06	Shifted Rosenbrock’s function	[ $-$ 100, 100]	390
SF07	Shifted rotated Griewank’s function without bounds	[0, 600] ${}^{\rm a}$	$-$ 180
SF08	Shifted rotated Ackley’s function with global optimum on bounds	[ $-$ 32, 32]	$-$ 140
SF09	Shifted Rastrigin’s function	[ $-$ 5, 5]	$-$ 330
SF10	Shifted rotated Rastrigin’s function	[ $-$ 5, 5]	$-$ 330
SF11	Shifted rotated Weierstrass function	[ $-$ 0.5, 0.5]	90
SF12	Schwefel’s problem 2.13	[ $-\pi,\pi$ ]	$-$ 460
Expanded functions
SF13	Expanded extended Griewank’s plus Rosenbrick’s function	[ $-$ 3, 1]	$-$ 130
SF14	Expanded rotated extended Schaffer’s F6	[ $-$ 100, 100]	$-$ 300

Function	RCGA_1	RCGA_2	RCGA_3	RCGA_4
SF01	2.4535E-04	1.2425E-03	5.6058E-04	1.3480E-03
SF02	3.0835E+02	3.9315E+02	4.4657E+02	3.8517E+02
SF03	8.2889E+06	8.5973E+06	8.2009E+06	7.8483E+06
SF04	2.2266E+03	3.3562E+03	3.3590E+03	3.8288E+03
SF05	5.8841E+03	6.7008E+03	7.4412E+03	6.8651E+03
SF06	3.1434E+02	1.4389E+02	1.0177E+03	2.0967E+02
SF07	4.6963E+03	4.6963E+03	4.6963E+03	4.6963E+03
SF08	2.0888E+01	2.0762E+01	2.0805E+01	2.0790E+01
SF09	1.2834E-04	7.0116E-04	4.7730E-04	8.1560E-04
SF10	8.1530E+01	8.0385E+01	7.6692E+01	7.6831E+01
SF11	2.5942E+01	2.6362E+01	2.7465E+01	2.8712E+01
SF12	2.7307E+04	2.1456E+04	2.5743E+04	1.9408E+04
SF13	1.3224E+00	1.3072E+00	1.2832E+00	1.2574E+00
SF14	1.2903E+01	1.3104E+01	1.3167E+01	1.3076E+01

This has been conducted on a set of twenty classical benchmark functions with different features and complexity levels. The mathematical expressions of those test functions are given in Table 1. The dimensionality ( $d$ ) of all the test functions is considered as 30.

4.1.1 Parameters’ settings

The common parameters for all the RCGAs, such as population size, maximum number of fitness evaluations, probability of crossover, mutation probability, user index parameter for SBX and polynomial mutation, are kept the same and the selected values of these parameters are given in Table 2. It is to be noted that the stopping criterion for each RCGA is kept as the maximum number of objective function evaluations.

Apart from these common parameters of the RCGAs, others special parameters for RCGA_1, RCGA_2 and RCGA_3 are as follows.

RCGA_1: The values of the parameters $m_{\textit{threshold}}$ and $th\_\textit{count}$ are taken as 40 and 80, respectively.

RCGA_2: If there is no improvement found on the best solution for a total of 40 numbers of consecutive generations, the algorithm prepares for a restart. At the beginning of the next evolution, one copy of the elite solution from the last generation will be transferred to the initial population and the rest are created randomly.

RCGA_3: After each 40 generations, the algorithm is going to restart. During restart, 20% of solutions (which is equal to ten for this case) have been chosen randomly from the old population and the remaining 80% of solutions (i.e., 40) have been generated randomly. This mixture of solutions will be the initial population for the next evolution of the GA.

All the RCGAs have been run for 50 times for each of the test problems and the best solution obtained after each run has been captured. For a particular function, the initial population of solutions (for the very first evolution only) is kept the same in each run and this has been done using a fixed seed value, while generating the initial population. Here, one thing is to be noted that during the restart, the initial population of solutions is taken as different from that of the very first evolution. From the obtained results, the best, worst, mean, median and standard deviation values are calculated for each of the test functions and they are given in Table 3 (the best values are written in bold). In addition, to make a comparison of the convergence rates of the RCGAs, a time study has been performed, where we basically have observed the average CPU time needed for reaching a particular objective function value ( $f$ ) in 50 runs for a test function. All these computations have been carried out on Intel i5 processor with 3.20 GHz and 16 GB RAM under Windows 10 platform. The algorithms have been coded using MATLAB 2017a programming language.

From the results (refer to Table 3), the mean values of the test functions yielded by the RCGA with the proposed restart strategy (i.e., RCGA_1) are found to be the better than that of the other RCGAs for seventeen out of twenty benchmark functions. Nevertheless, RCGA_1 has been seen to be the best performer in the time-study for all the test functions except F11 and F13. These results clearly show that the RCGA with the proposed restart strategy has the better search capability, convergence rate, and it is computationally less expensive compared to that of the other RCGAs. These said facts about the RCGA_1 have also been firmly established by the convergence graphs (refer to Figs 2–4) of the test functions used in this experiment. Each graph denotes the variations of the average objective function values (out of 50 runs) with that of the number of fitness evaluations for a particular function for all the RCGAs.

The reason behind the remarkably good performance of the RCGA with the proposed restart strategy lies with the fact that it has a superior capability to maintain a proper balance between the population diversity and selection pressure compared to that of the others. Nevertheless, it can track and avoid the problem of premature convergence of the algorithm. In addition, whenever the algorithm is found to be trapped in a locally optimum basin, the RCGA with the proposed restart strategy has the better capability to overcome the problem than that of a standard RCGA, as the proposed restart strategy will be able to incorporate more diversity in the population compared to a normal mutation operator.

4.2 The second experiment

In the second experiment, we have chosen 14 test problems from the CEC’2005 special session on real parameter optimization [30]. These problems have different features, such as separability, scalability and multi-modality. The said functions were generated from the classical benchmark functions by applying different techniques, such as rotating, shifting or hybridizing. These operations had incorporated extra complexities into these test functions to be solved. The descriptions of these test problems have been provided in Table 4. In addition, the detailed descriptions with the mathematical expressions of these test functions are available at www.ntu.edu.sg/home/EPNSugan.

In this said experiment, the dimensionality of all the problems has taken as 30 and the parameters used for all the four RCGAs are kept the same to that of the first experiment. Nevertheless, similar to that of the previous experiment, each test functions has been evaluated for 50 times using all the RCGAs and the best solution obtained after each run has been recorded. Next, we have calculated the function error, which is nothing but the difference between the obtained best fitness and the true globally optimum value (refer to Table 4), after each run. Then, an average function error (out of 50 runs) has been calculated for each of the test problems and these results are given in Table 5 (the best results are written in bold).

The RCGA with the proposed restart strategy(RCGA_1) has performed better than other RCGAs for the eight functions out of 14 functions (refer to Table 5). In another words, RCGA_1 is able to yield the best results for nearly 57% of the total problems used in this experiment. This superior performance of RCGA_1 again clearly indicates that this has more efficient global and local search capabilities to locate the globally optimum solution of a problem. In addition, the restart conditions of the proposed strategy have been designed so wisely that it is able to yield the better results compared to other strategies for most of the cases, which comprise of more complex unimodal and multi-modal optimization problems.

Similar to that of the first experiment, we have represented graphically the convergence behaviors of all four RCGAs in Figs 5 and 6 for all the 14 test functions, as given in Table 4. For the test functions, such as SF01, SF02, SF04, SF05, SF07, SF09, SF11 and SF14, the RCGA with the proposed restart strategy has shown the better convergence behavior compared to that of the other ones. From these results, it is needless to say that the performance of an RCGA with the proposed restart strategy has been significantly improved in comparison with that of a standard RCGA and the RCGAs with other restart strategies.

5. Conclusion

In this paper, a novel restart strategy has been proposed for a genetic algorithm for the improvement of its performance. This proposed strategy for restart is comprised of three restart conditions and whenever, any one of these conditions is found to be fulfilled, the algorithm gets restarted. The first restart condition basically helps the algorithm to come out of the locally optimum basin, if any. On the other hand, with the application of the second one, the algorithm tries to maintain a proper balance between the exploration and exploitation capabilities of the GA. Nevertheless, the third condition is applied to detect and overcome a premature condition of an algorithm during its evolution. To measure the performance of a real-coded genetic algorithm (RCGA) with the proposed restart strategy, two sets of experiments have been carried. In the first experiment, a set of twenty classical test functions with different characteristics has been taken and then, the results have been produced using four different RCGAs. From the results, it has been found that the RCGA with our proposed restart strategy has yielded the better performance than that of the remaining three RCGAs for most of the test functions.

In addition, a time study has also revealed the fact that the RCGA with the proposed restart strategy is computationally less expensive, and consequently, it has the faster convergence rate compared to that of other ones. Similarly, in the second experiment, 14 functions have been chosen from the list of CEC’05 benchmark problems and these functions have been tested using the said four RCGAs. In this case also, we have found that the RCGA with the proposed restart strategy has performed better than the others. From these experimental results, it is clear that the performance of an RCGA with the proposed restart strategy has improved to a considerable amount for a variety of test functions with different characteristics.

References

Ezzeddine

A.B.

Lóderer

Laurinec

Vrablecová

Rozinajová

Lucká

Lacko

and Grmanová

, Using biologically inspired computing to effectively improve prediction models, International Journal of Hybrid Intelligent Systems 13(2) (2016), 99–112.

Ali

A.F.

and Tawhid

M.A.

, Hybrid bat algorithm and direct search methods for solving minimax problems, International Journal of Hybrid Intelligent Systems (2018), 1–15.

Das

A.K.

and Pratihar

D.K.

, A novel restart strategy for solving complex multi-modal optimization problems using real-coded genetic algorithm, in: ISDA 2017, A. A et al., eds, Delhi, India (2017), pp. 32–41.

Fahimnia

Luong

and Marian

, Optimization/simula-tion modeling of the integrated production-distribution plan: An innovative survey, WSEAS Transactions on Business and Economics 5(3) (2008), 52–65.

Boender

C.G.E.

and Romeijn

H.E.

, Stochastic methods, in: Handbook of Global Optimization, Nonconvex Optimization and Its Applications Horst

and Pardalos

P.M.

, (eds), Boston, MA, 2 (1995), pp. 829–869.

C.-K.

and Li

, Test problem generator for unconstrained global optimization, Computers & Operations Research 51 (2014), 338–349.

Goldberg

D.E.

and Deb

, A comparative analysis of selection schemes used in genetic algorithms, in: Foundations of Genetic Algorithms 1 (1991), 69–93.

Pratihar

D.K.

, Realizing the need for intelligent optimization tool, in: Handbook of Research on Natural Computing for Optimization Problems, IGI Global, (2016), 1–9.

Pratihar

D.K.

and Pratihar

, A review on applications of soft computing in design and development of intelligent autonomous robots, International Journal of Hybrid Intelligent Systems 14(1-2) (2017), 49–65.

10.

Ghannadian

Alford

and Shonkwiler

, Application of random restart to genetic algorithms, Information Sciences 95(1-2) (1996), 81–102.

11.

Beligiannis

G.N.

Tsirogiannis

G.A.

and Pintelas

P.E.

, Restartings: A technique to improve classic genetic algorithms’ performance, in: International Conference on Computational Intelligence (2004), 404–407.

12.

Eid

H.F.

and Abraham

, Plant species identification using leaf biometrics and swarm optimization: A hybrid PSO, GWO, SVM model, International Journal of Hybrid Intelligent Systems 14(3) (2017), 155–165.

13.

Rechenberg

, Evolutionsstrategie – Optimierung technisher Systeme nach Prinzipien der biologischen Evolution, (1973).

14.

Hughes

J.A.

Houghten

and Ashlock

, Recentering and restarting a genetic algorithm using a generative representation for an ordered gene problem 1, International Journal of Hybrid Intelligent Systems 11(4) (2014), 257–271.

15.

Holland

J.H.

, Adaptation in natural and artificial systems, an introductory analysis with application to biology, control, and artificial intelligence, MIT Press, Cambridge, MA, USA, 1992.

16.

De Jong

K.A.

, Analysis of the behavior of a class of genetic adaptive systems, Ph.D. Dissertation, University of Michigan, 1975.

17.

Dantu

Berman

Kate

and Nagpal

, A comparison of deterministic and stochastic approaches for allocating spatially dependent tasks in micro-aerial vehicle collectives, in: Intelligent Robots and Systems (IROS 2012), Portugal (2012), 793–800.

18.

Deb

, An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering 186 (2000), 311–338.

19.

Deb

and Goyal

, A combined genetic adaptive search (GeneAS) for engineering design, Computer Science and Informatics 26 (1996), 30–45.

20.

Deb

and Agrawal

R.B.

, Simulated binary crossover for continuous search space, Complex Systems 9(3) (1994), 1–15.

21.

Suksut

Kerdprasop

and Kerdprasop

, Support vector machine with restarting genetic algorithm for classifying imbalanced data, International Journal of Future Computer and Communication 6(3) (2017), 92–96.

22.

dos Santos Coelho

Ayala

H.V.H.

and Mariani

V.C.

, A self-adaptive chaotic differential evolution algorithm using gamma distribution for unconstrained global optimization, Applied Mathematics and Computation 234(C) (2014), 452–459.

23.

Fogel

L.J.

Owens

A.J.

and Walsh

M.J.

, Artificial intelligence through simulated evolution, Wiley, New York, 1966.

24.

Liberti

and Kucherenko

, Comparison of deterministic and stochastic approaches to global optimization, International Transactions in Operational Research 12(3) (2005), 263–285.

25.

Dorigo

, Optimization, learning and natural algorithms, PhD Thesis, Politecnico di Milano, Italie, 1992.

26.

Mahmoodabadi

M.J.

Safaie

A.A.

Bagheri

and Nariman-Zadeh

, A novel combination of particle swarm optimization and genetic algorithm for pareto optimal design of a five-degree of freedom vehicle vibration model, Applied Soft Computing 13(5) (2013), 2577–2591.

27.

Shahlaei

Madadkar-Sobhani

Saghaie

and Fassihi

, Application of an expert system based on genetic algorithm – adaptive neuro-fuzzy inference system (GA-ANFIS) in QSAR of cathepsin K inhibitors, Expert Systems with Applications 39(6) (2012), 6182–6191.

28.

Metropolis

Rosenbluth

A.W.

Rosenbluth

M.N.

Teller

A.H.

and Teller

, Equation of state calculations by fast computing machines, The Journal of Chemical Physics 21(6) (1953), 1087–1092.

29.

Gupta

Sharma

T.K.

and Mehrotra

, Implementation of genetic algorithm for developing knowledge centric environment in higher education, International Journal of Hybrid Intelligent Systems 14(1-2) (2017), 13–19.

30.

Suganthan

P.N.

Hansen

Liang

J.J.

Deb

Chen

Y.-P.

Auger

and Tiwari

, Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization, Technical Report, Nanyang Technological University, Singapore and KanGAL Report Number 2005005 (Kanpur Genetic Algorithms Laboratory, IIT Kanpur), 2005.

31.

Eberhart

and Kennedy

, A new optimizer using particle swarm theory, in: Proceedings of the Sixth International Symposium on Micro Machine and Human Science, MHS’95 (1995), 39–43.

32.

Reynolds

R.G.

, An introduction to cultural algorithms, in: Proceedings of The Third Annual Conference on Evolutionary Programming, Singapore, (1994), 131–139.

33.

Storn

and Price

, Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization 11(4) (1997), 341–359.

34.

AkpıNar

Bayhan

G.M.

and Baykasoglu

, Hybridizing ant colony optimization via genetic algorithm for mixed-model assembly line balancing problem with sequence dependent setup times between tasks, Applied Soft Computing 13(1) (2013), 574–589.

35.

Dao

S.D.

Abhary

and Marian

, An improved structure of genetic algorithms for global optimisation, Progress in Artificial Intelligence 5(3) (2016), 155–163.

36.

Wang

Huang

Dong

W.S.

Yan

J.C.

Tian

C.H.

and Mo

W.T.

, Two-stage based ensemble optimization framework for large-scale global optimization, European Journal of Operational Research 228(2) (2013), 308–320.

37.

Yun

Chung

and Moon

, Hybrid genetic algorithm approach for precedence-constrained sequencing problem, Computers & Industrial Engineering 65(1) (2013), 137–147.