There is a certain correct reordering 'key', but its length can be 20+ (20! can't be bruteforced)

The reorder key is represented using a random string of the first x consecutive characters which is reorganized into alphabetical order

for example the reorder key BADEC would become to ABCDE,
here we move:
the 1st one (B) to 2nd spot (1 -> 2),
the 2nd one (A) to 1st spot (2 -> 1),
the 3rd one (D) to 4th spot (3 -> 4),
the 4th one (E) to 5th spot (4 -> 5),
the 5th one (C) to 3rd spot (5 -> 3),

I have a fitness function that gives a higher score depending on how correct the reorder key is.


My question is: How would I best go about breeding these keys. I thought about some solutions but I am not sure which one is better or if there are any better ones

Solution 1:
for the new key we choose the 2nd letter to be either one of the 2nd letters of the 2 highest scoring parent keys based on random chance

This has issues because for example if we have the parents
BAC (1 -> 2, 2 -> 1, 3 -> 3)
CBA (1 -> 3, 2 -> 2, 3 -> 1)

We can create CAA from this which is (1 -> 3, 2 -> 1, 3 -> 2)

Notice that 3 -> 2 reordering is nowhere to be found in the parent keys, meaning we might lose some valuable stuff (or create useless information). The parent keys scored high for a reason and I feel like we are throwing some of it out of the window.

Solution 2:
We could also choose the reorderings based on the parent keys but we could get stuck here:
BAC (1 -> 2, 2 -> 1, 3 -> 3)
CBA (1 -> 3, 2 -> 2, 3 -> 1)

1) we choose 3 -> 1 from the second key (so A is in the 3rd spot, new key: xxA)
(we can now not choose 2 -> 1 because we already have a reorder for 1)
2) we choose 1 -> 2 from the first key (so B is in the 1st spot, new key: BxA)
(we can now not choose anything else, there is no existing 2 -> 3)