001 /**
002 * Copyright (C) 2007-2011, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program. If not, see <http://www.gnu.org/licenses/>.
018 */
019
020 package org.dllearner.algorithms.gp;
021
022 import java.util.LinkedList;
023 import java.util.List;
024 import java.util.Map;
025 import java.util.Random;
026 import java.util.SortedSet;
027 import java.util.TreeMap;
028
029 import org.dllearner.core.AbstractLearningProblem;
030 import org.dllearner.core.AbstractReasonerComponent;
031 import org.dllearner.core.ReasoningMethodUnsupportedException;
032 import org.dllearner.core.owl.ObjectAllRestriction;
033 import org.dllearner.core.owl.NamedClass;
034 import org.dllearner.core.owl.Nothing;
035 import org.dllearner.core.owl.Description;
036 import org.dllearner.core.owl.ObjectSomeRestriction;
037 import org.dllearner.core.owl.FlatABox;
038 import org.dllearner.core.owl.Individual;
039 import org.dllearner.core.owl.Intersection;
040 import org.dllearner.core.owl.Union;
041 import org.dllearner.core.owl.Negation;
042 import org.dllearner.core.owl.ObjectProperty;
043 import org.dllearner.core.owl.Thing;
044 import org.dllearner.learningproblems.PosNegLPStrict;
045 import org.dllearner.learningproblems.ScorePosNeg;
046 import org.dllearner.learningproblems.ScoreThreeValued;
047 import org.dllearner.reasoning.FastRetrieval;
048 import org.dllearner.reasoning.ReasonerType;
049 import org.dllearner.utilities.Helper;
050 import org.dllearner.utilities.datastructures.SortedSetTuple;
051
052
053 /**
054 * A utility class, which implements crossover, mutation and tree creation methods.
055 *
056 * Schwaechen: Der Code ist ziemlich komplex und die Performance nicht besonders gut,
057 * da oefter Baeume komplett neu erstellt statt geklont werden etc. Wenn der Code
058 * erstmal lauffaehig ist, dann kann man hier noch mit Optimierungen ansetzen.
059 *
060 * Notiz: Wenn man den einzelnen Knoten noch eine Stelligkeit zuweist, dann koennte
061 * man diese Klasse komplett generisch halten, d.h. unabhaengig davon, dass
062 * DLs gelernt werden sollen.
063 *
064 * @author Jens Lehmann
065 *
066 */
067 public class GPUtilities {
068
069 public static int fitnessEvaluations = 0;
070 public static int crossover = 0;
071 public static int mutation = 0;
072 public static int hillClimbing = 0;
073
074 private static Random rand = new Random();
075
076 private static ScorePosNeg calculateFitness(AbstractLearningProblem learningProblem, Description hypothesis) {
077 return calculateFitness(learningProblem, hypothesis, null);
078 }
079
080 // TODO: eventuell darueber nachdenken diese return-type-Sache zu entfernen
081 // Alternative: man bezieht sie in die zentralen Score-Berechnungen mit ein
082 // (macht aber nicht so viel Sinn, da man das bei richtigen Reasoning-Algorithmen
083 // ohnehin mit einer Erweiterung der Wissensbasis um die Inklusion Target SUBSETOF ReturnType
084 // erschlagen kann)
085 private static ScorePosNeg calculateFitness(AbstractLearningProblem learningProblem, Description hypothesis, Description adc) {
086 Description extendedHypothesis;
087
088 // return type temporarily disabled
089 // => it is probably more appropriate to have the
090 // number of superclasses of a target concept
091 // as parameter of the learning problem
092 //
093 // if (!Config.returnType.equals("")) {
094 // System.out.println("return type");
095 //
096 // Concept newRoot;
097 // if(Config.GP.useMultiStructures)
098 // newRoot = new MultiConjunction(new AtomicConcept(Config.returnType),hypothesis);
099 // else
100 // newRoot = new Conjunction(new AtomicConcept(Config.returnType),hypothesis);
101 // // parent wieder auf null setzen, damit es nicht inkonsistent wird
102 // // TODO: ist nicht wirklich elegant und auch inkompatibel mit
103 // // dem Hill-Climbing-Operator
104 // hypothesis.setParent(null);
105 // extendedHypothesis = newRoot;
106 // } else
107 extendedHypothesis = hypothesis;
108
109 ScorePosNeg score;
110 if(adc != null)
111 // TODO: ADC-Support
112 // score = learningProblem.computeScore(extendedHypothesis, adc);
113 throw new RuntimeException("ADC not supported");
114 else
115 score = (ScorePosNeg) learningProblem.computeScore(extendedHypothesis);
116
117 // System.out.println(hypothesis);
118 // System.out.println(score.getScore());
119
120 /*
121 if (Config.GP.adc)
122 scoreAdc = adc.computeScore();
123
124 if (Config.GP.adc)
125 score = extendedHypothesis.computeScore(scoreAdc.getDefPosSet(), scoreAdc
126 .getDefNegSet());
127 else
128 score = extendedHypothesis.computeScore();
129 */
130 /*
131 fitness = score.getScore() - 0.1 * hypothesis.getConceptLength();
132
133 if (Config.GP.adc)
134 fitness -= 0.1 * adc.getConceptLength();
135
136 // zus�tzliche Bestrafung f�r sehr lange Definitionen
137 if(hypothesis.getNumberOfNodes()>50)
138 fitness -= 10;
139 */
140 fitnessEvaluations++;
141
142 return score;
143 }
144
145 public static Program createProgram(AbstractLearningProblem learningProblem, Description mainTree) {
146 return new Program(calculateFitness(learningProblem, mainTree), mainTree);
147 }
148
149 private static Program createProgram(AbstractLearningProblem learningProblem, Description mainTree, Description adc) {
150 return new Program(calculateFitness(learningProblem, mainTree,adc), mainTree, adc);
151 }
152
153 /**
154 * Perform a point mutation on the given program.
155 * @param p The program to be mutated.
156 */
157 public static Program mutation(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, Program p) {
158 mutation++;
159 if(p.getAdc() != null) {
160 // TODO: hier kann man noch mehr Feinabstimmung machen, d.h.
161 // Mutation abh�ngig von Knotenanzahl
162 if(Math.random()<0.5) {
163 Description mainTree = mutation(learningProblem, rs, p.getTree(),true);
164 Description adc = p.getAdc();
165 ScorePosNeg score = calculateFitness(learningProblem,mainTree,adc);
166 return new Program(score, mainTree, adc);
167 }
168 else {
169 Description mainTree = p.getTree();
170 Description adc = mutation(learningProblem, rs, p.getAdc(),false);
171 ScorePosNeg score = calculateFitness(learningProblem,mainTree,adc);
172 return new Program(score, mainTree, adc);
173 }
174 } else {
175 Description tree = mutation(learningProblem, rs,p.getTree(),false);
176 ScorePosNeg score = calculateFitness(learningProblem, tree);
177 return new Program(score, tree);
178 }
179 }
180
181 private static Description mutation(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, Description tree, boolean useADC) {
182 // auch bei Mutation muss darauf geachtet werden, dass
183 // Baum nicht modifiziert wird (sonst w�rde man automatisch auch
184 // andere "selected individuals" modifizieren)
185 Description t = (Description) tree.clone();
186 // bis auf Klon Mutation genau wie vorher
187 int size = t.getNumberOfNodes();
188 // TODO: auch Mutationen von Einzelknoten erlauben
189 if (size > 1) {
190 /* alte Implementierung
191 int randNr = rand.nextInt(size) + 1;
192 Node st = t.getSubtree(randNr);
193 Node stParent = st.getParent();
194 stParent.getChildren().remove(st);
195 st.setParent(null);
196 // int subTreeSize = st.getNumberOfNodes();
197 // ProgramTree treeNew = createGrowRandomTree(subTreeSize);
198 // Point mutation
199 Node treeNew = createGrowRandomTree(3);
200 treeNew.setParent(stParent);
201 stParent.getChildren().add(treeNew);
202 */
203 // neue Implementierung
204 int randNr = rand.nextInt(size) + 1;
205 Description st = t.getSubtree(randNr);
206 Description stParent = st.getParent();
207 stParent.getChildren().remove(st);
208 Description treeNew = createGrowRandomTree(learningProblem, rs, 3, useADC);
209 stParent.addChild(treeNew);
210 } else
211 // return createLeafNode(useADC);
212 return pickTerminalSymbol(learningProblem,rs,useADC);
213 return t;
214 }
215
216 private static void swapSubtrees(Description t1, Description t2) {
217 if (t1.getParent() != null && t2.getParent() != null) {
218 // handling children
219 Description t1Parent = t1.getParent();
220 Description t2Parent = t2.getParent();
221 // t1 is first child
222 if (t1Parent.getChild(0).equals(t1))
223 t1Parent.getChildren().add(0, t2);
224 else
225 t1Parent.getChildren().add(1, t2);
226 // t2 is first child
227 if (t2Parent.getChild(0).equals(t2))
228 t2Parent.getChildren().add(0, t1);
229 else
230 t2Parent.getChildren().add(1, t1);
231 // remove old children
232 t1Parent.getChildren().remove(t1);
233 t2Parent.getChildren().remove(t2);
234
235 // handling parents
236 // ProgramTree tmp = t1Parent;
237 t1.setParent(t2Parent);
238 t2.setParent(t1Parent);
239 } else
240 throw new Error(
241 "Trees are not real subtrees (at least one of them is a root node).");
242 }
243
244 /**
245 * Perform crossover on two programs.
246 * @param p1 First parent.
247 * @param p2 Second parent.
248 * @return A two-element array containing the offpsring.
249 */
250 public static Program[] crossover(AbstractLearningProblem learningProblem, Program p1, Program p2) {
251 crossover++;
252 if(p1.getAdc() != null) {
253 Description[] pt;
254 Program result[] = new Program[2];
255
256 // es wird entweder ADC oder Hauptbaum einem Crossover
257 // unterzogen und dann ein neues Programm erstellt
258 if(Math.random()<0.5) {
259 pt = crossover(p1.getTree(), p2.getTree());
260 result[0] = createProgram(learningProblem, pt[0], p1.getAdc());
261 result[1] = createProgram(learningProblem, pt[1], p2.getAdc());
262 } else {
263 pt = crossover(p1.getAdc(), p2.getAdc());
264 result[0] = createProgram(learningProblem, p1.getTree(),pt[0]);
265 result[1] = createProgram(learningProblem, p2.getTree(),pt[1]);
266 }
267 return result;
268 } else {
269 Description[] pt = crossover(p1.getTree(), p2.getTree());
270 Program result[] = new Program[2];
271 result[0] = createProgram(learningProblem,pt[0]);
272 result[1] = createProgram(learningProblem,pt[1]);
273 return result;
274 }
275 }
276
277 private static Description[] crossover(Description tree1, Description tree2) {
278 Description tree1cloned = (Description) tree1.clone();
279 Description tree2cloned = (Description) tree2.clone();
280
281 Description[] results = new Description[2];
282 int rand1 = rand.nextInt(tree1.getNumberOfNodes());
283 int rand2 = rand.nextInt(tree2.getNumberOfNodes());
284 Description t1 = tree1cloned.getSubtree(rand1);
285 Description t2 = tree2cloned.getSubtree(rand2);
286
287 if (t1.isRoot() && !t2.isRoot()) {
288 Description t2Parent = t2.getParent();
289 // t2 is first child
290 if (t2Parent.getChild(0).equals(t2))
291 t2Parent.getChildren().add(0, t1);
292 else
293 t2Parent.getChildren().add(1, t1);
294 t2Parent.getChildren().remove(t2);
295 t1.setParent(t2Parent);
296
297 t2.setParent(null);
298 results[0] = t2;
299 results[1] = tree2cloned;
300 } else if (!t1.isRoot() && t2.isRoot()) {
301 Description t1Parent = t1.getParent();
302 // t2 is first child
303 if (t1Parent.getChild(0).equals(t1))
304 t1Parent.getChildren().add(0, t2);
305 else
306 t1Parent.getChildren().add(1, t2);
307 t1Parent.getChildren().remove(t1);
308 t2.setParent(t1Parent);
309
310 t1.setParent(null);
311 results[0] = tree1cloned;
312 results[1] = t1;
313 } else if (!t1.isRoot() && !t2.isRoot()) {
314 swapSubtrees(t1, t2);
315 results[0] = tree1cloned;
316 results[1] = tree2cloned;
317 } else {
318 results[0] = tree2cloned;
319 results[1] = tree1cloned;
320 }
321 return results;
322 }
323
324 // m�sste auch mit ADC funktionieren, da nur am Hauptbaum etwas
325 // ver�ndert wird
326 public static Program hillClimbing(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, Program p) {
327 hillClimbing++;
328 // checken, ob Bedingungen f�r hill-climbing erf�llt sind
329 if(!rs.getReasonerType().equals(ReasonerType.FAST_RETRIEVAL)
330 || !(p.getScore() instanceof ScoreThreeValued)) {
331 throw new Error("Hill climbing can only be used with the fast-retrieval-algorithm on a three valued learning problem.");
332 }
333
334 // SortedSetTuple s = new SortedSetTuple(p.getScore().getDefPosSet(),p.getScore().getDefNegSet());
335 // Knoten kopieren, damit er sich nicht ver�ndert (es wird sonst der
336 // parent-Link ver�ndert)
337 Description treecloned = (Description) p.getTree().clone();
338 if(p.getAdc() != null)
339 return createProgram(learningProblem,hillClimbing(learningProblem,rs,treecloned,(ScoreThreeValued)p.getScore()),p.getAdc());
340 else
341 return createProgram(learningProblem,hillClimbing(learningProblem,rs,treecloned,(ScoreThreeValued)p.getScore()));
342 }
343
344 // one-step hill-climbing
345 // es ist zwar von der Implementierung her sehr aufw�ndig die besten
346 // Alternativen zu speichern und dann ein Element zuf�llig auszuw�hlen,
347 // aber w�rde man das nicht machen, dann w�re das ein starker Bias
348 // zu z.B. Disjunktion (weil die als erstes getestet wird)
349 private static Description hillClimbing(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, Description node, ScoreThreeValued score) {
350 SortedSetTuple<Individual> tuple = new SortedSetTuple<Individual>(score.getPosClassified(),score.getNegClassified());
351 SortedSetTuple<String> stringTuple = Helper.getStringTuple(tuple);
352 // FlatABox abox = FlatABox.getInstance();
353 Description returnNode = node;
354 // damit stellen wir sicher, dass nur Konzepte in die Auswahl
355 // genommen werden, die besser klassifizieren als das �bergebene
356 // Konzept (falls das nicht existiert, dann hill climbing = reproduction)
357 System.err.println("Next line needs fixing to work.");
358 System.exit(0);
359 // double bestScore = score.getScore()+Config.accuracyPenalty/2;
360 double bestScore = 0;
361 Map<Integer,List<String>> bestNeighbours = new TreeMap<Integer,List<String>>();
362 ScorePosNeg tmpScore;
363 SortedSetTuple<String> tmp, tmp2;
364 // FlatABox abox = ((FastRetrievalReasoner)learningProblem.getReasoner().getFastRetrieval().getAbox();
365 // FlatABox abox = Main.getFlatAbox();
366 FlatABox abox = null;
367 try {
368 abox = Helper.createFlatABox(rs);
369 } catch (ReasoningMethodUnsupportedException e) {
370 // TODO Auto-generated catch block
371 e.printStackTrace();
372 }
373
374 // TODO: testen, ob aktuelles Konzept zu speziell bzw. allgemein ist;
375 // dann kann man das effizienter implementieren
376
377 // Tests f�r Disjunktion bzw. Konjunktion
378 for(String concept : abox.concepts) {
379 // for(AtomicConcept ac : learningProblem.getReasoner().getAtomicConcepts())
380 tmp = new SortedSetTuple<String>(abox.atomicConceptsPos.get(concept),abox.atomicConceptsNeg.get(concept));
381 // TODO: double retrieval nutzen
382
383 tmp2 = FastRetrieval.calculateDisjunctionSets(stringTuple, tmp);
384 tmpScore = getScore(node.getLength()+2, learningProblem, rs, Helper.getIndividualSet(tmp2.getPosSet()),Helper.getIndividualSet(tmp2.getNegSet()));
385 if(tmpScore.getScoreValue()==bestScore)
386 bestNeighbours = updateMap(bestNeighbours,1,concept,false);
387 else if(tmpScore.getScoreValue()>bestScore)
388 bestNeighbours = updateMap(bestNeighbours,1,concept,true);
389
390 tmp2 = FastRetrieval.calculateConjunctionSets(stringTuple, tmp);
391 tmpScore = getScore(node.getLength()+2,learningProblem, rs, Helper.getIndividualSet(tmp2.getPosSet()),Helper.getIndividualSet(tmp2.getNegSet()));
392 if(tmpScore.getScoreValue()==bestScore)
393 bestNeighbours = updateMap(bestNeighbours,2,concept,false);
394 else if(tmpScore.getScoreValue()>bestScore)
395 bestNeighbours = updateMap(bestNeighbours,2,concept,true);
396 }
397
398 // Tests f�r All und Exists
399 for(String role : abox.roles) {
400 tmp = FastRetrieval.calculateAllSet(abox,role,stringTuple);
401 tmpScore = getScore(node.getLength()+2,learningProblem, rs, Helper.getIndividualSet(tmp.getPosSet()),Helper.getIndividualSet(tmp.getNegSet()));
402 if(tmpScore.getScoreValue()==bestScore)
403 bestNeighbours = updateMap(bestNeighbours,3,role,false);
404 else if(tmpScore.getScoreValue()>bestScore)
405 bestNeighbours = updateMap(bestNeighbours,3,role,true);
406
407 tmp = FastRetrieval.calculateExistsSet(abox,role,stringTuple);
408 tmpScore = getScore(node.getLength()+2,learningProblem, rs, Helper.getIndividualSet(tmp.getPosSet()),Helper.getIndividualSet(tmp.getNegSet()));
409 if(tmpScore.getScoreValue()==bestScore)
410 bestNeighbours = updateMap(bestNeighbours,4,role,false);
411 else if(tmpScore.getScoreValue()>bestScore)
412 bestNeighbours = updateMap(bestNeighbours,4,role,true);
413 }
414
415 // Gr��e bestimmen
416 int sizeSum1=0;
417 if(bestNeighbours.containsKey(1))
418 sizeSum1 += bestNeighbours.get(1).size();
419
420 int sizeSum2 = sizeSum1;
421 if(bestNeighbours.containsKey(2))
422 sizeSum2 += bestNeighbours.get(2).size();
423
424 int sizeSum3 = sizeSum2;
425 if(bestNeighbours.containsKey(3))
426 sizeSum3 += bestNeighbours.get(3).size();
427
428 int sizeSum4 = sizeSum3;
429 if(bestNeighbours.containsKey(4))
430 sizeSum4 += bestNeighbours.get(4).size();
431
432 // reproduction, falls nichts besseres gefunden wurde
433 if(sizeSum4==0)
434 return node;
435 else {
436 // zuf�llig eines der besten Elemente ausw�hlen
437 int nr = rand.nextInt(sizeSum4);
438 String name;
439 if(nr<sizeSum1) {
440 name = bestNeighbours.get(1).get(nr);
441 // returnNode = new Disjunction();
442 // returnNode.addChild(new AtomicConcept(name));
443 // returnNode.addChild(node);
444 // if(useMultiStructures)
445 returnNode = new Union(new NamedClass(name),node);
446 // else
447 // returnNode = new Disjunction(new AtomicConcept(name),node);
448 // wegen else if schlie�en sich die F�lle gegenseitig aus
449 } else if(nr<sizeSum2) {
450 name = bestNeighbours.get(2).get(nr-sizeSum1);
451 // returnNode = new Conjunction();
452 // returnNode.addChild(new AtomicConcept(name));
453 // returnNode.addChild(node);
454 // if(useMultiStructures)
455 returnNode = new Intersection(new NamedClass(name),node);
456 // else
457 // returnNode = new Conjunction(new AtomicConcept(name),node);
458 } else if(nr<sizeSum3) {
459 name = bestNeighbours.get(3).get(nr-sizeSum2);
460 // returnNode = new Exists(new AtomicRole(name));
461 // returnNode.addChild(node);
462 returnNode = new ObjectSomeRestriction(new ObjectProperty(name),node);
463 } else {
464 name = bestNeighbours.get(4).get(nr-sizeSum3);
465 // returnNode = new All(new AtomicRole(name));
466 // returnNode.addChild(node);
467 returnNode = new ObjectAllRestriction(new ObjectProperty(name),node);
468 }
469
470 return returnNode;
471 }
472 }
473
474 private static ScoreThreeValued getScore(int conceptLength, AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, SortedSet<Individual> posClassified, SortedSet<Individual> negClassified) {
475 // es muss hier die Helper-Methode verwendet werden, sonst werden
476 // Individuals gel�scht !!
477 SortedSet<Individual> neutClassified = Helper.intersection(rs.getIndividuals(),posClassified);
478 // learningProblem.getReasoner().getIndividuals();
479 // neutClassified.retainAll(posClassified);
480 neutClassified.retainAll(negClassified);
481 PosNegLPStrict lp = (PosNegLPStrict)learningProblem;
482 return new ScoreThreeValued(conceptLength, lp.getAccuracyPenalty(), lp.getErrorPenalty(), lp.isPenaliseNeutralExamples(), lp.getPercentPerLengthUnit(), posClassified, neutClassified, negClassified, lp.getPositiveExamples(),lp.getNeutralExamples(),lp.getNegativeExamples());
483 }
484
485 // aktualisiert die besten Knoten
486 // Integer: 1 Disjunktion, 2 Konjunktion, 3 Exists, 4 All
487 // Name: Name des Konzepts bzw. der Rolle
488 // clear-Flag ist true, falls neuer Nachbar besser als die bisherigen ist und
489 // false, falls er gleich gut ist
490 private static Map<Integer,List<String>> updateMap(Map<Integer,List<String>> bestNeighbours, Integer cat, String name, boolean clear) {
491 Map<Integer,List<String>> returnMap;
492 List<String> set;
493 if(clear) {
494 returnMap = new TreeMap<Integer,List<String>>();
495 set = new LinkedList<String>();
496 set.add(name);
497 returnMap.put(cat,set);
498 } else {
499 returnMap = bestNeighbours;
500 if(bestNeighbours.containsKey(cat)) {
501 bestNeighbours.get(cat).add(name);
502 } else {
503 set = new LinkedList<String>();
504 set.add(name);
505 returnMap.put(cat,set);
506 }
507 }
508 return returnMap;
509 }
510
511 private static Description pickTerminalSymbol(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, boolean useADC) {
512 // FlatABox abox = FlatABox.getInstance();
513 int nr;
514 int nrOfConcepts = rs.getNamedClasses().size();
515
516 // ein Blattknoten kann folgendes sein:
517 // Top, Bottom, Konzept => alles am Besten gleichwahrscheinlich
518 if(useADC)
519 nr = rand.nextInt(3+nrOfConcepts);
520 else
521 nr = rand.nextInt(2+nrOfConcepts);
522
523 if(nr==0)
524 return new Thing();
525 else if(nr==1)
526 return new Nothing();
527 // die Zahl kann nur vorkommen, wenn ADC aktiviert ist
528 else if(nr==2+nrOfConcepts) {
529 // System.out.println("== ADC 2 ==");
530 return new ADC();
531 }
532 else
533 return (NamedClass) rs.getAtomicConceptsList().get(nr-2).clone();
534 }
535
536 // Funktion nach Umstelllung der Konstruktoren nicht mehr ben�tigt
537 /*
538 private static Concept pickFunctionSymbol() {
539 FlatABox abox = FlatABox.getInstance();
540 int numberOfRoles = abox.roles.size();
541 int nr = rand.nextInt(3+2*numberOfRoles);
542
543 if(nr==0)
544 return new Disjunction();
545 else if(nr==1)
546 return new Conjunction();
547 else if(nr==2)
548 return new Negation();
549 else if(nr - 3 < numberOfRoles)
550 return new Exists(new AtomicRole(abox.getRole(nr-3)));
551 else
552 return new All(new AtomicRole(abox.getRole(nr-3-numberOfRoles)));
553 }
554 */
555
556 /*
557 private static Concept pickAlphabetSymbol(boolean useADC) {
558 FlatABox abox = FlatABox.getInstance();
559 int numberOfConcepts = abox.concepts.size();
560 int numberOfRoles = abox.roles.size();
561 int numberOfAlphabetSymbols = numberOfConcepts + 2*numberOfRoles + 5;
562 if(useADC)
563 numberOfAlphabetSymbols += 1;
564
565 int nr = rand.nextInt(numberOfAlphabetSymbols);
566
567 if(nr==0)
568 return new Top();
569 else if(nr==1)
570 return new Bottom();
571 // ADC bekommt die h�chste Nummer, die nur in diesem Fall m�glich ist
572 else if(nr==numberOfConcepts + 2*numberOfRoles + 5)
573 return new ADC();
574 else if(nr>=2 && nr < numberOfConcepts+2)
575 return new AtomicConcept(abox.getConcept(nr-2));
576 else if(nr==numberOfConcepts+2)
577 return new Conjunction();
578 else if(nr==numberOfConcepts+3)
579 return new Disjunction();
580 else if(nr==numberOfConcepts+4)
581 return new Negation();
582 else if(nr>=numberOfConcepts+5 && nr<numberOfConcepts+5+numberOfRoles)
583 return new Exists(new AtomicRole(abox.getRole(nr-numberOfConcepts-5)));
584 else
585 return new All(new AtomicRole(abox.getRole(nr-numberOfConcepts-5-numberOfRoles)));
586 }
587 */
588
589 /*
590 private static Concept createNonLeafNodeEqualProp() {
591 FlatABox abox = FlatABox.getInstance();
592 int numberOfRoles = abox.roles.size();
593 int nr = rand.nextInt(3+2*numberOfRoles);
594
595 if(nr==0)
596 return new Disjunction();
597 else if(nr==1)
598 return new Conjunction();
599 else if(nr==2)
600 return new Negation();
601 else if(nr - 3 < numberOfRoles)
602 return new Exists(new AtomicRole(abox.getRole(nr-3)));
603 else
604 return new All(new AtomicRole(abox.getRole(nr-3-numberOfRoles)));
605 }
606 */
607
608 /* BUG: erzeugt kein NOT
609 private static Node createNonLeafNode() {
610 // ein Nichtblattknoten kann folgendes sein:
611 // Existenz- oder Allquantor mit Rollenname,
612 // Disjunktion, Konjunktion
613 // => hier muss Disjunktion und Konjunktion wahrscheinlicher sein als
614 // ein Quantor+Rollenname => am Besten in einer ersten Stufe entweder
615 // Disjunktion, Konjunktion, Existenzquantor oder Allquantor auswählen
616 FlatABox abox = FlatABox.getInstance();
617 int nr = rand.nextInt(4);
618 if(nr==0)
619 return new Disjunction();
620 else if(nr==1)
621 return new Conjunction();
622 else {
623 // Rollenname generieren
624 int nr2 = rand.nextInt(abox.roles.size());
625 // Existenz- oder Allquantor
626 // TODO: auch hier Performance verbessern, indem toArray() nur
627 // einmal ausgeführt wird
628 if(nr==3)
629 return new Exists((String)abox.roles.toArray()[nr2]);
630 else
631 return new All((String)abox.roles.toArray()[nr2]);
632 }
633 }
634 */
635
636 /**
637 * Create a program using the full method.
638 * @param depth Depth of the tree.
639 * @return The created program.
640 */
641 public static Program createFullRandomProgram(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, int depth, boolean adc) {
642 if(adc) {
643 // erster Baum Hauptbaum, zweiter Baum ADC
644 return createProgram(learningProblem, createFullRandomTree(learningProblem, rs, depth, true),
645 createFullRandomTree(learningProblem, rs, depth, false));
646 }
647 else
648 return createProgram(learningProblem, createFullRandomTree(learningProblem, rs, depth, false));
649 }
650
651 private static Description createFullRandomTree(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, int depth, boolean useADC) {
652 // FlatABox abox = FlatABox.getInstance();
653 int numberOfRoles = rs.getObjectProperties().size(); // abox.roles.size();
654
655 if (depth > 1) {
656 int nr = rand.nextInt(3+2*numberOfRoles);
657 // System.out.println(nr);
658 // Node node = createNonLeafNodeEqualProp();
659 // Concept node = pickFunctionSymbol();
660 Description child1 = createFullRandomTree(learningProblem, rs, depth-1, useADC);
661 if(nr == 0 || nr == 1) {
662 Description child2 = createFullRandomTree(learningProblem, rs, depth-1, useADC);
663 if(nr == 0) {
664 // if(useMultiStructures)
665 return new Union(child1,child2);
666 // else
667 // return new Disjunction(child1,child2);
668 } else {
669 // if(useMultiStructures)
670 return new Intersection(child1, child2);
671 // else
672 // return new Conjunction(child1, child2);
673 }
674 } else if(nr==2) {
675 return new Negation(child1);
676 } else if(nr - 3 < numberOfRoles)
677 return new ObjectSomeRestriction(rs.getAtomicRolesList().get(nr-3),child1);
678 else
679 return new ObjectAllRestriction(rs.getAtomicRolesList().get(nr-3-numberOfRoles),child1);
680
681 /*
682 if(node instanceof Disjunction || node instanceof Conjunction) {
683 node.addChild(createFullRandomTree(depth-1, useADC));
684 node.addChild(createFullRandomTree(depth-1, useADC));
685 }
686 if(node instanceof Exists || node instanceof All || node instanceof Negation) {
687 node.addChild(createFullRandomTree(depth-1, useADC));
688 }
689 */
690 // return node;
691 } else {
692 // return createLeafNode(useADC);
693 return pickTerminalSymbol(learningProblem, rs, useADC);
694 }
695 }
696
697 /**
698 * Create a program using the grow method.
699 * @param depth The maximum depth of the program tree.
700 * @return The created program.
701 */
702 public static Program createGrowRandomProgram(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, int depth, boolean adc) {
703 if(adc) {
704 // erster Baum Hauptbaum, zweiter Baum ADC
705 return createProgram(learningProblem, createGrowRandomTree(learningProblem,rs,depth,true),
706 createGrowRandomTree(learningProblem,rs,depth,false));
707 }
708 else
709 return createProgram(learningProblem, createGrowRandomTree(learningProblem, rs, depth,false));
710 }
711
712 public static Description createGrowRandomTree(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs, int depth, boolean useADC) {
713 /*
714 private static Concept pickAlphabetSymbol(boolean useADC) {
715 FlatABox abox = FlatABox.getInstance();
716 int numberOfConcepts = abox.concepts.size();
717 int numberOfRoles = abox.roles.size();
718 int numberOfAlphabetSymbols = numberOfConcepts + 2*numberOfRoles + 5;
719 if(useADC)
720 numberOfAlphabetSymbols += 1;
721
722 int nr = rand.nextInt(numberOfAlphabetSymbols);
723
724 if(nr==0)
725 return new Top();
726 else if(nr==1)
727 return new Bottom();
728 // ADC bekommt die h�chste Nummer, die nur in diesem Fall m�glich ist
729 else if(nr==numberOfConcepts + 2*numberOfRoles + 5)
730 return new ADC();
731 else if(nr>=2 && nr < numberOfConcepts+2)
732 return new AtomicConcept(abox.getConcept(nr-2));
733 else if(nr==numberOfConcepts+2)
734 return new Conjunction();
735 else if(nr==numberOfConcepts+3)
736 return new Disjunction();
737 else if(nr==numberOfConcepts+4)
738 return new Negation();
739 else if(nr>=numberOfConcepts+5 && nr<numberOfConcepts+5+numberOfRoles)
740 return new Exists(new AtomicRole(abox.getRole(nr-numberOfConcepts-5)));
741 else
742 return new All(new AtomicRole(abox.getRole(nr-numberOfConcepts-5-numberOfRoles)));
743 }
744 */
745
746 // FlatABox abox = FlatABox.getInstance();
747 int numberOfConcepts = rs.getNamedClasses().size();
748 int numberOfRoles = rs.getObjectProperties().size();
749 // TODO: ev. gröÃere Wahrscheinlichkeit für Konjunktion/Disjunktion (?),
750 // mit gröÃerer Konzept-, und Rollenanzahl kommen die sonst kaum noch vor
751 int numberOfAlphabetSymbols = numberOfConcepts + 2*numberOfRoles + 5; //7;// 5;
752 if(useADC)
753 numberOfAlphabetSymbols += 1;
754
755 int nr = rand.nextInt(numberOfAlphabetSymbols);
756
757 // TODO: ev. alternative Erzeugung erlauben, bei der alle Knoten
758 // gleichwahrscheinlich sind (ist hier eindeutig nicht der Fall);
759 // beide Varianten haben Vor- und Nachteile
760 if (depth > 1) {
761 // TODO: ev, sollte man diese Wahrsceinlichkeit konfigurierbar machen
762 // 0.5 sieht auf den ersten Blick vern�nftig aus, aber bedeutet auch, dass
763 // 50% aller B�ume Tiefe 1 haben, d.h. B�ume nicht sehr tief werden
764
765 // ALTER CODE
766 // if(rand.nextDouble()>=0.5) // >=0.5)
767 // return createLeafNode(useADC);
768 //else {
769 // Node node = createNonLeafNodeEqualProp();
770 // if(node instanceof Disjunction || node instanceof Conjunction) {
771 // node.addChild(createGrowRandomTree(depth-1, useADC));
772 // node.addChild(createGrowRandomTree(depth-1, useADC));
773 // }
774 // if(node instanceof Exists || node instanceof All || node instanceof Negation) {
775 // node.addChild(createGrowRandomTree(depth-1, useADC));
776 // }
777 // return node;
778 // }
779
780 // NEUER CODE
781 // Concept node = pickAlphabetSymbol(useADC);
782
783 if(nr==0)
784 return new Thing();
785 else if(nr==1)
786 return new Nothing();
787 // ADC bekommt die h�chste Nummer, die nur in diesem Fall m�glich ist
788 else if(nr==numberOfConcepts + 2*numberOfRoles + 5)
789 return new ADC();
790 else if(nr>=2 && nr < numberOfConcepts+2)
791 return (NamedClass)rs.getAtomicConceptsList().get(nr-2).clone();
792 else if(nr==numberOfConcepts+2) {
793 // if(useMultiStructures)
794 return new Intersection(createGrowRandomTree(learningProblem, rs, depth-1, useADC),createGrowRandomTree(learningProblem, rs, depth-1, useADC));
795 // else
796 // return new Conjunction(createGrowRandomTree(learningProblem, depth-1, useADC),createGrowRandomTree(learningProblem, depth-1, useADC));
797 } else if(nr==numberOfConcepts+3) {
798 // if(useMultiStructures)
799 return new Union(createGrowRandomTree(learningProblem, rs, depth-1, useADC),createGrowRandomTree(learningProblem, rs, depth-1, useADC));
800 // else
801 // return new Disjunction(createGrowRandomTree(learningProblem, depth-1, useADC),createGrowRandomTree(learningProblem, depth-1, useADC));
802 } else if(nr==numberOfConcepts+4)
803 return new Negation(createGrowRandomTree(learningProblem, rs, depth-1, useADC));
804 else if(nr>=numberOfConcepts+5 && nr<numberOfConcepts+5+numberOfRoles)
805 return new ObjectSomeRestriction(rs.getAtomicRolesList().get(nr-numberOfConcepts-5),createGrowRandomTree(learningProblem, rs, depth-1, useADC));
806 else
807 return new ObjectAllRestriction(rs.getAtomicRolesList().get(nr-numberOfConcepts-5-numberOfRoles),createGrowRandomTree(learningProblem, rs, depth-1, useADC));
808
809 /*
810 if(node instanceof Disjunction || node instanceof Conjunction) {
811 node.addChild(createGrowRandomTree(depth-1, useADC));
812 node.addChild(createGrowRandomTree(depth-1, useADC));
813 }
814 if(node instanceof Exists || node instanceof All || node instanceof Negation) {
815 node.addChild(createGrowRandomTree(depth-1, useADC));
816 }
817 */
818 // return node;
819 } else {
820 // return createLeafNode(useADC);
821 return pickTerminalSymbol(learningProblem, rs, useADC);
822 }
823 }
824
825 public static void checkPrograms(Program[] progs) {
826 for(Program prog : progs) {
827 GPUtilities.checkProgram(prog);
828 }
829 }
830
831 public static boolean checkProgram(Program prog) {
832 return checkTree(prog.getTree(), true);
833 }
834
835 public static boolean checkTree(Description node, boolean isRootNode) {
836 if(isRootNode && node.getParent()!=null) {
837 System.out.println("inconsistent root");
838 return false;
839 }
840
841 // Kinder �berpr�fen
842 for(Description child : node.getChildren()) {
843 if(!child.getParent().equals(node)) {
844 System.out.println("inconsistent tree " + node + " (child " + child + ")");
845 return false;
846 }
847 }
848
849 return true;
850 }
851 }