Course on Heuristic Optimisation Procedures

-> Home page -> Teaching activities flag

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

Additional material to the course

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 Estimation of Distribution algorithms (pdf)
go Computational complexity (P, NP, NP-hard, NP-complete, APX, PTAS, FPTAS) (pdf) [EXT: youtube-short, youtube-long]

Topics

  • Usage of prototype model in problem solving
  • numerical/combinatorial optimisation
    1. problem structure, problem kinds
    2. problem types (decision, optimisation and combined problem)
  • traditional combinatorial problems
    1. SAT problem (informal and formal description, characteristics)
    2. TSP problem (informal and formal description, characteristics)
    3. GC problem (informal and formal description, characteristics)
  • 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 and structure
    9. PII (probabilistic iterative improvement) characteristics and structure
    10. tabu search (short term memory, acceptance criterion, long term memory)
    11. TS (tabu search) structure
    12. dynamic changes of evaluation function
    13. DLS (dynamic local search) structure
  • simulated annealing (candidate acceptance, algorithm structure, annealing schedule)
  • hybrid search algorithms
    1. hybrid strategies
    2. ILS (iterated local search) characteristics and structure
    3. GRASP (greedy randomised adaptive search procedure) characteristics and structure
    4. GRASP - constructive phase (greedy-random, random-greedy, random+greedy)
    5. path-relinking (principle, usage in GRASP)
    6. 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 swarm algorithms - ant system
    1. ant characteristics (nature and artificial)
    2. positive feedback in shortest path search
    3. AS (ant system) as a search algorithm
    4. AS - artificial ant world
    5. AS - selection of move direction
    6. AS - pheromone maintenance
    7. AS structure
    8. AS for MAXSAT (world topology and dynamics)
  • biologically inspired swarm 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
  • estimation of distribution algoritms
    1. characteristics of EDA
    2. EDA structure
    3. probabilistic models
    4. UMDA characteristics
    5. UMDA structure
    6. MIMIC characteristics
    7. MIMIC structure
    8. BMDA 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

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 22.12.2017