Course on Heuristic Optimisation Procedures

-> Home page -> Teaching activities flag

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

Academic year 2019/2020

Topics for final exam

  • usage of prototype model in problem solving
  • numerical/combinatorial optimisation
    1. problem structure, optimization types
    2. problem types (decision, optimisation and combined 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
  • 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, acceptance criterion, long term memory)
    13. TS (tabu search) structure
    14. dynamic changes of evaluation function
    15. DLS (dynamic local search) structure
  • hybrid search algorithms
    1. hybrid strategies
    2. GRASP (greedy randomised adaptive search procedure) characteristics and structure
    3. GRASP - constructive phase (greedy-random, random-greedy, random+greedy)
    4. path-relinking (principle, usage in GRASP)
    5. AICS (adaptive iterated construction search) characteristics and structure
  • systematic search
    1. DPLL - basic characteristics
    2. DPLL structure
    3. DPLL pruning (unit propagation, pure literal)
    4. DPLL - selection heuristics
    5. DPLL - conflict analysis (learning, backtracking)
  • 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 algorithm
    4. BFO - step function
    5. BFO structure
    6. BFO - social behaviour
  • biologically inspired algorithms - bee colonies
    1. model of bee foraging, waggle dance
    2. mapping between bee colony and ABC 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. EA 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

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 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 18.12.2019