I have a set of same-sized n(=25) matrices, m_1, m_2, ..., m_n, where each matrix falls into one of 10 classes. For each matrix, I have to find a "pair matrix" from the set so that the sum of the elements of the matrix scalar product of the two matrices is minimized. As each matrix can be selected as a "pair matrix" only once, this is a permutation problem. There are some restrictions:
- there can be no symmetric pair selections, meaning if m_i pairs with m_j, m_j cannot pair with m_i
- only matrices from different classes can pair up
Note that the second condition might make it impossible to find any viable permutations in general (e.g., all n matrices are from the same class), however this does not hold true for my case. The distribution of classes is as uniform as it can be with respect to the number of matrices.
My representation of pair selection is array of length n, where position (index) i of the array represents matrix m_i and the value j at that position (array[i]=j) represents the pair matrix m_j. As each matrix can be selected as a pair only once, each solution/chromosome is a permutation of values [1, 2, 3, ..., n].
My current crossover is cut-and-crossfill crossover and my mutation just randomly swaps a few elements in the array. The fitness is calculated as follows: for the pair m_i and m_j, calculate matrix scalar product m_ij=m_i*m_j and then sum all of the elements in m_ij. Multiply this value by 2 if condition 2) is not met. Sum all n values from the n pairs in the array and add some flat number P to the overall fitness for each symmetric pair from condition 1).
Note that the constraints 1) and 2) are implemented indirectly as a penalty, meaning that the fitness is increased if either of the condition is not satisfied. Ideally, I want would the constrains to be implemented directly so that my initialization and variation operators cannot produce illegal permutations. Additionally, the problem does not converge nicely and it looks like it finds better solutions only by pure chance. The reason could be the cut-and-crossfill crossover, which I used because it is used on the 8 queen problem, but I cannot prove that it converges.
My questions are: Is there is a better representation for my problem that would also directly include the constraints? If not, what would be the most efficient way of enforcing constraints in the initialization, mutation, and crossover?
I also tried to find some similar problems in books/online, however 8 queen problem is the most similar I was able to find. Typically, permutation problems found in literature include problems in which order is important (job shop scheduling problem) or where adjacency is important (traveling salesman problem), neither of which are relevant in my case.
Not a direct (or complete) answer to your question… just my 2-cents on the topic: Your approach (the representation as well as the use of penalties to enforce constraints) seems very “classic” (and there is nothing wrong with that!).
If you have the impression that “better solutions are found by chance” (and in case you have not done that already), maybe some parameter tuning helps (changing the population size, the number of selected parents, number of offsprings, mutation probability). Also, using the factor 2 as a penalty seems quite low to me – have you tried using a larger cost factor?
Lastly, even if each solution is represented as an array, I would rather describe this problem as a (balanced) assignment problem (with inter-related or dependent costs), not as an permutation problem. I.e., the sum of costs of all weighted pairs pij should be minimized
with wij being a weight (or cost) factor assigned to each pairing – set to a very large number in case i=j or if i and j have the same class and for each wji if pij has already been selected. Maybe this helps searching for some inspiration…