Recherche aléatoire et recherche de grille pour l'optimisation des fonctions

L'optimisation des fonctions nécessite la sélection d'un algorithme pour échantillonner efficacement l'espace de recherche et localiser une bonne ou la meilleure solution.

Il existe de nombreux algorithmes parmi lesquels choisir, même s’il est important d’établir une base de référence sur les types de solutions réalisables ou possibles pour un problème. Cela peut être réalisé à l'aide d'un algorithme d'optimisation naïf, tel qu'une recherche aléatoire ou une recherche par grille.

Les résultats obtenus par un algorithme d'optimisation naïf sont efficaces sur le plan informatique pour générer et fournir un point de comparaison pour des algorithmes d'optimisation plus sophistiqués. Parfois, les algorithmes naïfs obtiennent les meilleures performances, en particulier sur les problèmes bruyants ou non fluides et sur les problèmes pour lesquels l'expertise du domaine biaise généralement le choix de l'algorithme d'optimisation.

Dans ce tutoriel, vous découvrirez des algorithmes naïfs d'optimisation de fonctions.

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

• Le rôle des algorithmes naïfs dans les projets d’optimisation de fonctions.
• Comment générer et évaluer une recherche aléatoire pour l'optimisation des fonctions.
• Comment générer et évaluer une recherche de grille pour l'optimisation des fonctions.

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. Algorithmes naïfs d’optimisation de fonctions
2. Recherche aléatoire pour l'optimisation des fonctions
3. Recherche de grille pour l'optimisation des fonctions

Algorithmes naïfs d’optimisation de fonctions

Il existe de nombreux algorithmes différents que vous pouvez utiliser pour l’optimisation, mais comment savoir si les résultats que vous obtenez sont bons ?

Une approche pour résoudre ce problème consiste à établir une référence en matière de performances à l’aide d’un algorithme d’optimisation naïf.

Un algorithme d’optimisation naïf est un algorithme qui ne suppose rien sur la fonction objectif à optimiser.

Il peut être appliqué avec très peu d’effort et le meilleur résultat obtenu par l’algorithme peut être utilisé comme point de référence pour comparer des algorithmes plus sophistiqués. Si un algorithme plus sophistiqué ne parvient pas à obtenir un meilleur résultat qu’un algorithme naïf en moyenne, alors il n’a pas les compétences nécessaires pour résoudre votre problème et doit être abandonné.

Il existe deux algorithmes naïfs qui peuvent être utilisés pour l’optimisation des fonctions ; ils sont:

• Recherche aléatoire
• Recherche de grille

Ces algorithmes sont appelés algorithmes de « recherche » car, à la base, l'optimisation peut être présentée comme un problème de recherche. Par ex. trouver les entrées qui minimisent ou maximisent la sortie de la fonction objectif.

Il existe un autre algorithme appelé « recherche exhaustive » qui énumère toutes les entrées possibles. Ceci est rarement utilisé dans la pratique car il n'est pas possible d'énumérer toutes les entrées possibles, par ex. il faudrait trop de temps pour fonctionner.

Néanmoins, si vous travaillez sur un problème d'optimisation pour lequel toutes les entrées peuvent être énumérées et évaluées dans un délai raisonnable, cela devrait être la stratégie par défaut que vous devez utiliser.

Examinons-les de plus près tour à tour.

Recherche aléatoire pour l'optimisation des fonctions

La recherche aléatoire est également appelée optimisation aléatoire ou échantillonnage aléatoire.

La recherche aléatoire implique la génération et l'évaluation d'entrées aléatoires dans la fonction objectif. C’est efficace car cela ne suppose rien sur la structure de la fonction objectif. Cela peut être bénéfique pour les problèmes pour lesquels une grande expertise du domaine peut influencer ou biaiser la stratégie d'optimisation, permettant ainsi de découvrir des solutions non intuitives.

… l’échantillonnage aléatoire, qui prélève simplement m échantillons aléatoires sur l’espace de conception à l’aide d’un générateur de nombres pseudo-aléatoires. Pour générer un échantillon aléatoire x, nous pouvons échantillonner chaque variable indépendamment d'une distribution.

— Page 236, Algorithmes d'optimisation, 2019.

La recherche aléatoire peut également être la meilleure stratégie pour des problèmes très complexes avec des zones bruyantes ou non lisses (discontinues) de l'espace de recherche qui peuvent générer des algorithmes dépendant de gradients fiables.

Nous pouvons générer un échantillon aléatoire à partir d'un domaine en utilisant un générateur de nombres pseudo-aléatoires. Chaque variable nécessite une limite ou une plage bien définie et une valeur uniformément aléatoire peut être échantillonnée dans la plage, puis évaluée.

