Introduction to Meta-heuristics (CSC06A)
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 NP-hard, and we may never find polynomial time solution. To solve these problems efficiently, different "heuristics" have been used to "search for the sub-optimal 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 "single-point-single-path" (SPSP) search, and the second one is "multi-points-multi-paths" (MPMP) search. For the former, we introduce tabu-search, 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
All lectures will be given online in this quarter.
Please attend the classes using a zoom account with the u-aizu.ac.jp domain.
See Moodle for more detail.
|Number||Date and Time||Contents||Lecture notes|
|Lecture 1||10/7, 1-2||Classification of optimization problems and case studies||[Lecture-1]|
|Lecture 2||10/7, 3-4||A brief review of conventional search algorithms||[Lecture-2]|
|Lecture 3||10/14, 1-2||Tabu search||[Lecture-3]|
|Lecture 4||10/14, 3-4||Simulated annealing||[Lecture-4]|
|Lecture 5||10/21, 1-2||Iterated local search and guided local search||[Lecture-5]|
|Project I||10/21, 3-4||Team work I: solving problems using single-point search algorithms||[Team work - I]|
|Lecture 6||10/28, 1-2||Genetic algorithm||[Lecture-6]|
|Lecture 7||10/28, 3-4||Other Evolutionary Algorithms||[Lecture-7]|
|Project I||11/11, 1-2||Team work I: Presentation of team-work results||---|
|Lecture 8||11/11, 3-4||Differential evolution||[Lecture-8]|
|Lecture 9||11/18, 1-2||Swarm Intelligence||[Lecture-9]|
|Lecture 10||11/18, 3-4||Memetic algorithms||
|Project II||11/25, 1-2||Team work II: solving problems using multi-point search algorithms||[Team work - II]|
|Project II||12/2, 1-2||Team work II: Presentation of team-work results||---|