Chapter 1: Introduction PDF

Chapter 1: Introduction Course instructor: Prof. Roland Bouﬀanais (UNIGE) 1 semester 6 credits Review of course syllabus Textbook: livre PUP/Springer 1 / 42 To get started: let us consider the following example I Let us consider n people in a 2D space, each at positions xi , i = 1,... , n. I Problem: Find the point y where these people should meet to minimize the sum of the distances traveled by each of them. I What is this point? Geometric median, by definition (see 1D example) Xn argmin kxi y k y 2R2 i=1 I No analytical solution, but an iterative algorithm: Weiszfeld’s algorithm: ! ! X xi X 1 yk+1 = / n |xi yk | n |xi yk | i=1 i=1 I Numerical solution by hill climbing (or steepest descent) https://en.wikipedia.org/wiki/Geometric_median 2 / 42 letusstartwithabasicexam n people i n a 2 D space y÷p¥§§ P:@12 By, I i (Fyi) xnµ Question: Find the meetin point mimizing thet o t a l distance gtraveled individuals by a l l let u s denote by 1 that meeting point → minimize E."Ii-1" , develo To p someintuition about this problem, let u s turn problem t o the a d versionofthis - 3 1 1 5 ¥ t Median point [Pi,13,1304,B ,R ] i s this optimal point Backi n 213: Clearly the centroidi s not that point! → themedianpoint yieldsthatoptimal → like i n TD: point challen i s howt o computethat medianpoint → Now,the ge median.-yon.. qq.m E."Ei'I II g; exists! ↳ N o analytical solution ↳ We're left with a n approximat solution based e o n a n iterative process usingtheWeiszfeld's algorith in.i÷÷÷E÷i÷ m h en Yoppmedian In → difficult optimization if Conclusion: problem considered not a numerically. Illustration Distance between (x,y) and a set of points z=distance(x,y) height 100 350 350 40 0 300 400 400 80 250 350 350 total distan 60 300 300 y ce 250 40 200 100 250 80 60 20 0 40 200 y 20 40 20 60 200 x 0 30 30 80 0 0 0 100 0 20 40 60 80 100 x 3 / 42 Here is a diﬃcult optimization problem 4 / 42 1.1 Search Space I Unconstrained optimization: Classicaly, solve an optimization problem specified as: find x 2 S so that f (x) 2 R is maximal/minimal. xopt = argmin/argmax f (x) x2S fopt = min/max f (x) x2S I Constrained optimization: Usually, in optimization problems, x may be subject to given constraints (e.g. kxk < b). The constraints can be expressed by restricting S to acceptable solutions. 5 / 42 "T.si?:...................... "' The objectiv i s t o solve a general optimization problem e I n form, i t s most general sucha n opt.probl. c a n is {maxim → maximization minimization)→ problemdependent. al✓ Mal→ Mere mathematicall find.gg#aaigi y iiiIIh, sees Optimal solution OptimalValue: fopt-fln.pt) Yopt¥§, Yep, = {mmm Kopi. = m,} flat n es ' I n mostpralicalcases, optimization problems a r e subject t o CONSTRAINTS (wethenspeak of constrained optimization). tramplei N >o a r n L l. - n (N, 22] Rftate4 ↳ x lieso nthecircle centered abouttheoriginandwith radios2. These constraints reduce the search space 8 , whichi s the candidate solutions t o maximize/minimize the set ofall function f i → Objectivefunction ÷¥÷o:*::*.''!:*" → toss thiscoursesince inspired bynature Search Spac c a n be: The e 8 that doesn'tmeanthe problem discrete - solve!! - willb e easier t o - continuous - finite - infinite hostlfitnea function: As forthe Mathematically fi 8 ¥ alwaysreturna numericalvalue order relation: higher, lower, with some sort of good, bad, better,... fly,@fmIIiopmjIIy. Consideri the optimalvalue ng aopt: c, ¥ minimization €÷io.÷÷÷ ÷÷÷÷.. uniq "op te ue,] Noy, g aµ. may not be ② fopt i s necessari ly unique. {9%11}optima ③I n a real problem, w e have Manyoptimization techniques find localoptima,yettheglobalo n emighthard n o t (if impossible t o find→ B u t that'stheo n ew e w a n t Definitions & notations I S is the search space I S can be discrete, infinite or continuous. Usually, here S is very large I The elements x of S are called: possible solutions or configurations I The function f is called: objective function, cost function, loss function, fitness, or energy: f : S ! R I Optimal solution xopt : f (xopt ) f (y ), 8y 2 S I Optimal value: fopt = f (xopt ) I Unicity of xopt and fopt ? I Global or local optimum 6 / 42 Search space I In general, multidimensionnal problems: x = (x1 , x2 ,..., xn ). n is the problem size, or the number of degrees of freedom I The cardinality of S grows exponentially with the problem size. xi 2 S i S = S1 ⇥ S2... ⇥ Sn |S| = |Si |n I The diﬃculty is that S is too large for an exhaustive and systematic exploration I Metaheuristics: oﬀer a way to explore S when no exact polynomial algorithms exists I Metaheuristics contrasts with “Convex optimization” for which a lot of algorithms exists. 7 / 42 M u l l i n a l e 8 ↳Typically, ± has many components (meter) I = ( M , M '. ' - '"OI, n i s the#of degrees of freedom ↳ n i s t h e problemsize ↳Assume N iE S i , then B - S ,x £ x.. - xS n 1 $I = Card S Is i t = It, =,¥ (Si) Card [¥ the size ofthe searchspace growsexponentially with the problems i z e n T h i s i s where METAHeuristics comei n handya s theyoffera n effectiv explore whileavoidinga n exhaustive e way t o § search ↳ Not specific t o a givenfamilyofproblems a s i n thec a s e ofconvex optimizationforinstance optimizationproblems SomeExampby i Here a r e some examples ofHeuristics which o r mayn o tneed META may ContinuousConreimization 8.-R" ① ↳we c a n simply compute (andfellow)the gradient off ↳ If-I ⇐, 3¥, o tri local extrema a n d n o t always globalone ↳ Checkthe second derivative t o know i f itsaamaxminer Constrainedlontinuoustonrexoplimizat ② ↳ Example: Maximize f l a , ,% ) with constraintgla,.az).-o ↳ Lagrange multipliers: Find 1 - l a ,n e , s u c h that I f = X Ig → N o needforMetaharistics 1.2 Examples I S = Rn : Continuous optimization problem. Derivatives (numerical ones), Lagrange multipliers, Local/global optima. These need to be examined individually and consider border eﬀects. Lagrangian Multiplyer 1 I maximize f (x1 , x2 ) with the constraint that g (x1 , x2 ) = 0 I y gradf = gradg I is a Lagrange multiplier -1 -1 1 x 8 / 42 More examples I Linear programming: method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear relationships. P Maximize P z = f (x) = i ci xi with the following constraints n i aij xi  bj. x 2 S = R. Solutions are at the border of a convex polygon (SIMPLEX algorithm). Things get tricky if x 2 S = {0, 1}n. I Knapsack: P Pobjects of value pi with size wi. Maximize n pi xi with wi xi  c. xi 2 {0, 1}, c > 0 size of the sack. I Traveling Salesmen Problem (TSP): Combinatorial optimization problem (i.e., quadratic assigment problem 1QAP) 9 / 42 ③ linear Programming (LP) %b6m.im#zeZifcoy=i.E, C ir i l!;] = I I = cc...-on, a iE R f i (possibly subject t o m verylarge) linearconstraints if, A i j n i E bj tj.-g...,m with Caij),( b j ) ,(Cj)geike n There i s a n algorithm t o solve L P problems:simplex Simplex works Mostofthetime,i n a rathershort time, B u t sometimes fads!! here 8=112". B u t i f $.-fo,I }" Note that a i= fo, L P becomesmuch(won) minfowed Knapsackproblemy.. ④ a n d size W i Kiel,...,n n objects o f value p i ¥,w i s e.. ← Maximize It,pini while having (binary). c with a i= { l ,o } ⑤ t a ndefinition: k : tsp, Problem w e have a salesmanthat must visit hometown. n cities and eventually t o their the citiesbe visited t o ↳ I n which ordershoulddistance? minimize the traveled ÷÷ "ii. ÷, ÷. different pathsc a n w → with n cities, how many e consider? possible paths correspondingt o L, There a re n! all possible permutations CE IEEise n! Even withh e rs o , AB; HUGELY difficult. D} this i s Still more examples: NK problems I MaxOne problem I NK-problems. S Kauﬀman, gene regulatory network. N genes, linked to K others: graph with N nodes and degree K. x 2 S = {0, 1}N. N X f (x) = fi (xi , neighborsi ) | {z } i K args with K 1 neighbors of xi. MaxOne: K = 1. I Case K = 3: h(111) or h(110) is max. I NK problems are theoretically interesting since they oﬀer synthetic search spaces, especially when N and K are growing 10 / 42 More about NK problems I Let us consider N people with two commercial strategies denoted by xi = 0 or xi = 1 (binary type) I The success of each strategy critically depends on the strategies of other people (inter-dependency – complex systems), and their relationship (cooperation vs. competition) I Each individual is influenced by K others. The function indicates the resulting profit/gain associated with the strategy adopted by agent i given the inter-dependency with the rest of the collective I The overall collective profit/gain for the system of N agents is P simply the sum f = fi. 11 / 42 ⑥NK-ProblemI. Thisi s a n importantclass of optimization problems througho We will revisit i t this course. ut Kauffman (Bioinformatics). I t was introduced by Stuart regulator network t o describe gene y Model construction: → genes a r e given a binary statusE a r l i.e., active o r innate. influences the → the state ofa gene FIFE!.it#..ofoAergenes → N i s the total # o f genes → K is the number ofneighbors of each gene (i. e.the degreei n network parlance) Problem definition: in a fairly abstract way the so-called MaxOne problem ① Simplest example : if s ', fo, I = (a.....,an) i s a binarystring i e.. I = o no l o... i etc Maximize texts÷§ , d i i-e. I i opt 11114mg , problemfermentation: ②General a NK-problem c a n beexpresseda s Maximize fuel.- filai, ¥.. neighbors;) Kagame' i n total (includingn i ) f i i s the fitness of gene i neighbors; are all the genes j neighbori genei ng F o r instance, w e the MaxOne problem → i); neighbor fini,s d i simplye i doesnotdependo nthers neighbo Basic example: K = 3 EYETIE!!:P?''sam → " e function h lo a " genes ¥-2h f #' = Cai,a , , , ,a +. a , problemi * If h i s Max far h11,1,1 1 t h e s easy andthe optimalGlutton i s again 1 : ( I ,I... 1 ). * t h e problem getsreallytrickyi f h i s max for 1 0 1 andsmall fer t ofindthe 0 1 0 → Hard optima, Nk-problems a r e of interest t o u s a s they offer a problems of syntheti class c of optimization L, whose difficulty c a n betuned by increasing N and K 1.3 Revisiting computational complexity I To find an optimum solution, one needs an eﬃcient algorithm (obviously!) I The computational eﬀort required by an algorithm is given by the required amount of memory M and the computational time T I M and T are the space and time complexity of the algorithm respectively I Usually, the complexity of the worst case is considered, or that of the average case. I One usually consideres the asymptotic complexity, that is the relation M(n) and T (n) as a function of the problem size n 12 / 42 Refresheraboutalgorithmiccomplex ity which (complexit class a r e w e going t o work?. I n y) algorith should solve a An"efficient" problem "fastenough" m , e ve n for large proble sizes n m algorith c a nbe measured The "efficiency" ofa n m bytwometrics: - Time y complexit Tn ) → #of operations Size - Spac Complexit e y Mln) → ofmemory seek Typically, w e T I M G' M " forthe averagecase o r the worstcase informative enough t o have I n general. it's the asymptotically ↳ Behavior of Tc u ) & Mini for m e n ↳ Afterall, we're not interested i n small problems? ↳ Big "O" notation Tln): O (fan) meansthat thereexists n o and a constantk suchthat then TIME k fln) if n g i e. forn largeenough Ttiounded by fin, Example, Ten,= 0. 5 n ' t2 h t 6 1 " " ↳the " N " term dominatesa t large n → H u t= n t logn c ht h = 0 (h) problems w e have algorithm witha For a class of, s nmojnge pigmy.' it. T i n ,= o finganial, ↳ like 3 m e sorting, matrix multiplation/inverse ↳ These problemsbelon g t o the so-called P. class of complexity Measuring complexity: the big “O” notation I Complexity is expressed with an expression like “O()”. I If one says that T (n) = O(f (n)), it means that there exists a constant k and a value n0 such that if n n0 then T (n)  kf (n). For instance: T (n) = 0.5n2 + 2n = O(n2 ) T (n) = n + log(n) < n + n = O(n) 13 / 42 Algorithmic Complexity I For some problems (sorting, matrix multiplication, etc), an algorithm is known that solves them in a polynomial time T (n) = O(nm ) with m usually small. These problems belongs to the P-class. I For other problems no polynomial algorithms is known (or none exists!). There are only exponential algorithms. For instance T (n) = O(2n ) I These problems are computationally challenging because T (n) becomes excessively large when n increases even moderately. 14 / 42 Intractability of exponential problems n 10 50 100 1000 log2 n 3 6 7 10 n3 1000 125’000 106 109 2n 1024 1.3 ⇥ 1015 1.27 ⇥ 1030 1.05 ⇥ 10301 n! 3629 ⇥ 103 3.041 ⇥ 1064 10158 4 ⇥ 102567 15 / 42 Complexity Classes I In complexity theory, there are problems said to be in classes P, NP, NP-complete or NP-hard I The P-class contains problems which can be solved by a polynomial algorithm. I NP means non-deterministic polynomial as they can be defined through a non-deterministic Turing machine I NP problems are those problems for which a given solution can be verified in a polynomial time. I Thus, P-problems are obviously in NP. 16 / 42 Complexity classes and “hard-optimization” I NP-hard problems are those whose solution solves any NP-problem, up to a polynomial transformation I Problems that are both in the classes NP-hard and NP form the class NP-complete. I NP-complete problems comprise of Graph coloring, satisfaction problems, finding hamiltonian cycles in a graph,... I NP-complete and NP-hard are solved with exponential algorithms. 17 / 42 Complexityclassee algorithmic complexity, w e distinguish I n the theory several classes of ① R class : problemsthatc a nbe solved i polynomial line na ② NP-class: problems for whichpolynomItime asolution eanbe¥¥in only verified P E Np B u tNOT FOUND, ③ N P.hard : problems whose solution solves ANY N Pproblems, u p t o a polynomial transformation Complete: problems that a r e both i n N p ④ N P. a n d NP-hard ↳e g.. graph coloring,Hamiltonian cycle NOTEL: NP-hard & N P.complete algorithms c a n b e solved with exponentialalgorithms 0%50 (Np. complete. Complexity Classes P NP NP-complete NP-Hard 18 / 42 Example: Hamiltonian cycle Find a close path that goes through all nodes once and only once a a 1 1 1 1 b c b c 1 1 1 1 1 1 d d Note that the length of the path is 4 and is equal to the number of nodes. 19 / 42 "amiYI.%a9dea.se? bpI-th that goesthrough a " the nodes once § ONLY O N C E itiniitimiipa, j¥÷ ' ↳ Decisionproblem(Yoshio) ↳ Nota n optimizationproblem TSP finds out if an Hamiltonian cycle exists Construct a n Optimization problem basedo n theDecisionproblem → of o f t h e existence a n Hamiltonian cycle TSP (Traveling Salesman Problem): find the shortest path that goes through all nodes once and only once, assuming a fully connected graph. Add missing edges with weight 2 a a Several possible 2 2 1 Hamiltonian → 1 b c b c 1 1 cycles 1 1 µ optimization 1 1 d d No Hamiltonian cycle Shortest tour is of length 5 and not 4 µ N o optimizationpossible 20 / 42 TSP is a NP-hard problem I TSP is not in NP as one cannot check that a tour is of minimal length in a polynomial time I Finding a Hamiltonian cycle is not in P as no algorithm is known to find a Hamiltonian cycle in a polynomial time. I Finding a Hamiltonian cycle is known to be NP-complete (diﬃcult to demonstrate) I TSP solves the Hamiltonian cycle problem I TSP is therefore NP-hard → optimization problems a re typically N P.Hard. Hence,w to e resort METAHEI.es4 21 / 42 Complexity Classes: a Summary Hamiltonian cycle P NP NP-complete NP-Hard sorting Factoring TSP large intergers 22 / 42 Hard-optimization I Many optimization problems that need metaheuristics are NP-hard. One calls them Hard-optimization problems I A deterministic solution would require an exponential algorithm I Metaheuristics are then used I But, what is then the complexity of a metaheuristic? 23 / 42 1.4 Metaheuristics I Metaheuristics: term coined by Glover in 1986 I For many real-life problems (OR), no polynomial algorithm exists. (But for other problems yes!) I If n is large, the search space S becomes too vast to use an exponential algorithm I Metaheuristics are meant to explore S in a somewhat “intelligent" fashion to find optimals. (hopefully in a more eﬀective way than through a pure random sampling) I Trade-oﬀ between quality of the solution and computational cost (i.e. CPU time): able to return an acceptable solution in a reasonable amount of time 24 / 42 GOAL:. NP-Hard Optimization Problems ↳ "Exact" algorithms a r e exponential ↳ "Exact" solutioni s effectivel o u t ofreach y. Search space 8' 5×5×11,1, i n. - problemsite → There a r e strategies t o find solutions i n a shorter time t h a n exponentials and with less memory , usage than required when searching 8 inan exhaustive way → "META" means herethat o u r strategyw i l l b e va l i df o rMANYproblems Heuristics vs. Metaheuristics I Heuristics: methods of exploration that exploits some specific aspects of the problem at hand and only applies to it. I For example, when solving a LP problem by the simplex algorithm, a heuristic is often used for choosing so-called entering and leaving variables. I Metaheuristics: general exploration methods, often stochastic, that applies in the same way to many diﬀerent problems. I Examples are tabu search, simulated annealing, ant colony, and evolutionary algorithms. Topic of this course!! I Algorithms for approximation: seek to find solutions to specific problems with a chosen quality and with specific limits in terms of CPU time 25 / 42 Characterization of Metaheuristics so-called GUIDINGPARAMETERS (The I No hypothesis on the mathetical properties of f. The only requirement is that f can be computed for all x 2 S I Based on a number of parameters that guide the exploration, - and which aﬀect the quality of the search. Their optimal values are often found empirically for a given problem I Require a starting point (initial configuration), either selected at random or based on other strategies I Require a halting condition: e.g., CPU limit, boundary on the quality of the found solution, etc. ↳Therei s n owayt o know the explorationhas reached if theglobaloptimum.So, w e stopwhenthe CPUbudget has been spent,o r i fa stagnationo fthe fitness keeps being experienced aftera longtime 26 / 42 Characterization of Metaheuristics (more) I In general, they have a stochastic component and can be inspired by natural processes I Oftentimes, they have heavy CPU requirements (not cheap!), yet they are easy to implement and can readily be parallalized I Classically, they combine two key actions: intensification and diversification, more commonly exploitation and exploration: either we search for more promising solutions in S, else we further analyze a found region of interest Goldend rule: never use metaheuristics if another method can be applied! Tertius {exploitatio {Diversifica Exploratio } 'intensification o r e r n BALANCE tion n} 27 / 42 A metahewishis provides: → ①No guarantee of success ② N o guarantee ofthequality ofthebest solutionfound But i n practice, heuristics offera meta good → COMPROMISE between quality § {CPU time usage} memory 1.5 Operating Principles ' " ' "" " " " " I There is a critical need to find a suitable representation of the problem within the given search space S: i.e., how to code the possible solutions I A metaheuristic is a trajectory within S. t"::.....:÷÷÷÷ I To define this trajectory the motion along it, the following ingredients are required: I (1) Neighborhood V (x) for all x 2 S: these are the y reachable from x. ÷÷i÷¥:..'' aaa..... 28 / 42 How d o w e m ove i n §? ① We e defin the concept of NEIGHBORHOOD Fas) t e x t s ÷÷÷÷÷÷÷ ÷÷÷÷. ② we define moves/ transformations by means of a n operator U d oI s I ,t U (b) ETC#IsI z ETH.).... U i sa "search" o r "exploration" operatorthatselects the next point i nthe neighborhood Both F and V havet o b e specified ↳v i s typically a signature of each metaheerishis ↳ that each metahewistics hasits ow n way t o m ove through $ Operating Principles (more) I (2) Search/exploration operator U that selects among the neighbors within the current point along the exploration trajectory U U x0 ! x1 2 V (x0 ) ! x2 2 V (x1 )... I This process goes on until the halting criterion is activated I Depending on the metaheuritic, the output is either: (i) the point x corresponding to the optimal fitness f (x) found along the trajectory, or (2) the last point x along the trajectory 29 / 42 How to define the neighborhood? Twomain ways: ① I Find ways to explicitly express V (x) for all x 2 S: often unpractical if not impossible ② ( I In general, the neighborhood is specified by means of ` 1 elementary transforms Ti (or movements) such that Ti (x) 2 V (x) V (x) = {x 0 2 S|x 0 = Ti (x), i = 1,... `} practical s o F ( X l contains l way possible successors of± 30 / 42 Example #1: Movements in S = Z2 with 8=272, the neighborho# x ) i s the s e t integers od of I i j, ) corresponding t o the positions o n the lattice x 2 S ) x = (i, j) For instance, we can consider for cardinal movements denoted as NORTH, EAST, SOUTH and WEST such that "i.1 ) N(i, j) = (i, j + 1) Elementary E (i, j) = (i + 1, j) transformations (1) S(i, j) = (i, j + 1) %fF.IT: 1 w W (i, j) = (i 1, j) moves The choice the elementartransformations/moves of y i s arbitrary ( i t c o u l dincludediagonalmoves!) TheneighborhooTex, c a nb elargeO Rs m a l l d 31 / 42 Example #2: Permutations ¥ 9 combinatorial optimization I Let us consider the search space S of permutations of n objects I With n = 3, we have A = {(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)} = 3 != 6 with |A| = n!. I One can define a neighborhood of a given permutation by the set of permutations that can be generated through a given operation ( I ,a%I¥b,....)Te,(...,bi,n.. n.) &, I For instance, transposing (i, j), which consists in swapping positions i and j. I t i s howeververy important that any permutation i n 8 anyothero n e i n § bya FINITE generated from application c a nb e transformations of (i,j ) 32 / 42 Example #2: Permutations (more) I For n = 5, the selected movements are: I::÷; mi 2 { (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (number (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)} of I For example, the permutation (a3 , a2 , a4 , a5 , a1 ) admits ,µµ,µaµi,µµ§µgµ, (a2 , a3 , a4 , a5 , a1 ) as neighbor when applying the movement (1, 2) that transposes the first two elements All permutations are a finite product of transpotisions D Incond-usion: 141=64') and 18't o f u ! ) small!). → 1 ¥⇐ i (very 33 / 42 Notes on neighborhood I Some metaheuristics do not explore the complete neighborhood before moving to the next point I Typically, they use a stochastic element to randomly establish the next point, “hoping" that it would yield an optimal value for f in S I For metaheuristics conducting an exhaustive neighborhood search, we can define a hierarchical structure of the neighborhood: I If nothing useful is found at the 1st level, we move to the 2nd level, and so on so forth; I If nothing better is found, we stop the neighborhood search I Global vs. local search 34 / 42 Elementary exploration strategies (seedetailed noteso n annotated slides) uniformsampling I Random walks : of S '→ extremelyunlikelyt osucceed I Neighborhood-dependent random walks: randowwalks withinV a , ↳ s t i l l unlikelyt osucceed I Hill climbing → typically getsstucki n a localoptimum I Probabiliste hill climbing: probability to select a neighbor p(x) = f (x)/ f (x 0 )→ m o v et o o n e of yourneighborwitha P probability proportional t o thefitness I... p Case of backtracking and branch-and-bound algorithm: these are not metaheuristics (systematic search space exploration) but they share a number of characteristics with metaheuristics: (i) neighborhood selection (children), no specific property required for the fitness function NOTEG: Recall thatthechoice oftheneighborho mayaffectthe search! od quality ofthe 35 / 42 Iterated Local Search Let us consider a metaheuristic localSearch that gets stuck on local optima. One can construct a more powerful metaheuristic: y’ x’ y fitness search space I Reduce S to S 0 that only contains the local optima of S I Induced topology on S 0 : two points are neighbors if their basin of attraction remains as such for S I In practice, we seek to find the neighbors of x 0 2 S 0 by nudging x 0 in a random fashion and by applying again the local search strategy over S to find the neighboring local optimum in S 36 / 42 Energy/fitness Landscape Fitnesslandscape: representation ofH r fitnessa s a of£ , witha function I Graphical representation of the fitness given the of topology specified ooo neighberh neighborhood-induced topology bytax, "tricky" 8 [Typically A NK fitness landscape a fitness landscape 1¥. fitness lousyfitness 3 0 1023 landscape! x (NK-Landscape, N = 10, K = 3, fi contruit aléatoirement) 37 / 42 Fitness smoothing Average fitness 1 X f¯ = f (x) (2) |S| x2S A fitness f can be smoothed with a coeﬃcient : f (x) = f¯ + (f (x) f¯) (3) Smoothed NK Fitness Landscape 6 smoothing=0.4 smoothing=0.8 fitness 2 0 255 x 38 / 42 Fitness landscape and exploration I Easy vs. challenging landscape: selection of coding strategy, selection of neighborhood I Hard, yet easy case: maximize f (x) = x1 · x2... xn for xi 2 {0, 1}. The landscape is flat such that nothing can really guide the search I Example of MaxOne with two diﬀerent coding strategies 39 / 42 Example: MaxOne I MaxOne with two distinct coding strategies: we interpret (x1...xn ) as an integer. Neighborhood comprises x 1 et x + 1. If U chooses a neighbor without ever decreasing the fitness, we end up being stuck. However with the hypercube, it works! "" '" ' " ' " '" " " '" " ' " " " ' " " " ' """ " " 4 " P "" ' " 'neighbor ↳n o betterthanm e 110 tt$% 111 g) 0 010 011 ¥£"" fitness DA D 100 101 1,3 ID O 000 001 0 3 x reorientation, initial 0 local T 7 withthehypercub point ma, Gbmo bf'.by.. b.i t. *ALWAYS one e o. SUCCEED. in. 40 / 42 Population methods S S x1 x1 x0 y1 x0 z1 y0 x2 z0 y2 z2 x2 41 / 42 Population methods I Many metaheuristics consider a population of tentative solutions. Then, they let this population evolve to explore the S: e.g., genetic/evolutionary algorithms I The optimal solution is then the best solution found across all generations/evolutions I We work in an extended search space: S N where N is the number of individuals within the population I The neighborhood of a population is another population: elementary transforms are more complex since they can use the entire population, and not just one single solution I It can be seen as some sort of co-evolution of many solutions 42 / 42

Chapter 1: Introduction PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue