On the Genetic Algorithm
Hello all,
I thought some of you might be interested in my recent investigations on the
genetic algorithm. First, some introduction:
Some time back, I recalled in a post about a program I wrote maybe ten years ago
that calculates formulas based on inputs and solutions. I have since
reconstructed it in Euphoria. Calculates formulas? More properly said, it
"evolves" an algorithm for the solution to the formula. The steps of the
algorithm are in the gene code. Currently, one must manually convert from
evolved algorithm to formula. Perhaps a future version will simplify this.
In a nutshell the program, which I call GA Math, works like this: a population
of "beings" is created in which each being has a copy of the "register" (sequence
of six atoms) and a set of genes that is a sequence of four integers: {opcode,
from1, from2, store}. The opcode may refer to an add, subtract, multiply or
other simple mathematical operation. The "from" and "store" items refer to any
one of the register locations. So, for example, the gene {4,1,3,2} says to do
math-operation number 4 on the contents of register[1] and register[3] and store
it in register[2]. The beings each have a private number (p) also. From an
entered formula, such as v=l*w*h, the main register is filled with a random
number for each variable: {l,w,h,0,0,0}. Each being gets a copy of the main
register, but with the private number added: {l,w,h,p,0,0}. All of the being's
calculations are done into its copy of the register. Currently the number of
genes per being ranges from 6 to 12 which is decided randomly.
The program user enters a formula. By means of the functionality of David
Cuny's eval.e, it is evaluated to generate random numbers for each variable and
to create the answer to the formula based on these generated numbers. Each being
produces some answer on each try. The whole population attempts (currently) 8
times to calculate answers before the evolutionary selection process. The
percentage differences of each answer from the true answer are summed and
averaged for each being. The population is sorted according to closeness of fit.
The less accurate half of the population "dies" and is refilled with variations
of the top (more successful) half. Randomness controls these variations, but
selection is the controller of randomness, so to speak. That is, as with life
itself, there is the reward of continuity for responding positively to the
environment.
So much for the way it works. I was never much interested in reproducing
theories of how real life uses information in complex ways to effect both
continuity and change. It is the most basic quality of evolution that I found
fascinating: exploiting variation to adapt to a dynamic environment. But one
point here before I go on: there is a problem that I think is built-in to all
evolution. It tends to get stuck. If a partially successful or temporarily
successful evolution occurs, it tends to propagate throughout the whole
population and that tends to close off other, possibly more relevant, directions
of change. This is not a trivial thing, as it can, and no doubt has, killed off
many lifeforms.
Now to a lighter side of evolution. Here is a typical report from the program
with a few comments added. (The program clips out irrelevant genes and "froms".)
--------------------------------------------------
GA Math Beings Report
--------------------------------------------------
Math Beings working on formula : l*w*h--volume formula v=l*w*h
Number of try-sets per run : 500
Number of runs this session : 2
Number of tries per try-set : 8
This is try-set number : 6
Target value : 0.0010
Current closeness (percent) : 0.000000
Most successful being's original register values:
{[1.83] , [43.67] , [21.44] , [6.82] , [0] , [0]}
-- [l] [w] [h] [p] <<<< please read these comments
Most successful being's relevant genes:
abs, 1, 6
{[1.83] , [43.67] , [21.44] , [6.82] , [0] , [1.83]}
--result in register six ^
mul, 2, 6, 2
{[1.83] , [79.92] , [21.44] , [6.82] , [0] , [1.83]}
--in two ^
mul, 2, 3, 6
{[1.83] , [79.92] , [21.44] , [6.82] , [0] , [1713.40]}
--final answer in six ^
Last actual answer from formula: 1713.401
-------------------------------------
Notice it "wasted" a move in "abs 1,6". This is typical and common. There is
no penalty for inefficiency of algorithm because getting the right answer takes
all the focus. One reason for this post is to show the oddity of the genetic
algorithm as compared with our own mental processes.
Though at times the results are satisfyingly logical, here is an example of its
different kind of "thinking" responding to a user entry of c=3.14159*r*2
(remember that the population never sees the PI number, only the radius):
--------------------------------------------------
GA Math Beings Report
--------------------------------------------------
Math Beings working on formula : 3.14159*r*2
Number of try-sets per run : 500
Number of runs this session : 3
Number of tries per try-set : 8
This is try-set number : 55
Target value : 0.0010
Current closeness (percent) : 0.000983
Most successful being's original register values:
{[51.48] , [4.28] , [0] , [0] , [0] , [0]}
-- [r] ^ note the private number of this being
Most successful being's genes:
add, 1, 1, 6
{[51.48] , [4.28] , [0] , [0] , [0] , [102.96]}
--nice start, it doubles the radius (r) and stores it in register six
mul, 2, 1, 2
{[51.48] , [220.18] , [0] , [0] , [0] , [102.96]}
--this is 4.28*r stored in register two (note: 4.28=2PI-2)
add, 6, 2, 6
{[51.48] , [220.18] , [0] , [0] , [0] , [323.14]}
--here is the correction for the error of the private number
--so instead of PI*r*2 it is r(2PI-2)+2r --> (2PIr-2r)+2r --> 2PIr
Last actual answer from formula: 323.458
-------------------------------------
I have seen far stranger things than this. In the inevitable comparison of the
genetic algorithm to a thinking mind, it is the strangeness that stands out, the
otherness. However, down below the evolutionarily-derived conscious mind, I have
no doubt there is plenty of GA hairiness 
As to uploading the code, I may, if I can clean up the code enough, or I may
just offer it to anyone intested. It certainly could use some improvement. The
conversion from algorithmic steps to a coherent formula would be nice, as would
more math operations, and protection from overflow that more elaborate functions
would need.
If this sort of thing were optimized and tweaked, it could potentially generate
new previously unknown formulas from correct inputs and results, but that is far
off now...
--Quark
|
Not Categorized, Please Help
|
|
