Firefly Algorithm for Uncapacitated Facility Location Problem and Number of Fireflies (Developments of Language, Logic, Algebraic system and Computer Science)

Firefly Algorithm

for

_{Uncapacitated}

Facility

Location

Problem and Number

of

$\Gamma$

ireflies

Kohei

_{Tsuya, Mayumi Takaya,}

Szilárd

Zsolt Fazekas

\backslash ’

Akihiro

Yamamura

Akita

_University

Abstract

We

_apply

the

_{firefly algorithm}

to the _{uncapacitatcd facility} location

problemwhich is one ofoptimization problems and investigatethe opti‐

mum number of the fireflies. The light absorption coefficient _parameter

$\gamma$ of the firefly

algorithm

is examined to obtain better performance and

suitable values of $\gamma$ are explored for the uncapacitated

facility

location

problem. Effectiveness of local search in the

_firefly

_algorithm is also in‐

vestigated.

In _addition, we_investigatetheoptimumnumber of fireflies for

the_{firefly algorithm.}

1

Introduction

The method of

_simulating

swarm

intelligence

is

inspired by

the movement and

foraging

behavior in herd animals

_[1,

11,

21].

As

_{typical examples,}

_particle

swa,rm

optimiza,tion

was

inspired

by

the behavior of _groups of birds and fish,

ant

_{colony optimization}

was

inspired by

the

foraging

behavior ofants. Numer‐ ous swarm

intelligence algorithms

have been

proposed

and

investigated: particle

swarm

optimization

[10, 11],

ant

_colony

_{optiinization}

[6],

artificial bee

_colony

algorithm

[9],

bat

_algorithm

_[22],

cuckoo search

_[23],

_genetic

_algorithm

_{[5, 8]}

andso on. These have been

applied

toawide_range of

computational problems

like data

_mining

and

_{image processing}

_[1]

in addition to numerous

optimiza‐

tion

_problems

like the

_traveling

salesman

_problem

and the flow

_shop

_scheduling

problem.

Firefly algorithm

(FA

for

_short)

is one of metaheuristic

algorithms

and has

been studied

_by

many researchers.

Recently,

effectiveness of FA and suitable

values of_parameters of FA are

investigated

for some

optimization

problem

in

[18].

We introduce the results in

_[18]

and add some results on effect.iveness of

Efficient

_supply

chain _management has led to increased

_profit,

increased

market

_share,

reduced

_operating

_cost, and

_improved

customer satisfaction for

manybusinesses

[13,

16,

17].

Forthis purpose, it is

getting

moreand more im‐

portant

ininformation and communications

_technologies

to solve

_optimization

problem

such as the

uncapacitated facility

location

problem

(UFI P)

whichis a

combinatorial

_optimization

_problem.

The

_objective

of the UFLP is to

_optimize

the cost oftransport to eachcustomer and the cost associated to

_facility

_open‐

ing,

when the set of

_potential

locations of facilities and the customers are

given,

whereas \mathrm{U} $\Gamma$ \mathrm{L}\mathrm{P} is knowntobe NP‐hard

_(see

_[13]).

In thecontext of

_performing

economic activities

_efficiently,

various

_objects

have been considered as

facilities,

such as

manufacturing plants,

_storage facilities, warehouses,

libraries,

fire sta‐

tions, hospitals

orwirelessservicestations. Several

techniques

have been

applied

tothe UFLP such as theswarm

intelligence algorithms

or a meta‐heuristics al‐

gorithm; particle

swarm

optimization

(PSO) [7],

ant

colony

optimization

(ACO)

[12],

artificial

bee

_{colony algorithm}

_{(AUC) [19],}

and

_genetic

_algorithm

_[14].

UFLP is described as follows. Given a set F of fa,cilities and a set C of

customers, afixed

_opening

cost

_{f_{i} \in \mathbb{R}_{+}}

for each

_facility

i\in F, anda

