|
996
|
1 //====================================================================
|
|
|
2 // TEXTGEN -- BrainF*** Genetic Text Generator
|
|
|
3 // textgen.java
|
|
|
4 // Copyright (C) 2003, 2004 by Jeffry Johnston
|
|
|
5 // Version 0.20
|
|
|
6 //
|
|
|
7 // This program is free software; you can redistribute it and/or
|
|
|
8 // modify it under the terms of the GNU General Public License as
|
|
|
9 // published by the Free Software Foundation. See the file LICENSE
|
|
|
10 // for more details.
|
|
|
11 //
|
|
|
12 // Online resource used:
|
|
|
13 // http://www.genetic-programming.com/gpflowchart.html
|
|
|
14 //
|
|
|
15 // I have not read any books and have seen very little information
|
|
|
16 // online about GP implementation. Any suggestions are most welcome.
|
|
|
17 //
|
|
|
18 // Inspiration:
|
|
|
19 // 111-byte "Hello World!" with newline (assumed optimal)
|
|
|
20 // ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.
|
|
|
21 // <<+++++++++++++++.>.+++.------.--------.>+.>.
|
|
|
22 //
|
|
|
23 // Version history:
|
|
|
24 // 0.20 11 Aug 2004 Added -i and -o options
|
|
|
25 // 0.10 01 Dec 2003 Initial release
|
|
|
26 //====================================================================
|
|
|
27
|
|
|
28 import java.io.*;
|
|
|
29 import java.util.*;
|
|
|
30
|
|
|
31 //********************************************************************
|
|
|
32 // textgen
|
|
|
33 //********************************************************************
|
|
|
34 public class textgen {
|
|
|
35 static final String VERSION = "0.20";
|
|
|
36 static Random r = new Random();
|
|
|
37
|
|
|
38 //------------------------------------------------------------------
|
|
|
39 // main
|
|
|
40 //------------------------------------------------------------------
|
|
|
41 public static void main(String[] cmdline) {
|
|
|
42 int terms = 4, population = 500, generations = 0;
|
|
|
43 String text = "Default text?!";
|
|
|
44 double toppercent = 0.10;
|
|
|
45 String fileout = null;
|
|
|
46
|
|
|
47 // display copyright text
|
|
|
48 System.out.println("TEXTGEN BrainF*** Genetic Text Generator, version " + VERSION + ".");
|
|
|
49 System.out.println("Copyright (c) 2003 Jeffry Johnston.");
|
|
|
50 System.out.println();
|
|
|
51
|
|
|
52 // process command line
|
|
|
53 for (int n = 0; ; n++) {
|
|
|
54 try {
|
|
|
55 if (cmdline[n].equals("-?") || cmdline[n].equals("/?") || cmdline[n].equals("--?")
|
|
|
56 || cmdline[n].equals("--help") ) {
|
|
|
57 usage();
|
|
|
58 System.exit(0);
|
|
|
59 } else if (cmdline[n].equalsIgnoreCase("-i")) {
|
|
|
60 // open file
|
|
|
61 DataInputStream filein = null;
|
|
|
62 try {
|
|
|
63 filein = new DataInputStream(new FileInputStream(cmdline[n + 1]));
|
|
|
64 } catch (FileNotFoundException e) {
|
|
|
65 System.out.println("Error opening input file. File not found");
|
|
|
66 System.exit(1);
|
|
|
67 }
|
|
|
68 // read file
|
|
|
69 byte[] data = null;
|
|
|
70 int size = 0;
|
|
|
71 try {
|
|
|
72 size = filein.available();
|
|
|
73 data = new byte[size];
|
|
|
74 filein.readFully(data);
|
|
|
75 } catch (IOException e) {
|
|
|
76 System.out.println("Error reading input file.");
|
|
|
77 System.exit(1);
|
|
|
78 }
|
|
|
79 // close file
|
|
|
80 try {
|
|
|
81 filein.close();
|
|
|
82 } catch (IOException e) {
|
|
|
83 System.out.println("Error closing input file.");
|
|
|
84 System.exit(1);
|
|
|
85 }
|
|
|
86 try {
|
|
|
87 text = new String(data, "ISO-8859-1");
|
|
|
88 } catch (UnsupportedEncodingException e) {
|
|
|
89 System.out.println("This program requires ISO-8859-1 character set support.");
|
|
|
90 }
|
|
|
91 n++;
|
|
|
92 } else if (cmdline[n].equalsIgnoreCase("-o")) {
|
|
|
93 fileout = cmdline[n + 1];
|
|
|
94 n++;
|
|
|
95 } else if (cmdline[n].equalsIgnoreCase("-g")) {
|
|
|
96 generations = Integer.parseInt(cmdline[n + 1]);
|
|
|
97 if (generations < 1) {
|
|
|
98 System.out.println("Must have at least 1 generation.");
|
|
|
99 System.exit(1);
|
|
|
100 }
|
|
|
101 n++;
|
|
|
102 } else if (cmdline[n].equalsIgnoreCase("-t")) {
|
|
|
103 terms = Integer.parseInt(cmdline[n + 1]);
|
|
|
104 if (terms < 1) {
|
|
|
105 System.out.println("Must have at least 1 term.");
|
|
|
106 System.exit(1);
|
|
|
107 }
|
|
|
108 n++;
|
|
|
109 } else if (cmdline[n].equalsIgnoreCase("-p")) {
|
|
|
110 population = Integer.parseInt(cmdline[n + 1]);
|
|
|
111 if (terms < 2) {
|
|
|
112 System.out.println("Must have population of at least 10.");
|
|
|
113 System.exit(1);
|
|
|
114 }
|
|
|
115 n++;
|
|
|
116 } else if (cmdline[n].equalsIgnoreCase("-%")) {
|
|
|
117 int tp = Integer.parseInt(cmdline[n + 1]);
|
|
|
118 if (tp < 0 || tp > 100) {
|
|
|
119 System.out.println("Percentage out of range (0, 100).");
|
|
|
120 System.exit(1);
|
|
|
121 }
|
|
|
122 toppercent = (double) tp / 100;
|
|
|
123 n++;
|
|
|
124 } else {
|
|
|
125 text = cmdline[n];
|
|
|
126 if (text.charAt(0) == '\"') {
|
|
|
127 text = text.substring(1);
|
|
|
128 }
|
|
|
129 if (text.charAt(text.length() - 1) == '\"') {
|
|
|
130 text = text.substring(0, text.length());
|
|
|
131 }
|
|
|
132 }
|
|
|
133 } catch (ArrayIndexOutOfBoundsException e) {
|
|
|
134 break;
|
|
|
135 } catch (NumberFormatException e) {
|
|
|
136 System.out.println("Invalid number");
|
|
|
137 System.exit(1);
|
|
|
138 }
|
|
|
139 }
|
|
|
140 int top = (int) (toppercent * population);
|
|
|
141 int bottom = population - top;
|
|
|
142
|
|
|
143 if (fileout == null) {
|
|
|
144 System.out.println("Text: \"" + text + "\"");
|
|
|
145 }
|
|
|
146 System.out.print("Generations: ");
|
|
|
147 if (generations == 0) {
|
|
|
148 System.out.println("Infinite");
|
|
|
149 } else {
|
|
|
150 System.out.println(generations);
|
|
|
151 }
|
|
|
152 System.out.println("Terms: " + terms);
|
|
|
153 System.out.println("Population: " + population);
|
|
|
154 System.out.println("Top %: " + toppercent);
|
|
|
155 System.out.println();
|
|
|
156
|
|
|
157 CompareIndividuals compare = new CompareIndividuals();
|
|
|
158
|
|
|
159 // generate initial population
|
|
|
160 Individual[] citizen = new Individual[population];
|
|
|
161 for (int n = 0; n < population; n++) {
|
|
|
162 citizen[n] = new Individual(text, terms);
|
|
|
163 }
|
|
|
164
|
|
|
165 // keep looking for the best program
|
|
|
166 int best = Integer.MAX_VALUE;
|
|
|
167 for(int generation = 1; (generation <= generations) || (generations == 0);
|
|
|
168 generation++) {
|
|
|
169 // choose a top citizen to copy and tweak number order
|
|
|
170 for (int n = bottom; n < population; n++) {
|
|
|
171 citizen[n].tweak(citizen[r.nextInt(top)]);
|
|
|
172 }
|
|
|
173
|
|
|
174 // genetic stimulation
|
|
|
175 for (int n = 1; n < population; n++) {
|
|
|
176 int p = r.nextInt(population);
|
|
|
177 if (p < n) { // less mutation with good, more mutation with bad
|
|
|
178 citizen[n].mutate();
|
|
|
179 } else {
|
|
|
180 p = r.nextInt(top);
|
|
|
181 citizen[n].crossover(citizen[p]);
|
|
|
182 }
|
|
|
183 }
|
|
|
184
|
|
|
185 // get rid of the duds
|
|
|
186 Arrays.sort(citizen, compare);
|
|
|
187 for (int n = bottom; n < population; n++) {
|
|
|
188 citizen[n].restart();
|
|
|
189 }
|
|
|
190
|
|
|
191 // display progress
|
|
|
192 Arrays.sort(citizen, compare);
|
|
|
193 if (citizen[0].getFitness() < best) {
|
|
|
194 String temptext;
|
|
|
195 System.out.println((best = citizen[0].getFitness()) + " " + (temptext = citizen[0].getCode())
|
|
|
196 + " [" + generation + "]");
|
|
|
197 System.out.println();
|
|
|
198 if (fileout != null) {
|
|
|
199 PrintStream out;
|
|
|
200 try {
|
|
|
201 out = new PrintStream(new FileOutputStream(fileout));
|
|
|
202 out.print(temptext);
|
|
|
203 out.close();
|
|
|
204 } catch (IOException e) {
|
|
|
205 System.out.println("Error writing output file.");
|
|
|
206 System.exit(1);
|
|
|
207 }
|
|
|
208 }
|
|
|
209 }
|
|
|
210
|
|
|
211 }
|
|
|
212 }
|
|
|
213
|
|
|
214 //------------------------------------------------------------------
|
|
|
215 // getRandomBoolean()
|
|
|
216 //------------------------------------------------------------------
|
|
|
217 public static boolean getRandomBoolean() {
|
|
|
218 return r.nextBoolean();
|
|
|
219 }
|
|
|
220
|
|
|
221 //------------------------------------------------------------------
|
|
|
222 // getRandomInt()
|
|
|
223 //------------------------------------------------------------------
|
|
|
224 public static int getRandomInt(int n) {
|
|
|
225 return r.nextInt(n);
|
|
|
226 }
|
|
|
227
|
|
|
228 //------------------------------------------------------------------
|
|
|
229 // usage -- prints usage information
|
|
|
230 //------------------------------------------------------------------
|
|
|
231 public static void usage() {
|
|
|
232 System.out.println("Usage: textgen [-i file] [-o file] [-t #] [-p #] [-% #] \"text\" [-?]");
|
|
|
233 System.out.println("Where: \"text\" Text to generate");
|
|
|
234 System.out.println(" -i Input filename (in place of \"text\")");
|
|
|
235 System.out.println(" -o Output filename, default: screen only");
|
|
|
236 System.out.println(" -g Generations, default: infinite");
|
|
|
237 System.out.println(" -t Number of terms, default: 4");
|
|
|
238 System.out.println(" -p Population, default: 500");
|
|
|
239 System.out.println(" -% Percent to rank as top, default: 10");
|
|
|
240 System.out.println(" -? Display usage information");
|
|
|
241 }
|
|
|
242
|
|
|
243 }
|
|
|
244
|
|
|
245 //********************************************************************
|
|
|
246 // CompareIndividuals
|
|
|
247 //********************************************************************
|
|
|
248 class CompareIndividuals implements Comparator {
|
|
|
249 public int compare(Object o1, Object o2) {
|
|
|
250 return (((Individual) o1).getFitness() - ((Individual) o2).getFitness());
|
|
|
251 }
|
|
|
252 }
|
|
|
253
|
|
|
254 //********************************************************************
|
|
|
255 // Individual
|
|
|
256 //********************************************************************
|
|
|
257 class Individual {
|
|
|
258 int letters, mult, terms, fitness = -1;
|
|
|
259 int[] term, finder, fixer;
|
|
|
260 String expected;
|
|
|
261
|
|
|
262 //------------------------------------------------------------------
|
|
|
263 // (constructor)
|
|
|
264 //------------------------------------------------------------------
|
|
|
265 Individual(String expected, int terms) {
|
|
|
266 this.expected = expected;
|
|
|
267 letters = expected.length();
|
|
|
268 this.terms = terms;
|
|
|
269 term = new int[terms];
|
|
|
270 restart();
|
|
|
271 }
|
|
|
272
|
|
|
273 //------------------------------------------------------------------
|
|
|
274 // restart()
|
|
|
275 //------------------------------------------------------------------
|
|
|
276 public void restart() {
|
|
|
277 // multiplier (1 to 15)
|
|
|
278 mult = textgen.getRandomInt(15) + 1;
|
|
|
279 // value of each term (0 to 15)
|
|
|
280 for (int n = 0; n < terms; n++) {
|
|
|
281 term[n] = textgen.getRandomInt(16);
|
|
|
282 }
|
|
|
283 // ><+- multiple before each dot (one for each letter)
|
|
|
284 finder = new int[letters];
|
|
|
285 fixer = new int[letters];
|
|
|
286 for (int n = 0; n < letters; n++) {
|
|
|
287 finder[n] = textgen.getRandomInt(terms);
|
|
|
288 }
|
|
|
289 fitness = -1;
|
|
|
290 }
|
|
|
291
|
|
|
292 //------------------------------------------------------------------
|
|
|
293 // mutate()
|
|
|
294 //------------------------------------------------------------------
|
|
|
295 public void mutate() {
|
|
|
296 int n;
|
|
|
297 // mutate item
|
|
|
298 if (textgen.getRandomBoolean()) {
|
|
|
299 // term
|
|
|
300 n = textgen.getRandomInt(terms);
|
|
|
301 term[n] = textgen.getRandomInt(16);
|
|
|
302 } else {
|
|
|
303 // finder
|
|
|
304 n = textgen.getRandomInt(letters);
|
|
|
305 finder[n] = textgen.getRandomInt(terms);
|
|
|
306 }
|
|
|
307 fitness = -1;
|
|
|
308 }
|
|
|
309
|
|
|
310 //------------------------------------------------------------------
|
|
|
311 // tweak()
|
|
|
312 //------------------------------------------------------------------
|
|
|
313 public void tweak(Individual giver) {
|
|
|
314 if ((textgen.r).nextBoolean()) {
|
|
|
315 // copy the giver exactly
|
|
|
316 mult = giver.getMult();
|
|
|
317 for (int n = 0; n < terms; n++) {
|
|
|
318 term[n] = giver.getTerm(n);
|
|
|
319 }
|
|
|
320 } else {
|
|
|
321 // copy the giver, but use a new multiplier, adjust the terms accordingly
|
|
|
322 mult = textgen.getRandomInt(15) + 1;
|
|
|
323 for (int n = 0; n < terms; n++) {
|
|
|
324 term[n] = Math.round(giver.getTerm(n) * giver.getMult() / (float) mult);
|
|
|
325 }
|
|
|
326 }
|
|
|
327 // copy the finder
|
|
|
328 for (int n = 0; n < letters; n++) {
|
|
|
329 finder[n] = giver.getFinder(n);
|
|
|
330 }
|
|
|
331
|
|
|
332 // swap two of the terms to see if it helps (can be the same term)
|
|
|
333 int n1 = textgen.getRandomInt(terms);
|
|
|
334 int n2 = textgen.getRandomInt(terms);
|
|
|
335 int n3 = term[n2];
|
|
|
336 term[n2] = term[n1];
|
|
|
337 term[n1] = n3;
|
|
|
338
|
|
|
339 // swap finders to match swapped terms
|
|
|
340 for (int n = 0; n < letters; n++) {
|
|
|
341 if (finder[n] == n1) {
|
|
|
342 finder[n] = n2;
|
|
|
343 } else if (finder[n] == n2) {
|
|
|
344 finder[n] = n1;
|
|
|
345 }
|
|
|
346 }
|
|
|
347
|
|
|
348 fitness = -1;
|
|
|
349 }
|
|
|
350
|
|
|
351 //------------------------------------------------------------------
|
|
|
352 // crossover()
|
|
|
353 //------------------------------------------------------------------
|
|
|
354 public void crossover(Individual giver) {
|
|
|
355 int n;
|
|
|
356 if ((textgen.r).nextBoolean()) {
|
|
|
357 // term
|
|
|
358 n = textgen.getRandomInt(terms);
|
|
|
359 int n2 = textgen.getRandomInt(terms);
|
|
|
360 term[n2] = giver.getTerm(n);
|
|
|
361 } else {
|
|
|
362 // finder
|
|
|
363 n = textgen.getRandomInt(letters);
|
|
|
364 finder[n] = giver.getFinder(n);
|
|
|
365 }
|
|
|
366 fitness = -1;
|
|
|
367 }
|
|
|
368
|
|
|
369 //------------------------------------------------------------------
|
|
|
370 // getMult()
|
|
|
371 //------------------------------------------------------------------
|
|
|
372 public int getMult() {
|
|
|
373 return mult;
|
|
|
374 }
|
|
|
375
|
|
|
376 //------------------------------------------------------------------
|
|
|
377 // getTerms()
|
|
|
378 //------------------------------------------------------------------
|
|
|
379 public int getTerms() {
|
|
|
380 return terms;
|
|
|
381 }
|
|
|
382
|
|
|
383 //------------------------------------------------------------------
|
|
|
384 // getTerm()
|
|
|
385 //------------------------------------------------------------------
|
|
|
386 public int getTerm(int n) {
|
|
|
387 return term[n];
|
|
|
388 }
|
|
|
389
|
|
|
390 //------------------------------------------------------------------
|
|
|
391 // getFinder()
|
|
|
392 //------------------------------------------------------------------
|
|
|
393 public int getFinder(int n) {
|
|
|
394 return finder[n];
|
|
|
395 }
|
|
|
396
|
|
|
397 //------------------------------------------------------------------
|
|
|
398 // getFitness()
|
|
|
399 //------------------------------------------------------------------
|
|
|
400 public int getFitness() {
|
|
|
401 if (fitness < 0) {
|
|
|
402 int length = 4 + mult + terms * 2 + letters; // mult [ terms> terms< -]> letters.
|
|
|
403 int[] memory = new int[terms];
|
|
|
404 for (int n = 0; n < terms; n++) {
|
|
|
405 length += term[n];
|
|
|
406 memory[n] = (mult * term[n]) % 256;
|
|
|
407 }
|
|
|
408 int mp = 0;
|
|
|
409 for (int n = 0; n < letters; n++) {
|
|
|
410 length += Math.abs(finder[n] - mp);
|
|
|
411 mp = finder[n];
|
|
|
412 fixer[n] = expected.charAt(n) - memory[mp];
|
|
|
413 int n2 = Math.abs(fixer[n]);
|
|
|
414 if (Math.abs(fixer[n]) > 128) {
|
|
|
415 n2 = 256 - n2;
|
|
|
416 if (fixer[n] > 0) {
|
|
|
417 n2 = -n2;
|
|
|
418 }
|
|
|
419 }
|
|
|
420 length += Math.abs(fixer[n]);
|
|
|
421 memory[mp] = expected.charAt(n);
|
|
|
422 }
|
|
|
423
|
|
|
424 // combine results
|
|
|
425 fitness = length;
|
|
|
426
|
|
|
427 if (fitness < 0) { fitness = Integer.MAX_VALUE; }
|
|
|
428
|
|
|
429 }
|
|
|
430 return fitness;
|
|
|
431 }
|
|
|
432
|
|
|
433 //------------------------------------------------------------------
|
|
|
434 // getCode()
|
|
|
435 //------------------------------------------------------------------
|
|
|
436 public String getCode() {
|
|
|
437 String code = getBF(mult, '+', '+') + "[";
|
|
|
438 for (int n = 0; n < terms; n++) {
|
|
|
439 code += ">" + getBF(term[n], '+', '+');
|
|
|
440 }
|
|
|
441 code += getBF(terms, '<', '<') + "-]>";
|
|
|
442 int mp = 0;
|
|
|
443 for (int n = 0; n < letters; n++) {
|
|
|
444 code += getBF(finder[n] - mp, '>', '<');
|
|
|
445 mp = finder[n];
|
|
|
446 code += getBF(fixer[n], '+', '-') + ".";
|
|
|
447 }
|
|
|
448 return code;
|
|
|
449 }
|
|
|
450
|
|
|
451 //------------------------------------------------------------------
|
|
|
452 // getBF() {
|
|
|
453 //------------------------------------------------------------------
|
|
|
454 public String getBF(int n, char pos, char neg) {
|
|
|
455 char ch = ' ';
|
|
|
456 if (n > 0) {
|
|
|
457 ch = pos;
|
|
|
458 } else if (n < 0) {
|
|
|
459 ch = neg;
|
|
|
460 }
|
|
|
461 n = Math.abs(n);
|
|
|
462 if (n != 0) {
|
|
|
463 char[] c = new char[Math.abs(n)];
|
|
|
464 Arrays.fill(c, ch);
|
|
|
465 return new String(c);
|
|
|
466 } else {
|
|
|
467 return "";
|
|
|
468 }
|
|
|
469 }
|
|
|
470
|
|
|
471 }
|
|
|
472
|
|
|
473
|
|
|
474
|
