Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 1,334 papers for “Parallel metaheuristic”

A Parallel Hybrid Evolutionary Metaheuristic

For The Period, Ro Soares Vianna, Luiz S. Ochi et al. · 1999

This paper presents a Parallel Hybrid Evolutionary Metaheuristic for the Period Vehicle Routing Problem #PVRP#. The PRVP generalizes the classical Vehicle Routing Problem by extending the planning period from a single day to M days. The algorithm proposed is based on concepts used in Parallel Genetic Algorithms and Local Search Heuristics. The algorithm employs the island model in which the migration frequency must not be very high. The results of computational experiments carried out on problems taken from the literature indicate that the proposed approach outperforms existing heuristics in most cases.

Cited by 0

Parallel Metaheuristic Algorithms for Task Scheduling Problems

Sirui Mao, Masato Edahiro · INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY · 2025

This study addresses the task-scheduling optimization challenges in parallel computing systems using a novel meta-heuristic framework. We analyze the differential evolution in task scheduling and propose an advanced shift-chain methodology to improve the cooperation between scheduling components. The proposed framework introduces a wait-ing time-based neighborhood exploration strategy for handling complex task dependencies, along with two parallel implementation approaches: basic matching vector (MV) parallelization and an event-driven strategy. The experi-mental results demonstrated superior solution quality and computational efficiency compared with existing methods, particularly in large scale problems. The modular design of this framework enables practical applications in moderncomputing environments.

Cited by 0Open access

A parallel hybrid metaheuristic for bicluster editing

Gilberto F. de Sousa Filho, Teobaldo L. Bulhões Júnior, Lucídio dos Anjos Formiga Cabral et al. · International Transactions in Operational Research · 2015

Abstract The bicluster editing problem (BEP) consists of editing (adding or removing) the edges of a bipartite graph G in order to transform it into a vertex‐disjoint union of complete bipartite subgraphs, in such a way that the sum of the weights of the edited edges is minimum. In this paper, we propose five parallel strategies for the implementation of a hybrid metaheuristic for the BEP, consisting of a GRASP with VNS as local search. Computational experiments show near‐linear speedups on Linux cluster with 64 processors and better solutions than those of the sequential approach.

Cited by 5

Hierarchical Model of Parallel Metaheuristic Optimization Algorithms

E. Yu. Seliverstov, Anatoly Karpenko · Procedia Computer Science · 2019

The paper introduces a novel model of parallel metaheuristic optimization algorithms. The hierarchical graph model of a parallel optimization algorithm is proposed. It consists of the model for a parallel optimization algorithm at the top level of the hierarchy and the model for a sequential optimization algorithm at the bottom level. The unified representation of a metaheuristic optimization algorithm, which allows representing a class of metaheuristic algorithms, is used. The extension of the proposed model to the parametric hierarchical model is proposed. Graph model transformations for a parallel algorithm analysis and synthesis are introduced. The representation of several metaheuristic algorithms with the proposed model is discussed.

Cited by 10Open access

A supervised parallel optimisation framework for metaheuristic algorithms

Eugenio J. Muttio, Wulf G. Dettmer, J. Clarke et al. · Swarm and Evolutionary Computation · 2023

A Supervised Parallel Optimisation (SPO) is presented. The proposed framework couples different optimisation algorithms to solve single-objective optimisation problems. The supervision balances the exploration and exploitation capabilities of the distinct optimisers included, providing a general framework to solve problems with diverse characteristics. In this work, five optimisation algorithms are included in the ensemble: Particle Swarm Optimisation (PSO), Genetic Algorithm (GA), Covariance Matrix Adaption - Evolution Strategy (CMA-ES), Differential Evolution (DE), and Modified Cuckoo Search (MCS). A geometric path-finding problem with numerous local minima is used to demonstrate the advantage of SPO. The effectiveness of the approach is compared with that of stand-alone incidences of the integrated optimisation strategies and with state-of-the-art algorithms. In addition, a benchmark test suit composed of engineering applications is utilised to validate the general applicability of SPO with respect to a variety of problems. The good solutions generated by SPO are shown to be generally reproducible, while isolated algorithms, at best, render good solutions only occasionally.

Cited by 17Open access

Systolic genetic search, a parallel metaheuristic for GPUs

Pedemonte, Martín · Americanae (AECID Library) · 2019