transport

cost

_{c_{ij}\in \mathbb{R}_{+}}

from each

_facility

i\in F toeachcustomer

_{j\in C}

, where

\mathbb{R}_{+}

stands

for the setof

_positive

realnumbers, \mathrm{I}\mathrm{T} $\Gamma$ \mathrm{L}\mathrm{P} asksto findacombination of

opening

facilities to minimize cost of

_{transportation}

and

_opening

facilities.

Each customer

_j

is

_expected

to select a

facility

i from the

opened

facilities

so that the cost _{c_{ii}} is lowest. It is asked to find a subset X of facilities to be

opened

and the

_assignment

$\sigma$ : C \rightarrow X of each customer to an

appropriate

facility

so\mathrm{t}\mathrm{h}\mathrm{a}_{1}\mathrm{t} these minimize the sum of the

opening

costsof the facilities and

the _transport costs

_given

_by

theformula

_(1).

\displaystyle \sum_{i\in X}f_{i}+\sum_{j\in C}c_{ $\sigma$(j)g}

(1)

Severalswarm

intelligence algorithms

have been

applied

toUFLP untilnow.

For

_example,

_particle

swarm

optimization,

ant

colony

optimiza,tion,

artificial

bee

_{colony algorithm}

_(ABC

for

_short),

and

_genetic

_algorithm

are studied in

[7,

12, 14, 19,

_20].

In

_[18],

FA is

_applied

to \mathrm{U} $\Gamma$ \mathrm{L}\mathrm{P} and

_explore

suitable value of

paraÌnetersofFA. Effectiveness of

_equipping

a local search mechanisni to FA is

also discussed to minimize cost

_(1).

FA is also

_compared

with ABC

_algorithm

to find asolution of \mathrm{U} $\Gamma$ \mathrm{L}\mathrm{P}.

Experiments

arecarried out to answerthese issues.

In this paper, weir the

optimum

number of fireflies for FA in addition

tothe results in

_[18].

2

_{Firefly algorithm}

for the

_{uncapacitated}

facil‐

ity

location

_problem

2.1

_Applying

to

UFLP

Each

_firefty

k is

_given

an _open

facility

vector

_{Y_{k}}

_{(= [y_{k1}, y_{k2}, y_{k3}, \ldots, y_{k\mathrm{z} $\iota$}])}

_rep‐

facilities. If the i‐th

_facility

is_open,

_{y_{ki}=1}

. For theopen

facility

vector

\mathrm{Y}_{k}

ofa

firefly k,

X(k)

isdefined to be the set of facilities i in F such that

_{y_{ki}=1}

, that

is,

X(k)

is the set of the facilities that are

opened.

For the _open

facility

vector

\mathrm{Y}_{k}

,

assignment

function $\sigma$ :

C\rightarrow X(k)

from C to

X(k)

is defined

by

the trans‐

port costs _{c_{\dot{ $\eta$}j}} as follows. For each

j

in

C,

$\sigma$(j)

is defined to be i

_{\in X(k)}

such

that c_{ij} is the smallest among

\{c_{hj} |h\in X(k)\}

. If there are several candidates

h, one of them is selected

randomly.

The total cost

T(\mathrm{Y}_{k})

for each

firefly

k is

computed

as the sum of the cost of

_opening

facilities determined

_by

the open

facility

vector

_{\mathrm{Y}_{k}}

and the_transport cost determined

_by

the

_assignment

function

$\sigma$ :

C\rightarrow X(k)

for

\mathrm{Y}_{k}

. The cost

T(\mathrm{Y}_{k})

for the open

facility

vector

Y_{k}

is defined

by

the formula

₍₁₎

and is rewritten asfollows.

T(Y_{k})=\displaystyle \sum_{i\in X(k)}f_{i}+\sum_{j\in C}c_{ $\sigma$(j)j}

(2)

The notations used in this paper is summarized in Table 1.

