Polynomial circuits_eac3

Work in progress.

Reason for using polynomial representation can be simpler individuals for evolution, where changes affects the result less, than changes in circuits, so the evolution may run smoother. Another reason is implementation, which is using GAlib representation for individuals, which is transparent to library, so we can use more options from the library.

Idea of the structure of polynomial representation

In polynomial representation, each individual (distinguisher) is combined from outputLength's of polynomials. Each polynomial is in algebraic normal form (ANF), where terms are XORed and variables in term are ANDed and is evaluated to one bit of the output.

Polynomials	Bits of output
(x1)	1
(x1 & x2) ^ (x1 & x4 & x5) ^ ()	1
(x2 & x3 & x4)	0
empty polynomial	0

Where number of lines is size of the output (used for evaluator). Terms are in parenthesis in this example. Null term () is evaluated to 1 (it is not possible to express zero term - it is not needed). Empty polynomials is evaluated to 0.

Internal representation

Terms

Term is stored in the internal vector in this way:

• x₀ .. x₆₃ goes to the vector[0]
• x₆₄ .. x₁₂₇ goes to the vector[1] ...

Where x₀ is 0 if variable is not used in term, or 1 if it is used in term.

Evolution possibilities

Both mutation and crossover are possible on polynomials.

Mutation

Mutation is done both on polynomials and on terms.

Terms mutation strategies

1. MUTATE_TERM_STRATEGY_FLIP: get random position from range of term and flip that bit. May have problem with high count of variables (convergence to 0.5*termLength variables)
2. MUTATE_TERM_STRATEGY_ADDREMOVE: flip bit with probability 0.5 to determine, if we would add, or remove variable. Maybe we would like to do both

Polynomials mutation strategies

1. Add new term: with probability mutateAddTermProbability is added:
   a) one new term in case, that MUTATE_ADD_TERM_STRATEGY_ONCE is selected
   b) as long as coin with probability mutateAddTermProbability is true, add new term (if MUTATE_ADD_TERM_STRATEGY_ONCE is not set)
   New term looks to be empty (it is evaluated as 1), which would not change polynomial until term is mutated.
2. Remove of term is similar to add new term, depends on MUTATE_RM_TERM_STRATEGY_ONCE.

Crossover

Current implementation allows 2 types of crossover. The basic is polynomials crossover, the second, extending the polynomials crossover is terms crossover.

Crossover of polynomials

Input of crossover is pair of parent individuals, output is pair of children (because of this, we cannot use crossover to create odd count of children). The order of polynomials in parents is shuffled and then for each position in children, we get polynomial from random parent (because of the shuffled order, we take random polynomial). The another parent is used for the second child. In conclusion, the children together contains each of polynomials of parents, but distribution of polynomials source is random (e. g. child can be just shuffled parent).

Crossover of terms

It is part of crossover of polynomials. For each polynomial, crossover of terms is done with probability CROSSOVER_TERM_P. We take random index inside range of both terms and we swap the parts of terms after this crossover place index.