Information about Path relinking for high dimensional continuous optimization

Una presentación de un algoritmo evolutivo para resolver problemas de optimización global que di en el Metaheuristics International Conference de 2011 en Udine, Italia.

Introduction Path Relinking Experimental results Conclusions 2

Global optimization problems ◦ Non linear function f(x) ◦ x={x1,…, xn}, l≤xi≤u Minimize f ( x) l ≤ x≤u x ∈ℜ 3

Measuring success… ◦ Scalability of Evolutionary Algorithms and other Metaheuristics for Large Scale Continuous Optimization Problems, M. Lozano and F. Herrera (Eds.), http://sci2s.ugr.es/eamhco/CFP.php ◦ 19 continuous functions ◦ Number of variables D={50,100,200,500,1000} ◦ Maximum number of evaluations: 5000D The search space is continuous… ◦ Key issue: for which points will f(x) be evaluated? 4

Introduction Path Relinking Experimental results Conclusions 5

1 Generate solutions 4 2 Select solutions both by quality and diversity (EliteSet) 3 Perform a path relinking between each pair of solutions Return the best solution found so far GRASP with PR for the MMDP 6

Path Relinking for Global Optimization (PR) ◦ EliteSet construction (x1,...,xb) ◦ Improve x1, and replace it with the improved solution ◦ NewSubsets = (x,y), pair set of EliteSet solutions ◦ While NewSubsets ≠ ∅ Select next pair (x,y) from NewSubsets Remove (x,y) from NewSubsets Perform a path relinking with (x,y) →w Improve w If f(w) < f(x1) then x1 = w 7

EliteSet construction ◦ Generate diverse solutions Sampling the solution space ◦ Based on ideas from factorial design of experiments Factorial design kn n, #variables k, #values Genichi Taguchi 8

EliteSet construction ◦ Factorial design example for n=4, k=3 81 experiments ◦ Fractional design Taguchi Table L9 9 experiments (34) Exp. Exp. Factores 1 2 3 4 1 1 1 1 1 2 1 2 2 2 3 1 3 3 3 4 2 1 2 3 5 2 2 3 1 6 2 3 1 2 7 3 1 2 3 8 3 2 1 3 9 3 3 2 1 9

EliteSet construction ◦ Taguchi method is applied to obtain diverse solutions ◦ #values k = 3 midvalue = l + ½(u-l) lowervalue = l + ¼(u-l) uppervalue = l + ¾(u-l) ◦ #variables n∈{50,100,200,500,1000} 10

EliteSet construction ◦ Problem: biggest Taguchi table found: n=40 11

EliteSet construction x1 x2 x3 x4 x5 x6 x7 x8 X9 1 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 1 1 1 3 3 3 1 1 1 1 1 2 1 2 3 1 1 1 1 1 2 2 3 1 1 1 1 1 1 2 3 1 2 1 1 1 1 1 3 1 2 3 1 1 1 1 1 3 2 1 3 1 1 1 1 1 3 3 2 1 1 1 1 1 1 12

EliteSet construction x1 x2 x3 x4 x5 x6 x7 x8 X9 1 1 1 1 2 2 2 2 2 1 2 2 2 2 2 2 2 2 1 3 3 3 2 2 2 2 2 2 1 2 3 2 2 2 2 2 2 2 3 1 2 2 2 2 2 2 3 1 2 2 2 2 2 2 3 1 2 3 2 2 2 2 2 3 2 1 3 2 2 2 2 2 3 3 2 1 2 2 2 2 2 13

EliteSet construction x1 x2 x3 x4 x5 x6 x7 x8 X9 1 1 1 1 3 3 3 3 3 1 2 2 2 3 3 3 3 3 1 3 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 2 3 1 3 3 3 3 3 2 3 1 2 3 3 3 3 3 3 1 2 3 3 3 3 3 3 3 2 1 3 3 3 3 3 3 3 3 2 1 3 3 3 3 3 14

EliteSet construction x1 x2 x3 x4 x5 x6 x7 x8 X9 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 1 1 1 3 3 3 1 1 1 1 1 2 1 2 3 1 1 1 1 1 2 2 3 1 1 1 1 1 1 2 3 1 2 1 1 1 1 1 3 1 2 3 1 1 1 1 1 3 2 1 3 1 1 1 1 1 3 3 2 1 1 1 1 15

EliteSet construction x1 x2 x3 X4 x5 x6 x7 x8 X9 2 2 1 1 1 1 2 2 2 2 2 1 2 2 2 2 2 2 2 2 1 3 3 3 2 2 2 2 2 2 1 2 3 2 2 2 2 2 2 2 3 1 2 2 2 2 2 2 3 1 2 2 2 2 2 2 3 1 2 3 2 2 2 2 2 3 2 1 3 2 2 2 2 2 3 3 2 1 2 2 2 16

