Metaheuristics

The subject deals with the solution of very complex search and optimisation problems for which a solution cannot be obtained exactly in a reasonable time. For this purpose, metaheuristics will be used, which are general-purpose algorithms that allow good solutions to be obtained with acceptable computational times for a wide variety of problems in this area.
Know how to design and implement metaheuristics based on populations, trajectories and social adaptation to solve problems with huge search spaces.
Know how to select the different types of metaheuristics for each problem to be solved.

Block 1: Introduction to metaheuristics fundamentals
Block 2: Trajectory-based metaheuristics
Block 3: Population-based metaheuristics
Block 4: Metaheuristics based on social adaptation
Block 5: Parallel metaheuristics and other strategies

Basic bibliography
- A.E. Eiben & J.E. Smith. Introduction to Evolutionary Computing. 2ndEdition, 2015
- Michel Gendreau and Jean-Yves Potvin (Eds.). Handbook of Metaheuristics, Springer 2010.
- J.T. Palma, R. Marín. Artificial Intelligence: techniques, methods and applications. McGraw-Hill, 2008. ISBN 9788448156183
- Francisco Herrera (Univ. Granada). Algorithmics. http://sci2s.ugr.es/graduateCourses/Algoritmica
- Metaheuristics: Population-based metaheuristics. http://sci2s.ugr.es/graduateCourses/Metaheuristicas
- E.-G. Talbi. Metaheuristics. From design to implementation. Wiley, 2009
- Marco Dorigo, Thomas Stützle. Ant Colony Optimization. The MIT Press. ISBN 9780262256032 DOI: https://doi.org/10.7551/mitpress/1290.001.0001


Complementary bibliography
- Janusz Kacprzyk, Witold Pedrycz, Springer Handbook of Computational Intelligence. Springer, 2015.
- Russell, S., Norvig, P. Artificial Intelligence (A Modern Approach), (4th Edition Global Edition, 2022). ISBN: 9781292401133.


In addition, specific scientific articles available through the university's digital library will be recommended for the various topics.

BASIC AND GENERAL
CG3 - Ability to design and create efficient AI-based quality models and solutions,
robust, transparent and accountable
GC4 - Ability to select and justify the appropriate methods and techniques to solve a specific problem, or to develop and propose new methods based on artificial intelligence.
GC5 - Ability to design new computational systems and/or evaluate the performance of existing systems, integrating artificial intelligence models and techniques.
CB2 - Students are able to apply their knowledge to their work or vocation in a professional manner and possess the competences usually demonstrated through the development and defence of arguments and problem solving within their field of study.
CB4 - Students are able to convey information, ideas, problems and solutions to both specialist and non-specialist audiences.
CB5 - That students have developed those learning skills necessary to undertake further study.
with a high degree of autonomy

CROSS-CUTTING
TR3 - Ability to create new models and solutions autonomously and creatively, adapting to new situations. Initiative and entrepreneurial spirit.

SPECIFIC
CE12 - Knowing the fundamentals of artificial intelligence algorithms and models for solving problems of a certain complexity, understanding their computational complexity and having the ability to design new models.

LEARNING OUTCOMES
- Know how to design and implement metaheuristics based on populations, trajectories and social adaptation to solve problems with huge search spaces.
- Know how to select the different types of metaheuristics for each problem to be solved.

The teaching methodology will be based essentially on individual work, although it will sometimes be carried out in groups, mainly in discussion with the teaching staff in expository and interactive classes.

For each topic or thematic block of the lectures, the lecturers will prepare the contents, explain the objectives of the topic to the students in class, suggest bibliographic resources and provide additional work material, mainly exercises related to the theoretical concepts. In the lectures, the more theoretical aspects of the design of metaheuristics and their adaptation to different problems will be worked on. In addition, the lecturers will propose a set of activities to be carried out individually or in groups (cases, exercises) that students will have to hand in for assessment, in accordance with the deadlines set. Overall, these activities will allow the development of the competences CG3, CG4, CG5, CB2, CB4, CB5, CE12, TR3 as a whole, by combining both theoretical and applied understanding through the development and implementation of metaheuristics, evaluated empirically.

The practices and part of the interactive sessions will take place using different software tools and developing applications for each of the thematic blocks.

Students will work individually or in small groups, with constant monitoring and tutoring by the teaching staff. Practice scripts will be provided with the tasks to be carried out individually or in small groups.

