IV. PROPOSED ALGORITHM
In this article, a new approach based on ant colony optimization is proposed. In Antz Algorithm which is proposed in , ants choose the lightest node from the node’s table according to the nodes’ loads. When an ant selects a node as the lightest node, this node may have been chosen as the lightest node sooner in the table of another node, and the ant, corresponding to that node has chosen this node earlier than this ant, but the current ant does not know about this selection and it chooses this node as the lightest node too. So, whenever an ant meets a node, there must be a counter which counts the ants, meeting this node and must take this number as a probability that this node will be taken as the lightest node by other ants. This number is noted by the ant and this factor and the node`s load are the parameters to choose the lightest node.
A. Description of the Algorithm
The proposed algorithm is inspired from ant colony optimization. In the real world, ...view middle of the document...
They look at the paths and they realize one of the paths has stronger pheromone. So, they select this path as the shortest one too (Step 4). This procedure is shown in Fig. 5.
Fig 5. The act of ants in real world
This concept is used in ant colony optimization. In this approach, pheromone is as the nodes’ tables and will be a leader for other ants to find the lightest node sooner.
In Table 1, the proposed algorithm is shown. Whenever a job is inserted to the Grid, an ant is initialized for it. In the first steps, the ant begins to wander in the environment randomly with a probability (Probability) in order to fill its table and the nodes’ tables. The ant’s table contains information about the nodes that this ant have visited in its route and the node’s table contains information about other nodes’ load which are placed in this table when ants visited this node.
When the ant reaches to a node, it notes the load of the node in its table and increases the counter, which is defined as the number of ants, passed this node and notes it too (Ant_Counter). Then, the ant puts its table in the node’s table and simultaneously, if there is any information in the node’s table, the ant will note it in its table and if both of them contain the same information, the most updated one will replace to both tables (Update). As time passes, the next ant`s movement should be more dependent on the node’s table and it must choose the next node from the node’s table. This one is achieved by decreasing the factor Decrease with the factor Probability.
For choosing the next node from node’s table, the ant selects the current node as the best node and computes a factor which is the multiple of the node`s load and the Ant_Counter of the node, and named it as M. Then, it begins to compare this factor of the current node with this factor of each entry of the node’s table. The entry which has the least M, will be the lightest node and in case of a tie, the ant chooses one with an equal probability. The algorithm for choosing the next node from the node’s table is shown in Table 2. When the ant finds the lightest node from the node’s table, it moves to it and this process will be continued until the ant goes the MaxSteps number of steps. After these steps, the lightest node is selected and the job will be delivered to it.