View Javadoc
1   /**
2    * @(#)KPointCrossover.java
3    * Copyright (C) 2008-2011 delhezi.com
4    *
5    * This class is released under the:
6    * GNU Lesser General Public License (LGPL) version 3 or later.
7    * http://www.gnu.org/copyleft/lesser.html
8    */
9   package com.delhezi.ga.crossover.standard;
10  
11  import com.delhezi.ga.Chromosome;
12  import com.delhezi.ga.utility.RandomUniqueInteger;
13  
14  import java.util.ArrayList;
15  import java.util.Collections;
16  import java.util.List;
17  import java.util.logging.Logger;
18  
19  /**
20   * <code>KPointCrossover</code>: Krzyżowanie wielopunktowe
21   * k-Point Crossover (k-PX).
22   * @version 1.0 2009-06-10
23   * @author <a href="mailto:wojciech.wolszczak@delhezi.com">
24   * Wojciech Wolszczak</a>
25   */
26  public class KPointCrossover implements com.delhezi.ga.crossover.ICrossover {
27  
28      /** Logger object. */
29      private static final Logger LOGGER =
30          Logger.getLogger(KPointCrossover.class.getName());
31  
32      /** Delhezi Error Code. */
33      //private static final String DERC = "1-1.3-3-";
34  
35      /** Class name. */
36      private static final String CLASS_NAME = KPointCrossover.class.getName();
37  
38      /** Ilość punktów krzyżowania.*/
39      private int k = 1;
40  
41      /**
42       * Krzyżowanie.
43       * @param chromosome1 Chromosom.
44       * @param chromosome2 Chromosom.
45       * @since 1.0
46       */
47      public final void crossover(final Chromosome chromosome1,
48                                  final Chromosome chromosome2) {
49          LOGGER.entering(CLASS_NAME, "crossover",
50                          new Object[] { chromosome1, chromosome2 });
51          this.crossover(chromosome1, chromosome2, this.k);
52          LOGGER.exiting(CLASS_NAME, "crossover",
53                         new Object[] { chromosome1, chromosome2 });
54      }
55  
56      /**
57       * Krzyżowanie.
58       * @param chromosome1 Chromosom.
59       * @param chromosome2 Chromosom.
60       * @param k Ilość punktów krzyżowania,
61       * wartość z przedziału <1,chromosome1.size()-1>.
62       * @since 1.0
63       */
64      public final void crossover(final Chromosome chromosome1,
65                                  final Chromosome chromosome2, int k) {
66          LOGGER.entering(CLASS_NAME, "crossover",
67                          new Object[] { chromosome1, chromosome2, k });
68  
69          if (chromosome1.size() < 2) {
70              return;
71          }
72          if (k > chromosome1.size() - 1) {
73              throw new IllegalArgumentException("k > chromosome1.size() - 1");
74          }
75          if (k < 1) {
76              throw new IllegalArgumentException("k < 1");
77          }
78  
79          //Wybierz k losowych punktów krzyżowania.
80          List<Integer> kPoints = new ArrayList<Integer>(k);
81  
82          RandomUniqueInteger bezPowtorzenZUsuwaniem =
83              new RandomUniqueInteger(chromosome1.size()-1);
84  
85          for (int i = 0; i < k; i++) {
86              kPoints.add(bezPowtorzenZUsuwaniem.get());
87          }
88  
89          this.crossover(chromosome1, chromosome2, kPoints);
90  
91          LOGGER.exiting(CLASS_NAME, "crossover",
92                         new Object[] { chromosome1, chromosome2 });
93      }
94  
95      /**
96       * Krzyżowanie.
97       * @param chromosome1 Chromosom.
98       * @param chromosome2 Chromosom.
99       * @param kPoints Lista punktów krzyżowania.
100      * np. k{1,4,6,9,10} = x|xxx|xx|xxx|x|x.
101      * @since 1.0
102      */
103     private final void crossover(final Chromosome chromosome1,
104                                  final Chromosome chromosome2,
105                                  List<Integer> kPoints) {
106         LOGGER.entering(CLASS_NAME, "crossover",
107                         new Object[] { chromosome1, chromosome2, kPoints });
108 
109         //Chromosom nie może być wartością null.
110         assert chromosome1 != null : "Illegal argument chromosome1: null";
111         assert chromosome2 != null : "Illegal argument chromosome2: null";
112         //Lista punktów krzyżowania nie może być wartością null.
113         assert kPoints != null : "Illegal argument kPoints: null";
114       
115         Collections.sort(kPoints);
116 
117         Object tmpCh;
118         boolean s = false;
119         for (int i = 0; i < chromosome1.size(); i++) {
120             if (s) {
121                 tmpCh = chromosome1.getGene(i);
122                 chromosome1.setGene(i, chromosome2.getGene(i));
123                 chromosome2.setGene(i, tmpCh);
124             }
125             if (kPoints.size() > 0) {
126                 if (i == kPoints.get(0) - 1) {
127                     s = !s;
128                     kPoints.remove(0);
129                 }
130                 //jeśli jest ostatnia sekcja i nie trzeba wymieniać genów
131                 if ((kPoints.size() == 0) && (s==false)) {
132                     return;
133                 }
134             }
135         }
136 
137         LOGGER.exiting(CLASS_NAME, "crossover",
138                        new Object[] { chromosome1, chromosome2 });
139     }
140 
141     /**
142      * Ustaw ilość punktów krzyżowania..
143      * @param k Ilość punktów krzyżowania.
144      * @since 1.0
145      */
146     public void setK(int k) {
147         this.k = k;
148     }
149 
150     /**
151      * Zwraca ilość punktów krzyżowania.
152      * @return Ilość punktów krzyżowania.
153      * @since 1.0
154      */
155     public int getK() {
156         return this.k;
157     }
158 }