IlliGAL Blogging

breveCreatures is a Mac OS X screensaver developed by Jon Klein that uses an evolutionary algorithm to evolve creatures capable of moving in a 3D environment:

breveCreatures is a screensaver that simulates the evolution of virtual creatures in a physically simulated 3D world. Beginning initially with random creatures, the screensaver uses a genetic algorithm to develop creatures capable of realistic locomotion behaviors.

The breveCreatures screensaver is based on Karl Sims' work Evolving Virtual Creatures. I've just installed the screensaver on my PowerBook and it's fun to watch it.

IlliGAL blogger and all around bon vivant Rob Smith has moved from Bristol to London and has set up shop (officially?) at University College of London (see here). Rob's rounduit blog continues to explore the realm of those things we all would like to get around to (get roundtuit, get it?).

Interesting post at My Heart's in Accra about the PACE project or Programmable Artificial Cell Evolution. The post centers on Norm Packard's role, but the website reveals an EU-funded effort of many collaborators. Norm was a UIUC colleague when I first arrived here in 1990. He went on to co-found the Prediction Company and is now CEO of ProtoLife located near Venice, Italy (not California).

A day in the life of the squiggle links to a game of tag played by an genetic-algorithm evolved population here.

Previously I have raved about the Teaching Company (see here), and last week I just finished another terrific course called the Theory of Evolution: A History of Controversy by Edward Larson at Georgia. This morning I started a new course called Argumentation: The Study of Effective Reasoning byDavid Zarefsky at Northwestern. I continue to be astonished by the uniform quality of these courses.

The Mercury News has recently published an article Machines are catching up to human intelligence by Robert S. Boyd. The article discusses the importance of artificial intelligence (AI) and mentions a number of important AI applications.

Besides others, they mention the use of genetic algorithms for satellite design at NASA's Ames Research Center in Mountain View, CA:

An AI technology based on evolutionary principles - known as genetic algorithms - helped NASA design three small satellites that will be launched in February to study magnetic fields in Earth's atmosphere.

"The AI software examined millions of potential antenna designs before settling on a final one," said Jason Lohn, the lead scientist on the project at NASA's Ames Research Center in Mountain View, Calif. "Through a process patterned after Darwin's survival of the fittest, the strongest designs survive and the less capable do not."

I just came back from Xin Yao's talk on Iterated Prisoner's Dilemma. It was good to see Xin Yao at our department and have an inspiring discussion. Besides other interesting ideas, Xin Yao talked about a more realistic iterated prisoner's dilemma with more than two levels of cooperation and the effects of assigning a reputation to each player.

While surfing the web I found a nice Java applet that shows a skeleton that is learning to walk using a genetic algorithm, you can find it here.

The demo is on the site of MajorSpot, who provides an artificial intelligence SDK that includes genetic algorithms, neural networks, natural language processing, and other components:

Welcome to the Majorspot community, a site dedicated to making artificial intelligence a reality for programmers around the globe. This community is proud to be the home of the MajorSpot AI SDK, an open-source Java software component aimed at helping software developers design their own AI-driven software using genetic algorithms, neural networks, fuzzy logic, wavelet analysis and other tools.

Majorspot.org is a free and non-commercial community managed by volunteers and sponsored by Majorspot, Inc. a leading force in AI software research applied to the real world.

Fujitsu Chugoku Systems Ltd. and Fujitsu Ltd. announced that they had developed Nurse Scheduler V4.0 with Prof. Kamei's lab of Ritsumeikan University, and both companies put it on the market on 10/21/05. See Japanese press release in detail.

They started to sell Nurse Scheduler V1 and V2 in 1993 and 1996, respectively. Competitive GA was applied to the Nurse Scheduler V3 in 2001, and Cooperative GA is applied to the Nurse Scheduler V4, this time. Thanks to new algorithm, V4 became 4 times faster and 10 times more precise than previous versions, they said.

As of March, 2005, their shedulers have been used at 220 hospitals.

Henry Kang, who is one of my colleagues here in St. Louis, published several interesting papers about using evolutionary algorithms for sketching and painting. You can find some examples of the results on his web page including PDFs of the papers.

Recently, I've read an article at the Air Force Research Lab Technology Horizons about using genetic algorithms to evolve wavelet transforms that produce higher-quality images with better compression ratios than standard techniques provide. This work was done by Dr. Frank Moore's group at the University of Alaska. The article was written by Mr. Pat Marshall, of the Air Force Research Laboratory Information Directorate, and Dr. Frank Moore, of the University of Alaska Anchorage. Check it out.

In previous posts (chain back starting here), I wrote about my son Max and our experiences during college visits last spring and during the summer. The saga continues, and we are well into the college and scholarship application season. Max has applied to 9 schools: Earlham, Eckerd, Harvard, Illinois, Kalamazoo, Northwestern (Medill School of Journalism), Ursinus, Washington University, and Yale. In all cases except Northwestern, Max is applying for admission to liberal arts; at Northwestern, he has applied to major in journalism.

One thing that made the application process easy was the existence of the Common Application. The common app is both a paper and electronic application system that allows you to fill out a single application for 277 participating schools. All schools in our list except Northwestern and Illinois take the common app. Max and I used the electronic version, and the web site was well designed and easy to use. Some of the schools required supplements beyond the common app, and the web site had a nice tab for handling those as well.

