CS3030–ALGORITHMES D'OPTIMISATION

UNITÉ 1 Introduction aux algorithmes d'optimisation

Part A (2 Marks)
1. Que voulez-vous dire par algorithme d'optimisation et donnez un exemple ?
Un algorithme d'optimisation est une procédure qui s'exécute de manière itérative en comparant divers
solutions jusqu'à ce qu'une solution optimale ou satisfaisante soit trouvée. Avec l'avènement des ordinateurs, l'optimisation
est devenu une partie des activités de conception assistée par ordinateur.

Cinq étapes pour résoudre des problèmes d'optimisation

❖ visualisez le problème
❖ définir le problème
❖ écrivez une équation pour cela
❖ trouver le minimum ou le maximum pour le problème (généralement les dérivées ou les points extrêmes)
❖ répondre à la question

Algorithme d'optimisation en apprentissage profond - Trouve la valeur des paramètres (poids)

qui minimisent l'erreur lors de la cartographie des entrées aux sorties.

2. Quels sont les types d'optimisation et donnez des exemples de chaque méthode d'optimisation ?
Optimisation continue versus optimisation discrète
Optimisation non contrainte versus optimisation contrainte
Optimisation déterministe contre optimisation stochastique
3. Distinguish between continuous optimization and Discrete optimization.
L'optimisation continue – les variables utilisées dans la fonction objective peuvent prendre des valeurs réelles, par exemple,
valeurs provenant des intervalles de la ligne réelle. Méthode d'optimisation analytique descente de gradient, linéaire et non-
optimisation linéaire...
L'optimisation numérique (discrète) – les variables utilisées dans le programme mathématique sont restreintes à
supposer uniquement des valeurs discrètes, telles que les entiers. Optimisation combinatoire programmation entière.

4. Quelles sont les fonctions basées supplémentaires dans l'optimisation sans contrainte ?
Dans des problèmes de test tels que la fonction de Rosenbrock, la fonction de Wood, la fonction quadratique, etc.
sont prises, sur lesquelles différentes méthodes de résolution seront testées. La performance de chaque méthode est comparée
en termes de temps de calcul. D'autres fonctions de test sont,
• La fonction de Rosenbrock
• La fonction de Wood
• Fonction quadratique
• Fonction non linéaire
5. Définir l'optimisation multi-objectifs.
Le problème d'optimisation multiobjectif (également connu sous le nom de problème de programmation multiobjectif)
est une branche des mathématiques utilisée dans la prise de décision multicritères, qui traite de l'optimisation
problèmes impliquant deux ou plusieurs fonctions objectives à optimiser simultanément.
5. Quelles sont les techniques de solution en optimisation contrainte ?

7. Expliquez l'optimisation multivariable

maximum absolu / minimum absolu (également appelé max/min global) : Spécifiez un
la région R contenue dans le domaine de la fonction f. Si la valeur à (a, b) est supérieure ou égale à la valeur
à tout autre point dans R, alors f(a, b) est appelé le maximum global.
8. Analyse de Pareto
Le principe de Pareto stipule que 80 % des bénéfices d'un projet proviennent de 20 %.
pourcentage du travail. Ou, inversement, que 80 pour cent des problèmes peuvent être attribués à 20 pour cent de
Les causes. L'analyse de Pareto identifie les zones ou tâches problématiques qui auront le plus grand impact.

9. Définir les algorithmes de réparation

Les Algorithmes de Réparation sont une technique de gestion des contraintes qui consiste à réparer
individus non réalisables de la population pour les amener vers la région réalisable.
10. Quelles sont les approches par fonction de pénalité ?
Les méthodes de fonction de pénalité approximatif un problème contraint par un
problème non contraint structuré de sorte que la minimisation favorise la satisfaction des contraintes.
La technique générale consiste à ajouter à la fonction objective un terme qui produit un coût élevé en cas de violation de
contraintes.
 Partie B (16 points)
1. Expliquer une brève note sur l'optimisation sans contrainte et l'optimisation avec contrainte avec un exemple.

Optimisation sans contrainte

Les problèmes d'optimisation sont contraints, et les problèmes d'optimisation non contraints sont rares. Un exemple
d'un problème d'optimisation non contraint est l'ajustement de données, où l'on ajuste une courbe sur les données mesurées. Le
les méthodes de solution pour les problèmes d'optimisation sans contrainte peuvent être largement classées en fonction de leur base gradientielle
et des méthodes de recherche non basées sur les gradients. Comme son nom l'indique, les méthodes basées sur les gradients nécessitent un gradient
informations pour déterminer la direction de recherche. Les méthodes basées sur le gradient discutées sont les plus raides
descente, Davidon–Fletcher–Powell (DFP), Broyden–Fletcher–Goldfarb–Shanno (BFGS), Newton, et
Méthodes de Levenberg–Marquardt. La direction de recherche calculée par ces méthodes utilise le gradient
informations, informations Hessiennes, ou une combinaison de ces deux. Certaines méthodes font également un
approximation de la matrice Hessienne. Une fois la direction de recherche identifiée, il faut évaluer comment
beaucoup à déplacer dans cette direction afin de minimiser la fonction. C'est un problème unidimensionnel.

Recherche unidirectionnelle
La recherche unidirectionnelle fait référence à la minimisation de la valeur d'une fonction multivariée le long d'un chemin spécifié.
direction. Par exemple, si xi est le point de départ initial des variables de conception pour minimiser une multivariable
la fonction et S est la direction de recherche, alors nous devons déterminer une quantité scalaire α telle que la fonction
f(α) = xi + αSi
est minimisé. La valeur de α à laquelle cette fonction atteint un minimum est donnée par α*. C'est un un-
problème d'optimisation dimensionnelle et nous pouvons utiliser la technique de la section dorée pour minimiser cette fonction.
La méthode de la section dorée est modifiée pour traiter des fonctions multivariables.

Problème de test
Définissons un système à ressort comme un problème de test sur lequel nous appliquerons l'optimisation multivariable.
algorithms such as the steepest descent, DFP, BFG, Newton, and Levenberg–Marquardt methods. Consider
deux ressorts de longueur unité et avec rigidités k1 et k2, reliés à l'origine. Les deux autres extrémités de la
Les ressorts sont fixés à un mur. En appliquant une force, le système de ressorts se déformera jusqu'à une position d'équilibre.
que nous sommes intéressés à déterminer. Le potentiel du système de ressort est donné par

où est la force appliquée à l'origine en raison de laquelle elle se déplace vers une position (x1, x2)

Techniques de solution
Les techniques de solution pour les problèmes d'optimisation multivariables non contraints peuvent être regroupées en méthodes de gradient.
et des méthodes non basées sur le gradient. Les méthodes basées sur le gradient nécessitent des informations sur les dérivées de la fonction
dans la constitution d'une recherche. Les première et deuxième dérivées peuvent être calculées en utilisant la différence centrale
formule comme indiqué ci-dessous.

L'efficacité des méthodes de solution peut être évaluée selon trois critères :
Nombre d'évaluations de fonction.
• Temps de calcul.
• Taux de convergence. Par cela, nous entendons à quelle vitesse la séquence xi, xi+1,… converge vers x*.
la convergence est donnée par le paramètre n dans l'équation.

Méthode de descente la plus raide

La direction de recherche Si qui réduit la valeur de la fonction est une direction de descente. Il a été discuté plus tôt que
Dans la direction du gradient, il y a le changement maximal dans la valeur de la fonction. Ainsi, le long du négatif
direction du gradient, la valeur de la fonction diminue le plus. La direction du gradient négatif est appelée le
direction de la descente la plus raide. C'est-à-dire,

Lors des itérations successives, les variables de conception peuvent être mises à jour à l'aide de l'équation,
où α est un paramètre scalaire positif qui peut être déterminé à l'aide d'un algorithme de recherche de ligne tel que le
méthode de section dorée.
La méthode de descente la plus raide garantit une réduction de la valeur de la fonction à chaque itération. Si le point de départ
le point est éloigné du minimum, le gradient sera plus élevé et la réduction de la fonction sera
maximisé à chaque itération. Parce que la valeur du gradient de la fonction change et diminue à une petite
valeur près de l'optimum, la réduction de la fonction est inégale et la méthode devient lente
convergence) près du minimum. La méthode peut donc être utilisée comme point de départ pour d'autres méthodes basées sur le gradient.
algorithmes.

Advantage:
La méthode de descente la plus abrupte est celle qui atteint plus près du minimum de la fonction en quelques itérations.
même lorsque la supposition de départ est éloignée de l'optimum.

La méthode de Newton
The search direction in this method is based on the first and second derivative information and is given by

où [H] est la matrice hessienne. Si cette matrice est définie positive, alors Si sera une direction de descente. Bien que
La méthode de Newton est connue pour converger en une seule itération pour une fonction quadratique, il est rare que nous
trouver des fonctions dans des problèmes pratiques qui sont quadratiques. Cependant, la méthode de Newton est souvent utilisée comme un hybride
méthode en conjonction avec d'autres méthodes.

Advantage:
La méthode de Newton montre une convergence plus rapide si la supposition de départ est proche du point minimum.
Disadvantage:
La méthode de Newton peut ne pas converger si le point de départ est éloigné du point optimal.

Méthode de Newton modifiée

La méthode est similaire à la méthode de Newton avec la modification qu'une recherche unidirectionnelle est effectuée.
dans la direction de recherche Si de la méthode de Newton. Pour le même point de départ, la méthode de Newton modifiée
converge vers le point minimal en seulement six itérations par rapport à la méthode de Newton, qui converge
en dix itérations.

Méthode de Levenberg–Marquardt
La méthode de Levenberg-Marquardt est une sorte de méthode hybride qui combine la force des deux
la méthode de descente la plus raide et les méthodes de Newton. La direction de recherche dans cette méthode est donnée par

où I est une matrice d'identité et λ est un scalaire fixé à une valeur élevée au début de l'algorithme. Le
La valeur de λ est modifiée à chaque itération en fonction de si la valeur de la fonction diminue ou non. Si
la valeur de la fonction diminue dans l'itération, λ elle diminue par un facteur (moins de poids sur la descente la plus raide)
direction). D'autre part, si la valeur de la fonction augmente lors de l'itération, λ elle augmente par un facteur (plus
poids sur la direction de la descente la plus raide).

Méthode du gradient conjugué de Fletcher-Reeves

