artificial-intelligence - 如何实现有序交叉

Question

所以我有两个 parent ABCDEEDCBA

我可以从两者中选择一个子集吗:来自父级一:ACD来自父级二:EDC

然后，我将父代复制到子代，但将所选子集按父代二元顺序复制，如下所示:后代一:DBCAE后代二:CDEBA

Answer 1

回答标题问题:

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 }

更多理论:http://www.dmi.unict.it/mpavone/nc-cs/materiale/moscato89.pdf (镜像:http://www.scribd.com/doc/101866504/1989-On-Genetic-Crossover-Operators-for-Relative-Order-Preservation)

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