*Apologies for multiple cross postings*

               WORKSHOP ON COMPUTATIONAL INTELLIGENCE ON
                 CONSUMER GAMES AND GRAPHICS HARDWARE
                              CIGPU 2011

                      to be held as part of the

    2011 Genetic and Evolutionary Computation Conference (GECCO-2011)
                     July 12-16, Dublin, Ireland

                       Organized by ACM SIGEVO
20th International Conference on Genetic Algorithms (ICGA) and the 16th
               Annual Genetic Programming Conference (GP)

         One Conference - Many Mini-Conferences 15 Program Tracks

          PAPER SUBMISSION DEADLINE FOR WORKSHOP: April 7th, 2011

-------------------------------------

The fourth international workshop on "Computational Intelligence on
Consumer Games and Graphics Hardware (CIGPU 2011)" will be held as a
workshop in the GECCO-2011 conference in Dublin 12-16 July 2011.

CIGPU 2011 is the fourth workshop on the use of GPUs, games consoles and
other consumer hardware for evolutionary algorithms and other
computational intelligence techniques.

Due to its speed, price, and availability, there is increasing interest
in using mass consumer market commodity hardware for engineering and
scientific applications. Mostly this has concentrated upon graphics
hardware, particularly GPUs, due to their ability to offer teraflop
performance on a desktop using a restricted form of parallel computing.
There is also increasing interest in using the computing power of game
consoles, Cell processors, and portable entertainment and/or cellular
phone mobile devices for research and applications.


Submissions are invited in (but not limited to) the following areas:

* Parallel genetic programming (GP) on GPU
* Parallel genetic algorithms (GA) on GPU
* Parallel evolutionary programming (EP) on GPU
* Associated or hybrid computational intelligence techniques on GPU
-* Particle Swarm Optimisation (PSO)
-* Ant colony optimisation (ACO)
-* Parallel search algorithms
-* Data mining
* Differential Evolution on GPU
* Computational Biology or Bioinformatics on GPU
* Evolutionary computation on video game platforms
* Evolutionary computation on mobile devices

Papers that discuss novel implementations and the practicalities of
writing software for these hardware platforms are especially welcome.

-------------------------------------
Paper Submission
-------------------------------------

Submitted papers should follow the ACM format, and not exceed 8 pages.
Please see the GECCO 2011 information for authors for further details.
However, note that the review process of the workshop is not
double-blind. Hence, authors' information should appear in the paper.
All accepted papers will be presented at the workshop and appear in the
GECCO workshop volume. Proceedings of the workshop will be published on
CD-ROM, and distributed at the conference.

Papers should be submitted by 7 April, 2011 in PDF format to:
cigpu@...
and contain the subject "GECCO Workshop".

-------------------------------------
Important dates
-------------------------------------
Submissions: 7 April 2011
Decision notifications:     14 April 2011
Camera Ready:    26 April 2011
Presenter's registration:    2 May 2011

-------------------------------------
Websites
-------------------------------------
http://www.cs.ucl.ac.uk/staff/W.Langdon/cigpu/
http://www.sigevo.org/gecco-2011/

-------------------------------------
Workshop Chairs
-------------------------------------
Simon Harding - Memorial University, Canada
simonh@...
Bill Langdon - University College London, UK
w.langdon@...
Man Leung Wong - Lingnan University, Hong Kong
mlwong@...
Tony Lewis - Birkbeck, University of London, UK
tony@...
Garnett Wilson - Memorial University, Canada
gwilson@...


GECCO is sponsored by the Association for Computing Machinery Special
Interest Group on Genetic and Evolutionary Computation (SIGEVO). SIG
Services: 2 Penn Plaza, Suite 701, New York, NY, 10121, USA,
1-800-342-6626 (USA and Canada) or +212-626-0500 (Global).

Second call for papers -- deadline extended!
Call for tutorial proposals

2011 IEEE Conference on Computational Intelligence and Games

COEX, Seoul
South Korea, August 31-September 3, 2011

http://sclab.yonsei.ac.kr/~cig

Games have proven to be an ideal domain for the study of computational
intelligence as not only are they fun to play and interesting to
observe, but they provide competitive and dynamic environments that
model many real-world problems. Additionally, methods from
computational intelligence promise to have a big impact on game
technology and development, assisting designers and developers and
enabling new types of computer games.

The 2011 IEEE Conference on Computational Intelligence and Games
brings together leading researchers and practitioners from academia
and industry to discuss recent advances and explore future directions
in this quickly moving field.

Topics of interest include, but are not limited to, the following:

    * Learning in games
    * Coevolution in games
    * Neural-based approaches for games
    * Fuzzy-based approaches for games
    * Player/Opponent modeling in games
    * CI/AI-based game design
    * Multi-agent and multi-strategy learning
    * Applications of game theory
    * CI for Player Affective Modeling
    * Intelligent Interactive Narrative
    * Imperfect information and non-deterministic games
    * Player satisfaction and experience in games
    * Theoretical or empirical analysis of CI techniques for games
    * Comparative studies and game-based benchmarking
    * Computational and artificial intelligence in:
          o Video games
          o Board and card games
          o Economic or mathematical games
          o Serious games
          o Augmented and mixed-reality games
          o Games for mobile platforms

The conference will consist of a single track of oral presentations,
tutorial and workshop/special sessions, and live competitions. The
proceedings will be placed in IEEE Xplore, and made freely available
on the conference website after the conference.

IMPORTANT DATES:
Tutorial and special session proposal deadline: March 15, 2011
Paper submission deadline: March 30, 2011 -- extended!
Decision notification: May 15, 2011
Camera-ready submission: June 15, 2011
Conference dates: August 31-September 3, 2011

General Chair : Sung-Bae Cho
Program Co-Chairs: Simon Lucas and Phllip Hingston
Competitions Chair: Julian Togelius
Publicity Chair: Clare Bates Congdon
Proceedings Chair: Mike Preuss
Tutorials and special sessions chair: Georgios Yannakakis
Local Chairs: Kyung-Joong Kim, Kyu-Baek Hwang, Eun-Youn Kim



--
Julian Togelius
Assistant Professor
IT University of Copenhagen
Rued Langgaards Vej 7, 2300 Copenhagen S, Denmark
mail: julian@..., web: http://julian.togelius.com
mobile: +46-705-192088, office: +45-7218-5277

The papers to be presented next month at EuroGP are now
in the GP bibliography http://www.cs.bham.ac.uk/~wbl/biblio/

The GP-biblio is available via anonymous ftp from
ftp://ftp.cs.bham.ac.uk/pub/authors/W.B.Langdon/biblio
or via my home page. Additionally there is a www search interface at
http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html

If you have any additions, please let me have a _full_ citation
(prefereably in BibTeX).

                     Many thanks for your help

                                 Bill


         Dr. W. B. Langdon,
         Department of Computer Science,
         University College London
         Gower Street, London WC1E 6BT, UK
         http://www.cs.ucl.ac.uk/staff/W.Langdon/

A Field Guide to Genetic Programming
                        http://www.gp-field-guide.org.uk/
EuroGP 2011            http://evostar.dei.uc.pt/call-for-contributions/eurogp/
GECCO 2011             http://www.sigevo.org/gecco-2011/
GP EM                  http://www.springer.com/10710
GP Bibliography        http://www.cs.bham.ac.uk/~wbl/biblio/

14th ANNUAL GRADUATE STUDENT WORKSHOP

� � � � � � � � � � � to be held as part of the

2011 Genetic and Evolutionary Computation Conference
� � � � � � � � � � � � � � �(GECCO-2011)
� � � � � � � � � � 燡uly 12-16, Dublin, Ireland

� � � � � � � � � � Organized by ACM SIGEVO
20th International Conference on Genetic Algorithms (ICGA)
and the 16th Annual Genetic Programming Conference (GP)

One Conference - Many Mini-Conferences 15 Program Tracks

PAPER SUBMISSION DEADLINE FOR WORKSHOP: April 7th, 2011
WORKSHOP URL: http://gecco2011-gsw.blogspot.com/

--------------------------------------------------------------------------------\
------------

This full day workshop will comprise of presentations by selected
students pursing research in some aspect of evolutionary computation.
Students will present their work to an audience that will include a
'mentor' panel of established researchers in evolutionary computation.
Presentations will be followed by a question and discussion period led
by the mentor panel.

The goal of the workshop is to assist students with their research:
methodology, goals, and plans. Students will also receive feedback on
their presentation style. Other attendees will benefit by learning
about current research, engaging in technical discussions and meeting
researchers with related interests. Other students are encouraged to
attend as a means of strengthening their own research.

Students will also be invited to present their work as a poster at the
evening Poster Session - an excellent opportunity to network with
industry and academic members of the community.

The group of presenting students will be chosen with the intent of
creating a diverse group of students working on a broad range of topic
areas. You are an ideal candidate if your thesis topic has already
been approved by your university and you have been working on your
thesis or dissertation for between 6 and 18 months.

* Paper Submission

To present, write a paper describing your current research and submit
it by email to miguel.nicolau@... or gecco2011.gsw@..., using
the subject line "GECCO 2011 Graduate Workshop" (since email is
sometimes unreliable, please contact the same address if you don't
receive an acknowledgement message within a day or two).

