Hyper-heuristic Research in ASAP Group Course Introduction
Hyper-heuristics –Course Introduction 1
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
Hyper-heuristic Research in ASAP Group Course Introduction
Dr Rong Qu & Dr Gabriela Ochoa
ASAP Group The University of Nottingham
rxq@https://www.wendangku.net/doc/6515972393.html,, gxo@https://www.wendangku.net/doc/6515972393.html,
https://www.wendangku.net/doc/6515972393.html,/~rxq
https://www.wendangku.net/doc/6515972393.html,/~gxo Hyper-heuristics –Course Introduction 2
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
ASAP Group, The University of Nottingham
Hyper-heuristics –Course Introduction 3
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
?Part I (Day 1): Introduction ?Part II (Days 2 & 3): Hyper-heuristic Research
–Constructive and improvement hyper-heuristics
–Different themes in hyper-heuristics
?Part III (Day 4)
–Summary
Course Schedule Hyper-heuristics –Course Introduction 4
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
?Day
1(31st July 2007)
–Lecture 1: Outline of the course & Introduction to meta-heuristics
–Lecture 2: Meta-heuristics
–Lecture 3: Overview of application domains
–Lecture 4: Introduction to hyper-heuristics
Course Schedule
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
Course Schedule
?Day2(1st August 2007)
–Lecture 1: Constructive Hyper-Heuristics 1
–Lecture 2: Constructive Hyper-Heuristics 2
–Lecture 3: Improvement Hyper-Heuristics 1
–Lecture 4: Improvement Hyper-Heuristics 2
Hyper-heuristics –Course Introduction5
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
Course Schedule
?Day3(2nd August 2007)
–Lecture 1: Constructive Hyper-Heuristics 3
–Lecture 2: Improvement Hyper-Heuristics 3
–Lecture 3: Multi-Objective Hyper-Heuristics
–Lecture 4: Genetic Programming as a Hyper-Heuristics
Hyper-heuristics –Course Introduction6
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
Course Schedule
?Day4(3rd August 2007)
–Lecture 1: Search Space Analysis of Hyper-heuristics
–Lecture 2: Summary, and Research Directions
Hyper-heuristics –Course Introduction7 Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
A Brief Introduction to Search
Hyper-heuristics –Course Introduction8
Hyper-heuristics –Course Introduction 9
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
?The concept of search plays an important role in science and engineering ?Often we can't simply write down and solve the equations for a problem ?In one way, any problem whatsoever can be seen as a search for “the right answer”
Search Space
A B C
D
E Hyper-heuristics –Course Introduction 10
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
?Search space (state space)
?Goal
state
?Moving operator
?Neighborhoods
Search Space
A B C
D
E
Hyper-heuristics –Course Introduction 11
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
?Solving the TSP means finding the minimum cost solution
–Given a set of cities and distances between them
–Then find the optimal tour, that is, the shortest possible such tour
–n! n=50 1.52 * 1064
?Combinatorial explosion!Search Space
A
B C
D
E Hyper-heuristics –Course Introduction 12
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
?Heuristics
–Rule of thumb
–Methods towards finding optimal solutions
–Piece of advice that is usually based on prior experience
–A technique which improves the efficiency of a search process, possibly by sacrificing claims of completeness
Heuristics and Meta-heuristics
Hyper-heuristics –Course Introduction 13
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
?Meta-heuristics
–Heuristics with mechanisms (parameters) for solving computational problems
–Genetic Algorithms, Tabu Search, Simulated Annealing, Ant Colony, etc
Heuristics and Meta-heuristics Hyper-heuristics –Course Introduction 14
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
Heuristics and Meta-heuristics
meta-heuristic
potential Solutions
Operates upon
Summer School Course, Istanbul Technical University, 31st Jul –3rd Aug 2007
References
?UK Research Council Funding “Next Generation Decision Support: Automating the Heuristic Design Process”(EP/D061571/1) ￡2M ?[BUR03] E.K.Burke, G. Kendall, J.Newall, E.Hart, P.Ross &
S.Schulenburg, “Hyper-Heuristics: An Emerging Direction in Modern
Search Technology”, Handbook of Metaheuristics(eds. F.Glover &
G.Kochenberger), pp 457 –474, Kluwer, 2003
?[ROS05] P.Ross, “Hyper-heuristics”, Search Methodologies: Introductory Tutorials in Optimization and Decision Support
Techniques(eds. E.K.Burke & G.Kendall), pp 529-556, Springer 2005
Hyper-heuristics –Course Introduction15