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

Topics

  • Usage of prototype model in problem solving
  • numerical/combinatorial optimisation
    1. problem structure, optimization types
    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
    1. candidate acceptance
    2. algorithm structure
    3. annealing schedule
  • 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
  • biologically inspired algorithms - ant system
    1. 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
  • estimation of distribution algoritms
    1. characteristics of EDA
    2. EDA structure
    3. probabilistic models
    4. UMDA characteristics
    5. UMDA structure
    6. PBIL characteristics
    7. PBIL structure
    8. MIMIC characteristics
    9. MIMIC structure
    10. BMDA characteristics
    11. 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, approximation complexity classes (APX, PTAS, FPTAS)
    9. randomised algorithms, MAXSAT randomised algorithm

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