Format your paper following the ACM guidelines (details can be found
in the GECCO website) but note that your paper should not be
anonymised and that it should not exceed 4 pages in length. Please
submit your paper in PDF format.

* Important Dates

Submission deadline: Thursday, April 7, 2011
Acceptance notification: Thursday, April 14, 2011
Camera-ready final paper and copyright form due: Tuesday, April 26, 2011

--------------------------------------------------------------------------------\
------------
GECCO is sponsored by the Association for Computing Machinery Special
Interest Group on Genetic and Evolutionary Computation (SIGEVO). SIG
Services: 2 Penn Plaza, Suite 701, New York, NY, 10121, USA,
1-800-342-6626 (USA and Canada) or +212-626-0500 (Global).

DEADLINE EXTENSION!

New submission deadline March 28, 2011 (strict)

=================================================
9th Metaheuristics International Conference

                         MIC 2011

              25-28 July, 2011 in Udine, Italy


More details and up-to-date information at

	        http://mic2011.diegm.uniud.it

      New submission deadline March 28, 2011 (strict)


Scope of the Conference
========================

The Metaheuristics International Conference (MIC) series was established in 1995
and this is its 9th edition. MIC is the main event focusing on the progress of
the area of metaheuristics and their applications. As in previous editions, MIC
2011 will provide an opportunity to the international research community in
metaheuristics to discuss recent research results, to develop new ideas and
collaborations, and to meet old friends and make new ones in a friendly and
relaxed atmosphere.

MIC 2011 welcomes presentations that cover any aspects of metaheuristic research
such as new algorithmic developments, high-impact applications, new research
challenges, theoretical developments, implementation issues, and in-depth
experimental studies. MIC 2011 strives for a high-quality program that will be
completed by a number of invited talks, tutorials, and special sessions.


Relevant Research Areas
========================

MIC 2011 solicits contributions dealing with any aspect of metaheuristics.
Typical, but not exclusive, topics of interest are:

    + Metaheuristic techniques such as tabu search, simulated annealing, iterated
local search, variable neighborhood search, memory-based optimization, dynamic
local search, evolutionary algorithms, memetic algorithms, ant colony
optimization, variable neighborhood search, particle swarm optimization, scatter
search, path relinking, etc.

    + Techniques that enhance the usability and increase the potential of
metaheuristic algorithms such as reactive search mechanisms for self-tuning,
offline metaheuristic algorithm configuration techniques, algorithm portfolios,
parallelization of metaheuristic algorithms, etc.

    + Empirical and theoretical research in metaheuristics including large-scale
experimental analyses, algorithm comparisons, new experimental methodologies,
engineering methodologies for metaheuristic algorithms, search space analysis,
theoretical insights into properties of metaheuristic algorithms, etc.

    + High-impact applications of metaheuristics in fields such as
bioinformatics, electrical and mechanical engineering, telecommunications,
sustainability, business, scheduling and timetabling. Particularly welcome are
innovative applications of metaheuristic algorithms that have a potential of
pushing research frontiers.

    + Contributions on the combination of metaheuristic techniques with those
from other areas, such as integer programming, constraint programming, machine
learning, etc.

    + Challenging applications areas such as continuous, mixed
discrete-continuous, multi-objective, stochastic, or dynamic problems.


Important Dates
================

NEW SUBMISSION DEADLINE         March 28, 2011 (strict)
Notification of acceptance      May 13, 2011
Camera ready copy               May 27, 2011
Early registration              June 6, 2011
Conference                      July 25-28, 2011


Submission Details
===================


We will accept submissions in three different formats.

S1) Original research contributions for publication in the conference
proceedings of a maximum of 10 pages

S2) Extended abstracts of work-in-progress and position papers on an important
research aspect of a maximum of 3 pages

S3) High-quality manuscripts that have recently, within the last six months,
been submitted or accepted for journal publication


Accepted contributions of categories S1 and S2 will be published in the MIC 2011
conference proceedings. The proceedings will be assigned the ISBN
978-88-900984-3-7. Accepted contributions of category S3 will be orally
presented at the conference, but not be included into the conference proceedings
(neither in the post-conference proceedings).

The submission server is available at http://www.conftool.net/mic2011


Post-conference Publication
============================

It has become a tradition of MIC conferences to publish post-conference
proceedings in an edited book. Authors of accepted papers in categories S1 and
S2 (see submission details) are invited to submit improved and extended versions
of their conference papers for publication in the MIC 2011 post-conference
volume. The post-conference volume will appear in the Operations Research /
Computer Science Interfaces series of Springer Verlag (confirmation pending).


Best Paper Award
=================

A best paper award will be presented at the conference. Only papers submitted in
category S1 will be eligible for the best paper award.


Invited Talks
===============

There will be three invited talks at MIC 2011. The invited speakers are

- Holger H. Hoos, http://www.cs.ubc.ca/~hoos, University of British Columbia,
Canada
   Programming by Optimisation: Towards a new Paradigm for Developing
High-Performance Software

- Andrea Lodi, http://www.or.deis.unibo.it/lodi.html, Alma Mater Studiorum -
Universita degli Studi di Bologna, Italy
   The heuristic (dark) side of MIP solvers

- Pascal Van Hentenryck, http://www.cs.brown.edu/~pvh, Brown University, USA
   Meta-Heuristics for Last-Mile Disaster Preparedness and Recovery


Special Sessions
=================

The conference will integrate a number of special sessions. Currently confirmed
are the following.

- Dynamic Optimization, organized by Amir Nakib and Patrick Siarry
- Hybrid Tree Search and Metaheuristic Algorithms, organized by Zeynep Kiziltan,
Andrea Lodi, Michela Milano, Fabio Parisini
- Matheuristics, organized by Karl Doerner, Vittorio Maniezzo, Celso Ribeiro,
and Stefan Voss
- Metaheuristics in Employee Scheduling, organized by Dario Landa-Silva and
Nysret Musliu
- Metaheuristics for Novel and Emerging Vehicle Routing Problems, organized by
Jorge E. Mendoza, Christian Prins, Marc Sevaux
- Metaheuristics for Real Production Planning and Scheduling, organized by Ruben
Ruiz
- Metaheuristics in Health Care Management and Services, organized by Ana Viana
and Abdur Rais
- Methodologies for Heuristic Multi-Objective Optimization, organized by Walter
Gutjahr and Frank Neumann
- Metaheuristics for Quadratic Binary Programs, organized by Fred Glover,
Jin-Kao Hao, and Gary Kochenberger

The submission to the special sessions will be through the same submission site
as for the main conference. For submission details and paper categories, we
refer to the main submission information.


Conference Location
====================

The conference will be held in Udine, Italy. The conference site is Palazzo
Antonini, the main site of the University of Udine. This is a 16th century
palace in the city center of Udine.


Further Information
====================

Up-to-date information will be published on the web site
http://mic2011.diegm.uniud.it. For information about local arrangements,
registration forms, etc., please refer to the above-mentioned web site or
contact the local organizers at the address below.


Conference Address
===================

  MIC 2011 Organization
  Luca Di Gaspero / Andrea Schaerf
  DIEGM, University of Udine
  via delle Scienze 208
  33100 Udine, Italy
  http://mic2011.diegm.uniud.it
  mic2011@...
  Fax: +39 0432 55 8251



MIC 2011 Conference Committee
==============================


Technical Program Chairs
   Andrea Schaerf
   Luca Di Gaspero
   Thomas Stuetzle

Local organization
   Sara Ceschia
   Luca Di Gaspero
   Mirko Loghi
   Andrea Schaerf
   Tommaso Urli

