Optimisation des fonctions avec SciPy

L'optimisation consiste à trouver les entrées d'une fonction objectif qui aboutissent au résultat minimum ou maximum de la fonction.

La bibliothèque Python open source pour le calcul scientifique appelée SciPy fournit une suite d'algorithmes d'optimisation. De nombreux algorithmes sont utilisés comme élément de base dans d’autres algorithmes, notamment les algorithmes d’apprentissage automatique de la bibliothèque scikit-learn.

Ces algorithmes d'optimisation peuvent être utilisés directement de manière autonome pour optimiser une fonction. Plus particulièrement, les algorithmes de recherche locale et les algorithmes de recherche globale, les deux principaux types d'optimisation que vous pouvez rencontrer sur un projet de machine learning.

Dans ce tutoriel, vous découvrirez les algorithmes d'optimisation fournis par la bibliothèque SciPy.

Après avoir terminé ce tutoriel, vous saurez :

• La bibliothèque SciPy fournit une suite de différents algorithmes d'optimisation à des fins différentes.
• Les algorithmes d'optimisation de recherche locale disponibles dans SciPy.
• Les algorithmes globaux d'optimisation de la recherche disponibles dans SciPy.

Démarrez votre projet avec mon nouveau livre Optimization for Machine Learning, comprenant des tutoriels pas à pas et les fichiers code source Python pour tous exemples.

Présentation du didacticiel

Ce didacticiel est divisé en trois parties : ils sont:

1. Optimisation avec SciPy
2. Recherche locale avec SciPy
3. Recherche globale avec SciPy

Optimisation avec SciPy

La bibliothèque open source Python SciPy pour le calcul scientifique fournit une suite de techniques d'optimisation.

De nombreux algorithmes sont utilisés comme éléments de base pour d'autres algorithmes de la bibliothèque SciPy, ainsi que pour des bibliothèques d'apprentissage automatique telles que scikit-learn.

Avant d’examiner des techniques spécifiques, examinons les types d’algorithmes fournis par la bibliothèque.

Ils sont:

• Optimisation scalaire : Optimisation d'une fonction convexe à variable unique.
• Recherche Locale : Optimisation d'une fonction unimodale à variables multiples.
• Global Search : Optimisation d'une fonction multimodale à variables multiples.
• Moins carrés : résolvez des problèmes de moindres carrés linéaires et non linéaires.
• Ajustement de courbe : ajustez une courbe à un échantillon de données.
• Recherche de racine : recherchez la racine (entrée qui donne une sortie de zéro) d'une fonction.
• Programmation Linéaire : Optimisation linéaire soumise à contraintes.

Tous les algorithmes supposent que la fonction objectif optimisée est une fonction de minimisation. Si votre fonction maximise, elle peut être convertie en minimisation en ajoutant un signe négatif aux valeurs renvoyées par votre fonction objectif.

En plus de la liste ci-dessus, la bibliothèque fournit également des fonctions utilitaires utilisées par certains algorithmes, ainsi que le problème de test de Rosenbrock.

Pour un bon aperçu des capacités d'optimisation de la bibliothèque SciPy, voir :

• API d'optimisation et de recherche de racine (scipy.optimize).

Maintenant que nous avons une idée générale des types de techniques d'optimisation prises en charge par la bibliothèque, examinons de plus près deux groupes d'algorithmes que nous sommes plus susceptibles d'utiliser dans l'apprentissage automatique appliqué. Il s’agit de la recherche locale et de la recherche globale.

Recherche locale avec SciPy

La recherche locale, ou optimisation de fonction locale, fait référence à des algorithmes qui recherchent l'entrée d'une fonction qui aboutit à la sortie minimale ou maximale où la fonction ou la région contrainte recherchée est supposée avoir un seul optimal, par ex. unimodal.

La fonction en cours d'optimisation peut être convexe ou non et peut avoir une ou plusieurs variables d'entrée.

Une optimisation de recherche locale peut être appliquée directement pour optimiser une fonction si l'on pense ou sait que la fonction est unimodale ; sinon, l'algorithme de recherche locale peut être appliqué pour affiner le résultat d'un algorithme de recherche global.

La bibliothèque SciPy propose une recherche locale via la fonction minimiser().

La fonction minimize() prend en entrée le nom de la fonction objectif qui est minimisée et le point initial à partir duquel démarrer la recherche et renvoie un OptimizeResult qui résume le succès ou l'échec de la recherche et le détails de la solution si elle est trouvée.

...
# minimize an objective function
result = minimize(objective, point)

Des informations supplémentaires sur la fonction objectif peuvent être fournies si elles sont connues, comme les limites des variables d'entrée, une fonction de calcul de la dérivée première de la fonction (gradient ou matrice jacobienne), une fonction de calcul de la dérivée seconde de la fonction (matrice hessienne). matrice) et les éventuelles contraintes sur les entrées.

Surtout, la fonction fournit l'argument « method » qui permet de spécifier l'optimisation spécifique utilisée dans la recherche locale.

