Metaheuristics for Multi-Objective Optimization and Hybrid Approaches

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 Some methods in detail and some only introduction 2) P metaheuristics Some methods in detail and some only introduction 3) Metaheuristics for multi-objective Optimization only intro 4) Hybrid- only intro 5) Parallel -only intro Applications 1) Standard OR problems: TSP, knapsack, Setcovering 2) Scheduling and Manufacturing Job-shop Flowshop Flexible flowshop Lot-sizing PERT CPM Reservation and timetabling Workforce scheduling Several Special heuristics 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 Some methods in detail and some only introduction 2) P metaheuristics Some methods in detail and some only introduction 3) Metaheuristics for multi-objective Optimization only intro 4) Hybrid- only intro 5) Parallel -only intro Applications 1) Standard OR problems: TSP, knapsack, Setcovering 2) Scheduling in Manufacturing Job-shop Flowshop Flexible flowshop Lot-sizing PERT CPM 3) Scheduling in Service Reservation and timetabling Workforce scheduling Several Special heuristics 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 8