Re: Genetic Algorithms for factorize multivariate polynomials

On Jun 6, 10:49 am, "Jeremy Watts" <rtur...@xxxxxxxxxxx> wrote:
Hi,

I am attempting to use a GA to factorize a multivariate polynomial
(polynomials having more than one variable) with integer coefficients.

My failing memory supplies the word multinomial.

This sounds like a very reasonable application. I assume you mean
integer powers rather than integer coefficients, as the restriction to
integers in your coefficients would be lost in the next step anyway.

The first step I have used 'normalises' the polynomial, so that all of its
coefficients lie in the range -1 to +1. This works by dividing out by the
highest magnitude coefficient.

And I assume this is to insure that all the factors will also lie
between -1 and 1. This may be important to you if you are using a
fixed-sized binary representation but not so important if you simply
deal with real numbers.

I then use two 'template' factors as candidate solutions to the
factorization. These multivariate templates consist of a combination of
'all possible' polynomial terms that the fators could possibly have.

I assume that you are using two templates because you have two
variables, and the size of each template is set to match the highest
power of each variable.

Random coefficients in the range -1 to +1 are then produced for each of the
candidate factors. I have initially set this step to produce an initial
population of 10,000 solutions.

Well, 10,000 seems to me to be a bit of an overkill on what I expect
to be a well-behaved problem. I might be inclined to reduce the
population to 1,000 and put the same effort into 10 generations that
you are into 1. But then you're doing some other things I find a
little odd, so 10,000 may work fine for you. But do a few runs with
1/10th the population and see if they don't reach a satisfactory
solution without requiring 10 times the number of generations.

Each of these solutions are then assessed according to how fit they are by
choosing random values for the variables used, and evaluating the input
polynomial, and both of the candidate factor polynomials for these values.

The fitness function is then defined as being the 'value for the evaluated
input polynomial' minus the product of the 'evaluated factor polynomials'.
Clearly the closer this value is to zero, then the better the candidate
solution is.

Clearly

At this stage I then take the best 10% of solutions to go on to breed with
them.

One of the big balancing acts in dealing with GAs is selective
pressure to reach a solution versus premature convergence to a
solution. Normally I would say that killing off 90% of your
population with no chance of reproduction is way too severe and would
create a significant danger of converging too soon before the best
solution is found (at least in the case of a linear chromosome. If
you are using a real number representation, I'm less concerned.)
Against this you have two hedges. One is the large population size,
but this is of only limited use against exponential processes; it's
probably only going to stave off convergence for a few generations.
The other is that you don't describe any selective pressure at all on
the part of the 10% of the solutions selected to breed the next
generation. If they are treated equally without regard to quality and
each of them has an average of 10 offspring with separate partners in
the next generation, then you may be just fine. I don't have an
intuition for dealing with such stark contrast between absolute
selection and no selection. Normally I use a ramp function based on
the average fitness and its deviation to select parents for the next
generation, with the slope of the ramp function controlling selective
pressure.

I have to say this is the first time I've attempted to use a GA, and so my
question is one of representing solutions.

How could I represent the solutions here in terms of binary? Could I convert
each of the coefficients of the candidate factors to binary and string them
together to form a 'chromosome'?

Exactly. That would work just fine.

Is binary strictly necessary? Could I not simply stick with ordinay
floating numbers here and use selection/recombination/mutation with them?

Absolutely. And that would be much less troublesome in some ways.
If you are breeding the real numbers X and Y at a particular location
and X and Y are different then in the offspring replace them with one
of the 9 values X, Y, 2X-Y, 2Y-X, X/2+Y/2, 2X/3+Y/3, X/3+2Y/3, 3X/2-Y/
2, 3Y/2-X/2 chosen at random. If X and Y are the same then there is
no change in the offspring at that point. I think you will be happy
using this scheme to replace binary crossover within the binary
representation of a real number, and you do away with the artificial
restriction of real numbers between -1 and 1.

On the downside, you are giving something up by not having a linear
chromosome with crossover. One of the reasons that GAs work so
surprisingly well is that the linear structure facilitates small
compact blocks of genetic material with above average utility
expanding in the population in an exponential manner. Now for this
problem, no factor is more related to any other factor so there is no
inherent relational structure to be mirrored in the chromosome layout,
but the general principle still applies.

You could make an argument for representing your solution as a linear
chromosome of real numbers. To perform crossover between two
solutions, select a position in the chromosome at random. All the
real numbers in the offspring above that position come from the first
parent and all those below that position come from the second parent.
To find the value of the offspring in the chosen position select at
random one of the 9 values specified in the second paragraph up.

In fact the notion of an evolutionary system is robust and will take a
lot of abuse. For comparison, try considering the X and Ys in what is
now three paragraphs back to represent solution vectors listing all
the factors and form the offspring by selecting from the 9 solution
vectors specified. Actually my intuition is warning me that this leads
to too many duplicate values (therefor premature convergence) and so I
would eliminate X and Y as possible offspring and for this case would
select from the remaining 7 possible offspring. I think you'll find
the evolutionary system still works well.

Clif

Regards

Jeremy Watts

.

Relevant Pages

  • Re: Genetic Algorithms for factorize multivariate polynomials
    ... integer powers rather than integer coefficients, ... and both of the candidate factor polynomials for these ... selection and no selection. ... and X and Y are different then in the offspring replace them with one ...
    (comp.ai.genetic)
  • Re: Genetic Algorithms for factorize multivariate polynomials
    ... integer powers rather than integer coefficients, ... and both of the candidate factor polynomials for these ... selection and no selection. ... and X and Y are different then in the offspring replace them with one ...
    (comp.ai.genetic)
  • Re: Genetic Algorithms for factorize multivariate polynomials
    ... integer powers rather than integer coefficients, ... and both of the candidate factor polynomials for these ... selection and no selection. ... and X and Y are different then in the offspring replace them with one ...
    (comp.ai.genetic)
  • Integrating Rational Functions
    ... as a linear combination of a rational function, ... tangents of polynomials of degree 1, ... of which will have real number coefficients. ... has complex roots that show up in complex conjugate ...
    (sci.math)
  • Re: sparse polynomial arithmetic
    ... polynomials and the program operates under the *assumption* that ... but polynomials over multiprecision coefficients. ... "know" in advance that coefficients aren't going to overflow, ... so any comparison with a format ...
    (sci.math.symbolic)