Program Committee
   Roberto Battiti, Universita' degli Studi di Trento, Italy
   Mauro Birattari, Universite' Libre de Bruxelles, Belgium
   Jacek Blazewicz, Politechnika Poznanska, Poland
   Christian Blum, Universitat Politecnica de Catalunya, Spain
   Juergen  Branke, University of Warwick, UK
   Peter Brucker, Universitaet Osnabrueck, Germany
   Edmund Burke, University of Nottingham, UK
   Marco Caserta, Universitaet Hamburg, Germany
   Marco Chiarandini, Syddansk Universitet, Denmark
   Theo Crainic, CIRRELT, Canada
   Mauro Dell'Amico, Universita' degli Studi di Modena e Reggio Emilia, Italy
   Federico  Della Croce, Politecnico di Torino, Italy
   Marco Dorigo, Universite' Libre de Bruxelles, Belgium
   Karl Doerner, Universitaet Wien, Austria
   Paola Festa, Universita' degli Studi di Napoli, Italy
   Andreas Fink, Helmut-Schmidt-Universitaet Hamburg, Germany
   Luca Maria Gambardella, IDSIA, SUPSI, Switzerland
   Xavier Gandibleux, Universite' de Nantes, France
   Michel Gendreau, Universite' de Montreal, Canada
   Fred Glover, University of Colorado at Boulder & OptTek Systems, USA
   Bruce Golden, University of Maryland, USA
   Peter Greistorfer, Karl-Franzens-Universitaet Graz, Austria
   Walter Gutjahr, Universitaet Wien, Austria
   Said Hanafi, Universite' de Valenciennes, France
   Jin-Kao Hao, Universite' d'Angers, France
   Richard Hartl, Universitaet Wien, Austria
   Geir Hasle, SINTEF, Norway
   Holger Hoos, University of British Columbia, Canada
   Graham Kendall, University of Nottingham, UK
   Gary Kochenberger, University of Colorado at Denver, USA
   Manuel Laguna, University of Colorado at Boulder, USA
   Hoong Chuin Lau, Singapore Management University, Singapore
   Andrea Lodi, Universita' degli Studi di Bologna, Italy
   Arne Lokketangen, Molde University College, Norway
   Vittorio Maniezzo, Universita' degli Studi di Bologna, Italy
   Silvano Martello, Universita' degli Studi di Bologna, Italy
   Rafael Marti, Universitat de Valencia, Spain
   Barry McCollum, Queen's University Belfast, UK
   Peter Merz, Fachhochschule Hannover, Germany
   Michela Milano, Universita' degli Studi di Bologna, Italy
   Nenad Mladenovic, Brunel University, UK
   Pablo Moscato, University of Newcastle, Australia
   Nysret Musliu, Technische Universitaet Wien, Austria
   Frank Neumann, Max-Plank-Institut fuer Informatik, Germany
   Ibrahim Osman, American University of Beirut, Lebanon
   Erwin Pesch, Universitaet Siegen, Germany
   Jean-Yves Potvin, Universite' de Montreal, Canada
   Christian Prins, Universite' de Technologie de Troyes, France
   Guenther Raidl, Technische Universitaet Wien, Austria
   Helena Ramalhinho Lourenco, Universitat Pompeu Fabra, Spain
   Cesar Rego, University of Mississippi, USA
   Mauricio Resende, AT&T Labs Research, USA
   Celso Ribeiro, Universidade Federal Fluminense, Brasil
   Franca Rinaldi, Universita' degli Studi di Udine, Italy
   Andrea Roli, Universita' degli Studi di Bologna, Italy
   Ruben Ruiz, Universidad Politecnica de Valencia, Spain
   Marc Schoenauer, INRIA Saclay Ile-de-France, France
   Paolo Serafini, Universita' degli Studi di Udine, Italy
   Marc Sevaux, Universite' de Bretagne-Sud, France
   Patrick Siarry, Universite' Paris-Est Creteil, France
   Kenneth Soerensen, Universiteit Antwerpen, Belgium
   Eric Taillard, Haute Ecole d'Ingenierie et de Gestion du Canton de Vaud,
Switzerland
   El-Ghazali Talbi, LIFL, France
   Jacques Teghem, Universite' de Mons, Belgium
   Paolo Toth, Universita' degli Studi di Bologna, Italy
   Michael Trick, Carnegie Mellon University, USA
   Ana Viana, INESC Porto, Portugal
   Stefan Voss, Universitaet Hamburg, Germany
   Jean-Paul Watson, SANDIA National Laboratories, USA
   David Woodruff, University of California at Davis, USA
   Mutsunori Yagiura, Nagoya University, Japan

Hi All,

I need to give a talk to a banking I.T. audience* in a couple of weeks to
discuss some of the interesting things we've learnt over the last few years.

What would really help would be to demo GP solving a problem in real time. Does
anyone have any recommendations, i.e., a link to something online or a tool? The
more visual the better.

Any help much appreciated,

Stephen

* Although from a software engineering background, the audience have a basic
understanding of heuristics and have done some data mining work.

[Please circulate to all those who might be interested, and accept our
apologies if you received multiple copies of this announcement]

************************************************************
                     CALL FOR PAPERS

                       Workshop on
Scaling Behaviours of Landscapes, Parameters and Algorithms
       www.cs.nott.ac.uk/~ajp/GECCO-2011-HU-workshop/

                  to be held as part of the

     2011 Genetic And Evolutionary Computation Conference
                     (GECCO-2011)

                   July 12-16, 2011
                   Dublin, Ireland
               Organized by ACM SIGEVO
              www.sigevo.org/gecco-2011/

          Workshop Paper Submission Deadline:
                     April 7, 2011
************************************************************

Description:
All too often heuristics and meta-heuristics require significant parameter
tuning to work most effectively. Often this tuning is performed without any
a priori knowledge as to how good values of parameters might depend on
features of the problem. This lack of knowledge can lead to lot of
computational effort and also has the danger of being limited to only
problem instances that are similar to those that have been seen before. The
aim of the workshop is to develop methods to give deeper insight into
problem classes, and how to obtain and exploit structural information. In
particular, we often would like to be able to tune parameters using small
instances (for speed) but then adjust so as to be able to run on large
instances. This will require some theory of how to extrapolate tuning
outside of the size or features of the training set. An analogy is the
difference between non-parametric and parametric statistics; the former does
not assume any underlying probability distribution and the latter can (for
example) assume a Gaussian. Naturally, the latter might give stronger
results and with smaller sized samples. Hence, to distinguish this from
standard parameter tuning, we might call this "Parametric Parameter Tuning".
Of course, this is a challenging problem; but we hope to be able to discuss
any existing work and how the community might meet the challenge.

Related to this is the common and natural belief that the semantic
properties of the landscapes will be reflected in the performances of
algorithms. A subsequent underlying assumption, or hypothesis, if the
landscape has a particular functional dependence on features of the
instance, then such functional dependencies are also likely to play a key
role in understanding the behaviour of heuristic algorithms, and so merit
investigation. We are particularly interested the area of phase transitions;
when particular semantic properties display phases of 'almost always true'
and 'almost never true'. Statistical methods can then reveal some
appropriate parameters to describe the locations of such phases, and we
expect that this will also influence the understanding, design and tuning of
algorithms. This is exemplified by the work in the artificial intelligence
and statistical physics communities on propositional satisfiability and
graph colouring, and that has led to deeper understanding of algorithms, and
development of new ones. One of the goals of the workshop is to look into
phase transition theory with a view to potential applications to traditional
GECCO problems.

The target participants are those that:

* Work on the theory of search algorithms, but are seeking ways for the
theory to have a practical impact

* Work on direct applications, but are frustrated with the trial-and-error
approaches that often are often used, and would like to bring
'theoretically-inspired methods' into their work.

We also aim to bring together researchers and practitioners from related
fields such as Operational Research (OR), Artificial Intelligence and
Computer Science, providing a medium for sharing and inspiring of techniques
(even if application domains are different) and developing common
understandings.

We invite submissions as extended abstracts of around 3-4 pages addressing a
relevant topic. Speculative or position papers also are welcome. Submissions
will be reviewed for quality and relevance. Papers up to the usual limit of
8 pages are also permitted, however we will prefer extended abstracts.
Furthermore, longer papers will not be given a longer time for potential
presentations. See the workshop page for the submission guidelines and more.

Workshop Organisers:
Ender Ozcan, Andrew J. Parkes and Jon Rowe
    www.cs.nott.ac.uk/~exo/
    www.cs.nott.ac.uk/~ajp/
    www.cs.bham.ac.uk/~jer/

Important Dates:
    - Deadline for abstract submission: 7 April
    - Notification of Acceptance:      14 April
    - Camera-ready deadline:           26 April
    - Registration deadline:            2 May

Stephen,

These are very basic and the more visual one is arty, not practical in ways that
banking IT people might like, but FWIW:

http://hampshire.edu/lspector/psh/demo/regression/PshApplet/
http://hampshire.edu/lspector/PushBrush/

  -Lee

On Mar 3, 2011, at 3:59 PM, stephen_dignum wrote:

> Hi All,
>
> I need to give a talk to a banking I.T. audience* in a couple of weeks to
discuss some of the interesting things we've learnt over the last few years.
>
> What would really help would be to demo GP solving a problem in real time.
Does anyone have any recommendations, i.e., a link to something online or a
tool? The more visual the better.
>
> Any help much appreciated,
>
> Stephen
>
> * Although from a software engineering background, the audience have a basic
understanding of heuristics and have done some data mining work.

--
Lee Spector, Professor of Computer Science
Cognitive Science, Hampshire College
893 West Street, Amherst, MA 01002-3359
lspector@..., http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438

I think GP has a toy problem problem.

GP and related literature is FAR too often applied to trivial
problems, by which I mean problems for which we expect the GP system
to be able to find an optimal solution in a reasonable percentage of
number of runs.  Example problems in this vein include:

	 Symbolic Regression
	 Artificial Ant
	 3-, 6-, and 11-bit Multiplexer
	 Parity problems for small values of N
	 Lawnmower (particularly with ADFs)

These problems are very common in the literature for several reasons.
First, there's a long history behind them -- they all date back to
Koza I or Koza II -- so you can compare against a lot of previous
papers and methods.  Second, a number of systems, including my own,
have all of them implemented and so they make a convenient benchmark
test suite.

Third, and perhaps most insidious, is that these problems enable use
of the Computational Effort measure.  I have argued that this measure
has quite a lot of difficulties statistical and otherwise, but for
purposes here the big one is that it promotes the idea that GP is
intended to be used to tackle simple problems for which *expect* to be
able to find the absolute optimal solution so often that we can gauge
the quality of a method based on how often it does so.  But real-world
optimization problems don't regularly fit this mold.