Table 1: Notations

An

_example

of a

problem

instance of \mathrm{U} $\Gamma$ \mathrm{L}\mathrm{P} is

_given

in Table 2.

_Suppose

that

_\mathrm{A},

_\mathrm{B},

_{\mathrm{C}, \mathrm{D},}

\mathrm{E} are

facilities,

_\mathrm{a},

\mathrm{b},

_\mathrm{c}, \mathrm{d} are_customers, and

[

_1,

0_,

_1,

0_,1

]

is the

open

facility

vector

\mathrm{Y}_{s}

given

to a

firefly

s. Note that

f_{\mathrm{A}}=3, f_{\mathrm{B}}=4_{:} f_{\mathrm{C}}

=6,

f_{\mathrm{D}}=7

, and

f_{\mathrm{E}}=2

and

$\sigma$(\mathrm{a})

=\mathrm{A},

$\sigma$(\mathrm{b})

=\mathrm{B}

(it

may be \mathrm{E} as

well), $\sigma$(\mathrm{c})=\mathrm{C},

and

_{$\sigma$(\mathrm{d})=\mathrm{D}}

for this open

facility

vector

_{\mathrm{Y}_{s}}

. Then the total cost

T(\mathrm{Y}_{s})

for the

open

facility

vector

_{\mathrm{Y}_{s}}

is

_{computed following}

the

_equation

_(2).

_Similarly,

the

T(\mathrm{Y}_{s})

=

Opening

costs +

Transport

cost

= (3+6+2)+\displaystyle \min(1,2,9)+\min(8,5,2)\min(4,3,6)+\min(9,4,3)

= 20.

T(\mathrm{Y}_{t})

=

(4+6+7+2)+(2+2+3+2)

= 28.

Table 2:

_Example

of_open

_facility

vector for a

firefly

k

Attractiveness of a

firefly

is

represented

by

the

light

intensity.

FYom the

assumption

3,

the

_light

_intensity

of the

_firefly

is

_given

_by

the

_{objective function,}

that

_is,

the total cost

_{T(Y_{k})}

.

Light

intensity

I(\mathrm{Y}_{k})

of a

firefly

k is

represented

by

the

_equation

_(3).

I(\displaystyle \mathrm{Y}_{k})=\frac{1}{T(\mathrm{Y}_{k})}

.

(3)

Note that

_{I(\mathrm{Y}_{k})}

_gets

_larger

as

T(\mathrm{Y}_{k})

_gets

smaller. Itcanbe determined whether

the

_firefly

has a

good

solution

by

_comparing

I

(Yk).

The

Light

_intensity

of

firefly

s and t is as follows.

I(\displaystyle \mathrm{Y}_{s})=\frac{1}{20}iI(\mathrm{Y}_{t})=\frac{1}{28}

.

(4)

Distance between any two fireflies is

represented

by

the

hamming

distance

of their _open

_facility

vectors.

Suppose

that the

_fircfly

s and the

firefly

t have

open

facility

vectorsbelow. Then the

hamming

distance r_{st} between s and tis

3.

Y_{s}=[1, 0, 1, 0, 1]

\mathrm{Y}_{t}=[0, 1, 1, 1, 1]

If

_{I(Y_{s})>I(\mathrm{Y}_{t})}

holds for twofirefliessandt, thentmovestowardss. Movement

of the

_firefly

t toward the

_firefly

s isthe conversionof the _open

facility

vector of

t. Common components of

\mathrm{Y}_{s}

and

\mathrm{Y}_{t}

are carried over to the new open

facility

vector

_{Y_{t}.}

Each of _components of

_{Y_{t}}

different from

Yô

is

_replaced

with a

probability $\beta$.

The

_{probability $\beta$}

is

_given

_by

the

_following

formula

_(5).

$\beta$=\displaystyle \frac{$\beta$_{0}}{1+ $\gamma$ r_{st}^{2}}

