Ants and AI, and more detoxification

Ants should not be used when ant-communication via pheromone exchange is not needed or when there is little use for it. Nor should it be used, when two criteria you are trying to minimize are conflicting. Keep the target as simple as possible.
If you do want to push on with the ants, and there is a unique requirement on each ant, try to treat the ants as individual ants, for instance use past pheromonal information from ant a in time i to guide your ant a in time i+1.
ACS differs as it can use pheromones to exchange information between ants a and b... etc., in time i and also time i+1.
Beware of the cost of the global update rule, this can simply blow up. O(n*n) time for each solution iteration.

These are the most important lessons I have extracted from this last two months. Well that and read and reread, think and rethink, before committing to any ai strategy. Doing good research is half the work.
Well at least now I know how to start and finish an ai research project, well at least a small one.

bye

jzz

More Ants

The computer simulated ant pheromonal behaviour applied from ACS on the tsp-problem generally work like this:

1. There are n number of nodes, n*(n-1) / 2 number of edges which connect the nodes (There can be less edges, but this might result in dead ends). The geography of the search space is defined by a graph consisting of these nodes and edges.
2. There are m number of ants deployed at random on a node on the graph.
3. The ants are given a random fractional value q between 0 and 1 to give them "incentive" to move, a parameter q0 is set at the start of the algorithm, if q < q0, the ant will choose an edge the most heavily laden with pheromone, otherwise the ant will choose the shortest edge.
4. When the ants move from node to node, a "local update" is performed on the edge, that means to say an ant deposits pheromones on the edge. When the ant has traversed an edge, the node where it arrives at is marked as "visited". Ants will only traverse edges which have unvisited end-points.
5. The sum of the total distance traversed by the m ants, is compared to the best distance until now. If there is an improvement, the old best solution is replaced by this new solution.
6. When the ants have visited all the nodes, a "global update" is performed on the graph. Edges which belong to the best solution known, are reinforced by adding more pheromones on them. Edges which don't belong to the best solution are evaporated.
7. Rinse and repeat f number of times. Until a good solution is produced by the ants.

The ants are very very very good at hitting the tsp problem this way. And they are quite good at attacking the single objective (distance) trivial vrptw problem.

But alas the problem is not scalable to tackle multiple-objectives, because of its innate tendency to choose shortest edges. Objectives which do not improve by getting the shortest route will conflict with ACS's desire to create the shortest route(s). This is where pure ACS fails.

But I believe that some type of bastard child between genetic algorithms and tsp are quite capable of tackling non-trivial vrptw problems, and are very scalable with relation to the number of objectives. Using inheritance, recombination and mutation and ants. But more research will have to be done in this field.

But now I'm taking a break with ants, and now I'm going to try simulated annealing with genetic algorithms. To pick myself up again.

Tah-tah

jzz

Sheer Utter Complete Disappointment and Disillusionment

So, what have I been doing the past year?
I have been programming constantly, honing my C++ programming skills.

Let me get this off my chest first.
I have been working on a problem for 2 months now. The problem at hand is generally called "the vehicle routing problem with time windows" (vrptw). This specific problem that I have to solve is about a set of shops, a fleet of delivery trucks/persons, each truck and shop have certain working hours (i.e. they will not be available in the middle of the night), and moreover every shop has a different visiting priority (some are less urgent to visit), and every shop has a favourite deliverer. (preferred delivery agent)
A route must be charted for every agent on every agent's working day. The route consists of a string of feasible shops (shops that are open at the time of visit) which the agent must visit to complete her route. The goal is to create such routes and minimize the costs that are created by these routes.

This vrptw problem instance has been my first major ai programming challenge. I had lots of fun doing it. But the results weren't as rosy as I had hoped they would be.

The algorithm I chose to implement to tackle this problem is called Ant Colony System (ACS). ACS widely known for solving travelling salesperson type of problems. ACS is used in robotics (e.g. moving robotic limbs efficiently), routing (i.e. internet communication), because it effectively solves nearest neighbour type of problems.

