How to implement an ordered crossover

Question

So I have two parents ABCDE EDCBA

Is it possible to simply select a subset of both: From the parent: ACD From the parent two: EDC

Then I copy the parent code to the descendants, but copy the selected subset with the order of the parent binary code like this: The offspring is one: DBCAE Second generation: 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 above C ++ code with my own random class. I'm not sure if the rotation is correct, but cross-laying seems legal. At the end of the day you will not get any repetitions!

 #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; }