Analysis of evolutionary algorithms using multi-objective parameter tuning

Roberto Ugolotti, Stefano Cagnoni

Proceedings of the 2014 conference on Genetic and evolutionary computation, Pag: 1343-1350, 2014

Evolutionary Algorithms (EAs) and other metaheuristics are greatly affected by the choice of their parameters, not only as regards the precision of the solutions found, but also for repeatability, robustness, speed of convergence, and other properties. Most of these performance criteria are often conflicting with one another. In our work, we see the problem of EAs' parameter selection and tuning as a multi-objective optimization problem, in which the criteria to be optimized are precision and speed of convergence. We propose EMOPaT (Evolutionary Multi-Objective Parameter Tuning), a method that uses a well-known multi-objective optimization algorithm (NSGA-II) to find a front of non-dominated parameter sets which produce good results according to these two metrics.

By doing so, we can provide three kinds of results: (i) a method that is able to adapt parameters to a single function, (ii) a comparison between Differential Evolution (DE) and Particle Swarm Optimization (PSO) that takes into consideration both precision and speed, and (iii) an insight into how parameters of DE and PSO affect the performance of these EAs on different benchmark functions.

GPU-based Point Cloud Recognition using Evolutionary Algorithms

Roberto Ugolotti, Giorgio Micconi, Jacopo Aleotti, and Stefano Cagnoni

European Conference on the Applications of Evolutionary Computation, 2014

In this paper, we describe a method for recognizing objects in the form of point clouds acquired with a laser scanner. This method is fully implemented on GPU and uses bio-inspired metaheuristics, namely PSO or DE, to evolve the rigid transformation that best aligns some references extracted from a dataset to the target point cloud. We compare the performance of our method with an established method based on Fast Point Feature Histograms (FPFH). The results prove that FPFH is more reliable under simple and controlled situations, but PSO and DE are more robust with respect to common problems as noise or occlusions.

Multi-Objective Parameter Tuning for PSO-based Point Cloud Localization

Roberto Ugolotti, Stefano Cagnoni

9th Italian Workshop on Artificial Life and Evolutionary Computation, Vol: in press, 2014

It has been largely proven that population-based metaheuristics such as Particle Swarm Optimization (PSO) are severely affected by the choice of their parameters.

In this paper, we use a multi-objective parameter tuning method called EMOPaT (Evolutionary Multi-Objective Parameter Tuning) to optimize PSO when dealing with a real-world optimization task: the localization of an object acquired by a laser scanner in the form of a point cloud. We want to optimize both the time needed to reach a quality threshold and the final alignment between the point cloud and a reference model of the object. Our system is able to generate “fast” and “precise” versions of PSO and, among all the possible configurations which lie between the fastest and the most precise, the ones that give the best trade-offs between precision and speed.

2D-PAGE Texture Classification using Support Vector Machines and Genetic Algorithms - A Hybrid Approach for Texture Image Analysis

Carlos Fernandez-Lozano, Jose A. Seoane, Pablo Mesejo, Youssef S.G. Nashed, Stefano Cagnoni and Julian Dorado

Proc. of the International Conference on Bioinformatics Models, Methods and Algorithms (BIOSTEC'13), Pag: 5-14, 2013

In this paper, a novel texture classification method from two-dimensional electrophoresis gel images is presented. Such a method makes use of textural features that are reduced to a more compact and efficient subset of characteristics by means of a Genetic Algorithm-based feature selection technique. Then, the selected features are used as inputs for a classifier, in this case a Support Vector Machine. The accuracy of the proposed method is around 94%, and has shown to yield statistically better performances than the classification based on the entire feature set. We found that the most decisive and representative features for the textural classification of proteins are those related to the second order co-occurrence matrix. This classification step can be very useful in order to discard over-segmented areas after a protein segmentation or identification process.

Algorithm Configuration using GPU-based Metaheuristics

Roberto Ugolotti, Youssef S.G. Nashed, Pablo Mesejo, Stefano Cagnoni

Proc. of the 15th annual conference companion on Genetic and evolutionary computation (companion), 2013

In this paper we compare GPU-based implementations of three metaheuristics: Particle Swarm Optimization, Differential Evolution, and Scatter Search. A GPU-based implementation, obviously, does not change the general properties of the algorithms. As well, we give for granted that GPU-based implementation of both algorithm and fitness function produces a significant speed-up with respect to a sequential implementation. Accordingly, the main goal of this work has been to fairly assess the efficiency of the GPU-based implementations of the three metaheuristics, based on the statistical analysis of the results they obtain in optimizing a benchmark of twenty functions within a prefixed limited time.

An experimental study on the automatic segmentation of in situ hybridization-derived images

Pablo Mesejo, Stefano Cagnoni

Proc. of the International Conference on Medical Imaging using Bio-Inspired and Soft Computing, Pag: 153-160, 2013

Histology is a well established branch of biology focused on the study of the microscopic anatomy of cells and tissues. Despite its importance, it is surprising to check that most literature devoted to histological image processing and analysis is focused on registration and 3D reconstruction of the whole brain. Therefore, there is a lack of research about automatic segmentation of anatomical brain structures in histological images. To bridge this gap, this paper introduces a comparative study of different segmentation techniques applied to this kind of images.
A wide and representative image set has been collected to run experiments on the hippocampus, due to the importance of this anatomical district in learning, memory and spatial navigation. Seven approaches, from deterministic to non-deterministic ones, and from recent trends to classical computer vision techniques, have been compared using different standard metrics (Dice Similariry Coefficient, Jaccard Index, Hausdorff Distance, True Positive Rate and False Positive Rate). Proper statistical tests have been performed to draw accurate conclusions about the results. The best performance on this particular problem was obtained by a combination of Active Shape Models (optimized using Differential Evolution) with a refinement step based on Random Forests. This approach achieved an average Dice Similarity Coefficient of 0.89 with a standard deviation of 0.03.

Differential Evolution Based Human Body Pose Estimation from Point Clouds

Roberto Ugolotti, Stefano Cagnoni

Proceedings of the 15th annual conference companion on Genetic and evolutionary computation, 2013

This paper describes a method to estimate the body pose of a human from a point cloud obtained using a depth sensor. It uses Differential Evolution to minimize the distance between the articulated model of a human and the point cloud. The results are compared to other four state-of-the art methods on a publicly available dataset proving good ability in estimating the pose and in tracking the person in video sequences.
The entire system, from Differential Evolution to fitness computation, is implemented on GPU using nVIDIA CUDA. Thanks to the massive parallelization, our algorithm is able to obtain results in real time.

Particle Swarm Optimization and Differential Evolution for Model-based Object Detection

Roberto Ugolotti, Youssef S.G. Nashed, Pablo Mesejo, Špela Ivekovič, Luca Mussi, Stefano Cagnoni

Applied Soft Computing Journal, Vol: 13, Pag: 3092-3105, 2013

Automatically detecting objects in images or video sequences is one of the most relevant and frequently tackled tasks in computer vision and pattern recognition.
The starting point for this work is a very general model-based approach to object detection. The problem is turned into a global continuous optimization one: given a parametric model of the object to be detected within an image, a function is maximized, which represents the similarity between the model and a region of the image under investigation.
In particular, in this work, the optimization problem is tackled using Particle Swarm Optimization (PSO) and Differential Evolution (DE). We compare the performances of these optimization techniques on two real-world paradigmatic problems, onto which many other real-world object detection problems can be mapped: hippocampus localization in histological images and human body pose estimation in video sequences. In the former, a 2D deformable model of a section of the hippocampus is fit to the corresponding region of a histological image, to accurately localize such a structure and analyze gene expression in specific sub-regions. In the latter, an articulated 3D model of a human body is matched against a set of images of a human performing some action, taken from different perspectives, to estimate the subject posture in space.
Given the significant computational burden imposed by this approach, we implemented PSO and DE as parallel algorithms within the nVIDIA™ CUDA computing architecture.

Segmentation of Histological Images using a Metaheuristic-based Level Set Approach

Pablo Mesejo, Stefano Cagnoni, Alessandro Costalunga, Davide Valeriani

Proc. of the 15th Annual Conference Companion on Genetic and Evolutionary Computation (GECCO’13), 2013

This paper presents a two-phase method to segment the hippocampus in histological images. The first phase represents a training stage where, from a training set of manually labelled images, the hippocampus representative shape and texture are derived. The second one, the proper segmentation, uses a metaheuristic to evolve the contour of a geometric deformable model using region and texture information.
Three different metaheuristics (real-coded GA, Particle Swarm Optimization and Differential Evolution) and two classical segmentation algorithms (Chan & Vese model and Geodesic Active Contours) were compared over a test set of 10 histological images. The best results were attained by the real-coded GA, achieving an average and median Dice Coefficient of 0.72 and 0.77, respectively.

Visual search of neuropil-enriched RNAs from brain in situ hybridization data through the image analysis pipeline Hippo-ATESC

Roberto Ugolotti, Pablo Mesejo, Samantha Zongaro, Barbara Bardoni, Gaia Berto, Federico Bianchi, Ivan Molineris, Mario Giacobini, Stefano Cagnoni, Ferdinando Di Cunto

PLOS ONE, 2013

RNA molecules specifically enriched in the neuropil of neuronal cells and in particular in dendritic spines are of great interest for neurobiology in virtue of their involvement in synaptic structure and plasticity. The systematic recognition of such molecules is therefore a very important task. High resolution images of RNA in situ hybridization experiments contained in the Allen Brain Atlas (ABA) represent a very rich resource to identify them and have been so far exploited for this task through human-expert analysis. However, software tools that may automatically address the same objective are not very well developed.

A comparative study of three GPU-based metaheuristics

Y.S.G. Nashed, P. Mesejo, R. Ugolotti, J. Dubois-Lacoste, S. Cagnoni 

Proceedings of the 12th international conference on Parallel Problem Solving from Nature, Vol: 2, Pag: 398-407, 2012

In this paper we compare GPU-based implementations of three metaheuristics: Particle Swarm Optimization, Differential Evolution, and Scatter Search. A GPU-based implementation, obviously, does not change the general properties of the algorithms. As well, we give for granted that GPU-based implementation of both algorithm and fitness function produces a significant speed-up with respect to a sequential implementation. Accordingly, the main goal of this work has been to fairly assess the efficiency of the GPU-based implementations of the three metaheuristics, based on the statistical analysis of the results they obtain in optimizing a benchmark of twenty functions within a prefixed limited time

Automatic Hippocampus Localization in Histological Images using Differential Evolution-Based Deformable Models

P. Mesejo, R. Ugolotti, F. Di Cunto, M. Giacobini, S. Cagnoni

Pattern Recognition Letters, Vol: 34, Pag: 299–307, 2012

In this paper, the localization of structures in biomedical images is considered as a multimodal global continuous optimization problem and solved by means of soft computing techniques. We have developed an automatic method aimed at localizing the hippocampus in histological images, after discoveries indicating the relevance of structural changes of this region as early biomarkers for Alzheimer’s disease and epilepsy. The localization is achieved by searching the parameters of an empirically-derived deformable model of the hippocampus which maximize its overlap with the corresponding anatomical structure in histological brain images. The comparison between six real-parameter optimization techniques (Levenberg–Marquardt, Differential Evolution, Simulated Annealing, Genetic Algorithms, Particle Swarm Optimization and Scatter Search) shows that Differential Evolution significantly outperforms the other techniques in this task, providing successful localizations in 90.9% and 93.0% of two test sets of real and synthetic images, respectively.

Automatic Segmentation of Hippocampus in Histological Images of Mouse Brains using Deformable Models and Random Forest

P. Mesejo, R. Ugolotti, F. Di Cunto, S. Cagnoni, M. Giacobini

Proceedings of the 25th IEEE International Symposium on Computer-Based Medical System, 2012

We perform a two-step segmentation of the hippocampus in histological images. First, we maximize the overlap of an empirically-derived parametric Deformable Model with two crucial landmark sub-structures in the brain image using Differential Evolution. Then, the points  located in the previous step determine the region where a thresholding technique based on Otsu’s method is to be applied. Finally, the segmentation is expanded employing Random Forest in the regions not covered by the model. Our approach showed an average segmentation accuracy of the 92.25% and 92.11% on test sets comprising 15 real and 15 synthetic images, respectively.

First results and future developments of the MIBISOC Project in the IBISlab of the University of Parma

S. Cagnoni, O. Cordón, P. Mesejo, Y.S.G. Nashed, R. Ugolotti

Proceedings of the 14th international conference on Genetic and evolutionary computation (companion), Pag: 509-516, 2012

Medical Imaging using Bio-Inspired and Soft Computing (MIBISOC) is a Marie Curie Initial Training Network (ITN) within the EU Seventh Framework Programme. MIBISOC is a training programme in which sixteen Early-Stage Researchers (ESRs) are exposed to a wide variety of Soft Computing (SC) and Bio-Inspired Computing (BC) techniques, and face the challenge of applying them to the different situations and problems which characterize medical image processing tasks. Hence, the main goal of the project is to generate new methods and solutions from the combination of the ideas of experts from the area of Medical Imaging (MI) with those working on BC and SC applications.

The Intelligent Bio-Inpired Systems laboratory (IBISlab) in the University of Parma is one of the partners of this ITN. In this paper, we describe the work which is being developed in the IBISlab, as well as its future developments and main objectives, within the framework of this ITN.

libCudaOptimize: an open source library of GPU-based metaheuristics

Y.S.G. Nashed, R. Ugolotti, P. Mesejo, S. Cagnoni 

Proceedings of the 14th international conference on Genetic and evolutionary computation (companion), Pag: 117-124, 2012

Evolutionary Computation techniques and other metaheuristics have been increasingly used in the last years for solving many real-world tasks that can be formulated as optimization problems. Among their numerous strengths, a major one is their natural predisposition to parallelization. In this paper, we introduce libCudaOptimize, an open source library which implements some metaheuristics for continuous optimization: presently Particle Swarm Optimization, Differential Evolution, Scatter Search, and Solis&Wets local search. This library allows users either to apply these metaheuristics directly to their own fitness function or to extend it by implementing their own parallel optimization techniques. The library is written in CUDA-C to make extensive use of parallelization, as allowed by Graphics Processing Units.
After describing the library, we consider two practical case studies: the optimization of a fitness function for the automatic localization of anatomical brain structures in histological images, and the parallel implementation of Simulated Annealing as a new module, which extends the library while keeping code compatibility with it, so that the new method can be readily available for future use within the library as an alternative optimization technique.

Real-Time GPU Based Road Sign Detection and Classification

R. Ugolotti, Y.S.G. Nashed, S. Cagnoni 

Proceedings of the 12th international conference on Parallel Problem Solving from Nature, Vol: 1, Pag: 153-162, 2012

This paper presents a system for detecting and classifying road signs from video sequences in real time. A model-based approach is used in which a prototype of the sign to be detected is transformed and matched to the image using evolutionary techniques. Then, the sign detected in the previous phase is classified by a neural network. Our system makes extensive use of the parallel computing capabilities offered by modern graphics cards and the CUDA architecture for both detection and classification. We compare detection results achieved by GPU-based parallel versions of Differential Evolution and Particle Swarm Optimization, and classification results obtained by Learning Vector Quantization and Multi-layer Perceptron. The method was tested over two real sequences taken from a camera mounted on-board a car and was able to correctly detect and classify around 70% of the signs at 17.5 fps, a similar result in shorter time, compared to the best results obtained on the same sequences so far.

Automatic Hippocampus Localization in Histological Images using PSO-based Deformable Models

R. Ugolotti, P. Mesejo, S. Cagnoni, M. Giacobini, F. Di Cunto

Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, Pag: 487-494, 2011

The Allen Brain Atlas (ABA) is a cellular-resolution, genome-wide map of gene expression in the mouse brain which allows users to compare gene expression patterns in neuroanatomical structures. The correct localization of the structures is the first step to carry on this comparison in an automatic way.
In this paper we present a completely automatic tool for the localization of the hippocampus that can be easily adapted also to other subcortical structures. This goal is achieved in two distinct phases.
The first phase, called "best reference slice selection", is performed by comparing the image of the brain with a reference Atlas provided by ABA using a two-step affine registration. By doing so the system is able to automatically find to which brain section the image corresponds and wherein the image the hippocampus is roughly located.
The second phase, the proper "hippocampus localization", is based on a method that combines Particle Swarm Optimization (PSO) and a novel technique inspired by Active Shape Models (ASMs). The hippocampus is found by adapting a deformable model derived statistically, in order to make it overlap with the hippocampus image.
Experiments on a test set of 120 images yielded a perfect or good localization in 89.2% of cases.

CUDA and OpenCL-based asynchronous PSO

Y.S.G. Nashed, A. Bacchini, S. CagnoniL. Mussi

Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, 2011

In `synchronous' PSO, positions and velocities of all particles are updated in turn in each `generation', after which each particle's new fi tness is evaluated. The value of the social attractor is only updated at the end of each generation, when the fi tness values of all particles are known. The `asynchronous' version of PSO, instead, allows the social attractors to be updated immediately after evaluating each particle's fi tness, which causes the swarm to move more promptly towards newly-found optima. In asynchronous PSO, the velocity and position update equations can be applied to any particle at any time, in no speci c order. The most common GPU implementations of PSO assign one thread per particle and do not take full advantage of the GPU power in evaluating the fi tness function in parallel. Parallelization only occurs on the number of particles of a swarm and ignores the dimensions of the function. In our parallel implementations: (i) we designed the thread parallelization to be as fine-grained as possible, considering that, in PSO, velocity and position update occur independently over each dimension; (ii) we implemented an 'asynchronous' PSO which, despite updating all particles in parallel, allows each of them to update the social attractor without waiting for all other particles' fi tness values to be evaluated. A block diagram representing the GPU execution of our parallel asynchronous PSO is shown in Figure 1.

GPU-based asynchronous particle swarm optimization

L. Mussi, Y.S.G. Nashed, S. Cagnoni

Proceedings of the 13th annual conference on Genetic and evolutionary computation, Pag: 1555-1562, 2011

This paper describes our latest implementation of Particle Swarm Optimization (PSO) with simple ring topology for modern Graphic Processing Units (GPUs). To achieve both the fastest execution time and the best performance, we designed a parallel version of the algorithm, as fine-grained as possible, without introducing explicit synchronization mechanisms among the particles' evolution processes. The results we obtained show a significant speed-up with respect to both the sequential version of the algorithm run on an up-to-date CPU and our previously developed parallel implementation within the nVIDIA CUDA architecture.

Multi-Sensor System for Detection and Classification of Human Activities

R. Ugolotti, F. Sassi, M. Mordonini, S. Cagnoni

Journal of Ambient Intelligence and Humanized Computing, Pag: 1-15, 2011

This paper describes a novel system for detecting and classifying human activities based on a multi-sensor approach. The aim of this research is to create a loosely structured environment, where activity is constantly monitored and automatically classified, transparently to the subjects who are observed. The system uses four calibrated cameras installed in the room which is being monitored and a body-mounted wireless accelerometer on each person, exploiting the features of different sensors to maximize recognition accuracy, improve scalability and reliability. The algorithms on which the system is based, as well as its structure, are aimed at analyzing and classifying complex movements (like walking, sitting, jumping, running, falling, etc.) of potentially multiple people at the same time. Here, we describe a preliminary application, in which action classification is mostly aimed at detecting falls. Several instances of a hybrid classifier based on Support Vector Machines and Hierarchical Temporal Memories, a recent bio-inspired computational paradigm, are used to detect potentially dangerous activities of each person in the environment. If such an activity is detected and if the person “in danger” is wearing the accelerometer, the system localizes and activates it to receive data and then performs a more reliable fall detection using a specifically trained classifier. The opportunity to turn on the accelerometer on-demand makes it possible to extend its battery life. Besides and beyond surveillance, this system could also be used for the assessment of the degree of independence of elderly people or, in rehabilitation, to assist patients during recovery.


See publications...