La utilización de unidades de procesamiento gráfico (GPUs) para la resolución de problemas de propósito general ha experimentado un crecimiento vertiginoso en los últimos años, sustentado en su amplia disponibilidad, su bajo costo económico y en contar con una arquitectura inherentemente paralela, así como en la aparición de lenguajes de programación de propósito general que han facilitado el desarrollo de aplicaciones en estas plataformas. En este contexto, el diseño de nuevos algoritmos paralelos que puedan beneficiarse del uso de GPUs es una línea de investigación prometedora e interesante. Las metaheurísticas son algoritmos estocásticos capaces de encontrar soluciones muy precisas (muchas veces óptimas) a problemas de optimización en un tiempo razonable. Sin embargo, como muchos problemas de optimización involucran tareas que exigen grandes recursos computacionales y/o el tamaño de las instancias que se están abordando actualmente se están volviendo muy grandes, incluso las metaheurísticas pueden ser computacionalmente muy costosas. En este escenario, el paralelismo surge como una alternativa exitosa con el fin de acelerar la búsqueda de este tipo de algoritmos. Además de permitir reducir el tiempo de ejecución de los algoritmos, las metaheurísticas paralelas a menudo son capaces de mejorar la calidad de los resultados obtenidos por los algoritmos secuenciales tradicionales.Si bien el uso de GPUs ha representado un dominio inspirador también para la investigación en metaheurísticas paralelas, la mayoría de los trabajos previos tenían como objetivo portar una familia existente de algoritmos a este nuevo tipo de hardware. Como consecuencia, muchas publicaciones están dirigidas a mostrar el ahorro en tiempo de ejecución que se puede lograr al ejecutar los diferentes tipos paralelos de metaheurísticas existentes en GPU. En otras palabras, a pesar de que existe un volumen considerable de trabajo sobre este tópico, se han propuesto pocas ideas novedosas que busquen diseñar nuevos algoritmos y/o modelos de paralelismo que exploten explícitamente el alto grado de paralelismo disponible en las arquitecturas de las GPUs. Esta tesis aborda el diseño de una propuesta innovadora de algoritmo de optimización paralelo denominada Búsqueda Genética Sistólica (SGS), que combina ideas de los campos de metaheurísticas y computación sistólica. SGS, así como la computación sistólica, se inspiran en el mismo fenómeno biológico: la contracción sistólica del corazón que hace posible la circulación de la sangre. En SGS, las soluciones circulan de forma síncrona a través de una grilla (rejilla) de celdas. Cuando dos soluciones se encuentran en una celda se aplican operadores evolutivos adaptados para generar nuevas soluciones que continúan moviéndose a través de la grilla (rejilla). La implementación de esta nueva propuesta saca partido especialmente de las características específicas de las GPUs. Un extenso análisis experimental que considera varios problemas de benchmark clásicos y dos problemas del mundo real del área de Ingeniería de Software, muestra que el nuevo algoritmo propuesto es muy efectivo, encontrando soluciones óptimas o casi óptimas en tiempos de ejecución cortos. Además, los resultados numéricos obtenidos por SGS son competitivos con los resultados del estado del arte para los dos problemas del mundo real en cuestión. Por otro lado, la implementación paralela en GPU de SGS ha logrado un alto rendimiento, obteniendo grandes reducciones de tiempo de ejecución con respecto a la implementación secuencial y mostrando que escala adecuadamente cuando se consideran instancias de tamaño creciente. También se ha realizado un análisis teórico de las capacidades de búsqueda de SGS para comprender cómo algunos aspectos del diseño del algoritmo afectan a sus resultados numéricos. Este análisis arroja luz sobre algunos aspectos del funcionamiento de SGS que pueden utilizarse para mejorar el diseño del algoritmo en futuras variantes.

Cited by 1

A Parallel Multiobjective Metaheuristic for Multiple Sequence Alignment

Álvaro Rubio‐Largo, Mauro Castelli, Leonardo Vanneschi et al. · Journal of Computational Biology · 2018

The alignment among three or more nucleotides/amino acids sequences at the same time is known as multiple sequence alignment (MSA), a nondeterministic polynomial time (NP)-hard optimization problem. The time complexity of finding an optimal alignment raises exponentially when the number of sequences to align increases. In this work, we deal with a multiobjective version of the MSA problem wherein the goal is to simultaneously optimize the accuracy and conservation of the alignment. A parallel version of the hybrid multiobjective memetic metaheuristics for MSA is proposed. To evaluate the parallel performance of our proposal, we have selected a pull of data sets with different number of sequences (up to 1000 sequences) and study its parallel performance against other well-known parallel metaheuristics published in the literature, such as MSAProbs, tree-based consistency objective function for alignment evaluation (T-Coffee), Clustal [Formula: see text], and multiple alignment using fast Fourier transform (MAFFT). The comparative study reveals that our parallel aligner obtains better results than MSAProbs, T-Coffee, Clustal [Formula: see text], and MAFFT. In addition, the parallel version is around 25 times faster than the sequential version with 32 cores, obtaining an efficiency around 80%.

