How to implement ordered crossover

Question

So I have two parents ABCDE EDCBA

can I just select a subset from both: From parent one: ACD From parent two: EDC

Then I copy parent one into offspring one but copy the selected subset with parent twos order so: Offspring one: DBCAE Offspring two: CDEBA

Answer 1

To answer the title question:

http://www.eecs.tufts.edu/~jfinke02/jmona/xref/jmona/example/tsp/crossover/OrderedCrossoverFunction.html:

1   /**
2    * OrderedCrossoverFunction.java
3    * 
4    * Copyright 2009, 2010 Jeffrey Finkelstein
5    * 
6    * This file is part of jmona.
7    * 
8    * jmona is free software: you can redistribute it and/or modify it under the
9    * terms of the GNU General Public License as published by the Free Software
10   * Foundation, either version 3 of the License, or (at your option) any later
11   * version.
12   * 
13   * jmona is distributed in the hope that it will be useful, but WITHOUT ANY
14   * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
15   * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
16   * 
17   * You should have received a copy of the GNU General Public License along with
18   * jmona. If not, see <http://www.gnu.org/licenses/>.
19   */
20  package jmona.example.tsp.crossover;
21  
22  import java.util.Collections;
23  import java.util.List;
24  import java.util.Vector;
25  
26  import jmona.CrossoverFunction;
27  import jmona.functional.Range;
28  import jmona.random.RandomUtils;
29  
30  /**
31   * Ordered crossover (also known as OX) for a tour in the traveling salesman
32   * problem.
33   * 
34   * @author Jeffrey Finkelstein
35   * @since 0.1
36   */
37  // TODO references for the original authors of TSP crossover functions
38  public class OrderedCrossoverFunction implements
39      CrossoverFunction<List<Integer>> {
40  
41    /**
42     * Perform ordered crossover (also known as OX) on the specified tours.
43     * 
44     * Ordered crossover works in two stages. First, a random slice is swapped
45     * between the two tours, as in a two-point crossover. Second, repeated cities
46     * not in the swapped area are removed, and the remaining integers are added
47     * from the other tour, in the order that they appear starting from the end
48     * index of the swapped section.
49     * 
50     * @param tour1
51     *          A tour.
52     * @param tour2
53     *          Another tour.
54     * @see jmona.CrossoverFunction#crossover(Object, Object)
55     */
56    @Override
57    public void crossover(final List<Integer> tour1, final List<Integer> tour2) {
58  
59      // get the size of the tours
60      final int size = tour1.size();
61  
62      // choose two random numbers for the start and end indices of the slice
63      // (one can be at index "size")
64      final int number1 = RandomUtils.randomData().nextInt(0, size - 1);
65      final int number2 = RandomUtils.randomData().nextInt(0, size);
66  
67      // make the smaller the start and the larger the end
68      final int start = Math.min(number1, number2);
69      final int end = Math.max(number1, number2);
70  
71      // instantiate two child tours
72      final List<Integer> child1 = new Vector<Integer>();
73      final List<Integer> child2 = new Vector<Integer>();
74  
75      // add the sublist in between the start and end points to the children
76      child1.addAll(tour1.subList(start, end));
77      child2.addAll(tour2.subList(start, end));
78  
79      // iterate over each city in the parent tours
80      int currentCityIndex = 0;
81      int currentCityInTour1 = 0;
82      int currentCityInTour2 = 0;
83      for (final int i : new Range(size)) {
84  
85        // get the index of the current city
86        currentCityIndex = (end + i) % size;
87  
88        // get the city at the current index in each of the two parent tours
89        currentCityInTour1 = tour1.get(currentCityIndex);
90        currentCityInTour2 = tour2.get(currentCityIndex);
91  
92        // if child 1 does not already contain the current city in tour 2, add it
93        if (!child1.contains(currentCityInTour2)) {
94          child1.add(currentCityInTour2);
95        }
96  
97        // if child 2 does not already contain the current city in tour 1, add it
98        if (!child2.contains(currentCityInTour1)) {
99          child2.add(currentCityInTour1);
100       }
101     }
102 
103     // rotate the lists so the original slice is in the same place as in the
104     // parent tours
105     Collections.rotate(child1, start);
106     Collections.rotate(child2, start);
107 
108     // copy the tours from the children back into the parents, because crossover
109     // functions are in-place!
110     Collections.copy(tour1, child2);
111     Collections.copy(tour2, child1);
112   }
113 
114 }

