Monday, February 28, 2005

 

Let’s dance

The talking time is over. Yes, the Chance Discovery Consortium researchers are back in a white and cold Urbana-Champaign. After a 20 hours flight from Japan, they were at 9am sharp in the lab. It has been a long day. I do not know how they deal with their jet lag. We have been discussing the details of the methodology we are going to use for the experiment. The photo below shows (left to right, Yuichi Washida, Hiroshi Tamura, & Yukio Ohsawa) a little break during the discussion of a hot topic, the crafting and presenting of emergent scenarios based on KeyGraphs of a given communication. Starting tomorrow afternoon, the four-day experiment marathon will be at its max---reaching its climax on Wednesday afternoon---and we are running out of time to get everything ready.





Luckily, as I already mentioned on my previous post, nothing will be happening without the unconditional help and support of Chen-Ju Chao, Abhimanyu Gupta, Mohit Jolly, and Davina Lim. This DISCUS group, besides of their hard work, has been a great example of innovation and creativity, in the best DISCUS flavor.

The milestone of the day: Chen-Ju, below, just ten minutes away from nailing down the assistance of all the 50 students that will be part of the marathon. All in less than three days :D




 

Pot pourri of GA applications

Here in no particular order (or consistent selection criteria) are a number of sites featuring GA applications in chemistry, e-commerce, economics, the solution of ordinary differential equations, and water system design. Michigan State University has a nice listing of companies doing genetic algorithms and evolutionary computation here. The forum here claims to have the "Index of Most Important Applications of the Genetic Algorithms."

Sunday, February 27, 2005

 

Catching a Portugese digital fish

Caught the blog pescadordigital during a www.technorati.com fishing expedition. For those who don't speak Portugese (like me), use Google here to translate the page. The blog refers to another blog called webservcga that appears to be dedicated to reporting a school project at the University of Algarve (great windsurfing I'm told) involving a distributed compact genetic algorithm (CGA) in Java. All this surely traces back to IlliGAL Blogging blogger, Fernando Lobo, althought the Portugese Digital Fisherman does not identify him/herself explicitly.

 

GeneticGraph for aesthetic layout

Blog vas animatum has a link to GeneticGraph, a system that uses a spring algorithm in hybrid with a genetic algorithm to do aesthetic graph layout.

 

CiteULike

Machine Learning, Etc. has a useful post on CiteULike, a social citation system that looks pretty interesting.

 

More GA thesis blogging

Eagle-eyed blogger Yaroslav Bulatov of Machine Learning, Etc. left a comment to my post on thesis blogging about Trash Nexus, another genetic algorithm thesis blogger.

Saturday, February 26, 2005

 

Clustering for good

The DISCUS experiment continues with a firm pace. We have collected enough media survey questionnaires. After examining the questionnaires, Yuichi Washida has clustered the participants after his research achievements. In his own words on diffusion patterns of knowledge:
“Our arguments consist of two hypotheses: One is the difference of function by gender as a medium of knowledge diffusion in Japan's actual product market, while the other is the difference by generations. We found that certain generation and gender groups play important roles at the early stage of knowledge diffusion regarding new types of products with new technologies, which enable manufacturers to get effective feedback in creating and improving their products. We argue that the social network of this rapid and divergent feedback from the consumer side may explain why Japanese electronic manufacturers can realize high-quality products in short time periods.”
Questionnaires were grouped in four different clusters. The experiments that we will be conducting next week involve having enough representatives of each of those clusters. Scheduling people in groups, and making sure that they will be in, is a time consuming job---not to mention a tough scheduling issue.



The job has another added element of difficulty, the unbalanced distribution of participants among the different clusters. The board above shows the unbalanced distribution we face in two of the four clusters. Thus, for the success of the whole experiment, Chen-Ju Chao and Davina Lim---you can see them below---have been working hard to make sure that there are enough participants available from each cluster.



 

Panda uses "genetic" heuristic engine

Panda Software, a maker of computer security software, now includes a genetic heuristic engine to detect previously unknown malware without updates or signature files:

Panda has extended its TruPrevent(TM) Technologies and announces the availability of its most innovative heuristic technology against unknown threats: Genetic Heuristic Engine. This new technology integrates correlation of genetic digital signatures and deep code inspection in a single algorithm, patent pending, which scans the code and DNA traces typical of malware.

During the testing period, this technology has demonstrated remarkable effectiveness, detecting hundreds of new unknown malicious programs (including spyware) that have emerged over the last few months, without needing updates or signatures. By working alongside the rest of the TruPrevent(TM) Technologies, its detection capacity is maximized while false positives are minimized and with a minimum impact on system performance.
The company website is sufficiently obscure as to prevent this reader from knowomg whether the term "genetic" is used in the sense of a genetic algorithm or in the sense of a genetic metaphor. Do any IlliGAL Blogging readers know more?

 

GAs, swimming & data mining

Swimming science claims that the use of a simple GA to select features for data mining of data about swimmers helped improve classification accuracy by as much as 25.37%. Read the abstract of the study here.

 

Genetic Algorithm blog blogs GAs

Just found a blog named Genetic Algorithm on www.technorati.com. I missed it previously, because I have been searching on "genetic algorithms" (plural). Oops. The owner is apparently working on a thesis devoted to GAs and the traveling salesman problem. Lot's of water over that dam. Hope he/she considers using competent crossover/mutation per The Design of Innovation.

 

John Searle

A previous post remarked favorably on some of John Searle's work (let's sidestep the Chinese room for now). Here's a picture:



The picture above is one I've seen in book jackets before (linked from www.kurzweilai.net).

 

Making peace with postmodern thought

Julian Garcia links to the Postmodernism Generator, a site that uses AI techniques to generate sensibly insensible postmodernist essays. Scientists find this kind of thing enormously amusing since Alan Sokal's famous hoax, but I wonder if the joke isn't on us. The joke apparently is that postmodern argumentation has an involved set of semantic conventions and intricate theoretical constructs that look strange to the uninitiated, and the Sokal hoax showed that even the initiated have difficulty identifying the real thing.

But the essence of postmodernism (if such a thing can be said to exist) isn't really all that weird. It seems to me that the core of postmodernism is the acceptance of the principle that key facts of life are socially determined (little things like language, money, political and social institutions, that sort of thing) and our agreement (or disagreement) about their constitution is an integral part of their reality.

Of course, if this sort of thing is taken too far, it is a slippery and unacceptable slope toward solipsism, and from the point of view of an engineer or scientist, physics seems pretty darn real irrespective of the observer (Thomas Kuhn and his paradigm shifts notwithstanding). So what's a nice postmodern engineer to do in making peace with the postmodern world?

It seems to me that one sensible thing to do is to go read John Searle's account of all this in The Construction of Social Reality. Searle's brilliant argument preserves physics (brute facts) and delineates them from social facts in a rigorous manner. As with many philosophers, Searle's argumentation is not for the weak of heart, and it is not a light book to be read at the beach. Nonetheless, it seems like just the right antidote for those who might be tempted to take the postmodernism-as-joke thesis a bit too far.

 

Kevin Kelly lists advances in scientific method

Kevin Kelly, co-founder of Wired and futurist, has an interesting list of relatively recent innovations in the scientific method. To compile his list, he polled an eclectic group of scientific movers and shakers, and the result is posted here. The list includes "pattern mining," but it does not include automated invention via genetic algorithms or genetic programming. Pardon me for asking, but isn't the effective automation of the innovative/creative part of the scientific method kind of a big thing?

 

Dad, is that a good thing?

I was doing some google diving for old blog posts on genetic algorithms and came across an oldie but a goodie that brought back a funny memory. In 1997, I was interviewed by Jessie Scanlon then of Wired Magazine for an article called Mother Nature on a Motherboard. The article was published in the February 1997 issue on the Geek Page. I was pretty proud of myself, so I got a copy and brought it home. I was showing the article to my older boy Max, who had just turned 8, and said, "Max, here's an article about your dad on the Geek Page of Wired Magazine. How 'bout that?" He paused for a minute, his face got serious, and he replied, "Dad, are you sure the Geek Page is a good thing?"

