Tutorial

Meta-heuristics for Combinatorial OptimizationJin-Kao HaoLERIA University of Angers2, Boulevard LavoisierF- 49045 Angers Cedex 01 phone: (+33) 2 41 73 50 76email: hao@info.univ-angers.frweb: www.info.univ-angers.fr/pub/haoJ.K. Hao, Université d'Angers, FrancePLAN1. Combinatorial optimization2. Review of resolution methods 3. Local search methods4. Evolutionary methods 5. Hybrid methods6. Application examples7. ConclusionsJ.K. Hao, Université d'Angers, France1£‡˛˛£fi˝Part OneReview of Resolution Methods for Combinatorial OptimizationJ.K. Hao, Université d'Angers, FranceCombinartorial OptimizationMinimizationGiven a couple (S,f) where • S a finite set of solutions or configurations (search space)• f: S R a cost function (or objective)find s* X S such that f(s*) f(s) for each element s X (feasible space) X • • Example: Traveling Salesman Problem TSP• • • • • • • S • • • • s* • • • • Remarks : • For maximization, one replaces "f(s*) f(s)" by "f(s*) f(s)"• In practical situations, neither S or f is necessarily given (modeling)• Most of important optimization problems are NP-hard. J.K. Hao, Université d'Angers, France2Resolution Methods (AI) (OR)construction recombination local search construction Evolut. Algo. repair B&BGreedy scatter search Desc tabu SA CSP A* MC GSATEP ES GA (<56) (<66) path relinking (90) (92)(<72) (86) (83) (74) (68) (75) (66) (73)(77)Four main approaches :1. Construction: ...