La méthode de Levenberg–Marquardt utilise les forces à la fois de la descente la plus rapide et de la méthode de Newton pour
accélérer la convergence pour atteindre le minimum d'une fonction. La méthode est une méthode d'ordre supérieur,
car il nécessite le calcul de la matrice Hessienne. D'un autre côté, la méthode du gradient conjugué est un
méthode du premier ordre, mais montre la propriété de convergence quadratique et présente ainsi un avantage significatif
par rapport aux méthodes du second ordre. Deux directions, S1 et S2, sont dites conjuguées si

où H est une matrice symétrique, alors, S1 et S2 sont des directions conjuguées.

Méthode DFP
Dans la méthode DFP, l'inverse de la Hessienne est approximé par une matrice [A] et la direction de recherche est
donné par

Les informations stockées dans la matrice [A] sont appelées la métrique et comme elles changent à chaque itération,
la méthode DFP est connue sous le nom de méthode à métrique variable. Parce que cette méthode utilise des dérivées d'ordre un.
et a la propriété d'une convergence quadratique, il est appelé un méthode quasi-Newton.

Méthode BFGS
Dans la méthode BFGS, la matrice hessienne est approximée à l'aide de la matrice de métrique variable [A] donnée par l'équation

Il est important de noter que la matrice [A] converge vers l'inverse du Hessien dans le DFP
méthode, la matrice [A] converge vers le Hessien lui-même dans la méthode BFGS. Comme la méthode BFGS nécessite moins
les redémarrages par rapport à la méthode DFP, elle est plus populaire que la méthode DFP.

Méthode de Powell
La méthode de Powell est une méthode de recherche directe (aucun calcul de gradient n'est requis) avec la propriété de
convergence quadratique. Les directions de recherche précédentes sont stockées dans cette méthode et elles forment une base pour le
nouvelle direction de recherche. La méthode effectue une série de recherches unidirectionnelles le long de ces directions de recherche.
La dernière direction de recherche remplace la première dans la nouvelle itération et le processus se poursuit jusqu'à ce que
la valeur de la fonction ne montre aucune amélioration.

Algorithme de Nelder–Mead
L'algorithme de Nelder–Mead est une méthode de recherche directe et utilise uniquement les informations de fonction (sans gradient)
un calcul est nécessaire) pour passer d'une itération à une autre. La fonction objective est calculée à chaque
sommet du simplexe. En utilisant ces informations, le simplexe est déplacé dans l'espace de recherche. Encore une fois, l'objectif
la fonction est calculée à chaque sommet du simplexe. Le procédé de déplacement du simplexe se poursuit jusqu'à
la valeur optimale de la fonction est atteinte. Trois opérations de base sont nécessaires pour déplacer le simplex dans
l'espace de recherche : réflexion, contraction et expansion Le point centrodal xc est calculé en utilisant tout le
points mais à l'exclusion de xpire. C'est

Le point réfléchi est calculé comme

où α est une constante prédéfinie. En général, α = 1 est pris dans les simulations.

Fonctions de test supplémentaires

Problèmes de test supplémentaires tels que la fonction de Rosenbrock, la fonction de Wood, la fonction quadratique, et ainsi de suite
sont prises, sur lesquelles différentes méthodes de solution seront testées. La performance de chaque méthode est comparée
en termes de temps de calcul.

Fonction de Rosenbrock

The two-variable function is given by

Le minimum de cette fonction "vallée de bananes" est zéro et se produit en (1, 1)

Fonction quadratique

La fonction à deux variables est donnée par

Le minimum de cette fonction est zéro et se produit en (1, 2).

Fonction non linéaire

La fonction à deux variables est donnée par

La fonction de Wood
La fonction à deux variables est donnée par

Optimisation contrainte
Tous les problèmes d'optimisation comportent des contraintes. L'offre d'un produit est limitée par la capacité d'un
machine. La trajectoire d'une fusée est contrainte par l'objectif final ainsi que par la limite aérodynamique maximale.
la charge qu'il peut transporter. L'autonomie d'un aéronef est limitée par sa charge utile, sa capacité en carburant et son aérodynamique
caractéristiques.

Dans les problèmes d'optimisation contrainte, la région faisable est restreinte en raison de la présence de
contraintes. C'est plus difficile car pour un problème à plusieurs variables avec plusieurs non linéaires
Les contraintes, arriver à un point faisable en soi est une tâche décourageante. Le problème d'optimisation contraint
peut être énoncé mathématiquement comme,
Les fonctions f, gje, et hjsont toutes différentiables. Les variables de conception sont limitées par xlet xu. Le
contraintes gjesont appelées des contraintes d'inégalité et hjs'appellent des contraintes d'égalité.

Conditions d'optimalité
Définissons la fonction de Lagrange pour le problème d'optimisation sous contrainte avec l'égalité et
contraintes d'inégalité

Techniques de solution
Pour un problème d'optimisation simple (par exemple, avec deux variables) avec une contrainte d'égalité, le plus simple
l'approche consisterait à utiliser une méthode de substitution de variable. Dans cette méthode, une variable est écrite sous la forme
d'une autre variable en utilisant la contrainte d'égalité. Ensuite, elle est substituée dans la fonction objective pour la rendre
un problème d'optimisation non contraint qui est plus facile à résoudre. Par exemple, considérons l'optimisation
problème
Méthode de fonction de pénalité
La motivation de la méthode de la fonction de pénalité est de résoudre le problème d'optimisation sous contrainte en utilisant
les algorithmes pour les problèmes non contraints. Comme son nom l'indique, l'algorithme pénalise l'objectif
fonction en cas de violation des contraintes. La fonction objectif modifiée avec des termes de pénalité est écrite comme

où es-tuk(>0) est un paramètre de pénalité et la fonction

Dans le cas où les contraintes sont satisfaites (gi (x) ≤ 0),〈gi (x)〉 sera zéro et il n'y aura aucune pénalité sur l'objectif
fonction. En cas de violation des contraintes (gi (x)≥ 0),〈gi (x)〉 sera une valeur positive entraînant une pénalité
sur la fonction objective. La pénalité sera plus élevée pour une plus grande infaisabilité des contraintes. Le
La fonction F(x) peut être optimisée en utilisant les algorithmes pour les problèmes sans contrainte. La fonction de pénalité
la méthode de cette forme est appelée la méthode de fonction de pénalité extérieure.

Les principaux avantages de la méthode de fonction de pénalité sont

• Il peut être commencé à partir d'un point infaisable.

Les méthodes d'optimisation sans contrainte peuvent être utilisées directement.

Les principaux inconvénients de la méthode de fonction de pénalité sont

• La fonction devient mal conditionnée à mesure que la valeur des termes de pénalité augmente. En raison d'une brusque
des changements dans la valeur de la fonction, la valeur du gradient peut devenir grande et l'algorithme peut montrer
divergence.
• Comme cette méthode ne satisfait pas exactement les contraintes, elle n'est pas adaptée aux problèmes d'optimisation où
la faisabilité doit être assurée à toutes les itérations.

Méthode des multiplicateurs de Lagrange augmentée

Comme son nom l'indique, la méthode des multiplicateurs de Lagrange augmentés (ALM) combine à la fois Lagrange
méthodes des multiplicateurs et de la fonction pénalité. Pour un problème d'optimisation avec à la fois des égalités et des inégalités
sous contraintes, la fonction lagrangienne augmentée est donnée par

où λj et βi sont les multiplicateurs de Lagrange, rk est un paramètre de pénalité fixé au début de l'itération.

Programmation Quadratique Séquentielle

La programmation quadratique séquentielle (PQS) est l'une des méthodes les plus efficaces pour les problèmes non linéaires.
problèmes d'optimisation contraints. La méthode génère des étapes en résolvant des sous-problèmes quadratiques ; elle peut
peut être utilisé à la fois dans les recherches de ligne et les cadres de région de confiance. SQP est approprié pour les petits et les grands problèmes
et il est bien adapté à la résolution de problèmes avec des non-linearités significatives.
La méthode SQP peut être considérée comme une généralisation de la méthode de Newton pour l'optimisation sans contrainte.
qu'elle trouve un pas en s'éloignant du point actuel en minimisant un modèle quadratique du problème. Un nombre
des paquets logiciels (NPSOL, NLPQL, OPSYC, OPTIMA, MATLAB et SQP) sont basés sur cette approche. Dans
dans sa forme la plus pure, l'algorithme SQP remplace la fonction objective par l'approximation quadratique.

et remplace les fonctions de contrainte par des approximations linéaires.

Méthode des Directions Faisables

Certains problèmes d'optimisation nécessitent que des contraintes soient satisfaites à chaque itération. Par exemple, considérez
le problème d'optimisation de la forme d'un corps dont la traînée doit être minimisée. La force de traînée est calculée en utilisant
analyse de la dynamique des fluides computationnels (CFD) pour une forme donnée du corps. Il est évident que l'analyse CFD
fournira des résultats fiables s'il n'y a qu'une forme significative du corps. Cela peut être réalisé non seulement par
donner une définition appropriée des contraintes tout en les satisfaisant à chaque itération. Considérez un
problème d'optimisation contrainte

Une direction S est faisable au point x si

Si la fonction objective doit également être réduite, alors l'inégalité suivante doit également être satisfaite :

La méthode des directions réalisables de Zoutendijk et la méthode de projection par gradient de Rosen sont deux méthodes populaires.
méthodes des directions réalisables.

2. Explain a brief note about Gradient-based methods and Direct Search methods.
Se référer à la réponse à la question 1.

3. Expliquez une note courte sur l'optimisation combinatoire avec un exemple.

L'optimisation combinatoire est un domaine émergent à la pointe de la combinatoire et théorique

l'informatique qui vise à utiliser des techniques combinatoires pour résoudre des problèmes d'optimisation discrète.

A discrete optimization problem seeks to determine the best possible solution from a finite set of
Possibilités.

D'un point de vue informatique, l'optimisation combinatoire cherche à améliorer un algorithme en utilisant
méthodes mathématiques soit pour réduire la taille de l'ensemble des solutions possibles soit pour rendre la recherche elle-même
plus rapide

D'un point de vue informatique, l'optimisation combinatoire vise à améliorer un algorithme en utilisant
méthodes mathématiques soit pour réduire la taille de l'ensemble des solutions possibles soit pour rendre la recherche elle-même
plus rapide

Exemple :
L'optimisation combinatoire fait principalement référence aux méthodes utilisées pour aborder de tels problèmes et, pour le
la plupart du temps, ne fournit pas de directives sur la façon de transformer des problèmes du monde réel

en questions mathématiques abstraites, ou vice versa.

