AntNet September 23, 2007
Posted by nhabibi in Artificial Intelligence, Internet, Machine Learning.2 comments
AntNet routing algorithm is a mobile agents system that is based on Ant Colony Optimization (ACO) method (refer to perevious post). Informally, the AntNet algorithm and its main characteristics can be summarized as follows:
- At regular intervals, and concurrently with the data traffic, from each network node mobile agents are asynchronously launched towards randomly selected destination nodes.
- Agents act concurrently and independently, and communicate in an indirect way, through the information they read and write locally to the nodes.
- Each agent searches for a minimum cost path joining its source and destination nodes.
- Each agent moves step-by-step towards its destination node. At each intermediate node a greedy stochastic policy is applied to choose the next node to move to. The policy makes use of (i) local agent-generated and maintained information, (ii) local problem-dependent heuristic information, and (iii) agent-private information.
-While moving, the agents collect information about the time length, the congestion status and the node identifiers of the followed path.
- Once they have arrived at the destination, the agents go back to their source nodes by moving along the same path as before but in the opposite direction.
- During this backward travel, local models of the network status and the local routing table of each visited node are modified by the agents as a function of the path they followed and of its goodness.
- Once they have returned to their source node, the agents die.
(Source: AntNet original paper)
OPNET, is a network simulator that can be used to design networks with different size and components, and to implement, test and evaluate protocols.
I implemented AntNet by OPNET. The difficult point was learning OPNET! It’s a little tricky, but very well-defined and powerful. (Of course when you learned! 
) The best starting point is OPNET tutorials, inside software. In short, you first define network packets, links and nodes separately and then integrate them. Protocols can be coded in C/C++.
My report describe AntNet algorithm in detail and its implementation by OPNET, in Persian.
More information:
G. Caro & M. Dorigo paper: AntNet: Distributed Stigmergetic Control for communication networks
PS:
1-A network specialist says that AntNet is not applicable for large networks, like internet, due to high volume of routing related messages. I think it’s true.
2- What a long post! Didn’t you get bored?
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!