The teaching will be supported by the USC virtual platform in the following way: repository of the documentation related to the subject (texts, presentations, exercises, practice scripts, ...) and virtual tutoring of students (e-mail, forums).

The learning assessment considers both the theoretical part (60%) and the practical part (40%). In order to pass the subject, an overall mark of 5 or more out of a maximum of 10 points must be obtained, in accordance with the following criteria:
- Theoretical part: this will be assessed in a single exam to be taken on the official date. The grade for each part must be equal to or higher than 4 out of a maximum of 10 points in order to pass the subject as a whole. Otherwise, it will have to be repeated on the opportunity of recovery.

- Practical part: Evaluation of all the mandatory practical activities proposed by the teachers, according to the following schedule:
P1- Metaheuristics based on trajectories (3 interactive sessions).
P2- Population-based metaheuristics (3 interactive sessions)
P3- Swarm-based metaheuristics (3 interactive sessions + evaluation session of this practice).
The evaluation of the 3 interactive practices planned does not end with the delivery of the same but may include the completion of a self-evaluation questionnaire and/or a session of presentation and face-to-face discussion of the same. These evaluation activities will be mandatory and will be carried out in interactive class, so that, for the purposes of the provisions of Art.1 of the “Regulamento de asistencia a clase nas ensinanzas oficiais de grao e máster da Universidade de Santiago de Compostela (25/11/2024)”, attendance at the sessions where these activities are scheduled will be mandatory, being a requirement the completion of the same that, if not met, will result in a grade of 0.0 in the corresponding deliverable. Except for the one indicated in this section, class attendance will not have any other evaluation in the evaluation system, although the attendance to the different teaching activities contributes to improve the understanding of the subject and the acquisition of the competences. As a general rule, the evaluation with the self-evaluation questionnaire is scheduled in the first session of the following practical (usually the following week) while its review and defense in person is done one session later with respect to the session in which the test is taken.
All practicals will have the same weight in the practical grade. The grade of this part must be equal or higher than 4 out of a maximum score of 10 points, in order to pass the whole subject. Those practices and/or self-evaluation questionnaires with a grade lower than 3 out of 10 points must be evaluated in the second opportunity, requiring the completion of additional exercises, the completion of a self-report of corrections and work done, as well as an individualized defense.

The final grade of the subject will be the arithmetic average weighted by the percentages indicated above of the theoretical and practical parts. In case of incurring in any of the situations indicated above regarding not reaching in one or more parts the minimum grade required to pass the subject globally, the final grade of the opportunity will be the grade of the part of lower valuation. The parts that do not reach the minimum grade must be repeated in the second opportunity.



The final grade for the subject will be the arithmetic mean weighted by the percentages indicated above for the theoretical and practical parts. In the event of incurring in any of the situations indicated above due to not achieving the minimum mark required to pass the subject as a whole in one or more parts, the final mark for the opportunity will be the minimum of the marks obtained in those parts. The parts that do not reach the minimum mark must be repeated at the second opportunity.

Students who have not sat the examination or have not submitted to the assessment of any other compulsory activity will be marked as "no-shows".

In order to pass the subject at the second opportunity, students must undergo the evaluation of all those compulsory parts pending, in accordance with the above. For the rest, the grades obtained during the course will be retained.

In the case of fraudulent performance of exercises or tests, what is set out in the regulations on the evaluation of student academic performance and revision of grades will be applicable (https://www.xunta.gal/dog/Publicados/2011/20110721/AnuncioG2018-190711-…). In application of the ETSE regulations on plagiarism (approved by the Xunta da ETSE on 19/12/2019), the total or partial copying of any practical or theory exercise will result in the failure of the two opportunities of the course, with a grade of 0.0 in both cases (https://www.usc.es/etse/files/u1/NormativaPlagioETSE2019.pdf).

Classroom work time: 50 hours in total, divided into 30h (theoretical teaching), 20h (interactive teaching/practical), 1h (tutorials).
Personal working time: 99h (total).

It is recommended that students solve, implement, verify and validate all the proposed exercises and practices (not only the assessable ones). It is also considered important to make intensive use of the tutorials to resolve doubts and to actively participate in the expository and interactive sessions.

It is recommended to have passed the subjects "Mathematical Optimization", "Programming I and Programming II", "Basic Algorithms of Artificial Intelligence".
The course will be taught in Spanish and Galician, but part of the contents, bibliography or other references may be in English.