C'est un sous-domaine de l'optimisation mathématique qui consiste à trouver un objet optimal parmi un ensemble fini de
objets, où l'ensemble des solutions viables est discret ou peut être réduit à un
ensemble discret

Les problèmes typiques d'optimisation combinatoire sont le problème du voyageur de commerce (« TSP »), le minimum
problème de l'arbre couvrant ("MST"), et le problème du sac à dos.
Applications de l'optimisation combinatoire
Applications de l'optimisation combinatoire
Logistique
Décider quels taxis d'une flotte routent pour prendre des clients
Déterminer la manière optimale de livrer des colis
Attribuer des emplois aux personnes de manière optimale
Conception des réseaux de distribution d'eau Problèmes de sciences de la Terre (par exemple, les débits des réservoirs)

4. Avec un exemple, expliquez l'importance et les étapes impliquées dans l'optimisation combinatoire.
Résumé de la procédure générale de la méthode de branchement et de bornage pour la maximisation de la programmation entière
with flow chart.

Avec un exemple, expliquez l'importance et les étapes impliquées dans l'optimisation combinatoire.
Answer)

Procédure générale de Branch-and-bound pour la maximisation de la programmation entière avec un organigramme

5. Illustrez en détail la feuille de route pour le MOOP.

Feuille de route MOOP

Optimisation multiobjectif:

Maximum absolu / minimum absolu (aussi appelé max/min global) : Spécifiez une région R contenue dans le
domaine de la fonction f. Si la valeur en (a, b) est supérieure ou égale à la valeur à tout autre point dans R,
alors f(a, b) est appelé le maximum global.

L'approche de la somme pondérée :

L'approche de la somme pondérée consiste à réduire notre ensemble d'objectifs en un seul objectif en multipliant chacun de nos
objectifs par un poids fourni par l'utilisateur. Cette méthode est l'une des approches les plus largement utilisées. Une question
ce qui me vient à l'esprit en utilisant l'approche de la somme pondérée, c'est de déterminer quels poids attribuer à chacun
objectif.

Méthodes e-Contraintes :

La méthode ε-contrainte est l'une des méthodes classiques utilisées pour traiter les problèmes multi-objectifs.
optimization problems (MOPs) by converting a MOP into single objective optimization problems (SOPs).
Cette méthode dépend de la valeur epsilon, qui représente une limite de l'objectif.

Programmation par objectifs :

La programmation par objectifs est une branche de l'optimisation multi-objectifs, qui elle-même est une branche de la multi-critères.
analyse de décision (MCDA). On peut le considérer comme une extension ou une généralisation de la programmation linéaire à
gérer plusieurs mesures objectives normalement conflictuelles.

Méthode de Fonction d'Utilité :

Dans cette méthode, une fonction d'utilité U est définie, qui combine toutes les fonctions objectives du multi
problème d'optimisation objective. La fonction d'utilité devient alors la fonction objective de la
problème d'optimisation qui peut être résolu avec les contraintes.

UNITÉ 2 – Approximations

Part A(2 Marks)

1. List out the properties of linear programming model.

2. Quelle est la signification de la variable d'écart ?

3. Définir une fonction unimodale avec un croquis soigné.

4. Qu'est-ce qu'une méthode de branch-and-bound ?

5. Définir la fonction monomiale.

6. Définir la Programmation Stochastique.

La programmation stochastique ou probabiliste traite des situations où certains ou tous les paramètres de la
les problèmes d'optimisation sont décrits par des variables stochastiques (ou aléatoires ou probabilistes) plutôt que par
quantités déterministes. Les sources des variables aléatoires peuvent être plusieurs, en fonction de la nature et du
type de problème. Par exemple, dans la conception de structures en béton, la résistance du béton est une variable aléatoire.
variable puisque la résistance à la compression du béton varie considérablement d'un échantillon à l'autre.

En fonction de la nature des équations impliquées (en termes de variables aléatoires) dans le problème, un stochastique
Le problème d'optimisation est appelé un problème de programmation linéaire stochastique, géométrique, dynamique ou non linéaire.
L'idée de base utilisée dans la programmation stochastique est de convertir le problème stochastique en un équivalent.
problème déterministe. Le problème déterministe résultant est alors résolu en utilisant des techniques familières.
tels que la programmation linéaire, géométrique, dynamique et non linéaire.

7. Énoncé du théorème central limite.

Si X1,X2, . . . ,X nsont n variables aléatoires mutuellement indépendantes avec une moyenne et une variance finies (elles peuvent suivre
différentes distributions), la somme

Sn= ∑=1
tend vers une variable normale si aucune variable unique ne contribue de manière significative à la somme lorsque n tend vers l'infini.
À cause de ce théorème, nous pouvons approcher la plupart des phénomènes physiques comme des variables aléatoires normales.
Physiquement, Snpeut représenter, par exemple, la résistance à la traction d'un matériau renforcé de fibres, auquel cas
la résistance à la traction totale est donnée par la somme des résistances à la traction des fibres individuelles. Dans ce cas, le
La résistance à la traction du matériau peut être représentée comme une variable aléatoire distribuée normalement.

8. État l'application des GP.

GP a été utilisé avec succès comme un outil de programmation automatique, un outil d'apprentissage automatique et un outil automatique.
moteur de résolution de problèmes. La GP est particulièrement utile dans les domaines où la forme exacte de la solution n'est pas
connu à l'avance ou une solution approximative est acceptable (peut-être parce que trouver la solution exacte est
très difficile). Certaines des applications de GP sont l'ajustement de courbe, la modélisation de données, la régression symbolique, la sélection de caractéristiques.

sélection, classification, etc. John R. Koza mentionne 76 instances où la Programmation Génétique a pu

produire des résultats qui sont compétitifs avec des résultats produits par des humains (appelés résultats compétitifs pour les humains).

9. Montrez la représentation de l'arbre du programme en GPs.

Dans la GP basée sur des arbres, les programmes informatiques sont représentés sous forme de structures arborescentes qui sont évaluées de manière récursive

pour produire les expressions multivariées résultantes. La nomenclature traditionnelle stipule qu'un nœud d'arbre (ou simplement
un nœud) est un opérateur [+,-,*,/] et un nœud terminal (ou feuille) est une variable [a,b,c,d].

La GP basée sur les arbres a été la première application de la Programmation Génétique. Il existe plusieurs autres types (comme
présenté sur la page d'accueil de ce site web) tels que linéaire, cartésien et basé sur une pile qui sont typiquement
plus efficaces dans leur exécution des opérateurs génétiques. Cependant, la GP basée sur les arbres fournit un moyen visuel
pour engager de nouveaux utilisateurs de la Programmation Génétique, et reste viable lorsqu'il est basé sur une programmation rapide
langue ou ensemble sous-jacent de bibliothèques.

10. Faites la distinction entre la programmation génétique et l'algorithme génétique.

Les algorithmes génétiques et les EAs similaires sont des techniques d'optimisation puissantes, mais ils ont une inherrence
limitation : ils intègrent la structure de solution supposée dans la représentation de leur candidat
solutions. Cependant, nous ne savons peut-être pas quels paramètres doivent être optimisés dans un problème donné. De plus, nous
il se peut que vous ne connaissiez pas la structure des paramètres qui doivent être optimisés. Les paramètres sont-ils des nombres réels,
ou des machines d'état, ou des programmes informatiques, ou des tableaux complexes, ou des horaires, ou autre chose

La programmation génétique (PG) est une tentative de généraliser les algorithmes évolutionnaires (AE) en un algorithme capable d'apprendre non seulement le meilleur

solution à un problème avec une structure spécifique, mais qui peut aussi apprendre la structure optimale. GP évolue
programmes informatiques pour résoudre des problèmes d'optimisation. C'est la caractéristique distinctive de la GP par rapport à
autres EAs ; d'autres EAs évoluent des solutions, tandis que GP fait évoluer des programmes qui peuvent calculer des solutions. En fait, ceci
était l'un des objectifs initiaux de la communauté de l'intelligence artificielle.

Part B (16 Marks)

1. La matrice de gains du joueur A est montrée dans le tableau ci-dessous.

Player B

Joueur A 3 8 4 4

-7 2 10 2
a) Trouvez la solution optimale en utilisant la méthode graphique
 b) Écrivez le problème de programmation linéaire par rapport au Joueur A

c) Écrivez le problème de programmation linéaire en ce qui concerne le Joueur B.

La réponse est jointe au fichier.

2. Résoudre le problème d'optimisation en utilisant la programmation géométrique Minimiser f(x) = 3x1x2-3+ 4x1 -1 2

x2x3-2+5x1x2x3-14 + 6x3
3. Formulez la fonction objectif sous la forme d'une forme posynomiale en détail.
4. Expliquez en détail la programmation non linéaire entière avec des exemples pertinents.
{"text":"5. Expliquez la DUALITÉ dans la programmation non linéaire ? Expliquez le concept de local et global"}
minima
6. Expliquez la CONVEXITÉ dans la programmation non linéaire et expliquez l'impact des minima et
convexité en PNL
7. Énumérez les étapes des GP avec un exemple et signalez les opérateurs courants utilisés pour les GP.

Voici quelques étapes pour mettre en œuvre un GP.

i. Quelle est la mesure de la condition physique ?

ii. Quel est le critère d'arrêt ?

iii. Quel est l'ensemble terminal pour les programmes informatiques en évolution ? C'est-à-dire, quels symboles peuvent
apparaître aux feuilles des arbres syntaxiques ?
iv. Quelle est la fonction définie pour les programmes informatiques en évolution ? C'est-à-dire, quelles fonctions peuvent
apparaître aux nœuds non terminaux des arbres syntaxiques ?
v. Comment devrions-nous générer la population initiale de programmes informatiques ?
vi. Quels autres paramètres devons-nous déterminer pour contrôler l'exécution de GP ?

Un aperçu conceptuel d'un programme génétique simple.

Parents {programmes informatiques générés aléatoirement}

