want intelligent water drops algorithm code in c or java is applied on the travelling sales man theorem
Posts: 810
Threads: 0
Joined: Jul 2016
Description
This project deals with the Intelligent Water Drops algorithm or the IWD algorithm. The IWD algorithm is a population & nature-inspired combinatorial optimization algorithm. It tries to imitate the behavior that natural water drops conduct in river beds where they create complex paths that seem optimistic considering the environment, obstacles, and the surrounding terrain.
One way to use the IWD algorithm is to map our optimization problem into a graph over which Intelligent Water Drops (IWDs) travel from node to node to gradually create complete solutions. During this trip, the soli of the graph deposited on the links of the graph are changed and little by little the optimal paths will hold less soil in comparison to other possible paths.
It is also possible to solve continuous optimization problems by the IWD algorithm. One attempt is the IWD-CO (IWD for Continuous Optimization)
In this project, the focus is to gradually present implemented IWD-based algorithms.
Introduction
Almost every IWD algorithm is composed of two parts: a graph that plays the role of distributed memory on which soils of different edges are preserved, and the moving part of the IWD algorithm, which is a few number of Intelligent water drops. These Intelligent Water Drops (IWDs) both compete and cooperate to find better solutions and by changing soils of the graph, the paths to better solutions become more reachable. It is mentioned that the IWD-based algorithms need at least two IWDs to work.
Applications
Some of the researches performed with the IWD-based algorithms for different applications are given below:
Multi-dimensional Knapsack problem (MKP) [3]
Air Robot Path Planning [4]
Vehicle routing problem[5][6]
MANET Routing algorithm [7]
Economic Load Dispatch [8]
Travelling salesman problem (TSP) [9]
texture feature selection [10]
Automatic multilevel thresholding using a modified Otsu’s criterion [11]
Continuous optimization [12]
Job shop scheduling [13]
Steiner tree problem [14]
Maximum Clique problem [15]
Optimal data aggregation tree in wireless sensor networks [16]
Test data generation based on test path discovery [17]
Code coverage
Basic principles of the IWD algorithm
Water drops that flow in rivers, lakes, and seas are the sources of inspiration for
developing the IWD. This intelligence is more obvious in rivers which find their ways
to lakes, seas, or oceans despite many different kinds of obstacles on their ways. In the
water drops of a river, the gravitational force of the earth provides the tendency for
flowing toward the destination. If there were no obstacles or barriers, the water drops
would follow a straight path toward the destination, which is the shortest path from
the source to the destination. However, due to different kinds of obstacles in their way
to the destination, which constrain the path construction, the real path has to be
different from the ideal path and lots of twists and turns in the river path is observed.
The interesting point is that this constructed path seems to be optimum in terms of
distance from the destination and the constraints of the environment.
Convergence properties of the IWD algorithm
In this section, the purpose is to show that the IWD algorithm is able to find the optimal
solution at least once during its lifetime if the number of iterations that the algorithm is
run be sufficiently big. For a few particular ACO algorithms and careful setting of
parameters of the ACO, such property has been shown to exist and this kind of
convergence is called convergence in value (Dorigo and Stutzle, 2004). In the following,
the convergence in value for the IWD algorithm is investigated.
For any IWD in the proposed algorithm, the next node of the IWD is found
probabilistically by using equation (16). Therefore, as long as the probability of
visiting any node is above zero, in the long run, it is expected with probability one that
an IWD of the algorithm will choose that node at some iteration.
Any solution S of the given problem is composed of a number of nodes {np, nq, ... ,
nr} selected by an IWD during an iteration of the algorithm. As a result, if it is shown
that the chance of selecting any node nk in the graph (N, E) of the problem is above zero,
then the chance of finding any feasible solution from the set of all solutions of the
problem is nonzero. As a consequence, if it is proved that there is positive chance for
any feasible solution to be found by an IWD in an iteration of the algorithm, it will be
guaranteed that the optimal solution is found. Because, once an IWD finds an optimal
solution, that solution becomes the iteration-best solution in the algorithm and thus the
total-best solution is updated to the newly found optimal solution as expressed in Step 8
of the algorithm.