FR/Calc/NLPSolver

Introduction

Optimisation

De nombreux problèmes scientifiques et économiques se ramènent à la recherche d'un optimum parmi les valeurs définies par un ensemble de formules, que ce soit le maximum ou le minimum. Il y a également souvent des contraintes additionnelles qui restreignent l'étendue des solutions possibles. Par exemple, minimiser les coûts d'une société tout en continuant de répondre à la demande de ses clients.

Une telle formule pourrait ressembler à : [math]\displaystyle{ c = p_1 \cdot x_1 + p_2 \cdot x_2 }[/math]où [math]\displaystyle{ p_1 }[/math] et [math]\displaystyle{ p_2 }[/math] représentent les prix de deux produits et [math]\displaystyle{ x_1 }[/math] et [math]\displaystyle{ x_2 }[/math] sont les quantités à produire. Ce serait un problème typique d'optimisation linéaire, dans la mesure où le coût à minimiser dépend linéairement des variables cibles ([math]\displaystyle{ x_1 }[/math] et [math]\displaystyle{ x_2 }[/math]). Un problème non linéaire d'un autre côté introduirait des relations bien plus compliquées entre les variables. Un exemple de ces relations est la fonction de Rosenbrock : [math]\displaystyle{ f(x,y) = (1-x)^2 + 100 \cdot (y - x^2) }[/math]

