We will implement the optimization algorithm (firefly algorithm)

Introduction

A series of optimization algorithm implementations. First, look at Overview.

The code can be found on github.

Firefly algorithm

The Firefly Algorithm is an algorithm that focuses on the courtship behavior of fireflies. Model according to the following rules of conduct.

  1. Firefly light intensity is an evaluation value
  2. Other fireflies approach the firefly that emits strong light
  3. The more attractive you are, the closer other fireflies will come
  4. Fly randomly when there are no glowing fireflies nearby

Introduction to Evolutionary Computation Algorithms Optimal Solutions Derived from Behavioral Sciences of Organisms

draw2-Firefly.png

problem Firefly algorithm
Array of input values Firefly position
Input value fire Fly
Evaluation value ホタルの位置におけるEvaluation value(ホタルの光の強さ)
Variable name meaning Remarks
attracting_degree Attracting degree(\beta_0)(0.0~1.0) The larger it is, the greater the rate of approaching fireflies
absorb Light absorption coefficient(\gamma)(0.0~∞) The larger the value, the more light is attenuated.(I can't see the fireflies in the distance)
alpha Random number reflection rate(0.0~1.0) The larger it is, the better it moves randomly
is_normalization Whether to normalize the Euclidean distance When normalized, it feels good if the absorb value is around 20-100.

Firefly movement

The movement of fireflies compares two individuals, and if the light of the other party is stronger, it moves closer. The mobile type is as follows.

d_{ij} = |\vec{x_j} - \vec{x_i}|
attract = \beta_0e^{-\gamma d_{ij}^2}
\vec{x_i}(t+1) = \vec{x_i}(t) + attract(\vec{x_j}(t) - \vec{x_i}(t)) + \alpha \vec{\epsilon}
Formula meaning Hyperparameters
i Target firefly
j Opponent's firefly
x Coordinate
d_{ij} Distance between two fireflies(※1)
\gamma Light absorption coefficient(constant) absorb
\beta_0 Firefly attraction(constant) attracting_degree
attract Attractive value of the opponent's firefly
t Times of Day
\alpha Rate of incorporating random elements(constant) alpha
\vec{\epsilon} Random number in the same dimension as the coordinates(※2)
import random
import numpy as np

i =Index of my firefly
j =Index of the other party's firefly

#Love Move if the light of other fireflies is strong
if fireflys[i].getScore() < fireflys[j].getScore():
    pos = np.asarray(fireflys[i].getArray())
    pos2 = np.asarray(fireflys[j].getArray())

    d = np.linalg.norm(pos2 - pos)  #Euclidean distance
    attract = attracting_degree * (math.exp(-absorb * (d ** 2)))

    #range+Uniform random number in the range of negative values
    r = []
    for _ in range(problem.size)
        t = random.randint(0, 1)
        if t == 0:
            t = -1
        r.append(problem.randomVal() * t)
    r = np.asarray(r)

    #Calculate coordinates
    pos = pos + attract * (pos2 - pos) + alpha * r

    #update
    fireflys[i].setArray(pos)

Euclidean distance normalization

$ attract $ is significantly affected by the Euclidean distance value. However, when the number of dimensions changes, the range of the Euclidean distance also changes as follows.

Euclidean distance when separated by 1 in all dimensions 1D: $ \ sqrt {1 ^ 2} = 1 $ 2D: $ \ sqrt {1 ^ 2 + 1 ^ 2} = 1.4142 $ 3D: $ \ sqrt {1 ^ 2 + 1 ^ 2 + 1 ^ 2} = 1.7320 $

Therefore, I normalized it so that it falls within the range of 0 to 1 in any dimension. This normalization process is original to this article and is not in the original algorithm.

import random
import numpy as np

#Maximum n-dimensional distance
t = [problem.MAX_VAL - problem.MIN_VAL for _ in range(problem.size)]

#Maximum euclidean distance
max_norm = np.linalg.norm(t)

#Get the Euclidean distance of i and j fireflies
pos1 = np.asarray(fireflys[i].getArray())
pos2 = np.asarray(fireflys[j].getArray())
d = np.linalg.norm(pos2 - pos)

#Normalize the Euclidean distance in the range 0 to 1
d = d / max_norm

Regarding the attractiveness value of fireflies

It is $ attract $, which is important in the firefly algorithm, but I tried to graph how it changes depending on the value of $ \ gamma $ (absorb). (attracting_degree is 1)

plot_Firefly.png

The x-axis is the Euclidean distance to the other firefly, and the y-axis is the attract value. The larger the attract, the closer to the opponent's firefly.

As you can see from the graph, the value of attract decreases sharply after a certain distance.

I felt that normalization was necessary to make this attract value easier to control, so I added an implementation.

Whole code

import math
import random

import numpy as np

class Firefly(IAlgorithm):
    def __init__(self,
        firefly_max,
        attracting_degree=1.0,
        absorb=0.5,
        alpha=1.0,
        is_normalization=False,
    ):
        self.firefly_max = firefly_max
        self.attracting_degree = attracting_degree
        self.absorb = absorb
        self.alpha = alpha
        self.is_normalization = is_normalization

    def init(self, problem):
        self.problem = problem

        #For Euclidean distance normalization
        t = [problem.MAX_VAL - problem.MIN_VAL for _ in range(problem.size)]
        self.max_norm = np.linalg.norm(t)

        self.fireflys = []
        for _ in range(self.firefly_max):
            self.fireflys.append(problem.create())
        
    def step(self):
        for i in range(len(self.fireflys)):
            for j in range(len(self.fireflys)):
                if i == j:
                    continue

                #Move if the light is strong
                if self.fireflys[i].getScore() < self.fireflys[j].getScore():
                    pos = self.fireflys[i].getArray()
                    pos2 = self.fireflys[j].getArray()

                    d = np.linalg.norm(pos2 - pos)  #Euclidean distance
                    if self.is_normalization:
                        #Normalize in the range 0 to 1
                        d /= self.max_norm
                    
                    #Attracting degree
                    attract = self.attracting_degree * (math.exp(-self.absorb * (d ** 2)))

                    #range+Uniform random number in the range of negative values
                    r = []
                    for _ in range(problem.size)
                        t = random.randint(0, 1)
                        if t == 0:
                            t = -1
                        r.append(problem.randomVal() * t)
                    r = np.asarray(r)
    
                    pos = pos + attract * (pos2 - pos) + self.alpha * r

                    #update
                    self.fireflys[i].setArray(pos)


Hyperparameter example

It is the result of optimizing hyperparameters with optuna for each problem. A single optimization attempt yields results with a search time of 2 seconds. I did this 100 times and asked optuna to find the best hyperparameters.

problem absorb alpha attract firefly_max is_normalization
EightQueen 30.348200739383188 0.023361773591726337 0.2870040283132875 35 True
function_Ackley 28.535248274373334 0.02020150316119749 0.3817578607938779 22 True
function_Griewank 24.886474482157883 0.030874057659246265 0.2570801290508207 16 True
function_Michalewicz 12.85000382821637 0.00019928439251062913 0.9311223660128144 38 True
function_Rastrigin 12.146442425313117 0.0043715893301495105 0.6005897245267422 23 True
function_Schwefel 19.283223050420563 0.7687804405285998 0.09958914072852465 30 False
function_StyblinskiTang 22.45670196693838 0.040041083413524164 0.6313203783344563 8 True
function_XinSheYang 19.93462659647029 0.7629337202966674 0.7449791915452185 12 False
g2048 15.50932867945044 0.8550076810686411 0.29794958618177236 22 True
LifeGame 9.681288121919476 0.46635850168820797 0.9893266181614047 42 True
OneMax 3.0779446144304785 0.6083197521965231 0.8027617234478412 48 True
TSP 13.999384524084206 0.08809615253769626 0.46965098629117824 21 True

Visualization of actual movement

The 1st dimension is 6 individuals, and the 2nd dimension is 20 individuals, which is the result of 50 steps. The red circle is the individual with the highest score in that step.

The parameters were executed below.

Firefly(N, attracting_degree=0.08, absorb=50.0, alpha=0.03, is_normalization=True)

function_Ackley

function_Ackley_Firefly_2.gif

function_Ackley_Firefly_3.gif

function_Rastrigin

ffunction_Rastrigin_Firefly_2.gif

function_Rastrigin_Firefly_3.gif

function_Schwefel

function_Schwefel_Firefly_2.gif

function_Schwefel_Firefly_3.gif

function_StyblinskiTang

function_StyblinskiTang_Firefly_2.gif

function_StyblinskiTang_Firefly_3.gif

function_XinSheYang

function_XinSheYang_Firefly_2.gif

function_XinSheYang_Firefly_3.gif

Afterword

Since the image has a low alpha setting, it is difficult to get out of the local solution. It's nice that the fluffy feeling is like a firefly.

Recommended Posts

We will implement the optimization algorithm (firefly algorithm)
We will implement the optimization algorithm (overview)
We will implement the optimization algorithm (bat algorithm)
We will implement the optimization algorithm (Problem)
We will implement the optimization algorithm (Kujira-san algorithm)
We will implement the optimization algorithm (cuckoo search)
We will implement the optimization algorithm (harmony search)
We will implement an optimization algorithm (genetic algorithm)
We will implement an optimization algorithm (differential evolution)
We will implement an optimization algorithm (particle swarm optimization)
Implement the REPL
In the middle of development, we will introduce Alembic
#We will automate the data aggregation of PES! part1
I tried to simulate ad optimization using the bandit algorithm.