A lévy flight-based shuffled frog-leaping algorithm and its applications for continuous optimization problems
Graphical abstract
An expanded framework of shuffled frog-leaping algorithm for continuous optimization problem is performed according to the mechanism of exploration and exploitation, in which a lévy flight-based attractor was proposed. Experimental results show that our proposed algorithm has better performance than many state-of-the-art algorithms.
Introduction
Most continuous optimization problems involve in the science and engineering such as the image segmentation problems [1], artificial neural network
optimization problem [2], power system optimization problems [3], engineering design problems [4] etc. These problems can be described as followed:Where denotes the objective function, and present the inequality constraints or equality constraints, denotes the function variables, All variables have lower and upper bounds. Eqs. (1)–(4) means the constrained optimization problems, while Eqs. (1), (3), (4) without (2) present the unconstrained optimization problems. So, the constrained optimization problems can be seen as a special continuous optimization problems. Especially, many these problems are high dimensions and nonlinear. Traditional methods usually require substantial gradient information and seek to improve the solution in the neighborhood of a starting point. However, the gradient information of some problems can not be obtained easy and many problems are multimodal, it is to say, they have many local optimal solutions, which cause the traditional methods fail to solve these problems.
In recent years, many meta-heuristic optimization algorithms have been developed to solve these real life problems and obtained the better performance. Usually, these algorithms use a solution set (not one solution) to find the global optimum, they can be called the population-based algorithm. These algorithms can be divided into three categories [5]: evolutionary computation (evolutionary algorithms), swarm intelligence algorithms and physical phenomena algorithms. Evolutionary computation (EC) are inspired by the Darwinian principles of nature’s capability to evolve living beings well adapted to their environment. Some classical algorithms such as genetic algorithms [6], evolution strategies [7], evolutionary programming [8], and genetic programming [9] which have been widely accepted and used in many research fields and applications. The common ideology of these algorithms is to imitate the individual’s evolution through mutation, selection and recombination operation. Inspired by this ideology, many new or improved evolutionary algorithms have been arose, including Estimation of Distribution Algorithms (EDA) [10], Differential Evolution (DE) [11], [12], [13], [14], Co-evolutionary algorithms (CoEA) [15], [16]. Differential evolution is popular due to its simple and better performance, have developed to many new versions such as differential evolution algorithm with strategy adaptation (SaDE) [11], [12], adaptive differential evolution (JADE) [14] and self-adapting control parameters in differential evolution (jDE) [17], compact differential evolution (cDE) [18] and differential evolution with composite trial vector generation strategies (CoDE) [19]. The second kind population-based algorithms are the swarm intelligence algorithms which are inspired by the foraging behaviors or growth or living in nature organisms. The classical two kind swarm intelligence algorithms are the ant colony optimization [20], [21] (ACO) and particle swarm optimization (PSO) [22]. The ant colony optimization, mimicking the ants foraging behaviors, is success on the combinatorial optimization problem and the particle swarm optimization inspired by the behavior of birds is success on the continuous optimization problems. According to the network structure of particles, some improved PSO versions have been proposed including the scale-free PSO (SFPSO) [23], the fully-informed PSO (FIPSO) [24], [25], comprehensive learning PSO (CLPSO) [26], the self-learning PSO (SLPSO) [26] and selectively-informed PSO (SIPSO) [27]. Inspired by the quantum theory, some quantum-behave PSO version have been proposed, such as the standard quantum-behaved particle swarm optimization (QPSO) [28], weighted quantum-behaved particle swarm optimization (WQPSO) [29], improved QPSO with two stage strategy (TSQPSO) [30] and QPSO with memetic algorithm and memory (SMQPSO) [31]. On the other hands, some new swarm intelligence algorithms have been proposed after the PSO. Passino introduced a bacterial foraging optimization algorithm (BFOA) [32] inspired by the social foraging behavior of Escherichia coli bacteria in 2002; Shuffled frog leaping algorithm (SFLA) which works on the principle of communication among the frogs [33]; the bee colony optimization metaheuristic (BCO) [34] and artificial bee colony algorithm (ABC) [35] were inspired by the honeybee’s balance exploitation of known food sources and exploration for new and potentially better food sources in a dynamic environment; Dan Simon et al. proposed Biogeography-based optimization algorithm (BBO), simulated the biological system under different environments, and balances the immigration and emigration of different species [36]; Inspired by the cuckoo brood parasitism behavior, Xin-she Yang et al. proposed the Cuckoo Search algorithm (CS) [37]; Bat algorithm (BA) [38] was inspired by the characteristics of the bats which emit ultrasound; Glowworm swarm optimization (GSO) [39] was inspired by the behaviors of a group of firefly which exchanges information by fluorescence. Teaching-learning-based optimization (TLBO) was proposed based on the effect of a teaching on the score of learners in a class [40]; Gray wolf optimizer (GWO) was proposed based on the behavior of capturing prey of the gray wolf swarm [5]; Tree-seed algorithm (TSA) [41] was proposed in 2015, which can be seen as a tree growth model based on the relation between trees and their seeds; Artificial algae algorithm (AAA) [42] is inspired by the living behaviors of microalgae, photosynthetic species; Invasive tumor growth optimization algorithm (ITGO) was inspired by the invasive behaviors of the tumor growth [43]. The third kind population-based algorithms are the physical phenomena algorithms, which mimic physical rules with some physical phenomena. The popular algorithms are gravitational search algorithm(GSA) [44], Gravitational Local Search (GLSA) [45], Black Hole(BH) algorithm [46], Big-Bang Big-Crunch (BBBC)[47], Central Force Optimization (CFO) [48].
Since shuffled frog-leaping algorithm (SFLA) was proposed by Eusuff and Lansey in 2003 [33], it has been paid more attentions. It can be seen as a memetic algorithm (MA) [49], which combined the memetic transfer mechanism and the search rule of PSO. In these years, it has been widely applied to the combinatorial optimization problems such as the traveling salesman problem (TSP) [50], grid task scheduling problem [51], economic dispatch problem [52], [57], resource-constrained project scheduling problem [53], [59], flow shop scheduling problem [54], [58], vehicle routing problem [55], 0/1 knapsack problem [56]. But there have been a few papers that have reported results of the application of the continuous optimization problems [60], [61]. So, the performance of shuffled frog-leaping algorithm for continuous optimization problem should be improved for many applications. In fact, the success of meta-heuristic methods to solve optimization problems depends on the balance of exploration(diversification) and the exploitation (intensification). However, the current versions of shuffled frog-leaping algorithm pay attention to the new search rule about the exploitation and did not improved the search rule of the exploration. In memetic framework of shuffled frog-leaping algorithm, memetic transfer method is considered as the exploration. In effect, more experiments have been verified that only using the memetic transfer method is not enough for the exploration because of the lose of the global search rule. In addition, the local search method should be improved for the exploitation, because the current versions of shuffled frog-leaping algorithm search in a spherical or square space, which causes it easily to fall into local optimum.
In this context, the first contribution of our work is that we expand the traditional framework of shuffled frog-leaping algorithm. The new framework depends on the balance of the exploration and the exploitation including three major elements: memetic transfer mechanism, global search rule for the exploration and the local search rule for the exploitation. The second contribution is that an ‘attractor’ with lévy flight was used to enhance the local search ability, in which, the lévy flight embedded attractors expand its search space unlimited in spherical or square space, that ensure the algorithm easily to escape the local optimum. The third contribution is that we use the interactive learning rule for the global search, which enhance the diversification of our algorithm.
In this paper, we proposed a lévy flight embedded shuffled frog-leaping algorithm (LSFLA). The rest of the paper was organized as follows. Section 2 introduces the traditional shuffled frog-leaping algorithm. Section 3 describes the improved algorithm. Related works were presented in Section 4; Section 5 presents experimental simulations compared with well-known meta-heuristic algorithms, results, and analysis. Finally, the work is concluded in Section 6.
Section snippets
Shuffled frog-leaping algorithm (SFLA)
The shuffled frog-leaping algorithm is a swarm intelligence algorithm that mimics the memetic evolution of a group of frogs which are seeking the best available foods using a simple search rule similar to the PSO. In shuffled frog-leaping algorithm, frogs can be seen as individuals with different ideas (memetics). They can communicate with each other and transfer their memetics (culture information). In order to achieve this task, the population is divided into some different frog memeplexes
Related works
Compared with the combinatorial optimization problems, the shuffled frog-leaping algorithm has been least applied in the continuous optimization problems due to the low search speed or accuracy etc. Though, some methods have been used to improve the performance of shuffled frog-leaping algorithm for continuous optimization problems. But these methods only pay attention on the local search rule, which cause the algorithm easy to fall into the local optimum. In effect, a
Improved SFLA
In order to improve the performance of the shuffled frog-leaping algorithm, we have expanded the traditional framework to finish the balance of (exploration and exploitation). There are two rules and one process in this new framework, in which a local search rule and a global search rule finish the updating tasks, and a shuffling process was used as the enhancement of the diversity. Details shown as Fig. 1. For the local search rule, we proposed a lévy flight-based attractors to search in
Experimental results and analysis
In order to verify the performance of the proposed algorithms (LSFLA), three group of experiments were arranged as follows: 1) Experiment on the benchmark data set for continuous optimization problems. 2) Experiment on the real-world constrained engineering optimization problems. 3). Experiment on the real-world unconstrained continuous optimization problems for the support vector machine. In experiments 1), we compare our proposed algorithm to the well-known 12 algorithms including SPSO2011,
Conclusions
In this paper, we proposed an improved version of the shuffled frog-leaping algorithm, called the lévy flight embedded shuffled frog-leaping algorithm (LSFLA). In order to improve the performance of the traditional shuffled frog-leaping algorithm such as the accuracy and convergence speed, we established an new search framework which expanded the traditional framework including the shuffling process, local search step and global search. Two new search rules are proposed for the local search and
Acknowledgements
This work is supported by the Guang Dong Provincial Natural fund project (2016A030310300), Drug-target interaction prediction method based on collaborative intelligent optimization; building of strong Guangdong Province for Chinese medicine scientific research (20141165); the Humanities and social science fund project for Guangdong Pharmaceutical University (RWSK201409); the Natural Science Foundation of China under Grant (No. 61501128); NSFC, Research on reasoning of behavior trust for
References (88)
- et al.
A hybrid cooperative-comprehensive learning based PSO algorithm for image v segmentation using multilevel thresholding
Expert Syst. Appl.
(2008) - et al.
Estimates of energy consumption in Turkey using neural networks with the teaching-learning-based optimization algorithm
Energy
(2014) - et al.
An application of artificial bee colony algorithm with least squares support vector machine for real and reactive power tracing in deregulated power system
Int. J. Electr. Power Energy Syst.
(2012) - et al.
Grey wolf optimizer
Adv. Eng. Software
(2014) Co-evolving parasites improve simulated evolution as an optimization procedure
Physica D
(1990)Artificial cooperative search algorithm for numerical optimization problems
Inf. Sci.
(2013)- et al.
A quantum-behaved particle swarm optimization with memetic algorithm and memory for continuous non-linear large scale problems
Inf. Sci.
(2014) - et al.
Cuckoo Search via Ĺevy Flights .Proceeings of World Congress on Nature & Biologically Inspired Computing
(2009) - et al.
Teaching-learning-based optimization: an optimization method for continuous non-linear large scale problems
Inf. Sci.
(2012) TSA Tree-seed algorithm for continuous optimization
Expert Syst. Appl.
(2015)
Artificial algae algorithm (AAA) for nonlinear global optimization
Appl. Soft Comput.
ITGO: invasive tumor growth optimization algorithm
Appl. Soft Comput.
GSA: a gravitational search algorithm
Inf. Sci.
Black hole: a new heuristic optimization approach for data clustering
Inf. Sci.
A new optimization method: big bang-big crunch
Adv. Eng. Softw.
An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem
Inf. Sci.
A shuffled frog-leaping algorithm for hybrid flow shop scheduling with two agents
Expert Syst. Appl.
A novel hybrid shuffled frog leaping algorithm for vehicle routing problem with time windows
Inf. Sci.
Modified shuffled frog leaping algorithm with genetic algorithm crossover for solving economic load dispatch problem with valve-point effect
Appl. Soft Comput.
Shengxian Xie An effective shuffled frog-leaping algorithm for multi-objective flexible job shop scheduling problems
Appl. Math. Comput.
An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem
Comput. Oper. Res.
An improved shuffled frog-leaping algorithm with extremal optimisation for continuous optimisation
Inf. Sci.
Example-based learning particle swarm optimization for continuous optimization
Inf. Sci.
A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms
Swarm Evol. Comput.
Nor ashidi mat isa, bidirectional teaching and peer-learning particle swarm optimization
Inf. Sci.
M.Č repinšek, A chess rating system for evolutionary algorithms: a new method for the comparison and ranking of evolutionary algorithms
Inf. Sci.
GSA: a gravitational search algorithm
Inf. Sci.
One-class support vector machine-an application in machine fault detection and classification
Comput. Ind. Eng.
Support vector machine with parameter optimization by a novel hybrid method and its application to fault diagnosis
Neurocomputing
Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems, Foundations of Fuzzy Logic and Soft Computing
Adaptation in Natural and Artificial Systems
Evolution Strategies: Optimierung Technischer Systeme Nach Prinzipien Der Biologischen Evolution
Heuristic Knowledge Discovery for Archaeological Data Using Genetic Algorithms and Rough Sets, Artificial Intelligence Laboratory, Department of Computer Science
Genetic Programming On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems)
From recombination of genes to the estimation of distributions I. Binary parameters
Self-adaptive differential evolution algorithm for numerical optimization
Proc. IEEE Congr. Evol. Comput.
Differential evolution algorithm with strategy adaptation for global numerical optimization
IEEE Trans. Evol. Comput.
Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces
J. Global Optim.
JADE: adaptive differential evolution with optional external archive
IEEE Trans. Evol. Comput.
Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems
IEEE Trans. Evol. Comput.
Compact differential evolution
IEEE Trans. Evol. Comput.
Differential evolution with composite trial vector generation strategies and control parameters
IEEE Trans. Evol. Comput.
Ant colony optimization-artificial ants as a computational intelligence technique
IEEE Comput. Intell. Mag.
The ant system: optimization by a colony of cooperating agents
IEEE Trans. Syst. Man Cybern.-Part B
Cited by (47)
Evolving Marine Predators Algorithm by dynamic foraging strategy for real-world engineering optimization problems
2023, Engineering Applications of Artificial IntelligenceLevy flight incorporated hybrid learning model for gravitational search algorithm
2023, Knowledge-Based SystemsA new flower pollination algorithm with improved convergence and its application to engineering optimization
2022, Decision Analytics JournalCitation Excerpt :In addition, scrutinizing the standard FPA reveals a lack of information sharing in its local pollination and, herein, this has brought to the formulation of an information exchange operator, where the concept of mutual collaboration from the frog leaping algorithm [28] was adopted. The frog leaping algorithm has the advantage of sharing information based on the combination of the search rule of PSO and the mechanism of memetic transfer [29,30]. Furthermore, the randomness in population initialization using the typical random method may allocate the initial solution to a sub-optimum region, leading to poor population diversity.
An enhanced fuzzy-based clustering protocol with an improved shuffled frog leaping algorithm for WSNs
2022, Expert Systems with ApplicationsImproved Lévy flight distribution algorithm with FDB-based guiding mechanism for AVR system optimal design
2022, Computers and Industrial Engineering