如何實現有序的交叉

我能不能選擇來自兩個子集：從父之一：ACD 從父之二：EDC

然後我複製父一進後代之一，但複製與家長三三兩兩在選定的子集順序，以便：後代之一：DBCAE 後代二：CDEBA

2012-08-02 Undefined

要回答標題問題：

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 }

來源

2012-08-02 19:00:49

感謝那正是我之後的事！ – Undefined 2012-08-03 16:07:01

這裏是上面用C++實現與我自己的隨機類的代碼。我不確定輪換是否正確，但交叉似乎是合法的。在一天結束時，你不會得到任何重複！

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

來源

2016-11-12 17:30:44

如何實現有序的交叉

回答

相關問題