Firefly Algorithms for Multimodal Optimization – Xin-She Yang, 2010

This is the third post in a mini-series on nature-inspired optimisation algorithms.

The flashing light of fireflies is an amazing sight in the summer sky in the tropical and temperate regions. There are about two thousand firefly species, and most fireflies produce short and rhythmic flashes. The pattern of flashes is often unique for a particular species. The flashing light is produced by a process of bioluminescence, and the true functions of such signaling systems are still being debated. However, two fundamental functions of such flashes are to attract mating partners (communication), and to attract potential prey. In addition, flashing may also serve as a protective warning mechanism. The rhythmic flash, the rate of flashing and the amount of time form part of the signal system that brings both sexes together. Females respond to a male’s unique pattern of flashing in the same species, while in some species such as photuris, female fireflies can mimic the mating flashing pattern of other species so as to lure and eat the male fireflies who may mistake the flashes as a potential suitable mate.

The flashing lights of fireflies inspired the Firefly Algorithm. Start with an initial population of fireflies spread over the solution space, and let the brightness of an individual firefly be affected or determined by the landscape of the objective function (the one we are trying to optimise). Fireflies are attracted to (move towards) brighter fireflies in each iteration. At the end of the game (e.g. a specified number of intervals), the brightest firefly is the winner! There are three simplifying rules for our artificial fireflies:

1. All fireflies are unisex, one firefly is attracted to another regardless of sex
2. Attractiveness is proportional to brightness. Both attractiveness and brightness decrease as the distance between two fireflies increases
3. The brightness is determined by the objective function. “For a maximization problem, the brightness can simply be proportional to the value of the objective function. Other forms of brightness can be defined in a similar way to the fitness function in genetic algorithms.”

There are two key issues in modelling the firefly algorithm: the variation of light intensity, and the formulation of attractiveness. Attractiveness is determined by brightness, but as we also know, ‘beauty is in the eye of the beholder.’ More precisely, attractiveness β varies with the distance r_ij between fireflies i and j. Light intensity decreases with distance from its source too, and light is absorbed in the media, so attractiveness varies with the degree of absorption. Light intensity follows an inverse square law (1/r²), and absoption depends on an absorption coefficient γ and the distance r proportional to e^-γr.

We can combine these effects in a Guassian approximation:

I( r ) = I₀e^-γr2

where I₀ is the intensity at the origin.

Since attractiveness β is proportional to light intensity we can therefore use:

β( r ) = β₀e^-γr2

And to avoid calculating an exponential function, we can replace this with:

β( r ) = β₀/(1 + γr²)

The distance between fireflies is just the Cartesian Distance, which we can extend into multiple dimensions as needed. Putting all this together with a randomisation parameter α gives us the equation for moving fireflies on each iteration, firefly i moves towards a brighter firefly j according to:

x_i = x_i + β₀e^-γr2_ij(x_j – x_i) + α(rand – 1/2)

It is worth pointing out that the distance r defined above is not limited to the Euclidean distance. We can define many other forms of distance r in the n-dimensional hyperspace, depending on the type of problem of our interest. For example, for job scheduling problems, r can be defined as the time lag or time interval. For complicated networks such as the Internet and social networks, the distance r can be defined as the combination of the degree of local clustering and the average proximity of vertices. In fact, any measure that can effectively characterize the quantities of interest in the optimization problem can be used as the ‘distance’ r.

When γ → 0 we have the situation where light intensity does not decrease with distance in an idealized sky, and this corresponds to Particle Swarm Optimisation. When γ → ∞ we have ‘very shortsighted fireflies’ ! This corresponds to the completely random search method.

As the firefly algorithm is usually in somewhere between these two extremes, it is possible to adjust the parameter γ and α so that it can outperform both the random search and PSO. In fact, FA can find the global optima as well as all the local optima simultaneously in a very effective manner…. Our simulation results for finding the global optima of various test functions suggest that particle swarm often outperforms traditional algorithms such as genetic algorithms, while the new firefly algorithm is superior to both PSO and GA in terms of both efficiency and success rate. This implies that FA is potentially more powerful in solving NP-hard problems which will be investigated further in future studies.