Eureqa in Science News

There's a nice little piece in the January 14, 2012 issue of Science News on Lipson and Schmidt's Eureqa system. (h/t to Stuart Card for the pointer.)

New Book (Free): "Evolved to Win", by Moshe Sipper

Recent years have seen a sharp increase in the application of evolutionary computation techniques within the domain of games. Situated at the forefront of this research tidal wave, Moshe Sipper and his group have produced a plethora of award-winning results, in numerous games of diverse natures, evidencing the success and efficiency of evolutionary algorithms in general­—and genetic programming in particular—at producing top-notch, human-competitive game strategies. From classic chess and checkers, through simulated car racing and virtual warfare, to mind-bending puzzles, this book serves both as a tour de force of the research landscape and as a guide to the application of evolutionary computation within the domain of games.

An outstanding, timely book in the rapidly growing area of computational intelligence in games. A must read for both the neophyte and the seasoned researcher, with all the hallmarks of a landmark book.

John Koza, author of Genetic Programming tetralogy

In Evolved to Win Moshe Sipper provides a treasure trove of detailed examples and advice on using evolutionary computation, in conjunction with human expertise, to solve hard puzzles and to win a wide variety of challenging games. Sipper and his colleagues know this field better than anyone else, having produced some of the field's strongest and most exciting results, and this book provides a comprehensive tour of their results along with ample guidance for newcomers to the field.

Lee Spector, Professor of Computer Science, Hampshire College, and Editor-in-Chief of the journal Genetic Programming and Evolvable Machines

Free download Hard copy

citing Journal > conference > tech reports

I have seen recently several papers which cite technical reports.
May be there are good reasons for this but it was my understanding
that where work is available in a number of places we should cite
journal articles before conference papers and only cite technical
reports if the work is not otherwise available.

Bill

Response to the review of "Variation-Aware Analog Structural Synthesis: A Computational Intelligence Approach"

Trent McConaghy, coauthor of Variation-Aware Analog Structural Synthesis: A Computational Intelligence Approach, wrote a response to the review of the book in Genetic Programming and Evolvable Machines and I have agreed to publish his response here. Trent's letter follows:

In the December issue of Genetic Programming and Evolvable Machines (volume 12:4), John Rieffel gave a review of the book "Variation-Aware Analog Structural Synthesis: A Computational Intelligence Approach", of which I was a co-author.  

We would like to express our thanks to John for a thoughtful review, covering the reliable and trustworthy approaches to perform industrially-oriented symbolic regression, robust optimization, and analog structural synthesis.  

We would like to clarify one point: while the review reports that the book ignores "simulators that cheat", the book in fact dedicates substantial space on this issue, and how open-ended synthesis approaches are highly prone to it.  (See pp. 157-167, including the section "SPICE can lie".)

The broader issue -- trustworthy synthesis -- is a broad challenge that the last half of the book addresses.  Trustworthy synthesis outputs circuits that a designer trusts enough to commit to silicon.  The book proposes to use hierarchical building blocks developed over the decades by expert designers, enabling synthesis to output circuits that are trustworthy by construction.

As the book discusses, the computational intelligence techniques presented generalize beyond analog CAD, to domains such as robotics, financial engineering, mechanical design, and more.  

 -- Trent McConaghy, October 3, 2011

New impact factor

The journal received its first impact factor from Journal Citation Reports last year (2010), for the 2009 publication year. Now (in 2011) we have new numbers for the 2010 publication year. They have improved somewhat and are, I think, strong for a journal as young as Genetic Programming and Evolvable Machines:

Impact factor: 1.167
Rank in category: Artificial Intelligence: 63 out of 108
Rank in category: Theory and Methods: 41 out of 97

Journal Citation Reports also provides an Immediacy Index, for which our numbers are:

Immediacy index: 0.143
Rank in category: Artificial Intelligence: 64 out of 108
Rank in category: Theory and Methods: 52 out of 97

Programming excel from training examples

Remember people said GP could not program a spread sheet, well it seems microsoft has done it. At PASTE 2011 last week Sumit Gulwani gave a keynote which included discussion of his recent paper at PLDI http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/Harris_2011_SIGPlan.html in which he describes a research tool which allowed users to program microsoft tools (such as their spread sheet excell and their word processor) from training examples. Ie automatically create macros and short scripts for users who do not wish to remember how to program. Technical details are a bit sketchy but it seems something like GP is in there. It may be available commercially in the future.