Max's schools divide into two many categories, research universities and small colleges. All of the small colleges are listed in Loren Pope's helpful book, Colleges that Change Lives. Max and his mom visited Ursinus last week, and Max stayed overnight in the dorms and went to class, had an interview, and went on a tour. I very much like the small schools we have visited. The campuses exude an enthusiasm for undergraduate education that just doesn't exist at a research university. Tours of buildings drip with evidence of student research and extracurricular activity.

Right now we're in the middle of applying for scholarships. Much of the money available today is based on need, but we're concentrating on merit aid. The Ivies and Northwestern don't give any merit aid, but WUSTL and Illinois do, as do the CTCL schools. Some schools include students in the merit pool merely by applying, and others require separate scholarship applications. Max was named a National Merit Semifinalist, and that award requires a special application to be named a finalist and to be eligible for other awards connection to it.

There are a variety of sites that provide very helpful information on scholarships. My favorite is Fastweb run by monster.com. It has tabs for scholarship, college, and job & internship searches. The interface is intelligently arranged and the site is easy to use. We've gotten good tips on scholarships from the site and have followed up on a number of them.

I don't remember the search for college being this hard. I applied to one school, Michigan, and went there. I don't remember it being hard to get in. I took one admissions exam (the SAT), one time. Today, the process is complex, the competition is stiff, and the examinations are endless. Collegebound students today face a gauntlet that has grown beyond reason, but wise parents and students will learn and play the game because the value of a college education is so high.

IlliGAL alum Y-p Chen has published his book on the linkage learning genetic algorithm. Here is more detailed information about the book:

TITLE: Extending the Scalability of Linkage Learning Genetic Algorithms: Theory & Practice

AUTHOR: Ying-ping Chen

PUBLISHER: Springer, 2005, XX, 120 p. 37 illus., HardcoverISBN: 3-540-28459-1

ABOUT: Genetic algorithms (GAs) are powerful search techniques based on principles of evolution and widely applied to solve problems in many disciplines. However, most GAs employed in practice nowadays are unable to learn genetic linkage and suffer from the linkage problem. The linkage learning genetic algorithm (LLGA) was proposed to tackle the linkage problem with several specially designed mechanisms. While the LLGA performs much better on badly scaled problems than simple GAs, it does not work well on uniformly scaled problems as other competent GAs. Therefore, we need to understand why it is so and need to know how to design a better LLGA or whether there are certain limits of such a linkage learning process. This book aims to gain better understanding of the LLGA in theory and to improve the LLGA's performance in practice. It starts with a survey of the existing genetic linkage learning techniques and describes the steps and approaches taken to tackle the research topics, including using promoters, developing the convergence time model, and adopting subchromosomes.

KEYWORDS: Chromosome Representation, Genetic Algorithms, Genetic Linkage, Learning Techniques, Soft Computing

TABLE OF CONTENTS
Foreword by David E. Goldberg
Preface
1. Introduction
2. Genetic Algorithms and Genetic Linkage
3. Genetic Linkage Learning Techniques
4. Linkage Learning Genetic Algorithm
5. Preliminaries: Assumptions and the Test Problem
6. A First Improvement: Using Promoters
7. Convergence Time for the Linkage Learning Genetic Algorithm
8. Introducing Subchromosome Representations
9. Conclusions

BOOK INFORMATION
http://www.springeronline.com/3-540-28459-1

ORDER IT ON AMAZON.COM
http://www.amazon.com/gp/product/3540284591

Some time ago I've read a few papers from Marc Toussaint from the University of Edinburgh, who proposes and discusses Compression Evolutionary Algorithms (CEAs). CEAs can be seen as an alternative to standard Estimation of Distribution Algorithms (EDAs), such as ECGA and BOA. Some papers can be found at Marc's webpage.

The basic idea in EDAs is to ensure effective recombination by building and sampling a probabilistic model that encodes important interactions between problem variables. CEAs look at the same problem from another perspective. Specifically, CEAs map (or compress) the current representation so that the variables become independent (or nearly independent). As a result, simple univariate models or other simple recombination operators can be used to generate new strings and ensure effective exploration of the search space for nearly decomposable problems of limited order.

The Computational Cognitive Neuroscience Lab has two openings for post-doctoral researchers, one to two years, and one PhD position. The openings are for non Italians only.

The first issue of the new electronic journal Bayesian Analysis has been
published at http://ba.stat.cmu.edu. Check it out.

The 3.0.0 version (with major updates) of Open BEAGLE has been released and can be downloaded here.

Open BEAGLE is a C++ evolutionary computation framework. It provides a high-level software environment to do any kind of evolutionary computation, with support for tree-based genetic programming, bit string, integer-valued vector and real-valued vector genetic algorithms, evolution strategy, co-evolution, and evolutionary multi-objective optimization.

Important feature enhancements of version 3.0.0:

* Integer-valued vector GA representation
* Initialization/crossover/mutation operators for shuffled indices integer-valued vector GA
* Travelling salesman problem example that illustrates the integer-valued vector representation
* GP primitives with dynamic number of arguments
* Dynamic selection weight of GP primitives for initialization and mutation
* Support for individuals with variable number of automatically defined functions (ADFs)
* Support for evolutionary module acquisition in the GP framework
* GP ephemeral random value mutation operator

Kalyan Deb receives Bhatnagar prize from Prime Minister of India

On September 28, 2005, IlliGAL alum, Kalyanmoy Deb (1st on left) received the prestigious Bhatnagar award from Prime Minister Manmohan Singh (2nd from right). More information is available here.