# Memetic Chains for Improving the Local Wireless Sensor Networks Localization in Urban Scenarios +
## 5 Memetic Algorithm Chains for the Node Location Problem
### MA-VND-Chains Pseudo-Code
#### 5.2.4 VND LS  
There are different optimization techniques based a neighborhood structure that remains constant during every execution (e.g., Iterated Local Search (ILS) [70]). As the algorithm advances, a rigid structure of the neighborhood ceases part of the effectiveness of the process [71]. In addition, an inefficient search process has a higher computational cost than a more flexible and adapted process to the problem which requires the knowledge of the problem.  
The metaheuristic technique VNS solves global optimization problems by changes of neighborhoods. VNS looks for finding in each iteration a better local neighbor for changing the current individual. This ensures that the algorithm will never get a worse result. The method has a deterministic version named highest descent and another variant denominated first descent [72].  
In this paper, we apply a Variable Neighborhood Descent algorithm (VND) [73] which explores 26 potential neighborhood movements for each sensor. The VND LS explores all the neighborhood in order to obtain the best-adapted individual in a bounded region (i.e., it is the variant \"best improvement\" instead of the \"steepest descent\"). Since all the solutions are scanned, the final result will not change with a different contact order. In each iteration, the analysis of the fitness in the VND algorithm is performed through a pseudo-fitness function in order to compute the progress of the VND procedure.  
In the descent-phase, it is difficult to establish the number of neighborhoods to examine, therefore, it is essential to introduce new parameters that allow us to generate heterogeneity in the neighborhood structures and the complementarity of them. Hence, we propose that the structures used in the neighborhoods are dynamic and change depending on the room for improvement achieved in the bounded region above. This method allows for increasing the chances for finding a better global individual by VND compared with a homogeneous structure.  
VND begins with the selection of a sensor in order to start the deterministic descent-phase. Every individual is formed of a set of sensors. We randomly select in each iteration the starting sensor for the application of the LS procedure. The randomness favors the diversity of the solution each time the individual is selected by the LS. The determination of the neighborhood structure needs the estimation of a k-distance metric. This parameter modifies the distance that the neighbors occupy concerning the sensor of analysis. When the best neighbor offers a large improvement, the k-distance factor increases in order to reduce the number of iterations needed to obtain the global best location for the sensor.  
Depending on the geometry of the sensor distribution, the sensor has a combined LOS/NLOS linkage with the target. In the analysis of a neighborhood, the existence ofenhanced individuals which convert an NLOS link to a LOS link causes the value obtained by the pseudo-fitness function of our algorithm to present a large improvement that is awarded with a higher k-distance. Thus, the computational speed required to obtain the best possible individual is lower than with a low and constant k-distance value.  
The permutation of the sensors sequence in each epoch arises different LS results, therefore, it is necessary to store the number of times that the individual has not been improved by a LS procedure, \(n_{LS}\), and the step size used for each sensor in each individual, as detailed above. The memory will be responsible for storing these values so that the next LS uses the parameters calculated by the previous LS iteration to continue the search for the best individual for its bounded region.