Cited by 5

General framework of solving PSP by parallel metaheuristic.

Qiang Lü (5651812), Xiao-Yan Xia (304765), Rong Chen (29176) et al. · Figshare · 2015

<p>The OP stands for all kinds of application problems, which can be computationally modeled as an optimization problem. Three such models are possible for solving OP, namely , and , where and are derived from how to solve OP numerically and non-numerically respectively. Three parallel solutions can be applied to solve the modeled optimization problems, and the current parallel platform at both hardware and software level can easily support the above three solutions.</p>

Cited by 0Open access

A Parallel Multiobjective Metaheuristic for Multiple Sequence Alignment

Álvaro Rubio‐Largo, Leonardo Vanneschi, Mauro Castelli et al. · bioRxiv (Cold Spring Harbor Laboratory) · 2017

Abstract The alignment among three or more nucleotides/amino-acids sequences at the same time is known as Multiple Sequence Alignment (MSA), an NP-hard optimization problem. The time complexity of finding an optimal alignment raises exponentially when the number of sequences to align increases. In this work, we deal with a multiobjective version of the MSA problem where the goal is to simultaneously optimize the accuracy and conservation of the alignment. A parallel version of the Hybrid Multiobjective Memetic Metaheuristics for Multiple Sequence Alignment is proposed. In order to evaluate the parallel performance of our proposal, we have selected a pull of datasets with different number of sequences (up to 1000 sequences) and study its parallel performance against other well-known parallel metaheuristics published in the literature, such as MSAProbs, T-Coffee, Clustal Ω, and MAFFT. The comparative study reveals that our parallel aligner is around 25 times faster than the sequential version with 32 cores, obtaining a parallel efficiency around 80%.

Cited by 2Open access

New approaches in parallel algorithm portfolios for metaheuristic optimization

Δημήτριος Σουραβλιάς · 2017