(5)

where

_{$\beta$_{0}}

isthe

_probability

at

_{r_{st}=0}

and

_ỉio

is set

_1,

and $\gamma$ isthe

light absorption

coefficient.

In this

_paper,

suitable values of $\gamma$ is

explored.

Let

_firefly

t be close to

_firefly

s

by probability

$\beta$

as follows. The total cost

ofnew

\mathrm{Y}_{t}

at this time is

24,

which shows that the cost is

_decreasing.

new

\mathrm{Y}_{t}

=

[

1, 1, 1,

0

,1

]

new

T(Y_{t})

=

(3+4+6+2)+(1+2+3+3)

= 24.

2.2

Pseudocode of FA

FA program generates fireỉlies and set Lhe _parameters. Fireflies _compare the

intensity

each other and then

_change

their

_positions,

that

_is,

the open

facility

vectors

_according

totheir distance.

_Repeating

thisprocess, FAprogram

updates

fireflies’

_intensity

and their_open

_facility

_vectors, and then it_outputs a solution.

A

_pseudocode

of FA_program is illustrated below.

begin

Objective

function

_{\displaystyle \min T(Y)}

,

Initialize

_positions

of fireflies

_{\mathrm{Y}_{k}.(k=1,2, \ldots , K)}

I(Y_{k})

is defined

_by

the

_reciprocal

of

_{T(\mathrm{Y}_{k})}

,

Define_{parameter $\gamma$}and

_$\beta$

while

₍

\mathrm{r}<

_Repeat

_count)

for t= lto K

for s= lto K

if

_{I(\mathrm{Y}_{s})>I(\mathrm{Y}_{t})}

Move

_firefly

t towards

_firefly

s

else

Move

_firefly

t

_randomly;

end if

Update

of

_intensity

and total _cost;

end fors

end for t

Rank the fireflies and find the current best.

Local Search.

\mathrm{r}++;

end while

Post‐process

results and visualization end

3

_Experiments

and

Results

3.1

_Objectives

A_computer programofFA tosolve UFLP is

implemented

and

experiments

are

carried out. Suitable values of the

_{light absorption}

coefficient

parameter

$\gamma$ is

explored

to

_accomplish

better

_performance.

A program is

implemented

in

C#

language using

Visual Studio and run on an Intel Core i52. 67\mathrm{G}\mathrm{H}\mathrm{z}

Desktop

with 4.0\mathrm{G}\mathrm{B} memory. Several test data sets of benchmark

problems

are bor‐

rowed from

_OR‐Library

_[4],

which is acollectionoftest datasets for numerous

operations

research

_problems

and

_originally

described in

_[2].

\mathrm{U} $\Gamma$ \mathrm{L}\mathrm{P} is called

an

uncapacitated

warehouse location

problem

in

OR‐Library.

There are 15 data

files

_provided;

thetest data setsVII, X. XIII and A to \mathrm{C} from

_[3].

The test data

sets VII

_(cap71,

_72,

_73,

_74),

X