Tant que non (critère de terminaison)
Calculez la condition de chaque parent dans la population
Enfants Ø
While | Children | < | Parents |
Utilisez les aptitudes pour sélectionner les parents p de manière probabiliste.1et p2
Mate pi and P2 to create children c\ and c^
Enfants Enfants U {c1, c2}
Boucle
Muter aléatoirement certains des enfants
Parents Enfants
Prochaine génération
Fitness Measure
Quelle est la mesure de la forme physique ? Cette décision doit être prise pour tous les EAs, mais la décision est plus compliquée.
avec GP. Un programme informatique doit bien fonctionner pour une grande variété d'entrées, une variété de conditions initiales,
et une variété d'environnements. Par exemple, un programme pour trouver une trajectoire de satellite économe en carburant d'un
L'orbite vers une autre devrait bien fonctionner pour divers paramètres de satellites et diverses orbites. Par conséquent, beaucoup
différentes conditions doivent être utilisées pour déterminer l'aptitude d'un programme informatique. Pour un donné
programme informatique, chaque ensemble d'entrées de l'ordinateur et condition de fonctionnement retourne sa propre "sous-fitness". Comment
devrions-nous combiner ces sous-fitness pour obtenir une mesure de fitness unique pour le programme informatique ? Devrait-on
utilisons-nous la performance moyenne ? Devons-nous essayer de maximiser la performance dans le pire des cas ? Devons-nous utiliser certains

combinaison des deux ? Ces questions mènent naturellement à l'optimisation multi-objectifs (Chapitre 20),
bien qu'il ne soit pas nécessaire d'utiliser l'optimisation multi-objectifs dans le GP.

Critères de résiliation
Quel est le critère de terminaison ? Cette question doit être répondue pour tous les EAs, mais elle peut être particulièrement
important pour GP. Cela est dû au fait que la mesure de fitness est généralement plus exigeante en termes de calcul dans GP
que dans d'autres EA. Le choix du critère de terminaison pourrait déterminer si le GP est
réussi. Comme pour d'autres EAs, le critère de terminaison pour GP pourrait inclure des facteurs tels que le nombre de
iterations, number of fitness evaluations, run time, best fitness value, change in best fitness over several
générations, ou écart-type des valeurs de fitness sur l'ensemble de la population.

Ensemble Terminal
Quel est l'ensemble terminal pour les programmes informatiques évolutifs ? Cet ensemble décrit les symboles qui peuvent
apparaître aux feuilles des arbres de syntaxe. L'ensemble terminal est l'ensemble de toutes les entrées possibles à l'évolution
programmes informatiques. Cet ensemble comprend des variables qui sont des entrées pour le programme informatique, ainsi que
des constantes que nous pensons pouvoir être importantes. Les constantes pourraient inclure des entiers de base comme 0 et 1, et
également des constantes qui peuvent être importantes pour le problème d'optimisation particulier
(π, e, etc.).
 Les arbres de syntaxe ont trois terminaux : x, y et z. Certains
les constantes peuvent être obtenues implicitement ; par exemple, x - x =
0, et x/x—1. Donc tant que nous avons une soustraction et
fonction de division, nous n'avons pas vraiment besoin du 0 et du 1
constantes. Cependant, la plupart des implementations GP devraient
inclure des constantes dans leurs ensembles terminaux.
Nous pouvons également utiliser des nombres aléatoires dans l'ensemble terminal, mais
en général, nous ne voulons pas qu'un nombre aléatoire change après
il est généré. Ces types de nombres aléatoires sont appelés
constantes aléatoires éphémères. Aléatoire éphémère
les constantes sont obtenues en spécifiant une quantité désignée
comme R dans le terminal défini. Si R est choisi comme terminal pendant
initialisation de la population, nous générons un nombre aléatoire
r1entre les limites données, et insérer r1dans le GP
individu. À partir de ce moment-là, cette valeur particulière r 1
ne change pas. Cependant, si R est choisi à nouveau pour
initialisation d'un autre individu, ou pour mutation, alors
nous générons une nouvelle constante aléatoire r2pour cela
réalisation. Le choix des limites dans lesquelles
générer des constantes aléatoires éphémères est un autre GP
décision de conception. Définir l'ensemble terminal pour un GP
l'application est un exercice d'équilibre. Si nous utilisons un ensemble qui est trop
petit, alors le médecin généraliste ne pourra pas résoudre efficacement notre
problème. Cependant, si nous utilisons un ensemble terminal qui est trop
large, alors il peut être trop difficile pour le GP de trouver un bon
solution dans un délai raisonnable.

Koza étudie cette question pour le problème simple de

découvrir le programme x3 + x2 + x sur la base de 20 cas de test. Pour cela
problème, le seul terminal dont le GP a besoin est x. Quand l'ensemble des terminaux est le
ensemble minimal {x}, le GP trouve le bon programme en 50 générations
99,8 % du temps. Le tableau montre comment la probabilité de succès diminue
lorsque des membres supplémentaires (nombres à virgule flottante aléatoires) sont ajoutés au
ensemble terminal de la PG. Pour ce problème simple, la probabilité de succès
diminue linéairement avec le nombre de variables extranéennes dans le terminal
ensemble. La bonne nouvelle est que même lorsque 32 des 33 membres dans le terminal
L'ensemble est accessoire, mais GP est toujours capable de résoudre le problème 35 % du temps.

Fonction Ensemble
Quelle est la fonction définie pour les programmes informatiques en évolution ? Cet ensemble décrit les fonctions qui peuvent
apparaître aux nœuds non terminaux des arbres syntaxiques, tels que les suivants.
• Les opérateurs mathématiques standard peuvent être inclus dans l'ensemble de fonctions (par exemple, addition, soustraction,
multiplication, division, valeur absolue).
• Des fonctions spécifiques au problème que nous pensons être importantes pour notre problème d'optimisation particulier peuvent être
inclus dans l'ensemble de fonctions (par exemple, les fonctions exponentielles, les fonctions logarithmiques, les fonctions trigonométriques
fonctions, filtres, intégrateurs, différents.
• Des tests conditionnels peuvent être inclus dans l'ensemble de fonctions (par exemple, supérieur à, inférieur à, égal à).
• Les fonctions logiques peuvent être incluses dans l'ensemble des fonctions, si nous pensons qu'elles pourraient être applicables à la solution.
de notre problème d'optimisation particulier (par exemple, et, nand, ou, xor, nor, non).
Les fonctions d'assignation de variables peuvent être incluses dans l'ensemble de fonctions.
• Les instructions de boucle peuvent être incluses dans l'ensemble de la fonction (par exemple, les boucles while, les boucles for).
• Les appels de sous-routine peuvent être inclus dans l'ensemble de fonctions, si nous avons un ensemble de fonctions prédéfinies que nous avons.
créé pour notre problème.
Les arbres de syntaxe dans la Figure comprennent cinq fonctions : addition, soustraction, multiplication, division, et
valeur absolue. Nous devons trouver le bon équilibre dans notre définition de l'ensemble des fonctions et de l'ensemble terminal.
Les ensembles doivent être suffisamment grands pour pouvoir représenter une solution à notre problème, mais s'ils sont trop grands,
alors l'espace de recherche sera si vaste que le GP aura du mal à trouver un bon
solution.
Certaines fonctions doivent être modifiées pour GP car les arbres syntaxiques évolutifs peuvent ne pas avoir de fonction légale.
arguments. Par exemple, GP pourrait évoluer l'expression (/ x 0), qui est une division par zéro. Cela aurait
cela entraînerait une erreur Lisp, ce qui provoquerait la terminaison du GP. Par conséquent, au lieu d'utiliser le standard
opérateur de division en Lisp, nous pouvons définir un opérateur de division DIV qui protège contre la division par zéro, et
cela protège également contre le dépassement dû à une division par un nombre très petit :

