001/** 002 * 003 */ 004package org.biojavax.ga.functions; 005 006import java.util.Iterator; 007import java.util.Random; 008 009import org.biojava.bio.symbol.Alphabet; 010import org.biojava.bio.symbol.Edit; 011import org.biojava.bio.symbol.IllegalAlphabetException; 012import org.biojava.bio.symbol.PointLocation; 013import org.biojava.bio.symbol.SymbolList; 014import org.biojava.utils.ChangeVetoException; 015import org.biojavax.ga.functions.AbstractCrossOverFunction; 016import org.biojavax.ga.functions.GACrossResult; 017import org.biojavax.ga.functions.SimpleGACrossResult; 018 019/** 020 * This does a 2-point-crossover on two chromosomes keeping the Symbols in each 021 * chromosome constant. The method is commonly named OX - operator 022 * 023 * @author Susanne Merz 024 */ 025public class OrderCrossover extends AbstractCrossOverFunction { 026 027 /** 028 * Sets the maximal number of crossover points to two and the crossover 029 * probability to 0.5 and initializes this object. 030 */ 031 public OrderCrossover() { 032 this.setMaxCrossOvers(2); 033 double[] pro = {0.5}; 034 this.setCrossOverProbs(pro); 035 } 036 037 /* 038 * (non-Javadoc) 039 * 040 * @see org.biojavax.ga.functions.CrossOverFunction#performCrossOver(org.biojava.bio.symbol.SymbolList, 041 * org.biojava.bio.symbol.SymbolList) 042 */ 043 public GACrossResult performCrossOver(SymbolList chromA, SymbolList chromB) 044 throws ChangeVetoException { 045 int[] crosslocations = this.generateCrossoverLocations(chromA.length()); 046 // only do a chrossover if there are valid positions. 047 if (crosslocations[1] != 0.0) { 048 // if we found only one crossover position, we assume the 049 // second position to be the end of teh chromosome 050 if (crosslocations[0] == 0.0) { 051 crosslocations[0] = crosslocations[1]; 052 crosslocations[1] = chromA.length(); 053 } 054 Alphabet alphA = chromA.getAlphabet(); 055 Alphabet alphB = chromB.getAlphabet(); 056 SymbolList snipA = chromA.subList(crosslocations[0], crosslocations[1]); 057 SymbolList snipB = chromB.subList(crosslocations[0], crosslocations[1]); 058 SymbolList snipAwoB = snipA.subList(1, snipA.length()); 059 SymbolList snipBwoA = snipB.subList(1, snipB.length()); 060 // remove all elements of snipA from snipBwoA and vice versa 061 for (int i = 1; i <= snipB.length(); i++) { 062 int j = 1; 063 Iterator it = snipAwoB.iterator(); 064 boolean notfound = true; 065 while (it.hasNext() && notfound) { 066 067 if (it.next().equals(snipB.symbolAt(i))) { 068 try { 069 snipAwoB.edit(new Edit(j, 1, SymbolList.EMPTY_LIST)); 070 } catch (Exception e) { 071 e.printStackTrace(); 072 } 073 break; 074 } 075 j++; 076 } 077 Iterator it2 = snipBwoA.iterator(); 078 j = 1; 079 while (it2.hasNext()) { 080 if (it2.next().equals(snipA.symbolAt(i))) { 081 try { 082 snipBwoA.edit(new Edit(j, 1, SymbolList.EMPTY_LIST)); 083 break; 084 } catch (Exception e) { 085 e.printStackTrace(); 086 } 087 } 088 j++; 089 } 090 } 091 // remove all elements of snipA and snipB from both chromsomes 092 int sniplength = (crosslocations[1] - crosslocations[0]) + 1; 093 try { 094 // remove snipA from chromB and snipB from chromB 095 chromA.edit(new Edit(crosslocations[0], sniplength, 096 SymbolList.EMPTY_LIST)); 097 chromB.edit(new Edit(crosslocations[0], sniplength, 098 SymbolList.EMPTY_LIST)); 099 // remove elements of snipA from chromB 100 Iterator it1 = snipA.iterator(); 101 while (it1.hasNext()) { 102 Object current = it1.next(); 103 Iterator it2 = chromB.iterator(); 104 Iterator it3 = chromA.iterator(); 105 int position = 1; 106 while (it2.hasNext()) { 107 if (it2.next().equals(current)) { 108 chromB.edit(new Edit(position, 1, SymbolList.EMPTY_LIST)); 109 break; 110 } 111 position++; 112 } 113 } 114 // remove elements of snipB from chromA 115 it1 = snipB.iterator(); 116 while (it1.hasNext()) { 117 Object current = it1.next(); 118 Iterator it2 = chromA.iterator(); 119 Iterator it3 = chromB.iterator(); 120 int position = 1; 121 boolean notfound = true; 122 while (it2.hasNext() && notfound) { 123 if (it2.next().equals(current)) { 124 chromA.edit(new Edit(position, 1, SymbolList.EMPTY_LIST)); 125 notfound = false; 126 break; 127 } 128 position++; 129 } 130 } 131 } catch (IllegalAlphabetException e) { 132 System.out.println("Sorry, you used an illegal alphabet"); 133 e.printStackTrace(); 134 } 135 // put parts together in the order snipXwoY-snipY-X 136 try { 137 chromA.edit(new Edit(1, 0, snipB)); 138 chromA.edit(new Edit(1, 0, snipAwoB)); 139 chromB.edit(new Edit(1, 0, snipA)); 140 chromB.edit(new Edit(1, 0, snipBwoA)); 141 } catch (IllegalAlphabetException e) { 142 e.printStackTrace(); 143 } 144 // if the chromosomes are not cycle-invariant we need to 145 // adjust positions 146 int newposition = 1; 147 Iterator it = chromA.iterator(); 148 while (it.hasNext()) { 149 if (it.next().equals(snipB.symbolAt(1))) { 150 // newposition++; 151 break; 152 } 153 newposition++; 154 } 155 int versatz = crosslocations[0] - newposition; 156 157 if (versatz < 0) { 158 versatz = Math.abs(versatz); 159 // remove from front and add to end 160 try { 161 SymbolList temp = chromA.subList(1, versatz); 162 chromA.edit(new Edit(1, versatz, SymbolList.EMPTY_LIST)); 163 chromA.edit(new Edit(chromA.length() + 1, 0, temp)); 164 temp = chromB.subList(1, versatz); 165 chromB.edit(new Edit(1, versatz, SymbolList.EMPTY_LIST)); 166 chromB.edit(new Edit(chromB.length() + 1, 0, temp)); 167 168 } catch (IllegalAlphabetException e) { 169 e.printStackTrace(); 170 } 171 } 172 173 else if (versatz > 0) { 174 // remove from end and add to front 175 try { 176 versatz--; 177 int start = chromA.length() - versatz; 178 SymbolList temp = chromA.subList(start, chromA.length()); 179 chromA.edit(new Edit(start, chromA.length() - (start - 1), 180 SymbolList.EMPTY_LIST)); 181 chromA.edit(new Edit(1, 0, temp)); 182 temp = chromB.subList(start, chromB.length()); 183 chromB.edit(new Edit(start, chromB.length() - (start - 1), 184 SymbolList.EMPTY_LIST)); 185 chromB.edit(new Edit(1, 0, temp)); 186 187 } catch (IllegalAlphabetException e) { 188 e.printStackTrace(); 189 } 190 } 191 192 PointLocation[] points = {new PointLocation(crosslocations[0]), 193 new PointLocation(crosslocations[1])}; 194 GACrossResult result = new SimpleGACrossResult(points, new SymbolList[] { 195 chromA, chromB}); 196 197 return result; 198 } else return null; 199 } 200 201 /** 202 * generate a pair of locations where the crossover should be made do this in 203 * two steps for retracabilities sake. the location array will always list the 204 * earlier position first. 205 * 206 * @param chromlength 207 * the lenghth of the chromosomes, needed to decide if the 208 * probabilityarray needs to be extended. 209 * @return an int[] containing two positions on the chomosome 210 */ 211 private synchronized int[] generateCrossoverLocations(int chromlength) { 212 Random n = new Random(); 213 int[] locations = new int[2]; 214 // step 1 create an array containing a value for every position 215 // on the chromosome. The higher the number the more likely it 216 // will be choosen as crossoverposition. 217 double[] crosses = new double[chromlength]; 218 int maxIndex = getCrossOverProbs().length - 1; 219 220 for (int i = 1; i <= chromlength; i++) { 221 int index = Math.min(i - 1, maxIndex); 222 double crossProb = getCrossOverProbs()[index] - n.nextDouble(); 223 if (crossProb >= 0) { 224 crosses[i - 1] = crossProb; 225 } else { 226 crosses[i - 1] = 0; 227 } 228 } 229 230 // step 2 find the two highest numbers and return their positions 231 double highest = 0; 232 double second = 0; 233 for (int j = 0; j < crosses.length; j++) { 234 double current = crosses[j]; 235 if (current > second) { 236 // allways put highest number in pos[1], second in pos[0] 237 if (current > highest) { 238 locations[0] = locations[1]; 239 second = highest; 240 locations[1] = j + 1; 241 highest = current; 242 } else { 243 second = current; 244 locations[0] = j + 1; 245 } 246 247 } 248 } 249 // switch places so the lower number is in pos[0] 250 if (locations[0] > locations[1]) { 251 int temp = locations[0]; 252 locations[0] = locations[1]; 253 locations[1] = temp; 254 } 255 256 return locations; 257 } 258 259}