• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedUser profile (HSE staff only)Search
Master 2018/2019

Real-world Logistics and Bio-inspired Evolutionary Algorithms

Type: Elective course (Data Science)
Area of studies: Applied Mathematics and Informatics
When: 1 year, 3, 4 module
Mode of studies: Full time
Instructors: Vasilii Gromov
Master’s programme: Data Science
Language: English
ECTS credits: 4

Course Syllabus

Abstract

Rapid growth of large-scale complex logistics systems (ranging from mobile ad hoc devices to supply chains) often result in inability of logistics practitioners to make reasonable decisions. In turn, this makes necessary to develop both decision-making and decision-making support systems for logistics. It is worth emphasizing that various sophisticated demands and constraints inherent in real-world systems render each such system unique. Nevertheless, gained experience in developing decision-making logistics systems suggests that they tend to share some common features, mostly related to the high-dimensional discrete optimization problems (with “the curse of dimensionality” peculiar to them); in actual practice, it usually means that a certain bio-inspired (evolutionary) algorithm is employed. The course concerns with single- and multi-objective discrete optimization problems associated with modern logistics systems, state-of-the-art bio-inspired approaches to solve these problems (simulated annealing, genetic algorithms, tabu search, artificial immune systems, ant colony optimization, bee colonies, particle swarm optimization, differential evolution, gravitational search, bacterial foraging algorithm, cuckoo search and firefly algorithm, evolutionary scheduling and others), anytime (interruptible) algorithms, methods used to estimate and minimize risk for such systems, collective intelligence, guided self-organization – to sum up, the course deals with mathematics required to solve real-world complex logistics systems and the systems themselves.
Learning Objectives

Learning Objectives

  • To introduce the theoretical foundations of Evolutionary algorithms and other algorithm necessary to solve high-dimensional discrete optimization problems.
  • To provide the students with practical skills of modelling real-world logistics system.
  • To overview the current applications of decision-making support systems in logistics.
  • To demonstrate a few standard approaches to solve multi-objective optimization.
Expected Learning Outcomes

Expected Learning Outcomes

  • Understand the basics of discrete optimization.
  • Understand fundamental concepts, advantages and limitations of methods to solve discrete optimization problems.
  • Understand the basics of simulated annealing.
  • Understand the basics of Anytime algorithms.
  • Understand fundamental concepts of Tabu search.
  • Understand fundamental concepts of Genetic algorithms.
  • Understand the basics of Artificial Immune systems.
  • Understand fundamental concepts of Ant colony optimization.
  • Understand fundamental concepts of Particle swarm optimization and related algorithm.
  • Understand basics of Evolutionary Scheduling.
  • Understand fundamental concepts of Evolutionary algorithms for mobile ad hoc networks.
  • Understand basics of methods to solve multi-objective optimization problems.
  • Understand fundamental concepts of Bio-inspired algorithms and multi-objective optimization.
  • Understand fundamental concepts of Collective intelligence and guided self-organization (GSO).
  • Understand fundamental concepts of decision-making support systems.
  • Design and develop decision-making support systems for logistics.
Course Contents

Course Contents

  • Discrete optimization
    Linear and non-linear optimization. Problems of combinatorial optimization. Traveling Salesman Problem. Knapsack problem. Set partition problem. Set covering problem. Scheduling. Bin packing. Vehicle routing problems. VRP with time windows. VRP with delivery pick-up.
  • Methods to solve discrete optimization problems
    No free lunch theorem. Brute-force search. Branch-and-bound. Variable depth search. Kernigan-Lin algorithm. Metaheuristics. Heuristics. Hill-climbing. Steepest ascend.
  • Simulated annealing
    Initial value of synthetic temperature. Deterministic annealing. Adaptive simulated annealing. Efficient candidate generations. Cooling schedule.
  • Anytime algorithms
    Main concepts of anytime (interruptible algorithms). Anytime Repairing A*. Exploration heuristics. Anytime local search. Anytime Potential Search. Anytime route planning with constrained devices.
  • Tabu search
    Use of memory. Adaptive memory programming. Short-term memory. Candidate List Strategies. Tabu search principles. Tabu search in integer programming.
  • Genetic algorithms
    The main concepts of GA. Binary and real-coded GA. Steady state GA. Scattering search. Exploration vs. Exploitation. Cultural algorithms. Niching and speciation. Co-evolution.
  • Artificial immune systems
    Multi-Objective Optimization and Artificial Immune Systems. An Immune Algorithm Based Robust Scheduling Methods. An Artificial Immune Dynamical System for Optimization.
  • Ant colony optimization
    Various ACO. Application of ACO to combinatorial problems. A Cooperative Learning Approach to Traveling Salesman Problem.
  • Particle swarm optimization and related algorithm
    Particle swarm optimization. Differential evolution. Gravitational Search Algorithm. Bacterial Foraging Algorithms. Cuckoo Search and Firefly Algorithm. Bee colonies.
  • Evolutionary Scheduling
    Memetic Algorithms in Planning, Scheduling, and Timetabling. Landscapes, Embedded Paths and Evolutionary Scheduling.
  • Evolutionary algorithms for mobile ad hoc networks
    Topology management. Broadcasting algorithms. Routing protocols. Clustering approaches. Mobile network simulation. Energy management. Realistic vehicular mobility.
  • Methods to solve multi-objective optimization problems
    Pareto set. A priori methods. A posteriori methods. The method of successive concessions. The method of expert evaluation. Normal boundary intersection. Morphological analysis.
  • Bio-inspired algorithms and multi-objective optimization
    Hierarchical and simultaneous multi-objective problem optimization. Non-dominated sorting GA. Strength pareto evolutionary algorithm. Indirect optimization on the basis of self-organization.
  • Collective intelligence and guided self-organization (GSO)
    Сollective computation. Basic concepts of GSO. Self-Organizing Traffic Lights. Decentralized Decision Making for Multiagent Systems. Collective intelligence. Crowdsourcing. Collective computation. Information aggregation.
  • Decision-making support systems
    Decision-making and decision-making support systems for logistics. Main concepts. Real-world systems.
Assessment Elements

Assessment Elements

  • non-blocking Intermediate task 1
  • non-blocking Intermediate task 2
  • non-blocking Exam
Interim Assessment

Interim Assessment

  • Interim assessment (4 module)
    0.4 * Exam + 0.3 * Intermediate task 1 + 0.3 * Intermediate task 2
Bibliography

Bibliography

Recommended Core Bibliography

  • Dorronsoro, B. et al. Evolutionary algorithms for mobile ad hoc networks. – John Wiley & Sons, 2014 . – 240 pp.
  • Pardalos, P. M., Du, D. Z., Graham, R. L. (ed.). Handbook of combinatorial optimization. – Springer, 2013. – 3409 pp.
  • Prokopenko, M. Advances in applied self-organizing systems. – Springer, 2013. – 426 pp.

Recommended Additional Bibliography

  • Eiben, A. E. et al. Introduction to evolutionary computing. – Springer, 2003. – 287 pp.