CODEWITHSUNDEEP
genetic-algorithm
Avrohom Yisroel
Avrohom Yisroel

Reputation: 9440

How do I mutate a possible solution when the chromosomes are not simple numbers?

I'm just trying to understand GA, so please forgive any incorrect comments or assumptionshere. I have basically got the idea of how you encode potential solutions and then combine and/or mutate them to find similar (but hopefully better) solutions.

This seems simple when you have genes that are nice and simple. For example, this tutorial describes how to use a GA to find a sequence of digits and mathematical operators that will hit a target number. Given a couple of potential solutions, I can combine them by taking (say) the first n bits of one and the last (len-n) bits from the other. However I combine and mutate, I'll get something that makes sense.

However, what if I'm trying to solve something where the genes are not so simple? For example, suppose I want to solve a puzzle like this...

enter image description here

The idea is to fit all the pieces inside the frame. I can represent the frame as a 8x8 array, and the pieces as smaller arrays, like this...

int[][] piece1 = new int[2][];
piece1[0] = new int[] {1, 1, 1};
piece1[1] = new int[] {0, 1, 0};

This describes the top left piece in the picture. I could describe the others in a similar manner.

I can then attempt to fit all of my pieces into the frame, and count the number of array elements left over as my error.

However, how would I combine two potential solutions to produce a third? I can't just swap individual array entries, as that would populate the frame with invalid pieces. Similarly, how would I mutate a potential solution?

Sorry if I'm on the wrong track altogether. As I said, I'm very new to this, and trying to learn. Any help would be appreciated.

Upvotes: 0

Views: 100

Answers (1)

The Vee
The Vee

Reputation: 11550

A good genetic algorithm is all about the encoding and the operators, which are at least as important as the fitness function and selection rule. By choosing a naïve encoding, you can easily end up with an algorithm that takes up forever to discover an improvement, and may need some elitism to prevent good solutions from being lost to selection. This, of course, does not mean that your algorithm would never find a solution, but it may make it impractical. Dealing with hard constraints like this is tricky exactly because it may mean rethinking your encoding.

A simple encoding for your problem may be just stating where to put what piece and in what orientation. Because overlaps will happen, you will need to reject candidates which have an overlap, using a prohibitive fitness (infinity, if available in your data type) or an immediate discarding. (The former is easier to implement if you want to maintain a fixed population size.) Once you have such check implemented, it's straightforward to apply it to any result of mutation or crossover as well. Depending on your strategy you then either produce a candidate which will not be going to be selected, you retry, or you end up not generating a candidate from the current operation, if it lead to an unphysical solution.

Note that you may as well experiment with keeping the unphysical cases around, not with an infinite, just a high fitness: perhaps a second genetic operation will remove the overlap done by the first and produce something good.

Now what could an alternative encoding look like? If you want that, by its own nature, to prevent overlaps, maybe you could, instead of the final position of a piece, encode the tiling by the order the pieces are added from the top, Tetris-style. I'm not saying this is better, because that would just trade the hard limit on overlap for a hard limit on the height of the resulting structure, but it's a start. Just like in the previous case, you can then convert the hard limit to a soft one (simply make fitness proportional to height, and try to push that down to 8), leading to a reformulation of the problem equivalent to minimizing the number of unoccupied positions.

If you never want to even consider candidates that would not conform in one way or another to the hard rules, and have no intention on softening those, you would need to come up with an encoding that never encodes anything with an overlap and at the same time, never gets out of bounds. Building on the previous paragraph, you can make a distinction between a genotype and a phenotype: the genotype might be the Tetris-like encoding, and the phenotype the maximum prefix of that, cutting just before the piece that would, in Tetris terminology again, lose the game. You would then use the genotype for mutations and crossovers, but the phenotype for fitness evaluation.

Upvotes: 2

Related Questions