Elsevier

Applied Soft Computing

Volume 49, December 2016, Pages 641-662
Applied Soft Computing

A lévy flight-based shuffled frog-leaping algorithm and its applications for continuous optimization problems

https://doi.org/10.1016/j.asoc.2016.09.002Get rights and content

Highlights

  • A new framework of SFLA based on the exploration and exploitation mechanism was proposed to solve continuous optimization problems.

  • ‘Attractors’ based on the ‘lévy flight’ was proposed to enhance the local search ability of the proposed algorithm.

  • An interaction learning rule was proposed to improve the global search ability of the proposed algorithm.

  • Proposed algorithm was compared with many well-known algorithms to demonstrate that it is successful to solve the real-world unconstrained and constrained continuous optimization problems.

Abstract

Shuffled frog-leaping algorithm (SFLA), a novel meta-heuristic optimization algorithm inspired by the foraging behavior of frogs, has been widely applied to many areas for combination problems. But it is easy to fall into the local optimum especially for the continuous optimization problems. This paper proposed a novel variant of SFLA for the continuous optimization problems based on the expanded framework (called the lévy flight-based shuffled frog-leaping algorithm, LSFLA). In this new framework, the shuffling process, local search step and global search step are combined according to the exploration and exploitation mechanism. An lévy flight based attractor was adopted for the local search step, which enhance the local search ability of algorithm due to the search of short walking distance and occasionally longer walking distance. An interaction learning rule was used for the global search step, which enhances the exploration ability. In order to test the effectiveness of LSFLA, thirty benchmark functions, six real-world constrained continuous optimization problems and a real-world support vector machine (SVM) parameter optimization problem were compared to the many well-known heuristic methods. The experimental results demonstrate that the performance of our proposed algorithm is better than other algorithms for the continuous optimization problems.

Graphical abstract

  1. Download : Download high-res image (169KB)
  2. Download : Download full-size image

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:Min:y=f(x)Subjectto:g(x)=[g1(x),g2(x),...,gn(x)]0h(x)=[h1(x),h2(x),...,hm(x)]=0Where:x=[x1,x2,...,xd]XlixiuiWhere y denotes the objective function, g(x)and h(x)present the inequality constraints or equality constraints, x denotes the function variables, All xvariables have lower and upper bounds[li,ui]. 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)

  • S.A. Uymaz et al.

    Artificial algae algorithm (AAA) for nonlinear global optimization

    Appl. Soft Comput.

    (2015)
  • Deyu Tang

    ITGO: invasive tumor growth optimization algorithm

    Appl. Soft Comput.

    (2015)
  • E. Rashedi et al.

    GSA: a gravitational search algorithm

    Inf. Sci.

    (2009)
  • A. Hatamlou

    Black hole: a new heuristic optimization approach for data clustering

    Inf. Sci.

    (2013)
  • O.K. Erol et al.

    A new optimization method: big bang-big crunch

    Adv. Eng. Softw.

    (2006)
  • Ling Wang et al.

    An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem

    Inf. Sci.

    (2011)
  • Deming Lei et al.

    A shuffled frog-leaping algorithm for hybrid flow shop scheduling with two agents

    Expert Syst. Appl.

    (2015)
  • Jianping Luo

    A novel hybrid shuffled frog leaping algorithm for vehicle routing problem with time windows

    Inf. Sci.

    (2015)
  • Priyanka Roy et al.

    Modified shuffled frog leaping algorithm with genetic algorithm crossover for solving economic load dispatch problem with valve-point effect

    Appl. Soft Comput.

    (2013)
  • Junqing Li et al.

    Shengxian Xie An effective shuffled frog-leaping algorithm for multi-objective flexible job shop scheduling problems

    Appl. Math. Comput.

    (2012)
  • Chen Fang et al.

    An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem

    Comput. Oper. Res.

    (2012)
  • Xia Li

    An improved shuffled frog-leaping algorithm with extremal optimisation for continuous optimisation

    Inf. Sci.

    (2012)
  • H. Huang et al.

    Example-based learning particle swarm optimization for continuous optimization

    Inf. Sci.

    (2012)
  • J. Derrac et al.

    A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms

    Swarm Evol. Comput.

    (2011)
  • W.H. Lim

    Nor ashidi mat isa, bidirectional teaching and peer-learning particle swarm optimization

    Inf. Sci.

    (2014)
  • N. Veček et al.

    M.Č repinšek, A chess rating system for evolutionary algorithms: a new method for the comparison and ranking of evolutionary algorithms

    Inf. Sci.

    (2014)
  • E. Rashedi et al.

    GSA: a gravitational search algorithm

    Inf. Sci.

    (2009)
  • H.J. Shin et al.

    One-class support vector machine-an application in machine fault detection and classification

    Comput. Ind. Eng.

    (2005)
  • X.Y. Zhang et al.

    Support vector machine with parameter optimization by a novel hybrid method and its application to fault diagnosis

    Neurocomputing

    (2015)
  • D. Karaboga et al.

    Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems, Foundations of Fuzzy Logic and Soft Computing

    (2007)
  • J.H. Holland

    Adaptation in Natural and Artificial Systems

    (1975)
  • I. Rechenberg

    Evolution Strategies: Optimierung Technischer Systeme Nach Prinzipien Der Biologischen Evolution

    (1973)
  • A. Lazar et al.

    Heuristic Knowledge Discovery for Archaeological Data Using Genetic Algorithms and Rough Sets, Artificial Intelligence Laboratory, Department of Computer Science

    (2003)
  • J.R. Koza

    Genetic Programming On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems)

    (1992)
  • H. Mühlenbein et al.

    From recombination of genes to the estimation of distributions I. Binary parameters

  • A.K. Qin et al.

    Self-adaptive differential evolution algorithm for numerical optimization

    Proc. IEEE Congr. Evol. Comput.

    (2005)
  • A.K. Qin et al.

    Differential evolution algorithm with strategy adaptation for global numerical optimization

    IEEE Trans. Evol. Comput.

    (2009)
  • R.M. Storn et al.

    Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces

    J. Global Optim.

    (1997)
  • J. Zhang et al.

    JADE: adaptive differential evolution with optional external archive

    IEEE Trans. Evol. Comput.

    (2009)
  • J. Brest et al.

    Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems

    IEEE Trans. Evol. Comput.

    (2006)
  • Ernesto Mininno

    Compact differential evolution

    IEEE Trans. Evol. Comput.

    (2011)
  • Yong Wang et al.

    Differential evolution with composite trial vector generation strategies and control parameters

    IEEE Trans. Evol. Comput.

    (2011)
  • M. Dorigo et al.

    Ant colony optimization-artificial ants as a computational intelligence technique

    IEEE Comput. Intell. Mag.

    (2006)
  • M. Dorigo et al.

    The ant system: optimization by a colony of cooperating agents

    IEEE Trans. Syst. Man Cybern.-Part B

    (1996)
  • Cited by (47)

    • A new flower pollination algorithm with improved convergence and its application to engineering optimization

      2022, Decision Analytics Journal
      Citation 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.

    View all citing articles on Scopus
    View full text