Source-linked AI summary
Firefly Algorithm, Levy Flights and Global Optimization
Xin-She Yang
TL;DR
Global optimization metaheuristics commonly use controlled randomization, and this paper investigates whether Levy flights can be combined with Firefly Algorithm search. It formulates the Levy-flight Firefly Algorithm, compares it with PSO and genetic algorithms, and reports superior efficiency and success rate over both.
Problem
Nature-inspired metaheuristics address global and NP-hard optimization problems, while their randomization typically uses uniform or Gaussian distributions.
Method
The paper combines Levy-flight characteristics with the Firefly Algorithm and compares the resulting LFA with PSO and genetic algorithms.
Results
LFA is reported as superior to both PSO and GA in efficiency and success rate when finding global optima of various test functions.
Takeaways & Limitations
The results suggest that LFA is potentially more powerful for solving NP-hard problems.
Takeaways & Limitations
Further convergence improvement is left to sensitivity studies varying parameters such as β0, γ, α, and λ.
Abstract
from arXiv · showhide
Nature-inspired algorithms such as Particle Swarm Optimization and Firefly Algorithm are among the most powerful algorithms for optimization. In this paper, we intend to formulate a new metaheuristic algorithm by combining Levy flights with the search strategy via the Firefly Algorithm. Numerical studies and results suggest that the proposed Levy-flight firefly algorithm is superior to existing metaheuristic algorithms. Finally implications for further research and wider applications will be discussed.
1 Introduction
Nature-inspired metaheuristics use controlled randomization, local search, and selection to address global optimization, but commonly rely on uniform or Gaussian randomization. This paper proposes combining Levy flights with the Firefly Algorithm and compares the resulting LFA with PSO and other algorithms.
- Nature-inspired metaheuristics are used for modern global optimization, including NP-hard problems such as the travelling salesman problem.
- Their search strategies combine controlled randomization, efficient local search, and selection of the best solutions.
- Common randomization schemes in these algorithms use uniform or Gaussian distributions.
- Animal and insect movement, including fruit-fly exploration, exhibits Levy-flight characteristics involving intermittent, scale-free search patterns.
- The paper formulates a Levy-flight Firefly Algorithm and compares it with PSO and other relevant algorithms.
2 Firefly Algorithm
The Firefly Algorithm models optimization through idealized flashing and attraction behaviors, linking light intensity to the objective landscape. Its attractiveness decreases with distance and depends on light absorption, while the flashing formulation enables an optimization procedure.
- Firefly flashing is associated with the objective function, allowing light intensity to represent solution quality in the optimization landscape.
- The Firefly Algorithm idealizes fireflies as unisex agents attracted toward brighter fireflies, with attractiveness decreasing as distance increases.
- The algorithm treats attractiveness as determined by brightness, which is associated with the encoded objective function.
- Light intensity varies with distance from its source and is affected by absorption in the medium.
- Attractiveness is defined from the light intensity perceived by adjacent fireflies.
3 L´evy-Flight Firefly Algorithm
The Levy-flight Firefly Algorithm combines firefly attraction with Levy-flight motion, using parameterized attractiveness, distance, and randomization to search optimization spaces. Its limiting cases connect the method to PSO and completely random search, while intermediate settings are reported to outperform both.
- The Levy-flight Firefly Algorithm combines the firefly rules with Levy-flight characteristics into a new optimization algorithm.Its procedure is summarized in pseudo code.
- Firefly movement combines attraction toward brighter fireflies with Levy-flight randomization.The attraction term and randomization term jointly determine movement; Levy steps follow a heavy-tailed power-law distribution.
- Choice of Parameters: The attractiveness function may use a monotonically decreasing form, with γ controlling attractiveness variation and convergence behavior.In practice, γ is typically O(1) and may range from 0.01 to 100 according to the system's characteristic length.
- Asymptotic Cases: When γ → 0, attractiveness becomes constant and the algorithm corresponds to a special case of particle swarm optimization.The associated characteristic length tends to infinity, allowing a firefly to be seen anywhere in the domain.
- Asymptotic Cases: When γ → ∞, attractiveness approaches a Dirac delta, producing short-sighted fireflies and completely random search.Here the characteristic length tends to zero and fireflies cannot see one another.
- Asymptotic Cases: Intermediate settings of γ, λ, and α are reported to outperform both random search and PSO while finding global and local optima simultaneously.The paper presents the usual LFA regime as lying between the two limiting cases.
4 Simulations and Results
The simulations validate LFA on Ackley and Yang’s forest functions, then compare it with PSO and genetic algorithms under repeated, matched-population experiments. The reported results include rapid convergence on Ackley and higher efficiency and success rates for LFA.
- Validation: With α = 0.2, γ = 1, λ = 1.5, and β0 = 1, LFA was tested on the Ackley function.The Ackley function has global minimum f∗ = 0 at (0, 0, ..., 0).
- Validation: About 200 evaluations found the Ackley global minimum using 40 fireflies after 5 iterations.The two-dimensional Ackley function has its minimum at (0, 0).
- Validation: Yang’s forest function was used as a tougher test because it is non-smooth and its derivative is not well defined at the optimum.Its global minimum is f∗ = 0 at (0, 0, ..., 0).
- Comparison of LFA with PSO and GA: All algorithms used population size n = 40, and each was run at least 100 times until function-value variation fell below ǫ ≤ 10^-5.The comparison included LFA, standard PSO without inertia, and a genetic algorithm with mutation probability 0.05 and crossover probability 0.95.
- Comparison of LFA with PSO and GA: LFA was reported as more efficient at finding global optima, with higher success rates than the compared algorithms.For reference, 10,000 evaluations took about 5 seconds on a 3GHz desktop; population sizes n = 15 to 50 were sufficient for most problems.
5 Conclusions
The paper formulates and evaluates a Levy-flight firefly algorithm against PSO and genetic algorithms. Simulations suggest that LFA is superior in efficiency and success rate, while parameter sensitivity and hybrid applications remain future research topics.
- Conclusions: The paper formulates LFA and analyzes its similarities and differences with PSO before comparing their performance.The algorithms were implemented and evaluated on various test functions.
- Conclusions: Simulation results suggest that LFA is superior to both PSO and genetic algorithms in efficiency and success rate.The paper also reports that PSO often outperforms traditional algorithms such as genetic algorithms.
- Conclusions: LFA is presented as potentially more powerful for NP-hard problems, which the paper identifies for future investigation.This implication is stated as potential rather than as an established result on NP-hard problems.
- Conclusions: Further research should study sensitivity to β0, γ, α, and λ and applications combining the algorithm with other optimization methods.These topics are proposed as ways to improve convergence and broaden applications.