Τα προβλήματα βελτιστοποίησης είναι πανταχού παρόντα στην επιστήμη και στη μηχανική. Εμφανίζονται σε διάφορους τύπους και μορφές σε όλες σχεδόν τις διαδικασίες λήψης αποφάσεων. Η αφθονία και η ποικιλομορφία των προβλημάτων βελτιστοποίησης έχουν δώσει πρόσφορο έδαφος για την ανάπτυξη καινοτόμων μεθόδων και τεχνικών επίλυσης. Διάφορες μέθοδοι βελτιστοποίησης έχουν προταθεί τις τελευταίες δεκαετίες, καταγράφοντας διαρκή αύξηση των διαθέσιμων αλγορίθμων. Ωστόσο, τόσο θεωρητικές όσο και πειραματικές μελέτες καταλήγουν στο συμπέρασμα ότι η ύπαρξη ενός καθολικού αλγορίθμου βελτιστοποίησης ικανού να αντιμετωπίσει εξίσου καλά όλα τα δυνατά προβλήματα βελτιστοποίησης είναι απίθανη. Έτσι, ο προσδιορισμός του κατάλληλου αλγορίθμου καθορίζει το όριο μεταξύ επιτυχίας και αποτυχίας όταν ο στόχος είναι η επίλυση απαιτητικών προβλημάτων βελτιστοποίησης. Μια από τις πιο σημαντικές αποφάσεις της διαδικασίας επίλυσης είναι η επιλογή του αλγορίθμου βελτιστοποίησης που θα χρησιμοποιηθεί. Πρόκειται για μια δύσκολη επιλογή που συνήθως απαιτεί βαθιά γνώση του προβλήματος αλλά και εμπειρία. Σε περίπτωση που οι διαθέσιμες πληροφορίες για το πρόβλημα είναι περιορισμένες, συνήθως απαιτείται προκαταρκτική πειραματική μελέτη για την επιλογή του καταλληλότερου αλγορίθμου από ένα σύνολο υποψηφίων, μέσω μιας διαδικασίας δοκιμής σφάλματος. Αυτή η διαδικασία είναι επιρρεπής σε λάθη καθώς και χρονοβόρα. Στην πράξη μπορεί να απαιτεί περισσότερο χρόνο ακόμη κι από τη διαδικασία επίλυσης του ίδιου του προβλήματος, λόγω του υπολογιστικού φόρτου των χρησιμοποιούμενων στατιστικών μεθόδων. Επιπλέον, δε λαμβάνει άμεσα υπόψη την δυναμική του κάθε αλγορίθμου σε πραγματικό χρόνο, δηλαδή τις διακυμάνσεις της απόδοσης κατά την εκτέλεσή του. Τα Χαρτοφυλάκια Αλγορίθμων αποτελούν σχήματα που ενσωματώνουν διαφορετικούς αλγορίθμους ή διαφορετικές εκδοχές του ίδιου αλγορίθμου, οι οποίες εκτελούνται σειριακά (σε μία μονάδα επεξεργασίας) ή παράλληλα (όταν περισσότερες μονάδες επεξεργασίας είναι διαθέσιμες). Στην πρώτη περίπτωση, οι αλγόριθμοι του χαρτοφυλακίου εναλλάσσουν την εκτέλεσή τους, καταναλώνοντας ο καθένας εκ περιτροπής ένα τμήμα των διαθέσιμων υπολογιστικών πόρων (συναρτησιακοί υπολογισμοί ή χρόνος). Στη δεύτερη περίπτωση, οι μονάδες επεξεργασίας και οι υπολογιστικοί πόροι μοιράζονται μεταξύ των αλγορίθμων σύμφωνα με ένα προκαθορισμένο πλάνο, προσφέροντας προφανή πλεονεκτήματα ως προς το χρόνο εκτέλεσης. Το πλάνο κατανομής πόρων καθορίζεται συνήθως πριν από την εφαρμογή του χαρτοφυλακίου, διαμέσου προκαταρκτικής πειραματικής μελέτης ή ιστορικών δεδομένων απόδοσης των αλγορίθμων. Ωστόσο, η εκχώρηση προκαθορισμένων τμημάτων των υπολογιστικών πόρων μπορεί να είναι μη αποτελεσματική, καθώς δεν λαμβάνει υπόψη τη δυναμική του κάθε αλγορίθμου σε πραγματικό χρόνο. Σε τέτοιες περιπτώσεις, η δυναμική κατανομή πόρων κατά την εκτέλεση του χαρτοφυλακίου μπορεί να αποδειχθεί ιδιαίτερα επωφελής. Οι κύριοι στόχοι της διατριβής είναι η αιτιολόγηση της χρήσης χαρτοφυλακίων μεταευρετικών αλγορίθμων σε προβλήματα βελτιστοποίησης διαφόρων τύπων και η ανάπτυξη νέων μοντέλων παράλληλων χαρτοφυλακίων αλγορίθμων με δυναμικά προσαρμοζόμενα σχέδια κατανομής υπολογιστικών πόρων. Στο πρώτο μέρος της διατριβής δίνονται κίνητρα για τη χρήση χαρτοφυλακίων αλγορίθμων, διερευνάται η χρησιμότητα των μηχανισμών κατανομής υπολογιστικών πόρων σε μεταευρετικούς αλγορίθμους και προτείνονται δύο απλά παράλληλα μοντέλα χαρτοφυλακίων αλγορίθμων. Το πρώτο μοντέλο μπορεί να χρησιμοποιηθεί με οποιονδήποτε αλγόριθμο βελτιστοποίησης και εφαρμόζεται στο σχεδιασμό κρυπτογραφικά ισχυρών S-boxes, το οποίο είναι ένα σημαντικό πρόβλημα στην κρυπτογραφία. Το δεύτερο μοντέλο είναι κατάλληλο για πλυθησμιακούς αλγορίθμους και εφαρμόζεται στο πρόβλημα χρονοπρογραμματισμού φωτεινών σηματοδοτών σε περιβάλλοντα έξυπνων πόλεων. Στο δεύτερο μέρος της εργασίας, προτείνονται δύο νέα παράλληλα μοντέλα χαρτοφυλακίων αλγορίθμων, τα οποία υλοποιούν νέους μηχανισμούς κατανομής υπολογιστικών πόρων. Το πρώτο μοντέλο είναι ένα χαρτοφυλάκιο αλγορίθμων βασισμένο σε συναλλαγές, το οποίο χρησιμοποιεί ένα νέο μηχανισμό κατανομής πόρων, σύμφωνα με τον οποίο οι αλγόριθμοί του μπορούν να πωλούν λύσεις κερδίζοντας επιπλέον χρόνο εκτέλεσης. Το μοντέλο είναι αυτόνομο και επιτρέπει στους αλγορίθμους να αλληλεπιδρούν όταν πληρούνται συγκεκριμένες συνθήκες (για παράδειγμα στασιμότητα αναζήτησης). Το μοντέλο εφαρμόζεται σε τρία απαιτητικά προβλήματα όπως η ανίχνευση κυκλικών πινάκων στάθμισης, ο προσδιορισμός μεγέθους παρτίδας σε συστήματα παραγωγής με επιστροφές και ανακατασκευή προϊόντων, καθώς και η μεταφορά εμπορευμάτων σε ανθρωπιστικές εφοδιαστικές αλυσίδες. Το δεύτερο προτεινόμενο μοντέλο είναι ένα χαρτοφυλάκιο αλγορίθμων βασισμένο σε προβλέψεις, το οποίο χρησιμοποιεί τεχνικές πρόβλεψης χρονοσειρών για την πρόβλεψη της απόδοσης των αλγορίθμων που το αποτελούν. Οι προβλέψεις χρησιμοποιούνται για τον κατάλληλο διαμοιρασμό των διαθέσιμων υπολογιστικών πόρων στους αλγορίθμους του χαρτοφυλακίου. Το μοντέλο εφαρμόζεται στην ανίχνευση κυκλικών πινάκων στάθμισης.