Friday, February 25, 2005

 

Heard on the GA street

Future feeder has a post on genetic programming and human-competitiveness. Team popcorn appears to be doing a multiple-car race simulation using genetic algorithms here. Kerneltrap discusses the release of a new version of the genetic library patches for tuning the Linux kernel. ForwardMarkets has a post on using agents and genetic algorithms for calculations of strategic bidding in business. Maverick wonders why we can't create a real artificial intelligence given NNs, GAs, AI, ML, and all the rest. Finally, I never would have guessed how frequently people spell the word illegal as illigal on their blogs.

Thursday, February 24, 2005

 

Business blogging on the rise

In a previous post, I commented on the dearth and possible rise of academic blogging. In a related vein, Franz Dill has been blogging about the rise of business blogging, both in- and outside the walls of corporations. His latest post is over at IFTF's Future Now. A particularly good catch was his link to Business Blog Consulting. Franz is also blogger-in-chief over at The Eponymous Pickle, where today he has a short post on agent-based modeling.

 

Rubik's cube via EC

Virialexpansion wonders

I could probably use EC to attempt to solve the optimization version of that problem. There are still some more definitions that need to be made; if they can be quantified, then it could be attempted. I wonder if EC could find the theoretical minimum of T, not only the cardinality, but the actual moves? If it could, how would you prove it, though? The problem with that is that there are 43 quintillion different configurations of the cube... Ouch.

I saw an EC approach to Rubik's cube back in 1997 when I visited Ingo Rechenberg's Bionik und Evolutionstechnik laboratory at the Technische Universitaet Berlin as part of my first sabbatical. The link here has an Evolution Strategie approach to solving the cube and 9 other ES demos dating back to PPSN 1994.


.


The image above is of Ingo Rechenberg linked from his web page.

Wednesday, February 23, 2005

 

Ready, steady,…

The big day for DISCUS is coming. We have been collecting the media survey questionnaires for our colleagues in Hakuhodo and the Chance Discovery Consortium for more than a week. Now that we have the questionnaires, we will start contacting the people interested to join the focus groups for detailed discussions about how they use internet, email, and cell phones. From Monday to Friday, the lab will not look as empty as the picture below.



The only channel of communication among participants will be the computer-mediated one provided by DISCUS. Participants will be sitting at the lab workstations using DISCUS---yes, I will post some pictures with a lab running at full steam. No other communication among participants will be available. This way, we will be able to analyze totally self-contained communications using KeyGraph and Influence Diffusion Models.



However, this is not a one man’s job. I must thank all the DISCUS people. Without them, we would not even be able to think of doing the experiment we will be conducting next week. They are making possible this experiment a reality, taking even care of the smallest logistics details.

 

Stewart Wilson: Mover and shaker of LCSs

I started a photo tour of genetic algorithmists and computational evolutionaries with my image of John Koza a few posts ago. Here's an image of the prime mover of learning classifier systems (LCSs), Stewart Wilson:

.

The picture I wanted to post had Stewart wearing sunglasses, and they were a nice touch. But knowing Stewart they were for UV protection not the pursuit of cool.

 

Lemmings fans dig GAs

A team at Nottingham has developed a genetic algorithm to play the game of lemmings. Download the paper here. Hat tip to The Ludologist.

 

GAUL package updated

Freshmeat has a report that The Genetic Algorithm Utility Library (GAUL) has been updated:
Numerous additions and improvements were made. Most notably, island-model genetic algorithms are now available as parallel versions using either MPI or pthreads. Several new demonstration programs were added to the distribution.

More information is available on the GAUL homepage here.

 

GA used in lung cancer understanding

The New England Journal of Medicine reports the use of a genetic algorithm in better understanding a form of lung cancer. In an article entitled EGFR Mutation and Resistance of Non–Small-Cell Lung Cancer to Gefitinib, the authors report using GAs fairly routinely as part of structural modeling procedures:

The crystallographic structure of the EGFR tyrosine kinase domain, solved in complex with erlotinib, was used as a model for the prediction of kinase-inhibitor binding (Protein Data Bank accession code 1M17 [PDB] ).14 The inhibitor and solvent were stripped from the model. We used the AutoDock program, version 3.0,15 to predict binding, first using a model of erlotinib, made by means of the JME molecular-editing feature of the online resource PRODRG.16 The erlotinib test yielded a model for ligand binding highly similar to that seen in the crystal structure. Using the AutoDockTools interface, we used a grid spacing of 0.375Å and 60x50x40 points centered around the catalytic cleft of the enzyme for docking and adopted the genetic algorithm with local search using default settings. Gefitinib and CL-387,785 were then docked with the use of the same protocol. To illustrate potential inhibitor clashes with the T790M mutant, we prepared figures in which threonine at position 790 (T790) is mutated to methionine. We then chose the lowest free-energy cluster that overlapped in the quinazoline moiety with the crystallographic coordinates found for erlotinib binding.

This work cites earlier work in the following reference:

Morris GM, Goodsell DS, Halliday RS, et al. Automated docking using a Lamarckian genetic algorithm and empirical binding free energy function. J Comput Chem 1998;19:1639-1662.

Additional details are available here.

 

Man in the striped shirt

Genetic programming (GP) inventor John Koza has an unexplained penchant for wearing striped shirts regardless of the occasion.



Red stripes are his clear favorite, although the picture (linked from www.genetic-programming.org) shows a dashing gray-blue stripe. Must have been a special engagement or holiday.

 

$10,000 in prizes for GEC human-competitive results

John Koza and Third Millennium Online Products, Inc. announce a competition for human-competitive results produced by genetic and evolutionary computation. The deadline for the competition is 20 June 2005 and the announcement may be seen here. According to the competition, a result may be considered human-competitive if it satisfies one of 8 criteria:
  1. The result was patented as an invention in the past, is an improvement over a patented invention, or would qualify today as a patentable new invention.
  2. The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.
  3. The result is equal to or better than a result that was placed into a database or archive of results maintained by an internationally recognized panel of scientific experts.
  4. The result is publishable in its own right as a new scientific result ¾ independent of the fact that the result was mechanically created.
  5. The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.
  6. The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
  7. The result solves a problem of indisputable difficulty in its field.
  8. The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs).

The inaugural competition in 2004 awarded $5000 in prize money among six medalists.

In the interest of full disclosure, the writer of this post was a contest judge in 2004 and will serve in that capacity again this year.


 

RioRoboLab demos autonomous chopper

The New Mexico State University Roundup reports that members of the RioRoboLab showed a tethered helicopter during visitors day:
RioRoboLab director Ram Prasad said work on the autonomous helicopter began last semester as a Capstone Design effort under sponsorship of the U.S. Army White Sands Missile Range. A Capstone Design is an academic requirement for all graduating engineering students. Prasad said although helicopters are the most maneuverable aircraft, they are the most difficult to control when trying to provide stable flight characteristics. The objective is to implement technologies that are bio-inspired and can emulate human behavior to fly the helicopter. In response, students in the RioRoboLab have worked toward developing control systems to allow a model helicopter to attain autonomous flight.

Whether or not genetic algorithms or evolutionary computation were part of the demo is unclear from the article; however, the lab is a part of a larger Rio Grande Soft Computing Institute. The mission of the institute is "to develop and facilitate the application of innovative soft computing technologies for modeling, analysis, prototyping, manufacturing, testing and evaluation of dynamic processes and systems that have use in government and in industry."

Tuesday, February 22, 2005

 

The evolutionary music of E. R. Miranda

I was browsing the web for information on evolutionary music and came across the entries at Sony CSL Paris here and that took me to E. R. Miranda's web site at Plymouth here. Check out the cut Electroacoustic Samba II from his album Mother Tongue.

 

Flickr pool features evolutionary art