Bill

GPEM 12(4) now available online

The fourth issue of volume 12 of Genetic Programming and Evolvable Machines is now available online, with the following articles:

"Evolution of human-competitive lossless compression algorithms with GP-zip2"

by Ahmed Kattan and Riccardo Poli

"Defining locality as a problem difficulty measure in genetic programming"

by Edgar Galván-López, James McDermott, Michael O’Neill and Anthony Brabazon

"Accelerating floating-point fitness functions in evolutionary algorithms: a FPGA-CPU-GPU performance comparison"

by Juan A. Gomez-Pulido, Miguel A. Vega-Rodriguez, Juan M. Sanchez-Perez, Silvio Priem-Mendes and Vitor Carreira

"Long memory time series forecasting by using genetic programming"

by Emiliano Carreño Jara

SOFTWARE REVIEW

"GPLAB: software review"

by Indriyati Atmosukarto

BOOK REVIEW

"Trent McConaghy, P. Palmers, G. Peng, Michiel Steyaert, Georges Gielen: Variation-aware analog structural synthesis: a computational intelligence approach"

by John Rieffel

BOOK REVIEW

"Paul Coates: Programming architecture"

by Benachir Medjdoub

95% confident = 950/1000 for any distribution

A technique I have seen used for statistical confidence testing of non-Gaussian distributions is to generate 1000 random examples of the distribution. If the you want to be 95% confident that answer to be checked comes from the same distribution then it should be "like" 950 of the 1000 examples.

Eg if the distribution is reasonably well behaved then if the answer to be checked lies outside the range of the 25th to 975th example we can say we confidently reject the null hypothesis and say our answer is not from the distribution used to generate the 1000 examples. We do not need Z-scores, t-tests etc.

This non-parametric test should be ok with any distribution. We are effectively burning CPU cyles rather than spending brain cycles on devising and validating a statistical technique specifically for our new distribution.

Computational Intelligence Using Genetic Programming - GPTP'11

This is a repost of my piece on GPTP'11 from Epistasis Blog.

I just returned from the IXth Genetic Programming Theory and Practice Workshop held by the Center for the Study of Complex Systems at the University of Michigan. This is an invitation only workshop that brings together theorists and practitioners interested in the development and application of computer systems that can solve complex problems by developing their own programs (i.e. automatic programming). This group focuses on the use of genetic programming or GP to discover useful computer programs using the principles of evolution by natural selection. The proceedings from this workshop are published each year in a book that can be found on Amazon. The proceedings from this year will be published in late 2011 or early 2012.

The real value of this workshop is the large amount of time dedicted to open-ended discussion about how solve complex problems in medicine, industry, finance, etc. My own motivation for working with GP is to teach the computer how to solve a complex human genetics problem as I would. I do not believe that naive computer programs or analysis strategies such as those used in the agnostics genome-wide association study (GWAS) paradigm will be successful in addressing the complexity of the genotype-phenotype relationship. We, as human analysis engines, don't ignore the pathobiology of disease when we look at data. Why should we instruct the computer to do the same? Given infinite time, each of us would tinker and try new and different things with the data until we found a good answer that made biological sense. We would use our knoweldge of biochemistry, genomics, molecular biology, pathology and physiology to both frame the analysis and interpret the results. Our series of papers published as part of GPTP since 2006 have focused on adaptive computer programs that harness this kind of biological and biomedical knowledge to explore the space of computer programs that can build models of genetic architecture.

One of the more interesting and extended discussions at GPTP this year was about novelty-seeking. Ken Stanley gave a great talk about rewarding computer programs that explore new and different solutions to a problem (read more). His Picbreeder program is a nice example of novelty search in the sense that you can discover and develop interesting pictures without a clear initial objective in mind (e.g. evolve a picture of a car). An analogy in human genetics would be to reward computer program that generate genetic models of disease by exploring new biochemical pathways. I am working on approaches to try this within our own genetic analysis system. I like Ken's quote: "To achieve your highest goals, you must be willing to abandon them."

It is very clear that GP has been used to solve problems that humans or other computer programs haven't been able to. For example, Moshe Sipper has developed computer game players that rival human players (read more). Some of the participants (e.g. Michael Korns) even invest and make money using GP. This is a powerful way to do automatic programming and should be part of the broader toolbox of any complex problem-solver. I would be happy to send you a pre-print of our current GPTP paper.

