Context Navigation

source: branches/OKBJavaConnector/ECJClient/src/ec/app/edge/Edge.java @ 10216

Visit:

Last change on this file since 10216 was 6152, checked in by bfarka, 14 years ago
added ecj and custom statistics to communicate with the okb services #1441
File size: 22.8 KB

Line
1	/*
2	Copyright 2006 by Sean Luke
3	Licensed under the Academic Free License version 3.0
4	See the file "LICENSE" for more information
5	*/
6
7
8	package ec.app.edge;
9	import ec.util.*;
10	import java.io.*;
11	import java.util.*;
12	import java.util.zip.*;
13	import ec.*;
14	import ec.gp.*;
15	import ec.gp.koza.*;
16	import ec.simple.*;
17
18	/*
19	* Edge.java
20	*
21	* Created: Mon Nov 1 15:46:19 1999
22	* By: Sean Luke
23	*/
24
25	/**
26	* Edge implements the Symbolic Edge problem.
27	*
28	<p><b>Parameters</b><br>
29	<table>
30	<tr><td valign=top><i>base</i>.<tt>data</tt><br>
31	<font size=-1>classname, inherits or == ec.app.edge.EdgeData</font></td>
32	<td valign=top>(the class for the prototypical GPData object for the Edge problem)</td></tr>
33	</table>
34
35	<p><b>Parameter bases</b><br>
36	<table>
37	<tr><td valign=top><i>base</i>.<tt>data</tt></td>
38	<td>species (the GPData object)</td></tr>
39	</table>
40	*
41	* @author Sean Luke
42	* @version 1.0
43	*/
44
45	public class Edge extends GPProblem implements SimpleProblemForm
46	{
47	public static final String P_GENERALIZE = "generalize";
48	public static final String P_ALLPOS = "allpos";
49	public static final String P_ALLNEG = "allneg";
50	public static final String P_TESTPOS = "testpos";
51	public static final String P_TESTNEG = "testneg";
52	public static final String P_MAXTEST = "maxtest";
53
54	public static final int MIN_ARRAY_SIZE = 64;
55
56	// reading states (BAD is initial state)
57	public static final int BAD = 0;
58	public static final int READING0 = 1;
59	public static final int READING1 = 2;
60	public static final int EPSILON = 3;
61
62	// we'll need to deep clone this one though.
63	public EdgeData input;
64
65	// building graph
66	public boolean[] start;
67	public boolean[] accept;
68	public int numNodes;
69	public int[] from;
70	public int[] to;
71	public int[] reading;
72	public int numEdges;
73
74	// adjacency lists
75	public int[][] reading1;
76	public int[] reading1_l;
77	public int[][] reading0;
78	public int[] reading0_l;
79	public int[][] epsilon;
80	public int[] epsilon_l;
81
82	// positive test
83	public boolean[][] posT;
84	// negative test
85	public boolean[][] negT;
86	// positive all
87	public boolean[][] posA;
88	// negative all
89	public boolean[][] negA;
90
91	// testing
92	public boolean[] state1;
93	public boolean[] state2;
94
95	// generalize?
96	public boolean generalize;
97
98	public Object clone()
99	{
100	// we don't need to copy any of our arrays, they're null until
101	// we actually start using them.
102
103	Edge myobj = (Edge) (super.clone());
104
105	// we also don't need to clone the positive/negative
106	// examples, since they don't change through the course
107	// of our run (I hope!) Otherwise we'd need to clone them
108	// here.
109
110	// clone our data object
111	myobj.input = (EdgeData)(input.clone());
112	return myobj;
113	}
114
115	public static String fill(int num, char c)
116	{
117	char[] buf = new char[num];
118	for(int x=0;x<num;x++) buf[x]=c;
119	return new String(buf);
120	}
121
122	public static final int J_LEFT = 0;
123	public static final int J_RIGHT = 1;
124	public static final int J_CENTER = 2;
125	public static String justify(final String s, final int len, final int justification)
126	{
127	int size = len - s.length();
128	if (size<0) size=0;
129	switch(justification)
130	{
131	case J_LEFT:
132	return s + fill(size,' ');
133	case J_RIGHT:
134	return fill(size,' ') + s;
135	default: // (J_CENTER)
136	return fill(size/2,' ') + s + fill(size-(size/2),' ');
137	}
138	}
139
140	public String printCurrentNFA()
141	{
142	int strsize = String.valueOf(numNodes).length();
143	String str = "";
144	for(int x=0;x<numNodes;x++)
145	{
146	str += justify(String.valueOf(x),strsize,J_RIGHT) + " " +
147	(start[x] ? "S" : " ") + (accept[x] ? "A" : " ") +
148	" -> ";
149
150	if (reading0_l[x]>0)
151	{
152	str += "(0:";
153	for(int y=0;y<reading0_l[x];y++)
154	str += ((y>0 ? "," : "") + String.valueOf(reading0[x][y]));
155	str += ") ";
156	}
157
158	if (reading1_l[x]>0)
159	{
160	str += "(1:";
161	for(int y=0;y<reading1_l[x];y++)
162	str += ((y>0 ? "," : "") + String.valueOf(reading1[x][y]));
163	str += ") ";
164	}
165
166	if (epsilon_l[x]>0)
167	{
168	str += "(e:";
169	for(int y=0;y<epsilon_l[x];y++)
170	str += ((y>0 ? "," : "") + String.valueOf(epsilon[x][y]));
171	str += ")";
172	}
173	str += "\n";
174	}
175	return str;
176	}
177
178	public boolean[][] restrictToSize(int size, boolean[][]cases, EvolutionState state, int thread)
179	{
180	int csize = cases.length;
181	if (csize < size) return cases;
182
183	Hashtable hash = new Hashtable();
184	for(int x=0;x<size;x++)
185	{
186	while(true)
187	{
188	boolean[] b = cases[state.random[thread].nextInt(csize)];
189	if (!hash.contains(b)) { hash.put(b,b); break; }
190	}
191	}
192
193	boolean[][] newcases = new boolean[size][];
194	Enumeration e = hash.keys();
195	for(int x=0;x<size;x++)
196	{
197	newcases[x] = (boolean[])(e.nextElement());
198	}
199
200	// sort the cases -- amazing, but hashtable doesn't always
201	// return the same ordering, I guess that's because it does
202	// pointer hashing. Just want to guarantee replicability!
203
204	// is this correct?
205	java.util.Arrays.sort(newcases,
206	new java.util.Comparator()
207	{
208	public int compare(Object a, Object b)
209	{
210	boolean[] aa = (boolean[])a;
211	boolean[] bb = (boolean[])b;
212
213	for(int x=0;x<Math.min(aa.length,bb.length);x++)
214	if (!aa[x] && bb[x]) return -1;
215	else if (aa[x] && !bb[x]) return 1;
216	if (aa.length<bb.length) return -1;
217	if (aa.length>bb.length) return 1;
218	return 0;
219	}
220	});
221	return newcases;
222	}
223
224
225
226	public boolean[][] slurp(final File f)
227	throws IOException
228	{
229	LineNumberReader r = new LineNumberReader(new InputStreamReader(new GZIPInputStream(new FileInputStream(f))));
230	String bits;
231
232	Vector v = new Vector();
233	while((bits=r.readLine())!=null)
234	{
235	bits = bits.trim();
236	int len = bits.length();
237	if (len==0) continue; // empty line
238	if (bits.charAt(0)=='#') continue; // comment
239	if (bits.equalsIgnoreCase("e"))
240	v.addElement(new boolean[0]);
241	else
242	{
243	boolean[] b = new boolean[len];
244	for(int x=0;x<len;x++)
245	b[x] = (bits.charAt(x)=='1');
246	v.addElement(b);
247	}
248	}
249	r.close();
250	boolean[][] result = new boolean[v.size()][];
251	v.copyInto(result);
252	return result;
253	}
254
255
256	public void printBits(final EvolutionState state, final boolean[][] bits)
257	{
258	StringBuffer s;
259	for(int x=0;x<bits.length;x++)
260	{
261	s = new StringBuffer();
262	for(int y=0;y<bits[x].length;y++)
263	if (bits[x][y]) s.append('1');
264	else s.append('0');
265	if (s.length()==0) state.output.message("(empty)");
266	else state.output.message(s.toString());
267	}
268	}
269
270
271	public void setup(final EvolutionState state,
272	final Parameter base)
273	{
274	// very important, remember this
275	super.setup(state,base);
276
277	// do we generalize?
278	generalize = state.parameters.getBoolean(base.push(P_GENERALIZE),null,false);
279
280	// load the test examples here
281
282	File ap = null;
283	File an = null;
284	File tp = null;
285	File tn = null;
286	int restriction;
287
288	if (generalize)
289	{
290	ap = state.parameters.getFile(base.push(P_ALLPOS),null);
291	an = state.parameters.getFile(base.push(P_ALLNEG),null);
292	}
293
294	tp = state.parameters.getFile(base.push(P_TESTPOS),null);
295	tn = state.parameters.getFile(base.push(P_TESTNEG),null);
296
297	if (generalize)
298	{
299	if (ap==null) state.output.error("File doesn't exist", base.push(P_ALLPOS));
300	if (an==null) state.output.error("File doesn't exist", base.push(P_ALLNEG));
301	}
302
303	if (tp==null) state.output.error("File doesn't exist", base.push(P_TESTPOS));
304	if (tn==null) state.output.error("File doesn't exist", base.push(P_TESTNEG));
305	state.output.exitIfErrors();
306
307	if (generalize)
308	{
309	if (!ap.canRead()) state.output.error("File cannot be read", base.push(P_ALLPOS));
310	if (!an.canRead()) state.output.error("File cannot be read", base.push(P_ALLNEG));
311	}
312
313	if (!tp.canRead()) state.output.error("File cannot be read", base.push(P_TESTPOS));
314	if (!tn.canRead()) state.output.error("File cannot be read", base.push(P_TESTNEG));
315	state.output.exitIfErrors();
316
317	if (generalize)
318	{
319	state.output.message("Reading Positive Examples");
320	try { posA = slurp(ap); }
321	catch(IOException e) { state.output.error(
322	"IOException reading file (here it is)\n" + e, base.push(P_ALLPOS)); }
323	state.output.message("Reading Negative Examples");
324	try { negA = slurp(an); }
325	catch(IOException e) { state.output.error(
326	"IOException reading file (here it is)\n" + e, base.push(P_ALLNEG)); }
327	}
328
329	state.output.message("Reading Positive Training Examples");
330	try { posT = slurp(tp); }
331	catch(IOException e) { state.output.error(
332	"IOException reading file (here it is)\n" + e, base.push(P_TESTPOS)); }
333	if ((restriction = state.parameters.getInt(
334	base.push(P_MAXTEST),null,1))>0)
335	{
336	// Need to restrict
337	state.output.message("Restricting to <= " + restriction + " Unique Examples");
338	posT = restrictToSize(restriction,posT,state,0);
339	}
340
341	state.output.message("");
342	printBits(state,posT);
343	state.output.message("");
344
345	state.output.message("Reading Negative Training Examples");
346	try { negT = slurp(tn); }
347	catch(IOException e) { state.output.error(
348	"IOException reading file (here it is)\n" + e, base.push(P_TESTNEG)); }
349	if ((restriction = state.parameters.getInt(
350	base.push(P_MAXTEST),null,1))>0)
351	{
352	// Need to restrict
353	state.output.message("Restricting to <= " + restriction + " Unique Examples");
354	negT = restrictToSize(restriction,negT,state,0);
355	}
356
357	state.output.message("");
358	printBits(state,negT);
359	state.output.message("");
360
361	state.output.exitIfErrors();
362
363
364	// set up our input -- don't want to use the default base, it's unsafe
365	input = (EdgeData) state.parameters.getInstanceForParameterEq(
366	base.push(P_DATA), null, EdgeData.class);
367	input.setup(state,base.push(P_DATA));
368	}
369
370
371	public boolean test(final boolean[] sample)
372	{
373	final boolean STATE_1 = false;
374	// final boolean STATE_2 = true;
375	boolean st = STATE_1;
376
377	// set initial state
378	for(int x=0;x<numNodes;x++)
379	state1[x]=start[x];
380
381	// run
382	for(int x=0;x<sample.length;x++)
383	{
384	if (st==STATE_1)
385	{
386	for(int y=0;y<numNodes;y++)
387	state2[y]=false;
388	for(int y=0;y<numNodes;y++) // yes, start.length
389	if (state1[y]) // i'm in this state
390	{
391	// advance edges
392	if (sample[x]) // reading a 1
393	for(int z=0;z<reading1_l[y];z++)
394	state2[reading1[y][z]] = true;
395	else // reading a 0
396	for(int z=0;z<reading0_l[y];z++)
397	state2[reading0[y][z]] = true;
398	}
399
400
401	// advance along epsilon boundary
402	boolean moreEpsilons = true;
403	while(moreEpsilons)
404	{
405	moreEpsilons = false;
406	for(int y=0;y<numNodes;y++)
407	if (state2[y])
408	for(int z=0;z<epsilon_l[y];z++)
409	{
410	if (!state2[epsilon[y][z]]) moreEpsilons = true;
411	state2[epsilon[y][z]] = true;
412	}
413	}
414	}
415
416
417	else //if (st==STATE_2)
418	{
419	for(int y=0;y<numNodes;y++)
420	state1[y]=false;
421	for(int y=0;y<numNodes;y++) // yes, start.length
422	if (state2[y]) // i'm in this state
423	{
424	// advance edges
425	if (sample[x]) // reading a 1
426	for(int z=0;z<reading1_l[y];z++)
427	state1[reading1[y][z]] = true;
428	else // reading a 0
429	for(int z=0;z<reading0_l[y];z++)
430	state1[reading0[y][z]] = true;
431	}
432
433	// advance along epsilon boundary
434	boolean moreEpsilons = true;
435	while(moreEpsilons)
436	{
437	moreEpsilons = false;
438	for(int y=0;y<numNodes;y++)
439	if (state1[y])
440	for(int z=0;z<epsilon_l[y];z++)
441	{
442	if (!state1[epsilon[y][z]]) moreEpsilons = true;
443	state1[epsilon[y][z]] = true;
444	}
445	}
446	}
447
448	st = !st;
449	}
450
451	// am I in an accepting state?
452	if (st==STATE_1) // just loaded the result into state 1 from state 2
453	{
454	for(int x=0;x<numNodes;x++)
455	if (accept[x] && state1[x]) return true;
456	}
457	else // (st==STATE_2)
458	{
459	for(int x=0;x<numNodes;x++)
460	if (accept[x] && state2[x]) return true;
461	}
462	return false;
463	}
464
465
466
467
468
469
470	int totpos;
471	int totneg;
472
473	/** Tests an individual, returning its successful positives
474	in totpos and its successful negatives in totneg. */
475	public void fullTest(final EvolutionState state,
476	final Individual ind,
477	final int threadnum,
478	boolean[][] pos,
479	boolean[][] neg)
480	{
481	// reset the graph
482	numNodes = 2;
483	numEdges = 1; from[0]=0; to[0]=1;
484	start[0]=start[1]=accept[0]=accept[1]=false;
485	((EdgeData)input).edge = 0;
486
487	// generate the graph
488	((GPIndividual)ind).trees[0].child.eval(
489	state,threadnum,input,stack,((GPIndividual)ind),this);
490
491	// produce the adjacency matrix
492	if (reading1.length < numNodes \|\|
493	reading1[0].length < numEdges)
494	{
495	reading1 = new int[numNodes2][numEdges2];
496	reading0 = new int[numNodes2][numEdges2];
497	epsilon = new int[numNodes2][numEdges2];
498	reading1_l = new int[numNodes*2];
499	reading0_l = new int[numNodes*2];
500	epsilon_l = new int[numNodes*2];
501	}
502
503	for(int y=0;y<numNodes;y++)
504	{
505	reading1_l[y]=0;
506	reading0_l[y]=0;
507	epsilon_l[y]=0;
508	}
509
510	for(int y=0;y<numEdges;y++)
511	switch(reading[y])
512	{
513	case READING0:
514	reading0[from[y]][reading0_l[from[y]]++]=to[y];
515	break;
516	case READING1:
517	reading1[from[y]][reading1_l[from[y]]++]=to[y];
518	break;
519	case EPSILON:
520	epsilon[from[y]][epsilon_l[from[y]]++]=to[y];
521	break;
522	}
523
524	// create the states
525	if (state1.length < numNodes)
526	{
527	state1 = new boolean[numNodes*2];
528	state2 = new boolean[numNodes*2];
529	}
530
531	// test the graph on our data
532
533	totpos=0;
534	totneg=0;
535	for(int y=0;y<pos.length;y++)
536	if (test(pos[y])) totpos++;
537	for(int y=0;y<neg.length;y++)
538	if (!test(neg[y])) totneg++;
539	}
540
541
542
543
544	public void evaluate(final EvolutionState state,
545	final Individual ind,
546	final int subpopulation,
547	final int threadnum)
548	{
549	if (start==null)
550	{
551	start = new boolean[MIN_ARRAY_SIZE];
552	accept = new boolean[MIN_ARRAY_SIZE];
553	reading = new int[MIN_ARRAY_SIZE];
554	from = new int[MIN_ARRAY_SIZE];
555	to = new int[MIN_ARRAY_SIZE];
556	state1 = new boolean[MIN_ARRAY_SIZE];
557	state2 = new boolean[MIN_ARRAY_SIZE];
558	reading1 = new int[MIN_ARRAY_SIZE][MIN_ARRAY_SIZE];
559	reading0 = new int[MIN_ARRAY_SIZE][MIN_ARRAY_SIZE];
560	epsilon = new int[MIN_ARRAY_SIZE][MIN_ARRAY_SIZE];
561	reading1_l = new int[MIN_ARRAY_SIZE];
562	reading0_l = new int[MIN_ARRAY_SIZE];
563	epsilon_l = new int[MIN_ARRAY_SIZE];
564	}
565
566	if (!ind.evaluated) // don't bother reevaluating
567	{
568	fullTest(state,ind,threadnum,posT,negT);
569	// the fitness better be KozaFitness!
570	KozaFitness f = ((KozaFitness)ind.fitness);
571
572	// this is an awful fitness metric, but it's the standard
573	// one used for these problems. :-(
574
575	f.setStandardizedFitness(state,(float)
576	(1.0 - ((double)(totpos + totneg)) /
577	(posT.length + negT.length)));
578
579	// here are two other more reasonable fitness metrics
580	/*
581	f.setStandardizedFitness(state,(float)
582	(1.0 - Math.min(((double)totpos)/posT.length,
583	((double)totneg)/negT.length)));
584
585	f.setStandardizedFitness(state,(float)
586	(1.0 - (((double)totpos)/posT.length +
587	((double)totneg)/negT.length)/2.0));
588	*/
589
590	f.hits = totpos + totneg;
591	ind.evaluated = true;
592	}
593	}
594
595	public void describe(
596	final EvolutionState state,
597	final Individual ind,
598	final int subpopulation,
599	final int threadnum,
600	final int log)
601	{
602	if (start==null)
603	{
604	start = new boolean[MIN_ARRAY_SIZE];
605	accept = new boolean[MIN_ARRAY_SIZE];
606	reading = new int[MIN_ARRAY_SIZE];
607	from = new int[MIN_ARRAY_SIZE];
608	to = new int[MIN_ARRAY_SIZE];
609	state1 = new boolean[MIN_ARRAY_SIZE];
610	state2 = new boolean[MIN_ARRAY_SIZE];
611	reading1 = new int[MIN_ARRAY_SIZE][MIN_ARRAY_SIZE];
612	reading0 = new int[MIN_ARRAY_SIZE][MIN_ARRAY_SIZE];
613	epsilon = new int[MIN_ARRAY_SIZE][MIN_ARRAY_SIZE];
614	reading1_l = new int[MIN_ARRAY_SIZE];
615	reading0_l = new int[MIN_ARRAY_SIZE];
616	epsilon_l = new int[MIN_ARRAY_SIZE];
617	}
618
619	if (generalize)
620	fullTest(state,ind,threadnum,posA,negA);
621	else
622	fullTest(state,ind,threadnum,posT,negT);
623
624	if (generalize)
625	state.output.println("\n\nBest Individual's Generalization Score...\n" +
626	"Pos: " + totpos + "/" + posA.length +
627	" Neg: " + totneg + "/" + negA.length +
628	"\n(pos+neg)/(allpos+allneg): " +
629	(float)
630	(((double)(totpos+totneg))/(posA.length+negA.length)) +
631	"\n((pos/allpos)+(neg/allneg))/2: " +
632	(float)
633	(((((double)totpos)/posA.length)+(((double)totneg)/negA.length))/2) +
634	"\nMin(pos/allpos,neg/allneg): " +
635	(float)Math.min((((double)totpos)/posA.length),(((double)totneg)/negA.length)),
636	log);
637
638	state.output.println("\nBest Individual's NFA\n=====================\n",
639	log);
640
641	state.output.println(printCurrentNFA(),log);
642	}
643
644	public String describeShortGeneralized(final Individual ind,
645	final EvolutionState state,
646	final int subpopulation,
647	final int threadnum)
648	{
649	if (start==null)
650	{
651	start = new boolean[MIN_ARRAY_SIZE];
652	accept = new boolean[MIN_ARRAY_SIZE];
653	reading = new int[MIN_ARRAY_SIZE];
654	from = new int[MIN_ARRAY_SIZE];
655	to = new int[MIN_ARRAY_SIZE];
656	state1 = new boolean[MIN_ARRAY_SIZE];
657	state2 = new boolean[MIN_ARRAY_SIZE];
658	reading1 = new int[MIN_ARRAY_SIZE][MIN_ARRAY_SIZE];
659	reading0 = new int[MIN_ARRAY_SIZE][MIN_ARRAY_SIZE];
660	epsilon = new int[MIN_ARRAY_SIZE][MIN_ARRAY_SIZE];
661	reading1_l = new int[MIN_ARRAY_SIZE];
662	reading0_l = new int[MIN_ARRAY_SIZE];
663	epsilon_l = new int[MIN_ARRAY_SIZE];
664	}
665
666	fullTest(state,ind,threadnum,posA,negA);
667
668	return ": " +
669	((double)totpos)/posA.length + " " +
670	((double)totneg)/negA.length + " " +
671	(((double)(totpos+totneg))/(posA.length+negA.length)) + " " +
672	(((((double)totpos)/posA.length)+(((double)totneg)/negA.length))/2) + " " +
673	Math.min((((double)totpos)/posA.length),(((double)totneg)/negA.length)) + " : " ;
674	}
675
676	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Update cookies preferences