Swarm Intelligence September 22, 2007
Posted by nhabibi in Artificial Intelligence, Soft Computing.1 comment so far
Swarm intelligence (SI) is an artificial intelligence technique based around the study of collective behavior in decentralized, self-organized systems.
SI systems are typically made up of a population of simple agents interacting locally with one another and with their environment. Although there is normally no centralized control structure dictating how individual agents should behave, local interactions between such agents often lead to the emergence of global behavior. Examples of systems like this can be found in nature, including ant colonies, bird flocking, bacterial growth, and fish schooling.
(source: Wikipedia)
Several SI-based algorithms are proposed, like Ant Colony Optimization (ACO), Particle Swarm Intelligence (PSO), Stochastic Diffusion Search (SDS), etc. These algorithms are applied to an impressive number of optimization problems.
ACO is based on the behavior of real ants for finding food. This behavior can be described as follow (a little long, but intresting 
):
In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep traveling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food.
Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high as it is laid on the path as fast as it can evaporate. Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.
Thus, when one ant finds a good (short, in other words) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leaves all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with “simulated ants” walking around the graph representing the problem to solve.
(see a good example here.)
You can find my report about Swarm Intelligence here. It introduces SI in general, and Ant Colony Optimization in detail. Also, an ACO-based for Traveling Salesperson problem and a ACO-based routing algorithm, are described.
More information:
- M. Dorigo & G. D. Caro’s paper, the original paper on ACO
- M. Dorigo home page
Hidden Markov Model September 21, 2007
Posted by nhabibi in Artificial Intelligence, Pattern Recognition.1 comment so far
A Hidden Markov Model (HMM) is a statistical model in which the system being modeled is assumed to be a Markov process with unknown parameters, and the challenge is to determine the hidden parameters from the observable parameters. The extracted model parameters can then be used to perform further analysis, for example for pattern recognition applications.
In a regular Markov model, the state is directly visible to the observer, and therefore the state transition probabilities are the only parameters. In a hidden Markov model, the state is not directly visible, but variables influenced by the state are visible. Each state has a probability distribution over the possible output tokens. Therefore the sequence of tokens generated by an HMM gives some information about the sequence of states.
HMM has application in many fields that need to recognize patterns statistically, such as speech recognition, optical character recognition, cryptanalysis, boinformatics, etc.
I ignore describing Hidden Markov Model’s mathematic details here. My report, in Persian, introduces HMM in detail and describes its application in Speech Recognition briefly.
More information:
- A good tutorial from Leeds university
- L. R. Rabiner’s paper on Hidden Markov Model
- HMM Wikipedia page
Fuzzy & Data Minig September 20, 2007
Posted by nhabibi in Artificial Intelligence, Data Mining, Fuzzy, Soft Computing.1 comment so far
Fuzzy sets are sets whose elements have degrees of membership. Fuzzy sets have been introduced by Professor Lotfali Askarzadeh (1965) as an extension of the classical notion of set.
In classical set theory, an element either belongs or does not belong to the set. By contrast, fuzzy set theory an element belongs to the set, with membership degree in interval [0-1].
An example:
Assume that we have four students with bellow scores in biology exam:
Richard, 20
frank, 18
Anna, 14
Juli, 11
We want to define “A = set of Good Student in Biology Class“:
1- in classical set theory: A = {Richard, Frank}
2- in fuzzy set theory: A = { (Richard,1) , (Mark,0.7) , (Anna,0.3) , (Juli,0.1) }
In fact, we have associated a membership degree to each member, according to goodness of their score.
Fuzzy logic is derived from fuzzy set theory dealing with reasoning that is approximate rather than precisely deduced from classical predicate logic.
Fuzzy concept has application in many areas, specially in control systems.
In many topics, after proposing an algorithm, the fuzzy version of the algorithm is proposed and evaluated against the original one.
Here, is our report, in Persian, that introduces data mining in general, Apriori algorithm to extract association rules, a fuzzy-based Apriori algorithm, Decision Tree and fuzzy-based Decision Tree.
More information:
- Zadeh’s 1965 paper on Fuzzy Sets (It has more that 5000 citations till now!)
Detections in Arial Images September 18, 2007
Posted by nhabibi in Artificial Intelligence, Machine Vision.add a comment
Aerial photography is the taking of photographs from the air with a camera mounted, or hand held, on an aircraft, helicopter, balloon, rocket, kite, skydiver or similar vehicle.The use of aerial photography for military purposes was expanded during World War I.
According to photography place, different objects can be present in an aerial image. For example in an urban sense, there are roads, highways, buildings, humans, vehicles, etc.
Vehicle detection in aerial images, has several applications, for example traffic control, urban planning, approximating and simulating air pollution, data gathering for GIS, etc.
You can find a report on Vehicle Detection in aerial images, in Persian, here.
I’ve implemented a program in MATLAB to detect highways and vehicles in grayscale images. This program, has some constraints and assumptions, like any other machine vision system. It’s possible to improve it and add more features. You can find the project report, in Persian, here.
If you are interested in source codes, please contact me.
Machine Vision September 17, 2007
Posted by nhabibi in Artificial Intelligence, Machine Vision.add a comment
Machine Vision is concerned with computational understanding and use of the information present in visual images. In part, computer vision is analogous to the transformation of visual sensation into visual perception in biological vision. The goal of computer vision is primarily to enable engineering systems to model and manipulate the environment by using visual sensing.
MV is an interesting and practical field, but complicated.
For implementing MV algorithms, MATLAB is common. It has a rich Image Processing toolbox. Also, I’ve tried Java 2D API. It’s a little tricky, but ?
PS: In my opinion, the MV and Image Processing pages on wikipedia, aren’t good enough, of course as an exception.
Another Burst! September 16, 2007
Posted by nhabibi in nhabibi.add a comment
I haven’t updated me@wordpress for several months and been busy, specially for 4 last months.
Clearly, working without representing, is nothing! I want to continue and write briefly about some of the subjects I’ve learned and projects I’ve done.
Finally(!!!) I uploaded some photos to Flickr. Feedbacks say that this service is great and really it is.
I went to Mecca and Medina in summer and it was the best experience in my life. I miss everything about it.
Computer Clusters March 22, 2007
Posted by nhabibi in Distributed Computing.1 comment so far
It may be useful to describe briefly some terms related to distributed computing, an interesting and complicated subject.
Computer Cluster: is a group of loosely coupled computers that work together closely so that in many respects they can be viewed as a single computer.
Cluster Types:
1-High-availability clusters: are implemented for improving the availability of services which the cluster provides. They operate by having redundant nodes, which provide service when system components fail.
2-Load-balancing clusters: operate by having all workload come through one or more load-balancing front ends, which then distribute it to a collection of back end servers. It’s referred to as server farm.
3-High-performance clusters: are implemented to provide increased performance by splitting a computational task across many different nodes in the cluster, and are most commonly used in scientific computing.
Grid computing (Grid clusters): a technology closely related to cluster computing. The key difference is that a cluster is a single set of nodes sitting in one location, while a Grid is composed of many clusters and other kinds of resources (e.g. networks, storage facilities). Grids typically support more heterogeneous collections than are commonly supported in clusters.
SunCluster : a High-availability cluster software package for Solaris operating systems. Sun Cluster is a kernel-level clustering software.
Sun Grid: is an on-demand grid computing service operated by Sun Microsystems.The Sun Grid is an open source project with its source code available.
Source : Wikipedia
More info:
SunCluster Tour
A good overview on wikipedia
Berkeley Open Infrastructure for Network Computing
Genetic Algorithm March 21, 2007
Posted by nhabibi in Artificial Intelligence, Machine Learning, Soft Computing.add a comment
Genetic Algorithm (GA) is a search technique to find true or approximate solution, inspired by evolutionary biology such as inheritance, mutation and recombination.
The concept is very simple. Assume we have a problem and a pool of solutions (search space). Typically solution are represented by 1s and 0s.
Each individual has a fitness, according to a defined criteria.
GA does many iterations and terminates when reaches a satisfactory fitness level.
Definitions:
mutate ==> changing 1 to 0 and vise versa in a bit string
crossover ==> combining 2 string (parents) and generating
2 new ones (offspring)
The steps in summary are:
while (max fitness of current generation is below of desired fitness) {
1- select probabilistically some individuals from current population
2- recombine them 2 by 2 (crossover)
3- mutate some of them
4- replace new generation with old one
}
You can see a graphical representation of GA in GA viewer.
An implementation of GA in Java, for playTennis problem: Java Class – Example file for testing
Note: It’s not well-documented, I wrote it quickly!
Java RMI March 20, 2007
Posted by nhabibi in Java, Programming.1 comment so far
The Java Remote Invocation (RMI) is a technology to develop distributed applications more easily. It’s object equivalent of RPC:
Remote method invocation allows applications to call object methods located remotely, sharing resources and processing load across systems. Unlike other systems for remote execution which require that only simple data types or defined structures be passed to and from methods, RMI allows any Java object type to be used – even if the client or server has never encountered it before. RMI allows both client and server to dynamically load new object types as required.
Developing RMI applications, it’s little (?) tricky at first. I use a check-list, every time I want to make one!
There’re many tutorials and samples online, but basic steps, in summary, are: (RPC developers must be familiar with terms)
*Writing an interface (MyInterface) : a description of the methods we will allow remote clients to invoke.
*Implementing the interface (MyClass): implementing the functionality of the above methods.
*Writing a RMI Server (MyServer): a server that makes an instance of MyClass and registers it with a registry.
*Writing a RMI client (MyClient): a client that calls the registry to obtain a reference to the remote object, and calls its methods.
*Compiling: compiling the classes as ordinary with javac command, and, compiling the MyClass with rmic tool. This last one, creates stub and skeleton files
*Running Registry: making a registry ready to listen for incoming request with rmiregistry tool
*Running the Server and Client: running MyServer and MyClient with java command
That’s it!
More on RMI home on sun.
