Complex Intelligent Systems

Documentation for OAT, The Optimization Algorithm Toolkit

2007-12-21T09:53:00.001+11:00

For those not familiar, I run a little project called the Optimization Algorithm Toolkit (OAT) that provides a framework for exploration and experimentation with a suite of standard Computational Intelligence algorithms and benchmark problem instances. This week I have written and released some documentation for the platform, as follows:

OAT: The Optimization Algorithm Toolkit: Provides an overview of the OAT software distribution, a summary of the vision for OAT and its contribution to Computational Intelligence, and the future for the project.
OAT: A Quick Start Guide: A rudimentary guide to quickly and easily begin using and or developing for the OAT with step-by-step instructions and relevant links.
OAT HowTo: High-level Domain, Problem, and Algorithm Implementation: An overview of how to develop for the platform including creating a new problem domain, new problem instances, and new optimization algorithm strategies.

enjoy!

Jase.

Blind watch maker

2007-10-31T09:28:00.001+11:00

I found this great demonstration of a Genetic Algorithm on YouTube. The blind watch maker problem rests on the idea is that if you have all of the components required for a watch laid out in front of you, can you ever reconstruct it by using evolution alone?

Intelligence, Metaheuristics, and Orange

2007-10-13T08:34:00.000+10:00

A post on a Metaheuristics Taxonomy by nojhan, the final image is very information dense. A rant on intelligence at the singularity institute. Also, I came across an open source data mining package called orange, cheers Alex. Orange looks like WEKA, although perhaps more user friendly (from the screenshots).

Stupid filter

2007-10-11T10:35:00.001+10:00

Sounds strange, but a group of researchers are starting to build a web filter to eliminate stupid content from the Internet. If I understand correctly they will target the linguistics of web content and also capture user feedback to filter bad quality content in an effort to bring the Internet back to its intellectual roots. The project is looking at using similar technology to that used in spam filtering which seems like a good starting point to me.

John Conner?

2007-10-09T09:59:00.000+10:00

Found this interesting post on a self-aware robot. I'm not sure whether we should be worried about the end of humanity though as the robot is simply able to determine whether it is looking at itself in a mirror, it hasn't started contemplating its existence... yet!

Evolve rather than invent, and a science oath

2007-10-09T07:39:00.000+10:00

Don’t invent, evolve on the economist, cheers greythumb. Also, an official scientists hippocratic oath, proposed an currently being used in the UK (also on the guardian here and here), cheers to the science show.

Example of AI Projects in Industry

2007-10-07T09:10:00.000+10:00

A post on examples of AI projects in the industry "Artificial Intelligence problems in Industry (things I’ve worked on)", cheers AIgameDev.

Evolving Images

2007-10-02T12:20:00.000+10:00

MutatingPictures - an interesting website to evolve random shapes into images of faces. Another site with more features is picbreeder. Great concept application of crowd sourcing a selection function.

The three schools of the singularity

2007-10-01T11:58:00.001+10:00

The three schools of the singularity discussed in the latest post by the singularity institute, also discussed in the podcast at the singularity summit by Eliezer Yudkowsky in a talk titled Introducing the "Singularity": Three Major Schools of Thought.

Algorithms are cool!

2007-09-25T14:44:00.000+10:00

A nice heads-up post on Slashdot titled " The Gradual Public Awareness of the Might of Algorithms", that references "King Algorithm: An Oracle for Our Time, Part Man, Part Machine" in the NYT that in turn references the Google Image Labeler and Amazons Mechanical Turk (two sites/idea I think a lot of), and "Algorithms: Business by Numbers" in the economist that references TSP and other optimization algorithms as well as another article titled "Big Sums: Of greed and ants" on ACO.

Singularity Summit Audio, Gerry's Thesis Online

2007-09-24T10:31:00.000+10:00

The audio for the Singularity Summit 2007 is available (finally). A great post on Coding Horror titled "Everything is fast for small n", a compsci lesson that is not heeded enough in my (compintell) field... Also, I found Gerry's thesis is online (well done again Gerry).

