Course on Heuristic Optimization Procedures

Course on Heuristic Optimisation Procedures

-> Home page -> Teaching activities

Basic information on the course can be found on Study Programmes pages

course annotation (look at Business Informatics - MS level)

Academic year 2021/2022

Class time and location - Winter term
- Lectures: Tuesday 15:10-16:40 online (MS teams platform)
- Practicals: Thursday 7:30-10:40 Room B520 / online (MS teams platform)
Staff
- Lectures:Marian Mach (faculty)
- Practicals: Jan Magyar (faculty)
Lecture main topics (for details see presentations in Basic course material section)
- Abstract problem solving using local search paradigm
- Iterative improvement based search
- Metaheuristic search (swarm algorithms)
- Estimation of distribution algorithms
Practicals topics
- see page
Requirements for successful course completion
- Compulsory practical attendance (max 3 absences)
- Lecture attendance is optional but highly recommended (additional credit)
- To be awarded with overall credit > 50% (credit for practicals > 20%, final exam credit > 30%)
Grading
- Practicals: 40% (two writen exams, two projects)
- Final exam: 60%

Topics for final exam

prototype model

usage of prototype model in problem solving

numerical/combinatorial optimisation
1. problem structure
2. optimization types
3. problem types (decision, optimisation and combined problem)
traditional combinatorial problems
1. SAT problem
2. TSP problem
3. GC problem
searching for solutions
1. search as a solving paradigm
2. perturbative and constructive search
3. systematic and local search
4. combination of search types
5. search type selection
local search
1. characteristics of local search
2. neighbourhood (role, definition) and neighbourhood graph
3. basic components of local search (init, step, term)
4. structure of local search (decision and optimisation problem)
5. search trajectory
iterative improvement
1. informed vs. uninformed search strategy
2. evaluation function
3. iterative improvement (basic components)
4. structure of iterative improvement
5. local optimum curse
escape from local optima
1. random restarts (characteristics, structure)
2. larger neighbourhood (pruning, pivot rules)
3. neighbourhood switching
4. VND (variable neighbourhood descent) structure
5. step beyond neighbourhood (step construction in LK)
6. VDS (variable depth search) structure
7. acceptance of inferior candidates
8. RII (randomised iterative improvement) characteristics
9. RII structure
10. PII (probabilistic iterative improvement) characteristics
11. PII structure
12. tabu search (short term memory design)
13. enhancements of tabu search (acceptance criterion, long term memory)
14. TS (tabu search) structure
15. dynamic changes of evaluation function
16. DLS (dynamic local search) structure
simulated annealing
1. algorithm main components
biologically inspired algorithms - ant system
1. real ant characteristics, shortest path search
2. AS (ant system) as a search algorithm
3. AS - artificial ant world
4. AS - selection of move direction
5. AS - pheromone maintenance
6. AS structure
7. AS for MAXSAT (world topology and dynamics)
biologically inspired algorithms - bacterial foraging
1. movement vs food search (general animal, bacteria)
2. movement of E.coli (basic movement, external influence, social influence)
3. mapping between E.coli movement and BFO (bacterial foraging optimisation) algorithm
4. BFO - step function
5. BFO structure
6. BFO - reproduction and dispersion
7. BFO - social behaviour
biologically inspired algorithms - bee colonies
1. model of bee foraging, waggle dance
2. mapping between bee colony and ABC (artificial bee colony) algorithm
3. ABC - simplified model of bee colony
4. ABC - principles
5. ABC structure
6. ABC - source exploitation
7. ABC - as a search algorithm
probability foundations
1. probability distributions (joint, marginal, conditional)
2. variable (in)dependence
3. joint distribution factoring
estimation of distribution algoritms
1. characteristics of EDA (population sample vs model)
2. EDA structure
3. probabilistic models
4. BMDA (bivariate marginal distribution algorithm) characteristics
5. BMDA structure
computational complexity
1. theory of computational complexity
2. complexity of algorithms and problems
3. P and NP complexity classes
4. NP-hard and NP-complete complexity classes
5. complexity of combinatorial problems
6. solving NP problems
7. stochastic versus deterministic search
8. associated approximation problem
9. approximation complexity classes (APX, PTAS, FPTAS)
selected algorithms
1. constructive heuristics for TSP
2. GSAT family (GSAT, GWSAT, HSAT, HWSAT, ...)
3. GC heuristics (sequential, parallel)

Basic course material

Lecture presentations (in Slovak)

	Basic terms (solution, candidate, candidate space, problem types) (pdf)
	Prototype combinatorial problems (satisfiability, travelling salesman, graph coloring) (pdf)
	Search paradigms (perturbative, constructive, systematic and local search) (pdf)
	Davis-Putnam procedure (pdf)
	Local search (neighbourhood, algorithm structure, search trajectory) (pdf)
	Iterative improvement (pdf)
	Escape from local optimum (restarts, VND, VDS, RII, PII, TS, DLS) (pdf)
	Hybrid local search (ILS, GRASP, AICS) (pdf)
	Ant system algorithm (pdf)
	Bacterial foraging optimization algorithm (pdf)
	Artificial bee colony algorithm (pdf)
	Evolutionary algorithm (pdf)
	Probability short overview (pdf)
	Estimation of Distribution algorithms (pdf)
	Computational complexity (P, NP, NP-hard, NP-complete, APX, PTAS, FPTAS) (pdf) [EXT: youtube-short, youtube-long]