I would like to assemble a benchmark suite of non toy problems, ones
where we do not EVER expect to find the optimum, and indeed may not
even KNOW if there is an optimum.  Instead the goal is simply to
maximize performance (or minimize error).

Such problems should also be helpful to statistical analysis: results
should not generally fall into one of a small number of possible
fitness outcomes (like Multiplexer's buckets of powers of 2), but
instead should have a typical spread of a variety of outcomes.  They
might be multiobjective.  They should have standard functions which
enable reasonable comparison across similar methods (GE, GP, Strongly
Typed GP, Push, CGP, whatnot) and maybe even harder-to-compare
techniques like NEAT etc.  And they have to run fast and easy to
write: it's a *benchmark* suite.  This is VERY important.  No "and
then you use GP to evolve a car for my simulator" or "evolve a
symbolic algebra system".

In short: difficult, small, easy to write, possibly multiobjective,
typically producing a range of outcomes.

In some cases we can simply en-difficult-ize a common problem (like
Artificial Ant with 400 moves and the Los Altos Hills Trail -- not the
Santa Fe Trail), I guess.  But I'd like some new problems drawn from
people's experiences.  Also, I have no doubt someone has beaten me to
the punch here.  Maybe someone's already doing this in some workshop
at EuroGP or somewhere that I'm not aware of, in which case please let
me know!

So that's my call.  Please post here any suggestions of benchmark
problems in this vein.


Sean Luke

Hi All,

Thanks for all the responses for this, much appreciated. I'll send out some
personal thanks as I go through them over the next few days.

Regards

Stephen

Dear all,

We have published a paper in GPEM:

GP challenge: evolving the energy function for protein structure
prediction. Journal of Genetic Programming and Evolvable Machines,
11:61-88, 1 2010.  P. Widera, J. Garibaldi, and N. Krasnogor.

in which we describe a really hard (and practically relevant) problem
and provide datasets to run it. It has all the constraints mentioned in
the email below except , perhaps, "speed".  In the long run, I
personally dont think we can get much out of "fast" benchmarks when we
aim at solving real world problems. The reason for this are numerous and
both of a theoretical and practical nature. Moreover, what is slow today
is fast tomorrow (given the availability of ever more powerful compute
platforms) hence I wouldnt get hang up on speed for benchmarking.   In
any case, we would be very happy to collaborate with anybody who may
want to try their luck against this very difficult benchmark.


Nat

------------------------------------------------------------------------
*From: * Sean Luke <sean@...>
*Sender: * genetic_programming@yahoogroups.com
*Date: *Fri, 04 Mar 2011 16:38:56 -0500
*To: *<genetic_programming@yahoogroups.com>
*Subject: *[GP] Call for Hard Benchmark Problems in Genetic Programming



I think GP has a toy problem problem.

GP and related literature is FAR too often applied to trivial
problems, by which I mean problems for which we expect the GP system
to be able to find an optimal solution in a reasonable percentage of
number of runs. Example problems in this vein include:

Symbolic Regression
Artificial Ant
3-, 6-, and 11-bit Multiplexer
Parity problems for small values of N
Lawnmower (particularly with ADFs)

These problems are very common in the literature for several reasons.
First, there's a long history behind them -- they all date back to
Koza I or Koza II -- so you can compare against a lot of previous
papers and methods. Second, a number of systems, including my own,
have all of them implemented and so they make a convenient benchmark
test suite.

Third, and perhaps most insidious, is that these problems enable use
of the Computational Effort measure. I have argued that this measure
has quite a lot of difficulties statistical and otherwise, but for
purposes here the big one is that it promotes the idea that GP is
intended to be used to tackle simple problems for which *expect* to be
able to find the absolute optimal solution so often that we can gauge
the quality of a method based on how often it does so. But real-world
optimization problems don't regularly fit this mold.

I would like to assemble a benchmark suite of non toy problems, ones
where we do not EVER expect to find the optimum, and indeed may not
even KNOW if there is an optimum. Instead the goal is simply to
maximize performance (or minimize error).

Such problems should also be helpful to statistical analysis: results
should not generally fall into one of a small number of possible
fitness outcomes (like Multiplexer's buckets of powers of 2), but
instead should have a typical spread of a variety of outcomes. They
might be multiobjective. They should have standard functions which
enable reasonable comparison across similar methods (GE, GP, Strongly
Typed GP, Push, CGP, whatnot) and maybe even harder-to-compare
techniques like NEAT etc. And they have to run fast and easy to
write: it's a *benchmark* suite. This is VERY important. No "and
then you use GP to evolve a car for my simulator" or "evolve a
symbolic algebra system".

In short: difficult, small, easy to write, possibly multiobjective,
typically producing a range of outcomes.

In some cases we can simply en-difficult-ize a common problem (like
Artificial Ant with 400 moves and the Los Altos Hills Trail -- not the
Santa Fe Trail), I guess. But I'd like some new problems drawn from
people's experiences. Also, I have no doubt someone has beaten me to
the punch here. Maybe someone's already doing this in some workshop
at EuroGP or somewhere that I'm not aware of, in which case please let
me know!

So that's my call. Please post here any suggestions of benchmark
problems in this vein.

Sean Luke



--


Nat
--

--------------------------------------------------------------------------------\
-----------
NATALIO KRASNOGOR, Ph.D.

Professor of Applied Interdisciplinary Computing
Interdisciplinary Optimisation Laboratory (IOL)
Automated Scheduling, Planning and Optimisation (ASAP) Group
School of Computer Science
Jubilee Campus, University of Nottingham
Nottingham, NG81BB
United Kingdom

Tel.: +44 - (0)115 - 8467592
Fax.: +44 - (0)115 - 8467066

Skype: Natalio.Krasnogor

URL: http://www.cs.nott.ac.uk/~nxk/

e-mail: Natalio.Krasnogor@...

--------------------------------------------------------------------------------\
----------

Please consider sending your best papers to the
Genetic and Evolutionary Computation Conference (GECCO)
July 12-16 Dublin, Ireland, 2011
http://www.sigevo.org/gecco-2011/index.html

A list in no particular order

Evolving Regular Expressions as mRNA Motifs to Predict Human Exon Splitting
   http://www.cs.ucl.ac.uk/staff/W.Langdon/WBL_papers.html#langdon:2009:TR-09-02
   blocks.neg 2292 DNA sequences
   blocks.pos 1184 DNA sequences
   http://bioinformatics.essex.ac.uk/users/wlangdon/tr-09-02.tar.gz

Evolving DNA motifs to Predict GeneChip Probe Performance
   http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/gp-code/RE_gp_training.tar.gz
   hgu133a_re1.txt 15092 25 DNA bases, correlation in Humans
   hgu133a_re2.txt 15103
   hgu133a_re3.txt 15103 training and two test sets
   doi:10.1186/1748-7188-4-6

Human non-coding and protein coding DNA sequence
   Automated DNA Motif Discovery
   http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/gp-code/RE_gp2.tar.gz
   (larger tar contains dataset as well as code)
   A possible split of the training data is held in files
   genes_neg and genes_pos000 to genes_pos050

Nuclear protein location (20 inputs, binary class)
  
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/gp-code/wbl_gecco2004lb_protein.tar.\
gz
   files nnpsl2/Nuclear-test.txt
         nnpsl2/Nuclear-train.txt
   Repeated Sequences in Linear Genetic Programming Genomes
  
http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/WilliamBLangdon.html#langdon:2005:C\
S


Existing toys
1. Santa Fe Ant uses 600 moves,
    Why Ants are Hard GP98
   
http://www.cs.ucl.ac.uk/staff/W.Langdon/WBL_pre2003.html#langdon:1998:antspace
2. 20-mux and 37-mux
    A Many Threaded CUDA Interpreter for Genetic Programming
    http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/langdon_2010_eurogp.html
3. 22 bit parity
    Smooth Uniform Crossover, Sub-Machine Code GP and Demes: A Recipe For Solving
High-Order Boolean Parity Problems
    http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/poli_1999_22par.html
4. Mackey-Glass (1200 time points)
    A SIMD interpreter for Genetic Programming on GPU Graphics Cards
    http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/langdon_2008_eurogp.html
5. Sun Spots
    A SIMD interpreter for Genetic Programming on GPU Graphics Cards
    http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/langdon_2008_eurogp.html

                                 Bill


         Dr. W. B. Langdon,
         Department of Computer Science,
         University College London
         Gower Street, London WC1E 6BT, UK
         http://www.cs.ucl.ac.uk/staff/W.Langdon/

A Field Guide to Genetic Programming
                        http://www.gp-field-guide.org.uk/
GECCO 2011             http://www.sigevo.org/gecco-2011/
GP EM                  http://www.springer.com/10710
GP Bibliography        http://www.cs.bham.ac.uk/~wbl/biblio/

On Mar 5, 2011, at 9:05 AM, Bill LANGDON wrote:

> A list in no particular order

Bill, I'll go through them.


On Mar 5, 2011, at 5:28 AM, Natalio Krasnogor wrote:

> in which we describe a really hard (and practically relevant) problem
> and provide datasets to run it. It has all the constraints mentioned
> in
> the email below except , perhaps, "speed".  In the long run, I
> personally dont think we can get much out of "fast" benchmarks when we
> aim at solving real world problems.

I hear you: and I really do appreciate that argument of testing on
"real-world" problems.  But I think speed is more important than you
may have considered, because there is an additional constraint:
benchmark comparisons require 50 to 100 independent runs per
treatment.  If an evaluation takes 30 seconds to perform, then a
*single* typical GP run will take a month.  To do just 30 runs would
take over two years.  I've done a major experiment like that: it of
course requires massive multiprocessing to get out in a reasonable
time, which I luckily had on hand, being at a large university.  But
there are many who do not.

Here's my back-of-the-napkin minimum bound, which I hope is
reasonable. Let's say that we wish to allow a scientist to compare two
methods, each with 100 independent runs for statistical significance,
and each run requiring 100,000 evaluations.   That's 20 million
evaluations.  In order to have the thing done in 24 hours on a single
processor, no multithreading, a single evaluation must take up no more
than 0.004 seconds, not counting breeding and evolutionary overhead.
Longer than this is not at present reasonable given that (in my
experience) experiments are repeated multiple times until you've
worked out the bugs.

So here's my revised list:

	 - Nontrivial: highly unlikely to yield optimal results.
	 - Fast. [I think under 0.005 seconds per evaluation on a typical
processor.]
	 - Highly portable and easily written (correctly) in various languages.
	 - Broad spread of possible fitness outcomes that don't tend to fall
in buckets.
	 - Optionally multiobjective would be cool.
	 - Ideally not requiring a particular GP methodology.

Sean

WORKSHOP ON MEDICAL APPLICATIONS OF GENETIC AND EVOLUTIONARY COMPUTATION
                                     MEDGEC

                            to be held as part of the

       2011 Genetic and Evolutionary Computation Conference (GECCO-2011)
                      July 12-16, 2011, Dublin, Ireland

                            Organized by ACM SIGEVO
20th International Conference on Genetic Algorithms (ICGA) and the 16th

                 Annual Genetic Programming Conference (GP)

           One Conference - Many Mini-Conferences 15 Program Tracks

           PAPER SUBMISSION DEADLINE FOR WORKSHOPS: April 7th, 2011




We are pleased to invite you to submit a paper to MedGEC 2010 the GECCO
Workshop on Medical Applications of Genetic and Evolutionary Computation.

Full details can be found at the MedGEC Web site:
http://www.elec.york.ac.uk/events/MedGEC2011/

Subjects will include (but are not limited to) applications of GEC to:

Medical imaging
Medical signal processing
Medical text analysis
Clinical diagnosis and therapy
Data mining medical data and records
Clinical expert systems
Modelling and simulation of medical processes
Drug description analysis
Genomic-based clinical studies
Patient-centric care

A dedicated workshop at GECCO provides a much needed focus for medical
related applications of EC, not only providing a clear definition of the
state of the art, but also support to practitioners for whom GEC might not
be their main area of expertise or experience.

The Workshop has two main aims:

(i) to provide delegates with examples of the current state of the art of
applications of GEC to medicine.

(ii) to provide a forum in which researchers can discuss and exchange
ideas, support and advise each other in theory and practice.

GECCO is widely regarded to be the most authoritative conference in GEC and
as such, offers the ideal venue for this important and growing community.

Accepted Workshop papers will be published in the GECCO 2011 Companion
Material, included with the proceedings on a CD, and also in the ACM
Digital Library.

New for GECCO MedGEC 2011

A session of the workshop will be dedicated to the presentation of large
transnational projects in which GEC plays a significant role and of other
opportunities for young scientists to be involved in this field. In
particular, a short presentation of the EU-funded project MIBISOC ("Medical
Imaging using Bio-Inspired and Soft Computing", funded within the
Marie-Curie Initial Training Network Action FP7 PEOPLE-ITN-2008), which
funds 16 PhDs in laboratories form 5 European countries will be given, while
similar contributions will be solicited in the CFP.

Important dates:

Paper submission deadline: 7 April 2011

Notification of acceptance: 14 April, 2011

Camera-ready copy deadline: 26 April, 2011

Workshop: 12 or 13 July, 2011


For full details, please see the Workshop home page at:
http://www.elec.york.ac.uk/events/MedGEC2011/

Stephen Smith
Stefano Cagnoni
Robert Patton
Workshop Organizers

GECCO is sponsored by the Association for Computing Machinery Special
Interest Group on Genetic and Evolutionary Computation (SIGEVO). SIG
Services: 2 Penn Plaza, Suite 701, New York, NY, 10121, USA,
1-800-342-6626 (USA and Canada) or +212-626-0500 (Global).

Hi Sean,

Here's my suggestion for a difficult problem - the work by Julian Miller
et al. on predicting prime numbers [1].

Thanks,

David

[1] J.A. Walker and J.F. Miller, Predicting Prime Numbers using
Cartesian Genetic Programming, 10th European Conference on Genetic
Programming (EuroGP 2007), 205-216, Valencia, Spain, 2007

--
      Call for Hard Benchmark Problems in Genetic Programming
      Posted by: "Sean Luke" sean@...   jukkauh
      Fri Mar 4, 2011 1:38 pm (PST)


      I think GP has a toy problem problem.

      GP and related literature is FAR too often applied to trivial
      problems, by which I mean problems for which we expect the GP system
      to be able to find an optimal solution in a reasonable percentage of
      number of runs. Example problems in this vein include:

      Symbolic Regression
      Artificial Ant
      3-, 6-, and 11-bit Multiplexer
      Parity problems for small values of N
      Lawnmower (particularly with ADFs)

      These problems are very common in the literature for several reasons.
      First, there's a long history behind them -- they all date back to
      Koza I or Koza II -- so you can compare against a lot of previous
      papers and methods. Second, a number of systems, including my own,
      have all of them implemented and so they make a convenient benchmark
      test suite.

      Third, and perhaps most insidious, is that these problems enable use
      of the Computational Effort measure. I have argued that this measure
      has quite a lot of difficulties statistical and otherwise, but for
      purposes here the big one is that it promotes the idea that GP is
      intended to be used to tackle simple problems for which *expect* to be
      able to find the absolute optimal solution so often that we can gauge
      the quality of a method based on how often it does so. But real-world
      optimization problems don't regularly fit this mold.

      I would like to assemble a benchmark suite of non toy problems, ones
      where we do not EVER expect to find the optimum, and indeed may not
      even KNOW if there is an optimum. Instead the goal is simply to
      maximize performance (or minimize error).

      Such problems should also be helpful to statistical analysis: results
      should not generally fall into one of a small number of possible
      fitness outcomes (like Multiplexer's buckets of powers of 2), but
      instead should have a typical spread of a variety of outcomes. They
      might be multiobjective. They should have standard functions which
      enable reasonable comparison across similar methods (GE, GP, Strongly
      Typed GP, Push, CGP, whatnot) and maybe even harder-to-compare
      techniques like NEAT etc. And they have to run fast and easy to
      write: it's a *benchmark* suite. This is VERY important. No "and
      then you use GP to evolve a car for my simulator" or "evolve a
      symbolic algebra system".

      In short: difficult, small, easy to write, possibly multiobjective,
      typically producing a range of outcomes.

      In some cases we can simply en-difficult-ize a common problem (like
      Artificial Ant with 400 moves and the Los Altos Hills Trail -- not the
      Santa Fe Trail), I guess. But I'd like some new problems drawn from
      people's experiences. Also, I have no doubt someone has beaten me to
      the punch here. Maybe someone's already doing this in some workshop
      at EuroGP or somewhere that I'm not aware of, in which case please let
      me know!

      So that's my call. Please post here any suggestions of benchmark
      problems in this vein.

      Sean Luke

      Back to top
      Reply to sender | Reply to group | Reply via web post
      Messages in this topic (1)

--
Dr David R. White
Research Associate
Dept. of Computer Science
University of York,
Deramore Lane, YO10 5GH.
http://www.cs.york.ac.uk/~drw

 >>>bill<<<

On Mar 5, 2011, at 9:05 AM, Bill LANGDON wrote:

A list in no particular order

Bill, I'll go through them.
On Mar 5, 2011, at 5:28 AM, Natalio Krasnogor wrote:

in which we describe a really hard (and practically relevant) problem
and provide datasets to run it. It has all the constraints mentioned in
the email below except , perhaps, "speed". In the long run, I
personally dont think we can get much out of "fast" benchmarks when we
aim at solving real world problems.

I hear you: and I really do appreciate that argument of testing on "real-world" problems. But I think speed is more important than you may have considered, because there is an additional constraint: benchmark comparisons require 50 to 100 independent runs per treatment. If an evaluation takes 30 seconds to perform, then a *single* typical GP run will take a month. To do just 30 runs would take over two years. I've done a major experiment like that: it of course requires massive multiprocessing to get out in a reasonable time, which I luckily had on hand, being at a large university. But there are many who do not.
Here's my back-of-the-napkin minimum bound, which I hope is reasonable. Let's say that we wish to allow a scientist to compare two methods, each with 100 independent runs for statistical significance, and each run requiring 100,000 evaluations. That's 20 million evaluations. In order to have the thing done in 24 hours on a single processor, no multithreading, a single evaluation must take up no more than 0.004 seconds, not counting breeding and evolutionary overhead. Longer than this is not at present reasonable given that (in my experience) experiments are repeated multiple times until you've worked out the bugs.
So here's my revised list:
- Nontrivial: highly unlikely to yield optimal results.
- Fast. [I think under 0.005 seconds per evaluation on a typical processor.]
- Highly portable and easily written (correctly) in various languages.
- Broad spread of possible fitness outcomes that don't tend to fall in buckets.
- Optionally multiobjective would be cool.
- Ideally not requiring a particular GP methodology.
Sean
------------------------------------
Yahoo! Groups Links
<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/genetic_programming/
<*> Your email settings:
Individual Email | Traditional
<*> To change settings online go to:
http://groups.yahoo.com/group/genetic_programming/join
(Yahoo! ID required)
<*> To change settings via email:
genetic_programming-digest@yahoogroups.com genetic_programming-fullfeatured@yahoogroups.com
<*> To unsubscribe from this group, send an email to:
genetic_programming-unsubscribe@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/

Oh another toy is the Max problem.
An Analysis of the MAX Problem in Genetic Programming, GP-97
http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/langdon_1997_MAX.html

                                 Bill

         Dr. W. B. Langdon,
         Department of Computer Science,
         University College London
         Gower Street, London WC1E 6BT, UK
         http://www.cs.ucl.ac.uk/staff/W.Langdon/

CIGPU 2011             http://www.cs.ucl.ac.uk/staff/W.Langdon/cigpu/
A Field Guide to Genetic Programming
                        http://www.gp-field-guide.org.uk/
GECCO 2011             http://www.sigevo.org/gecco-2011/
GP EM                  http://www.springer.com/10710
GP Bibliography        http://www.cs.bham.ac.uk/~wbl/biblio/

On Mon, Mar 7, 2011 at 7:42 PM, bill punch <punch@...> wrote:
>
>
>
> I've often wondered why "structured tree" problems were not more popular for
the kind of benchmarking Sean has described. By "structured tree" problems, I
mean problems where only the structure of the tree is relevant to the solution
to the problem. That is, neither the tree nor any of its nodes perform an
operation. The first one I know of was the Royal Tree problem we worked on many
years ago, but there have been other variants introduced since then.
>
> Such problems have a number of advantages:
> - Evaluation is quick for two reasons. First, the tree be evaluated only once
(not multiple times on varying inputs). Second, the evaluation itself depends
only on the structure of the tree. Nodes are only functions in the sense that
they have arity; they perform no operations.
>
> - Such benchmarks are very tunable. The structure of the tree (depth, shape,
number of nodes, their relationships) can all be varied to make the problem easy
or hard.
>
> - Unlike most other problems, the solution cardinality is also tunable.
Solution sets can include only a single solution (which is not very typical in
GP), or a set of solutions to be determined by the tester. Tuning this set can
dramatically change the nature of the problem.
>
> - Deception can be introduced easily to test how well the considered algorithm
performs under noisy conditions.
>
> - The resulting trees are actually fairly readable, since one need only looks
at the tree structure and the labels.
>
> I suppose the question is whether being able to find good tree structures is
applicable to solving difficult, real-world problems. Perhaps that is an
interesting research question.
>
>       >>>bill<<<
>
> On 3/5/11 11:43 AM, Sean Luke wrote:
>
> On Mar 5, 2011, at 9:05 AM, Bill LANGDON wrote:
>
> A list in no particular order
>
> Bill, I'll go through them.
>
>
> On Mar 5, 2011, at 5:28 AM, Natalio Krasnogor wrote:
>
> in which we describe a really hard (and practically relevant) problem
> and provide datasets to run it. It has all the constraints mentioned
> in
> the email below except , perhaps, "speed".  In the long run, I
> personally dont think we can get much out of "fast" benchmarks when we
> aim at solving real world problems.
>
> I hear you: and I really do appreciate that argument of testing on
> "real-world" problems.  But I think speed is more important than you
> may have considered, because there is an additional constraint:
> benchmark comparisons require 50 to 100 independent runs per
> treatment.  If an evaluation takes 30 seconds to perform, then a
> *single* typical GP run will take a month.  To do just 30 runs would
> take over two years.  I've done a major experiment like that: it of
> course requires massive multiprocessing to get out in a reasonable
> time, which I luckily had on hand, being at a large university.  But
> there are many who do not.
>
> Here's my back-of-the-napkin minimum bound, which I hope is
> reasonable. Let's say that we wish to allow a scientist to compare two
> methods, each with 100 independent runs for statistical significance,
> and each run requiring 100,000 evaluations.   That's 20 million
> evaluations.  In order to have the thing done in 24 hours on a single
> processor, no multithreading, a single evaluation must take up no more
> than 0.004 seconds, not counting breeding and evolutionary overhead.
> Longer than this is not at present reasonable given that (in my
> experience) experiments are repeated multiple times until you've
> worked out the bugs.
>
> So here's my revised list:
>
>  - Nontrivial: highly unlikely to yield optimal results.
>  - Fast. [I think under 0.005 seconds per evaluation on a typical
> processor.]
>  - Highly portable and easily written (correctly) in various languages.
>  - Broad spread of possible fitness outcomes that don't tend to fall
> in buckets.
>  - Optionally multiobjective would be cool.
>  - Ideally not requiring a particular GP methodology.
>
> Sean
>
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>

We created a structural and content tree problem awhile back called the
TreeString problem:

http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/eurogp_GustafsonBK05.html

We found this very tunable and informative for difficulty and diversity
analysis.  I also liked Daida's Lid problem for structure analysis.


-----Original Message-----
From: genetic_programming@yahoogroups.com on behalf of w langdon
Sent: Mon 3/7/2011 14:52
To: genetic_programming@yahoogroups.com
Subject: Re: [GP] Call for Hard Benchmark Problems in Genetic Programming

Oh another toy is the Max problem.
An Analysis of the MAX Problem in Genetic Programming, GP-97
http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/langdon_1997_MAX.html

                                 Bill

         Dr. W. B. Langdon,
         Department of Computer Science,
         University College London
         Gower Street, London WC1E 6BT, UK
         http://www.cs.ucl.ac.uk/staff/W.Langdon/

CIGPU 2011             http://www.cs.ucl.ac.uk/staff/W.Langdon/cigpu/
A Field Guide to Genetic Programming
                        http://www.gp-field-guide.org.uk/
GECCO 2011             http://www.sigevo.org/gecco-2011/
GP EM                  http://www.springer.com/10710
GP Bibliography        http://www.cs.bham.ac.uk/~wbl/biblio/

On Mon, Mar 7, 2011 at 7:42 PM, bill punch <punch@...> wrote:
>
>
>
> I've often wondered why "structured tree" problems were not more popular for
the kind of benchmarking Sean has described. By "structured tree" problems, I
mean problems where only the structure of the tree is relevant to the solution
to the problem. That is, neither the tree nor any of its nodes perform an
operation. The first one I know of was the Royal Tree problem we worked on many
years ago, but there have been other variants introduced since then.
>
> Such problems have a number of advantages:
> - Evaluation is quick for two reasons. First, the tree be evaluated only once
(not multiple times on varying inputs). Second, the evaluation itself depends
only on the structure of the tree. Nodes are only functions in the sense that
they have arity; they perform no operations.
>
> - Such benchmarks are very tunable. The structure of the tree (depth, shape,
number of nodes, their relationships) can all be varied to make the problem easy
or hard.
>
> - Unlike most other problems, the solution cardinality is also tunable.
Solution sets can include only a single solution (which is not very typical in
GP), or a set of solutions to be determined by the tester. Tuning this set can
dramatically change the nature of the problem.
>
> - Deception can be introduced easily to test how well the considered algorithm
performs under noisy conditions.
>
> - The resulting trees are actually fairly readable, since one need only looks
at the tree structure and the labels.
>
> I suppose the question is whether being able to find good tree structures is
applicable to solving difficult, real-world problems. Perhaps that is an
interesting research question.
>
>       >>>bill<<<
>
> On 3/5/11 11:43 AM, Sean Luke wrote:
>
> On Mar 5, 2011, at 9:05 AM, Bill LANGDON wrote:
>
> A list in no particular order
>
> Bill, I'll go through them.
>
>
> On Mar 5, 2011, at 5:28 AM, Natalio Krasnogor wrote:
>
> in which we describe a really hard (and practically relevant) problem
> and provide datasets to run it. It has all the constraints mentioned
> in
> the email below except , perhaps, "speed".  In the long run, I
> personally dont think we can get much out of "fast" benchmarks when we
> aim at solving real world problems.
>
> I hear you: and I really do appreciate that argument of testing on
> "real-world" problems.  But I think speed is more important than you
> may have considered, because there is an additional constraint:
> benchmark comparisons require 50 to 100 independent runs per
> treatment.  If an evaluation takes 30 seconds to perform, then a
> *single* typical GP run will take a month.  To do just 30 runs would
> take over two years.  I've done a major experiment like that: it of
> course requires massive multiprocessing to get out in a reasonable
> time, which I luckily had on hand, being at a large university.  But
> there are many who do not.
>
> Here's my back-of-the-napkin minimum bound, which I hope is
> reasonable. Let's say that we wish to allow a scientist to compare two
> methods, each with 100 independent runs for statistical significance,
> and each run requiring 100,000 evaluations.   That's 20 million
> evaluations.  In order to have the thing done in 24 hours on a single
> processor, no multithreading, a single evaluation must take up no more
> than 0.004 seconds, not counting breeding and evolutionary overhead.
> Longer than this is not at present reasonable given that (in my
> experience) experiments are repeated multiple times until you've
> worked out the bugs.
>
> So here's my revised list:
>
>  - Nontrivial: highly unlikely to yield optimal results.
>  - Fast. [I think under 0.005 seconds per evaluation on a typical
> processor.]
>  - Highly portable and easily written (correctly) in various languages.
>  - Broad spread of possible fitness outcomes that don't tend to fall
> in buckets.
>  - Optionally multiobjective would be cool.
>  - Ideally not requiring a particular GP methodology.
>
> Sean
>
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>


------------------------------------

Yahoo! Groups Links

Hi Bill,

I agree that structured tree problems have their uses, particularly for
understanding what's going on in some of our systems, but as you suggested in
your last line the connection between doing well on such problems and doing well
on real-world problems is probably indirect at best.

Furthermore, these violate Sean's criterion of "Ideally not requiring a
particular GP methodology". If your GP system doesn't evolve trees (e.g. because
it evolves linear strings of machine code instructions, etc.) then these
problems make no sense. Or if it evolves things that could be considered trees
but that have radically different tree-shape-to-function mappings than standard
GP trees (as in Push) then it's not clear what good or bad performance on the
structured tree problems would mean.

  -Lee


On Mar 7, 2011, at 2:42 PM, bill punch wrote:

> I've often wondered why "structured tree" problems were not more popular for
the kind of benchmarking Sean has described. By "structured tree" problems, I
mean problems where only the structure of the tree is relevant to the solution
to the problem. That is, neither the tree nor any of its nodes perform an
operation. The first one I know of was the Royal Tree problem we worked on many
years ago, but there have been other variants introduced since then.
>
> Such problems have a number of advantages:
> - Evaluation is quick for two reasons. First, the tree be evaluated only once
(not multiple times on varying inputs). Second, the evaluation itself depends
only on the structure of the tree. Nodes are only functions in the sense that
they have arity; they perform no operations.
>
> - Such benchmarks are very tunable. The structure of the tree (depth, shape,
number of nodes, their relationships) can all be varied to make the problem easy
or hard.
>
> - Unlike most other problems, the solution cardinality is also tunable.
Solution sets can include only a single solution (which is not very typical in
GP), or a set of solutions to be determined by the tester. Tuning this set can
dramatically change the nature of the problem.
>
> - Deception can be introduced easily to test how well the considered algorithm
performs under noisy conditions.
>
> - The resulting trees are actually fairly readable, since one need only looks
at the tree structure and the labels.
>
> I suppose the question is whether being able to find good tree structures is
applicable to solving difficult, real-world problems. Perhaps that is an
interesting research question.
>       >>>bill<<<
>
> On 3/5/11 11:43 AM, Sean Luke wrote:
>> On Mar 5, 2011, at 9:05 AM, Bill LANGDON wrote:
>>
>>
>>> A list in no particular order
>>>
>> Bill, I'll go through them.
>>
>>
>> On Mar 5, 2011, at 5:28 AM, Natalio Krasnogor wrote:
>>
>>
>>> in which we describe a really hard (and practically relevant) problem
>>> and provide datasets to run it. It has all the constraints mentioned
>>> in
>>> the email below except , perhaps, "speed".  In the long run, I
>>> personally dont think we can get much out of "fast" benchmarks when we
>>> aim at solving real world problems.
>>>
>> I hear you: and I really do appreciate that argument of testing on
>> "real-world" problems.  But I think speed is more important than you
>> may have considered, because there is an additional constraint:
>> benchmark comparisons require 50 to 100 independent runs per
>> treatment.  If an evaluation takes 30 seconds to perform, then a
>> *single* typical GP run will take a month.  To do just 30 runs would
>> take over two years.  I've done a major experiment like that: it of
>> course requires massive multiprocessing to get out in a reasonable
>> time, which I luckily had on hand, being at a large university.  But
>> there are many who do not.
>>
>> Here's my back-of-the-napkin minimum bound, which I hope is
>> reasonable. Let's say that we wish to allow a scientist to compare two
>> methods, each with 100 independent runs for statistical significance,
>> and each run requiring 100,000 evaluations.   That's 20 million
>> evaluations.  In order to have the thing done in 24 hours on a single
>> processor, no multithreading, a single evaluation must take up no more
>> than 0.004 seconds, not counting breeding and evolutionary overhead.
>> Longer than this is not at present reasonable given that (in my
>> experience) experiments are repeated multiple times until you've
>> worked out the bugs.
>>
>> So here's my revised list:
>>
>>  - Nontrivial: highly unlikely to yield optimal results.
>>  - Fast. [I think under 0.005 seconds per evaluation on a typical
>> processor.]
>>  - Highly portable and easily written (correctly) in various languages.
>>  - Broad spread of possible fitness outcomes that don't tend to fall
>> in buckets.
>>  - Optionally multiobjective would be cool.
>>  - Ideally not requiring a particular GP methodology.
>>
>> Sean
>>

--
Lee Spector, Professor of Computer Science
Cognitive Science, Hampshire College
893 West Street, Amherst, MA 01002-3359
lspector@..., http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438

Hi Sean,

What a great question. The authors of the recent Open Issues article would
certainly agree with you on the toy problem problem ;-)
See section 2.7 in http://www.springerlink.com/content/a058142636361453/

When thinking about the types of problems we should be applying GP to it is
worth considering at least two things:

1) Problem difficulty metrics might be exploited to determine whether or not a
benchmark problem is appropriate (see Section 2.2 in Open Issues)

