Search

A parallel memetic global optimization algorithm suitable for shared memory multicore systems is proposed and analyzed. The considered algorithm combines two well-known and widely used population-based stochastic algorithms, namely Particle Swarm Optimization and Differential Evolution, with two efficient and parallelizable local search procedures. The sequential version of the algorithm was first introduced as MEMPSODE (MEMetic Particle Swarm Optimization and Differential Evolution) and published in the CPC program library. We exploit the inherent and highly irregular parallelism of the memetic global optimization algorithm by means of a dynamic and multilevel approach based on the OpenMP tasking model. In our case, tasks correspond to local optimization procedures or simple function evaluations. Parallelization occurs at each iteration step of the memetic algorithm without affecting its searching efficiency. The proposed implementation, for the same random seed, reaches the same solution irrespectively of being executed sequentially or in parallel. Extensive experimental evaluation has been performed in order to illustrate the speedup achieved on a shared-memory multicore server. Program summary Program title: p-MEMPSODE Catalogue identifier: AEXJ_v1_0 Program summary URL: http://cpc.cs.qub.ac.uk/summaries/AEXJ_v1_0.html Program obtainable from: CPC Program Library, Queen’s University, Belfast, N. Ireland Licensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.html No. of lines in distributed program, including test data, etc.: 9950 No. of bytes in distributed program, including test data, etc.: 141503 Distribution format: tar.gz Programming language: ANSI C. Computer: Workstation. Operating system: Developed under the Linux operating system using the GNU compilers v.4.4.3 (or higher). Uses the OpenMP API and runtime system. RAM: The code uses O ( n × N ) internal storage, n being the dimension of the problem and N the maximum population size. The required memory is dynamically allocated. Word size: 64 Classification: 4.9. Nature of problem: Numerical global optimization of real valued functions is an indispensable methodology for solving a multitude of problems in science and engineering. Many problems exhibit a number of local and/or global minimizers, expensive function evaluations or require real-time response. In addition, discontinuities of the objective function, non-smooth and deceitful landscapes constitute challenging obstacles for most optimization algorithms. Solution method: We implement a memetic global optimization algorithm that combines stochastic, population-based methods with deterministic local search procedures. More specifically, the Unified Particle Swarm Optimization and the Differential Evolution algorithms are harnessed with the derivative-free Torczon’s Multi-Directional Search and the gradient-based BFGS method. The produced hybrid algorithms possess inherent parallelism that is exploited efficiently by means of the OpenMP tasking model. Given the same random seed, the proposed implementation reaches the same solution irrespective of being executed sequentially or in parallel. Restrictions: The current version of the software uses only double precision arithmetic. An OpenMP-enabled (version 3.0 or higher) compiler is required. Unusual features: The software requires bound constraints on the optimization variables. Running time: The running time depends on the complexity of the objective function (and its derivatives if used) as well as on the number of available cores. Extensive experimental results demonstrate that the speedup closely approximates ideal values. [ABSTRACT FROM AUTHOR]

We present MEMPSODE, a global optimization software tool that integrates two prominent population-based stochastic algorithms, namely Particle Swarm Optimization and Differential Evolution, with well established efficient local search procedures made available via the Merlin optimization environment. The resulting hybrid algorithms, also referred to as Memetic Algorithms, combine the space exploration advantage of their global part with the efficiency asset of the local search, and as expected they have displayed a highly efficient behavior in solving diverse optimization problems. The proposed software is carefully parametrized so as to offer complete control to fully exploit the algorithmic virtues. It is accompanied by comprehensive examples and a large set of widely used test functions, including tough atomic cluster and protein conformation problems. Program summary: Program title: MEMPSODE (MEMetic Particle Swarm Optimization and Differential Evolution) Catalogue identifier: AELM_v1_0 Program summary URL: http://cpc.cs.qub.ac.uk/summaries/AELM_v1_0.html Program obtainable from: CPC Program Library, Queenʼs University, Belfast, N. Ireland Licensing provisions: Standard CPC license, http://cpc.cs.qub.ac.uk/licence/licence.html No. of lines in distributed program, including test data, etc.: 14 877 No. of bytes in distributed program, including test data, etc.: 592 244 Distribution format: tar.gz Programming language: ANSI C, ANSI Fortran-77 Computer: Workstations Operating system: Developed under the Linux operating system using the GNU compilers v.4.4.3. It has also been tested under Solaris and the Cygwin environment. RAM: The code uses internal storage, n being the dimension of the problem and N the maximum population size. The required memory is dynamically allocated. Word size: 64 bits Classification: 4.9 Subprograms used: Nature of problem: Optimization is a valuable mathematical tool for solving a plethora of scientific and engineering problems. Usually, the underlying problems are modeled with objective functions whose minimizers (or maximizers) correspond to the desired solutions of the original problem. In many cases, there is a multitude of such minimizers that correspond to solutions either locally, i.e., in their close neighborhood, or globally, i.e., with respect to the whole search space. There is a significant number of efficient algorithms for addressing optimization problems. One can distinguish two main categories, based on their adequacy in performing better global (exploration) or local (exploitation) search. Standard local optimization algorithms have the ability to rapidly converge towards local minimizers but they are also prone to get easily trapped in their vicinity. These algorithms usually exploit local information of the objective function, including first- and second-order derivatives. On the other hand, global optimization algorithms are designed to perform better exploration, although at the cost of questionable convergence properties. Typically, these approaches integrate stochastic operations. The form of the optimization problem at hand plays a crucial role in the selection of the most appropriate algorithm. Objective functions that lack nice mathematical properties (such as differentiability, continuity etc.) may raise applicability issues for algorithms that require derivatives. On the other hand, applications that require high accuracy may be laborious for stochastic algorithms. The existence of a multitude of local and/or global minimizers can render these problems even harder for any single optimization algorithm. Solution method: Evolutionary Algorithms and Swarm Intelligence approaches have been established as effective global optimization algorithms that make minor assumptions about the objective function. Particle Swarm Optimization (PSO) and Differential Evolution (DE) possess a salient position among the most successful algorithms of these categories. Numerous studies indicate that their performance can be radically improved when combined with efficient local optimization schemes. The resulting hybrid algorithms offer more balanced search intensification/diversification than the original ones, thereby increasing both their efficiency and effectiveness. Such hybrid schemes are called Memetic Algorithms, and they have gained a rapidly growing interest over the past few years. We present MEMPSODE (MEMetic, PSO and DE), a global optimization software that implements memetic PSO and DE within a unified framework. The software utilizes local search procedures from the established Merlin optimization environment. The performance of the implemented approaches is illustrated on several examples, including hard optimization tasks such as atomic cluster and protein conformation problems. Restrictions: The current version of the software uses double precision arithmetic. However, it can be easily adapted by the user to handle integer or mixed-integer problems. Unusual features: The software takes into account only bound constraints. General constraints may be tackled by user-defined penalty or barrier functions that can be easily incorporated in the source code of the objective function. Additional comments: The use of the Merlin Optimization Environment 3.1.1 (see subprograms above) is optional. A comprehensive user manual is provided that covers in detail the installation procedure and provides detailed examples of operation. Running time: The running time depends solely on the complexity of the objective function (and its derivatives, if used) as well as on the available computational budget (number of function evaluations). The test run provided (Rastrigin function ), requires function evaluations (2.8 seconds on an i7-920 CPU). [ABSTRACT FROM AUTHOR]