jump to navigation

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! :D ) 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? :D

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 ClassExample file for testing

Note: It’s not well-documented, I wrote it quickly!