EC presence at biology meetings

I've just come back from a round of biology meetings. Few biologists know that evolution in silica exists. They may know that GA is "something that GARLI does", but that's about it (GARLI is a GA-based phylogeny estimation package). Every time I speak of EC, it is very well received, with surprise and wonder.

It would be good if we could publicize at evolutionary biology meetings more. At a minimum, Springer reps should bring GPEM when they attend evolution meetings.

Non standard terminology

I came across two non standard uses of evolutionary computing jargon at GECCO. EC, like the rest of technical literature, is full of jargon. Jargon can be helpful where people agree on its meaning but confuses when it is misused. I have posted a link to the online glossary from "Genetic programming and data structures" on the GP mailing list. Hans-Georg Beyer has also defined evolutionary algorithms terminology.

GECCO 2011 bibtex GP bibliography

The latest release of the GP biblio contains more than one hundred entries from last month's GECCO conference in Dublin.
Bibtex files for the proceedings and companion are also online or searchable via CCSB

Wiki GP Bibliography

Adrian Carballal has created a wiki which allows you to maintain the GP bibliography's links to your homepage.

25 July 2011, University College, London, Genetic Programming for Software Engineering

The 14th CREST open workshop proved to be so popular that the free registrations were closed some weeks before hand.
Stephanie Forrest gave the keynote on evolving fixes to software for which she won the Humie.
Two other international speakers were Federica Sarro, who talked on estimating time to produce software using GP and Wasif Afzal, who reviewed GP for prediction (Slides, Video).
David White talked about new work on optimising server farms, JVM in cloud computing systems (Slides, Video). I talked about evolving a CUDA kernel for gzip running on a GeForce 295 GTX GPU (paper)

GPEM 12(3) [SI: Evolvable Hardware Challenges] now available online

The third issue of volume 12 of Genetic Programming and Evolvable Machines is now available online, with articles listed below. This is a big and exciting one, the special issue on Evolvable Hardware Challenges, edited by Pauline Haddow. Note also that the introduction and two of the other articles are available for free under open access.

"Introduction: special issue on evolvable hardware challenges"

by Pauline C. Haddow

"Challenges of evolvable hardware: past, present and the path to a promising future"

by Pauline C. Haddow & Andy M. Tyrrell

"An evolved anti-jamming adaptive beamforming network"

by Jason D. Lohn, Jonathan M. Becker & Derek S. Linden

"The evolution of standard cell libraries for future technology nodes"

by James Alfred Walker, James A. Hilder, Dave Reid, Asen Asenov, Scott Roy, Campbell Millar & Andy M. Tyrrell

"Hardware spiking neural network prototyping and application"

by Seamus Cawley, Fearghal Morgan, Brian McGinley, Sandeep Pande, Liam McDaid, Snaider Carrillo & Jim Harkin

"The route to a defect tolerant LUT through artificial evolution"

by Asbjoern Djupdal & Pauline C. Haddow

"Formal verification of candidate solutions for post-synthesis evolutionary optimization in evolvable hardware"

by Zdenek Vasicek & Lukas Sekanina

Software Review: "Open BEAGLE: a generic framework for evolutionary computations"

by Dmitry Batenkov

Book Review: "Sean Luke: essentials of metaheuristics"

by Michael Lones

GPEM 12(2) now available online

The second issue of volume 12 of Genetic Programming and Evolvable Machines is now available online, with the following articles:

"Semantically-based crossover in genetic programming: application to real-valued symbolic regression"

by Nguyen Quang Uy, Nguyen Xuan Hoai, Michael O’Neill, R. I. McKay & Edgar Galván-López

"Have your spaghetti and eat it too: evolutionary algorithmics and post-evolutionary analysis"

by Kfir Wolfson, Shay Zakov, Moshe Sipper & Michal Ziv-Ukelson

"Tracer spectrum: a visualisation method for distributed evolutionary computation"

by Michael O’Neill, Anthony Brabazon & Erik Hemberg

Software Review: "Eureqa: software review"

by Renáta Dubcáková

Book Review: "Hitoshi Iba, Topon Kumar Paul, Yoshohiko Hasegawa: Applied genetic programming and machine learning"

