AntNet September 23, 2007
Posted by nhabibi in Artificial Intelligence, Internet, Machine Learning.3 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?
***3-Please don’t contact me for sending the code. It’s not exactly correct and so not so much helpful. Thanks.
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!
