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.
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].
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.
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.
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 (
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 (
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
Threshold of Diversity Quotient (
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,
A set of twenty classical benchmark functions with their mathematical expressions
The task of selecting a suitable value for
Second condition: During a particular evolution, a GA is going to count the number of generations (say,
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
Third condition: This condition has already been explained as a special case during defining the maximum diversity quotient (
The common parameters for all the RCGAs
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.
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
Comparison of the results of all the RCGAs on test functions (F01–F20)
Convergence graphs of the RCGAs for the test functions: F01–F08.
Convergence graphs of the RCGAs for the test functions: F09–F16.
List of 14 benchmark problems from CEC’05 special session on real parameter optimization [30]
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.
Convergence graphs of the RCGAs for the test functions: SF01–SF08.
Convergence graphs of the RCGAs for the test functions: SF09–SF14.
Comparison of the average function errors obtained by the RCGAs
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 (
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
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 (
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.
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
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.
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.