EliteSet construction x1 x2 x3 x4 x5 x6 x7 x8 X9 3 3 1 1 1 1 3 3 3 3 3 1 2 2 2 3 3 3 3 3 1 3 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 2 3 1 3 3 3 3 3 2 3 1 2 3 3 3 3 3 3 1 2 3 3 3 3 3 3 3 2 1 3 3 3 3 3 3 3 3 2 1 3 3 3 17

EliteSet construction ◦ Taguchi table with 40 variables and 3 values experiments 81 We generate 81 solutions by applying this table to the first 40 variables (x1,..,x40) and setting 1 to all other variables We generate 81 solutions by applying this table to the first 40 variables (x1,..,x40) and setting 2 to all other variables We generate 81 solutions by applying this table to the first 40 variables (x1,..,x40) and setting 3 to all other variables ◦ Totalizing 243 solutions 18

EliteSet construction ◦ We move the table in steps of size 20 We obtained better results We generate 81 solutions by applying the table to the variables x21, … ,x60 and value 1 to the remaining variables We generate 81 solutions by applying the table to the variables x21, … ,x60 and value 2 to the remaining variables We generate 81 solutions by applying the table to the variables x21, … ,x60 and value 3 to the remaining variables 19

EliteSet construction ◦ # solutions generated with this process: DSize=243⌈n/20⌉ ◦ EliteSet is built choosing the best b solutions 20

Improvement is performed in two stages 1. Line search based on a single variable Grid size h=(u-l)/100 2. Simplex method Not limited to the grid 21

Improvement method: Line searches ◦ For each variable i We evaluate x+hei and x-hei, discarding the worst value ◦ We order the variables i={1, … ,n} according to these values x-hei x x+hei 22

Improvement method: Line searches 1. Explore the first n/2 variables in the order that was previously calculated: For each variable i, evaluate solutions with the form x+khei k=[-20,20] l ≤ x+khei ≤ u HOW? Randomly & using a first-improvement approach x-4hei x-hei x x+hei x+4hei 23

Improvement method: Line searches 1. Explore the first n/2 variables in the order that was previously calculated: For each variable i, evaluate solutions with the form x+khei k=[-20,20] l ≤ x+khei ≤ u HOW? Randomly & using a first-improvement approach 2. Re-evaluate the contribution of each variable, and reReorder We explore again the first n/2 variables 3. Repeat it for 10 iterations, or until no further improvement is possible 24

Improvement method: Simplex Let x be the best solution found after the first stage (line searches) We perturb the value of each variable: x=(x1, ... ,xi + α, ... ,xn) α is generated by a uniform probability in [-1,1] The simplex method is applied to these solutions 25

Relinking method ◦ Straight linking ◦ We perform the linking between three solutions An initial solution, a Two guiding solutions, x and y 26

Relinking method ◦ Straight linking y2 y x2 x a(2k-1) a(k+1) a(k-1) a(j) a(1) a2 a a1 x1 y1 27

Relinking method ◦ We start at a=(a1,...,an) ◦ Firstly we evaluate solutions in the direction given by the vector from a to x 1 a (1) = a + ( x − a ) k 1 a ( 2) = a + ( x − a) k −1 ... 1 a ( k − 1) = a + ( x − a ) 2 28

Relinking method: ◦ The best solution is chosen from previous step, a(j) ◦ Then we evaluate solutions in the direction given by the vector from a(j) to y 1 a (k ) = a ( j ) + ( y − a( j )) k 1 a (k + 1) = a ( j ) + ( y − a( j )) k −1 ... 1 a (2k − 2) = a( j ) + ( y − a ( j )) 2 29

Evolutionary Path Relinking (EvoPR) ◦ [Resende y Werneck, 2004] ◦ EliteSet evolution 30

EvoPR 1. EliteSet construction 2. Do 3. Apply relinking method to solutions in EliteSet 4. If no new solution can enter EliteSet → rebuild EliteSet 5. Until max number evaluations is reached 31

