Propagation and Back-Propagation Diffusion through Neighborhoods Algorithm
Propagation and Back-Propagation Diffusion through Neighborhoods Algorithm or PB-DNA is an optimization heuristic that belongs to Ant Colony Optimization Algorithms (ACA).
Concept[edit]
The approach is inspired by behavior of some species of ants (Solenopsis Invicta) in distress situation.
In an exploration space that may be a non-structured organization without centralized control entities, autonomous and elementary threads (called ant-agents) use the direct communication diffusion process by propagation and back-propagation explorations in order to extract the global minimum from a set of local minima.
Ants are behaviorally much ingenuous insects and have a very restricted memory that looks to have a large haphazard component. Performing as a cooperative however, they achieve an assortment of very intricate and complex tasks with an amazing consistency and reliability. The complex social behaviors of ants have been much studied by science, and computer scientists are now finding that these behavior patterns can provide models for solving problematic combinatorial optimization problems.
The researchers are aware that ants dispatch information by stigmergy through chemical substances called pheromones. But, this communication channel is not the unique support, some ants’ species that lack pheromone as “Cataglyphis Niger” (desert ants), use direct messages to forage individually, with no dependence on pheromone trails. Besides, the experiments with other species, able to diffuse pheromone like “Solenopsis Invicta” (red fire ants) demonstrate that the call for distress or danger may be acoustic.[2] These experiments have proved that these ants emit attack call, similar to the alarm that sounds in situation of threats. Obviously, the sound is faster than pheromone diffusion in the air, and ants rely on noise in urgent situations.
The algorithm is a heuristic inspired by behavior of ant specie of “Solenopsis Invicta” in situations of threats.
Unlike many ant-inspired algorithms that emit stigmergic mechanism of pheromone as ACA. PB-DNA is based on direct acoustic communication (one-to-one) of red fire ants. It is somehow proximate to the well-known SDS (Stochastic Diffusion Search) algorithm of Bishop. Both of algorithms -SDS and PB-DNA- belong to the family of swarm intelligence based on direct diffusion. Though, in contrast to SDS that uses an analogy of the ‘tandem calling’ mechanism of “Leptothorax Acervorum” ants, PB-DNA is inspired by “attack calling” of “Solenopsis Invicta” ants in situation of danger [2]
To avoid a combinatory explosion an ultimate propagation level (UPL) is defined. It is the maximum level of exploration that should not be exceeded. This threshold allows avoiding the divergence and the combinatory explosion. This means that the solution is not guaranteed in case after achieving the UPL, no optimum is found.
Visited neighbors are marked by a vector.
Phases[edit]
Phase 1: Propagation of Constraints[edit]
In situation of distress, the ant-agent initiator triggers the propagation process. It sends a matrix of constraints where each ant-agent computes its utility function upon this matrix. This process is repeated until the maximum level of exploration is reached or in case there are no more new neighbors to visit. The result of this phase is a tree of local minima where the root is the first neighborhood of the ant-agent initiator and the leaves are all the neighborhoods of the last visited levels in propagation trails. Leaves are last visited nodes in one of the two following cases:
The exploration of a neighborhood queue has reached the ultimate level of propagation,
The ant-agent does not have more neighbors to explore.
This tree of local minima has to be optimized and restricted in order to extract the global minimum. This constitutes the second phase of backpropagation.
Phase 2: Backpropagation of Local Minima[edit]
The phases of backpropagation and propagation proceed in parallel. Nevertheless, in each branch (propagation track), the backpropagation starts after the propagation. Once the leave is reached in the exploration branch, the backpropagation process is triggered automatically by ascending the tree. In the backpropagation phase, the exploration of the tree goes up from the leaves to the root. Each neighborhood communicates its local minimum to its connections until reaching the root (ant-agent initiator) that marks the end of the process and selects the cluster corresponding to the global minimum.
References[edit]
- ↑ Gamoura-Chehbi, Samia (2016-11-04). "Smart Workload Automation by Swarm Intelligence within the Wide Cloud Computing". International Journal of Mechanical Engineering and Automation. 3 (4). Retrieved 2017-02-04.
- ↑ 2.0 2.1 Hickling, Robert; Wei, Wei; Lambert, Lavone (1996). "Acoustic communication by imported fire ants". Journal of the Acoustical Society of America. 99 (4): 2557–2574. Bibcode:1996ASAJ...99.2557H. doi:10.1121/1.415201.
This article "Propagation and Back-Propagation Diffusion through Neighborhoods Algorithm" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Propagation and Back-Propagation Diffusion through Neighborhoods Algorithm. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
