Skip to content
Newer
Older
100644 666 lines (612 sloc) 39.1 KB
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
1 README.txt
2
3 Lee Spector (lspector@hampshire.edu), started 20100227
97a57b5 @lspector Obsoleted the README version history in favor of the github commit log.
authored Nov 12, 2011
4 See version history at https://github.com/lspector/Clojush/commits/master
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
5
97a57b5 @lspector Obsoleted the README version history in favor of the github commit log.
authored Nov 12, 2011
6 This is the README file accompanying Clojush, an implementation of the
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
7 Push programming language and the PushGP genetic programming system in the
8 Clojure programming language. Among other features this implementation
9 takes advantage of Clojure's facilities for multi-core concurrency. Use
10 Java's -XX:+UseParallelGC option to take maximum advantage of this feature.
11
97a57b5 @lspector Obsoleted the README version history in favor of the github commit log.
authored Nov 12, 2011
12 AVAILABILITY
13
14 https://github.com/lspector/Clojush/
15
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
16 REQUIREMENTS
17
18 To use this code you must have a Clojure programming environment; see
34e32ce @lspector Updated Clojure version in readme; flush after failure.
authored Jul 7, 2012
19 http://clojure.org/. The current version of clojush requires clojure 1.3.
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
20
9b2aca4 @lspector Updated README.txt.
authored Jul 17, 2012
21 Clojure is available for most OS platforms. A good starting point for
22 obtaining and using Clojure is http://dev.clojure.org/display/doc/Getting+Started.
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
23
24 QUICKSTART
25
9b2aca4 @lspector Updated README.txt.
authored Jul 17, 2012
26 Using Leiningen (from https://github.com/technomancy/leiningen) you can
27 run an example from the OS command line (in the Clojush directory) with
28 a call like:
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
29
b464fb1 @lspector Fixed lein command in README.txt.
authored Aug 21, 2012
30 lein run clojush.examples.simple-regression
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
31
32 This will load everything and run PushGP on a simple symbolic
33 regression problem (symbolic regression of y=x^3-2x^2-x). Although the
34 details will vary from run to run, and it's possible that it will fail,
35 this usually succeeds in a few generations.
36
9b2aca4 @lspector Updated README.txt.
authored Jul 17, 2012
37 Another simple (perhaps simpler) option is to use Clooj. To run an example
38 in Clooj, download and launch the latest "standalone" build from
39 https://github.com/arthuredelstein/clooj, open the Clojush project,
40 open an example file within Clojush/src/clojush/examples, and select
41 REPL > Evaluate entire file.
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
42
9b2aca4 @lspector Updated README.txt.
authored Jul 17, 2012
43 In other IDEs there will be other ways to run the examples. For example,
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
44 in Eclipse/Counterclockwise you can simply open an example and select
9b2aca4 @lspector Updated README.txt.
authored Jul 17, 2012
45 Clojure > Load clojure file in REPL. Similarly, in Clooj
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
46
9b2aca4 @lspector Updated README.txt.
authored Jul 17, 2012
47 For large-scale runs you may want to provide additional arguments to
48 java in order to allow access to more memory and/or to take maximal
49 advantage of Clojure's concurrency support in the context of clojush's
50 reliance on garbage collection. For example, you might want to provide a
51 rguments such as -Xmx2000m and -XX:+UseParallelGC. Details will depend
52 on the method that you use to launch your code.
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
53
54 DESCRIPTION
55
56 Clojush is a version of the Push programming language for evolutionary
57 computation, and the PushGP genetic programming system, implemented in
58 clojure. More information about Push and PushGP can be found at
59 http://hampshire.edu/lspector/push.html.
60
61 Clojush derives mainly from Push3 (for more information see
62 http://hampshire.edu/lspector/push3-description.html,
63 http://hampshire.edu/lspector/pubs/push3-gecco2005.pdf) but it is not
64 intended to be fully compliant with the Push3 standard and there are a
65 few intentional differences. It was derived most directly from the Scheme
66 implementation of Push/PushGP (called Schush). There are several differences
67 between Clojush and other versions of Push3 -- for example, almost all of the
68 instruction names are different because the "." character has special
69 significance in Clojure -- and these are listed below.
70
71 If you want to understand the motivations for the development of Push, and
72 the variety of things that it can be used for, you should read a selection of
73 the documents listed at http://hampshire.edu/lspector/push.html, probably
74 starting with the 2002 Genetic Programming and Evolvable Machines article
75 that can be found at http://hampshire.edu/lspector/pubs/push-gpem-final.pdf.
76 But bear in mind that Push has changed over the years, and that Clojush is
77 closest to Push3 (references above).
78
79 Push can be used as the foundation of many evolutionary algorithms,
80 not only PushGP (which is more or less a standard GP system except
81 that it evolves Push programs rather than Lisp-style function trees --
82 which can make a big difference!). It was developed primarily for
83 "meta-genetic-programming" or "autoconstructive evolution" experiments, in
84 which programs and genetic operators co-evolve or in which programs produce
85 their own offspring while also solving problems. But it turns out that
86 Push has a variety of uniquely nice features even within a more
87 traditional genetic programming context; for example it makes it unusually
88 easy to evolve programs that use multiple data types, it provides novel and
89 automatic forms of program modularization and control structure co-evolution,
90 and it allows for a particularly simple form of automatic program
91 simplification. Clojush can serve as the foundation for other evolutionary
92 algorithms, but only the core Push interpreter and a version of PushGP
93 are provided here.
94
95 USAGE
96
9b2aca4 @lspector Updated README.txt.
authored Jul 17, 2012
97 Example calls to PushGP are provided in other accompanying files.
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
98
99 Push programs are run calling run-push, which takes as arguments a Push
100 program and a Push interpreter state that can be made with make-push-state.
101 If you are planning to use PushGP then you will want to use this in the error
102 function (a.k.a. fitness function) that you pass to the pushgp function.
103 Here is a simple example of a call to run-push, adding 1 and 2 and returning
104 the top of the integer stack in the resulting interpreter state:
105
106 (top-item :integer (run-push '(1 2 integer_add) (make-push-state)))
107
108 If you want to see every step of execution you can pass an optional third
109 argument of true to run-push. This will cause a representation of the
110 interpreter state to be printed at the start of execution and after
111 each step. Here is the same example as above but with each step printed:
112
113 (top-item :integer (run-push '(1 2 integer_add) (make-push-state) true))
114
115 See the "parameters" section of the code for some parameters that will affect
116 execution, e.g. whether code is pushed onto and/or popped off of the code
117 stack prior to/after execution, along with the evaluation limits (which can be
118 necessary for halting otherwise-infinite loops, etc.).
119
120 Run-push returns the Push state that results from the program execution; this
121 is a Clojure map mapping type names to data stacks. In addition, the map
122 returned from run-push will map :termination to :normal if termination was
123 normal, or :abnormal otherwise (which generally means that execution was
124 aborted because the evaluation limit was reached.
125
126 Random code can be generated with random-code, which takes a size limit and a
127 list of "atom generators." Size is calculated in "points" -- each atom and
128 each pair of parentheses counts as a single point. Each atom-generator should
129 be a constant, or the name of a Push instruction (in which case it will be
130 used literally), or a Clojure function that will be called with no arguments
131 to produce a constant or a Push instruction. This is how "ephemeral random
132 constants" can be incorporated into evolutionary systems that use Clojush --
133 that is, it is how you can cause random constants to appear in
134 randomly-generated programs without including all possible constants in the
135 list of elements out of which programs can be constructed. Here is an example
136 in which a random program is generated, printed, and run. It prints a message
137 indicating whether or not the program terminated normally (which it may not,
138 since it may be a large and/or looping program, and since the default
139 evaluation limit is pretty low) and it returns the internal representation of
140 the resulting interpreter state:
141
142 (let [s (make-push-state)
143 c (random-code
144 100 ;; size limit of 100 points
145 (concat @registered-instructions ;; all registered instrs
146 (list (fn [] (rand-int 100)) ;; random integers from 0-99
147 (fn [] (rand)))))] ;; random floats from 0.0-1.0
148 (printf "\n\nCode: %s\n\n" (apply list c))
149 (run-push c s))
150
151 If you look at the resulting interpreter state you will see an "auxiliary"
152 stack that is not mentioned in any of the Push publications. This exists
153 to allow for auxiliary information to be passed to programs without using
154 global variables; in particular, it is used for the "input instructions"
155 in some PushGP examples. One often passes data to a Push program by pushing
156 it onto the appropriate stacks before running the program, but in many
157 cases it can also be helpful to have an instruction that re-pushes the
158 input whenever it is needed. The auxiliary stack is just a convenient place
159 to store the values so that they can be grabbed by input instructions and
160 pushed onto the appropriate stacks when needed. Perhaps you will find other
161 uses for it as well, but no instructions are provided for the auxiliary stack
162 in Clojush (aside from the problem-specific input functions in the examples).
163
6edcd7f @lspector Minor fixes to README.txt.
authored Jul 14, 2012
164 The pushgp function is used to run PushGP. It takes all of its parameters
165 as keyword arguments, and provides default values for any parameters that are
166 not provided. See the pushgp defn in pushgp/pushgp.clj for details. The single
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
167 argument that must be provided (actually it too has a default, but it makes
168 no sense to rely on that) is :error-function, which should be a function that
169 takes a Push program and returns a list of errors. Note that this assumes
170 that you will be doing single-objective evolution with the objective being
171 thought of as an error to be minimized. This assumption not intrinsic to Push
172 or PushGP; it's just the simplest and most standard thing to do, so
173 it's what I've done here. One could easily hack around that. In the most
174 generic applications you'll want to have your error function run through a
175 list of inputs, set up the interpreter and call run-push for each,
176 calculate an error for each (potentially with penalties for abnormal
177 termination, etc.), and return a list of the errors.
178
179 Not all of the default arguments to pushgp will be reasonable for all
180 problems. In particular, the default list of atom-generators -- which is ALL
181 registered instructions, a random integer generator (in the range from 0-99)
182 and a random float generator (in the range from 0.0 to 1.0) -- will be
183 overkill for many problems and is so large that it may make otherwise simple
184 problems quite difficult because the chances of getting the few needed
185 instructions together into the same program will be quite low. But on the
186 other hand one sometimes discovers that interesting solutions can be formed
187 using unexpected instructions (see the Push publications for some examples of
188 this). So the set of atom generators is something you'll probably want to
189 play with. The registered-for-type function can make it simpler to include
190 or exclude groups of instructions. This is demonstrated in some of the
191 examples.
192
193 Other pushgp arguments to note include those that control genetic
194 operators (mutation, crossover, and simplification). The specified operator
195 probabilities should sum to 1.0 or less -- any difference between the sum and
196 1.0 will be the probability for "straight" (unmodified) reproduction. The use
197 of simplification is also novel here. Push programs can be automatically
198 simplified -- to some extent -- in a very straightforward way: because
199 there are almost no syntax constraints you can remove anything (one or more
200 atoms or sub-lists, or a pair of parentheses) and still have a valid
201 program. So the automatic simplification procedure just iteratively removes
202 something, checks to see what that does to the error, and keeps the simpler
203 program if the error is the same (or lower!).
204
205 Automatic simplification is used in this implementation of PushGP in three
206 places:
207
208 1. There is a genetic operator that adds the simplified program to the next
209 generation's population. The use of the simplification genetic operator will
210 tend to keep programs smaller, but whether this has benificial or detrimental
211 effects on search performance is a subject for future research.
212
213 2. A specified number of simplification iterations is performed on the best
214 program in each generation. This is produced only for the sake of the report,
215 and the result is not added to the population. It is possible that the
216 simplified program that is displayed will actually be better than the best
217 program in the population. Note also that the other data in the report
218 concerning the "best" program refers to the unsimplified program.
219
220 3. Simplification is also performed on solutions at the ends of runs.
221
222 Note that the automatic simplification procedure will not always find all
223 possible simplifications even if you run it for a large number of iterations,
224 but in practice it does often seem to eliminate a lot of useless code (and to
225 make it easier to perform further simplification by hand).
226
227 If you've read this far then the best way to go further is probably to read
228 and run the examples.
229
230 IMPLEMENTATION NOTES
231
232 A Push interpreter state is represented here as a Clojure map that maps type
233 names (keywords) to stacks (lists, with the top items listed first).
234
235 Push instructions are names of Clojure functions that take a Push
236 interpreter state as an argument and return it modified appropriately. The
237 define-registered macro is used to establish the definitions and
238 also to record the instructions in the global list registered-instructions.
239 Most instructions that work the same way for more than one type are
240 implemented using a higher-order function that takes a type and returns a
241 function that takes an interpreter state and modifies it appropriately.
242 For example there's a function called popper that takes a type and returns
243 a function -- that function takes a state and pops the right stack in the
244 state. This allows us to define integer_pop with a simple form:
245
246 (define-registered integer_pop (popper :integer))
247
248 In many versions of Push RUNPUSH takes initialization code or initial stack
249 contents, along with a variety of other parameters. The implementation of
250 run-schush here takes only the code to be run and the state to modify. Other
251 parameters are set globally in the parameters section below. At some point
252 some of these may be turned into arguments to run-push so that they aren't
253 global.
254
255 Miscellaneous differences between clojush and Push3 as described in the Push3
256 specification:
257
258 - Clojush instruction names use "_" instead of "." since the latter has
259 special meaning when used in Clojure symbols.
260 - Equality instructions use "eq" rather than "=" since the latter in not
261 explicitly allowed in clojure symbols.
262 - for similar reasons +, -, *, /, %, <, and > are replaced with add, sub,
263 mult, div, mod, lt, and gt.
264 - Boolean literals are true and false (instead of TRUE and FALSE in
265 the Push3 spec). The original design decision was based on the fact that
266 Common Lisp's native Boolean literals couldn't used without conflating
267 false and the empty list (both NIL in Common Lisp).
268 - Clojush adds exec_noop (same as code_noop).
269 - Clojush includes an execution time limit (via the parameter
270 evalpush-time-limit) that may save you from exponential code growth or other
271 hazards. But don't forget to increase it if you expect legitimate programs
272 to take a long time.
273
274 Push3 stuff not (yet) implemented:
275 - NAME type/stack/instructions
276 - Other missing instructions: *.DEFINE, CODE.DEFINITION, CODE.INSTRUCTIONS
277 - The configuration code and configuration files described in the Push3
278 spec have not been implemented here. The approach here is quite different,
279 so this may never be implemented
280
281 TO DO (SOMETIME, MAYBE)
282
283 - Clean up issues involving Push globals and PushGP parameters for the same
284 or similar things.
285 - Implement remaining instructions in the Push3 specification.
286 - Add more examples.
287 - Add support for seeding the random number generator.
288 - Add improved genetic operators, e.g. fair mutation/crossover and
289 constant-perturbing mutations.
290 - Improve the automatic simplification algorithm.
291 - Possibly rename the auxiliary stack the "input" stack if no other
292 uses are developed for it.
293 - Write a "sufficient-args" fn/macro to clean up Push instruction definitions.
294
6edcd7f @lspector Minor fixes to README.txt.
authored Jul 14, 2012
295 VERSION HISTORY -- NOW OBSOLETE. See https://github.com/lspector/Clojush/commits/master
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
296 20100227: - First distributed version.
297 20100301: - Added (shutdown-agents) for proper termination.
298 20100306: - Added history (of total errors of ancestors) to individuals.
299 - Commented out (shutdown-agents) because it prevents multiple
300 runs in a single launch of a Clojure REPL.
301 20100307: - Fixed bug in history: reproductive auto-simplification added
302 was adding duplicate items.
303 20100314: - Added instructions: *_shove, code_extract, code_insert,
304 code_subst, code_contains, code_container, code_position,
305 code_discrepancy, *_rand. NOTE that the presence of *_rand
306 instructions means that programs produced using the full set
307 of instructions may be non-deterministic. As of this writing
308 pushgp (via evaluate-individual) will evaluate an individual
309 only once, so it will always have whatever fitness value it
310 had upon first testing.
311 - Added globals to support integer_rand and float_rand:
312 min-random-integer, max-random-integer, min-random-float
313 max-random-float.
314 - Fixed bug in code_car that could produce nil.
315 - Made execute-instruction safe for nil (although it shouldn't
316 arise anyway).
317 - Added stress-test for testing and debugging new Push
318 instructions. See the stress-test documentation string for
319 details.
320 - Implemented size limits on intermediate results on code stack
321 (in code_cons, code_list, code-append, code_insert, code_subst,
322 exec_s, exec_y).
323 - Fixed bug in exec_s (was always a noop previously).
324 20100319: - Added problem-specific-report function (to be customized per
325 problem). This can also be a convenient place to put other
326 stuff that you want done once per generation.
327 - Added support for saving lists of ancestors (maternal line
328 only) along with global parameters to turn both this and the
329 saving of total-error histories on and off.
330 - Added missing calls to "keep-number-reasonable" in numeric
331 Push instructions. This eliminates some potential crashes from
332 runaway number growth.
333 20100320: - Added print-ancestors-of-solution parameter and code.
334 - Print simplification in report only with non-zero value for
335 report-simplifications parameter.
336 - Added sextic polynomial regression example. This example also
337 demonstrates the use of fitness penalties for abnormally
338 terminating programs.
339 - Added a new argument to problem-specific-report (NOTE: not
340 backward compatible).
341 20100417: - Added thread-local random number generator objects to avoid
342 contention.
343 - Print parameters at the start of pushgp.
344 - Added readme comments about concurrency, -Xmx2000m, and
345 -XX:+UseParallelGC.
346 - Converted time limit code to use System/nanoTime (thanks to
347 Brian Martin). This means that time limits must now be
348 expressed in nanoseconds rather than milliseconds, and I
349 believe it will eliminate contention for shared Date objects
350 (but this should be checked; if there is contention then
351 we should revert to using Date and use thread-local date
352 objects as is being done with the random number generator
353 objects).
354 - Added print-return utility function for debugging.
355 - Added a new Push instruction, code_wrap, which pushes a 1-item
356 list containing the previous top item of the code stack.
357 - Added a new Push instruction, code_map, which acts much like
358 Lisp's (or Scheme's or Clojure's) "map" functions, using the
359 top item on the exec stack as the function to map and the top
360 item on the code stack as the list to map it down. The list of
361 results is left on top of the code stack. This is implemented
362 as a "macro" instruction that expands into a Push code
363 fragment that: 1) for each item in the list on top of the
364 code stack (or for the single non-list item that is there)
365 quotes the item onto the code stack and then runs the code
366 that's on top of the exec stack; 2) uses code_wrap to push a
367 list containing the last result onto the code stack; 3)
368 executes as many instances of code_cons as are necessary to
369 add all of the other results onto the list. Note that this
370 will act like an ordinary "map" function only when the code on
371 the exec stack leaves a single output on the code stack in
372 place of each input on the code stack; if it consumes or
373 produces more or less code then the effect will be quite
374 different.
375 20100502: - Made thread-local random integer function (lrand-int) safe for
376 bignums, but arguments greater than 2^31-1 are treated as if
377 they were 2^31-1 (2147483647).
378 20100526: - Reimplemented subst to use clojure.walk/postwalk-replace. Also
379 fixed comment, which described args backwards. (The behavior
380 was correct, emulating Common Lisp subst.)
381 20100918: - Created Eclipse project.
382 - Deleted re-load/backtrace utils.
383 - Removed shuffle, as it is now in clojure.core (in Clojure 1.2).
384 - Removed gratuitous def in define-registered.
385 - Added atom for instruction-table.
386 - Added atom for registered-instructions; NOTE: requires user
387 code that refers to registered-instructions to refer to
388 @registered-instructions instead. (Example odd.clj changed
389 to reflect this.)
390 - Added to-do item "Convert structs to records, which should be
391 faster. Experiments with Clojure 1.2 show this to be faster
392 but there are not good examples yet to serve as the basis for
393 changes.
394 - Added atoms for global-atom-generators and
395 global-max-points-in-program.
396 - Changed pushgp to take keyword arguments rather than a parameter
397 map. NOTE: this requires calls to pushgp to be written differently.
398 Updated examples to reflect this.
399 20100921: - Removed random-element in favor of rand-nth.
400 - Cleaned up indentation, miscellaneous other cosmetic things.
401 - Added namespaces for all example files.
402 - Updated README to mention requirement for clojure 1.2 and to
403 remove mention of ClojureX which has been discontinued.
404 - Converted structures to records (a clojure 1.2 feature, should
405 be faster).
406 20101005: - Added error-handlers to agents.
407 20101014: - [Artificial ant, krypto, tg8, decimation]
408 - Added articial ant example from Koza (via Luke).
409 - Added "tg8" integer symbolic regression problem.
410 - Added krypto number puzzle example.
411 - Added pushgp "decimation" feature, in which elimination
412 tournaments, conducted after fitness testing, reduce the
413 size of the population to a specified fraction of its original
414 size (specified in a decimation-ratio argument to pushgp;
415 the tournament sized is specified via decimation-tournament-size).
416 The ordinary tournament-size parameter is still used for subsequent
417 selection from the decimated population. Any specified trivial
418 geography applies both to decimation and to subsequent selection.
419 20101017: - Reverted from records to structs; wasn't significantly faster and
420 structs allow for greater flexibility in use of state as map.
421 20101102: - Switched to new clojure.core/frequencies from depricated
422 seq-utils/frequencies (h/t Kyle Harrington), and similarly
423 for flatten.
424 - Added :include-randoms keyword argument for registered-for-type.
425 Defaults to true, but if specified as false then instructions
426 ending with "_rand" will be excluded.
427 - Raised invalid output penalty in tg8 (it was lower than reasonable
428 errors for that problem).
429 20101103: - Converted evalpush-limit and evalpush-time-limit into vars
430 (global-evalupush-limit and global-evalpush-time-limit) bound
431 to atoms that are reset by calls to pushgp (keyword arguments
432 :evalpush-limit and :evalpush-time-limit).
433 - Changed pushgp parameters in the tg8.clj example.
434 20101104: - Implemented stackless tagging (see http://push.i3ci.hampshire.edu/
435 2010/10/28/stackless-tagging/). Tag instructions take one of
436 the following forms:
437 tag_<type>_<number>
438 create tage/value association, with the value taken from the
439 stack of the given type and the number serving as the tag
440 untag_<number>
441 remove the association for the closest-matching tag
442 tagged_<number>
443 push the value associated with the closest-matching tag onto
444 the exec stack (or no-op if no associations).
445 Here "closest-matching" means the tag with lowest number that
446 is greater than or equal to the number of the tag being matched,
447 or the lowest-numbered tag if none meet this criterion. Tag
448 instructions are not implemented in the same way as other
449 instructions; they are detected and handled specially by the
450 interpreter (see execute-instruction). Tag instructions
451 can be included in pushgp runs by using the new ephemeral
452 random constant functions tag-instruction-erc,
453 untag-instruction-erc, and tagged-instruction-erc, each of
454 which takes a limit (for the numerical part) as an
455 argument.
456 - Added examples using tags: tagged_ant, tagged_regression, and
457 tagged_tg8.
458 20101106: - Tweaked parameters in ant examples; among other things,
459 increased simplification since bloat was an issue. Also
460 added some evolved solutions in comments.
461 20101107: - Added Koza's lawnmower problem example; this demonstrates how
462 to add a new type/stack on a problem-specific basis, without
463 altering clojush.clj.
464 20101204: - Added pushgp-map, which allows pushgp calls on maps of arguments,
465 and a demonstration of its use in argmap_regression.clj.
466 - Added :gen-class and -main definition (thanks Kyle Harrington).
467 - Fixed eval-push termination to return :abnormal for exceeding
468 time-limit (thanks Kyle Harrington).
469 20101205: - Added modified version of Kyle's version of the intertwined
470 spirals problem.
471 - Minor changes to this README.
472 20101208: - Added alternative methods for node selection, used in mutation
473 and crossover (drafted by Brian Martin, with suggestions
474 from Kyle Harrington). This introduced three new globals:
475 global-node-selection-method, global-node-selection-leaf-probability,
476 and global-node-selection-tournament-size, each of which holds
477 an atom, and three new parameters to pushgp: node-selection-method,
478 node-selection-leaf-probability, and node-selection-tournament-size.
479 The node-selection-method can be :unbiased (in which case nodes
480 are selected using the uniform distribution that was previously
481 used -- this is the default), :leaf-probability (in which case
482 the value of the node-selection-leaf-probability argument,
483 which defaults to 0.1, specifies the probability that leaves,
484 as opposed to internal nodes, will be selected -- this is the
485 method used by Koza and others in tree-based GP), or
486 :size-tournament (in which case the value of the
487 node-selection-tournament-size argument, which defaults to 2,
488 determines the tournament size for node tournaments, with the
489 largest subtree in the tournament set being selected).
490 20110111: - Added zipper stack and functions (thanks to Kyle Harrington for
491 draft code, although this was re-written).
492 - Added registered-nonrandom function.
493 - Modified odd.clj example to use registered-nonrandom.
494 - Added examples/dsoar.clj, a version of the "Dirt-Sensing,
495 Obstacle-Avoiding Robot" (DSOAR) problem first described in:
496 Spector, L. 1996. Simultaneous Evolution of Programs and their
497 Control Structures. In Advances in Genetic Programming 2, edited
498 by P. Angeline and K. Kinnear, pp. 137-154. Cambridge, MA: MIT Press.
499 http://helios.hampshire.edu/lspector/pubs/AiGP2-post-final-e.pdf
500 This version was written by Brian Martin in 2010-2011.
501 20110118: - Added support for tagged_code_<number> instructions. These are like
502 tagged_<number> instructions except that retrieved values are pushed
503 onto the code stack rather than the exec stack. Without these the
504 only way to get tagged values onto the code stack is to wrap
505 values with code_quote prior to tagging. An alternative approach
506 is to add new tagging instructions that automatically perform
507 code_quote wrapping, but for full generality that would require
508 new instructions for each type; also quote-tagged values would
509 always be destined for the code stack, while the scheme adopted
510 here allows any stored value to be retrieved either to exec or to
511 code.
512 - A value of 0 for the evalpush-time-limit parameter of pushgp
513 now means that no time limit will be enforced. This is also
514 now the default.
515 20110322: - Tag reference bug fixed in closest-association (>= changed to <=).
516 - Added mux (multiplexer) example (a couple of approaches in one file).
517 20110409: - Added support for no-pop tagging through a var called
518 global-pop-when-tagging (holding an atom with a boolean value)
519 and a boolean argument to pushgp called pop-when-tagging.
520 The defaults are true, for backwards compatibility. If
521 @global-pop-when-tagging is false (which will result from
522 passing false as a :pop-when-tagging keyword argument to pushgp)
523 then executing instructions of the form tag_<type>_<number>
524 will tag a value as usual, but the tagged item will not be popped
525 from its source stack.
526 - Removed no-pop hackage from mux example (thanks Kyle).
527 20110424: - Added Gaussian mutation for floating point literals. This is
528 a genetic operator on par with ordinary mutation, crossover,
529 and simplification, with the probability for applying this operator
530 set with the gaussian-mutation-probability argument to pushgp
531 (which defaults to zero). The behavior of this operator, when used,
532 is controlled by two other arguments to pushgp,
533 gaussian-mutation-per-number-mutation-probability (which is the
534 probability that any particular floating point number in the
535 program will actually be mutated -- this defaults to 0.5) and
536 gaussian-mutation-standard-deviation (which specifies the standard
537 deviation of the Gaussian noise generator that is used to
538 produce changes to numbers -- this defaults to 0.1).
539 - Added examples/gaussian_mutation_demo.clj to demonstrate Gaussian
540 mutation.
541 - Added examples/korns_regression_p12.clj, a symbolic regression
542 problem based on Michael Korns's draft chapter from GPTP11.
543 20110505: - Added complex number support. New instructions for the 'complex'
544 stack include: pop, dup, swap, rot, flush, eq, stackdepth, yank,
545 yankdup, shove, rand, add, sub, mult, divide, fromfloat,
546 frominteger, fromfloats, fromintegers, conjugate, magnitude,
547 and principal_sqrt. (Brian Martin)
548 20110517: - Added a "scaled-errors" function to support error-scaling as
549 described by Maarten Keijzer in Scaled Symbolic Regression, in
550 Genetic Programming and Evolvable Machines 5(3), pp. 259-269,
551 September 2004. This must be used in a problem's error function,
552 and then the outputs of the evolved program must be "unscaled."
553 See the documentation string for scaled-errors and also
554 examples/scaled_sextic.clj for details.
555 - Added examples/scaled_sextic.clj to demonstrate the use of
556 scaled-errors.
557 - Changed examples/sextic.clj to use squared errors and an error
558 threshold, in order to facilitate comparisons between the
559 versions that do and don't use error scaling.
560 - Made minor changes to the korns_regression_p12 example.
561 20110526: - Enforce size limits on zipper manipulation results.
562 20110607: - Added overlap utility function, overlap-demo (which just prints
563 some examples to show how overlap works), and code_overlap
564 instruction. Overlap can be applied to any two (possibly
565 nested) things and it returns a number between 0 (meaning
566 no overlap) and 1 (meaning exact match). The overlap utility
567 function returns a ratio, but the code_overlap instruction
568 pushes a float.
569 - Removed complex number support from 20110505. There were previous
570 reports of problems and I've noticed problems from the fact that
571 (apply + ()) => zero (as opposed to 0) in the clojush namespace
572 defined by the code as revised for complex number support. If
573 someone knows how to re-introduce complex number support without
574 such problems then please let me know.
575 20110618: - Switched to Kyle Harrington's version of overlap; it's more clear,
576 possibly faster, and may fix a hard-to-trace bug that cropped up
577 in a long evolutionary run (?).
578 20110624: - Replaced lawnmower and dsoar examples with bugfixed versions
579 (thanks to Kyle Harrington).
580 - Added namespace and made miscellaneous other changes to
581 clojush-tests.clj.
582 - Added support for tagged-code macros. Tagged-code macro calls
583 have the effect of code instructions, but they take their
584 code arguments from the tag space and they tag their code return
585 values. They are implemented as macros to leverage the existing
586 code instruction set; note that this means that a single call
587 will contribute more than one iteration step toward the
588 evalpush-limit. Tagged-code macros appear in programs as hash maps
589 that map :tagged_code_macro to true, :instruction to a code
590 instruction, :argument_tags to a sequence of tags to be used
591 to acquire arguments, and :result_tags to a sequence of tags
592 to be used for tagging results. Execution of a macro expands
593 the needed code onto the exec stack to grab arguments from the tag
594 space and push them on the code stack, execute the code instruction,
595 and tag results. Note that results will also be left on the code
596 stack if global-pop-when-tagging is false. Conceptually, tag values
597 are "baked in" to these macros in much the same way that tag values
598 are "baked in" to the instruction names for stackless tag
599 instructions; we use hash maps simply because there is more
600 information to bake in and this prevents us from having to parse
601 the names (which would get messy and also waste time). Because
602 the maps make it difficult to read programs, however, a utility
603 function called abbreviate-tagged-code-macros is provided to
604 produce copies of programs with more human-readable (but not
605 currently executable) representations of tagged-macro calls.
606 A tagged-code-macro-erc is provided to generate random tagged-code
607 macros in pushgp runs. A new example, codesize20, provides
608 a simple demonstration of the use of tagged-code macros.
609 - Replaced walk-based code-manipulation with walklist functions
610 that only traverse list structure. This fixes an interaction
611 between map literals (e.g. tagged-code macros) and program
612 structure.
613 20110629: - Fixed abbreviate-tagged-code-macros printing of empty lists.
614 - Added seq condition to walklist to permit walking of seqs that
615 aren't actually full-fledged lists.
616 20110702: - Several fixes/refinements to tagged-code macros:
617 - Fixed incorrect no-op of arg-free calls with empty tag space.
618 - Added :additional_args to tagged-code macro structure; the
619 value should be a list of items and these will be executed
620 in order before calling the macro's instruction.
621 - Added optional 5th arg to tagged-code-macro-erc; this should
622 be a function of zero args that will be called to produce
623 the value of :additional_args (e.g. if you want to have one
624 random integer arg then you could specify a 5th arg of
625 (fn [] (list (lrand-int 101))).
626 - Changed format produced by abbreviate-tagged-code-macros to
627 handle :additional_args and to be slightly more concise.
628 20110714: - Added "trace" argument to eval-push and run-push. If this is
629 true then the resulting state will map :trace to a list of
630 executed instructions and literals, in reverse order of
631 execution. If the argument is :changes then instructions that
632 have no effect on the state will be excluded.
633 20110809: - Several additions/enhancements by Kyle Harrington:
634 - Converted problem-specific-report to a parameter in pushgp.
635 - Added reporting of program repeat counts in population.
636 - Added "error-reuse" parameter to pushgp for use in stochastic
637 and dynamic problems (for which reuse would be turned off).
638 - Added examples/mackey_glass_int.clj, a symbolic regression
639 problem as described in Langdon & Banzhaf's 2005 paper
640 (citation in file).
641 - Added examples/pagie_hogeweg.clj problem, a difficult
642 symbolic regression problem when coevolution is not used.
643 Introduced by Pagie & Hogeweg's 1997 paper (citation in file).
644 20110911: - Switched from Eclipse to Clooj/Leiningen for development and
645 rearranged the project for this.
646 - Added calls to end of all example files.
647 - Examples can be run from the OS command line (assuming
648 that leiningen is available) with calls like:
649 lein run examples.simple-regression
650 - Added local-file dependency and used file* for file access.
651 - Removed ant and tagged-ant examples because of bugs related
652 to confusion of push interpreted states and ant world states.
34a01b9 @thelmuth Added log about string stack to README.txt.
thelmuth authored Nov 11, 2011
653 20111104: - Added string stack and a variety of string stack instructions.
654 - Added two example pushgp runs that use the string stack in
655 the file examples/string.clj.
97a57b5 @lspector Obsoleted the README version history in favor of the github commit log.
authored Nov 12, 2011
656 20111112: - Obsoleted this version history in favor of the commit logs
657 at https://github.com/lspector/Clojush/commits/master
b15d8e9 @lspector first commit after move to Clooj/Leiningen environment
authored Sep 11, 2011
658
659
660 ACKNOWLEDGEMENTS
661
662 This material is based upon work supported by the National Science Foundation
663 under Grant No. 1017817. Any opinions, findings, and conclusions or
664 recommendations expressed in this publication are those of the authors and
665 do not necessarily reflect the views of the National Science Foundation.
Something went wrong with that request. Please try again.