Abstract
Evolutionary Algorithms (EA) are robust optimization approaches which have been successfully applied to a wide range of problems. However, these well-established metaheuristic strategies are computationally expensive because of their slow convergence rate. Opposition Based Learning (OBL) theory has managed to alleviate this problem to some extent. Through simultaneous consideration of estimates and counter estimates of a candidate solution within a definite search space, better approximation of the candidate solution can be achieved. Although it addresses the slow convergence rate to some extent, it is far from alleviating it completely. The present work proposes a novel approach towards improving the performance of OBL theory by allowing the exploration of a larger search space when computing the candidate solution. Instead of considering all the components of the candidate solution simultaneously, the proposed method considers each of component individually and attempts to find the best possible combination by using a metaheuristic technique. In the present work, this improved Opposition learning theory has been integrated with the classical HS algorithm, to accelerate its convergence rate. A comparative analysis of the proposed method against classical Opposition Based Learning has been performed on a comprehensive set of benchmark functions to prove its superior performance.
Introduction
Evolutionary Algorithms (EA) are robust optimization approaches which have been successfully applied to a wide range of nonlinear and complex problems [1, 2]. Despite the widespread success of these stochastic optimization strategies, the slow convergence rate of EAs render them infeasible for real world problems. The concept of Opposition Based Learning (OBL) [3] extended existing EAs by considering both guesses and counter or opposite guesses [4] of a candidate solution to improve the convergence rate of the learning algorithm. In absence of sufficient apriori knowledge about the problem to be solved, traditional learning often begins with a random guess, estimating the solution. Evidently, if the random estimate happens to be in the vicinity of the optimal solution, convergence of the learning algorithm to the global optimum may be fast. However, in the worst case scenario, if the initial random guess happens to be in the opposite location [3] with respect to where the global optimum resides in the search space, approximation or optimization may become so much time consuming that it might prove to fail the purpose. Instead of resorting to pure randomness, OBL theory [3] considers both the candidate solution and its corresponding opposite [3] number simultaneously at each iteration of a learning algorithm, before deciding upon the new search direction in the decision space. Even though using OBL theory has shown some improvement in the convergence rate of EA, OBL theory conducts the exploration process in a comparatively restricted search space. The present work highlights the fact that the definition of traditional opposite points presented in [3] confines the exploration process of the learning algorithm to a single hyper plane, which consequently limits the search space significantly. In this paper, a novel Improved Opposition based Learning (IOBL) theory has been proposed which attempts to improve the search capabilities of the traditional OBL theory. The present work considers each of the vector components of the candidate solution individually and tries to find the best possible combination of such individual components and their corresponding opposite component. Since the task of finding such a combination is NP-hard, a meta-heuristic approach has been taken up to address this problem.
Even though there exists several kinds of EA in literature [5, 6], a music based metaheuristic named Harmony Search (HS) [7] algorithm has been utilized for accentuating the computational power of the proposed IOBL theory. HS algorithm has some pronounced advantages over other renowned meta-heuristics, some of them being its derivative-free framework, meager decision parameters and not entailing the need for auxiliary information. The simple implementation of HS algorithm, its ability to avoid getting trapped in local minima and not requiring differential gradients constitute some of the reasons for the widespread popularity of this music improvisation-mimicking metaheuristic. HS algorithm has been used for a wide range of applications which have covered many areas including Power Systems [8], Water Network Design [9], Energy Dispatch System [10] and Structural Design [11] etc. The stated merits of HS algorithm assists in ameliorating its flexibility thus, making it an apt test case for our experimental setup. The main steps of a HS algorithm have been outlined in Fig. 1. However, amidst several advantages, the slow convergence speed of HS thwarts its applicability to many real world problems.
A novel Harmony Search algorithm (IOHS) employing the proposed IOBL theory can be cited as the main contribution of the present work. Performance of the proposed method has been evaluatedon a comprehensive test suite of fourteen benchmark functions. A comparative analysis has also been performed with traditional OBL theory to prove the superiority of the proposed method.
Rest of the paper has been organized as follows: Section 2 discusses Opposition Based Learning Theory, Section 3 details the present work, Section 4 reviews the experimental results and finally, Section 5 presents a brief conclusion.
Opposition Based Learning Theory (OBL)
The concepts of Opposition Based Learning (OBL) was introduced by Tizhoosh et al. [3] in 2005. The simultaneous consideration of a candidate estimate and its counter [4] estimate assists in exploring a larger search space which corresponds to the generation of the best possible candidate solution. A brief introduction to OBL Theory has been provided in this section.
Definition
Let us consider a real number v i.e., v ∈ R defined on an interval [m, n] i.e., v ∈ [m, n]. The opposite number is mathematically defined as:
Definition of the opposite number for a multi-dimensional space can be stated as follows:
Let X (v1, v2, v3 … v
N
) represent a point in N-dimensional space with coordinates v1, v2, v3 … v
N
∈ R such that v
i
∈ [m
i
, n
i
] and i∈ { 1, 2, 3 … . N }. Opposite point can be expressed as:
Let us assume that g (.) is an evaluation function, v ∈ [m1, n1] is an initial random guess and is its corresponding counter guess. As shown in Fig. 2, g (v) and are computed in every iteration of the algorithm and the fitter estimate is selected for the subsequent iteration of the learning procedure. The search space is recursively halved based on the contiguity of the estimate v and corresponding counter estimate with respect to the existing solution v0. A graphical overview of OBL Theory has been presented in Fig. 2.
Proposed methodology
As stated earlier, OBL theory owes its enhanced exploration capabilities to the computation of opposite numbers of a candidate solution in each iteration of the learning algorithm. There exists several Opposition based EAs [12, 13] in literature which shed light on the computational prowess of traditional OBL Theory. Even though this learning scheme assists in abating the convergence issue in EAs, the concept of classical opposite points restrict the search space to a single hyper plane. The proposed approach builds upon traditional OBL and attempts to increase its search potentialities. By taking into account multiple search directions, the present work elevates Opposition based EAs to an altogether new level. The main motivation behind the current work is to add new dimensions to the core concept of OBL Theory and to accentuate the convergence rate of EAs. To further illustrate the effectiveness of the current work, this novel strategy has been integrated with the basic variant of HS Algorithm and the experimental results reveal that this integration succeeds in surpassing traditional HS algorithm in terms of the convergence rate.
The Improved Opposition-based Algorithm(IOBL)
As opposed to traditional OBL theory, the proposed algorithm acknowledges each vector constituent of the candidate solution separately and strives to discover the best possible combination of these individual components and their corresponding counter components. A metaheuristic based approach can be taken to consider all of the possible combinations of candidate vector components and their corresponding opposite components within affordable time. Amidst several Eas [5, 6], HS algorithm has attracted the attention of practitioners all over the world owing to its powerful infrastructure and implementation ease. In few cases, HS has even been proved to outperform [14] the Genetic Algorithm (GA) [15]. Thus, HS algorithm has been employed in this paper to obtain the optimal oppositional candidate vector within a reasonable time constraint.
A novel harmony search based improved Opposition learning (IOBL) algorithm has been presented in this paper. The parameter Opposition Probability (OProb) denotes the Opposition Probability i.e., the probability of computing the improved Opposition Learning based counter of a candidate solution estimate. Higher the value of OProb, higher the possibility of performing improved Opposition-based Learning (IOBL) on a potential candidate vector. In the present work, the value of OProb has been set to 0.9 empirically. Hence, the proposed IOBL technique calculates the improved counter estimate of a selected harmony in lieu of the familiar Pitch Adjustment routine found in classical HS algorithm.
The proposed algorithm then moves on to the selection of a random harmony HR from OHM depending on the parameter HMCR. Next, itis examined whether the proposed improved counter of the selected harmony HR will be computed. Based on the Opposition Probability (OProb) as stated above, a random number r is generated in the range {1 … d } , d being the dimensionality of OHM vectors. r randomly selected components of the chosen vector HR are considered and improved counter (HR′) is obtained by performing the opposition of only the chosen r components. That is, is computed for all randomly selected vector components i∈ { 1 … d } where [m i , n i ] denotes the range of vector component i of HR. Using this operation, all possible combinations of the vector constituents and their individual opposite components are traversed, thus exploiting a greater amount of search-space at each iteration of the learning algorithm. Finally, this improvised harmony HR replaces the worst harmony HR worst in OHM if it is found to be better suited on the basis of a fitness score. These steps are reiterated until a pre-specified termination criterion has been reached. Algorithm 1 entails the pseudo code of the proposed algorithm while Fig. 3 outlines the major steps of the same.
Begin Initialize the following parameters: Harmony Memory size (n), Dimensionality of the Harmony Memory vectors (d), Harmony Memory Consideration Rate (HMCR), Opposition Probability (OProb), Evaluation function (g (.)) and Maximum number of generations (Max). Set the current generation number (GEN) to zero. Randomly initialize the improved Opposition learning based Harmony Memory OHM (n) ={ H1, H2 … H
n
}. Let each harmony H
k
denote a d-dimensional vector such that each jthvector component of H
k
i.e. H
jk
is bounded by a real valued interval [m
j
, n
j
] ie., H
jk
∈ [m
j
, n
j
] where jɛ [1, 2 … . d]. while (GEN < Max) { /*Random Selection of a harmony bfitHR from improved Opposition Learning based Harmony Memory bfitOHM*/ if (rand (0, 1) < HMCR) { Randomly choose a harmony HR from OHM (n). if (rand (0, 1) < OProb) { /*Performing improved Opposition-based Learning*/ Generate a random number in the range {1… d }. Let us denote the generated number by r. Randomly select r vector components from the selected d-dimensional harmonyHR. Let us store the selected vector components in Comp (r). Compute HR′, the improved opposition-based d-dimensional counter vector of selected harmony HR. HR′ is obtained from HR by computing the counter of only the vector components stored in Comp (r). HR = HR′ } else { Compute fitness values of each candidate vector in OHM (n). Let us denote the worst and best harmony in OHM (n) by HR
worst
and HR
best
respectively. HR = HR
best
± rand (0, 1) * (HR
best
- HR
worst
) } } Calculate the fitness value of each harmony in the current Harmony Memory (OHM (n)). Let us denote the worst harmony by HR
worst
. Compare the fitness value of HR and HR
worst
. Replace HR
worst
in OHM (n) by HR if HR is found to be better suited. GEN = GEN + 1 } Evaluate the fitness score of every harmony in OHM (n). Return the best solution and its corresponding fitness value. End
How IOBL theory works
For better understanding of the enhanced search space potentialities of the proposed IOBL Theory, the concept of reflecting hyper planes has been introduced in this section. It should be noted that a two dimensional solution space has been assumed in Fig. 4 primarily for the sake of simplicity.
Let us consider S (x1, x2) to be a point in two-dimensional space where x1, x2ɛR and x i ɛ [lb i , ub i ] for iɛ{ 1, 2 }. As shown in Fig. 4, the search space explored by S is limited solely to the diagonal when classical OBL theory is considered. However, while computing the improved counter estimate of S, the proposed IOBL theory acknowledges multiple search directions as well as . Thus, the increase in the amount of solution space exploited by IOBL Theory results into a marked improvement in the convergence speed of HS algorithm.
The proposed IOHS algorithm
In order to demonstrate the computational potency of the proposed methodology, the IOBL theory has been integrated with classical HS algorithm which, as the experimental results unveil, leads to a marked improvement in the convergence rate of this popular global search meta-heuristic.
First, the classical HS based harmony memory (HM) is initialized with random solution estimates. After performing the familiar harmony selection, pitch adjustment and randomization routine on HM, a parameter named Jumping Rate (JR
Gen
) is computed as given below:
In the present work, parameter JR Gen has been made adaptive with the current HM i.e., as the search proceeds, the need for dynamic generation jumping diminishes. Based on this computed JR Gen , instead of following in the footsteps of the traditional evolutionary mechanisms in every generation, a randomly chosen harmony H from the current HM can be forced to select a fitter candidate between itself and its corresponding improved Opposition learning based counter H o (obtained using the proposed IOBL algorithm as given in Algorithm 1). The fitter estimate between H and H o denoted by H fit , replaces the worst harmony H worst in the current HM if found to be fitter than the latter. The complete pseudo code of the classical HS algorithm embedded with the proposed IOBL algorithm has been provided in Algorithm 2 while the major steps have been outlined in the flowchart given in Fig. 5.
Begin Initialize the following parameters: Harmony Memory Size (size), Harmony Memory Consideration rate (HMCR), Minimum value of Pitch adjustment rate (PARmin), Maximum value of Pitch adjustment rate (PARmax), Pitch Bandwidth (BW), Minimum value of population jumping-rate (JR min), Maximum value of population jumping-rate (JR max) and Maximum number of generations (MAX). Set the current generation counter (Gen) to zero. /*Harmony Memory Initialization*/ Randomly generate the Harmony Memory HM (size) ={ H1, H2 … H
size
}. Let each harmonyH
k
represent a d-dimensional vector and thejthvector component of harmony H
k
i.e. H
jk
ɛ [m
j
, n
j
] where jɛ [1, 2 … . d]. while (Gen < MAX) { /*Random Selection of a harmony from Harmony Memory bfitHM*/ if (rand(0,1) <HMCR) { Randomly choose a harmony H from Harmony Memory HM (size). Compute if (rand(0,1) <PAR) { /*Performing Pitch Adjustment on selected Harmony bfitH*/ Compute H = H ± rand (0, 1) * BW } else { Compute fitness values of each candidate vector in HM (size). Let us denote the worst and best harmony in HM (size) by H
worst
and H
best
respectively. H = H
best
± rand (0, 1) * (H
best
- H
worst
) } } Calculate the fitness value of each harmony in the current Harmony Memory (HM (size)). Denote the worst harmony by H
worst
Compare the fitness value of H and H
worst
. Replace H
worst
in HM (size) by H if H is found to be better suited. /*Compute the value of population jumping rate for the current generation*/ Compute if(rand(0,1)<JR
Gen
) { /*Perform dynamic opposition-based generation jumping*/ Randomly choose a harmony H from the current Harmony Memory HM (size). Let H
O
denote the optimal d-dimensional counter candidate vector obtained using IOBL algorithm (as shown in Algorithm 1). Calculate the fitness value of H and H
O
. Denote the fitter candidate vector by H
fit
. Calculate the fitness value of each harmony in the current Harmony Memory (HM (size)). Denote the worst harmony by H
worst
. Compare the fitness value of H
fit
and H
worst
Replace H
worst
in HM (size) by H
fit
if H
fit
is found to be better suited. } /*End of dynamic opposition-based generation jumping*/ Gen = Gen + 1 } Evaluate the fitness score of every harmony in Harmony Memory HM (size). Return the best solution and its corresponding fitness value. End
The present work aims to highlight the computational superiority of the proposed IOBL theory embedded HS algorithm (IOHS).
Table 1 comprises the parameter values of the proposed IOHS algorithm. It should be mentioned that the experiments have been performed on an IntelR CoreTM i5-2400 processor with clock frequency of 3.10 GHz and 8 GB RAM.
Test suite used to evaluate the proposed IOHS algorithm
After a careful review of relevant literature [16, 17], a comprehensive set of 14 benchmark functions have been used as the test suite of the current experimental setup. These widely used benchmark functions are all minimization problems. Definitions of these test functions have been listed in Table 2. More details can be found in [16, 17].
A comparative analysis between Opposition based HS algorithm (OHS) and IOHS algorithm
A comparative analysis has been performed between the classical Opposition based HS algorithm (OHS) [18] and the proposed IOHS algorithm to exemplify the superiority of the proposed method. The experimental results have been presented in Table 3. f m denotes the value of the benchmark functions when averaged over 20 trials, σ refers to the standard deviation while denotes the improvement obtained by the proposed algorithm when OHS is used as a competitor algorithm. From Table 3, it is evident that the proposed IOHS algorithm has shown significant improvement over the existing OHS algorithm in all the benchmark functions barring function F9.The concept of improved Opposition learning based counter renders greater flexibility during the exploration of the solution space which translates to an improved convergence rate for benchmark functions F1, F2, F3, F4, F5, F6, F7, F8, F10, F11, F12, F13 and F14.
There has been maximum improvement of 93.55% and minimum improvement of 0.001% for benchmark functions F7 and F11 respectively. However, deterioration in the convergence speed is evident for benchmark function F9. Global optimum for function F9 i.e. the sum of different powers function is located in a parabolic shaped basin encompassed by multiple local optima and the improved Opposition based counter focuses on one local optimum before converging to the global optimum.
The above experimental results portray a marked improvement in the aforementioned benchmark function values which alludes to a better exploitation of the search space.
Conclusion
A novel Harmony Search algorithm embedded with an improved Opposition based Learning theory has been proposed in this paper. As mentioned in the preceding sections, the attempt to discover an optimal combination of each individual component of a candidate solution vector and its corresponding opposite component contributes in escalating the search-space exploration credentials of the traditional OBL Theory. The proposed approach facilitates in bolstering the convergence rate of classical Harmony Search algorithm and evidently, builds a profound foundation for future research work. Researchers can exploit this novel strategy in future to improve the convergence speed of other reputed EAs namely Ant Colony Optimization [5], Particle Swarm Optimization algorithm [6] and even relatively new optimization methods such as Cuckoo Search algorithm [19], Firefly Optimization algorithm [20] etc. Thus, the present work inevitably proffers opportunities for promising ventures to embark on in the field of optimization.
Footnotes
Acknowledgments
The authors are also thankful to “Centre for Microprocessor Application for Training Education and Research” and Department of Computer Science & Engineering, Jadavpur University, Kolkata for kindly providing the resources and infrastructural facilities that helped to complete this work.