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
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!)
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!
