Today following some guidance I was given by a Java expert, I finally managed to get methods in the main class of the simulation to take in arguments passed from the command line, set variables to equal these using setter methods, and then return them using getter methods. This is a large breakthrough which has taken me literally months to get to. In my next coding session, the task will be to start automating simulation so that it can run on its own, using some sort of scripting to kick it off with appropriate input values. In the meanwhile, gone to celebrate!
June 21, 2007
June 20, 2007
Wednesday: more Stochastic Diffusion Search …
More reading/writing about stochastic diffusion search today.
Quick note to self regarding topology: if you think about it, each agent in the SDS population is connected to every other agent in the population… however the connection only becomes “active” randomly so it is not a permanent neighbourhood.
Another quick note, look at page 62 of Nasuto’s thesis as he mentions the convergence from SDS. He also has an interesting worked example of how an SDS search progresses.
— Quick notes —
Stochastic diffusion search is a parallel based search algorithm, developed by Bishop in 1988. The algorithm achieves a linear time complexity (Nasuto thesis). Stochastic diffusion search attempts to solve inexact matching (stimulus equivalence) with less computational expense than that of Neocogntion or Hinton mapping methods (Bishop 1988). The algorithm has four distinct parts: initialisation, testing, diffusion, and termination.
Method of action
Stochastic diffusion search uses individual elements called “agents” to store positional mappings, the agent’s current position in the search space. During the testing phase each agent compares its mapping with that of another randomly selected mappings elsewhere in the search space.
During initialisation, each agent is randomly assigned a mapping into the search space. The testing and diffusion phases then loop until the termination conditions are discovered. In the diffusion phase, information is transferred between agents, enabling communication regarding possible solutions. Agents can become “active” they point to possible solutions in the search space, and remain “in-active” if else. Through agents independently searching for partial, possible solutions, a competitive, co-operative process emerges. As partial solutions are identified by the population of agents, and other positions are identified as incorrect, the partial solutions “compete” to have additional agents allocated to their positions. Through this, competition changes into co-operation, with increasing numbers of agents attracted to explore the potential solution.
As the process continues, more dimensions of possible solutions are analysed, hence identifying incorrect solutions, which are removed from the set of possible solutions. Through this process and the above-mentioned competition, all potential solutions will be independently evaluated, and after a number of iterations most promising one will attract the majority of the computational resources, with the position of the best fits the data model emerging.
June 19, 2007
Tuesday: understanding stochastic diffusion search …
Today I have been continuing the reading and researching I was doing over the weekend regarding stochastic diffusion search. I have found some interesting papers, mostly by Beattie regarding the self localisation of a wheelchair — see Beattie’s PhD thesis (link) or the publication in the Journal of Intelligent and Robotic Systems (link).
Stochastic diffusion search, as I understand it, is as follows — bear in mind though, that this has been heavily influenced by the wheelchair localisation papers I have been reading. I will use the analogy of the wheelchair localisation to try and convey my thoughts also:
Imagine a wheelchair, that is semi-intelligent and is trying to find its current location in a known area. The wheelchair has laser distance sensors at eight positions around its chassis, at North, Northeast, East, etc. The laser sensors initialise, and get a reading. The theory here is that if you know the orientation, in other words the angle, the wheelchair is pointing in and the distances returned for the sensors, you should be given a unique location.
Now with stochastic diffusion search, you have a number of agents which are effectively processing units. These agents point to a particular space in a simulated version of the world the wheelchair is in. To begin with these agents are competitive: they each of randomly select a location in the simulated world, and randomly test a particular orientation (eg the East dimension/distance) to see if it matches the reading that the laser sensors on the wheelchair provided in the same dimension. If they do match, this is potential solution; if they do not match, there is no benefit to continuing evaluation of the other dimensions at this location — it cannot be the location searched for. Through this the agents perform a partial search of the search space.
If the agent evaluates a particular dimension, and finds that it matches one of the dimensions were looking for, it becomes “active”; otherwise the agent remains “inactive”. During what is termed as the diffusion phase of the algorithm, the position of active agents can cross to inactive agents. Each in active agent randomly selects another agent in the network: if this selected agent is active, the agent doing the selection copies the search space mapping of the active agent; if the selected agent is not active, the agent doing the selecting reselect another location at random. This means active agents all represent possible solutions.
As I understand it, on each iteration of the algorithm a new orientation is evaluated by each agent: the active agents evaluate another dimension, eg if an agent had previously assessed North East and found it to be a match, it now selects another dimension from the same location in the map again, and evaluates that dimension — for example the agent now selects the East dimension. If this newly selected dimension is correct when evaluated against the sensor readings, this agent remains active, and become inactive if else. This means that the probability of an agent solution being correct, rather than a false-positive, increases with each iteration that the agent remains active. The process continues until termination conditions are fulfilled.
As can be seen from the explanation above the search algorithm changes from being competitive to acting in a cooperative fashion, and the more likely solutions attract more agent-interest on each iteration the algorithm. Now needless to say there are few differences between this algorithm and that of particle swarm optimisation:
Firstly the issue of topology. With particle swarm optimisation the agents involved in the simulation are locked together in a topological network, with the particles only really be interested in the findings of their topologically linked neighbours. In stochastic diffusion search, however, no such network it appears to exist, and each agent randomly selects its next “neighbour” to “communicate” about locations of potential solutions.
In stochastic diffusion search there is a definite move in the simulation from being competitive to being cooperative. In particle swarm optimisation, from what I can tell the algorithm is permanently cooperative: the agents do not compete with resources, and welcomely share their knowledge with other particles in the swarm.
…more to follow
June 16, 2007
Sat: on the hunt for disadvantages of PSO …
Continuing last weeks’ search, today I’m looking for areas where PSO is lacking. From what I’ve seen so far, I haven’t heard much said against it, other than the mathematics is not truly understood, there can be tendency to early convergence, and it is necessary to know something about the problem space to calibrate the settings of the algorithm … but that’s it, to date. However, I’ve been given the tip of looking at Stochastic Diffusion Search (SDS), so currently having a little hunt through the literature …
Having gone through a number of parpers, gone to sleep on it all …
Thu: (restrospectively) Still coding the main method …
Spent today still trying to figure out how to have a method in main which can be called by a later class. I think I understand the theory of what I’m trying to do — however the implementation still seems to be beyond me! Have placed some requests for help out on the Interweb — Javaranch, emailing Java experts I know, etc — so hopefully help will be on it’s way soon.
June 10, 2007
Sun: ever forwards with the PSO report …
I spent yesterday and today working on the particle swarm report, and I think the background section is nearly there. The only issue is struggling to find anything to discuss: something like difficulties in application, areas where an alternative method is preferred and why, disadvantages to the method, etc. Surely it cannot be an optimisation panacea? This link appears to have a few disadvantages of the method, but there’s got to be more somewhere …
June 3, 2007
Sun: Add’l links that may be of interest …
The IEEE Transactions on Evolutionary Computation seems to have had a PSO special in Jun 2004: link.
Sun 3-Jun: writing …
Today back on the case of writing the PSO report: writing u psome notes I’d taken a few weeks back, to taking more notes, and writing those up.
Having written up those notes, I’m now trying to finding the answer to everything else I want to put into this report. From reading the notes Will passed me about writing a technical report, coupled with other technical report information I found on the web, I suppose I now have more of a roadmap about what is to go into the report, which I will be using to guide me forwards.
At the moment, I’m trying to find out where PSO has been used successfully and unsuccessfully — I suppose where has it been applied to. I have come across a citation that looks to be of interest: Research on particle swarm optimization: a review, by Mei-Ping Song and Guo-Chang Gu (Coll. of Comput. Sci. & Technol., Harbin Eng. Univ., China), which appears in: Machine Learning and Cybernetics, 2004. Proceedings of 2004 International Conference on (Publication Date: 26-29 Aug. 2004, Volume: 4, On page(s): 2236- 2241 vol.4, ISBN: 0-7803-8403-2).
There does appear to be a fair amount of information on the web: unfortunately a lot of it appears to be restricted access, which is annoying … However, I’m planning on starting to look through Rui Mendes PhD report, to see what he has to say.
