Project Results
Evoperf provides the bases for robust and performance-guaranteed evolutionary computations on large-scale distributed platforms. These methods offer a large spectrum of applications in various domains such as systems biomedicine. We adopted a multi-layered approach including: algorithmics (and the corresponding theoretical proofs), platform/middleware and application levels.
Algorithmics and theoretical proofs level
A set of tools has been proposed for classifying dynamic multi-objective optimisation problems and analysing their performance. These include the Optimal Subpattern Assignment (OSPA) metric and the online dynamic multi-objective NK-landscape benchmark. The Algorithm-Based-Fault-Tolerance (ABFT) aspects of parallel and distributed EAs against cheating and crash faults have also been characterized. Whereas the inherent resilience of EAs has been previously observed in the literature, this work offered for the first time a formal analysis of the impact of the considered faults over the executed EA.
Platform/Middleware level
An in-depth investigation of existing platforms has been conducted, including HPC clusters, P2P solutions, Cloud computing platforms. The overhead of the various solutions has been measured in order to determine the granularity of parallelism that could be achieved. Some evolutionary algorithms have been specifically designed for such platforms. These include a cloud-computing based evolutionary algorithm using a synchronous storage service as pool for exchange information among population of solutions. Also, a P2P EA whose population is structured using the Newscast gossip protocol has been extensively analysed due to its adaptation to all considered distributed and parallel computing platform. The complete theoretical runtime analysis of this new parallel EA permitted to improve the state-of-the-art results proposed in the literature. Volunteer platforms have also been considered. Scalable and fault-tolerant evolutionary algorithms have been designed specifically for both peer-to-peer systems and master-slave platforms. The speed of convergence of such massively parallel evolutionary algorithms has been analysed and efficient policies to overcome the algorithmic loss of quality when the system undergoes high rates of transient failures have been investigated.
Application level
In collaboration with the LCSB (Luxembourg Center of Systems Biomedicine), a state-of-the-art protein structure similarity problem has been defined as an optimization one, referred to as the IFP Problem hereinafter. The evaluation of solutions being computationally expensive, a novel benchmark mimicking the properties of the original problem was proposed (http://nk-ifp-bench.gforge.uni.lu/) The latter was used to conduct large sets of experiments to fine-tune the algorithms. In order to efficiently tackle these hard optimization problems, several contributions have been made in the EAs field. The IFP problem motivated the development of novel diversity preservation techniques, such as the usage of multi-objectivisation with diversity as objective (DAO) and quantile constraints (QC). The latter were evaluated on a set of proteins and the found solutions were validated using extensive molecular structure prediction experiments. Other diversity preserving approaches have also been proposed: preference-based genetic algorithms (PBGAs) and a cooperative selection operator for genetic algorithms able to find best trade-offs between speed of convergence and diversity preservation. In addition, an automated algorithm for the visualization and classification of enzymatic proteins based on self-organising maps was proposed in order to examine whether the functionality is correlated to the secondary structure.