Cited by 0Open access

METADOCK: A parallel metaheuristic schema for virtual screening methods

Imbernón Tudela, Baldomero, Cecilia Canales, José María, Pérez Sánchez, Horacio et al. · RIUCAM · 2017

Virtual screening through molecular docking can be translated into an optimization problem, which can be tackled with metaheuristic methods. The interaction between two chemical compounds (typically a protein, enzyme or receptor, and a small molecule, or ligand) is calculated by using highly computationally demanding scoring functions that are computed at several binding spots located throughout the protein surface. This paper introduces METADOCK, a novel molecular docking methodology based on parameterized and parallel metaheuristics and designed to leverage heterogeneous computers based on heterogeneous architectures. The application decides the optimization technique at running time by setting a configuration schema. Our proposed solution finds a good workload balance via dynamic assignment of jobs to heterogeneous resources which perform independent metaheuristic executions when computing different molecular interactions required by the scoring functions in use. A cooperative scheduling of jobs optimizes the quality of the solution and the overall performance of the simulation, so opening a new path for further developments of virtual screening methods on high-performance contemporary heterogeneous platforms.

Cited by 0Open access

Metaheuristic scheduling of parallel machines with job delivery coordination

Shen-Tsu Wang · Journal of Information and Optimization Sciences · 2011

This paper considers a problem in which orders are processed by either one of two parallel machines and delivered by a single delivery truck to one customer area. Coordination among production stage and distribution stage in the supply chain to achieve ideal overall system performance has become more practical and has received a lot of attention from both industry practitioners and academic researchers. The coordinated scheduling problem of production and distribution operations deals with scheduling orders on the two identical parallel machines and grouping the completed orders into batches for delivery. To solve this complex problem, a regular genetic algorithm (GA) and an efficient approach which is based on a hybrid of GA and a parallel scheduling procedure (PSP) and is called hybrid GA (HGA), are proposed. Experimental results demonstrate that the regular GA and HGA perform very well with respect to the objective function. Besides, the HGA can find even or better solution in a shorter period of time than the regular GA. Thus, the proposed HGA should be the scheduling approach of choice.

Cited by 1

Preventive maintenance optimization for series-parallel systems using metaheuristic

EL SAMROUT, Mohamad, CHATELET, Eric, CHEBBO, Nazir · OpenGrey (Institut de l'Information Scientifique et Technique) · 2006

L optimisation des politiques de maintenance préventive est devenu un sujet d intérêt qui a fait l objet de nombreux travaux. Cette thèse propose une nouvelle politique optimisée de la maintenance préventive pour des systèmes série-parallèle. Elle est divisée en deux grandes parties. La première élabore et contrôle une nouvelle technique de recherche, et la deuxième propose un nouveau modèle pour calculer la fiabilité/disponibilité où l effet de la maintenance corrective est intégré. D abord, on propose des algorithmes basés sur l optimisation par colonies de fourmis (ACO) comme technique de recherche pour optimiser la détermination des périodes de la maintenance préventive pour chaque composant menant ainsi à la minimisation du coût de cette opération. Une fois appliquée, cette technique montre une performance intéressante vu la comparaison établie entre les ACO et des algorithmes génétiques. Cependant, le paramétrage des ACO demeure un problème critique qui a besoin de plus d analyse. Une étude détaillée sur l influence des paramètres sur la performance des ACO est lancée. Un plan expérimental est réalisé. Dans la seconde partie, nous proposons une nouvelle méthode pour intégrer l effet de la MC lors de la planification de la politique de maintenance préventive. Le taux de défaillance proportionnel est utilisé pour intégrer l effet de la MC sur la disponibilité du composant et par conséquent comme paramètre décisif dans la politique de maintenance

Cited by 0Open access