One should not confuse ACS with Ant System (AS), AS is a precursor of ACS. AS is the first pheromone-based algorithm proposed by Dorigo (Dorigo, 1992).
ACS is the new and improved successor of AS, both are modelled after ant behaviour when foraging for food and whatnot.
It is known that ants leave traces of pheromones where they walk and other ants may choose to follow this pheromone trail (pheromone exploitation) or explore (random exploration) other paths. This collective behaviour is called "stigmergy", coined by some French ant geek (Pierre-Paul Grassé in 1959).
The union of pheromone trails from different ants on the same path create a strong pheromone trail (reinforcement), while infrequently traversed trails evaporate.

It is claimed that ACS can tackle the vrptw problem, little documentation can be found about ACS being used to tackle the vrptw problem. I have found one (Gambardella et al, 1999) document on the internet about this problem. The problem described there is quite trivial compared to the one I am tackling. That document describes how they minimized the actual number of agents needed to solve a trivial vrptw problem. It was more or less travelling salesperson with multiple agents. (trivial: without all preferred agent etc. stuff I mentioned before).

From my experience with ACS, I conclude that ACS is great when you tackle problems with uniform objects. Uniform nodes, uniform edges, uniform agents etc. In my actual vrptw problem every agent is unique. Every shop is unique and has unique requests. Very much like the real world. That's one of the reasons why my experiment failed... anyways, I'll go into the specifics tomorrow. Enough general data for now.

Tah-tah

jzz


References

Dorigo M. (1992). Optimization, Learning and Natural Algorithms. Ph.D.Thesis, Politecnico di Milano, Italy, in Italian.

Gambardella L.M., Taillard E., Agazzi G. (1999), MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows , In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization. McGraw-Hill.

Grote dikke memmen and stuff

<cut&paste>
Rules:

1. Comment and I’ll respond with something random about you. I’ll respond in comments so you’ll have to check back.
   
2. I’ll tell you what song or movie reminds me of you.
   
3. I’ll pick a color/flavor of jello to wrestle with you in.
   
4. I’ll say something that only makes sense to you and me.
   
5. I’ll tell you my first memory of you.
   
6. I’ll tell you what animal you remind me of.
   
7. I’ll ask you something I’ve always wondered about you.
   
8. If I do this for you, you must post this on your blog. You MUST. It is written.
   

</cut&paste>

Impressions of me from the wonderful inedible blogger SNE:

1. Random:
   
2. Song/Movie: Freddy got fingered, albeit just for that hospital scene!
   
3. Jello: You strike me as strawberry for some reason I can't quite figure out.
   
4. Only you and me: Thanks for "lending" me the bike!
   
5. First memory: "Wow! Actually someone shorter than me!"
   
6. Animal: Sloth!
   
7. Always wondered: Why don't you just do your work in school? It would make things so much easier on you!
   

Hmmm... dunno what to say about this...
except "MUHAHAHAHA..."

bubbye

jzz

Likes & Dislikes

<cut&paste>Simply-not-edible tagged me. I’m to list a top 10 list of turn on’s & off’s. So, pretty much it’s 10 things I really like and don’t like… Here we go:</cut&paste>

• Turn on

• 
  

  1. I do not like green eggs and ham. -- Dr. Seuss r00lz supreme.
     
  2. books - billowfolds of information in those things, very amusing stories too.
     
  3. games - eons of time procrastinated into these things... horrible devices of slothfulness, very fnu!
     
  4. computers - infinitesimal complexity crammed into these things, gotta luv'em
     
  5. ai - when will computers make the next paradigm shift?
     
  6. music - layers and layers of temporal art, flooding into my consciousness cacofonically organized.
     
  7. martial arts - kick ass with quick moves, being in the moment
     
  8. loved ones - makes life worth the hassle
     
  9. sex - hereditarilly yummy
     
  10. nature - myriads of forms seeking a dynamic balance. Photosynthesis is very cool.
      
  
  
  
  



