Перевести двоичную строку в математическое выражение

Question

Я экспериментировал с генетическими алгоритмами в последнее время, и теперь я хотел бы построить математические выражения из геномов (для простоты можно найти выражение, которое соответствует определенному результату).

У меня есть геномы, состоящие из генов, которые представлены байтами. Один геном может выглядеть так: {12, 127, 82, 35, 95, 223, 85, 4, 213, 228}. Длина задана заранее (хотя она должна находиться в определенном диапазоне), равно как и форма, которую она принимает. То есть любая запись может принимать любое значение байта.

Теперь дело в том, чтобы перевести это в математические выражения. Определить базовые выражения довольно просто, например: выбрать первые 2 значения и рассматривать их как продукты, выбрать 3-е значение и выбрать его как оператор (+, -, *, /, ^, mod), выбрать 4-е значение в качестве продукта и выберите 5-е значение в качестве оператора, снова работая над результатом 3-го оператора над первыми 2-мя продуктами. (или просто обрабатывать это как выражение постфикса)

Сложность возрастает, когда вы начинаете разрешать правила приоритета. Теперь, когда, например, запись под индексом 2 представляет собой «(», вы обязаны иметь «)» где-то еще, кроме записи 3, но не обязательно записи 4

Конечно, то же самое относится ко многим вещам, вы не можете получить оператора в конце, вы не можете получить свободный номер и т. Д.

Теперь я могу сделать ОГРОМНЫЙ оператор переключения (например), используя все возможные возможности, но это сделает код нечитаемым. Я надеялся, что кто-нибудь там знает хорошую стратегию, как это сделать.

Заранее спасибо!

** РЕДАКТИРОВАТЬ **

По запросу: цель, которую я пытаюсь достичь, - создать приложение, которое может разрешить функцию для набора чисел. Что касается примера, который я привел в комментарии ниже: {4, 11, 30}, и он может придумать функцию (X ^ 3) + X

Answer 1

Велисарий в комментарии дал ссылку на аналогичную тему: Алгоритм перестановок операторов и операндов

Мой код:

    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

Как всегда с GA большая часть решения выбирает хорошее представление.RPN (или пост-исправление) уже было предложено.Еще одна проблема, которая у вас остается, заключается в том, что ваш GA может выдавать выражения, которые начинаются с операторов (или несоответствующих операторов и операндов в других местах), таких как:

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

(небольшая) часть решения будет заключаться в определении вычисленийдля операторов без операндов.Например, можно решить, что последовательность:

+

оценивается как 0, что является элементом идентификации для добавления.Естественно,

* 

оценил бы в 1. Математика, возможно, не выяснила, каков элемент идентичности для деления, но APL имеет.

Теперь у вас есть основа подхода, который не 'все равно, если вы получите правильную последовательность операторов и операндов, но у вас все еще есть проблема, когда у вас слишком много операндов для количества операторов.То есть, что такое интерпретация (постфиксный следующий)?

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

, который (возможно) оценивается как

2,9,-1

Что ж, теперь вы должны придумать собственное соглашение, если хотитечтобы уменьшить это до одного значения.Но вы могли бы принять соглашение о том, что GA создал векторную функцию.

EDIT: ответ на комментарий OP ...

Если байт может представлять либо оператор, либо операнд,и если ваша программа не накладывает никаких ограничений на то, где геном может быть разделен для воспроизведения, то всегда будет существовать риск того, что потомство представляет недопустимую последовательность операторов и операндов.Учтите, что вместо того, чтобы каждый байт кодировал либо оператор, либо операнд, байт может кодировать пару оператор + операнд (у вас могут быстро закончиться байты, поэтому, возможно, вам потребуется использовать два байта).Затем последовательность байтов может быть преобразована во что-то вроде:

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

, которое может вычислять, следуя правилу слева направо со значимой интерпретацией для первого члена, в 3((x+1)^2)

Answer 3

Используйте обозначение "post-fix".Это очень хорошо обрабатывает приоритеты.

Обозначения после исправления обрабатывают тривиально «группирование» или «правила приоритетов».

Например, выражение b ** 2-4 * a * c,в post-fix это

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

Чтобы оценить выражение после исправления, вы просто помещаете значения всоставлять и выполнять операции.

Таким образом, вышеприведенное становится примерно таким:,Вам также необходимо проверить «арность» всех ваших операторов, чтобы убедиться, что количество операторов и количество операндов сбалансированы.В этом случае число бинарных операторов + 1 - это число операндов.Унарные операторы не требуют дополнительных операндов.