The study of this subject is the solution of optimization problems. Finding the best solution to a problem is one of the most important elements of decision making. Optimal planning of processes, optimization of finding the shortest route in a transport company or allocation of resources are examples of optimization problems that appear so often in real life.



In the Operative Research subject, classic techniques for solving optimization problems are explained, such as Simplex, Branch & Bound or the Hungarian method. To apply these algorithms, the problems must have specific characteristics (usually they are simple problems). However, many of the problems presented in reality are very complex (NP-hard) and therefore it is impossible to use the algorithms we have mentioned. The algorithms that we will learn in the Heuristic Searches subject will, in a short time, try to obtain the best possible solutions. Of course, no guarantee of optimal results. They are known as heuristic algorithms, and they are based on intuition. During the subject, we will study combinatorial optimization problems, and learn how to formalize them, and design and implement algorithms to solve them. Not only that, we will learn how to choose the most effective among the proposed algorithms.



“Please note that this subject is taught only in Spanish/Basque”

- Acquiring the ability to formalize combinatorial optimization problems, represent their solutions appropriately, and define the search space.



- Knowing how to design and apply constructive algorithms, algorithms based on a single solution, and population algorithms.



- To acquire the ability to grasp multiple objectives or problems in dynamic contexts, and to have the ability to apply appropriate algorithms by analyzing the scientific bibliography.



- Knowing how to define and apply an experimental design to compare stochastic algorithms. Mastering techniques for visualizing results, and having the ability to apply statistical analysis methods to draw strong conclusions.

* Unit 1 - Introduction to heuristic searches.

1.1. Combinatorial optimization problems.

1.2. Coding and search space for solutions.

1.2. The complexity

1.3. A review of classical methods.

1.4. Constructive algorithms.



* Unit 2 - Local search heuristic algorithms.

2.1. Environmental function

2.2. Local search algorithms

2.3. Selection criteria.

2.4. Local maxima and minima and their estimation

2.5. Bases of attraction



* Unit 3 - Advanced local searches.

3.1. Multi-start methods (MLS, GRASP, ILS,...)

3.2. Environment function modification methods (VNS, VND...)

3.3. Methods for accepting bad solutions (SA, TS,...)



* Unit 4 - Algorithms based on populations

4.1. Introduction

4.2. Genetic algorithms

4.3. Estimation of Distribution Algorithms

4.4. Swarm Intelligence algorithms (ACO, PSO)



* Unit 5. Variations of optimization problems

5.1. Multi-objective optimization

5.2. Dynamic optimization

5.3. Optimization of problems with constraints



* Unit 6. Experimental design and algorithm comparison.

6.1. Experimental design.

6.2. Execution of algorithms.

6.3. Visualization of results.

6.4. Statistical analysis of the results (Uncertainty analysis)

In this lesson we will have four types of activities:



Lectures - Theoretical content will be presented and illustrated with simple examples. Student participation will be encouraged, with small exercise challenges focused on reflection.



Individual laboratory practice - Students will individually program heuristic algorithms for optimization problems in the Python language. The aim will be to illustrate the theoretical content.



Group project - In groups, they will have to develop a project. The teachers will ask them an optimization problem, and formalize the problem, and they will have to propose two algorithms to optimize it. Finally, they will have to develop an experimental design to compare the performance of the two. They will have to write all the work in a 4-page scientific article at the end of the semester.



Seminars - In these special sessions we will work on some concrete content that is additional to the workshop. Using a relaxed format, students will initially work on the content, followed by discussion.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • Los porcentajes y tipos de evaluaciones se especifícan en apartados posteriores (%): 100

Two types of assessment will be available: CONTINUOUS and FINAL.



During the CONTINUOUS evaluation you will have to complete six tasks: 2 tests (one practical and one theoretical), 2 project submissions and 2 laboratory submissions. By default, all students will go through this type of assessment. In this type of evaluation, the grade will be calculated through the evaluation of the following tasks:

- Project - 20% (divided into 2 phases, 10% each)

- Laboratory test - 20% (two tests, 10% each)

- 1. Theoretical test - 30%

- 2. Practical test - 30%



In order to be able to keep the CONTINUOUS evaluation, a minimum grade of 3.5 out of 10 must be obtained in each test. A minimum grade must also be passed in the laboratory assignments. Those who do not pass the minimum will automatically go to the FINAL evaluation.



In the assessment, the FINAL will be evaluated through a theoretical-practical exam and the delivery of the project:

- Project - 20%

- Theoretical-practical test - 80%



If the student did not pass, he would have another opportunity to do the theoretical-practical test in the non-regular call.



If desired, the student can proceed to the final assessment, always before the second exam.



Given the content of the course and its practical nature, it is recommended to carry out the assessment on a continuous basis.

In the non-ordinary exam, there will be only one theoretical-practical test worth 80% of the grade, which will cover the theoretical and practical concepts of the subject. The other 20% can be obtained with the delivery of the project.

Course notes that will be provided in eGela, as well as numerous scientific articles that the professor will recommend to the students. Finally, the practical exercises will be programmed in Python and using Jupyter Notebooks or Google Colab.

Basic bibliography

*C.R. Reeves (Ed.), Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scienti¿c Publications, 1993.

*C. Blum, A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. 35,

3 (Sep. 2003), 268-308

*H.H Hoos, T. Stuztle, Stochastic local search.Foundationsandapplications.MorganKaufmann,2005.

* B. Melián, J.A. Moreno Pérez, J. Marcos Moreno-Vega, J.(Ed.) Revista Iberoamericana de Inteligencia Arti¿cial 19, 2, 2003.

* A.E. Eiben, J.E. Smith, Introduction to Evolutionary Computing. Springer, 2007.

* C.A. Coello, G.B. Lamont, D.A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems. Springer,

2007

In-depth bibliography

* A. Díaz (Ed.), Optimización Heurística y Redes Neuronales en Dirección de Operaciones e Ingeniería.
Editorial Paraninfo, 1996.
*F. Glover, M. Laguna, Tabu Search. Kluwer Academic Publishers, 1997.
* M. Laguna and R. Martí, Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers, 2003.
* P. Larrañaga & Jose A. Lozano (Ed.) Estimation of Distribution Algorithms. Kluwer Academic Publishers, 2002.
* E. Aarts, J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization. John Wiley & Sons, 1997.

Journals

IEEE Trans. On Evolutionary Computation
Evolutionary Computation Journal
Journal of Heuristics
Soft Computing
Information Sciences

Web addresses

OR-Library http://people.brunel.ac.uk/~mastjjb/jeb/info.html . Repositorio de problemas de optimización.
Red Española de Metaheurísticos. http://heur.uv.es/
Dirección de LIO una librería de algorimtos heurísticos http://www.dsi.uclm.es/investigacion/simd/SOFTWARE/LIO/