#### Transcript Document

Introduction Spring, 2014 Metaheuristics Byung-Hyun Ha Outline Introduction Optimization problems Optimization methods Hard problems Python programming 1 Introduction Computational intelligence (CI) A set of nature-inspired computational methodologies and approaches to address complex real-world problems to which traditional approaches are ineffective or infeasible (Wikipedia) Major topics in CI Artificial neural networks Fuzzy logic Evolutionary computation • e.g., genetic algorithm including biologically inspired algorithms, such as swarm intelligence and artificial immune systems This class focuses on “evolutionary computation” For resolving various optimization-related problems in IE Additionally dealing with metaheuristics that are non-evolutionary • e.g., simulated annealing and tabu search Evolutionary computation is a branch of metaheuristics study. 2 Introduction Artificial neural networks Computational models inspired by animals’ central nervous systems • Roughly, (input) [computational models] (output) • Issues: network structures, training methods, etc. applications • Function approximation (regression analysis) • e.g., time series prediction • Classification • e.g., pattern and sequence recognition • Data processing • e.g. filtering, clustering • Robotics • e.g., directing manipulators • Control • e.g., numerical control input model output 3 Introduction Fuzzy logic A form of many-valued logic, dealing with reasoning that is approximate rather than fixed and exact • Classical logic: true and false • e.g., if T < 10 and T' < 0, then P = 100. • Approximate reasoning • e.g., if (process is too cool) and (process is getting colder) then (add heat to the process) Applications • Fuzzy control system • e.g., railway system control • Intelligent agents • e.g., generating crowds in 3D animation • Data analysis 4 Introduction Evolutionary computation A field involves continuous optimization and combinatorial optimization problems Techniques (mostly involve metaheuristic optimization algorithms) • • • • • • • • • • • • • Evolutionary algorithms, programming, strategy Genetic algorithm, programming Differential evolution Swarm intelligence Ant colony optimization Particle swarm optimization Bees algorithm Artificial life Artificial immune systems Harmony search Learning classifier systems Self-organization such as self-organizing maps, competitive learning ... 5 Introduction Metaheuristics A major subfield of stochastic optimization Assuming little or no information about problems being solved Stochastic optimization Employing some degree of randomness to find optimal (or as optimal as possible) solutions to hard (optimization) problems Optimization problems Selection of a best element (the optimal solution) from some set of available alternatives (feasible solutions) • e.g., Location of facilities, network optimization, layout planning, routing and scheduling, optimal control, ... And... Little or no information? Some degree of randomness? Hard problems? 6 Introduction Computational intelligence and metaheuristics A point of view Computational intelligence Metaheuristics Artificial neural networks Evolutionary computation Other approaches Fuzzy logic 7 Optimization Problems Described by (usually..) objective, input, constraints, output (decision variables or solution) Examples Well-posed problems • (0-1) knapsack (optimization) problems (combinatorial optimization) • Input: Finite set U, for each u U a size s(u) Z+ and a value v(u) Z+, and positive integer B • Question: Determine a subset U' U such that uU' s(u) B and so that uU' v(u) is maximized • Schwefel (nonlinear programming) Ill-posed problems • Find the best logistics network • Optimization by logistics simulation • Robot soccer 8 Optimization Problems Problem description (e.g., knapsack problems) Informally (using natural language) • Given a set of items, each with size and value, determine items to be included in a knapsack so that the total volume is less than or equal to a given limit and the total value is as large as possible. 5 3 2 7 ? 1 Formally (e.g., using mathematical notation) • Input: Finite set U, for each u U a size s(u) Z+ and a value v(u) Z+, and positive integer B • Question: Determine a subset U' U such that uU' s(u) B and so that uU' v(u) is maximized Formally (e.g., using mathematical programming) • • • • vi: value of item i, si: size of item i xi = 1, if item i is included; 0, otherwise max. i vixi s.t. i sixi B xi {0, 1} 9 Optimization Problems Feasible solutions Solutions that satisfy constraints The optimal solution A feasible solution that gives the best (minimum or maximum) objective function value Solution space Collection of all feasible (and infeasible) solutions • Some of solutions in solution space are optimal solutions e.g., n candidate items for knapsack problem: size 2n • 100 items: 1,267,650,600,228,229,401,496,703,205,376 possible solutions! Knapsack problems vi: value of item i, si: size of item i xi = 1, if item i is included; 0, otherwise max. i vixi s.t. i sixi B xi {0, 1} 10 Optimization Methods Solving problems and obtaining (optimal) solution All-enumeration? • Knapsack problem? • 100 items: 1,267,650,600,228,229,401,496,703,205,376 possibilities • Schwefel? • Robot soccer? 11 Optimization Methods for Well-posed Problems Exact methods e.g., find a largest element in a sequence. e.g., F-problem of single-machine scheduling • Problem description • Given n jobs with processing time given, find the optimal schedule that minimize the total flowtime (completion time). • Example instance • 3 jobs of {1, 2, 3}, with processing time p1 = 5, p2 = 2, p3 = 3 • Q: Number of possible schedules? • A: Infinite, why? 1 2 2 1 1 1 2 3 2 3 1 3 2 1 2 1 1 3 2 3 3 3 3 1 1 ... 1 2 3 2 1 3 ... ... 12 Optimization Methods for Well-posed Problems Exact methods (cont’d) e.g., F-problem of single-machine scheduling (cont’d) • Properties (theorems) • Schedule without inserted idle time constitute a dominant set. • Schedules without preemption constitute a dominant set A schedules can be completely specified by a permutation of jobs 1 2 2 1 1 1 2 3 (O) 2 3 (X) 1 (X) 2 3 1 2 1 1 3 (O) 2 3 (X) 3 3 (X) 3 1 1 1 2 3 2 1 3 (O) ... (X) ... (X) ... 13 Optimization Methods for Well-posed Problems Exact methods (cont’d) e.g., F-problem of single-machine scheduling (cont’d) • Q: How many schedules do we need to consider, then? • A: 3! = 6, why? 1 2 2 3 3 1 1 3 3 1 2 2 2 3 1 2 3 1 • Hence, a schedules can be completely specified by a permutation of integers • (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) • Size of solution space with n jobs • n! • How many possible schedules if we have 30 jobs? • 30! = 265,252,859,812,191,058,636,308,480,000,000 14 Optimization Methods for Well-posed Problems Exact methods (cont’d) e.g., F-problem of single-machine scheduling (cont’d) • Theorem • Total flowtime is minimized by shortest processing time (SPT) sequencing • Proof sketch (using proof by contradiction) • Suppose there is a sequence S that is optimal but not SPT sequence. • In S, there exists a pair of adjacent jobs, i and j, with j following i, such that pi pj . • Construct sequence S' in which job i and j are interchanged. • Fi + Fj Fj' + Fi' implies that F F', which is a contradiction. • Therefore, for all S, if S is optimal, then S is SPT sequence. • To get optimal solution, • Sort jobs by processing-time-decreasing order! 15 Optimization Methods for Well-posed Problems Exact methods (cont’d) e.g., knapsack problems? e.g., T-problem of single-machine scheduling • Problem description • Given n jobs with processing time and due date given, find the optimal schedule that minimize the total tardiness. • Example instance tardiness Job j 1 2 3 pj dj 3 8 8 6 3 10 due date completion time • Property? • Total tardiness is minimized by earliest due date (EDD) sequencing? • NO!!! (why? prove it.) 16 Hard Problems How about it? If it takes long time to solve a problem, it is a hard problem.. ;-) Solve a problem? Using an algorithm with input of size n Algorithms A finite list of well-defined instructions for solving a problem e.g., selection sort of sequence of n items (x1, x2, ..., xn) • for each i = 2, ..., n do: • ji • t xj • while j > 1 and t < xj –1: xj xj –1 jj–1 • xj t • Is it a hard problem? • How much time it takes to sort? 17 Hard Problems Measuring the time complexity of algorithms Definition: big-O notation (upper bound) • An algorithm has a complexity f(n) = O(g(n)) if there exist positive constant n0 and c such that n > n0, f(n) cg(n). Definition: big- notation (lower bound) • An algorithm has a complexity f(n) = (g(n)) if there exist positive constant n0 and c such that n > n0, f(n) cg(n). e.g., time complexity of selection sort for n items? Important classes Polynomial-time algorithm • Time complexity is O(p(n)), where p(n) is a polynomial function of n. Exponential-time algorithm • Time complexity is (cn), where c is a real constant strictly greater than 1. Complexity of a problem Equivalent to the complexity of the best algorithm solving the problem 18 Hard Problems Example of time complexity Size of largest problem instance solvable in 1 hour (Garey and Johnson, 1969) Time complexity With present computer With computer 100 times faster With computer 1000 times faster n N1 100 N1 1000 N1 n2 N2 10 N2 31.6 N2 n3 N3 4.64 N3 10 N3 n5 N4 2.5 N4 3.98 N4 2n N5 N5 + 6.64 N5 + 9.97 3n N6 N6 + 4.19 N6 + 6.29 19 Hard Problems Example of time complexity (cont’d) Comparing algorithms with complexity of n, nlogn, n2, n8, 2n, 3n • Assuming that our computer executes 106 computations per second comp. time 0.009 0.008 0.007 0.006 0.005 0.004 0.003 0.002 0.001 0 prob. size 9E+05 8E+05 7E+05 6E+05 5E+05 4E+05 3E+05 2E+05 1E+05 0E+00 0 20 40 60 80 100 9E+17 8E+17 7E+17 6E+17 5E+17 4E+17 3E+17 2E+17 1E+17 0 0 20 40 60 80 100 0 20 40 60 80 100 80 100 • Assuming that our computer has become 103 times faster than above 0.009 0.008 0.007 0.006 0.005 0.004 0.003 0.002 0.001 0 9E+05 8E+05 7E+05 6E+05 5E+05 4E+05 3E+05 2E+05 1E+05 0E+00 0 20 40 60 80 100 9E+17 8E+17 7E+17 6E+17 5E+17 4E+17 3E+17 2E+17 1E+17 0 0 20 40 60 80 100 0 20 40 60 20 Hard Problems Then, how about it (more formally)? A problem is hard, if we are sure that there is not any polynomial-time algorithm to solve the problem (to get the optimal solution)..? The above statement implies.. hard problems clear boundary easy problems But until now (sadly..), the clear boundary has not been proved yet i.e., neither one could present a polynomial-time algorithm, nor one could prove there does not exist any polynomial-time algorithm, for some problems, e.g., knapsack problems, T-problems, traveling salesman problems It’s about NP-completeness (will be discussed next class) 21 Optimization Methods (revisited) Exact methods Dynamic programming Branch and bound A*-search ... Example of dynamic programming Longest-path modeling Recursion formula for knapsack problems Knapsack problems vi: value of item i, si: size of item i xi = 1, if item i is included; 0, otherwise max. i vixi s.t. i sixi B xi {0, 1} • g(k, b) = g(k – 1, b), if sk > b g(k, b) = max{g(k – 1, b), g(k – 1, b – sk) + vk}, otherwise • g(k, 0) = 0 k, g(0, b) = 0 b Q: solve the following knapsack problem with B = 5. Item j 1 2 3 4 vj sj 3 2 4 3 5 4 6 5 Exploiting information of problems HEAVILY! 22 Optimization Methods Approximation methods Approximation algorithms Heuristic algorithms • Problem-specific heuristics • e.g., EDD rule for T-problem Metaheuristics • • • • • Simulated annealing Tabu search Genetic algorithms Ant colony optimization ... Using randomness to solve problems e.g., randomly choose next job among 2 earliest-due-date jobs for Tproblem Job j 1 2 3 Optimality? pj dj 3 8 8 6 3 10 23 Python Programming Why programming? No computer programming, no logical thinking (in my opinion)! Python A general-purpose, high-level programming language whose design philosophy emphasizes code readability Supporting multiple programming paradigms • Object-oriented, imperative, functional programming, ... Dynamic type system and automatic memory management Anyway.. powerful and beautiful (in my opinion) Why python? For computer programming experts • It’s easy, so it gives no burden at all. (still powerful and can learn a lot!) For beginners • It’s easy, so it’s best for the first programming language. 24 Python Programming Describing algorithms using Python Algorithm 1 -- Active Schedule Generation 1. Let k = 0 and begin with PS(k) as the null partial schedule. Initially, SO(k) includes all operations with no predecessors. 2. Determine f* = minjSO(k) {fj} and the machine m* on which f* could be realized. 3. For each operation j SO(k) that requires machine m* and for which sj f*, create a new partial schedule in which operation j is added to PS(k) and started at time sj . 4. For each new partial schedule PS(k + 1) created in Step 3, update the data set as follows: (a) Remove operation j from SO(k). (b) Form SO(k + 1) by adding the direct successor of j to SO(k). (c) Increment k by one. 5. Return to Step 2 for each PS(k + 1) created in Step 3, and continue in this manner until all active schedules have been generated. sj -- the earliest time at which operation j SO(k) could be started fj -- the earliest time at which operation j SO(k) could be finished 25 Python Programming Describing algorithms using Python (cont’d) def active_schedule_generation(X): # active list (bs, vs, ps, s), set(X), current best A, SX, z_best = [(0, 0, sum(j.p for j in X), [])], set(X), None i, s_max = 0, 0 # iter #, max sequence size # loop while True: bs, vs, ps, s = heappop(A) # subproblem s_max = max(s_max, len(s)) s_ = SX.difference(set(s)) # set(s') if len(s) == len(X): break # optimality check djobs = [(j.d, j) for j in s_ if j.d >= ps] if djobs: # step 3 j = max(djobs)[1] pjs, vjs, js = ps - j.p, vs, [j] + s s_.remove(j) if s_: bjs = vjs + min(max(0, pjs - x.d) for x in s_) else: bjs, z_best = vjs, vjs heappush(A, (bjs, vjs, pjs, js)) else: # step 4 for j in s_: pjs, vjs, js = ps - j.p, vs + ps - j.d, [j] + s s_.remove(j) if s_: bjs = vjs + min(max(0, pjs - x.d) for x in s_) else: bjs, z_best = vjs, vjs s_.add(j) heappush(A, (bjs, vjs, pjs, js)) 26 Summary Computational intelligence Artificial neural networks Fuzzy logic Evolutionary computation (Mathematical) optimization (problems) Selection of a best element (the optimal solution) from some set of available alternatives (feasible solutions) Stochastic optimization Employing some degree of randomness to find optimal (or as optimal as possible) solutions to hard (optimization) problems Metaheuristics A major subfield of stochastic optimization Assuming little or no information about problems being solved Python programming 27