In a random key genetic algorithm1, the chromosomes consist in a sequence of real numbers (initially randomly generated) in the interval $[0,1]$.
I've been told by my teacher that in these kinds of genetic algorithms, one cannot encode the solution directly into the chromosomes, as that would generate "infinitely large" convergence times. Instead, the proposed solution from my teacher is to use the weights in the chromosomes to modullate the construction of a solution through a greedy algorithm. Let me clarify that further with the classical example of the Travelling Salesman Problem:
In a direct encoding (my proposal), with $N=4$ cities, a chromosome with values $[0.1, 0.7, 0.4, 0.9]$ could be decoded in order to determine the order in which to visit the cities, which would become $1 \rightarrow 3 \rightarrow 2 \rightarrow 4$.
The other approach consists in constructing a solution by means of a regular greedy algorithm. For example, starting from the initial location, a simple greedy algorithm for the TSP would select, at each iteration, the closest city for its next step. In order to fit the chromosomes in this schema, when considering going to the next city, one would multiply the distance to the considered location by the value of the allele for that city, essentially changing the values of the greedy function with the chromosome's genes.
So my question would be:
- Is this kind of "modullating a greedy" chromosome encoding widespread in the literature? I couldn't find any examples. I find it surprising that it works well, because when using a greedy there's no way to explore the whole solution space, and the variations in the chromosomes arising from crossover are probably going to end up generating the same greedy solutions all the time.
- Is the first kind of encoding (the direct one) something unacceptable for a random-key genetic algorithm? Would something similar be unacceptable as well for a regular (as in, more generic) genetic algorithm?
