Using PSO to minimise the Michalewicz function

This tutorial showcases how to use the built-in Particle Swarm Optimisation (PSO) algorithm for finding the minimum in a continuos setting.

We start by importing our necessary modules

using EvoLP
using Statistics
using OrderedCollections

For this example, we will use the Michalewicz function, which is a test function included in EvoLP:

michalewicz(x; m=10)

In this case we will use d=2 and m=10, which are the default values implemented.

In PSO, we use particles. Each particle has a position and a velocity, and remembers the best position the whole swarm has visited. We can create a population of particles in multiple ways, but EvoLP provides 2 particle generators with random positions: either uniform or following a normal distribution.

Let's use the normal generator:particle generators

normal_rand_particle_pop(μ, m, C; y=Inf, rng=Random.GLOBAL_RNG)

julia> normal_rand_particle_pop(3, [0, 0], [1 0; 0 1])
3-element Vector{Particle}:
 Particle([-0.6025996585348097, -1.0055548956861133], [0.0, 0.0], Inf, [-0.6025996585348097, -1.0055548956861133], Inf)
 Particle([-0.7562454555135321, 1.9490439959687778], [0.0, 0.0], Inf, [-0.7562454555135321, 1.9490439959687778], Inf)
 Particle([0.5687241357408321, -0.7406267072113427], [0.0, 0.0], Inf, [0.5687241357408321, -0.7406267072113427], Inf)

Since we are using the 2-dimensional version of the function, we need to provide a vector of 2 means and a 2 \times 2 matrix of covariances:

population = normal_rand_particle_pop(50, [0, 0], [1 0; 0 1])
first(population, 3)

3-element Vector{Particle}:
 Particle([-2.2345188497511526, 0.2823261728889965], [0.0, 0.0], Inf, [-2.2345188497511526, 0.2823261728889965], Inf)
 Particle([-1.1381992988201621, 0.3398828702959355], [0.0, 0.0], Inf, [-1.1381992988201621, 0.3398828702959355], Inf)
 Particle([1.698201286351601, 0.22948004036555297], [0.0, 0.0], Inf, [1.698201286351601, 0.22948004036555297], Inf)

We can use the Logbook to save information about each iteration of the run. Let's save the average, median and best fitness:

statnames = ["avg_fit", "median_fit", "best_fit"]
callables = [mean, median, minimum]
thedict = LittleDict(statnames, callables)
logbook = Logbook(thedict)

Logbook(OrderedCollections.LittleDict{AbstractString, Function, Vector{AbstractString}, Vector{Function}}("avg_fit" => Statistics.mean, "median_fit" => Statistics.median, "best_fit" => minimum), NamedTuple{(:avg_fit, :median_fit, :best_fit)}[])

Now we can use the built-in PSO algorithm:

PSO(f, population, k_max; w=1, c1=1, c2=1)
PSO(logger::Logbook, f, population, k_max; w=1, c1=1, c2=1)

Let's use the default parameters, and 30 iterations:

result = PSO(logbook, michalewicz, population, 30);

Result(-1.7869667630510928, [2.2138980112680517, 1.553172513634117], Particle[Particle([1.428685070455722, 1.5729789857476428], [0.159565414786495, -0.0158435995264748], -0.9998494818877115, [2.1732738721113343, 1.5500178479768576], -1.7702208822709307), Particle([5.062066148334231, 1.7918254882657134], [0.5882540599147545, 0.20524146958185882], 0.27563665397460485, [2.6201681606358815, 1.56102322240344], -1.0049222229707342), Particle([-4.81405823311318, 2.2252356557901978], [4.635830129753535, -1.1137432072047928], -0.09316244535157811, [2.462384233683264, 1.6348660293752206], -1.0086612023022765), Particle([0.795316835535413, 1.5702999713782144], [-7.780861304147737, 0.029423487308228406], -0.9999900252295496, [2.196600451146207, 1.6026840206120945], -1.7594906455013994), Particle([-0.37804780050947384, -1.7278906592469454], [-1.2788806098867322, 1.549256155598798], 0.32593362714978663, [3.101973854184516, 1.5425801332880946], -0.9688057930051991), Particle([5.196057398457908, -0.009225062465880729], [-0.9715913372800933, 0.8681061728986315], 0.0020566735840459698, [-0.42290621935296124, 1.5430167101661563], -0.9697412142640489), Particle([2.9881090085000617, 0.8936528461303335], [0.7156189696279187, 2.2045979988133526], -4.3513856576635475e-7, [3.223966823490336, 1.5856933102194706], -0.99096754776653), Particle([-3.101580815948709, 0.2320185330497555], [5.647625422664895, 1.767094579843151], 3.997591054552839e-24, [-0.3003845489653445, 1.5637370610419095], -0.9979926537376673), Particle([3.2173389849314598, 1.4318285209356705], [-0.5582259050769709, -0.29636313820870847], -0.4849069316704974, [2.111179983115205, 1.5957459898811566], -1.654579217246576), Particle([-0.817497834714636, 1.1279158618806546], [4.3663480150878105, -0.3106709223508544], -0.0014235085720566718, [-0.3618457675245841, 1.5472309121557808], -0.9780770501074547)  …  Particle([-1.2953285428731636, 0.06337334698436958], [3.4168702435073977, -1.9474390982457443], 1.3139363709915775e-6, [2.1217907867611223, -0.6667687756415119], -0.7042914162387365), Particle([1.0507724181495834, 1.5149457029449434], [0.4488671696977689, 0.06746285835034718], -0.8849912469291212, [2.197541718492052, 1.7385722488185307], -1.0759747410287583), Particle([7.563530285944822, 0.6713274827261189], [-13.174141286484687, -0.7669086759631915], -3.190137298880005e-5, [-5.863566705602431, 1.7022494397973778], -0.8604040928414998), Particle([1.5765690988906864, 1.928970592747869], [0.5866695435072358, 0.41151333397518414], -0.0018038356126766793, [2.49869211553077, 1.5559781915180322], -1.0915382880926354), Particle([2.814025248409823, 1.241784152368009], [-0.24682517744103494, 0.004970037174846231], -0.023590688941040622, [2.242696635377322, 1.3984223428376281], -1.1097600287103033), Particle([1.9512628600165103, 1.5438057105610656], [-0.48547258874885796, -0.07496156390111547], -1.2203266624933695, [2.2118334269739917, 1.6169467684074077], -1.7149320161308612), Particle([3.5961348246803055, 2.09880196894783], [-1.8537952262474136, -1.232955949192212], 0.009979523782377644, [2.2257868222704555, 1.4055150320755416], -1.1566271596479112), Particle([1.5032582605012605, 1.698029521277721], [0.1678545410646366, -0.5350671257586546], -0.48820456344639696, [1.0945532203836623, 1.621069987707778], -0.89959964741122), Particle([2.620344179606402, 2.223763318274072], [-2.9329716451560532, -1.3722899053671909], -0.00872074180647769, [-0.7786228223108816, 1.587662840863214], -0.9884214174992991), Particle([1.590218321522256, 1.533818417223222], [0.5486745038111699, 0.00682854606100898], -0.9487261521111334, [2.1531506793729855, 1.563988027960315], -1.7609900907848899)], 30, 1550, 0.3782198429107666)

