Entries Tagged as 'algorithm'

Memetic algorithm

Memetic algorithms is a population-based approach for heuristic search in optimization problems. For some problem domains they have been shown to be more efficient than genetic algorithms. Some researchers view them as hybrid genetic algorithms or parallel genetic algorithms.

From the view of Genetic Algorithm, if GA is combined with some kinds of Local Search, the algorithm is termed as memetic algorithm.

Memetic algorithms are the subject of intense scientific research and have been successfully applied to a multitude of real-world problems ranging from the construction of university exam timetables, to the prediction of protein structures and the design of spacecraft trajectories.


References

  • P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms, Caltech Concurrent Computation Program, C3P Report 826, (1989).
  • Recent Advances in Memetic Algorithms, Series: Studies in Fuzziness and Soft Computing, Vol. 166, Hart, William E.; Krasnogor, N.; Smith, J.E. (Eds.), 2005
  • Special Issue on Memetic Algorithms, IEEE Transactions on Systems, Man and Cybernetics - Part B, Vol. 37, No. 1, Ong Y.S.; Krasnogor, N.; Ishibuchi H. (Eds.), Feb 2007.
  • A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE Transactions on Evolutionary Computation, 9(5):474- 488, N. Krasnogor and J.E. Smith. 2005.

Tags: Uncategorized by admin
No Comments »

Ricart-Agrawala algorithm

The Ricart-Agrawala Algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm is an extension and optimization of Lamport’s Distributed Mutual Exclusion Algorithm, by removing the need for <math>release</math> messages.


Algorithm


Terminology

  • A site is any computing device which is running the Ricart-Agrawala Algorithm
  • For any one request of the critical section:
    • The requesting site is the site which is requesting entry into the critical section.
    • The receiving site is every other site which is receiving the request from the requesting site.
  • ts refers to the local timestamp of the system according to its logical clock.


Algorithm

Requesting Site:

  • A requesting site <math>P_i</math> sends a message <math>request(ts, i)</math> to all sites.

Receiving Site:

  • Upon reception of a <math>request(ts, i)</math> message, the receiving site <math>P_j</math> will immediately send a timestamped <math>reply(ts, j)</math> message if and only if:

    • <math>P_j</math> is not requesting or executing the critical section OR
    • <math>P_j</math> is requesting the critical section but sent a request with a higher timestamp than the timestamp of <math>P_i</math>
  • Otherwise, <math>P_j</math> will defer the <math>reply</math> message.

Critical Section:

  • Site <math>P_i</math> enters its critical section only after receiving all <math>reply</math> messages.
  • Upon exiting the critical section, <math>P_i</math> sends all deferred <math>reply</math> messages.


Performance

  • Number of network messages; 2*(N-1)
  • Synchronization Delays: One message propagation delay


Common Optimizations

Once site <math>P_i</math> has received a <math>reply</math> message from site <math>P_j</math>, site <math>P_i</math> may enter the critical section without receiving permission from <math>P_j</math> until <math>P_i</math> has sent a <math>reply</math> message to <math>P_j</math>


Problems

One of the problems in this algorithm is failure of a node. In such a situation a process may starve forever.
This problem can be solved by detecting failure of nodes after some timeout.


See also

  • Lamport’s Bakery Algorithm
  • Lamport’s Distributed Mutual Exclusion Algorithm
  • Maekawa’s Algorithm
  • Suzuki-Kasami’s Algorithm
  • Raymond’s Algorithm

Diffusing update algorithm

DUAL stands for Diffusing Update ALgorithm and is the algorithm used by EIGRP to calculate and create routing tables based on certain criteria.

DUAL is used to ensure a path to a network and provide a loopless routing environment. In order to help ensure delivery of a packet to a network, DUAL sends out query packets to its adjacent neighbors, or directly connected routers. As query packets are sent out, each router continues to forward the query packet until a router responds with a reply packet that has information on how to reach the specific network. When the reply packets are received by the router that sent out the query packets, DUAL calculates which route will be the successor and feasible successor.</br>
The successor is the main route. It is the shortest, most efficient route to a network that DUAL can find. The route to the successor router is calculated using delay, bandwidth, and other factors. The feasible successor is the backup route. The router that is the feasible successor has the second-best route to the network. It is not necessary for EIGRP to have a feasible successor.
</br>
When the successor or feasible successor goes down, DUAL sends out query packets to each router, and places the route in its routing table as “active.” When the route is active, DUAL is recalculating the path to the new network. Once it is calculated, the route is marked as “passive,” and normal network operation can resume.</br></br>


External links

  • The DUAL Algorithm

Tags: Uncategorized by admin
No Comments »