INTELLIGENT WATER DROPS MODULE

Intelligent Water Drops(IWD) algorithm, or the IWD algorithm, is a swarm-based nature-inspired optimization algorithm. This algorithm contains a few essential elements of natural water drops and actions and reactions that occur between river's bed and the water drops that flow within. The IWD algorithm may fall into the category of Swarm intelligence and Metaheuristic. Intrinsically, the IWD algorithm can be used for Combinatorial optimization. However, it may be adapted for continuous optimization too. The IWD was first introduced by Shah-hosseini for the traveling salesman problem in 2007.

INSTALLATION

Download the Package manually and Install using:

python setup.py install

or:

pip install IWD

Usage

The module consists of two versions of the IWD Algorithm. The first version (iwd) implements the original IWD Algorithm, whereas the second version, Modified Intelligent Water Drops Algorithm (miwd) implements a relatively recent concept intoduced in IWD to avoid local traps.

Import 'iwd' or 'miwd' as follows:

from IWD import iwd

or:

from IWD import miwd

Initialization

The following could be used for both 'iwd' and 'miwd'.

Use parameters_initialization() class to create and instantiate an object of parameters_initailization class say parameters as follows:

parameters = iwd.parameters_initialization()

or:

parameters = miwd.parameters_initialization()

It is mandatory to provide the number of nodes(or cities) and the distance_matrix(a JSON dictionary) to parameters as shown below:

parameters.initialize_graph(number_of_nodes, distance_matrix)

Structure of distance_matrix is a JSON dictionary consisting of edge weights as shown in an example below for a graph with 4 nodes(cities)

distance_matrix =:

{
        0: {
                0: 0,
                1: 34,
                2: 56,
                3: 79
                },
        1: {
                0: 45,
                1: 0,
                2: 13,
                3: 77
                },
        2: {
                0: 89,
                1: 56,
                2: 0,
                3: 75
                },
        3: {
                0: 46,
                1: 48,
                2: 31,
                3: 0
                }
}

IWD uses Static and Dynamic parameters to approximate tour for TSP. Static Parameters are fixed during iterations. While dynamic parameters are constantly modified during the process. Static and Dynamic parameters must be set suitably for obtaining an accurate solution. If static or dynamic parameters are not provided, the module assumes default values shown below which may or may not provide perfect convergence with just a few iterations.

The instantiated object 'parameters' consists of a dictionary which consists of initialized static and dynamic parameters as follows:

parameters.parameter_list

The parameters contained in the 'parameter_list' are as folows:

The static parameters are:

  • Static Parameters for soil comprise the constants defined in : 'soil_parameters'
  • 'soil_parameters' further consist of list tuple [a_s, b_s, c_s], each of which could assume some value.
  • Static Parameters for velocity comprise the constants defined in : 'velocity_parameters'
  • 'velocity_parameters' further consist of list tuple [a_v, b_v, c_v], each of which could assume some value.
  • Initial amount of soil on all edges: 'initial_amount_of_soil'
  • Initial amount of velocity: 'init_vel'
  • Parameter for local updating, value lies between (0,1) : 'p_n'
  • Parameter for Global updating, value lies between (0,1) : 'p_iwd'
  • Maximum number of iterations: 'maximum_iterations'
  • Heuristic Undesirability : 'HUD'
  • In the case of 'miwd', additional constant is introduced: 'alpha'

The dynamic parameters are:

  • Iteration Count, usually zero initially: 'iteration_count'
  • Amount of soil on edges: 'soil'
  • Velocity of iwd: 'velocity'

How to access and set parameters is shown in detail below:

soil_parameters, default = [1, 0.01, 1]

parameters.parameter_list['soil_parameters']

a_s, default = 1

parameters.parameter_list['soil_parameters'][0]

b_s, default = 0.01

parameters.parameter_list['soil_parameters'][1]

c_s, default = 1

parameters.parameter_list['soil_parameters'][2]

velocity_parameters, default = [1, 0.01, 1]

parameters.parameter_list['velocity_parameters']

a_v, default = 1

parameters.parameter_list['velocity_parameters'][0]

b_v, default = 0.01

parameters.parameter_list['velocity_parameters'][1]

c_v, default = 1

parameters.parameter_list['velocity_parameters'][2]

maximum_iterations, default = 1000

parameters.parameter_list['maximum_iterations']

iteration_count, default initial value = 0

parameters.parameter_list['iteration_count']

initial_amount_of_soil, default = 10000

parameters.parameter_list['initial_amount_of_soil']

p_n, default = 0.9

parameters.parameter_list['p_n']

p_iwd, default = 0.9

parameters.parameter_list['p_iwd']

soil, It is a dictionary consisting of amount of soil between all edges. It is initialized with 'Initial_amount_of_soil'

parameters.parameter_list['soil']

HUD, it is a dictionary defining the undesirability of choosing an edge from current node. It is a dictionary usually initialized with distance_matrix for solving TSP

parameters.prameter_list['HUD']

Computation

After the Parameters are initialized as desired, the parameter_list could be passed to compute() function to get an approximate TSP tour as shown below:

solution = iwd.compute(parameter_list)

or:

solution = miwd.compute(parameter_list)

The value returned by compute() is a list consisting of:

  • Optimum TSP tour:

    solution[0]

  • Maximum Quality:

    solution[1]

  • Cost of TSP tour:

    solution[2]

HOME PAGE

RFERENCES