Improving Search Space Exploration And Exploitation With .

1Improving Search SpaceExploration and Exploitation withthe Cross-Entropy Method and theEvolutionary Particle Swarm OptimizationLeonel Carvalho, Vladimiro Miranda, Armando Leite da Silva,Carolina Marcelino, Elizabeth Wannerleonel.m.carvalho@inesctec.pt08-08-2018

2Methodological Approach Combination of two optimization methods– Cross-Entropy (CE) Method for exploration– Evolutionary Particle Swarm Optimization (EPSO)for exploitation New recombination operator for multi-period constraintsControllable Factors EPSO parameters were tunedusing an iterative optimizationalgorithm based on a 22 factorial design– Mutation Rate τ– Communication Probability Px1x2xp.InputMetaheuristic.z1z2zqUncontrollable FactorsOutputy

3CE Method for Optimization Heuristic method proposed by Reuven Rubinstein forcombinatorial and continuous non-linear optimizationbased on the Kullback–Leibler divergence– Kullback–Leibler divergence (relative entropy) is a measure ofhow one probability distribution diverges from a target one It is based on the concept that optimization problemscan be defined as a rare-event estimation problem– The probability of locating an optimal or near optimal solutionusing random search is a rare-event probability

4CE Method for Optimization Instead of random search, the CE Method sets anadaptive iterative importance sampling process– The sampling distribution (Bernoulli, Binomial, Gaussian,Multivariate Bernoulli) is modified in each iteration so that therare-event becomes more likely to occur The optimization process starts by defining a samplingdistribution for the variables followed by an iteratedadjustment of the distribution parameters (e.g. mean,standard deviation) according to the performance of anelite subset of the samples

5CE Method for OptimizationSelect µ0 and σ02, the number of samples per iteration N, the rarity parameter ρ, the smoothingparameter α, k : 0Dok : k 1Generate a sample of X1, , XN from the sampling distribution N(µk-1, σk-12)Compute S(X1), , S(XN) and order the samples from the worst to the best performing ones, i.e.S(X1) S(X2) S(XN)Compute γk as the ρth quantile of the performance values and select Nelite ρN; let ψ be the subsetfrom the ordered set of samples that contains all the Nelite samples, i.e., the samples S(X) γkFor j 1 to nµ kj : End ForApply smoothing i ΨX ijNeliteμ k : α μ k (1 α ) μ k 1Until k kMAXσ kj2: i Ψ(X ij µ kj ) 2N eliteσ 2k : α σ k2 (1 α ) σ 2k 1

6CE Method for Optimization0.07k 0k 8k 16The mean and varianceof the distribution isadjusted until there is aconcentration ofdensity at the optimum0.060.05Probability0.04k 240.030.020.010-600-400-2000200400Pg1 (MW)60080010001200

7EPSO Evolutionary Particle Swarm Optimization (EPSO) isan hybrid between Evolutionary Strategies andParticle Swarm Optimization proposed by VladimiroMiranda in 2002–––––Replication: each individual is replicated r timesMutation: the r clones have their weights w mutatedRecombination: the r 1 individuals generate one offspringEvaluation: each offspring has its fitness evaluatedSelection: the best particle out of the r 1 survives to bepart of a new generation

8Recombination in EPSO Movement Rule𝐗𝐗 new 𝐗𝐗 𝐕𝐕 new 𝐗𝐗 𝑴𝑴 𝐗𝐗 𝑤𝑤𝐶𝐶 𝐏𝐏 𝐗𝐗 𝑮𝑮 𝐗𝐗𝐕𝐕 new 𝑤𝑤𝐼𝐼 𝐕𝐕 𝑤𝑤𝑀𝑀. 𝐗𝐗 new– Inertia: movement in the same direction 𝑤𝑤𝐼𝐼 𝐕𝐕𝐗𝐗 𝑹𝑹– Memory: attraction towards the𝐗𝐗 𝑤𝑤𝐗𝐗 𝑀𝑀 𝐗𝐗𝑀𝑀individual best solution𝐗𝐗 𝑮𝑮 𝑤𝑤𝐶𝐶 𝐏𝐏 𝐗𝐗 𝑮𝑮 𝐗𝐗– Cooperation: attraction to a region𝐗𝐗 𝑮𝑮near the global best position.

9EPSO Particularities Weights are mutated and subjected to selectionMutation Rate𝑤𝑤 𝑤𝑤[1 σ𝑁𝑁 0,1 ] The individuals are attracted to a region near the best solutionfound 𝐗𝐗 𝑮𝑮 𝐗𝐗 𝑮𝑮 [1 𝑤𝑤𝐺𝐺𝐺𝐺𝑁𝑁 0,1 ] Matrix P acts as a communication barrier 𝐕𝐕 new 𝑤𝑤𝐼𝐼 𝐕𝐕 𝑤𝑤𝑀𝑀𝐗𝐗 𝑴𝑴 𝐗𝐗 𝑤𝑤𝐶𝐶 𝐏𝐏 𝐗𝐗 𝑮𝑮 𝐗𝐗1 0 0𝐏𝐏 0 00 0 0𝐗𝐗 𝑮𝑮CommunicationProbabilityIf i j then Pij 0ElseIf U(0,1) p then Pij 0Else Pij 1

