Analysis of Scheduling Policies in Metaheuristics for Evolutionary Biology
Pages 3 - 10
Abstract
Nowadays, parallel metaheuristics represent one of the preferred choices to address complex optimization problems. However, one of the main problems that arise when using this kind of techniques lies on the potential emergence of load imbalance issues. In fact, the complexity of current optimization problems makes mandatory the adoption of multiple, conditional search strategies within the metaheuristic, thus increasing the potential impact that load imbalance can have in parallel performance. This work analyzes different scheduling policies to address load imbalance issues in the metaheuristic Multiobjective Shuffled Frog-Leaping Algorithm (MO-SFLA). Using as a case study a problem from the field of evolutionary biology, phylogenetic reconstruction, we conduct the experimental evaluation of three scheduling approaches from the OpenMP specification: static, dynamic, and guided. The results obtained in four real-world datasets highlight the influence of the adopted scheduling mechanisms over the observed overhead times, also pointing out the benefits of integrating dynamic policies into the metaheuristic.
References
[1]
F. Abascal, R. Zardoya, and D. Posada. 2005. ProtTest: Selection of best-fit models of protein evolution. Bioinformatics 21, 9 (2005), 2104--2105.
[2]
E. Alba, G. Luque, and S. Nesmachnow. 2013. Parallel metaheuristics: recent advances and new trends. International Transactions in Operational Research 20, 1 (2013), 1--48.
[3]
D A. Bader, A. Stamatakis, and C W. Tseng. 2006. Computational Grand Challenges in Assembling the Tree of Life: Problems and Solutions. In Advances in Computers. Vol. 68. Elsevier, 127--176.
[4]
A. L. Bazinet, D. J. Zwickl, and M. P. Cummings. 2014. A Gateway for Phylogenetic Analysis Powered by Grid Computing Featuring GARLI 2.0. Systematic Biology 63, 5 (2014), 812--818.
[5]
N. Beume, C. M. Fonseca, M. López-Ibáñez, L. Paquete, and J. Vahrenhold. 2009. On the Complexity of Computing the Hypervolume Indicator. IEEE Trans. Evol. Comput.13, 5 (2009), 1075--1082.
[6]
W. Cancino, L. Jourdan, E.-G. Talbi, and A. C. B. Delbem. 2010. Parallel Multi-Objective Approaches for Inferring Phylogenies. In Proc. of EVOBIO'2010 (LNCS), Vol. 6023. Springer, 26--37.
[7]
C. Coello, C. Dhaenens, and L. Jourdan. 2010. Advances in Multi-Objective Nature Inspired Computing. Springer Verlag, Berlin / Heidelberg.
[8]
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 2 (2002), 182--197.
[9]
P.J. Dias and I. Sá-Correia. 2013. The drug:H+ antiporters of family 2 (DHA2), siderophore transporters (ARN) and glutathione:H+antiporters (GEX) have a common evolutionary origin in hemiascomycete yeasts. BMC Genomics 14, 901 (2013), 1--22.
[10]
P. A. Goloboff and S. A. Catalano. 2016. TNT version 1.5, including a full implementation of phylogenetic morphometrics. Cladistics 32, 3 (2016), 221--238.
[11]
W. Gropp, W. Lusk, and A. Skjellum. 2014. Using MPI: Portable Parallel Programming with the Message Passing Interface. 3rd edition. The MIT Press, Cambridge, MA, USA.
[12]
J. L. Hennessy and D. A. Patterson. 2017. Computer Architecture: A Quantitative Approach, 6th Edition. Morgan Kaufmann Publishers Inc.
[13]
D. T. Jones, W. R. Taylor, and J. M. Thornton. 1992. The rapid generation of mutation data matrices from protein sequences. Bioinformatics 8, 3 (1992), 275--282.
[14]
A. Kovalchuk, A. Kohler, F. Martin, and F. O. Asiegbu. 2015. Diversity and evolution of ABC proteins in mycorrhiza-forming fungi. BMC Evolutionary Biology 15, 249 (2015), 1--19.
[15]
S. Q. Lee and O. Gascuel. 2008. An improved general amino acid replacement matrix. Mol. Biol. Evol. 25, 7 (2008), 1307--1320.
[16]
P. Lemey, M. Salemi, and A.-M. Vandamme. 2009. The Phylogenetic Handbook: a Practical Approach to Phylogenetic Analysis and Hypothesis Testing. Cambridge Univ. Press, Cambridge.
[17]
F. Luna and E. Alba. 2015. Parallel Multiobjective Evolutionary Algorithms. In Springer Handbook of Computational Intelligence. Springer, 1017--1031.
[18]
H. Matsuda, H. Yamashita, and Y. Kaneda. 1994. Molecular Phylogenetic Analysis using both DNA and Amino Acid Sequence Data and Its Parallelization. Genome Informatics 5 (1994), 120--129.
[19]
I. Morgenstern et al. 2012. A molecular phylogeny of thermophilic fungi. Fungal Biology 116, 4 (2012), 489--502.
[20]
L. Nguyen, H. Schmidt, A. Haeseler, and B. Minh. 2015. IQ-TREE: A fast and effective stochastic algorithm for estimating maximum likelihood phylogenies. Mol. Biol. Evol. 32, 1 (2015), 268--274.
[21]
L. Poladian. 2005. A GA for Maximum Likelihood Phylogenetic Inference using Neighbour-Joining as a Genotype to Phenotype Mapping. In Genetic and Evolutionary Computation Conference. 415--422.
[22]
S. Santander-Jiménez, M. A. Vega-Rodríguez, and L. Sousa. 2018. Multiobjective Frog-Leaping Optimization for the Study of Ancestral Relationships in Protein Data. IEEE Transactions on Evolutionary Computation (2018), 1--14.
[23]
A. Sarkheyli, A. M. Zain, and S. Sharif. 2015. The role of basic, modified and hybrid shuffled frog leaping algorithm on optimization problems: a review. Soft Computing 19, 7 (2015), 2011--2038.
[24]
R. Stracke et al. 2014. Genome-wide identification and characterisation of R2R3-MYB genes in sugar beet (Beta vulgaris). BMC Plant Biology 14, 249 (2014), 1--17.
[25]
E.-G. Talbi. 2015. Parallel Evolutionary Combinatorial Optimization. In Springer Handbook of Computational Intelligence. Springer, 1107--1125.
[26]
R. van der Pas, E. Stotzer, and C. Terboven. 2017. Using OpenMP - The Next Step. The MIT Press, Cambridge, MA, USA.
Index Terms
- Analysis of Scheduling Policies in Metaheuristics for Evolutionary Biology
Recommendations
Enriched metaheuristics for the resource constrained unrelated parallel machine scheduling problem
Highlights- The problem of unrelated parallel machines with an additional resource is considered.
AbstractA Scatter Search algorithm together with an enriched Scatter Search and an enriched Iterated Greedy for the unrelated parallel machine problem with one additional resource are proposed in this paper. The optimisation objective is to ...
Metaheuristics for the single machine weighted quadratic tardiness scheduling problem
This paper considers the single machine scheduling problem with weighted quadratic tardiness costs. Three metaheuristics are presented, namely iterated local search, variable greedy and steady-state genetic algorithm procedures. These address a gap in ...
Metaheuristics for minimizing the makespan of the dynamic shop scheduling problem
For the shop scheduling problems such as flow-shop, job-shop, open-shop, mixed-shop, and group-shop, most research focuses on optimizing the makespan under static conditions and does not take into consideration dynamic disturbances such as machine ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2018
70 pages
ISBN:9781450365314
DOI:10.1145/3235830
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 September 2018
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
PBio 2018
PBio 2018: 6th International Workshop on Parallelism in Bioinformatics
September 23, 2018
Barcelona, Spain
Acceptance Rates
PBio 2018 Paper Acceptance Rate 7 of 9 submissions, 78%;
Overall Acceptance Rate 7 of 9 submissions, 78%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 38Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)1
Reflects downloads up to 28 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in