by Kalyan Veeramachaneni

CFP: Special Issue on Systems Identification

Guest Editors:

Steven Gustafson
GE Global Research, USA
steven D0T gustafson AT research D0T ge D0T com

Una-May O’Reilly
MIT, USA
unamay AT csail D0T mit D0T edu

Genetic programming is a valuable tool for reverse engineering data. Solutions found by Genetic Programming are in the form of algorithms that can be inspected, model checked, verified, and optimized. While this is possible with other classification methods, the intuitive representations GP employs makes it amenable to systems identification, defined here as: 

Systems Identification: the process of exploring and identifying the variables, coefficients, and

model forms that best or most efficiently represent a system.

A recent example of GP for systems identification can be found in Schmidt and Lipson’s 2009 Science article “Distilling Free-form Natural Laws from Experimental Data” (Schmidt and Lipson 2009). Similarly, scientists at Dow Chemical, University of Antwerp, and Evolved Analytics LLC, have developed flexible and robust GP systems that provide key statistics and visualizations during the evolutionary process to guide the human user (Kotanchek, Vladislavleva, and Smits 2009). In this Special Issue, we would like to bring a focus on this unique but extremely valuable application of GP for Systems Identification. Topics of interest include:

• GP approaches to learn laws of various systems, e.g. biological, mechanical and artificial.

• GP approaches to uncover nonlinear relationships between variables in complex systems

• Scalable GP systems that can handle one or more orders of magnitude more than typical systems to enable more real-world Systems Identification, e.g. financial anomaly detection.

• GP systems that provide an improved understanding of the solutions, from variable interaction to improved confidence bounding, e.g. providing statistics of similar to modern packages like Minitab, Matlab, R.

• Approaches that move GP closer to systems like CART as a way to explore variables, relationships, and data, where users can quickly inspect solutions and modify the system to improve performance and capability.

We encourage all prospective authors to contact the guest editors, at the address below, as early as possible, to indicate your intention to submit a paper to this special issue.

Submission Deadline: September 1, 2011

Acceptance Notification: November 15, 2011

Final Manuscript Deadline: January 15, 2012

References

Kotanchek, M. E., Vladislavleva, E. Y., and Smits, G. F. (2009). Symbolic Regression via GP
as a Discovery Engine: Insights on Outliers and Prototypes. In Riolo, R., O'Reilly, U.-M., and

McConaghy, T. Genetic Programming Theory and Practice VII, pp. 55-72, Springer.
http://www.springerlink.com/content/p508hr96008h61t5/

Schmidt, M., and Lipson, H. (2009). Distilling Free-Form Natural Laws from Experimental
Data. Science 324(5923) pp. 81 - 85.

GPEM 12(1) now available online

The first issue of volume 12 of Genetic Programming and Evolvable Machines is now available online, with the following articles:

"Editorial introduction"

by Lee Spector

"Acknowledgement"

by Lee Spector

"Expert-driven genetic algorithms for simulating evaluation functions"

by Omid David-Tabibi, Moshe Koppel & Nathan S. Netanyahu

"Autonomous experimental design optimization of a flapping wing"

by Markus Olhofer, Dilyana Yankulova & Bernhard Sendhoff

"Redundancies in linear GP, canonical transformation, and its exploitation: a demonstration on image feature synthesis"

by Ukrit Watchareeruetai, Yoshinori Takeuchi, Tetsuya Matsumoto, Hiroaki Kudo & Noboru Ohnishi

Book Review: "Justin Lee: Morphogenetic Evolvable Hardware"

by Martin A. Trefzer

Book Review: "Gisele L. Pappa, Alex Freitas: Automating the design of data mining algorithms, an evolutionary computation approach"

by John Woodward

Book Review: "Arthur K. Kordon: Applying computational intelligence: how to create value"

by Guillermo Leguizamón

"Erratum to: Stochastic optimization of a biologically plausible spino-neuromuscular system model"

by Stanley Gotshall, Kathy Browder, Jessica Sampson, Terence Soule & Richard Wells

"Erratum to: Dario Floreano and Claudio Mattiussi: Bio-inspired artificial intelligence: theories, methods, and technologies"

by Ivan Garibay

GECCO-2011 (Dublin) deadlines extended

The GECCO-2011 regular paper submission deadline has been extended to February 9.