2) and one of my favourite topics of the moment.....Dynamic problems (see
section 2.3 in Open Issues).
As researchers in GP we should not forget the origins of our field (in
particular I'm thinking of biological evolution and "Natural Selection").
The "natural" environment in which biological evolution originated and succeeds
is one where the environment is changing.
The consequence of existing in a dynamic environment driven by natural selection
is that we are not optimising per se.
All that matters is your fitness relative to others, that is, your ability to
reproduce and therefore the survival of your genome.
There are many real world problem environments which are dynamic by nature,
where required solutions need to be simply "good enough"
relative to competitors, and potentially these problems are a *natural target
for GP*.

Some dynamic problem instances in the literature include (apologies as most of
these are from our group as these are the ones I have to hand right now):

Langdon and Poli's Artificial Ant with changing trails:  
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/WBL.euro98_bloatd.pdf

Dynamic Symbolic Regression:
http://ncra.ucd.ie/papers/CEC2008subtreedeactivation.pdf
http://ncra.ucd.ie/papers/eurogp2004.pdf
http://www.springer.com/engineering/mathematical/book/978-3-642-00313-4
L. Vanneschi & G. Cuccu http://www.idsia.ch/~giuse/papers/van09gecco.pdf


Physics-based animation (Quadruped Gaits):
http://ncra.ucd.ie/papers/eurogpMurphy2009.pdf


As Simon mentioned, Games provide great benchmarks, which are often dynamic
problems too....

Mario:
Perez D., Nicolau M., O'Neill M., Brabazon A.  (2011). Evolving Behaviour Trees
for the Mario Bros Game Using Grammatical Evolution. In EvoGAMES 2011 the 3rd
European Event on Bio-inspired Algorithms in Games, Torino, Italy. Springer.

Ms PacMan:
http://ncra.ucd.ie/papers/evolvingMsPacmanControllerEvoGames2010.pdf

Toribash:
http://ncra.ucd.ie/papers/ToribashGA.pdf


Trading (there are so many GP papers in this area it's best to refer to the GP
Bibliography.  Algo trading/high-frequency trading is one great example):
http://ncra.ucd.ie/papers/evofinBradley2009.pdf
http://dx.doi.org/10.1109/MCI.2008.929841
http://ncra.ucd.ie/papers/cec2006_adaptiveTrading.ps


Dynamic Scheduling:
D. Jakobovic 虂, L. Budin, Dynamic scheduling with genetic programming. In
Proceedings of the 9th European Conference on Genetic Programming (Budapest,
Hungary, 10鈥�12 Apr. 2006), vol. 3905 of Lecture Notes in Computer Science, ed.
by P. Collet, M. Tomassini, M. Ebner, S. Gustafson, A. Eka 虂rt (Springer,
2006), pp. 73鈥�84

Intrusion Detection:
J. Hansen, P. Lowry, R. Meservy, D. McDonald, Genetic programming for prevention
of cyber-terrorism through dynamic and evolving intrusion detection. Decis.
Support Syst. 43(4), 1362鈥�1374

Time series forecasting:
N. Wagner, Z. Michalewicz, M. Khouja, R. McGregor, Time series forecasting for
dynamic environments: The dyfor genetic program model. IEEE Trans. Evol. Comput.
11(4), 433鈥�452 (2006)


Thanks,
Mike.

---
Dr Michael O'Neill
Director - Natural Computing Research & Applications Group
Complex & Adaptive Systems Laboratory
School of Computer Science & Informatics
University College Dublin
Belfield, Dublin 4
Ireland

GECCO 2011 (Dublin, Ireland)
http://www.sigevo.org/gecco-2011/



On 4 Mar 2011, at 21:38, Sean Luke wrote:

> I think GP has a toy problem problem.
>
> GP and related literature is FAR too often applied to trivial
> problems, by which I mean problems for which we expect the GP system
> to be able to find an optimal solution in a reasonable percentage of
> number of runs. Example problems in this vein include:
>
> Symbolic Regression
> Artificial Ant
> 3-, 6-, and 11-bit Multiplexer
> Parity problems for small values of N
> Lawnmower (particularly with ADFs)
>
> These problems are very common in the literature for several reasons.
> First, there's a long history behind them -- they all date back to
> Koza I or Koza II -- so you can compare against a lot of previous
> papers and methods. Second, a number of systems, including my own,
> have all of them implemented and so they make a convenient benchmark
> test suite.
>
> Third, and perhaps most insidious, is that these problems enable use
> of the Computational Effort measure. I have argued that this measure
> has quite a lot of difficulties statistical and otherwise, but for
> purposes here the big one is that it promotes the idea that GP is
> intended to be used to tackle simple problems for which *expect* to be
> able to find the absolute optimal solution so often that we can gauge
> the quality of a method based on how often it does so. But real-world
> optimization problems don't regularly fit this mold.
>
> I would like to assemble a benchmark suite of non toy problems, ones
> where we do not EVER expect to find the optimum, and indeed may not
> even KNOW if there is an optimum. Instead the goal is simply to
> maximize performance (or minimize error).
>
> Such problems should also be helpful to statistical analysis: results
> should not generally fall into one of a small number of possible
> fitness outcomes (like Multiplexer's buckets of powers of 2), but
> instead should have a typical spread of a variety of outcomes. They
> might be multiobjective. They should have standard functions which
> enable reasonable comparison across similar methods (GE, GP, Strongly
> Typed GP, Push, CGP, whatnot) and maybe even harder-to-compare
> techniques like NEAT etc. And they have to run fast and easy to
> write: it's a *benchmark* suite. This is VERY important. No "and
> then you use GP to evolve a car for my simulator" or "evolve a
> symbolic algebra system".
>
> In short: difficult, small, easy to write, possibly multiobjective,
> typically producing a range of outcomes.
>
> In some cases we can simply en-difficult-ize a common problem (like
> Artificial Ant with 400 moves and the Los Altos Hills Trail -- not the
> Santa Fe Trail), I guess. But I'd like some new problems drawn from
> people's experiences. Also, I have no doubt someone has beaten me to
> the punch here. Maybe someone's already doing this in some workshop
> at EuroGP or somewhere that I'm not aware of, in which case please let
> me know!
>
> So that's my call. Please post here any suggestions of benchmark
> problems in this vein.
>
> Sean Luke
>
>

....
>
> But I think speed is more important than you
> may have considered, because there is an additional constraint:
> benchmark comparisons require 50 to 100 independent runs per
> treatment.
>

No, i did not ignore the above at all (I've been playing this game for a
while now). Still, the constraints of 100 independent runs (how many
runs you *really* need depends on -amogst others- the variance you get
and the design of experiments you plan) or 0.004 seconds are pretty
arbitrary numbers.
At the end of the day the point is not to necessarily to compare GP
versus GP' but to compare GP versus any other method, so if the same
results on an expensive
problem can be done with other methods I will take it any day.

There are really expensive problems that may help push the GP state to
the art considerably and I think these cannot be ignored. Often, what
you get
are situations not unlike design optimisation in which you are trying to
get an optimal design for a very "unique" artifact that you will design
once (and perhaps use
multiple times or for long time), in that case, it does not really
matter if the evaluation takes 2 years-cpu time (not a great deal
nowadays anyways)
because it gets recouped over time with the use of the designoid
artifact. This situation is very different, of course, to one where for
each, eg. new dataset, you need to GP-design a slightly different
classifier of some (some examples have already been circulated in
response to your original email covering this) in which of course you
need speed.

In any case we can talk more during gecco and it is gret that you have
brought these matters of benchmarking to light, at the end of the day
what would be fantastic is a well annotated taxonomy of benchmarks for
various classes of scenarios people could draw from.

Thanks.

nat



>
>

--


Nat
--

--------------------------------------------------------------------------------\
-----------
NATALIO KRASNOGOR, Ph.D.

Professor of Applied Interdisciplinary Computing
Interdisciplinary Optimisation Laboratory (IOL)
Automated Scheduling, Planning and Optimisation (ASAP) Group
School of Computer Science
Jubilee Campus, University of Nottingham
Nottingham, NG81BB
United Kingdom

Tel.: +44 - (0)115 - 8467592
Fax.: +44 - (0)115 - 8467066

Skype: Natalio.Krasnogor

URL: http://www.cs.nott.ac.uk/~nxk/

e-mail: Natalio.Krasnogor@...

--------------------------------------------------------------------------------\
----------

Please consider sending your best papers to the
Genetic and Evolutionary Computation Conference (GECCO)
July 12-16 Dublin, Ireland, 2011
http://www.sigevo.org/gecco-2011/index.html

Two things:

1) I want to second Natalio's enthusiasm for the topic. I wonder if we
should hold an impromptu lunch meet up during gecco on this? Or, when the
GECCO schedule is set, we can find a time for discussions over a beer in
Dublin.

2)  I question how strict we should be about meeting a set of criteria to
qualify as a benchmark.