Flickr.com supports photo and image blogging, and a Flickr group devoted to Generative and Evolutionary Art has formed here. There's not many words on the site, so its hard to determine the techniques used on each image. Nonetheless, here is an image by killbyte called Pointy Rainbow.

 

GAs mentioned in networking book

ITworld.com has an interview with Max Goff, author of Network Distributed Computing: Fitscapes and Fallacies (Prentice-Hall) in which Goff mentions the possibility of evolving networks of distributed computers using genetic algorithms and genetic programming. He coins the term fitscapes as a contraction of the more familiar "fitness landscapes" in talking about distributed networks.

Althought Goff's argument is cast in evolutionary terms, his reasoning is more like that of Adam Smith in Wealth of Nations:
Goff: Well, it dawned on me that there were a lot of autonomous entities that were involved in the creation of software -- i.e., individuals and companies. But it also dawned on me that the good things that would probably happen with respect to software, if that fitscape model -- in other words, autonomous agents operating in their own best self interest -- if that sort of model were unleashed from a software perspective, that good things would happen. And part of what I discuss in the book are platforms that tend to give rise to that sort of organic behavior.

The only thing missing is the invisible hand. Although GAs, GP, and EC generally are useful technology, their influence as metaphor for reasoning about population-oriented systems is perhaps just as important.

Monday, February 21, 2005

 

Rube, Dave, what's the difference?

Someone searched on the term "Ruby Goldberg," but I think they meant Rube Goldberg, the cartoonist. I have a stash of Rube Goldberg postcards with reprinted cartoons I use as thank you notes, although to my knowledge there are no family ties between us. Here is Tee Up a Golf Ball. The groundhog is a nice touch.

Sunday, February 20, 2005

 

Folksonomy, John Holland, and DB design

Here is a white paper from a company called Ecosystems Design, Inc. that uses Hollandian ecosystems as a metaphor for database system system. The white paper is written by Len who then, writing at Life Among Mammals, uses Holland's bucket brigade here for some speculation regarding folksonomy.

 

Use GAs to identify dialects?

Don Schwartz speculates that a spatial GA might be used to analyze and identify the dialect of a speaker. There has been a fair amount of work on GAs and speech recognition and some on GAs and natural language processing. How would such an application really work?

 

Great workshops at GECCO-2005

The Genetic and Evolutionary Computation Conference (GECCO-2005) to be held in Washington, DC, 25-29 June 2005, (Saturday to Wednesday) has a terrific lineup of workshops:

A complete listing is available here. Workshop attendance is included at no additional charge in GECCO registration fees. A number of IlliGAL Blogging bloggers are workshop organizers. Perhaps some of them will tell us how their workshop plans are coming along.


 

Peirce, Burks, and GAs

I just saw Rob Smith's nice post on Peirce. Given the connections Rob makes, it should come as little surprise that genetic algorithms have an interesting intellectual lineage vis a vis Peirce. John Holland, genetic algorithm pioneer, was the first PhD in Communication Science (later Computer and Communications Science) at Michigan. Holland's dissertation advisor was Arthur W. Burks. Burks worked on the original ENIAC



