1

I've been experimenting with genetic algorithms as of late and now I'd like to build mathematical expressions out of the genomes (For easy talk, its to find an expression that matches a certain outcome).

I have genomes consisting of genes which are represented by bytes, One genome can look like this: {12, 127, 82, 35, 95, 223, 85, 4, 213, 228}. The length is predefined (although it must fall in a certain range), neither is the form it takes. That is, any entry can take any byte value.

Now the trick is to translate this to mathematical expressions. It's fairly easy to determine basic expressions, for example: Pick the first 2 values and treat them as products, pick the 3rd value and pick it as an operator ( +, -, *, /, ^ , mod ), pick the 4th value as a product and pick the 5th value as an operator again working over the result of the 3rd operator over the first 2 products. (or just handle it as an postfix expression)

The complexity rises when you start allowing priority rules. Now when for example the entry under index 2 represents a '(', your bound to have a ')' somewhere further on except for entry 3, but not necessarily entry 4

Of course the same goes for many things, you can't end up with an operator at the end, you can't end up with a loose number etc.

Now i can make a HUGE switch statement (for example) taking in all the possible possibilities but this will make the code unreadable. I was hoping if someone out there knows a good strategy of how to take this one on.

Thanks in advance!

** EDIT **

On request: The goal I'm trying to achieve is to make an application which can resolve a function for a set of numbers. As for the example I've given in the comment below: {4, 11, 30} and it might come up with the function (X ^ 3) + X

Improve this question
7
  • 1
    Use a language with an eval() function Commented Dec 2, 2010 at 20:29
  • 1
    I believe you need to provide a few more examples for us to understand what you want to accomplish. Commented Dec 2, 2010 at 20:29
  • is it just me or are you trying to create a hardcore compression algorithm?! Commented Dec 2, 2010 at 20:30
  • Thats not what i'm asking, The binary strings make no sense, i need to make sense of them (transform them into a mathematical expression) Commented Dec 2, 2010 at 20:30
  • Hm, maybe (LA)LR parser? Commented Dec 2, 2010 at 20:30

3 Answers 3

Reset to default
1

Belisarius in a comment gave a link to an identical topic: Algorithm for permutations of operators and operands

My 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
}
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I'm sorry for the inline comments, not really accurate in some places
0

Use "post-fix" notation. That handles priorities very nicely.

Post-fix notation handles the "grouping" or "priority rules" trivially.

For example, the expression b**2-4*a*c, in post-fix is

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

To evaluate a post-fix expression, you simply push the values onto a stack and execute the operations.

So the above becomes something approximately like the following.

stack.push( b )
stack.push( 2 )
x, y = stack.pop(), stack.pop(); stack.push( y ** x ) 
stack.push( 4 )
stack.push( a )
x, y = stack.pop(), stack.pop(); stack.push( y * x ) 
stack.push( c )
x, y = stack.pop(), stack.pop(); stack.push( y * x ) 
x, y = stack.pop(), stack.pop(); stack.push( y - x )

To make this work, you need to have to partition your string of bytes into values and operators. You also need to check the "arity" of all your operators to be sure that the number of operators and the number of operands balances out. In this case, the number of binary operators + 1 is the number of operands. Unary operators don't require extra operands.

Improve this answer

2 Comments

Thanks for the answer but the real challange is not how to evaluate a post-fix expression but how to actually build a valid one using only a set of random bytes without breaking valid format. Basicly you last part is the thing i'm trying to achieve. I might be able to hack this together with a whole collection of conditions but there is bound to be a nice common pattern for this problem
@Polity: There aren't a lot of conditions. You partition your values into operators and operands. You assemble an expression. Since the length is fixed, you can trivially assure that you'll have a valid expression as long as the count of operators and operands is correct.
0

As ever with GA a large part of the solution is choosing a good representation. RPN (or post-fix) has already been suggested. One concern you still have is that your GA might throw up expressions which begin with operators (or mismatch operators and operands elsewhere) such as:

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

A (small) part of the solution would be to define evaluations for operand-less operators. For example one might decide that the sequence:

+

evaluates to 0, which is the identity element for addition. Naturally

*

would evaluate to 1. Mathematics may not have figured out what the identity element for division is, but APL has.

Now you have the basis of an approach which doesn't care if you get the right sequence of operators and operands, but you still have a problem when you have too many operands for the number of operators. That is, what is the intepretation of (postfix following) ?

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

which (possibly) evaluates to

2,9,-1

Well, now you have to invent your own convention if you want to reduce this to a single value. But you could adopt the convention that the GA has created a vector-valued function.

EDIT: response to OP's comment ...

If a byte can represent either an operator or an operand, and if your program places no restrictions on where a genome can be split for reproduction, then there will always be a risk that the offspring represents an invalid sequence of operators and operands. Consider, instead of having each byte encode either an operator or an operand, a byte could encode an operator+operand pair (you might run out of bytes quickly so perhaps you'd need to use two bytes). Then a sequence of bytes might be translated to something like:

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

which could evaluate, following a left-to-right rule with a meaningful interpretation for the first term, to 3((x+1)^2)

Improve this answer

4 Comments

Thanks for the answer. The problem with this technique is that i might have to go outside the realm of mathmatics in order to create working functions, that is: If i assume in code an empty division should result in 0 for example, i might get a function that matches the set of numbers but this function might mathematically not be valid which is not what i want.
"Mathematics may not have figured out what the identity element for division is" - is it not 1? Divide anything by 1 and you get itself... Am I missing something here? (I know its slightly off-topic - sorry.)
@Chris: I think you are missing the commutation requirement for an identity element in a group. We have a+0==0+a, a*1==1*a, but there is no such number for division.
Ah, I wasn't really thinking in terms of commutation. Or indeed groups. I never was much into pure maths. ;-) Thanks for the clarification though.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.