Clustering using firefly algorithm Performance study(2)

萤火虫算法

J.Senthilnathetal./SwarmandEvolutionaryComputation1(2011)164–171165

Wealsopresenttheresultsofotherninemethodsusedintheliterature[9,14].Fortheeaseofunderstandingandcomparison,wefollowthesamemannerofanalysisanddiscussions,usedin[9].TheonlykeydifferenceistheuseoftheFAalgorithminthisstudy.Contributionofthispaper:Inthiswork,foragivendatasettheFAisusedtofindtheclustercenters.Theclustercentersareobtainedbyrandomlyselecting75%ofthegivendataset.This75%ofthegivendataset,wecallasatrainingset.TheFAalgorithmusesthistrainingsetandtheclustercentersareobtained.Inordertostudy,theperformanceoftheFAalgorithm,theremaining25%ofdatasetisused(calledtestdataset).TheperformancemeasureusedintheFAistheclassificationerrorpercentage(CEP).ThisCEPisdefinedastheratioofnumberofmisclassifiedsamplesinthetestdatasetandtotalnumberofsamplesinthetestdataset.Thiscanbedonebecauseinthetestdataset,weknowtheactualclassofthetestdata.Thedistancesbetweenthegiventestdataandtheclustercentersarecomputed.Thedataisassignedtotheclustercenter(class)thathastheminimumdistance.Hence,wecancomputetheperformancemeasure—classificationerrorpercentage(CEP).

ThepaperisorganizedastheimplementationoftheFAalgorithminSection2,clusteringusingtheFAandperformanceevaluationinSections3and4respectively,andthenresultspresentedanddiscussedinSection5.WeconcludethepaperinSection6bysummarizingtheobservations.2.Fireflyalgorithm

Firefliesareglowwormsthatglowthroughbioluminescence.Forsimplicityindescribingourfireflyalgorithm,wenowusethefollowingthreeidealizedrules:(i)allfirefliesareunisexsothatonefireflywillbeattractedtootherfirefliesregardlessoftheirsex;(ii)animportantandinterestingbehavioroffirefliesistoglowbrightermainlytoattractpreyandtosharefoodwithothers;(iii)attractivenessisproportionaltotheirbrightness,thuseachagentfirstlymovestowardaneighborthatglowsbrighter[21].TheFireflyAlgorithm(FA)[18]isapopulation-basedalgorithmtofindtheglobaloptimaofobjectivefunctionsbasedonswarmintelligence,investigatingtheforagingbehavioroffireflies.IntheFA,physicalentities(agentsorfireflies)arerandomlydistributedinthesearchspace.Agentsarethoughtofasfirefliesthatcarryaluminescencequality,calledluciferin,thatemitlightproportionaltothisvalue.Eachfireflyisattractedbythebrighterglowofotherneighboringfireflies.Theattractivenessdecreasesastheirdistanceincreases.Ifthereisnobrighteronethanaparticularfirefly,itwillmoverandomly.IntheapplicationoftheFAtoclustering,thedecisionvariablesareclustercenters.TheobjectivefunctionisrelatedtothesumonalltrainingsetinstancesofEuclideandistanceinanN-dimensionalspace,asgivenin[9].

Basedonthisobjectivefunction,initially,alltheagents(fireflies)arerandomlydispersedacrossthesearchspace.Thetwophasesofthefireflyalgorithmareasfollows.

i.Variationoflightintensity:Lightintensityisrelatedtoobjectivevalues[18].Soforamaximization/minimizationproblemafireflywithhigh/lowintensitywillattractanotherfireflywithhigh/lowintensity.Assumethatthereexistsaswarmofnagents(fireflies)andxirepresentsasolutionforafireflyi,whereasf(xi)denotesitsfitnessvalue.HerethebrightnessIofafireflyisselectedtoreflectitscurrentpositionxofitsfitnessvaluef(x)[18].Ii=f(xi),

1≤i≤n.

(1)

ii.Movementtowardattractivefirefly:Afireflyattractivenessis

proportionaltothelightintensityseenbyadjacentfireflies[18].Eachfireflyhasitsdistinctiveattractivenessβwhichimplieshowstrongitattractsothermembersoftheswarm.However,the

attractivenessβisrelative,itwillvarywiththedistancerijbetweentwofirefliesiandjatlocationsxiandxjrespectively,isgivenasrij=‖xi xj‖.

(2)

Theattractivenessfunctionβ(r)ofthefireflyisdeterminedby

β(r)=β0e γr

2

(3)

whereβ0istheattractivenessatr=0andγisthelightabsorptioncoefficient.

Themovementofafireflyiatlocationxiattractedtoanothermoreattractive(brighter)fireflyjatlocationxjisdeterminedbyxi(t+1)=xi(t)+βγr2

0e (xj xi).

(4)

AdetaileddescriptionofthisFAisgivenin[18].Apseudo-codeofthisalgorithmisgivenbelow.

Pseudo-code:AHigh-LevelDescriptionoffireflyalgorithmInput:

Createaninitialpopulationoffirefliesnwithind-dimensionalsearchspacexik,i=1,2,...,nandk=1,2,...,d

Evaluatethefitnessofthepopulationf(xik)whichisdirectlyproportionaltolightintensity,γIikAlgorithm’sparameter—β0Output:

Obtainedminimumlocation:ximinbegin

repeat

fori=1ton

forj=1ton

if(Ij<Ii)

Movefireflyitowardjind-dimensionusingEq.(4)endif

Attractivenessvarieswithdistancerviaexp[ r2]

EvaluatenewsolutionsandupdatelightintensityusingEq.(1)endforjendfori

Rankthefirefliesandfindthecurrentbestuntilstopconditiontrueend

3.ClusteringusingFA

Theclusteringmethods,separatingtheobjectsintogroupsorclasses,aredevelopedbasedonunsupervisedlearning.Intheunsupervisedtechnique,thetrainingdatasetaregroupedfirst,basedsolelyonthenumericalinformationinthedata(i.e.clustercenters),andarethenmatchedbytheanalysttoinformationclasses.Thedatasetsthatwetackledcontaintheinformationofclassesforeachdata.Therefore,themaingoalistofindthecentersoftheclustersbyminimizingtheobjectivefunction,thesumofdistancesofthepatternstotheircenters.

ForagivenNobjectstheproblemistominimizethesumofsquaredEuclideandistancesbetweeneachpatternandallocateeachpatterntooneofkclustercenters.TheclusteringobjectivefunctionisthesumoferrorsquaredasgiveninEq.(5)isdescribedasin[22]:

KJ(K)=

(xi ck)

(5)

k=1i∈ck