Hi,
I've recently read that the use of random keys in RKGA (Encoding phase) is useful for problems that require permutations of the integers and for which traditional one- or two-point crossover presents feasibility problems.
For example: Consider a 5-node TSP instance. Traditional GA encodings of TSP solutions consist of a stream of integers representing the order in which nodes are to be visited by the tour.1 But one-point crossover, for example, may result in children with some nodes visited more than once and others not visited at all.
My question is: if we don’t have a feasibility problems and our solutions are all feasible solutions so in this case is it correct to apply RKGA?
Hi.
Random-key-based (RK) approaches are used when a swarm or evolutionary algorithm encodes its individuals with real-valued vectors, and it is applied to solve some permutation problem (solutions are sequences of integers and RK maps a real-valued vector in one sequence of integers). If the algorithm uses an integer-based individual, RK is not used, but you should guaranty that disturbing operators (crossover, mutation, or other) generate only feasible solutions.
Commonly, 1-point crossover (and other crossover operators) create infeasible integer-based offspring, and a repair mechanism is needed.
Please check the paper of Puljić and Manger: Comparison of eight evolutionary crossover operators for the vehicle routing problem (Article Comparison of eight evolutionary crossover operators for the...
) for a detailed description of genetic operators used to generates feasible integer-based offsprings.Furthermore, RK is also used when integer-based vectors are used as individuals, but the disturbing operators (the mutation operator employed by the differential evolution algorithm, by example) creates real-based offsprings, and these new individuals should be repaired.
In my opinion, if your algorithm uses integer-based individuals, and your crossover and mutation operators generates only feasible solutions, neither RK nor any repair mechanism should be applied.
Best regards!
- Badges
- Science topic