Plenary Lecture, ARTIFICIAL INTELLIGENCE, KNOWLEDGE ENGINEERING and DATA BASES (AIKED '09), Cambridge, UK, February 21-23, 2009

Plenary Lecture

The Efficiency of Parallel Metaheuristics for Combinatorial Optimization – Paradigms, Models and Implementations

Professor Plamenka Borovska
Head of Computer Systems Department
Technical University of Sofia

Abstract: Parallel metaheuristics have proved to provide efficient and powerful tools for combinatorial optimization of grand challenge scientific and engineering problems. Metaheuristics offer the opportunity to find out optimal or suboptimal solution of NP-hard problems in reasonable time. Combinatorial optimization based on metaheuristics implies tree major aspects – the search space, the neighborhood relations and the guiding function, the specific forms of which determine the metaphor of the computation. The search strategies for the optimum implied may be trajectory-based or population-based, the latter simulating biological or cultural evolution. The major goal of parallelizing metaheuristics is not only to reduce significantly the computational time but to improve the quality of solutions obtained as well. The motives to utilize parallel metaheuristics are diversification and intensification. The paper focuses on the specifics of designing parallel computational models based on metaheuristics, implementing various parallel algorithmic paradigms and optimizing the correlations architectural space – target parallel computer architecture. Classifications of parallel computational models in respect to the granularity are presented. The aspects of tuning algorithmic parameters to the specifics of the problem being solved are considered. The problems of building up metaheuristics class libraries are under consideration. Parallel performance evaluation and quality of solution estimation on the basis of parallel program implementations are treated. Case studies are presented for trajectory-based and population-based parallel metaheuristics implementations on compact computer cluster of multi-core servers (super-server).

Brief Biography of the Speaker:
Prof. PhD Plamenka Borovska graduated from the Technical University of Sofia, Bulgaria, specialty Computer Systems and Technologies. Her PhD thesis is in the area of parallel computing. She defended her habilitation thesis “Strategies, Methods and Models for Parallel Information Processing” in 2007 at the Technical University of Sofia. Her research areas comprise parallel computing, high performance computer architectures, parallel algorithms and parallel programming, GRID technologies, parallel metaheuristics, bioinformatics, virtual screening and computer simulations for drug design. She has specialized in UK, University of Manchester, Computer Science Dept., Italy, Polytechnics of Milan, Dept. of Electronics and Information, Germany, University of Karlsruhe, Institute of Informatics. Prof. Borovska has about 100 publications at scientific journals and international conferences, has been a project manager of about 20 research projects focused on parallel computing, and has patents in USA and UK for multiprocessor systems.
Presently, Prof. Borovska is head of the Computer Systems Dept., Technical University of Sofia (URL: She is the Bulgarian representative in the International Federation of Information Processing IFIP in Technical committee 10, a member of IEEE, ACM Computer Society, a member of the Specialized Scientific Council in electronics and computing of the High Attestation Commission in Bulgaria, expert in information technologies for the State Agency for Information Technologies and Communication, Bulgaria and for the National Innovation Funds, editor-in-chief of the scientific journal “Computer Engineering”, Bulgaria. In 2006 she was awarded by the Bulgarian Academic Society for Computer Systems and Information Technologies for significant contribution to the development of information technologies in Bulgaria.



WSEAS Unifying the Science