Traduire une chaîne binaire en expression mathématique

Question

J'ai expérimenté des algorithmes génétiques récemment et maintenant je voudrais construire des expressions mathématiques à partir des génomes (pour parler facilement, il faut trouver une expression qui correspond à un certain résultat) . J'ai des génomes constitués de gènes qui sont représentés par des octets, un génome peut ressembler à ceci: {12, 127, 82, 35, 95, 223, 85, 4, 213, 228}. La longueur est prédéfinie (bien qu'elle doive tomber dans une certaine plage), pas plus que la forme qu'elle prend. C'est-à-dire que n'importe quelle entrée peut prendre n'importe quelle valeur d'octet.

Maintenant, l'astuce consiste à traduire cela en expressions mathématiques. Il est assez facile de déterminer les expressions de base, par exemple: Choisissez les 2 premières valeurs et traitez-les comme produits, choisissez la 3ème valeur et choisissez-la comme opérateur (+, -, *, /, ^, mod), choisissez la 4ème valeur comme un produit et choisir la 5ème valeur en tant qu'opérateur à nouveau sur le résultat du 3ème opérateur sur les 2 premiers produits. (ou juste le gérer comme une expression postfix)

La complexité augmente lorsque vous commencez à autoriser les règles de priorité. Maintenant, quand par exemple l'entrée sous l'index 2 représente un '(', vous devez avoir un ')' quelque part plus loin sauf pour l'entrée 3, mais pas forcément l'entrée 4

Bien sûr, il en va de même pour beaucoup de choses. ne peut pas finir avec un opérateur à la fin, vous ne pouvez pas vous retrouver avec un nombre en vrac, etc.

Maintenant, je peux faire une énorme déclaration de commutateur (par exemple) en prenant toutes les possibilités possibles, mais cela fera le code illisible. J'espérais que quelqu'un là-bas connaisse une bonne stratégie sur la façon de prendre celui-ci.

Merci d'avance!

** EDIT **

Sur demande: le but que je suis en train de réaliser est de faire une application qui peut résoudre une fonction pour un ensemble de nombres. Comme pour l'exemple que j'ai donné dans le commentaire ci-dessous: {4, 11, 30} et il pourrait venir avec la fonction (X^3) + X

Answer 1

Bélisaire dans un commentaire donné un lien vers un sujet identique: Algorithm for permutations of operators and operands

Mon code:

private static double ResolveExpression(byte[] genes, double valueForX) 
    { 
     // folowing: https://stackoverflow.com/questions/3947937/algorithm-for-permutations-of-operators-and-operands/3948113#3948113 
     Stack<double> operandStack = new Stack<double>(); 

     for (int index = 0; index < genes.Length; index++) 
     { 
      int genesLeft = genes.Length - index; 
      byte gene = genes[index]; 

      bool createOperand; 
      // only when there are enough possbile operators left, possibly add operands 
      if (genesLeft > operandStack.Count) 
      { 
       // only when there are at least 2 operands on the stack 
       if (operandStack.Count >= 2) 
       { 
        // randomly determine wether to create an operand by threating everything below 127 as an operand and the rest as an operator (better then/2 due to 0 values) 
        createOperand = gene < byte.MaxValue/2; 
       } 
       else 
       { 
        // else we need an operand for sure since an operator is illigal 
        createOperand = true; 
       } 
      } 
      else 
      { 
       // false for sure since there are 2 many operands to complete otherwise 
       createOperand = false; 
      } 

      if (createOperand) 
      { 
       operandStack.Push(GeneToOperand(gene, valueForX)); 
      } 
      else 
      { 
       double left = operandStack.Pop(); 
       double right = operandStack.Pop(); 

       double result = PerformOperator(gene, left, right); 

       operandStack.Push(result); 
      } 
     } 

     // should be 1 operand left on the stack which is the ending result 
     return operandStack.Pop(); 
    } 


    private static double PerformOperator(byte gene, double left, double right) 
    { 
     // There are 5 options currently supported, namely: +, -, *, /,^and log (math) 
     int code = gene % 6; 

     switch (code) 
     { 
      case 0: 
       return left + right; 
      case 1: 
       return left - right; 
      case 2: 
       return left * right; 
      case 3: 
       return left/right; 
      case 4: 
       return Math.Pow(left, right); 
      case 5: 
       return Math.Log(left, right); 
      default: 
       throw new InvalidOperationException("Impossible state"); 
     } 
    } 

    private static double GeneToOperand(byte gene, double valueForX) 
    { 
     // We only support numbers 0 - 9 and X 
     int code = gene % 11; // Get a value between 0 and 10 
     if (code == 10) 
     { 
      // 10 is a placeholder for x 
      return valueForX; 
     } 
     else 
     { 
      return code; 
     } 
    } 

    #endregion // Helpers 
} 

