Report

Multi-Objective Optimization • NP-Hard • Conflicting objectives – Flow shop with both minimum makespan and tardiness objective – TSP problem with minimum distance, time and cost objective – Container management – balancing volume, weight and value • Has no single solution but a set of solutions called Pareto Optimal Solutions – A solution is Pareto optimal if it not possible to improve a single objective without deteriorating another objective • The objective is to find the Pareto optimal set and the Pareto front • Metaheuristics can be used to approximate the Pareto optimal set – Both S and P – metaheuristics are used 1 Metaheuristics for Multiobjective Optimization • Fitness assignment – assign a scalar value to the quality of the solution • Diversity preserving – generate a diverse set of solutions • Elitism – Select the best set of solutions at every step General strategies • Aggregation – use an aggregation method to covert the problem into mono-objective • Weighted Metric – preselect a reference value of the objective function and measure the distance of the other solutions from this reference and minimize this distance • Parallel approach- treat each objective individually. Then crossover and mutate the solutions from each objective to find a compromise • Sequential approach- search in a preference order of objectives • Dominance based- search using a dominant criteria set by the final user 2 Hybrid Metaheuristics • • • • Combining S and P or a S and S metaheuristics Combining with other math programming methods Metaheuristics and AI Main classification – Relay - sequential – Teamwork – cooperative search – Example – Branch and bound – the upper bound of a node can be obtained using metaheuristic which also yields a partial solution upto the given node – Dynamic programming- if the state-action space is large, metaheuristics can reduce the action space by performing a local search among a set of all possible actions for a state 3 Parallel Metaheuristics • • • • Speed up search Improve quality Solve large NP hard problems Parallel designs – Algorithmic level – Independent or cooperative self-contained metaheuristics approaches are used in parallel – Iterative level – At an iteration search is done in several neighborhoods by different computers to speed up search – Solution level- the generation of the objective function value and the check for any constraint violations is done in parallel for a set of solutions generated by one search 4 Single-Metaheuristics • Accept nonimproving neighbors – Tabu search and simulated annealing • Iterating with different initial solutions – Multistart local search, greedy randomized adaptive search procedure (GRASP), iterative local search • Changing the neighborhood – Variable neighborhood search • Changing the objective function or the input to the problem in a effort to solve the original problem more effectively. – Guided local search 5 Population-based metaheuristics • • • • Nature-inspired Initialize a population A new population of solutions is generated Integrate the new population into the current one using one these methods – by replacement which is a selection process from the new and current solutions – – – – – Evolutionary Algorithms – genetic algorithm Estimation of distribution algorithm (EDA) Scatter search Evolutionary programming- genetic programming Swarm Intelligence • Ant colony • Particle swarm optimization (PSO) • Bee colony – Artificial Immune system AIS • Continue until a stopping criteria is reached • The generation and replacement process could be memoryless or some search memory is used 6 What was covered 1) S metaheuristics Applications • Some methods in detail and some 1) Standard OR problems: TSP, knapsack, only introduction Setcovering 2) P metaheuristics 2) Scheduling and Manufacturing • Some methods in detail and some Job-shop only introduction Flowshop 3) Metaheuristics for multi-objective Flexible flowshop Optimization –only intro Lot-sizing 4) Hybrid- only intro PERT CPM 5) Parallel -only intro Reservation and timetabling Several Special heuristics Workforce scheduling 1) Dispatch rules 2) Composite dispatch rules – ATC 3) Shifting bottleneck 4) Profile fitting 5) Flexible flow line loading FFLL 6) ELSP- frequency fixing and sequencing FFS 7) Maximizing number of jobs processed 8) Barriers algorithm for reservation 9) Graph coloring heuristic 10) FF and FFD First fit decreasing 11) Day-off scheduling and crew scheduling 12) Tournament scheduling 7 What was covered 1) S metaheuristics Applications • Some methods in detail and some 1) Standard OR problems: TSP, knapsack, only introduction Setcovering 2) P metaheuristics 2) Scheduling in Manufacturing • Some methods in detail and some Job-shop only introduction Flowshop 3) Metaheuristics for multi-objective Flexible flowshop Optimization –only intro Lot-sizing 4) Hybrid- only intro PERT CPM 5) Parallel -only intro 3) Scheduling in Service Several Special heuristics Reservation and timetabling 1) Dispatch rules Workforce scheduling 2) Composite dispatch rules – ATC 3) Shifting bottleneck 4) Profile fitting 5) Flexible flow line loading FFLL 6) ELSP- frequency fixing and sequencing FFS 7) Maximizing number of jobs processed 8) Barriers algorithm for reservation 9) Graph coloring heuristic 10) FF and FFD First fit decreasing 11) Day-off scheduling and crew scheduling 8 12) Tournament scheduling