(defun DIV (x y) ; définir une fonction de division protégée

(si (< (absy)ϵ) (retourner-de DIV 1)) ; retourne 1 si le diviseur est très petit
retourner-de DIV (/x y) ; sinon retour x/y

où ϵ est une très petite constante positive, comme 10-20. L'équation montre la syntaxe Lisp pour définir un protégé
routine de division. La fonction DIV renvoie 1 si le diviseur a une magnitude très petite. Nous pouvons avoir besoin de
redéfinir d'autres fonctions de manière similaire (fonctions logarithmiques, fonctions trigonométriques inverses, et ainsi de suite)
to make sure that the functions in our function set can handle all possible inputs.

Initialisation
Comment devrions-nous générer la population initiale de programmes informatiques ? Nous avons deux options de base pour
initialisation, qui sont appelées la méthode complète et la méthode de croissance. Nous pouvons également combiner celles-ci.
options pour obtenir une troisième option, qui est appelée la méthode demi-demi progressive.
La méthode complète crée des programmes de sorte que le nombre de nœuds de chaque nœud terminal jusqu'au niveau supérieur
le nœud est Dc, une constante spécifiée par l'utilisateur. Dcest appelé la profondeur de l'arbre syntaxique. À titre d'exemple, Parent 1 dans
Figure 7.3 has a depth of three, while Parent 2 has a depth of four. Parent 1 in Figure 7.3 is a full syntax tree
car il y a trois nœuds de chaque nœud terminal au nœud d'addition de niveau supérieur. Cependant, Parent 2
n'est pas un arbre de syntaxe complet car certaines des branches du programme ont une profondeur de quatre tandis que d'autres en ont seulement
une profondeur de trois.
Nous pouvons utiliser la récursivité pour générer des arbres syntaxiques aléatoires. Par exemple, si nous voulons générer un arbre syntaxique
avec une structure comme Parent 2, nous générons d'abord le nœud de soustraction au niveau supérieur et remarquons que cela
requiert deux arguments. Pour le premier argument, nous générons le nœud de multiplication et notons qu'il
nécessite deux arguments. Ce processus se poursuit pour chaque nœud et chaque argument jusqu'à ce que nous ayons généré
assez de niveaux pour atteindre la profondeur désirée. Lorsque nous atteignons la profondeur désirée, nous générons un terminal aléatoire
nœud pour compléter cette branche de l'arbre syntaxique. La figure ci-dessous illustre le concept pour une récursive
algorithme qui génère des programmes informatiques aléatoires. Nous pouvons générer un arbre de syntaxe aléatoire en appelant
routine GrowProgramFull(Dc, 1), où Dcest la profondeur d'arbre de syntaxe souhaitée. GrowProgramFull s'appelle lui-même
chaque fois qu'il doit ajouter une autre couche dans sa croissance
arbre syntaxique.

La méthode de croissance d'initialisation crée des programmes tels que le nombre de nœuds à partir de chaque nœud terminal
au nœud de niveau supérieur est inférieur ou égal à DcSi les parents de la Figure 7.3 ont été créés au hasard
initialisation, ensuite le Parent 1 pourrait avoir été généré avec soit la méthode complète soit la méthode de croissance,
bien que le Parent 2 ait été définitivement généré avec la méthode de croissance puisqu'il ne s'agit pas d'un arbre de syntaxe complet. La croissance
la méthode peut être implémentée de la même manière que la méthode complète, sauf que lorsque nous générons un nœud aléatoire
à des profondeurs inférieures à Dc, soit un nœud de fonction soit un nœud terminal peut être généré. Si un nœud de fonction est généré,
l'arbre syntaxique continue de croître. Comme avec la méthode complète, lorsque nous atteignons la profondeur maximale Dc, nous
générez un terminal aléatoire pour compléter cette branche de l'arbre syntaxique. La figure ci-dessous illustre le
concept pour un algorithme récursif qui génère des programmes informatiques aléatoires avec la méthode grow.
La méthode du demi-avant complet avec rampe génère la moitié de la population initiale avec la méthode complète, et l'autre moitié avec
la méthode de croissance. De plus, elle génère un nombre égal d'arbres syntaxiques pour chaque valeur de profondeur entre 2 et
Dc, qui est la profondeur maximale autorisée spécifiée par l'utilisateur. La figure 7.8 illustre le concept de
initialisation d'arbre syntaxique demi-demi en rampe.

Koza a expérimenté les trois types d'initialisations décrites ci-dessus pour quelques GP simples.
problèmes. Il a trouvé une différence dans la probabilité de succès du GP en fonction de la méthode d'initialisation utilisée
a été utilisé, comme montré dans le tableau 7.2. Le tableau montre que la méthode d'initialisation moitié-moitié avec rampes est
généralement bien mieux que les deux autres méthodes d'initialisation.

Paramètres de la programmation génétique

Quels sont les paramètres qui contrôlent l'exécution de GP ? Ces paramètres incluent ceux qui sont utilisés pour d'autres
EAs, mais incluez également des paramètres spécifiques aux GP.
Nous devons spécifier la méthode de sélection par laquelle les parents sont choisis pour participer au croisement.
pourrait utiliser une sélection proportionnelle à la forme physique, une sélection par tournoi, ou une autre méthode. En fait, nous pourrions utiliser
n'importe lequel des méthodes de sélection. C'est également un bon endroit pour mentionner que nous pourrions mettre en œuvre des méthodes basées sur les arbres.
croiser de façon plus intelligente que de simplement sélectionner des points de croisement aléatoires. Il existe certains sous-arbres qui
sont plus utiles que d'autres, et nous ne voudrions peut-être pas décomposer ces sous-arbres. Nous pourrions quantifier la forme physique
des sous-arbres en obtenant des corrélations entre les points de croisement et la performance des programmes enfants, puis
utiliser ces corrélations pour influencer la sélection des futurs points de croisement.
2. Nous devons préciser la taille de la population. Étant donné qu'il y a tant de degrés de liberté dans l'informatique.
Les programmes, la programmation génétique a généralement des populations plus grandes que les autres algorithmes évolutionnaires. La programmation génétique a généralement une taille de population d'au moins
500, et a souvent une taille de population de plusieurs milliers.
3. Nous devons spécifier la méthode de mutation. Différentes méthodes de mutation GP ont été utilisées au fil des ans,
dont certains sont décrits comme suit.
(a) Nous pouvons sélectionner un nœud aléatoire et remplacer tout ce qui se trouve en dessous de ce nœud par un généré aléatoirement.
arbre de syntaxe. Cela s'appelle la mutation d'arbre [Koza, 1992, page 106]. Cela équivaut à croiser un
programme avec un programme généré aléatoirement, et est également appelé croisement de poulet sans tête [Angeline,
1997].
(b) La mutation d'expansion remplace un terminal par un sous-arbre généré aléatoirement. Cela équivaut à
mutation de sous-arbre si le nœud remplacé dans la mutation de sous-arbre est terminal.
(c) Nous pouvons remplacer un nœud ou un terminal sélectionné au hasard par un nouveau nœud ou terminal généré aléatoirement.
Cela s'appelle une mutation ponctuelle ou une mutation de remplacement de nœud, et nécessite que l'arité de celui qui est remplacé
le nœud doit être égal à l'arité du nœud de remplacement. Par exemple, nous pourrions remplacer une opération d'addition
avec une opération de multiplication, ou nous pourrions remplacer une opération de valeur absolue par une opération de sinus.
(d) La mutation de levage crée un nouveau programme qui est un sous-arbre sélectionné au hasard du programme parent.
(e) La mutation de réduction remplace un sous-arbre de syntaxe choisi au hasard par un terminal sélectionné au hasard ; cela est
également appelé mutation de sous-arbre de collapse. La mutation de levage et la mutation de réduction ont été initialement introduites pour
réduire le code encombrant.
(f) La mutation par permutation permute aléatoirement les arguments d'une fonction sélectionnée au hasard [Koza, 1992].
Par exemple, nous pourrions remplacer les arguments x et y d'une fonction de division. Bien sûr, ce type de mutation
n'a aucun effet sur les fonctions commutatives.
(g) Nous pouvons muter aléatoirement des constantes dans un programme [Schoenauer et al., 1996]. Nous mettons souvent en œuvre
mutation de manière à ce que le programme mutant remplace le programme original uniquement s'il est plus adapté. Ceci
L'idée de remplacer uniquement si cela convient mieux peut être appliquée à la mutation dans n'importe quel algorithme évolutif.
4. Nous devons spécifier la probabilité de mutation pm. Cela est similaire à d'autres EAs. La mutation dans un GP avec N
les individus sont souvent mis en œuvre avec une méthode similaire à la suivante :

La grande taille de la population qui est utilisée dans GP, ainsi que le grand nombre de nœuds possibles où
un croisement peut se produire, ce qui signifie généralement que de bons résultats de GP ne dépendent pas de la mutation. Souvent, nous pouvons obtenir de bons
résultats avec pm= 0. Cependant, la mutation peut néanmoins être souhaitable au cas où un terminal ou une fonction importante
est perdu pour la population. Si cela se produit, la mutation est le seul moyen par lequel il pourrait réintégrer la population.
5. Nous devons spécifier la probabilité de crossover pc. C'est similaire aux G As. Après avoir sélectionné deux parents dans
À la figure 7.5, nous pouvons soit utiliser le croisement pour les combiner, soit les cloner pour la prochaine.
génération. La ligne : Mate pi et pi pour créer des enfants c1et c2dans la Figure 7.5 serait alors remplacé par
quelque chose comme ce qui suit :

La plupart des expériences suggèrent que le croisement est un aspect important de la GP et doit être utilisé avec une probabilité
pc≥ 0,9.
6. Nous devons décider si nous devons ou non utiliser l'élitisme. Comme avec tout autre EA, nous pouvons sauvegarder le meilleur ordinateur.
des programmes en GP d'une génération à l'autre pour s'assurer qu'ils ne sont pas perdus dans la génération suivante.
Le paramètre est appelé le paramètre d'élitisme. L'élitisme peut être mis en œuvre de plusieurs manières différentes.
par exemple, nous pourrions archiver les meilleurs m individus à la fin d'une génération, créer les enfants pour la suivante
génération comme d'habitude, puis remplacer les pires m enfants par les élites de la génération précédente.
Alternativement, nous pourrions copier les m élites aux premiers m enfants à chaque génération, puis créer seulement (N—
m) enfants supplémentaires à chaque génération (où N est la taille de la population).
7. Nous devons spécifier Dje, la taille maximale du programme de la population initiale. La taille d'un programme peut être
quantifié par sa profondeur, qui mesure le nombre maximum de nœuds entre le niveau le plus élevé et le
niveau le plus bas (inclus). Par exemple, le Parent 1 dans la Figure 7.3 a une profondeur de trois, tandis que le Parent 2 a une profondeur
de quatre.
8. Nous devons également spécifier Dc, la profondeur maximale des programmes enfants. Pendant le fonctionnement de GP, les programmes enfants
peut croître de plus en plus à chaque génération successivement. Si une profondeur maximale n'est pas imposée, alors l'enfant
les programmes peuvent devenir déraisonnablement longs, gaspillant de l'espace et du temps d'exécution ; cela s'appelle le gonflement GP.
profondeur maximale Dcpeut être appliqué de plusieurs manières. Une façon est de remplacer un enfant par l'un de ses parents si
la profondeur de l'enfant dépasse DcUne autre façon est de refaire l'opération de croisement si la profondeur de l'enfant dépasse D.c.
Une autre manière est d'examiner les arbres syntaxiques parents avant de choisir leurs points de croisement, et de contraindre
les points de croisement choisis au hasard pour que Dcne sera pas dépassée par les profondeurs des enfants.
9. Nous devons décider si nous voulons ou non permettre qu'un nœud terminal dans un arbre syntaxique soit remplacé par
un sous-arbre pendant le croisement. La figure 7.4 montre que le terminal z dans le Parent 1 est sélectionné pour le croisement, et
est remplacé par un sous-arbre dans l'Enfant 1. Nous utilisons pi pour désigner la probabilité de croisement à un nœud interne.
Lors de la sélection d'un point de croisement, nous générons un nombre aléatoire r uniformément distribué sur [0,1]. Si r est
moins que pje, ensuite nous sélectionnons un nœud terminal pour le croisement ; c'est-à-dire, nous sélectionnons un symbole dans l'arbre de syntaxe qui
n'est pas immédiatement précédé d'une parenthèse gauche. Cependant, si r est supérieur à pi, alors nous sélectionnons un s-
expression pour le croisement ; c'est-à-dire que nous sélectionnons un sous-arbre qui est entouré par des gauche et droite correspondants
parenthèses pour le croisement.
10. Nous devons décider s'il faut s'inquiéter ou non des individus dupliqués dans la population. Dupliqué
Les individus sont un gaspillage de ressources informatiques. Dans les EAs avec des espaces de recherche relativement petits ou petits
les populations, les doublons peuvent surgir assez souvent, et traiter les doublons peut être un aspect important de la
EA. Cependant, dans GP, l'espace de recherche est si vaste que les doublons se produisent rarement. Par conséquent, nous ne le faisons généralement pas.
il faut s'inquiéter des individus dupliqués dans GP.

UNITE 3 – METHODES DE RECHERCHE ALEATOIRE

PARTIE A (2 Points)

1. State few advantages and disadvantages of genetic algorithm and mention the role of fitness
fonction dans l'algorithme génétique.
Réponse :
Advantages:
• Ne nécessite aucune information dérivée (qui peut ne pas être disponible pour de nombreux cas réels)
problèmes).
• Est plus rapide et plus efficace par rapport aux méthodes traditionnelles.
• A de très bonnes capacités parallèles.
• Optimise à la fois les fonctions continues et discrètes ainsi que les problèmes multi-objectifs.
• Fournit une liste de « bonnes » solutions et pas seulement une solution unique.
• Obtient toujours une réponse au problème, qui s'améliore avec le temps.
• Utile lorsque l'espace de recherche est très grand et qu'un grand nombre de paramètres sont impliqués.
Limitations :
• Les GAs ne conviennent pas à tous les problèmes, en particulier aux problèmes simples pour lesquels la dérivée
l'information est disponible.
• La valeur de fitness est calculée de manière répétée, ce qui peut être coûteux en termes de calcul pour certains.
problèmes.
• Étant stochastique, il n'y a aucune garantie sur l'optimalité ou la qualité de la solution.
• Si elle n'est pas mise en œuvre correctement, l'AG peut ne pas converger vers la solution optimale.
Rôle de la fonction de fitness dans l'algorithme génétique.
Une fonction de fitness, simplement définie, est une fonction qui prend la solution comme entrée et produit la pertinence.
de la solution comme sortie. Dans certains cas, la fonction de fitness et la fonction objective peuvent être les mêmes,
tandis que dans d'autres, cela pourrait être différent en fonction du problème.
2. En quoi l'algorithme génétique diffère-t-il de l'algorithme traditionnel ?

