Méthodes d'Optimisation
Cours Complet sur les Méthodes d'Optimisation
Introduction
Les méthodes d'optimisation sont utilisées pour trouver les meilleures solutions possibles à des problèmes mathématiques complexes, souvent en minimisant ou maximisant une fonction objectif sous certaines contraintes. Ces méthodes sont essentielles dans divers domaines tels que l'ingénierie, l'économie, et les sciences de données. Nous allons explorer trois grandes catégories de méthodes d'optimisation : l'optimisation linéaire, l'optimisation non linéaire et les méthodes heuristiques.
Optimisation Linéaire
L'optimisation linéaire (ou programmation linéaire) consiste à maximiser ou minimiser une fonction linéaire sous des contraintes linéaires.
Formulation du Problème
Un problème d'optimisation linéaire est généralement formulé comme suit :
Maximiser ou Minimiser
Un problème d'optimisation linéaire est généralement formulé comme suit :
Maximiser ou Minimiser :
c^T * x
Sous les contraintes :
A * x ≤ b
x ≥ 0
où :
- c est un vecteur de coefficients de la fonction objectif,
- A est une matrice des coefficients des contraintes,
- b est un vecteur des termes constants des contraintes,
- x est le vecteur des variables de décision.
L'objectif est de trouver la meilleure valeur possible pour x tout en respectant les contraintes imposées par A et b.
Exemple de Vulgarisation
Histoire : Imagine que tu es un agriculteur qui doit décider combien de tonnes de blé et de maïs planter pour maximiser ses profits, tout en respectant les limites de surface cultivable et les ressources en eau disponibles.
Exemple en JavaScript avec glpk.js
const glpk = require('glpk.js');
const lp = {
name: "Agriculture",
objective: {
direction: glpk.GLP_MAX,
name: "profit",
vars: [
{ name: "blé", coef: 30 },
{ name: "maïs", coef: 20 }
]
},
subjectTo: [
{
name: "surface",
vars: [
{ name: "blé", coef: 1 },
{ name: "maïs", coef: 1 }
],
bnds: { type: glpk.GLP_UP, ub: 50 }
},
{
name: "eau",
vars: [
{ name: "blé", coef: 2 },
{ name: "maïs", coef: 1 }
],
bnds: { type: glpk.GLP_UP, ub: 80 }
}
],
bounds: [
{ name: "blé", bnds: { type: glpk.GLP_LO, lb: 0 } },
{ name: "maïs", bnds: { type: glpk.GLP_LO, lb: 0 } }
]
};
glpk.solve(lp, function(err, solution) {
if (err) throw err;
console.log('Optimal solution:', solution.result);
console.log('Values:', solution.vars);
});
Optimisation Non Linéaire
L'optimisation non linéaire traite des problèmes où la fonction objectif ou les contraintes sont non linéaires.
Formulation du Problème
Exemple de Vulgarisation
Histoire : Imagine que tu dois concevoir une canette de boisson qui minimise le coût de production tout en respectant des contraintes de volume et de matériau.
Exemple en JavaScript avec math.js
const math = require('mathjs');
function objective(x) {
return x[0]**2 + x[1]**2 + x[0]*x[1];
}
function constraint1(x) {
return x[0] + x[1] - 10; // x1 + x2 <= 10
}
function gradientDescent(f, grad, start, learningRate, tolerance, maxIterations) {
let x = start.slice();
for (let i = 0; i < maxIterations; i++) {
const gradVal = grad(x);
const newX = math.subtract(x, math.multiply(learningRate, gradVal));
if (math.norm(math.subtract(newX, x)) < tolerance) {
return newX;
}
x = newX;
}
return x;
}
function grad(x) {
return [
2*x[0] + x[1],
2*x[1] + x[0]
];
}
const start = [1, 1];
const learningRate = 0.1;
const tolerance = 1e-6;
const maxIterations = 1000;
const result = gradientDescent(objective, grad, start, learningRate, tolerance, maxIterations);
console.log('Optimal solution:', result);
console.log('Objective value:', objective(result));
Méthodes Heuristiques
Les méthodes heuristiques sont utilisées pour trouver des solutions approximatives à des problèmes complexes pour lesquels les méthodes exactes sont impraticables. Nous discuterons de deux méthodes populaires : le recuit simulé et les algorithmes génétiques.
Recuit Simulé
Le recuit simulé est une méthode d'optimisation inspirée du processus de recuit en métallurgie. Il cherche à éviter les minima locaux en acceptant des solutions moins bonnes avec une certaine probabilité.
Exemple de Vulgarisation
Histoire : Imagine que tu es un randonneur essayant de trouver le chemin le plus court vers le sommet d'une montagne. Parfois, tu dois descendre légèrement pour trouver un chemin plus direct vers le sommet.
Exemple en JavaScript
function simulatedAnnealing(objective, initialSolution, temp, coolingRate, maxIterations) {
let currentSolution = initialSolution.slice();
let bestSolution = currentSolution.slice();
let currentObjective = objective(currentSolution);
let bestObjective = currentObjective;
for (let i = 0; i < maxIterations; i++) {
const newSolution = currentSolution.map(x => x + (Math.random() - 0.5) * temp);
const newObjective = objective(newSolution);
if (newObjective < currentObjective || Math.random() < Math.exp((currentObjective - newObjective) / temp)) {
currentSolution = newSolution.slice();
currentObjective = newObjective;
}
if (currentObjective < bestObjective) {
bestSolution = currentSolution.slice();
bestObjective = currentObjective;
}
temp *= coolingRate;
}
return bestSolution;
}
function objective(x) {
return x[0]**2 + x[1]**2; // Simple quadratic objective function
}
const initialSolution = [5, 5];
const temp = 1000;
const coolingRate = 0.99;
const maxIterations = 1000;
const bestSolution = simulatedAnnealing(objective, initialSolution, temp, coolingRate, maxIterations);
console.log('Optimal solution:', bestSolution);
console.log('Objective value:', objective(bestSolution));
Algorithmes Génétiques
Les algorithmes génétiques sont des méthodes d'optimisation inspirées par la théorie de l'évolution de Darwin. Ils utilisent des mécanismes tels que la sélection, le croisement et la mutation pour évoluer vers des solutions optimales.
Exemple de Vulgarisation
Histoire : Imagine que tu es un jardinier essayant de créer la plus belle fleur possible en croisant différentes variétés et en sélectionnant les meilleures caractéristiques de chaque génération.
Exemple en JavaScript
function geneticAlgorithm(objective, bounds, populationSize, generations, crossoverRate, mutationRate) {
function randomSolution() {
return bounds.map(([low, high]) => low + Math.random() * (high - low));
}
function crossover(parent1, parent2) {
return parent1.map((gene, index) => Math.random() < 0.5 ? gene : parent2[index]);
}
function mutate(solution) {
return solution.map((gene, index) => Math.random() < mutationRate ? bounds[index][0] + Math.random() * (bounds[index][1] - bounds[index][0]) : gene);
}
let population = Array.from({ length: populationSize }, randomSolution);
let bestSolution = population[0];
let bestObjective = objective(bestSolution);
for (let generation = 0; generation < generations; generation++) {
population = population.map(solution => mutate(crossover(solution, population[Math.floor(Math.random() * populationSize)])));
population.forEach(solution => {
const currentObjective = objective(solution);
if (currentObjective < bestObjective) {
bestSolution = solution;
bestObjective = currentObjective;
}
});
}
return bestSolution;
}
function objective(x) {
return x[0]**2 + x[1]**2; // Simple quadratic objective function
}
const bounds = [[-10, 10], [-10, 10]];
const populationSize = 50;
const generations = 100;
const crossoverRate = 0.9;
const mutationRate = 0.01;
const bestSolution = geneticAlgorithm(objective, bounds, populationSize, generations, crossoverRate, mutationRate);
console.log('Optimal solution:', bestSolution);
console.log('Objective value:', objective(bestSolution));
Conclusion
Les méthodes d'optimisation sont essentielles pour résoudre des problèmes complexes dans divers domaines. L'optimisation linéaire et non linéaire traite des problèmes où les fonctions et les contraintes sont respectivement linéaires et non linéaires. Les méthodes heuristiques, telles que le recuit simulé et les algorithmes génétiques, offrent des solutions approximatives à des problèmes où les méthodes exactes sont impraticables. En comprenant et en appliquant ces méthodes, nous pouvons aborder efficacement une variété de défis d'optimisation.