If you need assistance, please send an email to forum at 4hv dot org. To ensure your email is not marked as spam, please include the phrase "4hv help" in the subject line. You can also find assistance via IRC, at irc.shadowworld.net, room #hvcomm.
Support 4hv.org!
Donate:
4hv.org is hosted on a dedicated server. Unfortunately, this server costs and we rely on the help of site members to keep 4hv.org running. Please consider donating. We will place your name on the thanks list and you'll be helping to keep 4hv.org alive and free for everyone. Members whose names appear in red bold have donated recently. Green bold denotes those who have recently donated to keep the server carbon neutral.
Special Thanks To:
Aaron Holmes
Aaron Wheeler
Adam Horden
Alan Scrimgeour
Andre
Andrew Haynes
Anonymous000
asabase
Austin Weil
barney
Barry
Bert Hickman
Bill Kukowski
Blitzorn
Brandon Paradelas
Bruce Bowling
BubeeMike
Byong Park
Cesiumsponge
Chris F.
Chris Hooper
Corey Worthington
Derek Woodroffe
Dalus
Dan Strother
Daniel Davis
Daniel Uhrenholt
datasheetarchive
Dave Billington
Dave Marshall
David F.
Dennis Rogers
drelectrix
Dr. John Gudenas
Dr. Spark
E.TexasTesla
eastvoltresearch
Eirik Taylor
Erik Dyakov
Erlend^SE
Finn Hammer
Firebug24k
GalliumMan
Gary Peterson
George Slade
GhostNull
Gordon Mcknight
Graham Armitage
Grant
GreySoul
Henry H
IamSmooth
In memory of Leo Powning
Jacob Cash
James Howells
James Pawson
Jeff Greenfield
Jeff Thomas
Jesse Frost
Jim Mitchell
jlr134
Joe Mastroianni
John Forcina
John Oberg
John Willcutt
Jon Newcomb
klugesmith
Leslie Wright
Lutz Hoffman
Mads Barnkob
Martin King
Mats Karlsson
Matt Gibson
Matthew Guidry
mbd
Michael D'Angelo
Mikkel
mileswaldron
mister_rf
Neil Foster
Nick de Smith
Nick Soroka
nicklenorp
Nik
Norman Stanley
Patrick Coleman
Paul Brodie
Paul Jordan
Paul Montgomery
Ped
Peter Krogen
Peter Terren
PhilGood
Richard Feldman
Robert Bush
Royce Bailey
Scott Fusare
Scott Newman
smiffy
Stella
Steven Busic
Steve Conner
Steve Jones
Steve Ward
Sulaiman
Thomas Coyle
Thomas A. Wallace
Thomas W
Timo
Torch
Ulf Jonsson
vasil
Vaxian
vladi mazzilli
wastehl
Weston
William Kim
William N.
William Stehl
Wesley Venis
The aforementioned have contributed financially to the continuing triumph of 4hv.org. They are deserving of my most heartfelt thanks.
Registered Member #27
Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058
I have developed the pseudo random generator search program to a genetic algorithm where each gene is a machine code instruction. It evolves the solution to a function expressed in the source code of the program. It works quite well for many simple functions and some times discovers solutions that are not completely obvious. For example it finds optimal solutions to functions like R0=R0*164 without problems: ADD R1,R0,R0,LSL #2 ADD R0,R0,R1,LSL #3 MOV R0,R0,R0,LSL #2
As expected there is a fundamental problem that puts a serious limit on how well it works on non trivial functions. The genes have these properties: 1. Changing all bits in a gene might not change the function of the gene. 2. Changing just one bit may change the function completely.
This means that the search space is not smooth at all and contains many walls that requires several very unlikely mutations to traverse. To put it another way, a gene that gives a near perfect result may be completely wasted because the perfect result may require a completely different gene. and the evolution will be stuck at a false optimum until mutations happen to traverse the wall. To make things worse getting stuck at a false optimum causes the genetic variation to sink as most genes are slowly replaced by genes of the same type as the false optimum, this makes progress even less likely.
So any changes that smooth out the search space by even a small amount will cause a large improvement in efficiency. Using machine code instructions directly as genes seems like a particularly bad idea, something more abstract like reverse Polish notation will probably work a lot better but be far more complex since it will require several additional steps to end up with optimal machine code.
Registered Member #177
Joined: Wed Feb 15 2006, 02:16PM
Location: Munich, Germany
Posts: 214
Interesting, what scheme are you particulary using? Do you use 1 individual and mutate it until the solution fits, or do you use a bunch of individuals and let them recombine?
Registered Member #27
Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058
I have 2048 programs with N instructions in each, usually N=4 since it is enough to do interesting things and still does not take days to complete.
I compare the output from each program with the target function, then I sort the programs after how well they fit.
The plan was to let the most fit programs reproduce and over write the least fit ones, but that did not work well. The result was lots of upper class snobs with very little genetic variation and there were no progress. So instead I just select two and two instructions by random to breed new instructions. The mutation stage inverts 0.1% of the bits on random.
Then I repeat the process until the fit is 100% or I get tired of waiting.
Registered Member #52
Joined: Thu Feb 09 2006, 04:22AM
Location: Austin TX
Posts: 57
I tried my hand at genetic programming almost a decade ago and found it to be a lot harder to get working than a genetic algorithm. You seem to have run into the same problems that I did. Your fitness function could send you in the wrong direction and changing a single bit can generate wildly different values.
To get around the issue of changing a single bit causing major changes I used a tree where a node could be a math operation, memory operation, or constant value. Since math or memory operations would create or destroy new nodes then they were set to a lower change percentage. This also meant that the program size was not constant and reproduction was asexual. RPN might work just as well as a tree.
My fitness function also had to take into account different aspects of fitness. For instance one of the programs I was trying to do was a sort algorithm, so I had to check how well sorted the values were, if the values changed, and how many of the new values were in the original set.
This site is powered by e107, which is released under the GNU GPL License. All work on this site, except where otherwise noted, is licensed under a Creative Commons Attribution-ShareAlike 2.5 License. By submitting any information to this site, you agree that anything submitted will be so licensed. Please read our Disclaimer and Policies page for information on your rights and responsibilities regarding this site.
Genetic programming
