Skip to main content

Research Repository

Advanced Search

A tensor analysis improved genetic algorithm for online bin packing

Asta, Shahriar; �zcan, Ender

Authors

Shahriar Asta

Profile Image

ENDER OZCAN ender.ozcan@nottingham.ac.uk
Professor of Computer Science and Operational Research



Abstract

Mutation in a Genetic Algorithm is the key variation operator adjusting the genetic diversity in a population throughout the evolutionary process. Often, a fixed mutation probability is used to perturb the value of a gene. In this study, we describe a novel data science approach to adaptively generate the mutation probability for each locus. The trail of high quality candidate solutions obtained during the search process is represented as a 3rd order tensor. Factorizing that tensor captures the common pattern between those solutions, identifying the degree of mutation which is likely to yield improvement at each locus. An online bin packing problem is used as an initial case study to investigate the proposed approach for generating locus dependent mutation probabilities. The empirical results show that the tensor approach improves the performance of a standard Genetic Algorithm on almost all classes of instances, significantly.

Citation

Asta, S., & Özcan, E. (2015). A tensor analysis improved genetic algorithm for online bin packing. In Proceedings of the 2015 on Genetic and Evolutionary Computation Conference - GECCO '15. https://doi.org/10.1145/2739480.2754787

Conference Name Genetic and Evolutionary Computation Conference (2015)
End Date Jul 15, 2015
Acceptance Date Jun 1, 2015
Publication Date Jul 11, 2015
Deposit Date Jun 14, 2016
Publicly Available Date Mar 28, 2024
Peer Reviewed Peer Reviewed
Book Title Proceedings of the 2015 on Genetic and Evolutionary Computation Conference - GECCO '15
DOI https://doi.org/10.1145/2739480.2754787
Keywords Genetic Algorithm, Bin Packing Problem, Tensor, Genetic Diversity, Fixation (Popular Genetics), Natural Selection, Locus (Genetics), Mutation
Public URL https://nottingham-repository.worktribe.com/output/757220
Publisher URL http://dl.acm.org/citation.cfm?doid=2739480.2754787
Related Public URLs http://www.sigevo.org/gecco-2015/
Additional Information Published in: GECCO '15 : proceedings and companion publication of the 2015 Genetic and Evolutionary Conference : July 11-15, 2015, Madrid, Spain. New York : ACM, 2015, ISBN: 978-1-4503-3472-3. pp. 799-806, doi:10.1145/2739480.2754787

Files





You might also like



Downloadable Citations