Back to Search
Start Over
Improving the Bin Packing Heuristic through Grammatical Evolution Based on Swarm Intelligence
- Source :
- Mathematical Problems in Engineering, Vol 2014 (2014)
- Publication Year :
- 2014
- Publisher :
- Hindawi Limited, 2014.
-
Abstract
- In recent years Grammatical Evolution (GE) has been used as a representation of Genetic Programming (GP) which has been applied to many optimization problems such as symbolic regression, classification, Boolean functions, constructed problems, and algorithmic problems. GE can use a diversity of searching strategies including Swarm Intelligence (SI). Particle Swarm Optimisation (PSO) is an algorithm of SI that has two main problems: premature convergence and poor diversity. Particle Evolutionary Swarm Optimization (PESO) is a recent and novel algorithm which is also part of SI. PESO uses two perturbations to avoid PSO’s problems. In this paper we propose using PESO and PSO in the frame of GE as strategies to generate heuristics that solve the Bin Packing Problem (BPP); it is possible however to apply this methodology to other kinds of problems using another Grammar designed for that problem. A comparison between PESO, PSO, and BPP’s heuristics is performed through the nonparametric Friedman test. The main contribution of this paper is proposing a Grammar to generate online and offline heuristics depending on the test instance trying to improve the heuristics generated by other grammars and humans; it also proposes a way to implement different algorithms as search strategies in GE like PESO to obtain better results than those obtained by PSO.
- Subjects :
- Optimization problem
Article Subject
business.industry
Bin packing problem
General Mathematics
lcsh:Mathematics
General Engineering
Particle swarm optimization
Genetic programming
lcsh:QA1-939
Swarm intelligence
Grammatical evolution
lcsh:TA1-2040
Artificial intelligence
Heuristics
business
lcsh:Engineering (General). Civil engineering (General)
Mathematics
Premature convergence
Subjects
Details
- Language :
- English
- ISSN :
- 15635147
- Volume :
- 2014
- Database :
- OpenAIRE
- Journal :
- Mathematical Problems in Engineering
- Accession number :
- edsair.doi.dedup.....dc21f122216b9f5f959b4bd7a42de7b0