En pratique l'optimisation non linéaire est utilisée pour l'ajustement de courbe à des données observées (en minimisant une fonction d'erreur) ou pour des relations économiques plus compliquées.

Classeurs - Calc

Dans la mesure où les problèmes d'optimisation consistent en plusieurs variables et beaucoup de relations différentes entre elles, ils peuvent être modélisés dans une feuille de calcul et donc permettre une interaction facilitée pour l'utilisateur. Il est alors utile d'avoir un outil incorporé permettant de résoudre un tel modèle.

Dans Calc, il y avait par défaut un solveur linéaire et pour outrepasser cette limitation, l'extension NLP Solver peut être utilisée afin d'ajouter des solveurs qui sont également capables de prendre en charge des problèmes non linéaires (tout autant que des linéaires).

Quand l'utiliser ?

Dans la mesure où le NLPSolver peut à la fois prendre en charge les problèmes linéaires et non linéaires, vous pourriez vous demander pourquoi il est nécessaire d'avoir encore le solveur linéaire. La réponse est facile : les performances.

Résoudre des problèmes non linéaires est un lourd fardeau et constitue toujours un champ de recherche actif en mathématiques. Il n'y a pas tant de solutions. Très souvent, il est nécessaire de connaître précisément le problème à résoudre et de choisir la méthode appropriée ainsi que ses paramètres en fonction de cette connaissance.

Puisque la représentation de modèles d'optimisation dans un classeur ne peut pas être analysée en profondeur, le solveur doit être capable de prendre en charge un large spectre de problèmes d'optimisation. Un autre problème est que de nombreux algorithmes ont tendance à se coincer dans les extremums locaux. Cela signifie que la solution qu'ils trouvent peut ne pas être la meilleure solution globale. Une catégorie d'algorithmes qui solutionnent ces deux problèmes sont ceux qui se fondent sur des stratégies évolutionnaires mais elles sont lentes en comparaison de l'approche déterministe du solveur linéaire.

Stratégies évolutives

Dans la nature, il n'y a pas tant d'analyse, mais les choses "fonctionnent" à travers un système complexe de comportements et d'événements. Avec le temps, les colonies de fourmis construisent des routes très courtes pour transporter la nourriture jusqu'à leur fourmilière - juste par instinct. Les colonies d'oiseaux restent ensemble et suivent leur chef dans une même formation. Une simple modification dans l'esprit des chefs influence le comportement de tous les oiseaux de la colonie. De la même façon, la population humaine est influencée par le savoir de chacun. Les gens parlent, partagent l'information et forment leur propre jugement sur ce qu'ils ont appris, lu ou entendu.

Plusieurs personnes ont eu l'idée d'utiliser ces principes pour résoudre des problèmes numériques et combinatoires. C'est également l'approche que le NLPSolver a adoptée pour résoudre des problèmes d'optimisation non linéaire. La solution est trouvée en réutilisant la solution vers un optimum (global), et qui est réalisé par des "essais structurés et des erreurs". En utilisant des modifications aléatoires, il devient possible de trouver un optimum global au lieu de rester coincé sur un optimum local. La façon dont le problème est structuré n'a également pas beaucoup d'importance dans la mesure où le solveur va s'adapter automatiquement en apprenant. Le plus grand inconvénient de cette approche est qu'il doit évaluer l'ensemble du modèle d'optimisation de nombreuses fois pour trouver la solution, ce qui prend beaucoup de temps et est donc plutôt lent.

Solveurs

DEPS - Differential Evolution & Particle Swarm Optimization

DEPS consiste en deux algorithmes indépendants : Évolution différentielle et Optimisation par essaims de particules. Tous deux sont particulièrement adaptés aux problèmes numériques tels que l'optimisation non linéaire et sont complémentaires l'un de l'autre dans la mesure où ils comblent leurs lacunes respectives.

L'idée derrière l'Optimisation par essaims de particules est de représenter tous les vecteurs de solution comme des coordonnées dans un espace à n dimensions. Chaque individu (particule) traverse cet espace et garde la trace de son propre meilleur point. Cette information ainsi que la connaissance de la particule ayant la solution actuelle la meilleure influence la façon dont elle va bouger à chaque itération. En fonction de cela, les particules vont toujours essayer de construire un essaim et tourner autour des meilleurs solutions, traversant même de meilleures solutions sur son chemin.

L'évolution différentielle d'un autre côté est une stratégie pour "recombiner" deux individus, similaire aux algorithmes génétiques. Au lieu de croiser des chromosomes (i.e. mélanger leurs variables), la connaissance de la fonction cible est utilisée pour réutiliser les deux points. À chaque itération de l'algorithme, chaque individu choisit l'une des deux stratégies et les applique à son vecteur de solution actuel. La probabilité de changer de stratégie peut être modifiée avec l'option Taux d'échange de l'agent.

SCO - Social Cognitive Optimization

SCO prend en compte le comportement humain d'apprentissage et de partage de l'information. Chaque individu a accès à une bibliothèque commune avec un partage de la connaissance entre tous les individus. À chaque étape, un individu recherche la (vraisemblablement) meilleure information disponible dans la bibliothèque et construit une décision basée sur elle, en même temps que sa propre connaissance du problème.

Ensuite, il remplace les informations les plus mauvaises dans la bibliothèque par la solution nouvellement apprise. De cette manière, tous les individus travaillent ensemble (l'aspect social) et prennent leur décision (l'aspect cognitif). C'est pour cela que cette méthode est appelée Optimisation cognitive sociale.

Utilisation

Que vous utilisiez DEPS ou SCO, vous commencez par vous rendre sous Outils > Solveur et définissez la cellule devant être optimisée, la direction dans laquelle aller (minimisation, maximisation) et les cellules à modifier pour atteindre le but. Puis vous allez dans les options, spécifiez le solveur à utiliser et si nécessaire ajustez les paramètres correspondants.

Il y a également une liste de contraintes que vous pouvez utiliser pour restreindre la plage possible de solutions pour pénaliser certaines conditions. Cependant, dans le cas des solveurs évolutifs DEPS et SCO, ces contraintes sont aussi utilisées pour spécifier des limites aux variables du problème. En raison de la nature aléatoire des algorithmes, il est fortement recommandé d'opérer ainsi et de donner des limites supérieures (et si "Supposer des variables non négatives" est désactivé, également des limites inférieures) à toutes les variables.

Elles n'ont pas à être proches de la solution réelle (qui est probablement inconnue) mais doivent donner une grossière indication de la taille attendue ([math]\displaystyle{ 0 \leq \text{var} \leq 1 }[/math] ou peut-être [math]\displaystyle{ -1000000 \leq \text{var} \leq 1000000 }[/math]). Les limites sont spécifiées en sélectionnant une ou plusieurs variables (comme plage) sur le côté gauche et en saisissant une valeur numérique (non une cellule ou une formule) sur la droite. De cette façon, vous pouvez également forcer certaines variables comme Entier ou Logique (binaire) uniquement.

Options et paramètres

Options générales

Taille de l'essaim	... définit le nombre d'individus qui participent au processus d'apprentissage. Chaque individu trouve ses propres solutions et contribue à la connaissance générale.
Cycles d'apprentissage	... définit le nombre d'itérations que l'algorithme doit exécuter. À chaque itération, tous les individus font une estimation de la meilleure solution et partagent leur savoir.
Estimation des limites des variables	... Si activé (comportement par défaut), l'algorithme essaie de trouver les limites des variables en utilisant les valeurs de départ.
Seuil de limites des variables	Lors de l'estimation des limites de variables, ce seuil spécifie comment les valeurs initiales sont modifiées pour construire les limites. Le calcul est le suivant : [math]\displaystyle{ \text{Limite} = \text{ValeurInitiale} \pm(\text{Seuil} \cdot \text{ValeurInitiale}) }[/math]. Exemple: La [math]\displaystyle{ \text{ValeurInitiale} }[/math] est [math]\displaystyle{ 100 }[/math] et le [math]\displaystyle{ \text{Seuil} }[/math] est [math]\displaystyle{ 3 }[/math] (par défaut). Dans ce cas, la limite inférieure serait [math]\displaystyle{ 100 - 3 \cdot 100 = -200 }[/math] et la limite supérieure [math]\displaystyle{ 100 + 3 \cdot 100 = 400 }[/math].
Utiliser le comparateur ACR	Si désactivé (par défaut), le comparateur BCH est utilisé. Il compare deux individus en regardant d'abord leurs violations de contrainte et seulement si elles sont égales, il mesure leur solution actuelle. Si activée le comparateur ACR est utilisé. Il compare deux individus en fonction de l'itération actuelle et mesure leur capacité à connaître les bibliothèques des pires solutions connues (en ce qui concerne leurs violations de contrainte).
Utiliser un point de départ aléatoire	Si activé, la bibliothèque est simplement remplie avec des points choisis aléatoirement. Si désactivé, les valeurs présentes actuellement (telles que données par l'utilisateur) sont insérées dans la bibliothèque comme point de référence.
Limite de stagnation	Si ce nombre d'individus trouve des solutions dans une plage close, l'itération est arrêtée et la meilleure de ces valeurs est choisie comme optimale.
Tolérance de stagnation	Définit dans quelle plage les solutions sont considérées comme similaires.
Afficher le statut étendu du solveur	Si activé, une boîte de dialogue supplémentaire est affichée pendant le processus de résolution, donnant des informations sur le processus en cours, le niveau de stagnation, la meilleure solution actuelle connue ainsi que la possibilité d'arrêter ou de relancer le solveur.

Options spécifiques DEPS

Taux de changement de l'agent	Spécifie la probabilité pour un individu de choisir la stratégie d'évolution différentielle.
DE : Probabilité de croisement	... définit la probabilité pour un individu d'être combiné avec le meilleur point global. Si le croisement n'est pas utilisé, le point est assemblé à partir de la mémoire propre à l'individu.
DE : Facteur d'échelle	Pendant le croisement, le facteur d'échelle décide de la "rapidité" du mouvement.
PS : Coefficient de réduction	... définit la vitesse à laquelle les particules/individus se déplacent les uns entre les autres.
PS : constante cognitive	... définit l'importance de la mémoire propre (en particulier le meilleur point atteint).
PS : constante sociale	... définit l'importance du meilleur point global entre toutes les particules/individus.
PS : probabilité de mutation	... définit la probabilité que, au lieu de déplacer une coordonnée de la particule vers le meilleur point, il choisit une nouvelle valeur au hasard dans la plage valide pour cette variable.

Options spécifiques SCO

Taille de la bibliothèque

... Définit la somme d'informations à stocker dans la bibliothèque publique. Chaque individu stocke son savoir ici et demande des informations.

Scripting

Il y a un certain nombre de raisons pour lesquelles il peut être utile d'atteindre le solveur à travers un langage de script (comme le Basic LibreOffice). L'une d'elles pourrait être que vous ne voulez pas spécifier toutes les contraintes à chaque fois que vous voulez exécuter le solveur sur un problème spécifique. Dans ce cas, vous pouvez gérer les paramètres du solveur à partir du Basic.

Propriétés et méthodes

À part pour les propriétés et les méthodes par défaut définies par l'interface XSolver, DEPS et SCO publient les propriétés suivantes :

Propriété	Type	Signification
SwarmSize	Integer	Taille de Swarm
LearningCycles	Integer	Cycles d'apprentissage
GuessVariableRange	Boolean	Supposition de la plage de variables
VariableRangeThreshold	Double	Seuil de la plage de variables
UseACRComparator	Boolean	Utiliser le comparateur ACR
UseRandomStartingPoint	Boolean	Utiliser un point de départ aléatoire
StagnationLimit	Integer	Limite de stagnation
Tolerance	Double	Tolérance de stagnation
EnhancedSolverStatus	Boolean	Afficher les statuts étendus du solveur
com.sun.star.comp.Calc.NLPSolver.DEPSSolverImpl
AgentSwitchRate	Double	Taux de changement de l'agent
DEFactor	Double	Facteur d'échelle
DECR	Double	Probabilité de croisement
PSC1	Double	Constante cognitive
PSC2	Double	Constante sociale
PSWeight	Double	Coefficient de réduction
PSCL	Double	Probabilité de mutation
com.sun.star.comp.Calc.NLPSolver.SCOSolverImpl
LibrarySize	Integer	Taille de la librairie

Exemple

L'exemple suivant va créer une itération de la ligne 5 à 300 (la numérotation interne démarre à 0 !) pour la feuille 1 et les résout chacune séparément en minimisant l'objectif dans la même ligne.

Sub OptimizeDEPS 
  Dim Solver as Object
  Set Solver = CreateUnoService("com.sun.star.comp.Calc.NLPSolver.DEPSSolverImpl")
  Solver.Document = ThisComponent
  Solver.Maximize = false

  Dim ObjectiveCell as new com.sun.star.table.CellAddress
  ObjectiveCell.Sheet = 0
  ObjectiveCell.Column = 10 

  Dim VariableCells(0) as new com.sun.star.table.CellAddress
  VariableCells(0).Sheet = 0  VariableCells(0).Column = 2

  For TargetRow = 4 To 299
    ObjectiveCell.Row = TargetRow
    VariableCells(0).Row = TargetRow
    Solver.Objective = ObjectiveCell
    Solver.Variables = VariableCells
    Solver.solve

  Next
    MsgBox "Terminé."

End Sub

License and Disclaimer

This extension has been developed at Sun Microsystems Inc. and is licensed under the terms of the GNU Lesser General Public License version 3.Research and implementation of DEPS and SCO have been done by Xiao-Feng Xie of adaptivebox.net. Both were modified and applied to the needs of the OpenOffice.org Solver by Andreas Schneider for Sun Microsystems, Inc.

The original documentation in English can be accessed from here [1]