La génération d'échantillons aléatoires est triviale sur le plan informatique et ne prend pas beaucoup de mémoire. Il peut donc être efficace de générer un large échantillon d'entrées, puis de les évaluer. Chaque échantillon est indépendant, les échantillons peuvent donc être évalués en parallèle si nécessaire pour accélérer le processus.

L'exemple ci-dessous donne un exemple de fonction objectif de minimisation unidimensionnelle simple et génère puis évalue un échantillon aléatoire de 100 entrées. L'entrée avec les meilleures performances est ensuite signalée.

# example of random search for function optimization
from numpy.random import rand

# objective function
def objective(x):
	return x**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# generate a random sample from the domain
sample = r_min + rand(100) * (r_max - r_min)
# evaluate the sample
sample_eval = objective(sample)
# locate the best solution
best_ix = 0
for i in range(len(sample)):
	if sample_eval[i] < sample_eval[best_ix]:
		best_ix = i
# summarize best solution
print('Best: f(%.5f) = %.5f' % (sample[best_ix], sample_eval[best_ix]))

L'exécution de l'exemple génère un échantillon aléatoire de valeurs d'entrée, qui sont ensuite évaluées. Le point le plus performant est ensuite identifié et signalé.

Remarque : Vos résultats peuvent varier en raison de la nature stochastique de l'algorithme ou de la procédure d'évaluation, ou des différences de précision numérique. Pensez à exécuter l’exemple plusieurs fois et comparez le résultat moyen.

Dans ce cas, nous pouvons voir que le résultat est très proche de l’entrée optimale de 0,0.

Best: f(-0.01762) = 0.00031

Nous pouvons mettre à jour l'exemple pour tracer la fonction objectif et montrer l'échantillon et le meilleur résultat. L’exemple complet est répertorié ci-dessous.

# example of random search for function optimization with plot
from numpy import arange
from numpy.random import rand
from matplotlib import pyplot

# objective function
def objective(x):
	return x**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# generate a random sample from the domain
sample = r_min + rand(100) * (r_max - r_min)
# evaluate the sample
sample_eval = objective(sample)
# locate the best solution
best_ix = 0
for i in range(len(sample)):
	if sample_eval[i] < sample_eval[best_ix]:
		best_ix = i
# summarize best solution
print('Best: f(%.5f) = %.5f' % (sample[best_ix], sample_eval[best_ix]))
# sample input range uniformly at 0.1 increments
inputs = arange(r_min, r_max, 0.1)
# compute targets
results = objective(inputs)
# create a line plot of input vs result
pyplot.plot(inputs, results)
# plot the sample
pyplot.scatter(sample, sample_eval)
# draw a vertical line at the best input
pyplot.axvline(x=sample[best_ix], ls='--', color='red')
# show the plot
pyplot.show()

La réexécution de l’exemple génère l’échantillon aléatoire et rapporte le meilleur résultat.

Best: f(0.01934) = 0.00037

Un tracé linéaire est ensuite créé montrant la forme de la fonction objectif, l'échantillon aléatoire et une ligne rouge pour le meilleur résultat localisé à partir de l'échantillon.

Recherche de grille pour l'optimisation des fonctions

La recherche par grille est également appelée échantillonnage par grille ou échantillonnage factoriel complet.

La recherche de grille consiste à générer des entrées de grille uniformes pour une fonction objectif. En une dimension, il s'agirait d'entrées uniformément espacées le long d'une ligne. En deux dimensions, ce serait un réseau de points régulièrement espacés sur la surface, et ainsi de suite pour des dimensions plus élevées.

Le plan d'échantillonnage factoriel complet place une grille de points régulièrement espacés sur l'espace de recherche. Cette approche est facile à mettre en œuvre, ne repose pas sur le hasard et couvre l’espace, mais elle utilise un grand nombre de points.

— Page 235, Algorithmes d'optimisation, 2019.

Comme la recherche aléatoire, une recherche par grille peut être particulièrement efficace sur des problèmes pour lesquels l'expertise du domaine est généralement utilisée pour influencer la sélection d'algorithmes d'optimisation spécifiques. La grille peut aider à identifier rapidement les zones d’un espace de recherche qui pourraient mériter plus d’attention.

La grille d’échantillons est généralement uniforme, même si cela ne doit pas nécessairement être le cas. Par exemple, une échelle log-10 pourrait être utilisée avec un espacement uniforme, permettant d’effectuer un échantillonnage sur plusieurs ordres de grandeur.

