2 Copyright 2007 Scott Gasch
4 Licensed under the Apache License, Version 2.0 (the "License"); you
5 may not use this file except in compliance with the License. You may
6 obtain a copy of the License at
8 http://www.apache.org/licenses/LICENSE-2.0
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
13 implied. See the License for the specific language governing
14 permissions and limitations under the License.
17 package org.guru.wannabe.genetic;
20 import java.util.regex.*;
23 import java.util.TreeMap;
24 import java.util.List;
25 import java.util.ArrayList;
26 import java.util.Arrays;
28 public class ParallelChessGeneticProcess implements GeneticProcess {
29 private static final int numProcessors = 4;
30 private static final String baselineDna = "./baseline.dna";
31 private static final String baselineLog = "./baseline.log";
32 private static final String scriptName = "./trial.ep_";
34 private int numGenerations;
35 private int numPerGeneration;
38 // Helper function to emulate system(3).
39 private static void system(String cmd[]) {
40 Runtime runtime = Runtime.getRuntime();
42 Process ps = runtime.exec(cmd);
43 InputStream stdin = ps.getInputStream();
44 InputStreamReader isr = new InputStreamReader(stdin);
45 BufferedReader br = new BufferedReader(isr);
47 while((line = br.readLine()) != null) ;
49 } catch(Exception e) {
50 throw new AssertionError(e);
54 // Private helpers to build filenames
55 private static String seedFilename(int generation, int which) {
56 return "./gen" + generation + "_seed" + which + ".dna";
59 private static String logFilename(int generation, int which) {
60 return "./gen" + generation + "_" + which + ".log";
63 private static String dnaFilename(int generation, int which) {
64 return "./gen" + generation + "_" + which + ".dna";
67 // Uses mutate.pl to cause dna mutations
68 private static void mutate(String from, String to) {
69 String cmd[] = new String[] { "./mutate.pl", from, to };
73 new BufferedWriter(new FileWriter(to, true));
74 out.write("# mutate " + from + " -> " + to + "\n");
76 } catch(IOException e) {
77 throw new AssertionError(e);
81 // Runs a chess trial event
82 private static void chessTrial(String dnaFile, String logFile) {
83 String cmd[] = new String[] { "./typhoon",
89 "--command", "script ./trial.ep_" };
93 // The mainInitialize method produces the 0th generation DNA from
94 // a seed file called "baseline.dna" using a helper script called
95 // mutate.pl (the generic DNA mutation routine).
96 public boolean mainInitialize(int numGenerations,
97 int numPerGeneration) {
99 System.out.println("Performing pre-generation setup tasks.");
100 this.numGenerations = numGenerations;
101 this.numPerGeneration = numPerGeneration;
102 this.numSeeds = numPerGeneration / 5;
103 if ((numGenerations <= 0) ||
104 (numPerGeneration <= 0) ||
106 throw new IllegalArgumentException("Bad value");
109 // Create generation zero seeds based on mutations of baseline.dna
110 for (int x = 0; x < numSeeds; x++) {
111 String seedFile = seedFilename(0, x);
112 if (!new File(seedFile).exists()) {
113 mutate(baselineDna, seedFile);
115 System.out.println("Using existing " + seedFile);
119 // Run baseline.dna trial to get a starting point.
120 if (!new File(baselineLog).exists()) {
121 chessTrial(baselineDna, baselineLog);
123 System.out.println("Using existing " + baselineLog);
128 public boolean generationInitialize(int generationNumber) {
130 // Using the seed dna of the previous generation, build the
131 // genes for the current generation.
132 System.out.println("Initializing generation " + generationNumber);
133 for (int x = 0; x < numPerGeneration; x++) {
134 String dnaFile = dnaFilename(generationNumber, x);
135 String seedFile = seedFilename(generationNumber, x % numSeeds);
136 mutate(seedFile, dnaFile);
141 public boolean generationEvaluation(int generationNumber) {
142 class ChessGame implements Runnable {
143 public String dnaFile;
144 public String logFile;
145 public ChessGame(String dnaFile, String logFile) {
146 this.dnaFile = dnaFile; this.logFile = logFile;
149 if (!new File(logFile).exists()) {
150 System.out.println("Creating " + logFile);
151 chessTrial(dnaFile, logFile);
153 System.out.println("Using existing " + logFile);
158 // Populate work queue
159 System.out.println("Evaluating generation " + generationNumber);
160 List<ChessGame> workQueue = new ArrayList<ChessGame>();
161 for (int x = 0; x < numPerGeneration; x++) {
162 String dnaFile = dnaFilename(generationNumber, x);
163 String logFile = logFilename(generationNumber, x);
164 workQueue.add(new ChessGame(dnaFile, logFile));
167 // Depopulate the work queue in parallel
168 Thread threadPool[] = new Thread[numProcessors];
169 while(!workQueue.isEmpty()) {
170 ChessGame next = workQueue.remove(0);
173 if ((threadPool[x] == null) ||
174 (!threadPool[x].isAlive())) {
175 threadPool[x] = new Thread(next);
176 threadPool[x].setPriority(Thread.MAX_PRIORITY);
177 threadPool[x].start();
181 if (x >= numProcessors) {
185 } catch(Exception e) {
193 // Wait for all threads to become idle again
196 if (threadPool[x] != null && threadPool[x].isAlive()) {
202 } catch(Exception e) {
205 } while(x < numProcessors);
209 public boolean generationReproduction(int generationNumber) {
212 class FileAndScore implements Comparable<FileAndScore> {
213 public final String file;
214 public final int score;
215 public final int number;
216 public FileAndScore(String file, int score, int number) {
217 this.file = file; this.score = score; this.number = number;
219 public int compareTo(FileAndScore other) {
220 return other.score - score;
224 System.out.println("Seeding subsequent generation.");
225 List<FileAndScore> scores = new ArrayList<FileAndScore>();
226 for (int x = 0; x < numPerGeneration; x++) {
227 String logFile = logFilename(generationNumber, x);
229 BufferedReader log = new BufferedReader(
230 new FileReader(logFile));
233 Pattern.compile("\\s+correct solutions\\s+:\\s+(\\d+)");
234 while ((line = log.readLine()) != null) {
235 Matcher m = p.matcher(line);
237 int score = Integer.parseInt(m.group(1));
239 new FileAndScore(logFile, score, x);
246 catch (Exception e) {
247 throw new AssertionError(e);
250 java.util.Collections.sort(scores);
251 for (int x = 0; x < numSeeds; x++) {
252 FileAndScore breeder = scores.get(0);
254 String dnaFile = dnaFilename(generationNumber, breeder.number);
255 String seedFile = seedFilename(generationNumber + 1, x);
256 if (!new File(seedFile).exists()) {
257 System.out.println("Number " + breeder.number + " got score " +
258 breeder.score + " and will propagate.");
259 String cmd[] = new String[] { "/bin/cp", "-f", dnaFile, seedFile };
262 System.out.println("Using existing " + seedFile);