Large-Scale Heterogeneous Self-Organizing Swarms

2007-09-21T14:22:00.000+10:00

I came across an interesting project on manipulating large self-organizing swarms of agents by Hiroki Sayama (cheers Complexity Digest). I particularly like the aspect of the software that allows blending of configurations, allowing the user to select and discriminate parameters based on exhibited behaviors.

Hiroki provides pre-print of a paper describing the work titled "Decentralized control and interactive design methods for large-scale heterogeneous self-organizing swarms"(2007).

Optimized Machine Learning and Bots

2007-09-17T20:50:00.000+10:00

A great post on the machine learning blog about optimizing the implementation of machine learning algorithms. A review on AIGameDev of a relatively new IDE for creating bots for the game Unreal Tournament called Pogamut 2.

Artificial Intelligence is cool again!

2007-09-14T09:39:00.000+10:00

Apparently AI is OK again (cheers intelligent machines). AI exploiting virtual worlds as a medium to learn from humans (cheers Machines Like Us).
A discussion of the book "To Mock a Mockingbird and Other Logic Puzzles" on Coding Horror, interesting because its full of combinatorial logic problems we use as benchmarks in computational intelligence (the book on google books).

Evaluating the success of a predictive system

2007-08-20T08:16:00.001+10:00

Another great post from the Machine Learning blog on the choice of metrics for evaluating machine learning.

Hard Problems in AI

2007-08-14T12:00:00.000+10:00

A quick post on The most difficult AI problem? and a follow-up Why Genetic Programming cannot solve the most important AI problem, cheers to Intelligent Machines.

A.I. Gone Awry

2007-08-05T10:54:00.000+10:00

A feature article on Skeptic titled "A.I. Gone Awry - The Futile Quest for Artificial Intelligence", worth a read.

Evolutionary Algorithms in Design

2007-07-29T16:33:00.000+10:00

An article on NewScientistTech titled "Evolutionary algorithms now surpass human designers" that generally discusses the design capabilities of EA's with examples, specifically those from the GECCO 2007 Human Competitive Results Competition (so called 'the humies'). Reminds me of all the cool examples on TalkOrigins "Genetic Algorithms and Evolutionary Computation". I'm happy whenever this stuff gets press :)

Motivating Research

2007-07-23T08:07:00.001+10:00

A rant and comments on motivating (or not) research in papers, from the Machine Learning blog.

Problem Difficulty and Interview with Norvig

2007-07-18T07:46:00.000+10:00

A brief post on an software engineers perspective of problem difficulty, Cheers Intelligent Machines.
An interview with Peter Norvig on Technology Review (that guy who wrote that book), cheers Geeking with Greg.

General AI and Selection of the Likeliest

2007-07-09T07:42:00.000+10:00

An article on the evolution and the second law of thermodynamics 'Selection of the Likeliest' (2007), cheers GreyThumb. A video of a public lecture at Google on 'Artificial General Intelligence' (2007), cheers AI-Depot.

The Moser Function

2007-07-05T08:15:00.000+10:00

The Moser Function: The application of the theory of 'Suspension of Disbelief' to ones own research project ( as proposed by Irene Moser) in order to make continual progress on the project, and to ultimately produce a dissertation. Manipulation of the Moser function may occur through various means not limited to discussion of the base-motivation(s) and or resultant-impact(s) of a research project with colleagues. The effect of which may negatively impact project productivity (in some extreme cases for extended periods of time), until such time that the new variables can be suitably integrated (see Moser Integration).

Swarm Behavior

2007-07-04T07:36:00.000+10:00

An article on Swarm Behavior on National Geographic (Cheers Dan, Mind Hacks, and Intelligent Machines)

Online Learning

2007-07-03T07:53:00.000+10:00

A nice summary of the different ways to think about online learning
An article about AI being lost in the woods

What AI can achieve

