FR/Calc/NLPSolver

From The Document Foundation Wiki
Jump to: navigation, search

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 à : c = p_1 \cdot x_1 + p_2 \cdot x_2p_1 et p_2 représentent les prix de deux produits et x_1 et x_2 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 (x_1 et x_2). 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 : f(x,y) = (1-x)^2 + 100 \cdot (y - x^2)

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 (0 \leq \text{var} \leq 1 ou peut-être -1000000 \leq \text{var} \leq 1000000). 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 : \text{Limite} = \text{ValeurInitiale} \pm(\text{Seuil} \cdot \text{ValeurInitiale}).

Exemple:

La \text{ValeurInitiale} est 100 et le \text{Seuil} est 3 (par défaut). Dans ce cas, la limite inférieure serait 100 - 3  \cdot 100 = -200 et la limite supérieure 100 + 3  \cdot 100 = 400.

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]