1. Obtain an EliteSet of b elite solutions. 2. Evaluate the solutions in EliteSet and order them. Make NewSolutions = TRUE and GlobalIter=0. while ( NumEvaluations < MaxEvaluations ) do 3. Generate NewSubsets, which consists of the sets (a, x, y) of solutions in EliteSet that include at least one new solution. Make NewSolutions = FALSE and Pool = ∅. while ( NewSubsets ≠ ∅ ) do 4. Select the next set (a, x, y) in NewSubSets. 5. Apply the Relinking Method to produce the sequence from a to x and y. 6. Apply the Improvement Method to the best solution in the sequence. Let w be the improved solution. Add w to Pool. 7. Delete (a, x, y) from NewSubsets end while for (each solution w ∈ Pool) 8. Let xw be the closest solution to w in EliteSet if ( f(w) < f(x1) or ( f(w) < f(xb) & d(w, xw)>dthresh) then 9. Make xw = w and reorder EliteSet 10. Make NewSolutions = TRUE end if end for 11. GlobalIter = GlobalIter +1 If ( GlobalIter = MaxlIter or NewSolutions= FALSE) 12. Rebuild the RefSet. GlobalIter =0 end if end while 32

Introduction Path Relinking Experimental results Conclusions 33

Benchmark ◦ 19 functions with known optimum 6 from CEC’2008 5 shifted functions 8 hybrid functions ◦ Requirements 5 dimensions: D={50,100,200,500,1000} 25 executions per algorithm and function Maximum number of evaluations: 5000D 34

Requirements ◦ Experiments report the error: f (x)-f (op) x is the best solution found op is the optimum of the function 35

Results ◦ Constructive methods We compare our constructive method with the method described in [Duarte et al., 2010] 1000 constructions F3, F8, F13 50 100 200 500 1000 Frequency 5.3E10 1.1E11 2.7E11 7.3E11 1.5E12 Taguchi 3.7E10 6.0E10 1.3E11 3.7E11 7.6E11 36

Results ◦ Improvement methods We test several methods that were reported as the best ones for global optimization (Hvattum et al., 2010) 100 constructions (Taguchi) + Improvement + Simplex F3, F13, F17 50 100 200 500 1000 CS [Kolda et al., 2003] 8.2E13 2.8E14 8.0E14 1.7E15 2.1E16 SW [Solis y Wets, 1981] 3.2E10 6.2E10 1.4E11 1.9E11 8.4E11 TLS [Duarte et al., 2010] 1.7E9 5.2E9 1.3E10 2.3E11 9.7E10 TSLS 1.8E3 4.1E3 1.2E4 2.2E10 4.6E4 37

Results ◦ Path relinking methods Static PR and Evolutionary PR F3, F13, F17 PR EvoPR |ES| 10 4 8 12 50 6.2E1 7.6E1 5.2E1 7.9E1 100 1.3E2 1.8E2 2.5E2 6.1E2 200 5.2E2 4.8E2 9.8E2 1.7E3 500 2.3E3 1.6E3 2.7E3 4.3E3 1000 5.8E3 3.9E3 6.7E3 8.9E3 Average 1.7E3 1.3E3 2.1E3 3.1E3 38

Final experiment ◦ 19 functions, 5 dimensions, 25 runs per method and function, 5000D evaluations ◦ Average error is reported DE CHC G-CMACMAES STS EvoPR 50 3.1E0 2.4E5 1.0E2 1.3E2 1.4E1 100 3.0E1 5.8E6 2.3E2 6.2E2 6.3E1 200 3.5E2 1.4E8 5.4E2 2.8E3 1.9E2 500 3.7E3 3.4E9 2.2E255 1.9E4 3.7E2 1000 1.5E4 2.0E10 - 1.4E4 1.2E3 Average 3.7E3 4.8E9 5.6E254 7.2E3 3.7E2 39

Introduction Path Relinking Experimental results Conclusions 40

Path Relinking for Global Optimization ◦ Constructive method based on Fractional experiment design Diverse solutions ◦ Linking strategy with more than two solutions ◦ Improvement method Line search with grid First-improvement approach Random evaluation of points 41

A balance between... ◦ Solution space exploration ◦ Limited number of evaluations Competitive method compared with state of the art ◦ EvoPR performs better in high dimensions 42

you! Thank you!

MIC 2011: The IX Metaheuristics International Conference id-1 Udine, Italy, July 25–28, 2011 Path Relinking for high dimensional continuous optimization

Read more

Path Relinking for high dimensional continuous optimization. Authors. ... Path Relinking for high dimensional continuous optimization. Authored by

Read more

View 324 Relinking posts, presentations, experts, and more. Get the professional knowledge you need on LinkedIn. LinkedIn Home What is LinkedIn? Join Today

Read more

Path Relinking for Large Scale Global ... Since we are facing high dimensional ... of the path relinking (PR) for optimization of large scale ...

Read more

Path Relinking and GRG for ... unconstrained nonlinear optimization problem, ... lower and depends on the dimension of the input space.

Read more

View 2995 Continuous Optimization posts, ... continuous innovation is what buyers want. ... Path relinking for high dimensional continuous optimization.

Read more

The AID Method for Global Optimization ... Path relinking processes ... Unidimensional search for solving continuous high-dimensional optimization ...

Read more

... An Adaptive Memory Procedure for Continuous ... GRASP and Path Relinking for the ... for solving high-dimensional continuous optimization ...

Read more

high-dimensional continuous optimization problems more efﬁciently. ... variants: the static and the evolutionary path relinking. Both

Read more

## Add a comment