Below you find a text describing the generator. I did not get the quations from my Mac-MS-Word over alright. Hence I "verbalise" them here:
equation 1: bi is equal to the sum for j from 1 to n of the products of aij
and xj
and this for i=1..n
equation2: minus the sum for i from 1 to n of the absolute value of the
difference between
the sum for j from 1 to n of the products of aij and xj
and
bi
Sorry, I know this is not easy to read, you find these equations on p. 364 and 365 of my J. of Alife paper
I have only LISP-code of this generator availavle (I don't know any C). The implementation is straightforward though.
This problem generator was first described by Bremermann (1962?). The goal is to solve the matrix equation Ax=b. The matrix A (dimension n by n) and the n-dimensional vector b are given. The n-dimensional vector x has to be found. Or, equivalently, the following system of linear equations has to be solved:
(1)
Except for the sign inversion, which allows to use a maximization-GA, the fitness function is identical to the one reported in [2].
(2)
The diagonal elements of A are randomly chosen from the set {1,2,3,...,9}. When all off-diagonal elements of A are zero then the problem is not epistatic, i.e. each component xi only contributes to its corresponding bi. By setting off-diagonal entries to non-zero, the degree of epistasis is increased: the more non-zero off-diagonal elements in A, the higher the de gree of epistasis.
When only the elements on the diagonal (aii) and immediately above it (ai-1;i) are non-zero then the i-th equation couples xi and xi+1. Due to transitivity, this means that all x-components are coupled. Hence, given an array with only non-zero di agonal elements one can gradually increase the degree of epistasis by setting elements immediately above the diagonal to non-zero. This procedure is used to produce problems with different degrees of epistasis. In order to allow for easy experimentation, the bi are chosen such that all components xi of the solution to the system of equations are equal to 1. In the experiments reported in [3],[4], n is equal to 10, i.e. A is a 10 by 10 matrix, and x and b both contain 10 components.
References
[1] Bremermann, H.J., (1962), Optimization Through Evolution and Recombination, In: Self-Organizing Systems, M.C. Yovits et al, Eds., Washington, DC: Spartan 1962.
[2] Fogel, D.B., Atmar, J.W., (1990), Comparing Genetic Operators with Gaussian Mutations in Simulated Evolutionary Processes Using Linear Systems, Journal of Biological Cybernetics, vol. 63, Springer Verlag.
[3] Paredis, J., (1995), The Symbiotic Evolution of Solutions and their Representations, Proceedings of the Sixth International Conference on Genetic Algorithms (ICGA 95), Eshelman, L. (ed.), Morgan Kaufmann Publishers.
[4] Paredis, J., (1996), Symbiotic Coevolution for Epistatic Problems, in Proceedings of the European Conference on Artificial Intelligence 1996 (ECAI-96), W. Wahlster (ed.), John Wiley & Sons .
Jan Paredis MATRIKS Universiteit Maastricht Postbus 616 NL-6200 MD Maastricht The Netherlands email: jan@riks.nl tel: +31 43 3883356 fax: +31 43 3253155
For more information, please contact William M. Spears.
Last modified: 07/29/99