1

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.

Sergey Ronin
  • 756
  • 7
  • 23

2 Answers2

1

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:

giacomelli
  • 7,287
  • 2
  • 27
  • 31
0

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.

guroosh
  • 642
  • 6
  • 18
  • I get error: `chk[p1[x]] = 1 TypeError: unhashable type: 'numpy.ndarray'` – Sergey Ronin Mar 29 '19 at 13:57
  • I tested with python list, not with numpy array. – guroosh Mar 30 '19 at 14:05
  • What I use in my answer is a numpy array. Can you address those specifically, given that I'm trying to optimize my crossovers which are also the most used functions in my genetic algorithm? – Sergey Ronin Mar 30 '19 at 14:41
  • Chk is used to see if a point (x1, y1) is already present in the child path or not, so either instead of using a 2D numpy array you can use a 1D numpy array consisting of tuples which are hashable or you can try [this](https://stackoverflow.com/questions/46961952/how-to-make-a-tuple-including-a-numpy-array-hashable) – guroosh Mar 30 '19 at 15:02