_(cap

_{101, 102, 103,}

₁₀₄₎

and XIII

_(cap

_{131, 132,}

133,

134)

are

employed

for

experiments.

These test data sets are summarized

in Table

_3,

in which m stands for the number ofcustomers and n stands for

the number of facilities. The

_optimal

solutionsfor these testdata setsaretaken

from

_{OR‐Library.}

Table 3: Test data from

_OR‐Library

3.2

Number of fireflies

Find the

_optimum

number of fireflies for FA. In this _{paper, average} relative

percenterror

(ARPE

for

short)

and hitto

optimum

rate

(HR

for

short)

isused for

performance

evaluation of the

_algorithm.

ARPE is theaverage of the difference

more chance toobtain better solutions. ARPE is

_{given by}

the formula

_(6).

ARPE=\displaystyle \sum_{i=1}^{R}(\frac{H_{i}-U}{U}) \times \frac{100}{R}

(6)

where

_{H_{i}}

denotes the i‐th

_replication

solution

_value,

R is the numberof

_replica‐

tions,

and U is the

_optimal

value

_{provided by}

_[4].

HR representsthenumber of

times that the

_algorithm

finds the

_optimal

solutions over all

repetitions.

IfHR

is

_higher,

then the

_probability

to obtain a better solutionis

higher.

_$\gamma$ is set to

be

_e.01,

the _repeat count

_50,

and the number of fireflies is one of the values

10,

15, 20, 25,

30or35inthe

_experiments.

The result is the_averagevalue when the

algorithm

isexecuted 100 times. The table 4 and table 5 is summaryofARPE

or HR at _repeat count is 50.

Table 4: ARPE for each

_firefly

number

_(number

of

_ỉirefly,

_ARPE)

Table 5: HR for each

_firefly

number

_(number

of

_firefly,

_HR)

4

_Summary

We discussed several

_aspects

of the

_{firefly algorithm}

for UFLPand obtained two

First, optimal

values of the

_{light absorption}

coefficient _$\gamma$ of FA in UFLP

are obtained. It is found that FA works better when _$\gamma$ is

_0.001,

0.005 or 0.01.

These values work well

_regardless

ofsizeof

_problem

instanceof UFLP. Suitable

values for

_particular

test data are obtained

by experiments, however,

suitable

values of $\gamma$ have not been

_complete]y

classified for a

general

case.

Therefore,

it

is necessary toseek suitable parameterswhen FA is

_applied

to an

optimization

problem.

Second,

it is verified that local search

_iinproves

performance

of FA and so

the combination of FA and local search

_algorithm

is effective. FA is

_compared

with FA with local search and ABC

algorithm

with _respect to average relative

percenterrorand hitto

optimum

rate. No

superiority

of FAoverABC

algorithm

is

_recognized,

whereas FA with local search works aswellasABC

algorithm

for

UFLP.

Itseems _{necessary to compare}FA and ABC

algorithm

formorevarious sizes

oftest data and other _type of

_{optimization problems}

in order to

_comprehend

thestrong

points

ofFA. It is also desirableto

_explore

suitable_parametersmakes

FA with local searchtowork better.

References

[1]

A.

_Abraham,

C.

_Grosan,

V.

_Ramos,

Swarm

_Intelligence

in Data

_Mining,

Springer‐Verlag

Berlin

_Heidelberg,

₍₂₀₀₆₎

[2]

J.E.

_Beasley,

_{OR‐Library: distributing}

test

_{problems Uy}

electronic

_mail,

J.

of

the

_Operational

Research

_Society,

₄₁₍₁₁₎

_(1990),

1069‐1072.

[3]

J.E.

_{Beasley, Lagrangean}

heuristics for location

_{problems, European}

J.

_of

Operational Research,

65

_(1993),

383‐399.

[4]

J.E.

_Beasley,

_{OR‐Library,}

_http:

//\mathrm{w}\mathrm{w}\mathrm{w}.brunel.ac.uk_/\sim

_{mastj j}

_{\mathrm{b}/\mathrm{j}\mathrm{e}\mathrm{b}/}

inf0. html.

[5]

K.D.

_Jong,

_{Analysis of}

the behavior

_of

a class

of genetic adaptive

_systems,

Ph.D.

_{Thesis, University}

of

_Michigan,

1975.

[6]

M.

_{Dorigo, optimization, Learning}

and Natural

_Algorithms,

Ph.D.

_Thesis,

Politecnico di

_Milano,

1992.

[7]

A.R. Guner and M.

_Sevkli,

A discrete

_particle

swarm

optimization

algorithm

for

_{uncapacitated facility}

location

_problem,

J.

_{of Artificial}

Evolution and

Applications,

2008(10) (2008),

9 _pages.

[8]

J.H.

