A modified single and multi-objective bacteria foraging optimization for the solution of quadratic assignment problem

Non-polynomial hard (NP-hard) problems are challenging because no polynomial-time algorithm has yet been discovered to solve them in polynomial time. The Bacteria Foraging Optimization (BFO) algorithm is one of the metaheuristics algorithms that is mostly used for NP-hard problems. BFO is inspired b...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-03
Main Authors: Parvandeh, Saeid, Soltani, Parya, Boroumand, Mohammadreza, Boroumand, Fahimeh
Format: Article
Language:English
Subjects:
Assignment problem
Bacteria
Coliforms
E coli
Genetic algorithms
Heuristic methods
Multiple objective analysis
Operations research
Optimization
Polynomials
Search algorithms
Sorting algorithms
Tabu search
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Non-polynomial hard (NP-hard) problems are challenging because no polynomial-time algorithm has yet been discovered to solve them in polynomial time. The Bacteria Foraging Optimization (BFO) algorithm is one of the metaheuristics algorithms that is mostly used for NP-hard problems. BFO is inspired by the behavior of the bacteria foraging such as Escherichia coli (E-coli). The aim of BFO is to eliminate those bacteria that have weak foraging properties and maintain those bacteria that have breakthrough foraging properties toward the optimum. Despite the strength of this algorithm, most of the problems reaching optimal solutions are time-demanding or impossible. In this paper, we modified single objective BFO by adding a mutation operator and multi-objective BFO (MOBFO) by adding mutation and crossover from genetic algorithm operators to update the solutions in each generation, and local tabu search algorithm to reach the local optimum solution. Additionally, we used a fast nondominated sort algorithm in MOBFO to find the best-nondominated solutions in each generation. We evaluated the performance of the proposed algorithms through a number of single and multi-objective Quadratic Assignment Problem (QAP) instances. The experimental results show that our approaches outperform some previous optimization algorithms in both convergent and divergent solutions.
ISSN:2331-8422