The output was suppressed so that we can analyse each part of the result separately using the Result functions:

@show optimum(result)

-1.7869667630510928

@show optimizer(result)

2-element Vector{Float64}:
 2.2138980112680517
 1.553172513634117

@show f_calls(result)

1550

We can also take a look at the logbook's records and see how the calculated statistics changed throughout the run:

for (i, I) in enumerate(logbook.records)
    print("it: $(i) with best_pos: $(I[3]) and avg_pos: $(I[1]) \n")
end

it: 1 with best_pos: -0.6266617676908544 and avg_pos: -0.018252293770098352
it: 2 with best_pos: -0.9865982929711137 and avg_pos: -0.22191821634591366
it: 3 with best_pos: -0.9994512974151742 and avg_pos: -0.2839931656149039
it: 4 with best_pos: -0.9994765922247122 and avg_pos: -0.3330692562966202
it: 5 with best_pos: -0.9934644140521175 and avg_pos: -0.35062294050339365
it: 6 with best_pos: -0.9998919642184088 and avg_pos: -0.42596288155425843
it: 7 with best_pos: -0.9999603224369378 and avg_pos: -0.32845222741546126
it: 8 with best_pos: -0.9996631074648755 and avg_pos: -0.3421392785945614
it: 9 with best_pos: -0.9996631356275208 and avg_pos: -0.42093756189258735
it: 10 with best_pos: -1.049232225858897 and avg_pos: -0.3697758791380901
it: 11 with best_pos: -0.9998899594899777 and avg_pos: -0.3565612886971721
it: 12 with best_pos: -1.0467260818631505 and avg_pos: -0.41175194479846783
it: 13 with best_pos: -1.7732240282650267 and avg_pos: -0.5294081626765919
it: 14 with best_pos: -1.7537732484542057 and avg_pos: -0.4487999826955131
it: 15 with best_pos: -1.7756243640351168 and avg_pos: -0.4560693807989733
it: 16 with best_pos: -1.654579217246576 and avg_pos: -0.421288513986036
it: 17 with best_pos: -1.7609900907848899 and avg_pos: -0.4544980910695759
it: 18 with best_pos: -1.3177120476299709 and avg_pos: -0.5119330968913021
it: 19 with best_pos: -1.7313308840176402 and avg_pos: -0.4763608723650634
it: 20 with best_pos: -1.3526697889752861 and avg_pos: -0.39170756134791035
it: 21 with best_pos: -1.7206162641121447 and avg_pos: -0.5576775213663206
it: 22 with best_pos: -1.569193244853281 and avg_pos: -0.43335450715436935
it: 23 with best_pos: -1.7702208822709307 and avg_pos: -0.4400774343081305
it: 24 with best_pos: -1.7594906455013994 and avg_pos: -0.3837171646870026
it: 25 with best_pos: -1.7680480722198895 and avg_pos: -0.37389735725113965
it: 26 with best_pos: -1.4313008968287873 and avg_pos: -0.4777123732786851
it: 27 with best_pos: -1.7869667630510928 and avg_pos: -0.40069454519802217
it: 28 with best_pos: -1.7571928592545023 and avg_pos: -0.4110766923008347
it: 29 with best_pos: -1.4382705040143733 and avg_pos: -0.45364484640881403
it: 30 with best_pos: -1.60254935065714 and avg_pos: -0.30239030360064617