Editorial special issue on parallel natureinspir

Authors: Grégoire Danoy

Publish Date: 2012/09/04

Volume: 63, Issue: 3, Pages: 737-739

PDF Link

Abstract

Natureinspired optimization techniques have proven to efficiently solve a wide range of problems related to parallel computing and more generally to computer science In addition the intrinsic parallelization and distribution capabilities of natureinspired techniques can been exploited in order to provide powerful optimization solutions However many research challenges remain to be addressed such as the design and implementation of efficient natureinspired optimization algorithms for massively parallel and distributed architectures and their application to realworld problemsThis special issue is composed of extended versions of selected best papers presented at the 14th International Workshop on Nature Inspired Distributed Computing NIDISC 2011 These articles provide a good theoretical and practical overview of natureinspired optimization techniques and their application to metaheuristics and parallel/distributed computing In the following we propose a brief overview of the different contributions included in this special issueIn the first paper by EA Macedo et al “Multiple Biological Sequence Alignment in Heterogeneous Multicore Clusters with UserSelectable Task Allocation Policies” a parallel version of a heuristic iterative algorithm DIALIGNTX is proposed to tackle the Multiple Sequence Alignment MSA problem a wellknown NPHard bioinformatics problem The authors empirically demonstrate the execution time reduction obtained with the proposed parallel implementation as well as the impact of the choice of the allocation policyThe second paper by P Koros̆ec et al “Multicore Implementation of the Differential AntStigmergy Algorithm” also proposes to parallelize a stateoftheart optimization algorithm the Differential AntStigmergy algorithm DASA which is a variant of the Ant Colony Optimization ACO for numerical continuous optimization The authors focus on DASA parallelization on homogeneous multicore architectures and propose two parallel variants shared memory PDASA and distributed memory DDASA They experimentally show the execution time gains on different blackbox problems and profile the suitability of PDASA for all types of problems while DDASA requires complex ones However PDASA performance requires an expensive hardware architecture manycore platformThe third paper by J Cecilia et al “Enhancing GPU Parallelism in Natureinspired Algorithms” also tackles the parallelization of two natureinspired optimization algorithms Ant Colony Optimization ACO and Membrane Systems also named P systems but on a different hardware architecture ie Graphics Processing Units GPUs Indeed ACO inspired by the ant foraging behavior and P systems that mimic the biochemical process within cells are both inherently massively parallel The authors have conducted an extensive study on their implementation tuning on different GPU platforms Their performance is evaluated on two wellknown problem classes Satisfiability problems SAT and Traveling Salesman Problems TSP Experimental results demonstrate that with an efficient implementation speedup factors of 4–5 orders of magnitude can be reachedThe fourth paper by PD Yoo et al “Combining Analytic Kernel Models for EnergyEfficient Data Modeling and Classification” tackles one key aspect in data center operation ie energy consumption This work focuses on modeling and classifying/predicting largescale data with an accuracy equivalent to the stateoftheart while minimizing its computational cost To this end the authors propose a semiparametric framework that combines two different kernelbased and analytic approaches ie a global nonparametric kernel regression model KNearest Neighbor kNN with a local parametric vectorfield reconstruction VFRC A natureinspired optimization approach the binary particle swarm optimization bPSO is additionally used for improving the VFRC classification task Experimental results on largescale benchmark datasets and comparison to stateoftheart classification approaches show that the approach reduces the computational complexity of the learning process while ensuring a better or similar test errorThe fifth paper by A Piwonska et al “Learning Cellular Automata Rules for Binary Classification Problem” also focuses on clustering It proposes to use Genetic Algorithms GAs for discovering twodimensional Cellular Automata CA rules to perform binary classification The experiments conducted on three classification problems outline the performance and scalability of the discovered rules compared to knearest neighbors algorithms kNN and humandesigned heuristic rulesIn the sixth paper by B Dorronsoro et al “Cellular Genetic Algorithms without Additional Parameters” new natureinspired algorithms are proposed ie parameterless variants of the cellular genetic algorithm cGA a wellknown decentralized metaheuristic These algorithms have already proven to perform well on many hard optimization problems and various parallel versions have been developed for different architectures such as GPUs or clusters However their performance highly relies on their parameterization which includes typical GA parameters and some cGA specific ones ie population and neighborhood shapes The authors thus avoid these additional parameters setting with selfadaptive cGAs which combine population shape adaptation strategies based on convergence speed and neighborhood shape adaptation strategies that rely on the allocated individual fitness Their accuracy and efficiency is experimentally proven against six other cGAs on a large set of continuous and combinatorial optimization benchmarksThe seventh paper by M Khouadjia et al “MultiEnvironmental Cooperative Parallel Metaheuristics for Solving Dynamic Optimization Problems” proposes MEMSO a MultiEnvironmental MultiSwarm Optimizer MEMSO uses a parallel cooperative model where independent metaheuristics are run in parallel and exchange information about their search in different subproblems Indeed such multipopulation approaches typically perform well in tracking the moving optimum of dynamic problems The better performance of the proposed MEMSO compared to other metaheuristics is empirically assessed on the dynamic vehicle routing problem DVRP A study of different integration policies is also provided These experiments are conducted on the Grid’5000 testbed an experimental grid of more than 5000 coresIn the last paper by M Seredynski et al “Analysing the Development of Cooperation in MANETs” the authors propose to use evolutionary game theory for the search of the fittest packet relaying strategies in Mobile Ad hoc NETworks MANETs The authors analyze incentives for cooperation in packet relaying where nodes use their local trust information to estimate the degree of cooperation DOC of other nodes which will trigger the decision to forward the information The best strategies for different network sizes were experimentally found using the proposed natureinspired approach In addition the authors have studied the robustness of the obtained strategies during the evolutionary process ie their stability against the remaining strategies the influence of the initial network configuration distribution of initial strategies and of selfish never relay and altruistic always relay strategies They demonstrate that cooperation will emerge in two network settings small network or network with many selfish nodesThe guest editor would like to express his sincere gratitude to the EditorinChief of the Journal of Supercomputing Professor Hamid R Arabnia for giving the opportunity to organize this special issue and for his continuous support He also would like to deeply thank the Springer team and Editorial Office members for their precious help In addition he is very grateful to the anonymous reviewers for their time and expertise Finally he would like to thank all the authors for their contributions and effort without which this special issue would not be possible

Keywords: