Introduction to Metaheuristics (CSC06A) 

Quarter

3

Most (if not all) engineering problems can be formulated as optimization problems. To solve optimization problems, different methods have been studied in mathematical programming, operations research, and so on. Conventional methods, however, are usually not efficient enough when the problem space is large and complex. Many problems faced in artificial intelligence are combinatorial optimization problems. These problems are NPhard, and we may never find polynomial time solution. To solve these problems efficiently, different "heuristics" have been used to "search for the suboptimal solution".
Heuristics are search methods produced based on human's intuitive and creative thinking, and are often useful in local search to find good solutions quickly in a restricted area. Metaheuristics are higher level heuristics that control the whole process of search, so that global optimal solutions can be obtained systematically and efficiently. Although metaheuristics cannot always guarantee to obtain the true global optimal solution, they can provide very good results many practical problems. Usually, metaheuristics can enhance the computing power of a computer system greatly without increasing the hardware cost.
So far many metaheuristics have been proposed in the literature. In this course, we classify the metaheuristics into two categories. The first one is "singlepointsinglepath" (SPSP) search, and the second one is "multipointsmultipaths" (MPMP) search. For the former, we introduce tabusearch, simulated annealing, iterated local search, and so on. For the latter, we introduce evolutionary algorithms (including genetic algorithms, genetic programming, evolutionary strategy, memetic algorithm and so on), ant colony optimization, and so on. Although the efficiency and efficacy of these methods have been proved through experiments, because they were proposed based on human intuition, the theoretic foundation is still weak. Therefore, in this course, we will mainly introduce the basic idea of each method, and try to explain the physical meaning clearly. Mathematic proofs will be introduced very briefly when necessary.
After this course, we should be able to
Class Schedule 

Number  Date and Time  Contents  Lecture notes 
1  10/2, 12  Classification of optimization problems and case studies  [Lecture1] 
2  10/2, 34  A brief review of conventional search algorithms  [Lecture2] 
3  10/9, 12  Tabu search  [Lecture3] 
4  10/9, 34  Simulated annealing  [Lecture4] 
5  10/16, 12  Iterated local search and guided local search  [Lecture5] 
6  10/16, 34  Team work I: solving problems using singlepoint search algorithms  [Team work  I] 
7  11/6, 12  Team work I: Presentation of teamwork results   
8  11/6, 34  Genetic algorithm  [Lecture6] 
9  11/13, 12  Other Evolutionary Algorithms  [Lecture7] 
10  11/13, 34  Differential evolution  [Lecture8] 
11  11/20, 12  Swarm Intelligence  [Lecture9] 
12  11/20, 34  Memetic algorithms 
[Lecture10] [Lecture11] 
13  11/28, 12  Team work II: solving problems using multipoint search algorithms  [Team work  II] 
14  11/28, 12  Team work II: Presentation of teamwork results   