News from the IT sector and anything remotely related that I find interesting. Check out Non-Tech City for more of my views, nicely diluted with that of others.
Monday, February 28, 2005
Imagine a Use For Old Computers
Imagine a use for old computers, the ones that people throw out or leave in cupboards gathering dust. One that was free for everyone involved, took very little effort to implement, involved no running or maintenance costs. One that also provided on a massive scale, free, unregulatehttp://www.blogger.com/img/gl.link.gifd connectivity for all. Take an open source distribution of linux and cut it back to the bare-bones, giving it simple networking tools, allowing it to act as a wireless router. Remove all unnecessary cards and devices so that it's power consumption was reduced to a minimum and add solar power or some other free energy source.
Then take this box, and find a blind spot in the network and drop it there, leave it to connect to others, providing a grid of interconnectivity. Soon this would cover vast spaces. ISP's wouldn't like it, because you would be passing on a paid connection, so go around them. Write a new open source protocol: internet v2.0 - open source. Would this be breaking any laws? Would it be morally or ethically wrong in any way? The only legal problem I can see is that in these security conscious times unattended boxes all over the place could be a nuisance.
These machines could also have excess computing power, it doesn't take much to be a router. Maybe they could be under-clocked to save more power, but when the sun is out and there's no need to, they could donate their spare cycles to Seti@home or another of those types of program, again, becoming useful rather than becoming trash. Let's give ourselves a slightly larger budget and things get even more interesting, for example if we install a bluetooth adapter (they're all over eBay for a couple of pounds). Then imagine a kind of peer to peer music streaming, you wear a bluetooth ear-piece, and the PC streams your favourite songs to it, switching automatically to the nearest node, looking up your playlist from your website, or a centralised website where you enter your favourite songs. The songs could reside on your PC, or each node could hold a few, becoming a distributed library.
This is what distributed computing could be, but it won't. It will be RFID chips monitoring sales patterns and shoplifting, and it will be expensive pay-per-use wifi connectivity owned by ISP's and telephone companies.
If you have another use for old computers/hardware then please post it on our new forum, i'm going to try and compile enough ideas to write an essay on it.
Bill Cosby Wants to Sell You a PC
Call me cynical, but I don't think that Bill Cosby really knows all that much about computers. Oddly, he did appear in two computer ads, grinning away as he praised their virtues. There's 186 old computer adverts courtesy of 1000bit after this link, some of them are pretty interesting.
This looks very interesting, this project is trying to make interactive panels out of any flat surface around the house. The example use they give is making light switches that you can move around the walls without having to change the wiring. I want a keyboard made into the top of my desk, so I can use it to write on top of without having to move the keyboard.
MP3 Alarm Clock
Why haven't I seen one of these before? I sometimes use my PC to wake me up with an MP3, but that means I have to leave my HiFi/PC on all night. This is great, and it looks fantastic too. It has 256MB of flash memory, but claims to hold 8 hours of music, that must be at a pretty low bit rate.
Sunday, February 27, 2005
New X-Box 360 Pictures?
Is this the new X-Box? No. Probably not, it looks like it would cost a fortune to make, and will date very quickly. Look at the internals, it looks like a 1980's television! It's also copyrighted by Rune Larsen, at a place called cgnetworks.com which is a graphics design site. This is obviously a fake, but nice job Rune.
iBook Repair Saga No. 2
I had always been a PC user, until very recently when I purchased an iBook, partially motivated by the iPod I bought a while ago that i have been extremely happy with.
I bought the iBook around a month ago at the online education store, and received it soon after, I was very pleased with my purchase apart from one small issue.
When I first started using the iBook I noticed that the screen was ever so slightly off centre (it is able to rotate slightly so that it is sometimes correctly aligned and sometimes around 1-2mm off centre.
I did not think too much about it although I was slightly disappointed about the build quality, I thought that this was the reason that it was so much cheaper than the presumably better built powerbooks.
That was until I saw two other iBooks that friends purchased (partly due to my thorough recommendation) that did not suffer the problem at all, this is what encouraged me to call technical support.
I called Apple who told me that this kind of thing was all handled my local dealers now, and that i should call a company in another town in my county.
When I called this firm they said that they didn't know if it was covered by Apple warranty, but that they could open a file and check. however, if it was not I would be charged £40 inspection fee, I would also have incurred the cost of either driving it to the dealer (over an hour each way) or posting it twice.
The iBook is very new and in warranty, I would like to know why I am not able to have the machine looked at without the risk of having to pay £40, which I cannot afford. I have been using the iBook for several weeks now and have grown used to the issue as it does not affect the actual use of it in anyway, therefore I am no longer seeking an inspection or repair.
The inconvenience of it being away would far outweigh the problem itself.
I am however, informing you that this does not go very far to reinforce the reputation that Apple has as a friendly and efficient company, and as a recent switcher has made me realise that the level of service available is no higher than I used to receive with PC vendors (that level of service being one of my motivations to switch to Apple).
I merely encourage you to resolve this poor technical support before it creates reverse switchers, something that I do not wish to see, as Apple seems to be a far more creative and intelligent company that most others.
Microscopic Mr. T
This microscopic Mr. T image was found on a Dallas Semiconductor single-chip T1 transceiver integrated circuit, other images like this can be found at Molecular Expressions.
Holistic Computer Medicine
The Holistic Computer Medicine site has some interesting ideas on increasing uptime. Have you ever considered using crystals to ward off bad-vibes? How about distilling viruses down to one bit to use as a harmless cure for existing virii? (That's one hell of a compression rate, aas long as it's 2 way) Well, if you've tried everything else and you're still having problems then this may be worth a go, it can't do any harm, right?
Friday, February 25, 2005
Hackers May Target Pacemakers - Why?
Why, why, why, would hackers target pacemakers? What could there possibly be gained from doing that? The article mentions it briefly but then goes on to talk about the technology itself, the article is nothing to do with hackers really. The hacker angle was thrown in on purpose to allow the headline I would imagine.
iPod Recording - For Free
Apparently, all iPods have the capability of recording, but so that they're not used to record copyrighted material this is disabled. It may also be so that 3rd parties can flog recording devices for the iPod. There is a way around it, but don't get too excited - you have to install linux on your iPod to do it.
Here's a collection of iPod Shuffle art, this is becoming a bit of a phenomenon, I wonder why no one has embraced customising other pods? Their cost and screen covering blank space are an issue but there's plenty more standard iPods than shuffles right now. Go, now, customise your iPod. And leave a pic in a comment.
Personal Mobile Phone Jammer
There's a masters thesis based upon a Personal Mobile phone jammer, this is such a great idea, but if people start making these themselves then there could be serious problems in getting a signal in built up areas. That reminds me, I have to write my masters thesis soon...
I really want one of these now, on my desk keeping my coffee warm. Would have been far cooler if you could see the CPUs in the finished product though...
Wednesday, February 23, 2005
Happy 50th Birthday Steve Jobs!
Tracking Real Objects From Cyberspace
I find this idea strange, there's no reason why I should as it's a perfectly good use of the internet. But it's what it allows us to do an know that I find odd, tracking packages at the UPS website, tracking books at bookcrossing and now I have seen this website that allows you to track dollar bills around the country. What a bizarre piece of information to be able to access; where has this note been before?
Tuesday, February 22, 2005
I uploaded this photo to my Flickr account today with some weird tags, because it was a weird photo. As i did so I wondered to myself, 'I wonder how many people have ever uploaded a photo and felt it fitting to label it "buggly"?'
So, I typed in flickr.com/photos/tags/buggly to see, and lo and behold there was only one.
This reminded me of Google-whacking; had I just stumbled upon the (very unoriginal) idea of Flickr-whacks? Does anybody have anymore?
I'd like this post to be a shining beacon to people like me, who in the course of a normal day waste vaste ammounts of time doing things like typing random words into Flickr.
Comment away with your Flickr-Whacks, Flickrwhacks, FlickrWhacking, whatever.
iBook Repair Saga No. 1
Damn, I was so excited about getting my iBook. Now the novelty has worn off, quick.
When I first got it I noticed that the screen was ever so slightly off centre, which meant that the catch didn't work quite as it should. Sometimes you have to press the screen down 2 or 3 times to get it to stick. It also looks a bit weird, even though it's only 1 or 2mm out.
I sort of decided that I could put up with it, and imagined that it was probably something you got if you chose to buy an iBoook rather than a more expensive powerbook. But since then I have looked at my brother's and my flatmate's iBooks, and this problem isn't evident on either of them. So, I called Apple and they said that they don't really deal with repairs anymore and told me to take it to the nearest Apple dealer. This turned out to be a 3rd party dealer which is in another county, so I called them. They said that Apple probably wouldn't cover this and would class it as damage. To find out if I could get it repaired I would have to take it all the way over there, and then if Apple decided not to pay out then I would have to pay a £40 engineer charge. Being a student I can't afford this, I can't afford an iBook, but I bought one because i'd heard great things about them. I will keep trying, but for now, I reccomend shopping elsewhere.
Monday, February 21, 2005
Bloggers of the World Unite!
Tommorow, on the 22nd, bloggers around the world are being asked to raise awareness of these men. Follow the link and read their stories, and then put a banner on your site. No-one should be imprisoned for something they've said, especially on the Internet.
Man Pleads Not Guilty to Hacking Tsunami Appeal
Still a lot of talk about the guy in London who used a non-standard browser to submit a donation to the tsunami appeal. It flagged some intrusion detector and now he's being charged. I don't know if he's innocent or if he was trying to hack it (sounds like the second to me), but if he is innocent then someone is going to have to say a BIG sorry. Not only was he trying to donate to charity at the time, but now all the public think he's an evil haxor.
Paris Hilton Blonde, Hacked.
Paris is once again in the spotlight, this time for having her phone hacked into. The Hacker managed to steal photos, address books and notes, all of which are now on the internet. More than a little bit annoyed that she's getting all this attention for nothing and there aren't more column inches about the great HST, RIP.
Friday, February 18, 2005
100 Greatest Gadgets of all Time
Mobile PC has an article listing the greatest 100 gadgets of all time (in their opinion, certainly not mine). Still, there's a few things in there that I remember.
I like to know how things work. This morning I woke up with a terrible hangover, so I did some research. Hangovers are a combination of symptoms:
Now that we know what causes them we can put together a post-booze strategy. First, lots of water before bed and in the morning to combat the dehydration. Second, some burnt toast as the carbon acts as a filter in your stomach. This won't cure it completely but should help considerably, isn't science wonderful?
Thursday, February 17, 2005
Ten by Ten
Ten by Ten is a fabulous website that trawls through various news sites to determine the 100 most important words of the hour. It then collates these into a 10 by 10 square with approprioate pictures. Not only is this a clever experiment and an interesting way to represent information it's all open to development. Each hours results are archived and publicly accessible, so people can create their own interesting projects with the data. The image above is from http://www.tenbyten.org/Data/Now/now.jpg, meaning that it will be updated with the last hours results.
Using GMail as Journal/Organiser
There's a brilliant article at White's of Henry Lane about using a GMail account as a kind of personal organiser by using tags and labels. What a powerful solution, using a simple tool, i'm gonna try it out as soon as I get a chance (must stop procrastinating).
If anyone wants to try this I have 50 invites left, leave your name and email in a comment and i'll send you one.
Wednesday, February 16, 2005
Infinite Binary Table Paradox
Listen to this...
Take a table, with an infinite ammount of rows. Each row is a string of binary digits (0's and 1's). Now, each row is infinitely long, and there are an infinite ammount of rows, this is ok because there are an infinite ammount of possible combinations if we have an infinite length for each row.
But, now we create a new row, call it n, made up of the first number from row 1, the second from row 2, etc. but inverted. So, row 1 starts with a 0, so we place 1 in position 1 of row n. This means that n cannot be in the infinite ammount of rows, because each place in n is copied from another row, but inverted so it cannot match any one row. Therefore we have an infinite ammount of rows, containing all possible combinations, but it cannot contain row n. Weird.
Tech News Roundup
Haptic Feedback at Home
I've played with haptic feedback devices and used them at uni, I tried out a surgery simulation and it was absolutely amazing. The amount of feel you get is truly wonderful, with feedback resistance in 6 fields of motion. It really gave you a good sense of touch. But that cost over £10,000, i'd like to see how good these cheap versions for home use are.
Tuesday, February 15, 2005
Linux Powered Kitten Feeder
This couple seemed to be worried that their cats were not being fed treats whilst they were at work, so they did the logical thing - created a linux box with a web-enabled microcontroller connected to a mechanical feeding device. The description of how to make one of these yourself is very thorough, but I don't think i'll be trying it anytime soon. If you want to feed the lovely little kittens then head here.
control = Feeder()
print "Thanks for feeding the kittens!"
DIY Night Vision
This guy has made a night vision viewer out of stuff he found in bins, it looks like it really went well. One question sprang to mind when I read this: what the hell is he going to use it for?
Overclocking Gone Mad
Overclocking a processor to over 7GHz so that it doesn't run properly, getting a BIOS screenshot and then having to put it back in order to boot windows to post the pic. Odd, but I do find it cool.
Monday, February 14, 2005
Art and Technology?
The pairing of technology with art has become cemented; all music now comes in digital format, virtually all has been recorded, in or edited in, digital. It's now the case that many instruments are in a very real way, computers. This is all well and good but computers here are essentially enabling art rather than helping to create it. I witnessed the exception to this rule last night, in a reggie watts concert. His use of a sampler and beatboxing is a prime example of technology becoming a part of the art, not only enabling the artist, but inspiring him with capabilities that weren't dreamed of a few years ago. Check him out.
Beta 4 ever!
A few sites that I use everyday are in Beta; GMail and Flickr spring to mind. They've been in beta ever since I started to use them, and they show no sign of being in a hurry to get out. It used to be that beta was a transitory phase but it's increasingly becoming a symbol of ever changing, ever improving code, almost a designer logo saying 'we're at the bleeding edge'. I think it also makes a good get out clause - 'gmail crashed? Oh well, it's in beta so don't say we didn't warn you.'
Global Correlations in Random Data
At universities all over the world are small, very simple electronic number generators dubbed 'eggs' by those that work with them. They record the binary output of these machines and plot the data in graphs, an equal ammount of 0's and 1's will provide a flat graph, which is what you'd expect and what any statistician will tell you the average will be.
It has started to become evident however that certain events can alter the output of these machines, the Global Consciousness Project has been conducting experiments in this field for some time. They have discovered that strangers can alter the output by merely 'willing' it to change, most bizarely thought thy have discovered that these many eggs all over the world are affected at the same time by global phenomena. The funeral of Princess Diana, September 11th attacks and Asian Tsunami all affected egg output significantly.
Now time for the weird part, it is not an enormous leap to believe that thought can affect the output of these machines, our brains and the eggs all work on electrical signals and these can interfere with each other. The fact that this works globally is surpirising, but believable because these horrific events captivate the thoughts of millions all at once. The scarily weird part comes in that the effect of these events happens before the event itself, in the case of september 11th four hours before, in the tsunami 24 hours before.
There is actually real science behind this, and even an explanation as to why the result can happen before the event, but it involves some hairy phsyics. i know now what you're thinking; who works for the GCP? Uri Geller? David Blaine? Well, many respected scientists (over 75) from many countries (over 41) are involved, including professors from Princeton and Edinburgh Universities.
I urge you to give this site a read, it's scary/fascinating stuff.
Buzzwords We All Hate To Hear But Love To Use
Via Bizreport comes this list of overused buzz words from the IT industry. I've heard all of these in lectures and at work. I worked in web design at a newspaper last summer, now that's a place that loves buzzwords.
"World-class, best-of-breed, bleeding-edge, state-of-the-art: Variations on the claim that this is a unique and superior product.
E-anything: Something that is now being done online or in another electronic space, such as e-commerce or e-mail."
Saturday, February 12, 2005
Big Brother is Watching Your Bins
New chips are being put into wheelie bins that could tell the council about your rubbish habits.
This is typical of a slowly encroaching breech of privacy that, as it moves so slowly, no on can be bothered to do anything about. Some have suggested that the information could be mis-used, if people see a dramatic reduction in the ammount of household waste then this implies that they are on holiday, putting them at risk of burglary.
Turing Machine Made of Trains
This reminds me of something I found out in the first year of my Comp Sci degree that surprised me but that shouldn't have: you can make computers out of anything. They have been made out of copper pipes and water, circuits and electrons, gears and springs and now train and track. This all leads back to the days of hacking model railways at MIT.
Weirdness From Google
Weirdness from Google here, a father was granted custody of his child but the mother ran off with him. 16 years later the boy Googles himself and finds out he is officially missing.
Companies House 217 Scam
This is very scary, companies house here in the UK is where all companies are registered and they hold a database of campany details. Apparently anyone can go up there and request form 217 and change the address of a company or even the names of the directors. Three businesses so far have had the address changed by hijackers who then ran up massive debt at the new fake address in the name of that company. How stupid is that, not a hard loophole to spot surely?
Friday, February 11, 2005
Linspire Five-O Media Hub
There's a new Linkux distribution out called linspire five-o, which comes equipped with a very non-standard feature. The OS comes complete with an MP3 server which can beam music to all the other PC's in the house, it supports MP3's and has no nasty DRM to foul things up. I was thinking of getting an old PC on the network to be a media server, maybe it will run this, although this is a commercial distribution.
Successful Applications of Data Mining
Rather than post an enormous essay like last time, I thought i'd just give you the conclusion, forgive the references. This stuff is quite interesting, it's allowing huge advances in the usefulness of data:
Data mining has found many different applications through necessity, because almost every organisation in the world is undergoing a data storage crisis. The amount of data in the world doubles every year and our capacity to analyse that data is simply not keeping up. Data warehousing provides a solution to the storage problem, but it is useless without analysis. Data mining can solve this issue, making the data warehouse not only justifiable but indispensible to the large modern corporation. Data mining is still a very young technology, there are three main type of data mining, clustering, predictive modeling and frequent pattern extraction, and these models are basically the same whatever use they are put to. The innovation and advancement is coming from programmers and analysts who are finding ever more intelligent ways to use them to extract meaningful information from data. [Apte 97] Companies are making use of this new technology and it’s use is increasing, the worldwide spending on data mining is currently estimated at $539 million and if current growth continues it will reach $1.85 billion by 2006, this proves that there is a demand for fast and efficient analysis of vast amounts of data. Companies and organisations have been collecting information for decades and now it seems that they can finally start to use it productively rather than file it all away for occasional reference. [Leavitt 02] It may however, have negative connotations for the consumer, it raises privacy issues surrounding maintaining records of customer/citizen activity and companies must ensure that in trying to become more efficient they do not cross ethical and moral boundaries about what data they collect and how they use that information. [Nascio 04]
Firefox not Sustainable?
This article explains why Firefox cannot continue to expand at the rate that it is, I see why this could be true. But I really am excited by the way that people have seen it's a better tool and actually bothered to switch, some of them are people not normally bothered by this type of thing (luddites). I say keep going, keep trying to get people to try it and maybe it'll stick around in the numbers that it's being downloaded in. Try Thunderbird too, i'm using it for RSS feeds and my G-Mail account and im pleased with it so far.
Thursday, February 10, 2005
Downloading vs. Shoplifting
This article makes an interesting point about the penalties for copyright infringment and shoplifting: "the penalties laid out for downloading one season of a TV show with BitTorrent are much harsher than if you actually stole a DVD set of the same show from a government store". Doesn't seem right to me, essentially it's the same crime, but in a real sense shoplifting is a more criminal act.
Literature Survey - Metahueristic Algorithms: Ant Colony Optimisation
Abstract: This literature survey focuses on the ant colony metahueristic for solving combinatorial optimisation problems. It will research different approaches to the topic and investigate the state of the art before assessing its impact and use in real computer systems today.
A metaheuristic is a simple strategy where by a solution to an optimisation can be found by exploring the solution space in some way. [Dict 04]
Ant Colony Optimisation (ACO) is a metaheuristic for solving combinatorial optimization problems. It was developed by Colorni et al in the early 1990’s and is based on the way that ants convey information about route efficiency to each other. [Colorni 91]
The idea is based on the way in which ants discover the most efficient path between the colony and a food source and vice versa. This is achieved by laying a trail of pheromones at each decision point in the journey, that is, where there is more than one possible route. The shortest route will be utilised more as the time taken to cross that path will be shorter; therefore the amount of pheromone build up will be greater on this route. Other ants decide which route to take based upon the amount of pheromone detected at that decision point. The shortest route will be more often travelled and pheromone build up will be higher until eventually all ants take this route. This is a form of autocatalysis, or positive feedback. [Dorigo 99]
This paper focuses on the use of models of this strategy in various optimisation problems and their efficiency compared to existing algorithms for that field.
2 Research into ACO
This process is used to develop algorithms in the field of metaheuristics. The paper focuses on its use in modelling ant colony optimisation to find the optimal solution or solutions, or in the case of racing algorithms, the best case that can be found in a limited period of time.
2.1 ACO in the Travelling Salesman Problem
In the travelling salesman problem the aim is to calculate the most efficient route where each city in the graph is visited once, it is used for route planning both for electronic and physical traffic.
Dorigo et al conducted the first research into this field. Because of the similarity between this problem and the way that ants reinforce efficient routes to food sources, it was the first field to which an ACO metaheuristic was applied. [Dorigo 95]
The first work into ACO in the TSP was conducted in 1995 on the Ant-Q algorithm. [Dorigo 95] This algorithm was an implementation of the ACO metaheuristic, it was tested and compared to well established algorithms such as Elastic Net, Simulated Annealing and Self Organizing map.
The tests were performed using the same hardware configuration and specification on a set of 50 node graph problems (50 city maps).
The results show that Ant-Q was nearly always the best performing algorithm; this illustrates that even in the early stages of research that ACO was a very effective concept.
Although this is true, the first ACO implementation, AS, did not manage to match the performance of other available algorithms of it’s time.
Ant-Q and the similar ACS, both researched by Dorigo et al have shown that it is now extremely capable as a technique to match the efficiency of leading solutions. [Dorigo 95] [Dorigo 96] [Dorigo 97] [Dorigo 99]
2.1 Racing Algorithm Metaheuristics
Another problem where this technique that has been used is the racing algorithm for configuring metaheuristics. [Birattari 02] This technique finds either an optimal solution or the most efficient one possible to the optimisation problem within a time constraint. It does this by discarding solutions from the finite set of possible solutions by finding an equally or more efficient solution from within the solution set.
The metaheuristic used in this research is best suited to repetitive problems: “problems where many similar instances appear over time”. [Birattari 02]
The example given in the paper is that of finding the best route for a delivery driver, which is essentially the travelling salesman problem.
This is similar to what is explored in the previously mentioned papers except that instead of simply finding the best route between two points (colony and food source) there are many cities that must all be visited at least once. Visiting the cities only once is not a constraint however, as the optimal solution may be one where a city is visited more often.
In tests on the ant colony optimization problem, when compared with two other racing algorithms, one of which does not correct for multiple executions of instances (tn-race) and the other that does (tb-race), the proposed algorithm (F-race) showed promising results. Correcting for multiple instances is a good precaution for an algorithm to take especially in this case where there is a time constraint. Performing a test on a particular instance needlessly will waste execution time that could lead to the algorithm not reaching an optimal solution and resorting to provide the most efficient found before the algorithm is forced to end.
Using 1000 pseudo-samples (randomly ordered samples) the three algorithms were run. As the aim of racing algorithms is to discard results until an optimal or as near to optimal result as time allows is found, the results can be taken as the number of possible instances still in the solution space after the time period expires (in this case 10 seconds). [Birattari 02]
The results show that (on average) F-race had 7.9 possible solutions remaining after the time period, tn-race 31.1 and tb-race 253.8. Obviously the fewer remaining solutions the more efficient the final result is likely to be and the more tested the remaining solutions will be. The remaining solutions are tested in order to find which to discard next, F-race's remaining solutions were tested 77.9 times where as tb-race's where tested/run 5 times. This would make the selection of an efficient solution much more likely by the algorithm that discards solutions quicker. However, having tested but not discarded solutions means nothing after the algorithm is forced to finish. Despite this, F race (the ACO approach to solving this problem), still reduced the solution space the most and found the most efficient route when compared to the two existing approaches using the same hardware configuration.
F race is described in the paper as the 'bravest' algorithm of the three, because it discarded the most solutions. [Birattari 02]
It is clearly a viable solution to solving this time constrained problem. This could have applications in real time optimisation problems, where an optimal solution is desirable but a timely solution is vital, such as TCP/IP traffic routing.
2.1 ACO in the Single Machine Total Tardiness Problem (SMTTP)
The use of the ACO metaheuristic in application on the Single Machine Total Tardiness Problem (SMTTP) has also been explored [Bauer 99] [Bauer 00]. SMTTP is the issue of finding the most efficient order to process tasks in a non multi-thread capable processor in order to reduce to a minimum the idle time of the processor. [Bauer 99]
Many solutions have already been devised and have been very successful - branch and bound is a well-known example. It is clear that the purpose of these algorithms is to maximise the throughput of the processor and that the solution will itself become part of the problem as it will require computation. Therefore there must exist a trade off between the processor time required to compute the next task and how much processor time is saved by using it efficiently. [Bauer 00]
To allow an ACO solution this paper proposes that the states of the processor be represented on a graph as the cities are in a travelling salesman problem, allowing it to function in a similar way. [Bauer 00]
The experiment used 250 benchmark tests containing different amounts of jobs awaiting scheduling to the processor. The results were shown as the net benefit of relocation for a job (NBR) as a percentage of overall efficiency.
An existing algorithm called M-NBR works by selecting two solutions, comparing the NBR and discarding the slower was used as a comparison. It was shown that ACO solved all problems to optimality and that M-NBR solved less than half to the most efficient solution. [Bauer 00]
The results show that in experiments with large sets of problem instances very good optimal solution times where produced: “Our approach outperformed all leading heuristics significantly.” [Bauer 99]
The use of ACO in this problem has shown to be a good solution as long as the problem size is sufficiently large. However, due to the increasing use of multiple processors and multi-thread capable processors it would be interesting to research whether ACO is suitable for these more complex challenges, as this simplified model could become obsolete in years to come.
2.1 ACO in Constraint Satisfaction Problems (CSP’s)
Constraint satisfaction programs are solved using a technique known as linear programming. Golomb and Baumert initiated development of this type of programming in 1965 when they proposed chronological backtracking. [Hemert 04]
Using ACO in CSP’s has proven to be a valid technique, a method was proposed by Hemert et al. [Hemert 04]
The finite set of solutions is slowly narrowed down in the search for the optimal solution (occasionally solutions). Before this a filtering technique is often used to cut out a set of improbable solutions to reduce the number of solutions to be examined. The use of ant colony optimisation in CSP’s is proposed to be very efficient as they do not search all possible solutions but instead follow a path through the solutions following trails of efficient solutions; this is the model of pheromone trails.
During experimentation on ACO and normal constraint programming it was shown that on small problems constraint programming was still the most effective but that as the problem size increased (over 35 variables was the transition) the ACO approach became significantly more efficient. [Hemert 04]
This shows that ACO is an effective technique for solving constraint problems providing that they are of a sufficient size, as CSP’s become exponentially more complex as more variables are added and ACO performs well in large, complex problems. [Hemert 04]
CSP’s are used for large problems such as deriving timetables for bus or train routes where there are many vehicles and destinations, or maximising the cost efficiency of mixing various grades of oil in the Industrial sector.
ACO is capable of providing a very efficient and timely method for finding the optimal solution compared to constraint programming.
Ant Colony Optimisation is a very versatile metaheuristic. Since it’s conception in the early 1990's it has been successfully used in travelling salesman problems, processor job scheduling and vehicle routing, as well as many other applications not touched on by this paper. It has been the subject of many research papers and its efficiency has improved greatly from it’s first implementation, AS [Dorigo 95]. It is now a real contender to many established benchmark algorithms.
One issue that seems to have arisen in the use of ACO on several different problems is that they do not perform particularly well on small problems; in CSP’s and SMTTP’s in particular this became evident. [Birattari 02] [Bauer 99] [Bauer 00]
This is due mostly to the period at the start of computation where the algorithm is in a state of disarray as not enough pheromone data has yet been computed. In this state progress is relatively slow when compared to progress towards the end of computation where much of the possible solutions have been discarded. In real ant behaviour this phase can last several minutes and is called the transitory phase, but after this order starts to emerge and a more efficient route starts to become default to the ants. [Dorigo 99]
This overhead is the cause for their unsuitability for small problems, by the time that transitory phase is over other algorithms have made headway in finding an optimal solution. It is only in larger problems that this overhead can be offset by the more efficient method of solving the problem.
Considering this restriction on the use of ACO, two things become obvious. Firstly, it is clear that they are not useful for small problems with a limited number of instances although they are evidently able to outperform established algorithms on large scale problems. Secondly, that if they are to become competitive on smaller scale problems that the transitory phase must be reduced or eliminated to allow the efficient later phase of computation to start earlier. Existing techniques to solve CSP’s often utilise filtering techniques to crop improbable areas of the solution space prior to attempting to find an optimal solution, a technique similar to this could be employed in ACO techniques in order to promote faster calculation. Another possibility is the creation of some pre-existing pheromone trails along promising routes calculated by past experience in order to reduce the transitory phase.
The results shown in this paper make it clear that ACO is already being used in a number of applications and that research is being carried out into its suitability for many more. One interesting paper that was not included was the use of ACO in cutting stock levels and packing bins, showing that even a supermarket has a need and use for advanced metaheuristic algorithms such as ACO. [Levine 03]
[Dorigo 99] M. Dorigo & G. Di Caro, The Ant Colony Optimization Meta-Heuristic, In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization, McGraw-Hill, pp. 11-32 (1999).
[Dorigo 96] M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, 26(1):29--41, 1996.
[Dorigo 97] M. Dorigo and L. M. Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53--66, 1997.
[Birattari 02] M. Birattari, T. Stutzle, L. Paquete, and K. Varrentrapp. A racing algorithm for configuring metaheuristics. Technical report, Intellektik, Technische Universitat Darmstadt, Darmstadt, Germany, 2002.
[Bauer 00] A. Bauer, B. Bullnheimer, R.F. Hartl, and C. Strauss. Minimizing total tardiness on a single machine using Ant Colony Optimization. Central European Journal of Operations Research, 8:125--141, 2000.
[Bauer 99] A. Bauer, B. Bullnheimer, R. F. Hartl, and C. Strauss. An ant colony optimization approach for the single machine total tardiness problem. In CEC99: Proceedings of the Congress on Evolutionary Computation, pages 1445--1450, July 1999.
[Colorni 91] A. Colorni, M. Dorigo, V. Maniezzo. Distributed Optimization by Ant Colonies, Proceedings of European Conference on Artificial Life ECAL '91, Paris, France, Elsevier, pp. 134-142, 1991
[Hemert 04] J. Hemert & C. Solnon. A study into Ant Colony Optimisation, Evolutionay Computation and Constraint Programming on Binary Constraint Satisfaction Problems, 2004, http://citeseer.ist.psu.edu/659158.html
[Levine 03] Levine, J. and Ducatelle, F. (2003). Ant colony optimisation and local search for bin packing and cutting stock problems. Journal of the Operational Research Society. (forthcoming).
[Handl 03] Handl J. and Dorigo M., 2003. On the Performance of Ant-based Clustering. Proc. of the 3 Int. Conf. on Hybrid Intelligent Systems, IOS Press, Dec. 03, Australia.
[Dict 04] www.dictionary.com, 19th November 2004
[Dorigo 95] Gambardella L. and M. Dorigo, 1995. Ant-Q: A Reinforcement Learning approach to the traveling salesman problem. Proceedings of ML-95, Twelfth International Conference on Machine Learning, Tahoe City, CA, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, 252--260.
Apple May Licence Mac OS X for PC
Apparently there's three companies after a PC version of Mac OS X, but it isn't revealed who, or if they got what they wanted.
This would be a very bad move in my opinion, windows has a massive piracy problem and evry soon there would be a rash of pirated OS X copies. This is not a problem if it only runs on Mac hardware, also the prestige would be lost if mac OS was available on nasty beige pieces of crap. initially the boxes would be novelty, come at a premium and be high quality, but that wouldn't last forever.
The article also reveals that way back when MS bought 150 million dollars of stock in Apple they made a good deal, because that stock is now worth over a BILLION dollars. Think you can escape MS by buying a Mac? Nope.
Online Auctions Reach Weird New Levels
You can now bid on the chance to have a monkey named after you. The money will go to the upkeep of a nature reserve. "This opportunity is for someone who wants to leave behind a truly lasting legacy that they cared about conservation and wildlife" Says Robert Wallace, the mastermind behind this odd scheme.
European Software Patent Petition
Flash Based Chaos Theory Game
This flash game is a chaos theory simulation using border detection collisions that illustrates how chain reactions occur and spread. It's also addictive and I spent bloody ages playing it, my best score was 120, beat that!
Just to keep it high brow, read this, it's a chaos theory introduction.
Wednesday, February 09, 2005
LED Stick Men Hot Action
I have no idea what the text says, but these images are great. If anyone can read this then please tell me if you can buy these things!
Space Flight Competition
I wish I was a US citizen, then I could enter this competition. Volvo are giving away a flight into space with Virgin Galactic, obviously scheduled for whenever the hell they start doing it. I wonder how much it cost Volvo?
There's a description on the Virgin Galactic site of what it will be like to take one of these flights.
The new cell chip developed by IBM, Sony and Toshiba is up and running. It's going in the new playstation apparently and also workstations and HDTV's. It has been running at over 4GHz and is essentially 8 core CPU's running in parrallel, which means i'm not looking forward to ever having to program for one.
This site proclaims to be an "erotic and informative video series about learning to build a computer to run linux on", which is very strange. But, if you want to learn this stuff I can think of worse ways of doing it.
Tuesday, February 08, 2005
Scary Geek Art
Imagine an enormous speaker mounted on a robot arm like something you'd expect to see in a car factory. Imagine that it watched you and reacted to your presence, sometimes getting excited and spinning at 100km/h screaming bizarre noise as it went. Imagine all this in a spooky old church. That's what some guy has built here.
WiFi Detector Ring
This is an interesting product, a wearable WiFi detector. I often have the problem in this cafe I know where I don't know what table can reach the WiFi signal. I know that the far side of the place does, but if I had this ring I could sit anywhere where the LED was on. I see that as useful, but I would only consider it if it looks like a plain silver ring, i'm not walking around like Mr. T. The image is an early prototype by the way.
Virtual Laser Keyboard
This is amazing, if it works. The unit shines a laser outline of a keyboard onto your deks and uses "optical recognition" to tell which key is being tapped.
Monday, February 07, 2005
2 x iPod Posts
Virus Attacking Cars?
Students Taught Virus Writing and Spamming
Apparently, students at the University of Calgary are offered a course on virus writing, and soon will be able to take one on writing spamming software. I see the argument that computer science students should have an understanding of how these things work, if they are to work in the anti-virus field, but maybe for the sake of not causing a media fuss the course should have had an anti-virus title/content.
Need a valentines gift for that special geek? Well, don't get this because it's tacky, and it'll go in their computer out of sight. Stupid.
Extremely Small/Costly RAID Array
This guy and three friends had just bought iPod shuffles and somehow he convinced them to let him borrow them before they had even played with them to turn them into a RAID array. How odd.
Anton Tomov Fed Up With Pirates
A new piece of software for the Pocket PC has a remarkably harsh punishment for all those that put in a fake or artificially created serial number during install; it runs the code below.
KernelIoControl(IOCTL_HAL_REBOOT, NULL, 0, NULL, 0, NULL);
For all of you not up on Pocket PC programming the software wipes the machine's memory clean. Illegal reaction to an illegal action.
Old I Know, But Benevolent
I know everyone has them now, but they're starting to bug me. 'Invite a Friend', everytime I log in, mocking the fact that I don't know enough people to give them all away. Smug bloody invites. Leave your name/email in a comment and i'll send you one.
LCD Picture Frame
I want one of these, but I want more features. For a start I want more memory than it comes with, I want it to also be a sort of photo file server, wireless would be nice too but a USB port would do. I also want it to be able to display not only photos but also movies. You know what does all that, that I already own? My iBook. Now I don't want to nail that to the wall but I may look on eBay for an old laptop, maybe this will be my next project.
Airport Express Mulitfunction
The airport express, it has so many uses. Here's a picture from Flickr of someone using it to charge/load his iPod shuffle, provide wireless access and warm his coffee all at the same time. Not sure if that voids the warranty.
This could be really exciting, they claim to have millions of users and if this figure keeps increasing then it could take over the home phone market. There's also a possible threat to the mobile market too, as they offer a Pocket PC version. Therefore, Skype + Pocket PC + City Wide WiFi = Free replacement for mobile phone.
Geek Action Figures
"Each Everyday Superhero is 6 inches tall, made from plastic, and comes with accessories. Geekman comes with Geeky Glasses, Handheld Computer/PDA, Notebook Computer, Coffee Mug & Wristwatch."
Remote Sentencing by Mobile Phone
Rescheduling a trial costs a fortune, that's why when the defendant got struck in traffic this judge decided to phone him on his mobile to avoid having to do so. Is this the first sentencing over wireless technology? We already have preliminary job interviews over the phone, why not court cases?
Blogging About Work a Risky Business
If you work in IT and blog about IT then it can get a bit iffy. Some companies publish guidelines about what you can and can't say, others don't. But it's starting to be an issue, with many stories of people being fired for spilling the beans. Good job i'm still a student.
When to Unplug
I like Tech, you like tech, we all like Tech. But sometimes you need to unplug, these people are a case in point.
Uptight People Here
So, once you've finished reading this blog, i order you all to have a breather and spend five minutes in the real world.
Mozilla Firefox hits 22 Million Downloads
Firefox hit 20 Million downloads yesterday according to Spread Firefox. I use this browser on my Mac and my PC and really love the whole tabbed browsing/less spyware thing. If you haven't tried it out yet then I thoroughly reccomend it, I put a link here for you because I know how hard it is to fight that apathy.
Do Not Eat iPod Shuffle
Ok, so the Apple website at some point had a warning disclaimer saying that you shouldn't eat your iPod Shuffle (or chew dependant on which store you're looking at). Small laugh. Then someone with too much time on their hands wrote a (very long) poem about it which I couldn't finish. Now Apple have changed the site, but Google still points there if you search for "don't eat iPod Shuffle". Basically this is a rant about how some people have far too much time on their hands, which I suppose I am proving I do by writing this. Damn.
I want to work for Google!
Google have started offering bonuses based on the employees contribution to it's success. Massive bonuses, sometimes exceeding a million dollars. This is a great way to attract the top programmers, even those on an already massive wage.
Computer Key Money Box
No G5 Powerbooks
Despite rumours about G5 powerbooks being on the way (partly fuelled by the discovery of some HTML code on the Apple store containing the string 'Powerbook G5') it appears that it's not to be.
There were some performance increases unveiled and a new scrolling touchpad, but all models still use the G4 processor (which is good if, like me, you just bought a G4).
The reason that Apple have given is that the G5 is just too power hungry and hot for a laptop. That would make it bigger, heavier and noisier than current Powerbooks, not Apple's style.
Sanyo Workers asked to Spend Wages at Work
Following on from the post about MS employees being worried about showing their iPods at work, this article writes that Sanyo workers have been asked to spend a portion of their wages on Sanyo goods. A large portion by the sound of it.
Mac Mini and Mac Media Center
I want a Mac Mini. I use my iBook for everything now, bar music and films which I still use my PC for because of the storage space it offers. So i'm going to get one, just as soon as they're capable of being a media center. I want a bigger hard disc, and most of all I want this to be finished:
I think that this will be a very cool (open source) tool. Who wants a Windows Media Center when this will be ready soon?
iPods on MS Campus
There's an interesting article over at Wired about 80% of MS employees
having a portable media player, 80% of which are iPods, i.e. there are
16,000 iPods on the MS campus. The local apple shop is selling them
faster than they can ship them in. But some employees are worried that
it will be construed as betraying their company, indeed it seems that
high level memos have been zipping around about employees choice of
What's the big deal? Do you have to be loyal to them? Would there job
really be on the line if they chose an iPod over an MS alternative?
G-Mail over Hotmail? AIM over MSN? Google over MSN Search? Playstation
over X-Box? You get the point, I certainly wouldn't like to work
somewhere where my choice of consumer electronics has to be based not
on personal preference but instead on what my boss will say.
What i've done with my new iBook
Sorry to harp on about the iBook again but it's a new gadget and you
understand how it is...
I tried out the WiFi for the first time, found a network and jumped
on, it was really quick and I was surfing and logged into MSN easily.
The ability to check e-mail whilst being outside with no wires is new
to me but it's very cool.
I've also been learning a lot of unix commands as i'm determined to
make use of that Darwin chassis beneath OS X.
New iBook & Advice for Switchers
I bought an iBook, i've had it 3 days now, it's my first ever mac and I love it.
If you are considering switching to a mac or getting one to use
alongside your current PC then finding impartial advice can be
difficult. There are also a lot of myths surrounding macs that may
never have been true, or are throwbacks to the pre OS X days, which
only serve to cloud the issue.
The main myth about Macs is that there are a lot of compatability
issues when working with PC's, this could not be farther from the
truth. A lot of popular software for PC's have Mac counterparts, MS
Office, Adobe Photoshop and MS Internet Explorer to name a few. There
are also a lot of freeware options such as Open Office that perform as
well as MS Office and are capable of saving and reading files in
Office format. Exchanging files between Macs and PC's is also trouble
free, Apple's version of WiFi, Airport, will connect to a wireless
network of PC's and wired networking is also no problem.
CD's written by Macs can be read on PC's and vice versa and the
increasingly popular USB flash drives also work.
Other popular file formats are also cross-platform compatible;
obviously HTML pages are no problem, but Jpeg, gif, pdf and MP3 files
are also perfectly compatible.
Therefore if you use a PC to surf, check e-mail, compose documents,
listen to music or watch DVD's then with the right (free) software you
will have no problem straight out of the box.
The only drawback is that you will have to learn to use OS X. It's a
very capable OS, being based on Unix, but it does take a bit of
getting used to if you have previously been in a PC only environment.