Une suite d'algorithmes de recherche locale populaires est disponible, tels que :

• Algorithme de Nelder-Mead (méthode='Nelder-Mead').
• Méthode de Newton (méthode=’Newton-CG’).
• Méthode de Powell (méthode=’Powell’).
• Algorithme BFGS et extensions (méthode=’BFGS’).

L'exemple ci-dessous montre comment résoudre une fonction convexe bidimensionnelle à l'aide de l'algorithme de recherche locale L-BFGS-B.

# l-bfgs-b algorithm local optimization of a convex function
from scipy.optimize import minimize
from numpy.random import rand

# objective function
def objective(x):
	return x[0]**2.0 + x[1]**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# define the starting point as a random sample from the domain
pt = r_min + rand(2) * (r_max - r_min)
# perform the l-bfgs-b algorithm search
result = minimize(objective, pt, method='L-BFGS-B')
# summarize the result
print('Status : %s' % result['message'])
print('Total Evaluations: %d' % result['nfev'])
# evaluate solution
solution = result['x']
evaluation = objective(solution)
print('Solution: f(%s) = %.5f' % (solution, evaluation))

L’exécution de l’exemple effectue l’optimisation et signale le succès ou l’échec de la recherche, le nombre d’évaluations de fonction effectuées et l’entrée qui a abouti aux optima de la fonction.

Status : b'CONVERGENCE: NORM_OF_PROJECTED_GRADIENT_<=_PGTOL'
Total Evaluations: 9
Solution: f([3.38059583e-07 3.70089258e-07]) = 0.00000

Maintenant que nous sommes familiarisés avec l’utilisation d’un algorithme de recherche locale avec SciPy, examinons la recherche globale.

Recherche globale avec SciPy

La recherche globale ou l'optimisation globale des fonctions fait référence à des algorithmes qui recherchent l'entrée d'une fonction qui aboutit à la sortie minimale ou maximale où la fonction ou la région contrainte recherchée est supposée avoir plusieurs optima locaux, par ex. multimodal.

La fonction en cours d'optimisation est généralement non linéaire, non convexe et peut avoir une ou plusieurs variables d'entrée.

Les algorithmes de recherche globale sont généralement stochastiques, ce qui signifie qu'ils utilisent le caractère aléatoire dans le processus de recherche et peuvent ou non gérer une population de solutions candidates dans le cadre de la recherche.

La bibliothèque SciPy fournit un certain nombre d'algorithmes d'optimisation globale stochastique, chacun via des fonctions différentes. Ils sont:

• Optimisation du Basin Hopping via la fonction Basinhopping().
• Optimisation de l'évolution différentielle via la fonction différentiel_evolution().
• Recuit simulé via la fonction dual_annealing().

La bibliothèque fournit également la fonction shgo() pour l'optimisation des séquences et la fonction brute() pour l'optimisation de la recherche sur la grille.

Chaque algorithme renvoie un objet OptimizeResult qui résume le succès ou l'échec de la recherche et les détails de la solution si elle est trouvée.

L'exemple ci-dessous montre comment résoudre une fonction multimodale bidimensionnelle à l'aide du recuit simulé.

# simulated annealing global optimization for a multimodal objective function
from scipy.optimize import dual_annealing

# objective function
def objective(v):
	x, y = v
	return (x**2 + y - 11)**2 + (x + y**2 -7)**2

# define range for input
r_min, r_max = -5.0, 5.0
# define the bounds on the search
bounds = [[r_min, r_max], [r_min, r_max]]
# perform the simulated annealing search
result = dual_annealing(objective, bounds)
# summarize the result
print('Status : %s' % result['message'])
print('Total Evaluations: %d' % result['nfev'])
# evaluate solution
solution = result['x']
evaluation = objective(solution)
print('Solution: f(%s) = %.5f' % (solution, evaluation))

L’exécution de l’exemple effectue l’optimisation et signale le succès ou l’échec de la recherche, le nombre d’évaluations de fonction effectuées et l’entrée qui a abouti aux optima de la fonction.

Status : ['Maximum number of iteration reached']
Total Evaluations: 4028
Solution: f([-3.77931027 -3.283186 ]) = 0.00000

Lectures complémentaires

Cette section fournit plus de ressources sur le sujet si vous souhaitez approfondir.

Apis

• API d'optimisation (scipy.optimize).
• API d'optimisation et de recherche de racine (scipy.optimize).

Articles

• Recherche locale (optimisation), Wikipédia.
• Optimisation globale, Wikipédia.

Résumé

Dans ce tutoriel, vous avez découvert les algorithmes d'optimisation fournis par la bibliothèque SciPy.

Concrètement, vous avez appris :

• La bibliothèque SciPy fournit une suite de différents algorithmes d'optimisation à des fins différentes.
• Les algorithmes d'optimisation de recherche locale disponibles dans SciPy.
• Les algorithmes globaux d'optimisation de la recherche disponibles dans SciPy.

Avez-vous des questions ?
Posez vos questions dans les commentaires ci-dessous et je ferai de mon mieux pour y répondre.