How can I code my variable length chromosomes for GA?

Hi, I need to code my chromosomes in a way that each chromosome consists of several string (I'm not sure if this is possible, I want to prevent chromosomes of different types go through the crossover process together and mate, so I figured out to define different kinds of chromosomes and restrict them to mate only with the same kind), also the chromosomes have different lengths. I'm new to MATLAB and I don't know how to start coding and define the chromosomes. I'd be so grateful if somebody could help me with this.

[Walter Roberson]

In your situation, is there anything that remains constant about the chromosomes? It sounds as if the "type" remains constant, but does the length of each individual chromosome remain constant after crossover and mutation? For example is it possible that all chromosomes have the same number of "units" and only swap on "unit" boundaries, but units are not all the same number of base pairs? If so then you could encode the chromosomes according to some kind of arbitrary numbering of the "units".

If you were given a particular (possibly mutated) chromosome, is there a fast way to identify which "type" of chromosome it is?

[Sherwin]

Actually, even the chromosomes of the same type don't have equal lengths. and if they crossover there will be a new chromosome with a new length. And about your second question, I can't even think of a slow way. It hadn't occur to me till now. Now it all seems impossible to me.

Answer 1

[Walter Roberson]

For the situation in which chromosomes can mutate or cross-over on any boundary, and can be variable length, and the various types of chromosomes must not cross-over together, then:

• pick a maximum length that is not to be exceeded. Code all the chromosomes as your base pairs, then padded by as many copies of character that is not a valid base pair, so that the total length is constant. The filler could, for example, be the space character.
• prefix each chromosome by a character or fix-length string which indicates which "type" it is. It is acceptable to use type indications that overlap with valid characters for base pairs, but it would probably be a good idea during debugging to use something distinct, so that if you ever see one of the type characters inside a chromosome you would know immediately that there was a bug in the processing
• use a custom cross-over function and custom mutation function. Inside those, pull out the type indicator and remove any trailing occurrences of the padding character (this is especially easy if you used space for the padding, as then you can use deblank()). You can then perform the cross-over and mutation according to your rules about how the various types are allowed to interact. Then put the crossed-over or mutated chromosomes back together again, padding them to the appropriate length and putting on the appropriate type code. (If you do allow different types to cross-over or mutate together, you would have to have rules about which type the result was to be.)
• your objective function to evaluate the "fitness" should know to remove the type indication and remove the padding before scoring (and your scoring routine could take into account the type, if it was appropriate to do so.)

Now everything being passed around is constant length and contains the type information so you can protect against invalid cross-overs or mutations.

I do wonder, though, how you are going to evaluate the "fitness" of members of your population. What is it that you are trying to make them "better" at?

[Sherwin]

Thank you so much for your comprehensive answer. I'm really grateful. As I said I'm new to MATLAB and also new to metaheusristic algorithms. These were the first form of chromosomes that crossed my mind for solving my model, and as it turns out, it's gonna be so difficult to code. Again thanks a lot.

[Walter Roberson]

What model are you trying to solve?

[Sherwin]

My thesis model. I'm trying to solve it by Genetic Algorithm.

[Walter Roberson]

To confirm: your thesis involves a function that can take one chromosome at a time and return a numeric value for the chromosome, and you want to find the single chromosome that returns the "best" value? Or do you have a set of those kinds of functions that you are trying to satisfy simultaneously, a multi-objective genetic algorithm situation? Or are you trying to find a population of chromosomes that work together for some purpose?

Answer 2

[Adeke Terkumber]

Hi, please I wish to ask; is it possible to solve a Genetic Algorithm problem that has not objective function using MATLAB software?

Thank you.