(I believe Burks is the gentleman seated in the picture, but I can't confirm this in any of the web sources I could find) and founded Michigan's Logic of Computers Group. But Art Burks is also a Peirce scholar and edited the final two volumes of Harvard's Collected Papers of C. S. Peirce (see here) . Here is a listing of some of Art Burks's other books.

 

Confessions of a Teaching Company fan

This post doesn't have anything to do with genetic algorithms, but I was exercising this morning and watching Jules Schwartz of Boston University lecture on product life cycle in his course Finance and Accounting for the Non-Financial Manager offered by the Teaching Company. I've been a fan of the teaching company for maybe eight years. Back then, I was a runner (jogger really) training for marathons, and I would get Teaching Company audio tapes to keep me company during long training runs and learn new stuff. I've stopped pounding the pavements, and now exercise indoors, and I get TC videos to keep me company on my Precor elliptical trainer (sigh, if only IlliGAL Blogging readership warranted product endorsement fees). Anyway, if you've never taken one of these courses, do it. An early course in my listening was Great Minds of the Western Intellectual Tradition. It is now in its 3rd edition and is well worth the investment of time and money.

Friday, February 18, 2005

 

Some serious EH blogging in Portugese

There's some serious blogging on evolvable hardware over at eyes wide open in Portugese.

Thursday, February 17, 2005

 

Gizoogling GAs

According to today's Wall Street Journal, google.com is available in over 100 languages, but not hip-hop slang. That stunningly insensitive marketplace void was recently filled by gizoogle.com. Doing a search on genetic algorithms on gizoogle (here) is enlightening dawg. Peace out.

 

The rise of academic blogging

Yesterday I posted the following:


Since IlliGAL Blogging opened up shop on 24 January, I've been a little surprised that the young avant garde of the EC world hasn't been blogging its brains out, but maybe I'm missing something.
To which, Amir at thesilog commented:

During my surfing in blogosphere, I have found few really technical weblogs. This rush of academic weblogs (in AI-related fields) is rather new or at least new in the eye of me! Most previous academic weblogs are something between daily life of an graduate student or professor and their research-related news, e.g. mine weblogs is a sample of it.
Yes, this is what I've found, and I think it is rather surprising. Blogging has been around for awhile. I would have thought that dozens of young faculty and hotshot grad students who already were blogging for personal reaons would have turned to academic blogging by now.

Amir continues

And more importantly, it would be nice to discuss about "what a weblog can do for us?". Is it a place to report, or a place to disuss, or place to fast-publishing? What about its formality? Can I claim that I have this XYZ idea if I do not publish a paper in a conference or journal and write a post in my weblog instead?
Others need to answer these questions for themselves, but my lab website has always been a place to disseminate work, inform, and influence. Blogging for IlliGAL Blogging is a way to do those things in a manner that can provide more continually updated content. Also the comment facility allows us to have useful online dialogue in a straightforward manner. Previous efforts at interacting with readers were too static or too annoying.

Moreover, I like the informality of blogging, but I've never been one to be overly formal in academic discourse either. This work is fun. I'm not sure why it is necessary to dress up the joy of discovery in stilted language and thereby turn it into a form of drudgery.

I do share Amir's concern with posting new ideas prior to publication. I don't believe blogging takes the place of scholarly publication, and we are holding new results from this site until they are published. Having said this, it has been a long standing policy at IlliGAL to publish papers as tech reports on the web immediately following paper completion. The public nature of that posting has made it difficult for others to claim our ideas as their own, and perhaps contemporaneous posting of new ideas to a blog could serve the same function. This might especially become the case if bloggers continue their habit of citing one another generously (as is the academic ideal).

If this were to take place, rapid exchange of new ideas in blogs could represent a new kind of open-source brainstorming, but I have difficulty believing this process will become the norm. It is hard to imagine a tenure and promotion committee ever looking favorably upon a series of blogposts as being sufficiently serious. On the other hand, much of what is going on right now on the web was difficult to imagine 15 years ago. What do IlliGAL Blogging readers think?

Wednesday, February 16, 2005

 

Notes 2 Self notes EC Blogs

Notes 2 Self notes lots of new EC blogs here. Has anyone got a listing of other EC-related blogs. Since IlliGAL Blogging opened up shop on 24 January, I've been a little surprised that the young avant garde of the EC world hasn't been blogging its brains out, but maybe I'm missing something.

 

Supergenes and competence

Javarunner continues to post about JGAP and evolutionary computation here, but digging below the surface shows an interesting post on supergenes. Supergenes in JGAP aggregate variables that are interrelated either from inspection of the set of equations being optimized or intuition. The supergene page claims the following:
The supergene conception can significantly (up to 3 times in the most boundary cases) increase the evolution speed. It can also increase the accuracy of solution for the small populations. However these effects are dependent from the chosen population size and maximal number of iterations. While in some cases the use of supergenes can be definitely sensible, we would recommend to try both supergene and non-supergene versions for your specific task.
Interestingly, IlliGAL work has demonstrated significant speed ups (sometimes going from exponential scalability to subquadratic) in hard problems in similar way, except IlliGAL competent GAs require no prior knowledge of the problem being solved or the variable interrelationships. This approach works, because initial results are used to determine which variables are interdependent, and then "supergenes" are automatically constructed to solve the problem quickly.

Similar automatic linkage detection or supergene detection could be built into JGAP and other traditional GAs so they automatically give faster, better solutions to hard problems without as much prior problem knowledge or understanding.

 

Script and program resources listed

at Marcus Zillman's Script Resources blog here.

 

Wash mouth out with GA SOAP

Jim Fuller's ruminations on XML, XSLT, and Ant posts a link to a ppt presentation on how to "create a GA process that will discover the XSLT program which taken a source.xml generates a target.xml."

 

Holland festschrift volume published

I received my shiny new copy of the edited volume Perspectives on Adapation in Natural and Artificial Systems from Oxford University Press today. Some of the contributors include Kenneth Arrow, Brian Arthur, Bob Axelrod, Lashon Booker, Michael Cohen, Stephanie Forrest, Doug Hofsatadter, John Koza, Melanie Mitchell, Rick Riolo, and Oliver Selfridge to name a few. The volume follows up on the 1999 festschrift in Ann Arbor honoring John H. Holland's many contributions to science and technology. My contribution is entitled, John H. Holland, Facetwise Models, and Economy of Thought. Only $54.50 in hardcover. Operators are standing by to take your call (actually servers are standing by to take your computerized order).

Tuesday, February 15, 2005

 

Why blog? Hugh Hewitt's answer

Hugh Hewitt's recently released book Blog: Understanding the Information Reformation that's Changing Your World, follows the recent history of how blogs changed the course of the 2004 US Presidential election. He also considers the current information reformation as analogous to the Protestant one that followed the introduction of Gutenberg's press. The analogy, according to Hewitt, is about the rapid, qualitative shift in the speed of information dissemination (p. 55):

But Luther was living in a new day. Almost immediately after they were posted [Luther's 95 theses, which were originally written in Latin], someone, no one knows exact who. got hold of a copy of Luther's theses, translated the Latin into German, and published them. Thanks to Gutenberg, Luther--and more important, his ideas--were known all over Germany within two weeks, and all over Europe in a month.

The book has useful chapters on the nuts and bolts of blogging, blogging as an organizational tool, and the kinds of blogs Hugh would like to see started himself. His list of do's and don'ts is helpful:
The key rules of blogging success and significance are these:
  • Post often.
  • Link freely.
  • Be generous in praise and attribution.
  • Don't be long-winded too often, if at all. Brevity is the soul of blogging when you are getting started.
  • Paragraphs are your friend.
  • Profanity loses audiences.
  • Avoid feuds and flame wars.
  • At least at the start, skip the comments sections. You end up with the problem of nuts if you are any good.
  • Keep the title short and easy to remember so that it is easy to recall and type into the space at the top of the page.
In the main, this sounds like good advice to me.

 

TDD, GP & testing in general

There is a post at javarunner linking TDD or test-driven development and genetic programming. Of course, the idea of using GAs in test generation goes back a ways, but the post seems to be pushing this in a more philosophical direction.

 

Open source search engine for Java GAs

The search engine koders.com specializes in searching for open source software. Try the search for genetic algorithms in Java here. Hat tip livejournal.

 

GAs as a labor of love

ForwardMarkets has an interesting post about personal motivation and AI (in particular, GAs). AI and GAs were a labor of love in his case, but they are for most of us. GAs were/are CP-cool and CP-easy (cocktail party cool to talk about and fairly easy to convey the main ideas), but they are engaging enough to get totally lost in. You like analysis, have we got analysis to do. You like design, have we got creative ways to fiddle with mechanism. You like applications, the spectrum of human endeavor is your oyster. And if you have a contrarian streak, you get to rebel against the received CS/AI wisdom and be on the edge, although (hopefully?) some of that is going away (see SIGEVO: From Outlaws to Mainstream post here).

Monday, February 14, 2005

 

Fourteen days to D-day

The DISCUS experiment is getting closer and closer. As mentioned in a previous post, the purpose of this survey is to understand how and why a consumer uses each new media and communication means such as the Internet, email, and cell phones in daily life. By this study, we hope to find more efficient and comfortable ways and media of communication toward the near future. These marketing research is conducted by researchers of Hakuhodo Inc., Illinois Genetic Algorithms Lab, and Chance Discovery Consortium using cutting-edge innovation and creativity support tools for computer-mediated communication developed as part of the DISCUS project.

In the first four days we already collected 20 questionnaires. Our goal is to reach 200 questionnaires by the February 23, and invite 40 participants to join the focus groups. If you are UIUC student or affiliate and want to participate, just send a mail to discus@illigal.ge.uiuc.edu. Surveys can be filled until February 23, and selected candidates will be asked to participate on focus group activities the week from February 28 to March 4.

 

Ying-ping Chen directs NCTU Natural Computing Lab

IlliGAL alum and IB (IlliGAL Blogging) blogger Ying-ping Chen is directing the Natural Computing Laboratory at National Chiao Tung University in Hsinchu City, Taiwan. Y-P is known for his work on analysis and extensions to the linkage-learning GA. He also has extensive experience in practical experience in using GAs in the real world.

 

The abstract of my PhD thesis

Hello,

I am posting the abstract of my recent PhD thesis, which was greatly improved from by visit to IlliGAL last spring.

Title: Pittsburgh genetics-based machine learning in the data mining era: representations, generalization, and run-time

Abstract:


Pittsburgh genetics-based machine learning (DeJong, Spears, & Gordon, 1993) is, among others (Wilson, 1995; Venturini, 1993), an application of evolutionary computation techniques (Holland, 1975; Goldberg, 1989a) to machine learning tasks. The systems belonging to this approach are characterized by evolving individuals that are complete rule-sets, usually variable-length. Therefore, the solution proposed by these kind of systems is the best individual of the population.

When using this approach, we have to deal with some problematic issues such as controlling the size of the individuals in the population, applying the correct degree of generalization pressure across a broad range of datasets, reducing the considerable run-time of the system, being able to solve datasets with diverse kind of attributes, etc. All these issues become even more critical when applied to modern-day data mining problems.

In this thesis we have the general objective of adapting the Pittsburgh model to handle successfully these kind of datasets. This general objective is split in three: (1) Improving the generalization capacity of the model, (2) Reducing the run-time of the system and (3) Proposing representations for real-valued attributes. These three objectives have been achieved by a combination of four types of proposals:

- Explicit and static default rules
- Windowing techniques for generalization and run-time reduction
- Bloat control and explicit generalization pressure techniques
- The Adaptive Discretization Intervals rule representation for real-valued attributes

Some of these proposals are focused only on a single objective, some others solving partially more than one objective at the same time. All these proposals are integrated in a system, called GAssist (Genetic clASSIfier sySTem).

An experimentation process including a wide range of data mining problems based on many different criteria has been performed. The experiments reported in the thesis are split in two parts. The first part studies several alternatives integrated in the framework of GAssist for each kind of proposal. The analysis of these results leads us to propose a small number of global configurations of the system, which are compared in the second part of the experimentation to a wide range of learning systems, showing how this system has competent performance and generates very reduced and interpretable solutions.



As one of the topics of my reseach is the use of default rules, I am very interested in the work of Rob Smith in this topic.

Sunday, February 13, 2005

 

GAs dissed at remarkably unreactive

Blogger remarkably unreactive spends much of a remarkably uninformed post dissing GAs (and the engineers who make and use them). If only he knew about the many cool things GAs and GP are doing in his own field. I suppose I could post a set of interesting links to chemistry and material science applications of GAs and GP. Nah. Let him find his own way into that growing literature.

 

Ian Clarke is playing with GAs

here.

 

Evolutionary art featured at The Big Picture

Vik Rubenfeld's The Big Picture has a nice post on evolutionary art.

 

Rob Smith posting

I'm glad to see Rob Smith and his maiden posts on IlliGAL Blogging. Rob did the first post-renaissance thesis on dynamic environments and GAs in 1987 and his PhD dissertation did a lovely job of trying to advance Holland's notion of a default hierarchy by creating an adaptive scheme to properly place rules in an effective hierarchy without prior assumptions about specificity or the like (Alert, Alert, Alert: This work should be revisited by GBML types. It has been wrongly overlooked, mainly because it was about a decade ahead of its time). Since then, Rob has held a variety of positions in the US and the UK. He currently is at the University of Western England (UWE), and his CV and publications list are available here. One of his most often cited works is his application of learning classifier systems for learning high-performance fighter jet maneuvers.

Saturday, February 12, 2005

 

Epistasis Blog is blogging about..

epistasis here. Would someone please connect biological concern with epistasis to GA concern for problem difficulty here.

 

Co-evolutionary wiki up and running

Paul Wiegand noticed IlliGAL Blogging and asked me to post an announcement for the Co-Evolutionary wiki that is up and running, so here it is:

Dear colleagues,

At GECCO-04, an informal coevolution discussion was held where many of the terms used in coevolution were discussed. As a result of this, and after substantial further discussion via email, we have set up aCoevolution Wiki which offers descriptions of several main terms. Naturally, all of these descriptions are subject to debate, and the wiki therefore features a dedicated discussion page for each term. The Coevolution Wiki can be visited here:

http://www2.demo.cs.brandeis.edu/cgi-bin/coec-wiki

Contributions to this online discussion, or any other comments, are very welcome!

Signed, Anthony Bucci, Edwin de Jong, Anthony Liekens, Paul Wiegand


I took a look, and the coec-wiki has made a nice start. Go peek yourself.

Blogging and wikis are important content management tools that should receive greater use in the community for information dissemination and exchange. I applaud this and other efforts in the same vein. We may be a little behind the wiki curve in my lab, but we are now using one for internal lab information exchange online. Some of the free tools are quite sophisticated and good.

 

GA efficiency in 4-part harmony

In a recent post I discussed the term competence in connection with GAs. The term is used to refer to well-designed GAs that solve a large class of hard problems quickly, reliably, and accurately. The bottom of line of designing competent GAs to solve problems in the class of problems Herb Simon called nearly decomposable is that you end up with solvers that might be as good as subquadratic, that is, they give good solutions in times that grow no more quickly than a quadratic function of the number of decision variables (in a relaxed PAC sense).

Polynomial time is usually good news and cause for celebration, but if you are solving big ole problems, the square of a large number is darn huge (yes, Virginia, these are technical terms I'm using here). The square of a thousand is a million, which means that you might have to go off and run 1000s of function evaluations in large problems, which may be impractical if your eval is an expensive simulation, computation, or data-crunching task.

Thus, we see a problem with stopping at seeking GAs that are merely competent. Yes, competence takes us from solutions that are worst-case exponential to polynomial (from intractable to tractable), but to go from tractable to practical requires that we pay attention to enhancing the efficiency of effective (competent) GAs.

At IlliGAL we do this with a four-part decomposition of the efficiency problem:
  1. Parallelization
  2. Time continuation
  3. Evaluation relaxation
  4. Hybridization

Erick Cantu-Paz's work was our first principled foray into the issue of parallelization. My paper on time continuation set the stage for Ravi Srivastava's thesis and Kumara Sastry's work with me on BB-mutation. Kumara's MS thesis and Laura Albert's thesis set the stage for our current thinking in evaluation relaxation. Work with Siegfried Voessner in 1999 laid down a barebone's framework for thinking about global-local hybrids and was followed up by Abhishek Sinha's MS thesis. Many of these items are cited in the references of The Design of Innovation (Google searchable version here).


 

GA-created music

As long as I am blogging about stuff (like art) that was once believed to beyond the reach of computation, I should mention evolutionary music. Al Biles, a frequent contributor and attendee of the GECCO conference, has a nice summary of his work here, along with a bibliography of evolutionary music more generally here.

 

Genetic and evolutionary art

A stock phrase in some of my writing has gone something like the following: "Genetic algorithms are used across the spectrum of human endeavor," and some have criticized that sentence as overstated, but compared to other computational procedures, GAs have found their way into nooks and crannies of human thought that have previously resisted computational aid. One area where this is particularly true is in the realm of visual art. Since the early 90s, a fair number of people have used genetic algorithms to evolve art. A nice survey site is here. A page of Steven Rooke's work is here, and a site citing Latham's work is here. Whether you find the art products pleasing to your eye is not really the issue. That a computer program was an active participant in the act of creation is.

Friday, February 11, 2005

 

Biota.org, darwin@home & the Alive Prize

Picked up on biota.org from ruminator's ilk, which led me to Darwin at Home which has a list of advisors. Here is the project mission statement:

It is our hypothesis that compute space is now or soon will be sufficiently rich and complex to support a reasonable "lifelike" simulation of the processes and products of evolution.

The Darwin@Home project is a challenge to multiple, independent teams to construct platforms in software, hardware or a combination, to test this hypothesis. In recent years, several platforms have been built that suggest that this goal is attainable. We believe that by pooling efforts and creating a shared community of interest, we will quicken the journey along the path of innovation.

The project has been picked up in NewScientist.com and eventually the project would like to offer a prize similar to the X prize:
A long term goal of Biota.org has been to create an international prize competition called the AlivePrize. Darwin@Home is a first step along that road by encouraging the community of people developing platforms and providing them resources and intellectual contributions. In a couple of years after the Darwin@Home efforts have matured, we will pursue the goal of financing and managing a competitive prize modeled after the Ansari X-Prize and the DARPA Grand Challenge.

I wonder whether this sort of thing is helpful to the field or merely shameless self-promotion and grandstanding. But perhaps some of you are wondering the same thing about this blog.

 

Is your GA competent?

At IlliGAL, we use the term competence to refer to principled procedures that solve a large category of hard problems quickly, reliably, and accurately. By principled, we mean that there exists theory that gives us reason to believe that the procedure will work and scale well over the whole class, but we stop short of requiring a convergence proof (see my burning GAs and toaster convergence rant) and accept dimensional arguments bolstered by facetwise or other simplified models. The quick, reliable, and accurate part is quite similar to the usual requirements of PAC learning. We want polynomial time performance, that is probably approximately close to being accurate. For hard problems we look for boundedly difficult problems along dimensions of difficulty that challenge our procedure. This is a game theoretic argument. If we understand the dimensions of problem difficulty, and we can solve problems on some farout boundaries of those dimension in a sufficiently quick, reliable, and accurate fashion, we should be able to solve easier problems as fast or faster as those on the edge of our design envelope. The end result are procedures that scale nicely (subquadratically as problem size grows) whereby GA parameters can be set in a principled manner to give reliable and accurate solutions.

 

IlliGAL Blogging rolls expand

IlliGAL Blogging welcomes more alums and affiliates to our roll of bloggers. Yukio Ohsawa (yukio) is a faculty member at Tsukuba University just outside of Tokyo and spearheads reseach in chance discovery. Naohiro Matsumura (nao) is on the staff of Osaka University and is pursuing very interesting reseach using the influence diffusion method (IDM). Long-time GPer Una-May O'Reilly works in Rod Brooks's robotics lab at MIT and is current chair of the GECCO conference. Welcome, welcome. Now post, post.

Thursday, February 10, 2005

 

More Georges

More on IlliGAL alum Georges Harik and Gmail from BBC News here.

 

Georges Harik, IlliGAL, and Google

During the mid-90s, Georges Harik visited the Illinois Genetic Algorithms Lab for an extended period as part of his PhD studies at the University of Michigan. He did a lovely thesis on the linkage learning GA, and did a number of other very creative things, including the gambler's ruin problem population sizing, compact GA, and extended compact GA. Georges left the lab to make his mark in commerce, first working for a data-mining group at SGI and then taking a position as one of the early employees at Google in early 1999. Today, Georges is Director of Googlettes as part of Google. Read and listen to his interview on WebTalkRadio about his role in Gmail.

 

Chance discovery, marketing, and focus groups: DISCUS is comming

The DISCUS project is approaching to a big milestone. During the last fall visit to Urbana-Champaign of our research colleagues from Hakuhodo, Tsukuba University, Osaka University, and the Chance Discovery Consortium, we agreed we needed to have common users involved in our research endeavor. They are the final users of the DISCUS tools, thus, the sooner we get their feedback the better.

We have been designing a big experiment to validate some of our theoretical assumptions and results on innovation and creativity support, and influence diffusion in web-centric social networks. From February 28 to March 4, several focus groups will be using the state-of-the-art DISCUS platform. The goal, to discus about media environments under the guidance of our Hakuhodo colleagues. Around forty, non-DISCUS related, potential customers will form several focus groups to discus about different media environments and how they use them. Besides the intrinsic marketing interest of such experiment, this first big stress test will help us to see, in real time and close to reality, the performance and feedback of the innovation and creativity support tools of DISCUS.

Wednesday, February 09, 2005

 

Genetic algorithms walking back to their source

There is no point in saying that genetic algorithms were inspired on biological grounds. This is not new. However, currently there is a pushing effort to explore how evolutionary method may be able to go back to the source and help solving hard problems, closing an interesting loop. There are several applications of evolutionary computation in the bioinformatics and biochemist, to mention a few, closing a thirty years loop. Here are two links to interesting results to real applications and results of using evolution as design tools. The first one shows the virtual images of peptides designed using genetic algorithms to block pathogen interactions between proteins---I have been involved in this work. The second links is an interesting paper on another approach proposed to evolving molecules for drug design by James Foster.

 

GAs picked up in mainstream blogs

The Technology Review story on GAs is getting picked up in a variety of blogs, including non-geek blogs. The Big Picture by Vik Rubenfeld is the latest to do so.

 

Creative evolutionary design tools

This is a small follow up on my last post about creativity, genetic algorithms and architecture. Leandro Madrazo emailed me about the post on evolutionary methods and architecture. The truth is that I really appreciate him spending time on this blog. Again, if you are interested on collaborative human-based genetic algorithms and architecture, you may want to a closer look to his work. Another must read work on the convergence of evolutionary computation and creativity, with again some applications to architecture, is the one by Una-May O’Reilly. She has been working on very interesting applications of genetic programming and artificial life. You can check it out here.

Tuesday, February 08, 2005

 

Take a chance on chance discovery

I was recently asked to write a foreword for a new volume of papers on chance discovery. In particular, Readings in Chance Discovery, Akinori Abe and Yukio Ohsawa (editors), ISBN 0-9751004-8-3, will soon be published in the International Series on Advanced Intelligence (Series Editors: R. J. Howlett and L. C. Jain) . I wrote the following:

I first became familiar with the term "chance discovery" on a trip to Japan in December 2001. I was invited to give a series of lectures on genetic algorithms and engineering leadership at the Graduate School of Systems Management of Tsukuba University by my good and longtime colleague Takao Terano. One of the hosts for the visit was a relatively new faculty member named Yukio Osawa, and when I arrived, he filled my ears with the glory of chance discovery. Unfortunately, during that first meeting, Dr. Osawa's zeal for chance discovery went in one of my ears and out the other, and if the situation had not changed, this story would have had an uninteresting ending. But Dr. Osawa is nothing if he is not persistent, and he continued to regale me with tales of chance disovery accomplishment, and somehow he got me to come back to Japan and give a tutorial with him merging GAs and CD topics into one program.

At that second meeting, my ears and my mind opened up, and I came to realize the importance of CD as a subject. Simply put, where much work in data-mining makes hay from high probability co-occurences, CD uses a variety of techniques to elevate and study the unlikely. In so doing, chance discovery focuses on phenomena that may be important in the future, on phenomena that may be an underlying and unrecognized cause, or important background phenomena that just plain deserve further exploration and explanation. As a result, chance discovery appears central to better, more mechanistic, understanding of creativity, smart mobs (to use Rheingold's term), and, more generally, the unexplained.

Since that second meeting, I have become a fan and sometimes practitioner of CD and its extensions. My own work on on collaborative systems couples genetic algorithms (regular, interactive, and human-based) with Keygraph chance discovery to help support organizational innovation (see http://www-discus.ge.uiuc.edu/). Chance discovery continues to chug along as a field in Japan, and the current volume's geographical representation shows that CD is becoming (has become?) a
scientific topic without borders.

In short, the current volume advances the state of chance discovery art, in philosophy, in theory, and in practice. For those who are familiar with chance discovery and uses, it is an indispensible guide to where CD research is and is going. To those who are unfamiliar with the topic, I recommend it as an entry point to an important area. Either way, I urge you to pick up this volume read it, use it, and don't be like me and take another eight months to pay attention and get involved.

I mean it. Go read something about chance discovery.

Monday, February 07, 2005

 

Catching up on GAs

Thanks to ForwardMarkets for noticing IlliGAL Blogging. The post mentioned the value of this site in catching up on GAs since the publication of my 1989 book, Genetic Algorithms in Search, Optimization, and Machine Learning (GASOML). In 2002, I completed the now Google searchable The Design of Innovation: Lessons from and for Competent Genetic Algorithms (DoI). The aim of the volume was to fill a void between largely empirical studies of this, that, or the other new operator and purely theoretical studies using lovely mathematics that have very little to tell us about the design of GAs that really work. The approach of the book in understanding fundamental facetwise and patchquilt models has been extended to understanding multiobjective GAs, classifier systems, and organizational size. Such usable theory may answer exactly the kinds of questions IlliGAL Blogging readers have been accumulating since the publication of GASOML.

 

Burning GAs & toaster convergence

I met a young man today who told me a story about a professor at a major US university. The faculty member, trained in traditional operations research (OR), opened his class on optimization with the phrase, "Burn genetic algorithms." What an open-minded sentiment. The enlightened gentleman went on to argue that most problems of interest could be solved by assuming convexity. When one has a hammer, everything DOES look like a nail, but tackling only the problems we can provably solve seems remarkably uninventive, especially coming from a professor of technology in this most inventive of eras.

After all, we don't place the same burden of proof on other inventions used in our everday lives. Has anyone proven that an airplane flies--that is, really proven flight in a sense that would satisfy the spherical gentleman in his convex world? Has anyone proven that an automobile is mobile? Has anyone proven that a toaster toasts bread? Indeed, we do understand the principles of flight, the physics of internal combustion, the science of electricity and heating, and it is important to understand physics and principles in any design task, but proofs of convergence elude us in even fairly simple material machines; we don't even think it very worthwhile an endeavor to pursue such proofs. Why then do we demand so much more from conceptual machines such as optimization procedures, computer codes, and genetic algorithms?

One answer is that we are trapped in Descartes's mind-body dichotomy, treating conceptual objects differently and separately from their material counterparts. If this is the problem, why don't we just stop ourselves before we kill again. Design is design is design, whether it is performed on material or conceptual objects (repeat this six times before bed time).

Another answer is that we are all merely prisoners of the cultural conventions of our training, trapped, like the GA-burning OR professor living in his convex world, by the norms of our narrow fields. To combat this kind of narrowmindedness requires us all to remember that there are usually interesting nuggets of knowledge in every discipline, even those we don't full grasp or understand, but to suggest that any discipline should be "burned" is a kind of intellectual fascism that has no place in a school of any kind, let alone a major research university.

 

IlliGAL Blogging GECCO live

IlliGAL Blogging super secret steering committee met on Friday and decided to blog GECCO-2005 live. IlliGAL bloggers will roam the conference with laptops in hand and report from different workshops, tutorials, and talks live. For information on attending what promises to be the largest conference on genetic and evolutionary computation ever held see the conference website here.

 

Art, innovation, and the beauty of evolution

Dawkin's Blind Watchmaker (1986) program and the Faceprints system developed at New Mexico by Caldwell(1991) are two early examples of interactive genetic algorithms. For example, in Faceprints, the system replaces the role of a human sketch artist in evolving the faces of criminal suspects from witness recollection. Since those early efforts, an interesting spin was taking on such algorithms, the so-called genetic art. Genetic algorithms creating art based on the guidance of human evaluators. You can find an example of genetic art here.

However, what began with as genetic art also leaped into the realm of architecture. I found the application of genetic algorithms in the architecture realm fascinating. Requiring greats dosis of creativity and innovation, architects have found on genetic algorithms and idea pump that help them explore new concepts, objects, spaces, and lights---to mention a few. Manuel De Landa presented some interesting meditations about the impact of population based methods on the creative grounds of architecture. Leandro Madrazo has also been working on web-based learning environments to support collaborative learning. Even without realizing it, his work has a clear flavor of a real application of human-based genetic algorithms to the development of architectural concepts.

Sunday, February 06, 2005

 

SuperBowl XXXIX, betting, and GAs

While waiting to overeat, overcommercial, and overwatch the spectacle called the Superbowl, I was thinking about genetic algorithms and football, and a quick googlie later I found the site aiBET that uses a genetic algorithm to make football betting predictions. Unfortunately, the betting is of the round ball kind and not the olive ball of American football. On the other hand, the ROI of aiBET on the English Championship since October 2004 is -13%, so perhaps a coin toss to determine your choice Eagles v. Patriots would do just as well. Ward Systems software is being used for betting apparently, and some claim somewhat better results. Client Paul Smith claims to hit 75-80% on regular and substantial betting activity. Neuroshell predictor uses a combine of neural networks and GAs.

 

New GA/EC bloggers

Welcome to Gerulf Pedersen who has joined the rolls of IlliGAL bloggers. Howdy to Chris Donnan of babies, computers, 'n other rants. Chris posts a list of places to start reading on AI/EC subjects:

MIT Journal of Evolutionary Computation
Illinois Genetic Algorithms Laboratory (IlliGAL) Blog
IEEE Computational Intelligence Society
Edwin de Jongs Home Page
Professor Kalyanmoy Deb
MIT Journal of Machine Learning Research (JMLR)
The NeuroEvolution of Augmenting Topologies (NEAT)
E. Zitzler's PISA - A Platform and Programming Language Independent Interface for Search Algorithms.
Joshua Knowles Publications
Natalio Krasnogor Publications

Looks good to me. Thanks also to eponymouspickle for mentioning IlliGAL Blogging. Looking more carefully, the epickle is yet another blog for the ubiquitous Franz Dill. With his blog entries over at IFTF, inside the corporate firewall of major consumer products company, and now the Epickle, Franz's got his own blogorama network effect going. Although the epickle blog just got going on 29 January, the posts to date are an eclectic collection that may interest readers of this blog. I liked his links to the update on what Doug Lenat has been doing with his life and Charlene Li's blog.

Saturday, February 05, 2005

 

Action at the crossroads of disciplines

I noticed an interesting post at viralexpansion about the value of studying different disciplines:

My thesis advisor and I were talking today. She commented that sometimes students ask "Why should we study other sciences? Why can't we just study computer science?" Her response is that the more knowledge that you amass, the more likely you are to be able to advance your own field.

Think about it. Most of the major advances in any science has been from the application of models and concepts of one field to another. Take biology for example - apply some basic biological concepts to computer science; what you get are things ike "DNA Computing" and "Genetic Algorithms". Take physics and materials science - apply some basic physical characteristics of materials, apply some electromagnetic physics, and you get things like the transistor. Take that one step further and apply logic, and you get the integrated circuit.


Indeed, and Arthur Koestler in the Act of Creation coined a nice term for this kind of creativity. He called it bisociation. Genetic algorithmists will recognize bisociation as a kind of cross-disciplinary crossover, and part of the surprise in the research leading up to the publication of The Design of Innovation was realizing how fast such processing could be. Where some still think of recombinative innovation as being slow, the math shows that discovery times grow only linearly or quadratically (depending upon the problem scaling) as the number of problem attributes increases. This speed contrasts sharply with the oft heard comment that GAs are slow. Yes, badly designed GAs are slow in hard problems (see Dirk Thierens's work in the mid 90s), but when you use next-generation GAs with adequate codings, watch out. Be prepared for surprisingly good answers quickly and reliably.

 

IlliGAL Blogging welcomes new bloggerati

IlliGAL Blogging welcomes new bloggers, Hussein Abbass, Claudio Lima, Kei Ohnishi, and Robert E. Smith. Rob Smith did his MS and PhD with me when I was at Alabama. Drs. Abbass and Ohnishi had fairly recent extended visits to the IlliGAL lab, and Claudio Lima had a recent short visit and appears to be returning to us in the fall. We look forward to their posts. We also look forward to the posts of a number of contributors who for one reason or another remain blogshy.

 

Company sells stock trading GA-NN combo

Gainesville-based NeuroDimension supports a number of GA and neural-net packages. Among their offerings is their TradingSolutions package
that helps you make better trading decisions by combining traditional technical analysis with state-of-the-art artificial intelligence technologies. It has the ability to learn patterns from historical data, allowing you to create highly accurate systems that inform you when to enter and exit positions.

NeuroDimension has ties to the University of Florida's Computational Neural Engineering Lab.

Friday, February 04, 2005

 

GA system a runnerup in WSJ Innovation Awards

Nanyang Polytechnic of Singapore received mention as a runnerup in the Wall Street Journal Innovation Awards in the category of software for their GA-based system for managing manpower requirements. NYP's press release describes the system as follows:

NYP's entry, the Genetic Algorithm (GA) Based Rostering System, seeks to solve large complex rostering problems by using a dynamic gene-modelling method to overcome limitations found in traditional artificial intelligence (AI) systems. The result is the ability to deliver a high degree of accuracy with prompt response to changes. The system is currently deployed at the Singapore General Hospital, which saw the time taken to roster its 2000 nursing staff cut from several days to just 25 minutes. The system has received a patent in Singapore and patent applications being filed in the US and Australia.

Hat tip to Technology Playground for their post. In other corners of the blogosphere, Merkintöjä is bringing news of the Technology Review article to Finnish readers, and AI etc. has picked up on IFTF linking to IlliGAL Blogging.


 

A comment on Dill's blogging comment

Franz Dill's thoughtful comment on my post Why let law profs have all the fun raises key issues regarding the attraction of blogging. I take his second point first:

We have, of course, had web sites since the early 90s, but there is something fresh and interesting about weblogs ... Many people would just not visit web sites on an ongoing basis. A blog, with refreshed content has an immediacy that cannot be matched. It is, of course, content hungry, which is not always easy to feed.

Indeed, part of a blog's attraction is its ease of updating and thus its immediacy. In the terms of economics, blogging reduces the transaction costs of posting, thereby reducing the economic size of the posting unit. To some extent this is merely a continuation of what the web wrought initially in the 90s.

But there is something else at work. The transaction costs of posting to a threaded discussion are comparable to those of posting to a blog, but I find blogging much more attractive than threaded discussions, which I rarely frequent. Threaded discussions are largely free-for-all forums dominated by the principle of the survival of the loudest (or survival of the person with most time on his/her hands). Blogs, on the other hand, allow the publisher to post views and receive comments, yet remain in control of the publication process. The asymmetry of the blogger/commentator relationship in blogging is essential to its growing popularity.

This point can be carried over into the first part of Dill's comment in which he makes a good point regarding public/private blogging:
There is a part of it that is not public, behind corporate firewalls, that continues the discussion.
Indeed, blogging and wikis are being adopted by progressive companies as part of internal communications networks. The use of wikis vs. blogs internally may be driven by the same symmetry/asymmetry conditions noted in the public blogosphere/discussion arenas. How all this will shake out is unclear, but efficiency of posting is a driver behind it all, and it will be interesting to follow how wikis/blogs will be integrated into organizational practice along with the rest of the discourse engine we now all take for granted (email, IM, chat, etc.).

 

GECCO 2005, learning classifier systems, and other genetics-based machine learning

This year I have the honor of being the chair of the GECCO track formerly known as learning classifier systems. For the last two years, I had the feeling that it was the moment to enlarge the scope of the track. Una-May agreed that this GECCO was the right one to give it a shoot.

Since the inception of learning classifier systems (LCS) by John Holland, learning paradigms driven by genetic algorithms (GA) have shown their competence on a broad spectrum of fields and applications. In a broader spectrum, genetics-based machine learning (GBML) systems have successfully tackled the creation of cognitive models, classification and prediction systems, and anticipatory behavior---to mention a few. Recently, GBML has been experiencing an important renaissance thanks to two key factors: (1) the new GA theoretical achievements have provided a better understanding of the underlying complex mechanisms used, and (2) the successful applications of such systems to real-world problems such as data mining.

I am very pleased to announce that instead of the 13 paper of GECCO 2004, we received 25 submissions to the track (We almost doubled the number of submission!). We have been able to maintain the core LCS group, and extend our reach to new interesting research in GBML. Una-May and I are very happy that the enlarge of the track scope was welcome by the research community. We also were able to competently deal with the uncertainty of the volume of submissions that a new track---such as the one I proposed to Una-May---would attract. Moreover, the track showed to be prepared to assume such volume increase.

Thursday, February 03, 2005

 

Epistasis blog picks up BioGEC Workshop

Jason Moore of epistasis blog put out by the Dartmouth Computational Genetics Laboratory has posted an announcement for the BioGEC workshop of GECCO-2005:
The fourth annual workshop on Biological Applications of Genetic and Evolutionary Computation (BioGEC), organized in connection with the 2005 Genetic and Evolutionary Computation Conference (GECCO-2005) in Washington DC, USA, is intended to explore and critically evaluate the application of GEC to biological problems. Specifically, the goal is to bring biologists and computer scientists together to foster an exchange of ideas that will yield emergent properties that will move the field forward in unpredictable ways.In order to facilitate interaction and discussion, the workshop invites papers in the form of commentaries, essays, perspectives, surveys, tutorials, and reviews that focus on ideas for discussion. Details on the call for papers can be found here.

Dozens of other tutorials and workshops are included in the price of admission. Check out the main GECCO website here.

 

GA-based school scheduler available

Freshmeat reports that a school scheduling program based on GAs is available. The procedure, called tablix,can be run on a single machine or on a loose cluster:
Tablix is a high school timetable generator. It uses a coarse-grained parallel genetic algorithm to construct sensible timetables from XML-formated school information files. It can run on a single host as well as on a heterogenous parallel virtual machine using PVM. Its features include a number of possible restrictions for teachers or classes, HTML-formatted output, and configurable genetic parameters.
The developer of the application is Tomaz Solc.

Wednesday, February 02, 2005

 

Why let law profs have all the fun?

Like many Americans, I became hooked on the blogosphere during the 2004 Presidential election cycle. In my own case, my daily fix consisted of reading HughHewitt, Instapundit, Polipundit, Captainsquartersblog, and Powerlineblog. I almost OD'd on news/commentary aggregators and electoral vote trackers such as realclearpolitics and electoral-vote. As I read through many of the commentary blogs, I came to realize that many of the pajamahadeen were lawyers, and many of those taught in law schools.

The blogs during the election were an impressive display. Lone critics connected from their laptops to other citizens through the magic of the modern web, holding candidates, the mainstream media (MSM), and each other accountable for inaccuracy, spin, and flat-out lies. It also looked like great fun: freelance writers and researchers, writing and researching, largely for fun, not profit, motivated by the leverage of influencing their countrymen. During the election, I told my wife that "I can do that," but to take on a blog requires discipline, and I wasn't sure what to blog about.

I resisted the temptation for as long as I could, and as I sat thinking during Christmas break about upgrading my laboratory's website (IlliGAL) I came to know exactly what I had to do. I needed to get my lab blogging on genetic algorithms, and we needed to make the blog the centerpiece of the site. To this point, we've only been able to get up on Blogger, but eventually we plan to host our own blog using Wordpress, and after we are hosting our own blog, we will integrate the blog into the home page as part of major overhaul of the website.

In so doing, we believe we will continue to get the 500 or so visitors who come to IlliGAL looking for tech reports and code each day, but we also hope to inform, teach, interact, and link with the community of genetic algorithms and evolutionary computation as well as newcomers who want know more about GAs, how they work, and how they can be used.

My short sojourn through the blogosphere has been a blast, first as a reader and now as a contributor. The immediacy of publishing at a push a button, beats the heck out of the academic publication cycle with its tedious submission, review, revision, and more review. The informality and the freedom of being able to take a subject where you want to because you want to is liberating in a way that is hard to describe. So what are you waiting for? If you've said, "I can do that," you're right, you can. Why not hop on the web, take five minutes, signup for a Blogger account, and start blogging? You'll find out what the lawyerbloggers and all the rest found out some time ago, and even if you don't reach thousands, you'll get what you're thinking into the written word, and maybe, just maybe, an interested person will read it. And when you get that first post up and running, why not drop us line and give us (www.illigal.blogspot.com) a link?

Tuesday, February 01, 2005

 

Little models, big results

I am in my 25th year as a genetic algorithmist. In September 1980, I sat in John Holland's course, Introduction to Adaptive Systems, wondering what all the genetics stuff had to do with adaptive systems. Shortly thereafter, I proposed applying genetic algorithms to gas pipeline optimization and rule learning, did so, and went on to take my first teaching job at the University of Alabama. Although I had succeeded in applying GAs in my problem domain, my doing so left me with as many questions as I answered. And although I had used GAs to help solve interesting engineering problems, I was unhappy with GAs--and my own lack of understanding of GAs--as engineered objects.

That experience on my thesis left me with a thirst to better understand genetic algorithms, how they work, and how to make them work better. And that thirst led me to try difference equations, Markov chains, transform methods, anything that I could get my hands on, to help me do a better job in GA analysis and design. At first, my studies took me toward more esoteric and sophisticated tools, but then my training in fluid mechanics kicked (somewhere between my leaving Alabama and coming to Illinois), and I turned to the methodology of little models, including facetwise models, and patchquilt integration using dimensional analysis.

My 2002 book, The Design of Innovation, tells the long version of this story, but the basic idea of little modeling is to construct models for various effects in isolation (selection alone, crossover alone, mutation alone), and use dimensional analysis to create models for complex phenomena from pairs of simpler models. For example, we might create a model for convergence time under selection alone, combine this with a model for mixing under crossover alone, and consider the pairwise effect as a dimensionless ratio of the two times. This approach, though algebraically simple, is remarkably powerful in helping sort out experimental results and organize a researcher's thinking.

More recently, Ali Yassine, Tian-Li Yu, and I have carried the little modeling approach over to organizational theory here. We are still exploring the possibilities for this kind of study, but we believe the approach that has worked so well for GAs will help shine light on some of the complexity of large human organizations.

Interestingly, the approach from the modeling middle is almost universally criticized by both theoreticians (who believe it to be too simplistic) and practitioners (who find theory of any sort abhorrent). Aristotle was rather partial to the golden mean, and I find this middling type of analysis just the ticket, especially when approaching a poorly understood phenomenon without a well trodden body of accepted theory. Little models give great bang for the buck, and I urge every serious genetic algorithmist on the planet to become acquainted with the array of mixing, schema theorem, population-sizing, and convergence time models IlliGAL members and others have used to understand and design modern GAs. Without some analytical guidance, our understanding would have been too meager, but with more sophisticated models our ability to design would have been non-existent. The right balance of accuracy and model simplicity has been crucial to the advance of our art.

This page is powered by Blogger. Isn't yours?