3. Mentionnez les avantages de l'optimisation par essaim de particules et ses applications.

Avantages :
Les principaux avantages de l'algorithme PSO peuvent être résumés comme suit : concept simple, mise en œuvre facile,
robustesse par rapport aux paramètres de contrôle et efficacité computationnelle par rapport aux mathématiques
algorithmes et autres techniques d'optimisation heuristique.
Applications :
L'optimisation par essaim particulaire (PSO) peut être appliquée à divers problèmes d'optimisation, par exemple, l'optimisation du stockage d'énergie. PSO peut
simuler le mouvement d'un essaim de particules et peut être appliqué dans les effets visuels comme ces effets spéciaux dans
le film hollywoodien.

4. Quelles sont les caractéristiques de l'algorithme d'Optimisation par Colonies de Fourmis ?

Réponse : L'optimisation par colonies de fourmis (ACO) est une métaheuristique basée sur les populations qui peut être utilisée pour trouver
solutions approximatives à des problèmes d'optimisation difficiles. Dans ACO, un ensemble d'agents logiciels appelés artificiels
les fourmis recherchent de bonnes solutions à un problème d'optimisation donné.

5. Justifiez que l'intelligence des essaims est supérieure aux algorithmes de calcul conventionnels.
La notion intuitive d'« intelligence des essaims » est celle d'un « essaim » d'agents (biologiques ou
artificiel) qui, sans contrôle central, exécutent collectivement (et seulement collectivement) (inconsciemment, et
d'une manière quelque peu aléatoire) des tâches nécessitant normalement une forme de «intelligence». La capacité de
calcul universel réalisé avec asynchronie naturelle par un système de calcul cellulaire dynamique, aucun
dont les cellules peuvent prédire le calcul effectué par le nuage.
6. Que signifie l'algorithme d'optimisation basé sur la biogéographie ?

La biogéographie est l'étude de la distribution géographique des organismes biologiques.

L'optimisation basée sur la biogéographie est un algorithme évolutif qui optimise une fonction de manière stochastique.
et en améliorant de manière itérative les solutions candidates par rapport à une mesure de qualité donnée, ou fonction de qualité.
7. Define Swarm Intelligence and what is the characteristics of the swarm?
L'intelligence en essaim (IE) est le comportement collectif de systèmes décentralisés et auto-organisés, naturels ou
artificiel. Le concept est utilisé dans le travail sur l'intelligence artificielle. L'expression a été introduite
par Gerardo Beni et Jing Wang en 1989, dans le contexte des systèmes robotiques cellulaires.
Caractéristiques :
• Le système est composé d'un grand nombre d'individus
 • Le système est composé d'individus homogènes ayant des caractéristiques similaires.
• L'information doit être échangée entre les individus soit directement, soit par le biais de l'environnement.
autres mots, le groupe doit fonctionner sur la base de l'auto-organisation.
• Les interactions entre les individus doivent uniquement être basées sur des informations locales.

8. Quelle est la différence entre les méthodes heuristiques et les méthodes métaheuristiques ?

Méthode heuristique Méthode métaheuristique

Les heuristiques sont souvent dépendantes du problème, c'est-à-dire des méthodes métaheuristiques.
sont problème indépendant
définir une heuristique pour un problème donné techniques qui peuvent être appliquées à un large éventail de
problèmes.
Exemple : Choisir un élément aléatoire comme pivot. Les métaheuristiques ne connaissent rien du problème.
dans le tri rapide il sera appliqué, il peut traiter des fonctions un noir
boîtes
Il exploite les informations dépendantes du problème pour trouver des métaheuristiques qui ressemblent à des modèles de conception généraux.
une solution suffisamment bonne à un problème spécifique idées algorithmiques qui peuvent être appliquées à un large
gamme de problèmes

9. Quelles sont les principales stratégies de la recherche tabou ?

3 stratégies principales :
Stratégie d'interdiction :
contrôler ce qui entre dans la liste tabou
Stratégie de libération : contrôle
qu'est-ce qui sort de la liste tabou et quand
• Stratégie à court terme :
gérer l'interaction entre la stratégie d'interdiction et la stratégie de libération pour sélectionner des solutions d'essai

10. Pourquoi la recherche d'harmonie est-elle réussie ?

Il nécessite moins de connaissances en mathématiques et aucune connaissance des dérivées.
2. Utilisez à la fois des variables continues, discrètes et entières
Trouve une solution raisonnablement bonne avec peu d'itérations.
4. Pas besoin de spécifier une valeur initiale spéciale pour la variable de décision lors du démarrage de l'algorithme de problème.

PARTIE–B (16 Points)

1. Dessinez le diagramme en blocs fonctionnel du système d'intelligence collective, expliquez le rôle des sous-blocs.
Représentez également les propriétés et le domaine d'application des systèmes d'intelligence collective.

L'intelligence collective (IC) est le comportement collectif de systèmes décentralisés et auto-organisés.

naturel ou artificiel. Le concept est utilisé dans les travaux sur l'intelligence artificielle. L'expression a été
introduit par Gerardo Beni et Jing Wang en 1989, dans le contexte des systèmes robotiques cellulaires.

Aspects clés :
• Comportement : Difficile de prédire le comportement à partir des règles individuelles.

• Connaissance : Les fonctions de la colonie ne pouvaient pas être comprises avec la connaissance du fonctionnement de
un agent.
• Sensibilité : Même un petit changement dans les règles simples entraîne un comportement de groupe différent.
Avantages du regroupement

• Plus de transparence. Le travail en essaim rend l'expérience plus agréable pour toutes les parties concernées.

• Développement de nouvelles compétences. Le travail en essaim ouvre de nouvelles façons de collaborer : il prospère grâce aux compétences diverses.
dans votre équipe.

• Autonomisation des employés.

• Réduction du turnover du personnel.

Algorithmes d'intelligence en essaim

Ces algorithmes comprennent

• Algorithmes Génétiques (AG)

• Optimisation par Colonies de Fourmis (ACO)

• Optimisation par essaim de particules (PSO)

• Évolution Différentielle (ED)

• Colonies d'Abeilles Artificielles (ABC)

• Optimisation par essaim de ver luisant (GSO)

• et l'algorithme de recherche Cuckoo (CSA).

Properties:
La propriété caractéristique d'un système d'intelligence de groupe est sa capacité à agir de manière coordonnée.
sans la présence d'un coordinateur ou d'un contrôleur externe.
Propriétés fondamentales des métaheuristiques

• Les métaheuristiques sont des stratégies qui "guident" le processus de recherche.

• L'objectif est d'explorer efficacement l'espace de recherche afin de trouver des solutions (près de) optimales.

• Les algorithmes métaheuristiques sont approximatifs et généralement non déterministes.

• Les métaheuristiques ne sont pas spécifiques à un problème.

Applications :
L'intelligence en essaim (IE) est le comportement collectif de systèmes décentralisés et auto-organisés.
naturel ou artificiel. Les systèmes SI sont généralement composés d'une population d'agents simples interagissant localement
les uns avec les autres et avec leur environnement. L'inspiration vient souvent de la nature, en particulier
systèmes biologiques.
2. Énumérez la procédure impliquée dans l'utilisation de l'algorithme génétique pour optimiser le contrôleur
paramètres.
L'algorithme génétique est une méthode pour résoudre à la fois les problèmes contraints et non contraints.
problèmes d'optimisation qui sont basés sur la sélection naturelle, le processus qui motive l'évolution biologique. Le
L'algorithme génétique modifie de manière répétée une population de solutions individuelles.
L'algorithme génétique (GA) est une technique d'optimisation basée sur la recherche, fondée sur les principes de
Génétique et sélection naturelle. Elle est souvent utilisée pour trouver des solutions optimales ou presque optimales à des problèmes difficiles.
des problèmes qui autrement prendraient une vie à résoudre.
Il génère des solutions à des problèmes d'optimisation en utilisant des techniques inspirées de l'évolution naturelle.
tels que l'hérédité, la mutation, la sélection et le croisement.
Les algorithmes génétiques sont basés sur les principes de la génétique naturelle et de la sélection naturelle. Les éléments de base
de la génétique naturelle—reproduction, croisements et mutations—sont utilisés dans la procédure de recherche génétique. Les AG
diffèrent des méthodes traditionnelles d'optimisation à cet égard :
1. Une population de points (vecteurs de conception d'essai) est utilisée pour
commençant la procédure au lieu d'un seul point de conception. Si
le nombre de variables de conception est n, généralement la taille du
la population est considérée comme 2n à 4n. Puisque plusieurs points sont
utilisées comme solutions candidat, les AG ont moins de chances d'obtenir
piégé dans un optimum local.
2. Les algorithmes génétiques n'utilisent que les valeurs de la fonction objectif. Le
les dérivées ne sont pas utilisées dans la procédure de recherche.
3. Dans les GAs, les variables de conception sont représentées sous forme de chaînes.

des variables binaires qui correspondent aux chromosomes

dans la génétique naturelle. Ainsi, la méthode de recherche est naturellement
applicable pour résoudre la programmation discrète et entière
problèmes. Pour des variables de conception continues, la chaîne
La longueur peut être variée pour atteindre la résolution souhaitée.
4. La valeur de la fonction objective correspondant à un design
le vecteur joue le rôle de la forme physique dans la génétique naturelle.
5. Dans chaque nouvelle génération, un nouvel ensemble de chaînes est
produit en utilisant une sélection de parents randomisée et
crossover from the old generation (old set of strings).
Bien que randomisés, les algorithmes génétiques ne sont pas une simple recherche aléatoire.
techniques. Ils explorent efficacement les nouvelles combinaisons
avec les connaissances disponibles pour trouver une nouvelle génération
avec une meilleure valeur de fonction d'aptitude ou objectif.
Algorithme

La procédure de calcul impliquée dans la maximisation de la fonction de fitness F (x1, x2, x3, . . . , x n) dans le génétique
L'algorithme peut être décrit par les étapes suivantes.
1. Choisissez une longueur de chaîne appropriée l = nqto
représenter les n variables de conception du vecteur de conception
X. Supposer des valeurs appropriées pour ce qui suit
parameters: population size m, crossover
probabilité pc, probabilité de mutation pm, permis
valeur de l'écart type des valeurs de condition physique de la
population (sf)maxà utiliser comme critère de convergence,
et le nombre maximum de générations (imaximum) être
utilisé un deuxième critère de convergence.

2. Générer une population aléatoire de taille m,

chacun consistant en une chaîne de longueur l = nq. Évaluer
les valeurs de fitness Fje, i = 1, 2, . . . , m, des m chaînes.

3. Effectuez le processus de reproduction.

4. Effectuer l'opération de croisement en utilisant
la probabilité de croisement pc.

5. Effectuer l'opération de mutation en utilisant la probabilité de mutation pmtrouver la nouvelle génération

de m chaînes.
6. Évaluer les valeurs de fitness Fje, i = 1, 2, . . . , m, des m chaînes de la nouvelle population. Trouvez le
écart type des m valeurs de forme.
7. Testez la convergence de l'algorithme ou du processus. Si sf ≤ (sf)maxle critère de convergence est
satisfait et donc le processus peut être arrêté. Sinon, allez à l'étape 8.
8. Testez le nombre de génération. Si i ≥ imax, les calculs ont été effectués pour le
nombre maximal de générations permis et donc le processus peut être arrêté. Sinon, définissez le
numéro de génération asi = i + 1et aller à l'étape 3.

Applications en temps réel :

Problème du voyageur de commerce (TSP)
2. Problème de routage de véhicules (PRV)
3. Marchés financiers
4. Système de fabrication
Conception en génie mécanique
6. Regroupement et exploitation de données
7. Traitement d'image
8. Réseaux de neurones
9. Réseaux de capteurs sans fil
10. Sciences médicales
3. Avec un diagramme de flux clair, expliquez l'algorithme de l'algorithme des essaims de particules.
Dans la science computationnelle, l'optimisation par essaim de particules (PSO) est une méthode computationnelle qui
optimise un problème en essayant itérativement d'améliorer une solution candidate par rapport à une mesure donnée
de qualité.
PSO est le mieux utilisé pour trouver le maximum ou le minimum d'une fonction définie sur une multidimensionnelle
espace vectoriel.
Comme exemple, considérons le comportement des oiseaux dans un groupe. Bien que chaque oiseau ait un espace limité
L'intelligence par elle-même suit les règles simples suivantes :
Il essaie de ne pas s'approcher trop près des autres oiseaux.
Il se dirige vers la direction moyenne des autres oiseaux.
Il essaie de trouver la "position moyenne" entre les autres oiseaux sans grands écarts dans le groupe.
Ainsi, le comportement du troupeau ou de l'essaim est basé sur une combinaison de trois facteurs simples :
1. Cohésion - rester ensemble.
2. Séparation - ne vous approchez pas trop.
3. Alignement - suivre la direction générale du troupeau.
Le PSO est développé sur la base du modèle suivant :
1. Lorsqu'un oiseau localise une cible ou de la nourriture (ou le maximum de la fonction objective), il instantanément
transmet l'information à tous les autres oiseaux.
2. Tous les autres oiseaux gravitent vers la cible ou la nourriture (ou le maximum de la fonction objective), mais pas directement.
Il y a un élément de la pensée indépendante de chaque oiseau ainsi que de sa mémoire passée. Ainsi, le modèle
simule une recherche aléatoire dans l'espace de conception pour la valeur maximale de la fonction objective. À ce titre,
progressivement au fil de nombreuses itérations, les oiseaux se dirigent vers la cible (ou le maximum de la fonction objective).

Détails de l'algorithme
Supposons que nous avons P particules et que nous notons la position de la particule i à l'itération t comme Xi(t), ce qui
dans l'exemple ci-dessus, nous l'avons comme une coordonnée Xi(t) = (xi(t), yi(t)). En plus de la position, nous avons également un
vitesse pour chaque particule notée sous la forme Vi(t) = (vxi(t), vyi(t)). À l'itération suivante, la position de chaque particule
serait mis à jour comme
Xi(t+1)=Xi(t)+Vi(t+1)
ou, de manière équivalente,

xi(t+1)=xi(t)+vxi(t+1)
yi(t+1)=yi(t)+vyi(t+1)
et en même temps, les vitesses sont également mises à jour selon la règle
Vi(t+1)=wVi(t)+c1r1(pbesti–Xi(t))+c2r2(gbest–Xi(t))
où r1 et r2 sont des nombres aléatoires compris entre 0 et 1, les constantes w, c1 et c2 sont des paramètres de l'ACO
l'algorithme, et pbesti est la position qui donne la meilleure valeur f(X) jamais explorée par la particule i et gbest est
qui a été exploré par toutes les particules dans le nuage.
Notez que pbesti et Xi(t) sont deux vecteurs de position et que la différence pbesti–Xi(t) est une soustraction de vecteurs.
L'ajout de cette soustraction à la vitesse originale Vi(t) permet de ramener la particule à la position pbesti.
Similaires sont pour la différence gbest–Xi(t).

Nous appelons le paramètre w la constante de poids d'inertie. Il se situe entre 0 et 1 et détermine dans quelle mesure
la particule doit-elle continuer avec sa vitesse précédente (c'est-à-dire la vitesse et la direction de la recherche). Le
Les paramètres c1 et c2 sont appelés respectivement les coefficients cognitif et social. Ils contrôlent comment
quel poids devrait être accordé entre le raffinement du résultat de recherche de la particule elle-même et la reconnaissance de
résultat de recherche du essaim. Nous pouvons considérer ces paramètres contrôlant le compromis
entre exploration et exploitation.

Soustraction de vecteurs.
Diagramme par Benjamin D. Esham, domaine public.

Les positions pbesti et gbest sont mises à jour à chaque itération pour refléter la meilleure position trouvée jusqu'à présent.
Une propriété intéressante de cet algorithme qui le distingue des autres algorithmes d'optimisation est qu'il
ne dépend pas du gradient de la fonction objectif. Dans la descente de gradient, par exemple, nous cherchons le
minimum d'une fonction f(X) en déplaçant X dans la direction de− ∇f(X) comme c'est, où la fonction descend
le plus rapide. Pour toute particule à la position X à ce moment, son mouvement ne dépend pas de laquelle
la direction est la "descente" mais seulement là où arepbest et gbest. Cela rend PSO particulièrement adapté si
différencier f(X) est difficile.
Une autre propriété de l'APO est qu'elle peut être facilement parallélisée. Alors que nous manipulons plusieurs particules pour
trouver la solution optimale, chaque particule peut être mise à jour en parallèle et nous n'avons besoin que de collecter les mises à jour
valeur de gbest une fois par itération. Cela fait de l'architecture map-reduce un candidat parfait pour être implémenté
PSO.
Mise en œuvre computationnelle de PSO
Considérez un problème de maximisation sans contrainte : Maximiser f(X) avec X(l) ≤ X ≤ X(u) où X(l) et X
(u) désigne respectivement les bornes inférieure et supérieure de X. La procédure PSO peut être mise en œuvre par
les étapes suivantes.
1. Supposons que la taille du nuage (nombre de particules) soit N. Pour réduire le nombre total de fonctions
des évaluations nécessaires pour trouver une solution, nous devons assumer une taille de nuée plus petite. Mais avec une taille trop petite...
la taille de l'essaim, il est probable que cela prenne plus de temps pour trouver une solution ou, dans certains cas, nous ne pourrons peut-être pas en trouver une
solution à tous. En général, une taille de 20 à 30 particules est supposée pour le nuage en tant que compromis.
2. Generate the initial population of X in the range X (l) and X (u) randomly as X1, X2, . . . , XN . Hereafter,
pour plus de commodité, la position de la particule j et sa vitesse à l'itération i sont notées comme X (i) j et V (i) j,
respectivement. Ainsi, les particules générées initialement sont notées X1(0), X2(0), . . . , XN(0). Les vecteurs Xj(0)(j
= 1, 2, . . . , N ) sont appelés particules ou vecteurs de coordonnées de particules (similaires aux chromosomes dans la génétique
évaluer les valeurs de la fonction objective correspondant aux particules comme
f [X1(0)], f [X2(0)], . . . , f [XN (0)].
3. Trouvez les vitesses des particules. Toutes les particules se déplaceront vers le point optimal avec une vitesse. Au départ,
Toutes les vitesses des particules sont supposées être nulles. Définissez le numéro d'itération comme i = 1.
4. À la ième itération, trouvez les deux paramètres importants suivants utilisés par une particule typique j : (a) Le
meilleure valeur historique de Xj (i) (coordonnées de la jème particule à l’itération actuelle i), Pbest, j, avec la plus élevée
valeur de la fonction objective, f [Xj (i)], rencontrée par la particule j dans toutes les itérations précédentes. Le
meilleure valeur historique de Xj (i) (coordonées de toutes les particules jusqu'à cette itération), Gbest, avec la valeur la plus élevée
de la fonction objective f [Xj (i)], rencontrée dans toutes les itérations précédentes par l'un des N particules. (b)
Trouvez la vitesse de la particule j à la ième itération comme suit :
Vj (i) = Vj (i − 1) + c1r1[Pbest,j − Xj (i − 1)] + c2r2[Gbest − Xj (i − 1)]; j = 1, 2, . . . , N où c1 et c2 sont les
taux d'apprentissage cognitifs (individuels) et sociaux (de groupe), respectivement, et r1 et r2 sont uniformément
nombres aléatoires distribués dans la plage de 0 à 1. Les paramètres c1 et c2 désignent l'importance relative
de la mémoire (position) de la particule elle-même à la mémoire (position) du nuage. Les valeurs de c1 et
c2 est généralement supposé être 2 afin que c1r1 et c2r2 garantissent que les particules survolent la cible
environ la moitié du temps. (c) Trouvez la position ou la coordonnée de la j ième particule lors de la ième itération comme
Xj (i) = Xj (i − 1) + Vj (i); j = 1, 2, . . . , N
où un pas de temps d'unité est supposé dans la vitesse. Évaluer les valeurs de la fonction objective correspondantes
aux particules comme
f [X1(i)], F[X2(i)], . . . , F[XN (i)].
5. Vérifiez la convergence de la solution actuelle. Si les positions de toutes les particules convergent vers le même ensemble
des valeurs, la méthode est supposée avoir convergé. Si le critère de convergence n'est pas satisfait, l'étape 4 est
répété en mettant à jour le numéro d'itération comme i = i + 1, et en calculant les nouvelles valeurs de Pbest,j et
Gbest. Le processus itératif se poursuit jusqu'à ce que toutes les particules convergent vers la même solution optimale.
 Les principaux avantages de l'algorithme PSO sont résumés comme suit : concept simple, facile
mise en œuvre, robustesse aux paramètres de contrôle, et efficacité computationnelle par rapport à
algorithme mathématique et autres techniques d'optimisation heuristique.
L'optimisation par essaims particulaires (PSO) peut être appliquée à divers problèmes d'optimisation, par exemple, l'optimisation du stockage d'énergie.
L'APO peut simuler le mouvement d'un essaim de particules et peut être appliqué dans des effets visuels comme ceux spéciaux.
effets dans le film hollywoodien.

4. Avec un organigramme soigné, expliquez l'algorithme de l'optimisation par colonies de fourmis.

En informatique et en recherche opérationnelle, l'algorithme d'optimisation par colonies de fourmis (ACO) est un
technique probabilistique pour résoudre des problèmes computationnels qui peuvent être réduits à la recherche de bons chemins
à travers des graphiques. Les fourmis artificielles représentent des méthodes multi-agents inspirées du comportement des véritables fourmis.
Ant colony optimization is a probabilistic technique for finding optimal paths. In computer science
et les recherches, l'algorithme d'optimisation par colonies de fourmis est utilisé pour résoudre différents problèmes computationnels
problèmes.
Ils ont un avantage par rapport aux approches de recuit simulé et d'algorithme génétique similaires.
problèmes lorsque le graphe peut changer dynamiquement ; l'algorithme de colonie de fourmis peut être exécuté en continu et
s'adapter aux changements en temps réel.
 Représentation graphique du processus ACO sous la forme d'un réseau multi-couches

Comportement de Recherche des FourmisUne fourmi k, lorsqu'elle se trouve au nœud i, utilise la piste de phéromones τij pour calculer le
probabilité de choisir j comme le prochain nœud :

où α représente le degré d'importance des phéromones et N (k) i indique l'ensemble du voisinage

nodes of ant k when located at node i. The neighborhood of node i contains all the nodes directly connected
au nœud i, j'excepte le nœud prédécesseur (c'est-à-dire, le dernier nœud visité avant i). Cela empêchera la fourmi de
revenant au même nœud visité juste avant le nœud i. Une fourmi se déplace d'un nœud à l'autre jusqu'à ce qu'elle
atteint le nœud de destination (nourriture).
Retrace des chemins et mise à jour des phéromones
Avant de revenir au nœud de départ (nœud arrière), la k-ème fourmi dépose Δτ (k) de phéromone sur les arcs qu'elle
a visité. La valeur de phéromone τij sur l'arc (i, j) parcouru est mise à jour comme suit :

En raison de l'augmentation de la phéromone, la probabilité que cet arc soit sélectionné par les fourmis à venir
va augmenter.
Évaporation de la traînée de phéromones
Lorsqu'une fourmi k se déplace vers le nœud suivant, le phéromone s'évapore de tous les arcs ij selon le
relation

où p∈ (0, 1] est un paramètre et A désigne les segments ou arcs parcourus par l'ant k dans son chemin de retour à la maison.
vers la destination. La diminution de l'intensité des phéromones favorise l'exploration de différents chemins pendant le
processus de recherche. Cela favorise l'élimination des mauvais choix faits dans la sélection du chemin. Cela aide également à
déterminant la valeur maximum atteinte par les traces de phéromones. Une itération est un cycle complet impliquant
le mouvement des fourmis, l'évaporation des phéromones et le dépôt de phéromones.

Algorithme
L'ACO a été utilisé pour résoudre des problèmes de graphes en étudiant les chemins possibles sur les graphes. L'ACO est
inspiré par le comportement des fourmis qui leur permet de trouver le chemin le plus court entre leur nid et la nourriture
ressource par le biais de phéromones. Les fourmis choisissent le chemin le plus court tout en recherchant rapidement des ressources alimentaires dans

progrès du temps.
5. Expliquez l'idée derrière les algorithmes de recherche en harmonie

La méthode de recherche d'harmonie (HS) est un algorithme d'optimisation métaheuristique émergent.

C'est un algorithme métaheuristique inspiré par le processus d'improvisation musicale dans lequel le musicien recherche
la meilleure harmonie et continue de polir l'harmonie afin d'améliorer son esthétique.
Il a été développé par Geem et al. en 2001.
Idéalisons d'abord le processus d'improvisation d'un musicien talentueux. Lorsqu'un musicien improvise, il y a
il y a trois choix possibles :

1. Jouez n'importe quel morceau de musique exactement de mémoire.

Jouer quelque chose de similaire à une pièce connue.

3. Composez de nouvelles notes ou des notes aléatoires.

Geem a formalisé ces trois options en un processus d'optimisation quantitative et les trois correspondants
composants.
Des composants tels que
1.Mémoire d'harmonie (MH)
2. Ajustement de la tonalité

3. La randomisation est introduite.

Le taux de mémoire d'harmonie est similaire au taux de croisement c dans les GA. Afin d'utiliser cette mémoire
effectivement, il est généralement associé à un paramètre appelé taux de mémoire de harmonie (HMCR [0, 1]).
Si ce taux est bas (proche de 0), seules quelques-unes des meilleures harmonies sont utilisées et ainsi la convergence de l'algorithme est lente.
Si ce taux est très élevé (proche de 1), cela entraîne l'exploitation des harmonies dans le HM, ainsi que l'espace de solution.
n'est pas exploré correctement, ce qui conduit à des solutions potentiellement inefficaces.
Le deuxième composant est l'ajustement de la hauteur déterminé par une bande passante de hauteur (BW) (également appelée frette)
largeur [15] ) et un taux de réglage de pas (PAR), cela correspond à générer une solution légèrement différente dans le
Algorithme HS.
La hauteur peut être ajustée de manière linéaire ou non linéaire, mais le plus souvent, un ajustement linéaire est utilisé.
Hjenouveau= Hjeancien+ BW × rjeoù es-tuje∈ [ 1, 1] et 1 ≤ i ≤ D
Où Hje est la ième composante de l'harmonie ou de la solution existante et Hinew est la ième composante de
ancien

nouvelle harmonie après l'action d'ajustement de la hauteur et BW est la bande passante.

Algorithme :
1. Initialisez le problème d'optimisation et les paramètres de l'algorithme.
2. Initialiser la mémoire de harmonie (HM).
3. Improvisation d'une nouvelle harmonie.
4. Mettez à jour le HM
5. Résiliation
HS crée un enfant chaque génération Algorithme :
Jeux : Su-do-ku

Applications de recherche harmonieuse :

Systèmes Énergétiques
 Il y a beaucoup de travail axé sur les problèmes d'optimisation concernant les systèmes de puissance, tels que le coût.
minimisation. Un algorithme HS modifié est proposé pour traiter la répartition de charge économique non convexe de réels-
systèmes de puissance mondiaux. La répartition de charge économique et la répartition combinée de charge économique et d'émission
les problèmes peuvent être convertis en la minimisation de la fonction de coût
Informatique
L'algorithme HS a été récemment appliqué dans de nombreuses applications en informatique et
ingénierie, parmi eux : le regroupement ou clusterisation de pages Web, le résumé ou la synthèse de texte,
Routage Internet et robotique.
Traitement du signal et de l'image :
Li et Duan modifient le HS en ajoutant un facteur gaussien pour ajuster le [Link] ce HS modifié, ils
développer un processus de préentraînement pour sélectionner les poids utilisés dans la combinaison des cartes de caractéristiques pour créer le
cible plus conspicue dans la carte de salience.

HS est une amalgamation d'idées EA précédemment établies, y compris

recombinaison uniforme globale, mutation uniforme, mutation gaussienne, et remplacement des pires
individu chaque génération.

La contribution de HS réside dans deux domaines. Premièrement, la manière dont HS combine ces idées est novatrice. Deuxièmement, le
la motivation musicale de HS est nouvelle.

De plus, la mise en œuvre de l'algorithme HS est également plus facile.

De plus, l'algorithme HS est une métaheuristique basée sur une population, ce qui signifie que plusieurs harmoniques
les groupes peuvent être utilisés en parallèle

6. Expliquez en détail l'algorithme de saut de grenouille mélangé ?

 UNITÉ 4 – OPTIMISATION DANS LA SÉCURITÉ RÉSEAU

PARTIE–A (2 points)
1. Qu'est-ce que l'optimisation dans un réseau dynamique ?

➔ L'optimisation du réseau désigne les outils, les techniques et les meilleures pratiques utilisées pour surveiller et
ameliorer les performances du réseau.
➔ La première étape du processus d'optimisation consiste à mesurer une série de métriques de performance réseau.
et identifier tout problème.
➔ La surveillance des performances du réseau comprend la mesure du trafic, de la bande passante, du jitter et de la latence causée
par des problèmes d'infrastructure insuffisante ou de sécurité réseau inadéquate.
➔ Problèmes d'optimisation de réseaux dynamiques dont les paramètres varient (par exemple, en fonction du temps) et sont
pas statique.
2. Définir le classement

➔ La forme la plus simple de méthode d'évaluation des emplois.

➔ La méthode consiste à classer chaque emploi par rapport à tous les autres emplois, généralement en fonction d'un facteur global.
comme 'difficulté du travail'.

➔ Chaque emploi dans son ensemble est comparé avec d'autres et cette comparaison des emplois se poursuit jusqu'à ce que tous les emplois aient été
a été évalué et classé.
➔ AssetRank a été proposé pour classer tout graphique d'attaque de dépendance en utilisant un modèle de marche aléatoire.
AssetRank est une généralisation de PageRank l'étendant pour gérer à la fois des nœuds conjonctifs et disjonctifs.
AssetRank est soutenu par une interprétation probabiliste sous-jacente basée sur une marche aléatoire.