L’inconvénient est que la grossièreté de la grille peut enjamber des régions entières de l’espace de recherche où résident les bonnes solutions, un problème qui s’aggrave à mesure que le nombre d’entrées (dimensions de l’espace de recherche) du problème augmente.

Une grille d'échantillons peut être générée en choisissant la séparation uniforme des points, puis en énumérant chaque variable tour à tour et en incrémentant chaque variable de la séparation choisie.

L'exemple ci-dessous donne un exemple de fonction objectif de minimisation bidimensionnelle simple et génère puis évalue un échantillon de grille avec un espacement de 0,1 pour les deux variables d'entrée. L'entrée avec les meilleures performances est ensuite signalée.

# example of grid search for function optimization
from numpy import arange
from numpy.random import rand

# objective function
def objective(x, y):
	return x**2.0 + y**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# generate a grid sample from the domain
sample = list()
step = 0.1
for x in arange(r_min, r_max+step, step):
	for y in arange(r_min, r_max+step, step):
		sample.append([x,y])
# evaluate the sample
sample_eval = [objective(x,y) for x,y in sample]
# locate the best solution
best_ix = 0
for i in range(len(sample)):
	if sample_eval[i] < sample_eval[best_ix]:
		best_ix = i
# summarize best solution
print('Best: f(%.5f,%.5f) = %.5f' % (sample[best_ix][0], sample[best_ix][1], sample_eval[best_ix]))

L'exécution de l'exemple génère une grille de valeurs d'entrée, qui sont ensuite évaluées. Le point le plus performant est ensuite identifié et signalé.

Remarque : Vos résultats peuvent varier en raison de la nature stochastique de l'algorithme ou de la procédure d'évaluation, ou des différences de précision numérique. Pensez à exécuter l’exemple plusieurs fois et comparez le résultat moyen.

Dans ce cas, nous pouvons voir que le résultat trouve exactement les optima.

Best: f(-0.00000,-0.00000) = 0.00000

Nous pouvons mettre à jour l'exemple pour tracer la fonction objectif et montrer l'échantillon et le meilleur résultat. L’exemple complet est répertorié ci-dessous.

# example of grid search for function optimization with plot
from numpy import arange
from numpy import meshgrid
from numpy.random import rand
from matplotlib import pyplot

# objective function
def objective(x, y):
	return x**2.0 + y**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# generate a grid sample from the domain
sample = list()
step = 0.5
for x in arange(r_min, r_max+step, step):
	for y in arange(r_min, r_max+step, step):
		sample.append([x,y])
# evaluate the sample
sample_eval = [objective(x,y) for x,y in sample]
# locate the best solution
best_ix = 0
for i in range(len(sample)):
	if sample_eval[i] < sample_eval[best_ix]:
		best_ix = i
# summarize best solution
print('Best: f(%.5f,%.5f) = %.5f' % (sample[best_ix][0], sample[best_ix][1], sample_eval[best_ix]))
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a filled contour plot
pyplot.contourf(x, y, results, levels=50, cmap='jet')
# plot the sample as black circles
pyplot.plot([x for x,_ in sample], [y for _,y in sample], '.', color='black')
# draw the best result as a white star
pyplot.plot(sample[best_ix][0], sample[best_ix][1], '*', color='white')
# show the plot
pyplot.show()

La réexécution de l’exemple génère l’échantillon de grille et rapporte le meilleur résultat.

Best: f(0.00000,0.00000) = 0.00000

Un tracé de contour est ensuite créé montrant la forme de la fonction objectif, l'échantillon de grille sous forme de points noirs et une étoile blanche pour le meilleur résultat localisé à partir de l'échantillon.

Notez que certains des points noirs pour la limite du domaine semblent être hors du tracé ; ce n'est qu'un artefact sur la façon dont nous choisissons de dessiner les points (par exemple non centrés sur l'échantillon).

Lectures complémentaires

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

Livres

• Algorithmes d'optimisation, 2019.

Articles

• Recherche aléatoire, Wikipédia.
• Optimisation des hyperparamètres, Wikipédia.
• Recherche par force brute, Wikipédia.

Résumé

Dans ce didacticiel, vous avez découvert des algorithmes naïfs d'optimisation de fonctions.

Concrètement, vous avez appris :

• Le rôle des algorithmes naïfs dans les projets d’optimisation de fonctions.
• Comment générer et évaluer une recherche aléatoire pour l'optimisation des fonctions.
• Comment générer et évaluer une recherche de grille pour l'optimisation des fonctions.

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