10EPSO Recombination in the 2018 Competition Test Bed B consists of a Dynamic OPF for 6 periodsthat considers ramp constraints for generators (5 x 53constraints)– Feasible solutions are difficult to obtain since theproduction in each period can be highly conditioned by theproduction in the adjacent periods Idea: to compute a new production for the currentperiod based on the recombination of this productionwith the production of the next period

11EPSO Recombination in the 2018 Competition Additional recombination rule for ���𝑗: 𝑋𝑋𝑖𝑖,𝑗𝑗𝛿𝛿 𝑋𝑋𝑖𝑖,𝑗𝑗 1(1 a(4,4)0.7Beta(16,16) x)0.60.5P( 0 δ 1 is random variablethat follows a Beta(α,β) pdfBeta(0.5,0.5)0.4 Beta(0.5,0.5) was selected0.30.20.1000.10.20.30.40.50.60.70.80.91

12EPSO Recombination in the 2018 Competition In EPSO, integer variables are modeled as real variablesand rounded for fitness computation To force diversity, after the computation of a newposition, each integer in the new position is comparedwith that of its predecessor and, if all integers in the twopositions are equal, then one integer in the new solutionis randomly selected to be increased/decreased by thevalue of 1 with probability 0.5

13Switch from CE Method to EPSO101010101211CE Method1010FitnessWhen to switchfrom methods?1310101010109EPSO8765400.511.522.5#Fitness Evaluations33.544.55104

14Switch from CE Method to EPSO Trial & error– Not very clever but a practical approach for the competition Track the rate of improvement of the best fitness over anumber of iterations and switch when the rate becomesinferior a given threshold– A new parameter has to be defined Monitor the variance of the CE Method samplingdistributions– The problem is that the variance can decrease very slowly for variablesthat can take a wide range of values without significantly affecting thefitness function

15EPSO Parameter Tuning Iterative method based on 22 factorial design and the Two-wayANOVA to guarantee the best performance for EPSODefine maximum allowable interval for τ and P (e.g. [0.2, 0.8] )Run a 22 factorial design (4 experiments)Perform 4 31 runs of EPSO for the 4 combinations of the limit values of τ and PDoRun Two-way ANOVA and select the variable with the highest F-test statistic/thelowest p-valueCompute the main effect to determine which limit should be updatedUpdate the limit to the central value of the current interval (e.g. if the outputdecreases with the variable increase, then set the lower limit to the central value)Run a 22 factorial design with the updated limits ( 2 experiments)While there is evidence that τ and P affect the output (p-value less than 0.05)or if the difference between interval limits is greater than a value (e.g. 0.1)

16Parameter Tuning for MinimizationSetting values for τ and PTwo-way ANOVA resultsFactorτPτ PτPτ PτPτ PτPτ PF-test Statistic P-value Main Effect1st 3689.172nd 23286.793nd 9187.144th 81244.34FactorIteration1st0.20.80.20.8τ (low)τ (high)P (low)P .354x 1054.94.84.74.64.54.44.34.2Greater than thethreshold level of 0.05ABCDBox-plots for the final range of τ and P

17Results Test Bed A – Stochastic OPF: 12 independent runsFitnessCase 1Case 2Case 3Case 4Case 5Best80,732.46 67,709.06 55,245.86 84,382.21 71,044.22Worst81,547.19 68,923.91 56,683.60 84,880.76 71,128.74Mean81,077.07 68,473.43 55,935.62 84,442.94 22.97

18Results Test Bed A – Stochastic OPF: 12 independent runsTest Bed A - Case 31010log(Best 4

19Results Test Bed A – Stochastic OPF: 12 independent runsTest Bed A - Case 51010log(Best 4

20Results Test Bed B – Dynamic OPF: 10 independent dDeviation15,175.7915,618.73

21Final Remarks Combination of methods to address different stagesof the search can greatly improve accuracy androbustness of heuristic methods Systematic parameter tuning is essential to reducethe information required from the user Sometimes tailor-made recombination rules to dealwith specific constraints of the optimizationproblems can lead to better performances

22Thank you for your attention!Leonel Carvalholeonel.m.carvalho@inesctec.pt

Improving Search Space Exploration and Exploitation with the Cross-Entropy Method and the Evolutionary Particle Swarm Optimization Leonel Carvalho, Vladimiro Miranda, Armando Leite da Silva, Carolina Marcelino, Elizabeth Wanner. leonel.m.carvalho@inesctec.pt . 08-08-2018 . 1