Course on Heuristic Optimisation Procedures

-> Home page -> Teaching activities flag

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

Academic year 2020/2021

Topics for final exam

  • prototype model
    1. 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
  • systematic search
    1. DPLL - basic characteristics
    2. DPLL structure
    3. DPLL pruning (unit propagation, pure literal)
    4. DPLL - selection heuristics
    5. DPLL - conflict analysis (clause learning, backtracking)
  • 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
  • hybrid search algorithms
    1. hybrid strategies
    2. ILS (iterated local search) characteristics and structure
    3. GRASP (greedy randomised adaptive search procedure) characteristics (greedy vs random principle)
    4. GRASP structure
    5. GRASP - constructive phase (greedy-random, random-greedy, random+greedy)
    6. path-relinking (principle, usage in GRASP)
    7. AICS (adaptive iterated construction search) characteristics and structure
  • 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
  • biologically inspired algorithms - evolutionary algorithms
    1. natural selection and its model
    2. genetic transfer and its model
    3. mapping between evolution process and EA (evolutionary algorithm)
    4. EA structure
  • 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. UMDA (univariate marginal distribution algorithm) characteristics
    5. UMDA structure
    6. MIMIC (mutual information maximizing input clustering) characteristics
    7. MIMIC structure
    8. BMDA (bivariate marginal distribution algorithm) characteristics
    9. 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)
    10. randomised algorithms, MAXSAT randomised algorithm
  • 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)

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

Additional reading

how to solve it How to Solve It: Modern Heuristics
clever algorithms Clever Algorithms: Nature-Inspired Programming Recipes
stochastic local search Stochastic Local Search: Foundations and Applications

Copyright MM
Last updated 13.12.2020