CODEWITHSUNDEEP
python-3.xnumpygenetic-algorithmtraveling-salesman
Sergey Ronin
Sergey Ronin

Reputation: 776

"unique" crossover for genetic algorithm - TSP

I am creating a Genetic Algorithm to solve the Traveling Salesman Problem.

Currently, two 2D lists represent the two parents that need to be crossed:

path_1 = np.shuffle(np.arange(12).reshape(6, 2))
path_2 = np.arange(12).reshape(6,2)

Suppose each element in the list represents an (x, y) coordinate on a cartesian plane, and the 2D list represents the path that the "traveling salesman" must take (from index 0 to index -1).

Since the TSP requires that all points are included in a path, the resulting child of this crossover must have no duplicate points.

I have little idea as to how I can make such crossover and have the resulting child representative of both parents.

Upvotes: 1

Views: 968

Answers (2)

giacomelli
giacomelli

Reputation: 7407

You need to use an ordered crossover operator, like OX1.

OX1 is a fairly simple permutation crossover. Basically, a swath of consecutive alleles from parent 1 drops down, and remaining values are placed in the child in the order which they appear in parent 2.

I used to run TSP with these operators:

Upvotes: 1

guroosh
guroosh

Reputation: 652

You can do something like this,

Choose half (or any random number between 0 to (length - 1)) coordinates from one parent using any approach, lets say where i % 2 == 0.

These can be positioned into the child using multiple approaches: either randomly, or all in the starting (or ending), or alternate position.

Now the remaining coordinated need to come from the 2nd parent for which you can traverse in the 2nd parent and if the coordinate is not chosen add it in the empty spaces.

For example,

I am choosing even positioned coordinated from parent 1 and putting it in even position indices in the child and then traversing in parent 2 to put the remaining coordinated in the odd position indices in the child.

def crossover(p1, p2, number_of_cities):
    chk = {}
    for i in range(number_of_cities):
        chk[i] = 0
    child = [-1] * number_of_cities
    for x in range(len(p1)):
        if x % 2 == 0:
            child[x] = p1[x]
            chk[p1[x]] = 1
    y = 1
    for x in range(len(p2)):
        if chk[p2[x]] == 0:
            child[y] = p2[x]
            y += 2
    return child

This approach preserves the order of cities visited from both parents.

Also since it is not symmetric p1 and p2 can be switched to give 2 children and the better (or both) can be chosen.

Upvotes: 0

Related Questions