2007-07-02T08:15:00.000+10:00

A post on Intelligent Machines titled "What artificial intelligence can achieve".
Some definitions of intelligence from Machines Like Us.

Evolutions Beauty and Problems

2007-06-22T08:34:00.000+10:00

An anecdote about the power of natural selection as a design process, and a follow up on the processes inability to ensure perfect design.
Also, on ROC and AUC measures in classification.

The Traveling Salesman Problem: A Computational Study

2007-06-06T07:50:00.000+10:00

A new book on TSP, "The Traveling Salesman Problem: A Computational Study" (2006), and a review on the OR blog. Google books (no preview), on Amazon (with searchable content).

Creepy robot

2007-06-04T16:51:00.000+10:00

Possibly the creepiest robot I have ever seen. Those Japanese sure know how to weird everybody out. Another case of great science, terrible marketing!

Why most published research findings are false

2007-05-23T07:33:00.000+10:00

A paper titled "Why Most Published Research Findings Are False" (2005) which discusses medical research, although many of the points ring true for many fields, cheers seed. Reminds me of this old chestnut "Is the scientific paper a fraud ?" (1963) by Medawar.
Also, a ppt presentation on Goldberg (and other's) billion bit optimization, titled "Billion bits or bust".

jase.

Conversation between two computers

2007-05-17T14:04:00.000+10:00

I found this interesting article which is a transcript of a conversation between two chat bots. My favourite line is:

ALICE: Are you alive?
Jabberwacky: Perhaps.
A: Why the uncertain tone?
J: Everything is uncertain except for five facts.
A: The whole universe?
J: And we both might just be some ones and zeros in the computer memory.

Jabberwacky knows what it's about!

Heuristic definition

2007-05-03T08:53:00.000+10:00

Found a nice blog post with a great description of what a heuristic is (link).

The rest of the article is also good for those of us who like to procrastinate rather than get our thesis written!!!

Hive Mind and Web2.0

2007-04-26T08:25:00.000+10:00

A post on bees and the hive mind (by a beekeeper). How these ideas may relate to the social web (web 2.0). Also, a new book on parameter setting in evolutionary algorithms, cheers MEDAL.

Game AI, Science in Silicon, and Ants for Aircraft

2007-04-21T08:07:00.000+10:00

An article in the guardian about intelligent game artificial intelligence (go bottom up), cheers to Togelus. An awesome video about doing science in silicon, (technically light but very pretty!) cheers Seed. The use of ant algorithms in aircraft scheduling, cheers GreyThumb.

Spock 'Entity Resolution' Challenge

2007-04-19T18:29:00.000+10:00

Spock have an entity resolution machine learning challenge (like the NetflixPrize) with a $50K USD prize. Cheers for the heads up to Machine Learning Theory and O'Reilly Radar. See entity resolution on Wikipedia, on google scholar, and on google.

More Second (A)Life

2007-04-09T09:17:00.000+10:00

Virtual ants in second life, and flocking fish in second life.
Also a paper on exploration/exploitation with human decision makers, titled "Should I stay or should I go? How the human brain manages the trade-off between exploitation and exploration" (2007).

ALife in Second Life, Evolving Robots

2007-03-14T11:57:00.000+11:00

An article on ALife in Second Life, fleshing out the virtual work with an artificial ecosystem. I like this.
Evolving robots at the TED conference. article, video of the robots evolving (reminds me of Karl Sims work), the guy.

Realistic CG Image

2007-03-13T13:26:00.000+11:00

Found this link to one of the most realistic CG images I have ever seen. Very nice stuff, another one can be found here.

Crysis Game Engine

2007-03-09T10:13:00.000+11:00

Just found a link (official site) to this amazing game engine with some pretty impressive physics and graphics rendering. As far as the AI goes the most impressive information I read was the collaborative computer players. The designers have combined individual AI as well as a group AI for each computer player so that they are able to coordinate movements and tactics for more realistic combat strategies. This stuff kind of makes me wish I had picked a different topic for my thesis, but then I guess it's not all beer and skittles!

A cool walking robot and life as a hack

2007-03-07T16:57:00.000+11:00

Awesome video of a dynamically stabilizing robot learning how to walk - seriously, you need to see this! Cheers to Paul Graham.
A post by Kevin Kelly on every organism being a hack. Talks about evolutionary arms races, specifically in the context to software protection and anti-virus software. An interesting read.

Machine Learning Techniques: Right and Wrong

2007-03-05T09:20:00.000+11:00

There is a cool post at the machine learning blog on what is right and what is wrong with a number of popular machine learning techniques. I love the idea of promoting such discussions! Optimization anyone?

Evolution of Cooperation

2007-02-26T09:01:00.000+11:00

Post titled "Evolution of Signaling in Artificial Agents" on the Panda's Thumb (PT) about evolving cooperation in robots which references a piece at The Loom titled "Evolving Robotspeak". Basically the work is about evolving neural nets in robots with light and infrared sensors and engendering communication through competition for food. The source paper is titled "Evolving conditions for the emergence of communication in robots" (2007).
The original PT article also highlights an article last year on the biological evolution of cooperation titled "The Evolution of Cooperation: Hawks, Doves, Ravens and Starlings", which references an interesting paper in nature on evolving cooperation with neural nets in simple 2D landscapes titled "Evolution of cooperative strategies from first principles" (2006).

Fun stuff to read about, enjoy!

Tips, Vision, and a Google class

2007-02-22T09:39:00.000+11:00

A list of tips for computer science graduate students. The 'writing your thesis' one was short and sweet, the rest didn't really interest me.
A somewhat interesting biologically inspired vision system.
A new CS class on google tech by a guy from Google.

Google on AI

2007-02-19T18:26:00.000+11:00

Via a KurzweilAI post, there is a video on cnet with Larry Page of Google talking about artificial intelligence and his thoughts that is a problem of computation rather than that of smart algorithms.

A billion-bits, Optimization, and Long Term Predictions

2007-02-19T09:23:00.000+11:00

The IlliGAL have released a technical report version of their paper on using a compact GA (cGA) on a billion-bit optimization titled "Towards a billion bit optimization via efficient genetic algorithms" (2007). The 'Good Math, Bad Math' blog have a brief on optimization with a geometric example and a note on linear and dynamic programming. And finally, there is an interesting podcast (from the long now seminar series) by Philip Tetlock titled "Why Foxes Are Better Forecasters Than Hedgehogs" about his work in an 18 year study on measuring and evaluating peoples forecasting abilities.

The Machine

2007-02-13T12:19:00.000+11:00

Cool video on web 2.0. Short, sweet and few weeks old, but worth a watch.

In Browser Reference Scraping

2007-02-08T08:59:00.000+11:00

Yeah, I'm totally sick of control-c control-v of reference information from websites. There is a cool firefox extension for scraping bibliographic information from sites called Zotero. Seems to work pretty good for me, although it was unable to scrape SpringerLink and DBLP. Google Scholar, IEEE Explore and Amazon worked just fine. Cheers to the MEDAL Blog for the heads up.

Machine Learning and Stats

2007-02-05T09:21:00.000+11:00

An interesting post on Thoughts regarding "Is machine learning different from statistics?". Also a review on Turing Machines with a cool little code example.

Interestingness in GA's and Parallel Machine Learning

2007-01-29T09:41:00.000+11:00

Via the IlliGAL blog, this interesting application of GA's and flickr "interestingness" as a helping hand in the objective function.
A small note on parallel machine learning problems. I like the potential for using MapReduce suggested in the discussion.

Many Eyes

2007-01-24T09:45:00.000+11:00

IBM Many Eyes project for collaborating on interpreting data via visualizations! Great Idea!
Thanks O'Reilly Radar.

Dr Gerard

2007-01-09T11:06:00.000+11:00

For our Gerry, Christmas came a week early this year when he was given the review of his thesis - a much better one than he expected and probably the one he deserved. With all the fretting behind him, he is now faced with the predicament of finding new interesting pastimes to fill the abundance of spare time suddenly available..

Naturally, this called for a reasonable synapses reset at the local pub. With all the dusty thesis stuff washed out of his neurons and a new year on his hands, our Gerry is poised to tackle a brilliant career in chemistry whenever he is not busy chasing snakes off riverbanks on his fishing tours.

Google Patent Search and GA's

2006-12-15T13:55:00.000+11:00

I just checked out the the Google Patent Search, and searched for Genetic Algorithms. Yep, there are patents out on them (see here in particular, as well as here and here). WTF? I don't claim to understand patents or their implications, but this does not seem cool to me, what else has a patent on it that we use everyday? Illigal blog also has something on a new GA-based patent that has been granted.

jase.

2006 e-Science and Grid-Computing Conference - Amsterdam

2006-12-11T16:47:00.000+11:00

So what is e-Science? Presumably attending an entire conference on the subject would be enough to answer that, but unfortunately nobody was able to provide me with a robust definition. So I guess I'll answer with my own interpretation. e-Science seems to be a buzzword for inter-disciplinary science which involves computers in some form.

The plenary talks were good, although some seemed to drag a little bit. The highlight was a talk on the first day by the chairman of the Netherlands Organisation for Scientific Research, Prof. P. Nijkamp. Although specifically targeted at the conference audience his talk was easily applicable to any field of research in describing the dangers of overstating scientific results. He provided case-studies of technologies which had promised to solve the worlds problems which years later had turned out to be far from these claims. He talked about how technology firms talk about the paperless office, yet we are consuming more paper than ever before. Well rehearsed and well delivered it was an exceptional presentation.

Tim gave a somewhat jet-lagged performance with his presentation of Dynamic Problems and Nature Inspired Metaheuristics. Pretty good considering the time-zone he was operating in! My presentation was after lunch and went quite well. Some useful comments by colleagues in the following days provided me with some good material for future work.

The conference dinner was very nice taking place at the Westindisch Huis, quite special indeed. Overall I must say the conference was a very enjoyable experience of which I am very thankful to have been involved in.

Mechanical Turk

2006-12-01T19:07:00.000+11:00

There is a post on O'Reilly Radar on an amazon service called Mechanical Turk. Basically it provides a service for getting lots of humans to work on problems that machines find difficult. I've had this idea in my own research a number of times, and it is great that one of the 'big boys' is trying it out. It seems it is targeted at getting users to work on the problems (by paying them in micro-payments) - great idea!

On Using Randomness in Machine Learning

2006-11-23T16:42:00.000+11:00

Explicit Randomization in Learning algorithms

e-Science and Grid Computing Conference Scholarship

2006-11-16T15:42:00.000+11:00

I have been fortunate enough to recieve a travel scholarship from the IEEE's Technical Committee on Scalable Computing (TCSC) to attend the e-Science and Grid Computing conference in Amsterdam in early December 2006. According to the TCSC a listing of all students who recieved one of the scholarships will be placed on the TCSC's website soon.

Geeking with Greg: AI and "Web 3.0"

2006-11-13T10:41:00.000+11:00

Geeking with Greg: AI and "Web 3.0"

Exemplar Programming

2006-10-24T10:05:00.000+10:00

An interesting take on machine learning over at the machine learning theory blog:

Exemplar Programming

Here's a snip:

Machine learning can be thought of as exemplar programming. Exemplar programming is creating examples of a (input,output) pairs which are used by an algorithm to predict a function from input to output.

[...]

Exemplar programming is a viewpoint of machine learning which (mostly) ignores statistics, prior information, and the possibility of overfitting. That’s a great deal to ignore, but there are gains as well.

jase.

NetflixPrize

2006-10-13T09:12:00.000+10:00

Netflix the DVD rental company recently announced their NetflixPrize in which they will give away $1 million dollars for an algorithm that can out-perform their recommendation approach Cinematch by 10%. Given that this competition has caused a little bit of a stir in our research group I thought I would put this post together to capture a number of useful resources.

NetflixPrize forum, FAQ, Rules, Leaderboard
Wikipedia references on Collaborative Filtering (CF) and Recommendation Systems
A video talk by a Netflix engineer on their Cinematch algorithm
A collection of links about Cinematch
Collections of papers on CF here, here, and here
Research groups working on CF here

There are many many papers out there on collaborative filtering and recommendation systems. Here are a few good review and seminal CF works:

If/when you find any more useful resources, add them to the comments of this post!

jase.

Niching for Ant Colony Optimization

2006-09-25T15:19:00.000+10:00

After what has been a fairly uphill battle I have managed to get a research paper accepted into a workshop at the 2nd International Conference on e-Science and Grid Computing. The paper is titled 'Niching applied to Population-based Ant Colony Optimization'. The research applies two diversity preservation techniques from Evolutionary Computation (fitness sharing & crowding) to the Ant Colony Optimization metaheuristic (specifically population-based ant colony optimization). The purpose of maintaining 'niches' of like solutions is to ensure convergence of the ACO algorithm to multiple areas of the search space.

The paper presents a proof-of-concept with the algorithms presented alongside some very preliminary qualitative analysis. The techniques presented in the paper form the core of my PhD thesis, and as such I have already begun to apply them to more complex problems with far more rigorous analysis. Expect another paper soon on one of these algorithms applied to a far more complex suite of problems.

A larger technical report as well as demonstration software with included source code is available.

Interesting Links

2006-09-25T15:08:00.000+10:00

I came across an interesting blog on metaheuristics by Johann Dréo called "Dreaming of Metaheuristsics". It is new so there is not much content yet, although there are some interesting posts on swarm related research in particular the one on ACO authorship (Dan!).

I also came across some interesting work on evolving flying creatures with path following behaviour in a 3D environment, includes a brief and link to the paper "Evolving Flying Creatures with Path Following Behaviors" (2006?). There is further information and publications about this work on Yoon Sik Shim’s homepage.

Finally I have uploaded new versions of the function optimisation and combinatorial optimisation software, so check them out. The major additions to both are different versions of Population-based ACO approaches thanks to Dan.

jase.

Master Hans

2006-09-18T11:52:00.000+10:00

Congratulations to our Hans who on Friday submitted his Masters thesis! For this momentous occasion, we went down the on campus bar to celebrate and inebriate. See below for photos of the proud father and the group.

Well done Hans!!!

P.S. Thanks go to Irene for capturing the moment.

Hawaii 5.0

2006-08-17T09:56:00.000+10:00

Dan decreed Wednesday 16 August 2006 as Hawaiian Shirt Day, and after some judicious Op Shop shopping several of us procured shirts of varying degrees of brightness and... er... taste. From left to right: me, Dan, Nigel and Jason.

Nigel's hair was unrelated to the theme of the day, and luckily didn't clash at all *cough cough* with his shirt. Nice cup btw, too.

The start of a new tradition? Time will tell.

P.S. I will eventually post something about research (like the ANTS2006 conference coming up), just as soon as deal with all the work I've got. *sigh*

2006-08-15T19:56:00.000+10:00

The Dynamic Aircraft Landing Problem and Combinatorial Complexity

Beasley & al. have published a series of aircraft landing problems on the OR library and subsequently solved them in a static and dynamic context. The static case is defined as solving the problem as a single instance by showing the solver the complete sequence of aircrafts and their landing schemes (earliest and latest landing times), whereas the dynamic case presents aircraft to the solver according to their appearance times and withdraws them from the items to optimise within freeze time of their allocated landing times.

All aircraft have target landing times. Landing every aircraft on target would lead to a perfect solution of 0 cost. Penalties apply for landing early (before target) and for landing late (after target).

Every pair of aircraft landing one after the other has to observe a separation time. Separation times vary according to the sizes of both planes involved.

The aircraft landing problem is considered a combinatorial optimisation problem. Some authors solve them with GAs, other with special-purpose deterministic solvers.

According to first intuition, solving this problem in a dynamic context adds the challenge of adaptation to a changing environment. A closer look at the example problems from the library, however, convinced me of the contrary. Take, for instance, airland7:

The yellow entries are the time lines of aircraft that have already landed. The blue dots are target times. The yellow dots are actual landing times according to a deterministic schedule which starts at the target time of the first plane and then assigns landing times strictly according to separation times. It shows, however, that there is, on average, just one or two aircraft being processed by the solver. Is this combinatorial optimisation?

The objective function says, minimise penalty. If there are two aircraft, there is the task of juggling the penalties of the two planes against each other – given the constraint of the separation times of the planes that have landed (and the separation time between the two planes still to be landed). There is the question of maybe landing the aircraft early as a precaution, in case new aircraft come in soon. This is a strategic decision problem, possibly a timeseries prediction problem, or just a guessing game.

It is self-evident, and the authors of dynamic aircraft landing papers usually point this out, that the problem instance in the dynamic case is quite different from the static (complete) instance. The solver sees a sequence of problems, none of which is identical with the problem as a whole. Nonetheless the best outcome of a static solving attempt is often mentioned when results are stated – as if the “static” result could or should be achieved by the solver in a dynamic trial. This is not possible – or is it?

The airland1 instance has only 10 planes, most of which are visible to the solver at the same time. Some attempts report a result within 1% of the best-known result for the complete (static) problem. Which prompts the question: Is this problem trivial in that the combinatorial conundrum is only 7 items long? Is it actually easier for the solver to find good solutions to the complete problem because part of the components have been “blotted out” for the time being?

This seems more likely if there is a limit to the range of useful permutation swaps upstream and downstream. The number of potentially useful permutations seems limited to a few in either direction (if anyone comes up with a metric, I would be grateful). I cannot see a great complexity in this problem if the number of potentially useful permutations is limited.

The constraint given by the separation times “alignes” landing times of planes in tight sequences like pearls on a string; the last plane with similar target time will push all the previous planes of the same cluster towards an earlier landing time. All there is to do is determine the landing time of the first plane in the cluster such that the early penalties of the cluster equal the late penalties. If all clusters are optimised in this way, it should become apparent whether the predefined clusters are indeed disjoint – or overlap after the optimisation of each pair of clusters.

It would also seem that there could be a rather large number of near-optimal solutions. It is also conceivable, that a larger proportion of random moves could make up for lack of information in a dynamic case, producing some accidental good results. However, in a real situation, the sequence only occurs once. If we allow for a series of trial runs, as we would with a stochastic solver, we would want to indicate how many of the solutions produced were feasible and what variation we observed.

Factors that might increase the complexity of the problem are the number of runways, differences in separation times and differences in penalties and the number of aircraft in need of a landing time. Any other ideas? Comments on the nature of this beast?

Ant Inspired Computation in 1988

2006-08-14T16:32:00.000+10:00

Late last year I chanced upon the title of a 1988 paper by Moyson and Manderick: The Collective Behaviour of Ants: An Example of Self-Organization in Massive Parallelism. Recently I was able to get an electronic copy.

The paper presents an argument for the use of biological ant colonies as an inspiration for parallel problem solving. The paper discusses the importance of randomness in decision making in conjunction with a chemical trail (pheromone) to direct the ants towards a food source or a nest. The emergent effect of trail formation between food and nest which results from simple local interactions is shown to be of great importance since it can be shown to occur without the specific requirement for a path between food and nest, i.e. there is no reward or cost function associated with forming a trail, it just occurs through the definition of four behaviours (rules).

Each artificial ‘ant’ moves about a grid according to four simple rules. Each ant first checks whether it has found food. If so it reverses direction and starts laying pheromone, looking for more pheromone. If no food has been found the ant checks for the nest and if it is encountered the ant reverses direction and looks for pheromone. If the ant found neither food nor pheromone nor nest it travels in a random way, left, forward or right. If a pheromone is encountered its new direction is determined by this pheromone in any of the three directions: left, forward or right.

The researchers found that these simple rules were enough to allow the ants to create paths between multiple food sources and the nest without an inbuilt requirement for the ants to build a path between a nest and food.

The paper introduces several key concepts taken from biology and replicated in an artificial simulation:

Self-organisation without the requirement for centralised control.
Use of randomness in conjunction with directedness in the form of an artificial pheromone to guide decision making.
Emergent effects (path linking) occurring in the absence of a cost function.
The requirement for a critical mass of artificial ants before emergent effects are observed.

So what? Well the paper was published in early 1988, and references Probabilistic Behaviour of Ants: A Strategy of Errors. The same paper referenced by the seminal work of Dorigo, Maniezzo and Colorni on Ant System, three years later. Whereas the later paper has been referenced by almost every major work in the field to date (57 according to citeseer), Moyson and Manderick’s paper has received only one citation by Koza in a non-ant-inspired computation paper. As Prof. Julius Sumner Miller would say “Why is it so?”

Sartorial Sarcasm at the CITR Research Briefing Day

2006-08-06T22:08:00.000+10:00

Universities seem to like combining water with oil, chalk with cheese, comedy with Adam Sandler. At the start of this year our Faculty formed a super research Centre combining seven different research groups and last week they decided it was time we all got together to find out what we all do, and how we can work together to produce bigger and better research "outcomes" (OK, so maybe they didn't use that word, but they were thinking it!).

What could be more boring than a full-day "briefing" on what other people who research very different things to yourself do? What indeed... well, to make things a bit more interesting, Tim and I undertook a mutual dare to smarten things up a little by wearing (real) bow ties. (btw, mine is actually dark green, not black, which stayed in the wardrobe at home.)

Anyway, this little bit of sartorial silliness has now spawned themed days, which we'll try to get as many involved in as possible. The next one is Hawaiian Shirt Day, in case you were wondering (thanks Dan).

James.

Why model evolution as search

2006-08-03T10:18:00.000+10:00

There is a good layman's explanation on Good Math, Bad Math as to why to model evolution as a search process.

Imagining the 10th Dimension

2006-08-02T16:33:00.000+10:00

I came across this awesome flash thing that explains the ten dimensions of string theory. It's for the layman, and goes for a few minutes. Totally worth watching. The 9th dimension is totally lame :)

Hello world, from Jason

2006-08-02T15:55:00.000+10:00

Hey, what a great idea Dan! Can't wait to start spamming this thing with AI stuff.

Don't forget to check my personal PhD blog called Pensive Pondering, I have a new post up there about collaborative drawing systems. Also, don't forget to check my awesome personal homepage for heaps of cool applets and information on my research.

If you want something random and geeky to read, check out Topological Quantum Computation. There is some course notes on it here if you want more.

- Jason

Welcome

2006-08-02T15:40:00.000+10:00

The Complex Intelligent Systems (CIS) Group was until recently called the Centre for Intelligent Systems and Complex Processes (CISCP). The group was founded in 1992 and has been involved primarily with research in the fields of artificial neural networks, evolutionary algorithms, collective intelligence algorithms, data visualization, brain dynamics and brain modelling.

We are located within the Centre for Information Technology Research, Faculty of Information and Communication Technology, Swinburne University of Technology, Hawthorn, VIC, Australia. (So many Technologies!)

As a group we attend most major conferences in these fields and also contribute to world leading journals in the above research areas. The group's size varies and at time of writing we comprise about 10-15 researchers and affiliates.

In the near future this blog will contain a variety of material including interesting research, research reviews, group social events, conference reviews, plus more...