More theory: http://www.dmi.unict.it/mpavone/nc-cs/materiale/moscato89.pdf (mirror: http://www.scribd.com/doc/101866504/1989-On-Genetic-Crossover-Operators-for-Relative-Order-Preservation)

Related: http://www.scribd.com/doc/53306810/35/ORDERED-CROSSOVER:

Answer 2

Here is the code above implemented in C++ with my own random class. I'm not sure if the rotation is correct but the cross overing seems legit. At the end of the day, you won't get any repeats!

#include <array>
#include <random>
#include <iostream>

// I converted this found code into a functional class
// http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution
class MyRandom
{
public:
    MyRandom() : gen(rd()) {}

    int nextInt(const int& max)
    {
        std::uniform_int_distribution<> dis(0, max);
        return dis(gen);
    }

private:
    std::random_device rd;
    std::mt19937_64 gen;
    std::uniform_int_distribution<> setdis;
    bool disSet = false;
};

void crossover(std::vector<int>& parent1, std::vector<int>& parent2)
{
    int size = int(parent1.size());

    MyRandom rand;
    int number1 = rand.nextInt(7);
    int number2 = rand.nextInt(7);

    int start = fmin(number1, number2);
    int end = fmax(number1, number2);

    std::vector<int> child1;
    std::vector<int> child2;

    for(int i = start; i<end; i++)
    {
        child1.push_back(parent1[i]);
        child2.push_back(parent2[i]);
    }

    int geneIndex = 0;
    int geneInparent1 = 0;
    int geneInparent2 = 0;

    for (int i = 0; i<size; i++)
    {
        geneIndex = (end + i) % size;
        geneInparent1 = parent1[geneIndex];
        geneInparent2 = parent2[geneIndex];

        bool is_there = false;
        for(int i1 = 0; i1<child1.size(); i1++)
        {
            if(child1[i1] == geneInparent2)
            {
                is_there = true;
            }
        }
        if(!is_there)
        {
            child1.push_back(geneInparent2);
        }

        bool is_there1 = false;
        for(int i1 = 0; i1<child2.size(); i1++)
        {
            if(child2[i1] == geneInparent1)
            {
                is_there1 = true;
            }
        }
        if(!is_there1)
        {
            child2.push_back(geneInparent1);
        }
    }

    std::rotate(child1.begin(), child1.begin()+start, child1.end());
    std::rotate(child2.begin(), child2.begin()+start, child2.end());

    for(int i = 0; i<size; i++)
    {
        parent1[i] = child2[i];
        parent2[i] = child1[i];
    }
}

int main(int argc, const char * argv[]) {


    std::vector<int> parent1 = {0, 1, 2, 3, 4, 5, 6, 7};
    std::vector<int> parent2 = {7, 6, 5, 4, 3, 2, 1, 0};

    for(int i = 0; i<8; i++)
    {
        std::cout << parent1[i] << " ";
    }
    std::cout << std::endl;
    for(int i = 0; i<8; i++)
    {
        std::cout << parent2[i] << " ";
    }
    std::cout << std::endl;

    crossover(parent1, parent2);

    for(int i = 0; i<8; i++)
    {
        std::cout << parent1[i] << " ";
    }
    std::cout << std::endl;
    for(int i = 0; i<8; i++)
    {
        std::cout << parent2[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}