Applying the big bang-big crunch metaheuristic to large-sized operational problems

Yousef K. Qawqzeh, Ghaith Jaradat, Ali Al-Yousef, Anmar Abu-Hamdah, Ibrahim Almarashdeh, Mutasem Alsmadi, Mohammed Tayfour, Khalid Shaker, Firas Haddad

Abstract


In this study, we present an investigation of comparing the capability of a big bang-big crunch metaheuristic (BBBC) for managing operational problems including combinatorial optimization problems. The BBBC is a product of the evolution theory of the universe in physics and astronomy. Two main phases of BBBC are the big bang and the big crunch. The big bang phase involves the creation of a population of random initial solutions, while in the big crunch phase these solutions are shrunk into one elite solution exhibited by a mass center. This study looks into the BBBC’s effectiveness in assignment and scheduling problems. Where it was enhanced by incorporating an elite pool of diverse and high quality solutions; a simple descent heuristic as a local search method; implicit recombination; Euclidean distance; dynamic population size; and elitism strategies. Those strategies provide a balanced search of diverse and good quality population. The investigation is conducted by comparing the proposed BBBC with similar metaheuristics. The BBBC is tested on three different classes of combinatorial optimization problems; namely, quadratic assignment, bin packing, and job shop scheduling problems. Where the incorporated strategies have a greater impact on the BBBC's performance. Experiments showed that the BBBC maintains a good balance between diversity and quality which produces high-quality solutions, and outperforms other identical metaheuristics (e.g. swarm intelligence and evolutionary algorithms) reported in the literature.

Keywords


Big bang-big crunch metaheuristic; quadratic assignment; bin packing; job shop scheduling; combinatorial optimization; operational problems.

Full Text:

PDF


DOI: http://doi.org/10.11591/ijece.v10i3.pp2484-2502
Total views : 44 times

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.