• Turn off

  
  
  
  
  1. Wysiwyg html editor that fudges my markup code
     
  2. competitive games with no high-score
     
  3. uninformative error messages
     
  4. computer languages that are badly formatted i.e. (((lisp)(clips)))
     
  5. yucky dishes my mom forces me to take home as left-over, which I force feed myself the next n days.
     
  6. Prolonged rainy days, symptoms of monsoons and typhoons, nah, just general bad weather.
     
  7. Closed source unstable software. Long live free software! A la liberté.
     
  8. Close facial encounters with sweaty armpits in buses during the hot season.
     
  9. Wet panties when I'm wearing them, I don't mind making panties wet... by suggestion.
     
  10. indigestion.
      

I tag Faerie

toodles,

jzz

Quickie

Getting the hang of programming and designing a website. Markup template done. Now programming database. Hooking up database, markup template with php. Using oop techniques.
Probably done in 3 days. Woohoo!

bye

jzz

Interview

<cut&paste>
Okay, let's get the official things out of the way before going on to the rest of the day.

1. I’ll respond by asking you 5 questions, each person’s will be different, posted in my comments on this post- so check back..
   
2. You’ll update your blog with the answers to my questions..
   
3. You’ll include this explanation and an offer to interview others in the same post..
4. When others comment asking to be interviewed, you ask ‘em 5 questions.

Right, then. Now, in advance - don't make me think up too many questions. Please.
</cut&paste>

Questions posed by Faerie:

1. If you were an animal, what kind of animal would you be? Please explain your answer.

I'd be a sloth. It would be nice to survive as a content yoga artist in perfect harmony with your surroundings and have a colony of microscopic beings live under your fur in their microscopic world of their own.



2. If you had the money to go away on holiday, where would you most like to go?

Where do you wanna go babe? You know this, I want to go to China first, Beijing. To see how much has changed in the past eleven years. (2005 - 1994) See how much of my childhood memories has been torn down.



3. What do you want to be when you grow up?

Hm... I want to be the father of your children when I grow up :) and have a good job as an AI engineer on some health improvement related job and get rich while doing what I like :)



4. Make a top three of your favorite meals.

hm... tuff one.



1. Sweet & Sour pork from a real traditional Chinese cook... not exactly vegetarian
2. My mom's beef stew... not exactly vegetarian either
   
3. Sweet seasoned ribs... very dead too

All above probably have a vegetarian equivalent.




5. If you were unjustly locked in prison, how would you escape? Use your imagination!

First, I would try to decline not so tempting offers from other inmates to be their butt-buddy, and prevent rectal carnage.
Secondly, I'd try to escape the boredom by improving myself in any way I could.
Thirdly, start massive uprisings and dissent from the inside and let people become aware of this great injustice and let the movement to free me and others like me spread like wildfire, then break out.

toodles,

jzz

More Design and Implementations...

I designed a database last night. I think it's pretty good. It is simple and the implementation code in php comes to me easily (haven't coded it yet). I think I'll need a wrapper for the database connections etc. And I wonder if I need a new parser to handle the text etc...
At the moment I'm trying to figure out how mysql takes a dump, that way I can feed it to a new database that uses the same table structure. This would spare me eons of time. Which I don't have.
This coding stuff is pretty tiring. And it's not really good to my health either. Staying indoors, bathing in cathode-rays instead of sunlight isn't doing wonders to my complexion.
After I'm done with this database stuff, the only thing I would have to do is, code a graphical user interface for my clients, so they can update their own site. Less work for me. And make a parser for the database so it spews out good html or not (in case of *.pdf, *.doc... etc...).
Then comes the fun part! I get to design the xhtml/css and graphics. I was thinking of a single-column design, nothing fancy. First start with a base css. Then add browser bug squashing css support... I hate this part. Why don't they just build compliant browsers.
I love doing the arty part of websites. I'm actually a graphical artist at heart, but I'm generally bad at creating digital art, although I can nitpick with the best of them.

the plan for tomorrow:

1. create client-side maintenance login


2. create foto album generator


3. create database login wrapper


4. create text renderer


5. create html base template site-wide


6. design/implement css site-wide


7. ... check for bugs and eventual security holes...

Too much to do in so little time. Can't slack off now. All I need is a good set of class interfaces I could recycle in each project. This would spare me seas of time. And it's a good thing I can rip-off code good gpl-licensed code from certain php websites.

sleepy time,

bye

jzz