001 /*
002 * SimuCS - Simulator to use with Classifier Systems
003 * MSc project - Oxford University
004 * by Benoit Isaac - Summer 2005
005 */
006
007 package simuLCS;
008 import java.util.Arrays;
009 import java.util.Iterator;
010 import java.util.Vector;
011
012 /**
013 * Implements the main functions of our ZCS.
014 * A few lines of code (roulette Wheel, creation of the Match Set using covering) below draw inspiration from the freely available XCSJava
015 * by Martin V. Butz
016 * @author Benoit, Martin V. Butz
017 */
018 public class ZClassifierSet extends ClassifierSet {
019
020 private static final int maxPopSize = ZCSConfig.maxPopSize;
021
022 /**
023 * Creates a new, empty population. (With an empty Set)
024 *
025 * @see ClassifierSet
026 */
027 public ZClassifierSet(Template t) {
028 this(t, false);
029 }
030
031 /**
032 * Creates an empty set that can be ranked if <code>isSort = true</code>
033 * @param t
034 * @param isSort
035 */
036 public ZClassifierSet(Template t, boolean isSort) {
037 super(t, isSort);
038 }
039
040 /**
041 * Creates a Set with <code>initialSize</code> random classifiers
042 * @param t
043 * @param initialSize
044 */
045 public ZClassifierSet(Template t, int initialSize) {
046 this(t);
047 for (int i = 0; i < initialSize; i++)
048 addClassifier(
049 new ZClassifier(t.getNbBitsCondition(), t.getNbBitsAction()));
050 }
051
052 /**
053 * Creates a ZClassifierSet with <code>initialSize</code> copies of
054 * the classifier <code>init</code>.
055 * @param classifier
056 */
057 public ZClassifierSet(Template t, int initialSize, ZClassifier init) {
058 this(t);
059 for (int i = 0; i < initialSize; i++)
060 addClassifier(new ZClassifier(init));
061 }
062
063 /**
064 * Constructs a match set out of the population.
065 * After the creation, it is checked if the match set covers all possible actions
066 * in the environment. If one or more actions are not present, covering occurs, generating the missing action(s). If maximal
067 * population size is reached when covering, deletion occurs.
068 * <i>Modified to be used with a <code>Set</code> implementation.</i>
069 * @param state the situation that shoud satisfy the conditions of the classifiers
070 * @param pop the Population in which the new classifiers should be inserted
071 */
072 public ZClassifierSet getMatchSet(String state, ZClassifierSet pop) {
073
074 ZClassifierSet satisfiedClassifiers =
075 new ZClassifierSet(this.getTemplate(), false);
076 int nbOfActions = getTemplate().getNbPossibleActions();
077
078 boolean[] actionCovered = new boolean[nbOfActions];
079 for (int i = 0; i < actionCovered.length; i++)
080 actionCovered[i] = false;
081
082 Iterator iter = getIterator();
083 ZClassifier cl;
084 while (iter.hasNext()) {
085 cl = (ZClassifier) iter.next();
086 if (cl.match(state)) {
087 satisfiedClassifiers.addClassifier(cl);
088 actionCovered[Utils.getValueFromBits(cl.getAction())] = true;
089 }
090 }
091
092 Vector v = new Vector();
093 // saving all the possible actions not yet covered in a vector
094 for (int i = 0; i < actionCovered.length; i++) {
095 if (!actionCovered[i]) // action not covered
096 v.addElement(new Integer(i));
097 }
098 int nbActionsStillToCover =
099 getTemplate().getMinNbActions() - (nbOfActions - v.size());
100 if (nbActionsStillToCover > 0) { // not enough actions covered
101 // generate covering classifier for a randomly selected action
102 // among those still not covered
103 int curActToCover;
104 for (int j = 0; j < nbActionsStillToCover; j++) {
105 curActToCover = (int) ((double) ZCSConfig.drand() * v.size());
106 String act =
107 Utils.getBitsFromValue(
108 ((Integer) v.elementAt(curActToCover)).intValue(),
109 getTemplate().getNbBitsAction());
110 // creation of a new Classifier covering this action and this situation
111
112 double strength = pop.getAverageStrength();
113 ZClassifier newCl = new ZClassifier(strength, state, act);
114 if (Config.PRINT_MODE > 5) {
115 System.out.println("Covering ! New: " + newCl);
116 }
117 // TODO check that we don't remove a previously created by covering ???
118 pop.addClassifierMaintainingSize(newCl);
119 satisfiedClassifiers.addClassifier(newCl);
120 v.removeElementAt(curActToCover);
121 }
122 }
123 return (ZClassifierSet) satisfiedClassifiers;
124
125 }
126
127 /**
128 * Constructs a random action set out of the given match set.
129 * @param nbOfClassifiers the number of classifiers to select
130 */
131
132 public ZClassifierSet getRandomActionSet(int nbOfClassifiers) {
133 ZClassifierSet result;
134 if (getSize() < nbOfClassifiers) {
135 result = this;
136 } else {
137 result = new ZClassifierSet(getTemplate(), false);
138 // we have to select nbOfClassifiers Classifier among those here.
139 Vector v = new Vector(this.classifiers);
140 int curClassToSelect;
141 for (int j = 0; j < nbOfClassifiers; j++) {
142 curClassToSelect =
143 (int) ((double) ZCSConfig.drand() * v.size());
144 result.addClassifier(
145 (ZClassifier) v.elementAt(curClassToSelect));
146 v.removeElementAt(curClassToSelect);
147 }
148
149 }
150 return result;
151 }
152
153 /**
154 * By convention, the default Action Set is generated with a Roulette Wheel
155 * @see ClassifierSet#getActionSet()
156 */
157 public ClassifierSet getActionSet() {
158 // System.out.println("Call to getRWActionSet");
159 return getRWActionSet(1);
160 }
161
162 /**
163 * Get an Action Set from the current set, by selecting <code>nbOfClassifiers</code>
164 * using the Roulette Wheel
165 * @param nbOfClassifiers
166 * @return
167 */
168 public ZClassifierSet getRWActionSet(int nbOfClassifiers) {
169 ZClassifierSet result;
170 if (getSize() < nbOfClassifiers) {
171 result = this;
172 } else {
173 result = new ZClassifierSet(getTemplate(), false);
174 // we have to select nbOfClassifiers Classifiers among those here.
175 // using Roulette Wheel Selection
176 ZClassifier toAdd;
177 for (int i = 0; i < nbOfClassifiers; i++) {
178 toAdd = selectClassifierRW();
179 while (result.contains(toAdd))
180 toAdd = selectClassifierRW();
181 result.addClassifier(toAdd);
182 }
183
184 }
185 return result;
186 }
187
188 /**
189 * Updates the Set, with the technique we designed
190 * @param reward
191 * @param maxReward
192 */
193 public void updateSet(double reward, double maxReward) {
194 double bucket = 0.;
195 double giveToBucket;
196 Iterator iter = getIterator();
197 ZClassifier current;
198 // each classifier gives a part to the bucket ( beta * strength)
199 while (iter.hasNext()) {
200 current = (ZClassifier) iter.next();
201 synchronized (current) {
202 giveToBucket = ZCSConfig.beta * current.getStrength();
203 // the strength should not be decreased if we can get the maximum
204 // reward (the rule is perfect, it should not be punished
205 if (giveToBucket
206 > (maxReward / ((1 - ZCSConfig.gamma) * getSize())))
207 giveToBucket =
208 (maxReward / ((1 - ZCSConfig.gamma) * getSize()));
209 bucket += giveToBucket;
210 current.addStrength(-giveToBucket);
211 }
212 }
213 // each classifier get a reward
214 iter = getIterator();
215 // double toAddToEach = (ZCSConfig.beta * reward + ZCSConfig.gamma * bucket)/getSize();
216 double toAddToEach = (reward + ZCSConfig.gamma * bucket) / getSize();
217
218 while (iter.hasNext()) {
219 current = (ZClassifier) iter.next();
220 synchronized (current) {
221 current.addStrength(toAddToEach);
222 if (Config.PRINT_MODE > 4
223 || (toAddToEach > 3000 && Config.PRINT_MODE > 2)) {
224 System.out.println(
225 "-Classifier :"
226 + current
227 + " added to S:"
228 + toAddToEach);
229 }
230 }
231 }
232 }
233
234 /**
235 * @return
236 */
237 private double getAverageStrength() {
238 double totalStrength = getSumStrength();
239 return (totalStrength / getSize());
240 }
241
242 private double getSumStrength() {
243 double totalStrength = 0.;
244 for (Iterator i = getIterator(); i.hasNext();)
245 totalStrength += ((ZClassifier) i.next()).getStrength();
246 return totalStrength;
247 }
248
249 /**
250 * Returns true if the specified action is covered in this set.
251 */
252 private boolean isActionCovered(String act) {
253 Iterator iter = getIterator();
254 Classifier current;
255 while (iter.hasNext()) {
256 current = (Classifier) iter.next();
257 if (current.getAction().equals(act))
258 return true;
259 }
260 return false;
261 }
262
263
264 /**
265 * The Genetic Algorithm for the ZCS.
266 */
267 public void runGA(int timeSteps, String state, ZClassifierSet pop) {
268 // Don't do a GA if the theta_GA threshold is not reached, yet
269 // if (getSize() == 0 || time - getTimeStampAverage() < ZCSConstants.theta_GA)
270 if (getSize() == 0 || ((timeSteps % ZCSConfig.theta_GA) != 0))
271 return;
272
273 if (Config.PRINT_MODE > 3) {
274 System.out.println(timeSteps + "->GA Launched.");
275 }
276
277 // Select two Classifiers with roulette Wheel Selection
278 ZClassifier cl1P, cl2P;
279 if (getSize() < 2) // not enough classifiers
280 return;
281 if (getSize() == 2) { // we take those 2
282 Iterator iter = getIterator();
283 cl1P = (ZClassifier) iter.next();
284 cl2P = (ZClassifier) iter.next();
285 } else {
286 cl1P = selectClassifierRW();
287 cl2P = selectClassifierRW();
288 while (cl1P.equals(cl2P)) // the second one has to be different
289 cl2P = selectClassifierRW();
290 }
291
292 if (Config.PRINT_MODE > 4) {
293 System.out.println("Selected : " + cl1P);
294 System.out.println("Selected : " + cl2P);
295 }
296
297
298 ZClassifier cl1 = new ZClassifier(cl1P);
299 ZClassifier cl2 = new ZClassifier(cl2P);
300 //Half of each parent's strength is deducted from the parent and assigned
301 // to its copy
302 // TODO put back the deduction !
303 // cl1P.setStrength(cl1P.getStrength() / 2);
304 cl1.setStrength(cl1P.getStrength() / 2);
305 // cl2P.setStrength(cl2P.getStrength() / 2);
306 cl2.setStrength(cl2P.getStrength() / 2);
307
308 if (cl1.onePointCrossover(cl2)) {
309 // update their strengths to the mean
310 double totalStrength = cl1.getStrength() + cl2.getStrength();
311 cl1.setStrength(totalStrength / 2);
312 cl2.setStrength(totalStrength / 2);
313 }
314
315 if (Config.PRINT_MODE > 4) {
316 System.out.println("After crossover : " + cl1);
317 System.out.println("After crossover : " + cl2);
318 }
319
320 if (state.equals("")) {
321 // we cannot apply a niche mutation since we don't know the current state
322 cl1.applyMutation(cl1.getAction().length());
323 cl2.applyMutation(cl2.getAction().length());
324 } else { // we can apply a niche mutation
325 cl1.applyMutation(state, cl1.getAction().length());
326 cl2.applyMutation(state, cl2.getAction().length());
327 }
328
329 if (Config.PRINT_MODE > 4) {
330 System.out.println("After mutation : " + cl1);
331 System.out.println("After mutation : " + cl2);
332 }
333
334 // insert the new classifiers in the population
335 pop.addClassifierMaintainingSize(cl1);
336 pop.addClassifierMaintainingSize(cl2);
337 }
338
339 /**
340 * Selects one classifier using roulette wheel selection according to the fitnesses
341 * of the classifiers.
342 */
343 private ZClassifier selectClassifierRW() {
344
345 if (getSize() == 0) {
346 System.out.println("ERROR [Roulette Wheel : empty set !]");
347 return null;
348 }
349 Iterator iter = getIterator();
350 ZClassifier current;
351 double sumStrengths = getSumStrength();
352 double myProbaToBeSelected;
353 double currentSum = 0.;
354
355 double choicePoint = ZCSConfig.drand();
356 while (iter.hasNext()) {
357 current = (ZClassifier) iter.next();
358 myProbaToBeSelected = current.getStrength() / sumStrengths;
359 currentSum += myProbaToBeSelected;
360 if (currentSum > choicePoint) {
361 // Roulette wheel designates this one
362 return current;
363 }
364 }
365 return null; // Problem occurred
366 }
367
368 /**
369 * Looks for an identical classifier in the population.
370 * @param newCl The new classifier.
371 * @return Returns the identical classifier if found, null otherwise.
372 */
373 private ZClassifier getIdenticalClassifier(ZClassifier newCl) {
374 Iterator iter = getIterator();
375 ZClassifier current;
376 while (iter.hasNext()) {
377 current = (ZClassifier) iter.next();
378 if (newCl.isIdentical(current))
379 return current;
380 }
381 return null;
382 }
383
384 /**
385 * Adds a classifier to the set.
386 * If the mamximum Population Size has been reached, a Classifier is deleted
387 * before adding this new one (using an inverse Roulette Wheel).
388 */
389 private void addClassifierMaintainingSize(ZClassifier classifier) {
390 while (getSize() + 1 > maxPopSize)
391 removeClassifierRW();
392 super.addClassifier(classifier);
393 }
394
395 /**
396 * Remove a classifier using probability proportional to the inverse
397 * of their strengths (inverse Roulette wheel)
398 *
399 */
400 private boolean removeClassifierRW() {
401
402 double sum = getSumStrength();
403 double sumParts = 0.;
404 Iterator iter = getIterator();
405 ZClassifier current;
406 double myPart, myProbaToBeSelected;
407 while (iter.hasNext()) {
408 current = (ZClassifier) iter.next();
409 myPart = sum / current.getStrength();
410 sumParts += myPart;
411 }
412
413 double choicePoint = ZCSConfig.drand();
414 iter = getIterator();
415 double currentSum = 0.;
416 while (iter.hasNext()) {
417 current = (ZClassifier) iter.next();
418 myPart = sum / current.getStrength();
419 myProbaToBeSelected = myPart / sumParts;
420 // System.out.println(current+" proba:"+myProbaToBeSelected);
421 currentSum += myProbaToBeSelected;
422 if (currentSum > choicePoint) {
423 // Roulette wheel designate this one
424 removeClassifier(current);
425 // System.out.println("To remove:"+current);
426 return true;
427 }
428 }
429 return false; // problem during the deletion
430 }
431
432 /**
433 * Removes the specified classifier from the population.
434 * @return true if the given classifier was found and removed; false if it was not found
435 */
436 private boolean removeClassifier(ZClassifier classifier) {
437 if (contains(classifier)) {
438 super.removeClassifier(classifier);
439 return true;
440 } else {
441 return false;
442 }
443 }
444
445 /**
446 * Returns an array with the classifier ranked according to their strength
447 * @param nbFromTop
448 * @return
449 */
450 public ZClassifier[] giveBestClassifiers(int nbFromTop) {
451 ZClassifier[] array = new ZClassifier[0];
452 array = (ZClassifier[]) this.classifiers.toArray(array);
453 Arrays.sort(array);
454 return array;
455 }
456
457
458
459 /**
460 * Prints to the console the <code>i</code> best classifiers of the population
461 * @param i
462 */
463 public void printBestInSet(int i) {
464 System.out.println("Averages:");
465 System.out.println(
466 "Strength: "
467 + (getAverageStrength())
468 + " Nb Classifiers: "
469 + (getSize()));
470 ZClassifier[] best = giveBestClassifiers(i);
471 for (int j = (best.length - i); j < best.length; j++)
472 best[j].printClassifier();
473
474 }
475
476 }