Answer 2

Utiliser la notation "post-fix". Cela gère très bien les priorités.

La notation après correction gère trivialement le "groupement" ou les "règles de priorité".

Par exemple, l'expression b ** 2-4 * a * c, en post-fix est

b, 2, **, 4, a, *, c *, -

Pour évaluer une expression post-correctif, il vous suffit de pousser les valeurs sur une pile et d'exécuter les opérations.

Donc, ce qui précède devient quelque chose comme ce qui suit. Pour que cela fonctionne, vous devez partitionner votre chaîne d'octets en valeurs et en opérateurs. Pour cela, vous devez partitionner votre chaîne d'octets en valeurs et en opérateurs. Vous devez également vérifier l'arité de tous vos opérateurs pour vous assurer que le nombre d'opérateurs et le nombre d'opérandes sont équilibrés. Dans ce cas, le nombre d'opérateurs binaires + 1 est le nombre d'opérandes. Les opérateurs unaires ne nécessitent pas d'opérandes supplémentaires.

Answer 3

Comme toujours avec GA une grande partie de la solution est de choisir une bonne représentation. RPN (ou post-correctif) a déjà été suggéré. L'une des préoccupations que vous avez encore est que votre GA pourrait jeter les expressions qui commencent par les opérateurs (ou les opérateurs de non-concordance et opérandes ailleurs) tels que:

+,-,3,*,4,2,5,+,- 

A (petite) partie de la solution serait de définir des évaluations pour opérandes opérateurs sans-fils. Par exemple, on pourrait décider que la séquence:

+ 

évalue à 0, qui est l'élément d'identité pour l'addition. Naturellement

* 

évaluerait à 1. Les mathématiques ne peut pas avoir compris ce que l'élément d'identité pour la division est, mais l'APL a.

Maintenant vous avez la base d'une approche qui ne se soucie pas si vous obtenez la bonne séquence d'opérateurs et d'opérandes, mais vous avez toujours un problème quand vous avez trop d'opérandes pour le nombre d'opérateurs. Autrement dit, quelle est l'interprétation de (postfix following)?

2,4,5,+,3,4,- 

qui (peut-être) est évaluée à

2,9,-1 

Eh bien, maintenant vous devez inventer votre propre convention si vous voulez réduire à une seule valeur. Mais vous pouvez adopter la convention selon laquelle l'AG a créé une fonction vectorielle.

EDIT: réponse au commentaire de l'OP ...

Si un octet peut représenter soit un opérateur ou un opérande, et si vos places de programme aucune restriction sur l'endroit où un génome peut être divisé pour la reproduction, il y aura toujours être un risque que la progéniture représente une séquence invalide d'opérateurs et d'opérandes. Considérons, au lieu d'avoir chaque octet encoder un opérateur ou un opérande, un octet pourrait encoder une paire opérateur + opérande (vous pourriez manquer d'octets rapidement alors peut-être que vous auriez besoin d'utiliser deux octets). Ensuite, une séquence d'octets peut être traduit à quelque chose comme:

(plus 1)(plus x)(power 2)(times 3) 

qui pourrait évaluer, suite à une règle de gauche à droite avec une interprétation significative pour le premier terme, à 3((x+1)^2)