Sean said:
  >  >> - Fast. [I think under 0.005 seconds per evaluation on a typical
  >  >> processor.]

Una-May says:
Red herring...what's fast now is not what will be fast later. Why not
instead consider something like "tunably large"?


>

--
Una-May O'Reilly, PhD.
Principal Research Scientist, CSAIL, MIT
http://people.csail.mit.edu/unamay/
http://groups.csail.mit.edu/EVO-DesignOpt

just a small comment to add to this issue of
  speed:

  Sean, in your estimate you mentioned "single threaded" -
  but an inexpensive desktop machine now has quad cores
  and 8 parallel threads with hyper-threading - running a single threaded
application
  only uses just over 10% of its power - soon running these
  apps multi-threaded will be the norm (maybe it already
  IS the norm for most people on this list...)

  cheers,
     Simon

ps. I also agree this has been a good discussion.




-----Original Message-----
From: genetic_programming@yahoogroups.com
[mailto:genetic_programming@yahoogroups.com] On Behalf Of Natalio Krasnogor
Sent: 08 March 2011 17:05
To: genetic_programming@yahoogroups.com
Subject: Re: [GP] Call for Hard Benchmark Problems in Genetic Programming

....
>
> But I think speed is more important than you may have considered,
> because there is an additional constraint:
> benchmark comparisons require 50 to 100 independent runs per
> treatment.
>

