Publier

INFO-H-413 Heuristic optimisation

< Retour

questions 2022 et 2023 - 10 Jun 2024

Set de questions 2022 :
- expliquer local search
- taille du neighborhood du TSP
- Expliquer SA + il se passe quoi si la température reste constante
- Différence entre minimum local strict et non strict
- Expliquer ACO + combinaison avec ii
- C\'est quoi le multi objective optimizaation + quels algos


Set de questions 2023 :
- C\'est quoi local search
- Parler de SAT et TSP, 2 exchange et tout ce qui est relatif à sa complexité
- Expliquer VND
- Expliquer SA
- C\'est quoi le runtime, comment améliorer avec l\'exemple d\'asymptotic behavior
- itérative greedy
- et un truc en lien avec 3-opt


Oral juin 2024 - 10 Jun 2024

- Difference between constructive and perturbative search
- give an example of perturbative/constructive search for SAT and TSP
- What is the neighborhood size of the 2 exchange TSP ? And what is the complexity, for 1 step, to find the evaluation value ? (Je n’avais pas bien compris sa question mais en gros c’est 1, parce que il suffit de retirer les weights des edges qu’on retire et ajouter ceux des edges qu’on ajoute dans le cycle)
- what is an evaluation function
- is the evaluation function always the same as the objective function ?
- explain SA
- How is SA different from probablistic iterative search ?
- what is a memetic algortihm? Explain the 2 different selections that occurs. What is the lambda-mu selection for the survival selection ?
- What is VND ?
- What is a run time distribution ? Puis il a tracé une autre droite que la mienne et il m’a demandé laquelle était la meilleure. Puis il m’a demandé : how to improve this curve ? J’ai bugué sur le coup et en fait la réponse c’est juste de restart, puisque comme c’est stochastique il y moyen d’avoir de meilleurs résultats
- what is the fitness-distance ?

Oral - 10 Jun 2024

- pertubative algorithm
- strict local minima
- what is neighbourhood
- exchange 2 for tsp + neighbourhood size + time complexity
- explain dynasearch
- explain dynamic local search
- explain ils
- explain solution quality distribution

Oral juin 2024 - 10 Jun 2024

- explique difference entre contructive et perturbative algo
- explique difference entre strict and non-strict minima
- il m\'a demandé quels algos j\'ai fait pour la partie 2 du projet et m\'a demandé d\'en expliquer un
- explique SA et la différence avec probabilistic II
- explique RDT, et il a dessiné un 2ème sur celui que j\'ai fait et m\'a demandé de les comparer. Puis il m\'a demandé ce qu\'on peut faire pour celui qui plateau
- Finalement il m\'a dit de parler de problème multi objectifs. J\'ai expliqué la courbe pareto optimal et puis il m\'a demandé d\'expliquer l\'algo avec les poids (je sais plus comment il s\'appelle)

Oral 10/06/24 - 10 Jun 2024

First questions about simple definitions :
- Define perturbative local search
- Define strict optimum and non-strict optimum
- Define neighbourhood + give example (e.g. 2-exchange for TSP and give the neighbourhood size : n*(n-1)/2)

Then more precise questions on stochastic local search :
- Talk about the lin-kernighan algorithm for the TSP (+ link with k-exchange)
- What\'s a tabu search ? and what\'s the aspiration criterion ? (specifies
conditions under which tabu status may be overridden)
- Talk about the memetic algorithm (used in the 2nd part of implementation exercise)
Talk about the selection strategy (in general and survival) + explain the lambda and mu techniques

Then question about empirical analysis :
- What\'s a runtime ? Need to be precise

Then ask me to leave for 2 minutes, then say the grade

INFO-H-413 - 12 Jun 2010

Le prof a commencé avec une question genre "Qu'est ce qu'on a vu au cours?". Ca parait impressionnant mais pas besoin de précision donc pas de soucis...
Ensuite, il m'a demander de comparer l'apprentissage online et offline. Il m'a plus particulièrement parlé du Tabu Search (pour mon projet, j'avais fait un memetic algo) : des histoires de voisinage, comment l'améliorer, dans quel genre de search space c'est le plus efficace (rugueux, correlé, ...)
Le prof est super sympa, pas de soucis donc de ce coté là


Il n'y a pas de publications plus anciennes.