📄 lithos.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0045)http://www.esatclear.ie/~rwallace/lithos.html -->
<HTML><HEAD><TITLE>Lithos</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
<BODY>
<CENTER>
<H1>Lithos</H1></CENTER>
<P>Lithos is a stack based evolutionary computation system. Unlike most EC
systems, its representation language is computationally complete, while also
being faster and more compact than the S-expressions used in genetic
programming. The version presented here applies the system to the game of Go,
but can be changed to other problems by simply plugging in a different
evaluation function. Source code and Windows executable are provided. Let me
know by <A href="mailto:rwallace@esatclear.ie">email</A> if you have any queries
or interesting results or modifications.
<P>This software is in the public domain.
<P>THIS SOFTWARE IS PROVIDED STRICTLY AS IS. THE AUTHOR MAKES NO REPRESENTATION
OR WARRANTY OF ANY KIND, INCLUDING BUT NOT LIMITED TO ANY WARRANTY OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. UNDER NO CIRCUMSTANCES
SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT OR INDIRECT EXPENSES OR DAMAGES AS A
RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE.
<P><A name=Contents>
<H2>Contents</H2></A>
<P>
<UL>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#The genetic algorithm"><B>The
genetic algorithm</B></A>
<UL>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#Parameters">Parameters</A>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#The next generation">The
next generation</A>
<LI><A href="http://www.esatclear.ie/~rwallace/lithos.html#The log file">The
log file</A> </LI></UL>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#The virtual machine"><B>The
virtual machine</B></A>
<UL>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#The instruction set">The
instruction set</A>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#Control flow">Control
flow</A> </LI></UL>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#Example programs"><B>Example
programs</B></A>
<UL>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#Factorial(n) recursive style">Factorial(n)
recursive style</A>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#Factorial(n) iterative style">Factorial(n)
iterative style</A> </LI></UL>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#The game of Go"><B>The
game of Go</B></A>
<LI><A
href="http://www.esatclear.ie/~rwallace/lithos.html#Download"><B>Download</B></A>
</LI></UL>
<P><A name="The genetic algorithm">
<H2>The genetic algorithm</H2></A>
<P>Like other evolutionary computation systems, Lithos evolves a population of
individuals. In each generation, every individual is tested for fitness at a
task, then the less fit ones are replaced by offspring of the more fit ones,
using crossover and mutation to achieve variety.
<P>In this case, the individuals are programs, each represented as a sequence of
instructions. In testing fitness, each program is run on some input and the
output is evaluated according to some measure of quality. In the version
presented here, the input is the current state of the board in the game of Go,
and the output is interpreted as a decision about the next move to make.
<P><A name=Parameters>
<H3>Parameters</H3></A>
<P>The system is controlled by the following parameters:
<P><B>Population</B> is the number of programs. This doesn't change over time;
offspring of more fit programs replace less fit ones.
<P><B>Max Size</B> is the maximum allowed size of a program. (At the start of a
run, the entire population is initialized to empty programs. Crossover and
mutation may produce longer or shorter programs as generations go by, up to
<I>Max Size</I> instructions.)
<P><B>Max Memory</B> is the number of words of memory available to each program
at run time. (This does not include the memory to store the program code.) Must
be at least large enough to hold the program's input data; for the game of Go,
this means at least 383 words.
<P><B>Max Time</B> is the number of instructions can execute during its
"thinking time" in each move of the game (or step of the task or whatever). If
this is exceeded, the program times out and whatever it has left on the stack at
that point is taken as its output.
<P><B>Max Moves</B> is the maximum number of moves the game is allowed to
continue for. (In practice this will rarely be reached.)
<P><B>Overselection Rate</B> is the number of individuals in each generation
guaranteed to be transmitted unchanged to the next. With the default value of 2,
the best 2 individuals are copied to the next generation before tournament
selection takes place for the rest of the population slots.
<P><B>Tournament Size</B> is the number of individuals involved in each
selection tournament.
<P><B>Crossover Rate</B> and <B>Mutation Rate</B> control how often these two
operators will be applied when producing offspring programs for the next
generation. The default values of 50 and 50 mean they are equally likely to be
applied; 90 and 10, for example, would apply crossover 90% of the time and
mutation only 10%. At least one of these values must be nonzero.
<P><B>Autosave Frequency</B> controls how often the current population is
automatically saved to the <CODE>data</CODE> file in case of power failure or
other external interruption. The default value of 100 saves every 100
generations. A value of 1 would save every generation, 0 would turn off autosave
altogether.
<P><B>Log Frequency</B> controls how often entries are written to the
<CODE>log</CODE> file. The default value of 1 writes a log entry every
generation. A value of 10 would log every 10 generations (suitable for runs with
a small population for very many generations), 0 would turn off logging.
<P>The parameter values are read from a file called <CODE>params</CODE> if it is
present, otherwise the following defaults are used:
<P><PRE>[Population] 100
[Max Size] 1000
[Max Memory] 1000
[Max Time] 10000
[Max Moves] 1000
[Overselection Rate] 2
[Tournament Size] 4
[Crossover Rate] 50
[Mutation Rate] 50
[Autosave Frequency] 100
[Log Frequency] 1
</PRE>
<P>This is the format used, so creating a <CODE>params</CODE> file and inserting
the above into it will keep the defaults; individual entries can then be
changed. Note that if the file is present at all, it must have all the entries
in this exact order.
<P><A name="The next generation">
<H3>The next generation</H3></A>
<P>When all the individuals in a generation have been evaluated for fitness, the
program chooses some of them to be transmitted to the next generation. Taking
the default values of <I>Population</I> = 100, <I>Overselection Rate</I> = 2 and
<I>Tournament Size</I> = 4, the procedure is as follows:
<P>
<OL>
<LI>Fill the first 2 slots of the next generation with the 2 best individuals
of this one.
<LI>Fill each of the other 98 slots with an offspring of one or two current
individuals. </LI></OL>
<P>To fill a slot:
<P>
<OL>
<LI>Choose a parent by tournament selection.
<LI>Decide whether to use crossover or mutation according to the <I>Crossover
Rate</I> and <I>Mutation Rate</I> parameters.
<LI>If mutation, fill the slot with a mutated version of the parent.
<LI>If crossover, choose another parent by tournament selection, and fill the
slot with an offspring based on a combination of the parents' codes. </LI></OL>
<P>To choose a parent by tournament selection:
<P>
<OL>
<LI>Choose 4 individuals at random.
<LI>Select the most fit of those 4. </LI></OL>
<P>To mutate an individual:
<P>
<OL>
<LI>Choose at random whether to perform insertion, substitution or deletion
(equal probabilities, except if the individual is of zero length then only
insertion can be performed; if of length equal to <I>Max Size</I> then
insertion cannot be performed).
<LI>If insertion, choose an insertion point (between any two adjacent
instructions, or at the start or end, equal probability for each point) and
insert a random instruction there.
<LI>If substitution, choose an instruction and change it at random. (1 in 30
chance of changing it to the same instruction, i.e. leaving it unchanged.)
<LI>If deletion, choose an instruction and delete it.
<LI>Flip a coin; if it comes up heads, go back to step 1. (So usually only one
or two instructions will be mutated, but in theory any number could be.)
</LI></OL>
<P>To cross over two individuals:
<P>
<OL>
<LI>Choose a break point in each individual.
<LI>Copy the first individual's code up to its break point, then copy the
second individual's code from its break point on. </LI></OL>
<P>To choose a break point:
<P>
<OL>
<LI>The start and end are valid break points.
<LI>Every point between a label and a nonlabel instruction is also valid.
(Labels are explained under <A
href="http://www.esatclear.ie/~rwallace/lithos.html#Control flow">Control
flow</A>; the theory is that code should get spliced at reasonable breaks
between functional units. Informal eyeballing of debugging output suggests
this works fairly often.)
<LI>Choose a valid break point at random. </LI></OL>
<P>When all the slots in the population have been filled, the process of
evaluating all the individuals for fitness begins again.
<P><A name="The log file">
<H3>The log file</H3></A>
<P>The <CODE>log</CODE> file has columns for the following values:
<P><B>Generation:</B> The current generation number.
<P><B>Complexity:</B> The size of the most fit individual.
<P><B>Diversity:</B> The number of "subspecies" in the population, where two
programs belong to the same subspecies if their first and last instructions are
equal. (Zero length programs are ignored in this count, thus the maximum
possible value is 30 * 30 = 900. A crude measure, but simple to define and cheap
to compute.)
<P><B>Score:</B> A measure of the performance of the most fit individual at the
task. For games, it's the number of points scored by that individual when
playing against the second most fit one.
<P>The columns are tab separated so the file can easily be loaded into a
spreadsheet for plotting graphs.
<P><A name="The virtual machine">
<H2>The virtual machine</H2></A>
<P>Lithos uses a stack based virtual machine. A program within it consists of a
sequence of instructions, normally executed one after the other; most
instructions take their inputs from the stack and push their outputs onto it.
<P>The virtual memory is an array of words. Taking the default value of <I>Max
Memory</I> = 1000, memory addresses go from 0 to 999. Inputs are placed at the
bottom of memory - for the game of Go, words 0 to 382 are initialized to the
current state of the game, with the rest being zero.
<P>Each word contains an integer, 32 bits on typical hardware. (Or in general,
whatever the C compiler decides an <CODE>int</CODE> is. Note that
<I>Population</I> * <I>Max Size</I> cannot exceed the range of an
<CODE>int</CODE>; in practice, this means that the total size of all the VM
programs cannot exceed 2 gigabytes, which is a restriction that 32 bit machines
would impose anyway.) Thus, VM programs can directly handle, on typical systems,
numbers in the range of approximately -2 billion to +2 billion.
<P>The stack grows from the top down and is initially empty. It wraps around on
overflow or underflow. So if the first instruction is <CODE>CONST1</CODE>, the
value 1 will be placed in location 999. If the first instruction is
<CODE>ADD</CODE>, the stack will underflow so the input words in locations 0 and
1 will be added together and the result will be placed in location 1. (Evolved
programs quite often exploit this.)
<P>Stack words are left unchanged unless explicitly overwritten, so in the above
<CODE>ADD</CODE> example, location 0 will retain its original contents.
<P>When a program terminates (either by executing its last instruction or by
staying in a loop and timing out after <I>Max Time</I> instructions), whatever
it has left on top of the stack is taken as its output. (Because of wraparound,
this means that a null program will effectively echo its input - the first words
of the input will be "on top" of the stack.)
<P>While a single memory space is used for input, data stack and subroutine
return addresses, it is not used for program code. This is in a separate memory
area, and programs have no way to directly access their own code.
<P><A name="The instruction set">
<H3>The instruction set</H3></A>
<P>There are 30 instructions, each consisting of an opcode only (no immediate
operands). In the table below, the inputs are taken from the stack, pushed in
the order given (i.e. the last operand is on top of the stack) and the outputs
are pushed onto the stack.
<P>
<TABLE border=1>
<TBODY>
<TR>
<TH>Instruction</TH>
<TH>Inputs</TH>
<TH>Outputs</TH>
<TH>Description</TH></TR>
<TR>
<TD colSpan=4>Numbers</TD></TR>
<TR>
<TD><CODE>CONST0</CODE></TD>
<TD></TD>
<TD><CODE>0</CODE></TD>
<TD>Constant 0</TD></TR>
<TR>
<TD><CODE>CONST1</CODE></TD>
<TD></TD>
<TD><CODE>1</CODE></TD>
<TD>Constant 1</TD></TR>
<TR>
<TD><CODE>RANDOM</CODE></TD>
<TD></TD>
<TD><CODE>random(0..1)</CODE></TD>
<TD>Random number, either 0 or 1</TD></TR>
<TR>
<TD colSpan=4>Arithmetic</TD></TR>
<TR>
<TD><CODE>INC</CODE></TD>
<TD><CODE>x</CODE></TD>
<TD><CODE>x + 1</CODE></TD>
<TD>Increment</TD></TR>
<TR>
<TD><CODE>DEC</CODE></TD>
<TD><CODE>x</CODE></TD>
<TD><CODE>x - 1</CODE></TD>
<TD>Decrement</TD></TR>
<TR>
<TD><CODE>ADD</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x + y</CODE></TD>
<TD>Addition</TD></TR>
<TR>
<TD><CODE>SUB</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x - y</CODE></TD>
<TD>Subtraction</TD></TR>
<TR>
<TD><CODE>MUL</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x * y</CODE></TD>
<TD>Multiplication</TD></TR>
<TR>
<TD><CODE>DIV</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x / y</CODE></TD>
<TD>Division</TD></TR>
<TR>
<TD colSpan=4>Comparison</TD></TR>
<TR>
<TD><CODE>EQ</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x == y</CODE></TD>
<TD>Equal</TD></TR>
<TR>
<TD><CODE>NE</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x != y</CODE></TD>
<TD>Not equal</TD></TR>
<TR>
<TD><CODE>LT</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x < y</CODE></TD>
<TD>Less than</TD></TR>
<TR>
<TD><CODE>GT</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x > y</CODE></TD>
<TD>Greater than</TD></TR>
<TR>
<TD><CODE>LE</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x <= y</CODE></TD>
<TD>Less than or equal</TD></TR>
<TR>
<TD><CODE>GE</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x >= y</CODE></TD>
<TD>Greater than or equal</TD></TR>
<TR>
<TD colSpan=4>Logic</TD></TR>
<TR>
<TD><CODE>AND</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x and y</CODE></TD>
<TD>And</TD></TR>
<TR>
<TD><CODE>OR</CODE></TD>
<TD><CODE>x, y</CODE></TD>
<TD><CODE>x or y</CODE></TD>
<TD>Or</TD></TR>
<TR>
<TD><CODE>NOT</CODE></TD>
<TD><CODE>x</CODE></TD>
<TD><CODE>not x</CODE></TD>
<TD>Not</TD></TR>
<TR>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -