Source code: exptree/utilities/generator.java
1 /* Evolvo - Image Generator
2 * Copyright (C) 2000 Andrew Molloy
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */
18
19 /*
20 * @(#)generator.java 0.1 08/19/2000
21 */
22 package exptree.utilities;
23
24 import java.util.Random;
25 import exptree.*;
26 import exptree.operators.*;
27 import settings.*;
28
29 /**
30 * Creates a randomly generated mathematic expression and places it in an expressionTree.
31 *
32 * The generation process is influenced by several parameters contain in a globalSettings object.
33 * The most significant are the properties "complexity," "depreciation," and "variable.probability."
34 * The complexity value determines how likely the node being produced is to be a terminal node, where
35 * the lower complexity's value, the more likely it is to be terminal. Depreciation is a value that
36 * is subtracted from complexity at each level of the tree, to ensure the generation process will end
37 * within a reasonable number of tree levels. The variable.probability determines how likely a terminal
38 * node is to be a value or a variable, where higher values mean variables are more likely to occur
39 * than values.
40 *
41 * All three of these settings should fall in the range of 0.0 to 1.0. Depreciation, however, should never
42 * actually be 0.0.
43 *
44 * @version 1.1 08/19/2000
45 * @author Andy Molloy
46 */
47 public class generator
48 {
49 /** The variables the generated expression may use. */
50 variablePackage variables;
51 /** The user defined settings that influence the generation of expressions. */
52 globalSettings settings;
53 /** A list of the available operators. */
54 operatorInterface list[];
55
56 /** Class constructor which sets the object's settings and variablePackage. */
57 public generator(globalSettings s, variablePackage v)
58 {
59 variables = v;
60 settings = s;
61 list = settings.getOperators(); // Get the list of available operators and put them in a convenience member variable
62 }
63
64 /** Returns a generated expressionTree based on the given Random object. */
65 public expressionTree generate(Random randomNumber)
66 {
67 return generate(0.0, randomNumber);
68 }
69
70 /** Returns a generated expressionTree based ont he given Random object, starting at the level<I>th</I> level of the tree. */
71 public expressionTree generate(double level, Random randomNumber)
72 {
73 // Here's where the magic takes place.
74 expressionTree root = new expressionTree(); // Start by making a new expressionTree
75
76 double c = settings.getDoubleProperty("complexity"); // and getting the values for our complexity, depreciation,
77 double d = settings.getDoubleProperty("depreciation"); // and variable probability from the settings.
78 double v = settings.getDoubleProperty("variable.probability");
79
80 c -= d * level; // Since the process is recursive, and complexity (c) is not passed as a parameter, we subtract the depreciation
81 // (d) value from it, multiplied by the current level. c may drop below zero at this point, but it is used
82 // only in a comparison, so that's okay.
83
84 if( randomNumber.nextDouble() > c ) // Decide if we should make this a terminal node
85 { // Okay we want a terminal node, so decide if it should be a
86 // value or variable
87 if( randomNumber.nextDouble() > v )
88 {
89 // it's a value
90 root = new value(randomNumber.nextDouble()*2.0-1.0);
91 }
92 else
93 {
94 // it's a variable
95 // This section of code is likely to change. At the moment the available variables are hard coded into this
96 // routine, which does not make for a very portable solution. For instance, this routine would have to be rewritten
97 // to include a time variable. variablePackage will likely be rewritten in the near future to support an arbitrary
98 // number of variables, and this section of code rewritten to take advantage of that.
99 boolean flag = false;
100
101 while (!flag) // We need to decide which variable to use for this node. Since each variable has its own
102 { // chance of occuring, we need to keep picking one and deciding based on a random number and the
103 // variables likelyhood to occur until the program decides to keep one. NOTE: This could result
104 // in an infinite loop if all variables have a probability of 0.0. Currently, the settings package
105 // makes an attempt to prevent this situation, though some testing should be done here, too.
106 double variabletype = randomNumber.nextDouble();
107 double chance = randomNumber.nextDouble();
108 // This is really very messy and should be rewritten as soon as possible...
109 if( variabletype < 0.2 )
110 {
111 if ( chance < settings.getDoubleProperty("variable.x") )
112 {
113 flag = true;
114 root = variables.getVariable("x");
115 }
116 }
117 else if ( variabletype < 0.4 )
118 {
119 if ( chance < settings.getDoubleProperty("variable.y") )
120 {
121 flag = true;
122 root = variables.getVariable("y");
123 }
124
125 }
126 else if ( variabletype < 0.6 )
127 {
128 if ( chance < settings.getDoubleProperty("variable.r") )
129 {
130 flag = true;
131 root = variables.getVariable("r");
132 }
133
134 }
135 else if ( variabletype < 0.8 )
136 {
137 if ( chance < settings.getDoubleProperty("variable.theta") )
138 {
139 flag = true;
140 root = variables.getVariable("theta");
141 }
142 }
143 else
144 {
145 flag = true;
146 root = variables.getVariable("time");
147 }
148 // </messy>
149 }
150 }
151 }
152 else
153 { // Okay, we decided to not make this a terminal node, so it's an operation
154 root = new expressionTree(); // make a new expressionTree
155 root.setOperator(pickRandomOp(randomNumber)); // pickRandomOp is method defined below that chooses a new operator
156
157 int count;
158 int numParams = root.getNumParams(); // now that we have an operator, we need to define some parameters for it
159 if (numParams != 0)
160 {
161 expressionTree params[] = new expressionTree[numParams]; // so we make an array of expressionTrees...
162
163 for(count = 0; count < numParams; count++)
164 {
165 params[count] = generate(level + 1.0, randomNumber); // and recurse to generate each of the paramters, at 1 level deeper
166 }
167 root.setParams(params); // and then set the parameters
168 }
169 }
170
171 return(root);
172 }
173
174 /** Returns a randomly chosen operatorInterface object. */
175 operatorInterface pickRandomOp(Random whichOp)
176 {
177 boolean flag = false;
178 operatorInterface pick = new addition(); // The compiler complains if we don't set this equal to something, so we do
179 double chance;
180
181 while (!flag) // This could result in an infinite loop if all operators have their probability set to 0.0.
182 { // The settings package makes an attempt to prevent that from occurring
183 pick = list[(int)(whichOp.nextDouble() * list.length)];
184 chance = whichOp.nextDouble();
185 if ( chance < settings.getDoubleProperty(pick.getName()) )
186 {
187 flag = true;
188 }
189 }
190
191 return pick;
192 }
193
194 }