No, i did not ignore the above at all (I've been playing this game for a while
now). Still, the constraints of 100 independent runs (how many runs you *really*
need depends on -amogst others- the variance you get and the design of
experiments you plan) or 0.004 seconds are pretty arbitrary numbers.
At the end of the day the point is not to necessarily to compare GP versus GP'
but to compare GP versus any other method, so if the same results on an
expensive problem can be done with other methods I will take it any day.

There are really expensive problems that may help push the GP state to the art
considerably and I think these cannot be ignored. Often, what you get are
situations not unlike design optimisation in which you are trying to get an
optimal design for a very "unique" artifact that you will design once (and
perhaps use multiple times or for long time), in that case, it does not really
matter if the evaluation takes 2 years-cpu time (not a great deal nowadays
anyways) because it gets recouped over time with the use of the designoid
artifact. This situation is very different, of course, to one where for each,
eg. new dataset, you need to GP-design a slightly different classifier of some
(some examples have already been circulated in response to your original email
covering this) in which of course you need speed.

In any case we can talk more during gecco and it is gret that you have brought
these matters of benchmarking to light, at the end of the day what would be
fantastic is a well annotated taxonomy of benchmarks for various classes of
scenarios people could draw from.

Thanks.

nat



>
>

--


Nat
--

--------------------------------------------------------------------------------\
-----------
NATALIO KRASNOGOR, Ph.D.

Professor of Applied Interdisciplinary Computing Interdisciplinary Optimisation
Laboratory (IOL) Automated Scheduling, Planning and Optimisation (ASAP) Group
School of Computer Science
Jubilee Campus, University of Nottingham Nottingham, NG81BB United Kingdom

Tel.: +44 - (0)115 - 8467592
Fax.: +44 - (0)115 - 8467066

Skype: Natalio.Krasnogor

URL: http://www.cs.nott.ac.uk/~nxk/

e-mail: Natalio.Krasnogor@...

--------------------------------------------------------------------------------\
----------

Please consider sending your best papers to the Genetic and Evolutionary
Computation Conference (GECCO) July 12-16 Dublin, Ireland, 2011
http://www.sigevo.org/gecco-2011/index.html






------------------------------------

Yahoo! Groups Links