1 /**
2 * @(#)OrderCrossover.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.permutation;
10
11 import com.delhezi.ga.Chromosome;
12 //import java.util.logging.Logger;
13
14 /**
15 * <code>OrderCrossover</code>: Krzyżowanie z porządkowaniem
16 * OrderCrossover (OX1).
17 * @version 1.0 2009-06-10
18 * @author <a href="mailto:wojciech.wolszczak@delhezi.com">
19 * Wojciech Wolszczak</a>
20 */
21 public class OrderCrossover implements com.delhezi.ga.crossover.ICrossover {
22
23 /** Logger object. */
24 //private static final Logger LOGGER =
25 // Logger.getLogger(OrderCrossover.class.getName());
26
27 /** Delhezi Error Code. */
28 //private static final String DERC = "1-1.2-1-";
29
30 /** Class name. */
31 //private static final String CLASS_NAME = OrderCrossover.class.getName();
32
33 /**
34 * Funkcja crossover implementuje krzyżowanie z porządkowaniem;
35 * Geny w chromosomach powinny być unikalne, ich wartości nie mogą się
36 * powtarzać; Punkty krzyżowania wybierane są losowo.
37 * @param chromosome1 Chromosom.
38 * @param chromosome2 Chromosom.
39 * @since 1.0
40 */
41 @Override
42 public final void crossover(final Chromosome chromosome1,
43 final Chromosome chromosome2) {
44 assert (chromosome1.getGenes().length == chromosome2.getGenes().length);
45 if (chromosome1.getGenes().length == 0) {
46 return;
47 }
48 final int geneLength = chromosome1.getGenes().length;
49
50 //Losowe określenie dwóch punktów krzyżowania.
51 final int cutpoint1 = (int) (Math.random() * geneLength);
52 final int cutpoint2 = (int) (Math.random() * geneLength);
53
54 this.crossover(chromosome1, chromosome2, cutpoint1, cutpoint2);
55 }
56
57 /**
58 * Funkcja crossover implementuje krzyżowanie z porządkowaniem;
59 * Geny w chromosomach powinny być unikalne, ich wartości nie
60 * mogą sie powtarzać.
61 * @param chromosome1 Chromosom.
62 * @param chromosome2 Chromosom.
63 * @param cutpoint1 Punkt krzyżowania np. xx|xxx|xx cutpoint1=2.
64 * @param cutpoint2 Punkt krzyżowania np. yy|yyy|yy cutpoint2=5.
65 * @since 1.0
66 */
67 public final void crossover(final Chromosome chromosome1,
68 final Chromosome chromosome2,
69 final int cutpoint1, final int cutpoint2) {
70 assert (chromosome1.getGenes().length == chromosome2.getGenes().length);
71 if (chromosome1.getGenes().length == 0) {
72 return;
73 }
74
75 final int start = Math.min(cutpoint1, cutpoint2);
76 final int end = Math.max(cutpoint1, cutpoint2);
77
78 if ((start == end) || (start == 0 && end == chromosome2.getGenes().length)) {
79 return;
80 }
81
82 final int geneLength = chromosome1.getGenes().length;
83
84 //Tworzymy geny potomków.
85 Object[] child1 = new Object[geneLength];
86 Object[] child2 = new Object[geneLength];
87
88 //Dla sekcji dopasowania.
89 for (int i = start; i < end; i++) {
90 //Wypełnij sekcję dopasowania chromosomów potomnych genami
91 //rodzica.
92 child1[i] = chromosome1.getGene(i);
93 child2[i] = chromosome2.getGene(i);
94 }
95
96 int currentIndex1 = 0;
97 int currentIndex2 = 0;
98 boolean znaleziono;
99
100
101 // Dla SKRAJNYCH genów z lewej strony.
102 for (int i = 0; i < start; i++) {
103 // Dla child1
104 for (; ; ) {
105 znaleziono = false;
106 //Sprawdzenie czy jest już taki gen w chromosomie
107 for (int k = 0; k <= end && znaleziono == false; k++) {
108 if (child1[k] == chromosome2.getGene(currentIndex2)) {
109 znaleziono = true;
110 currentIndex2++;
111 }
112 }
113 //Jeśli nie ma to dodaj
114 if (znaleziono == false) {
115 child1[i] = chromosome2.getGene(currentIndex2);
116 currentIndex2++;
117 break; //KONIEC for(;;)
118 }
119 }
120
121 // Dla child2
122 for (; ; ) {
123 znaleziono = false;
124 for (int k = 0; k <= end && znaleziono == false; k++) {
125 if (child2[k] == chromosome1.getGene(currentIndex1)) {
126 znaleziono = true;
127 currentIndex1++;
128 }
129 }
130 if (znaleziono == false) {
131 child2[i] = chromosome1.getGene(currentIndex1);
132 currentIndex1++;
133 break; //KONIEC for(;;)
134 }
135 }
136 } //for
137
138
139 //Wypełniamy SKRAJNE geny obiektu potomnego z prawej strony.
140 for (int i = end; i < geneLength; i++) {
141 // Dla child1
142 for (; ; ) {
143 znaleziono = false;
144 for (int k = 0; k < geneLength && znaleziono == false; k++) {
145 if (child1[k] == chromosome2.getGene(currentIndex2)) {
146 znaleziono = true;
147 if (currentIndex2 < geneLength - 1) {
148 currentIndex2++;
149 } else {
150 currentIndex2 = 0;
151 }
152 }
153 }
154 if (znaleziono == false) {
155 child1[i] = chromosome2.getGene(currentIndex2);
156 if (currentIndex2 < geneLength - 1) {
157 currentIndex2++;
158 } else {
159 currentIndex2 = 0;
160 }
161 break; //KONIEC for(;;)
162 }
163 }
164
165 // Dla child2
166 for (; ; ) {
167 znaleziono = false;
168 for (int k = 0; k < geneLength && znaleziono == false; k++) {
169 if (child2[k] == chromosome1.getGene(currentIndex1)) {
170 znaleziono = true;
171 if (currentIndex1 < geneLength - 1) {
172 currentIndex1++;
173 } else {
174 currentIndex1 = 0;
175 }
176 }
177 }
178 if (znaleziono == false) {
179 child2[i] = chromosome1.getGene(currentIndex1);
180 if (currentIndex1 < geneLength - 1) {
181 currentIndex1++;
182 } else {
183 currentIndex1 = 0;
184 }
185 break; //KONIEC for(;;)
186 }
187 }
188 } //for
189
190 chromosome1.setGenes(child1);
191 chromosome2.setGenes(child2);
192 }
193 }