Crossover and mutation in Differential Evolution

Question

I'm trying to solve Traveling Salesman problem using Differential Evolution. For example, if I have vectors:

[1, 4, 0, 3, 2, 5], [1, 5, 2, 0, 3, 5], [4, 2, 0, 5, 1, 3]

how can I make crossover and mutation? I saw something like a+Fx(b-c), but I have no idea how to use this.

Answer 1

if F=0.6, a=[1, 4, 0, 3, 2, 5], b=[1, 5, 2, 0, 3, 5], c=[4, 2, 0, 5, 1, 3] then a+Fx(b-c)=[-0.8, 5.8, 1.2, 0, 3.2, 6.2] then change the smallest number in the array to 0, change the second smallest number in the array to 1, and so on. so it return [0, 4, 2, 1, 3, 5]. This method is inefficient when used to solve the jsp problems.

Answer 2

I ran into this question when looking for papers on solving the TSP problem using evolutionary computing. I have been working on a similar project and can provide a modified version of my written code.

For mutation, we can swap two indices in a vector. I assume that each vector represents an order of nodes you will visit.

def swap(lst):

        n = len(lst)
        x = random.randint(0, n)
        y = random.randint(0, n)
        
        # store values to be swapped
        old_x = lst[x]
        old_y = lst[y]

        # do swap
        lst[y] = old_x
        lst[x] = old_y

    return lst

For the case of crossover in respect to the TSP problem, we would like to keep the general ordering of values in our permutations (we want a crossover with a positional bias). By doing so, we will preserve good paths in good permutations. For this reason, I believe single-point crossover is the best option.

def singlePoint(parent1, parent2):

        point = random.randint(1, len(parent1)-2)

        def helper(v1, v2):
            # this is a helper function to save with code duplication

            points = [i1.getPoint(i) for i in range(0, point)]
            
            # add values from right of crossover point in v2
            # that are not already in points
            for i in range(point, len(v2)):
                pt = v2[i]
                if pt not in points:
                    points.append(pt)

            # add values from head of v2 which are not in points
            # this ensures all values are in the vector.
            for i in range(0, point):
                pt = v2[i]
                if pt not in points:
                    points.append(pt)

            return points
        
        # notice how I swap parent1 and parent2 on the second call
        offspring_1 = helper(parent1, parent2)
        offspring_2 = helper(parent2, parent1)

        return offspring_1, offspring_2

I hope this helps! Even if your project is done, this could come in handy GA's are great ways to solve optimization problems.