_{Holland, Adaptation}

inNatural and

_{Artificial Systems:}

An

_Introductory

Analysis

with

_Applications

to

_{Biology, Control,}

and

_{Artificial Intelligence,}

A Uradford

_Book,

1992.

[9]

D.

_Karaboga,

An Idea Uasedon

Honey

BeeSwarmfor Numerical

optimiza‐

[10]

J.

_Kennedy

and

_R.Eberhart,

Particle Swarm

_{optimization, Proceedings}

of

the IEEE international conference onneural

networks,

1995,

1942‐1948.

[11]

J.

_Kennedy,

R. EUerhart and Y.

_Shi,

Swarm

_{intelligence,}

Academic

_Press,

2001.

[12]

A.

_Kole,

P. Chakrabarti and S.

_{Bhattacharyya,}

Anant

_colony

_optimiLation

algorithm

for

_{uncapacitated facility}

location

_{problem, Artzficial Intelligence}

and

_{Applications,}

_{1(1) (2014),}

55‐61.

[13]

B. Korte and J.

_Vygen,

Combinatorial

_{optimization: Theory}

and

_Algo‐

rithms, Springer‐Verlag,

2007.

[14]

J.

_Kratica,

D.

_Tosic,

V.

_Filipovic

and I.

_{Ljubic, Solving}

the

_{simple plant}

location

_{problem by genetic algorithm,}

RAIRO ‐

Operations Research,

35

(2001),

127‐142.

[15]

S.M. Lewis and C. K.

_Cratsley,

Flash

_{signal evolution,}

mate choice and

predation

in

_fireflies,

Annual Review

_{of Entomology,}

₅₃₍₂₎

_(2008),

293‐321.

[16]

R. Rahmaniani and A.

_Ghaderi,

A combined

_facility

location and network

design problem

with

_multi‐type

of

_{capacitated links,}

_Applied

Mathematical

Modelling,

37(9) (2013),

6400‐6414.

[17]

D.

_{Simchi‐Levi,}

P.

_Kaminsky,

E.

_{Simchi‐Levi, Designing}

and

_Managing

the

Supply

Chain.

_{Concepts, Strategies}

and Case

_{Studies, McGraw‐Hill, Boston,}

Mass,

USA.

₍₂₀₀₀₎

[18]

K.

_Tsuya,

M.

_Takaya,

and A.

_Yamamura,

_Application

of the

_{firefly algo‐}

rithm to the

_{uncapacitated}

_facility

location

_problem,

J.

_{of Intelligent}

and

Fuzzy Systems,

32(4)

(2017)

3201‐3208.

[19]

N.

_Tuncbilek,

$\Gamma$.

Tasgetiren

and S.

Esnaf,

Artificial bee

colony optimization

algorithm

for

_{uncapacitated facility}

location

_problems,

J.

_of

Economic and

Social

_Research,

_{14(1) (2012),}

1‐24.

[20]

Y.

_Watanabe,

M.

_Takaya

and A.

_Yamamura,

Fitnessfunction in ABC

_algo‐

rithm for

_{uncapacitated}

_facility

location

_problem,

Lecture Notesin

_Computer

Science,

9357

_(2015),

129‐138.

[21]

X.S.

_{Yang, Biology‐Derived}

_Algorithms

in

_{Engineering optimization,}

Hand‐

book of

_Bioinspired

_Algorithms

and

_{Applications, Chapman}

& Hall

_{/\mathrm{C}\mathrm{R}\mathrm{C},}

2005,

589‐600.

[22]

X.S.

_Yang,

A new metaheuristic

bat‐inspired algorithm,

Studies in Com‐

putational Intelligence,

284

_(2010),

65‐74.

[23]

X.S.

_Yang

and S.

_Deb,

Cuckoo search via

_{Levy flights, Proceedings}

of the

World

_Congress

on Nature and

Biologically Inspired Computing,

IEEE Pub‐