Solving MAX-SAT Problem by Binary Biogeograph-based Optimization Algorithm

Document Type

Conference Proceeding

Source of Publication

2019 IEEE 10th Annual Information Technology, Electronics and Mobile Communication Conference, IEMCON 2019

Publication Date

10-1-2019

Abstract

© 2019 IEEE. Several sensing problems in wireless sensor networks (WSNs) can be modeled to maximum satisfaction (MAX-SAT) or SAT problems. Also, MAX-SAT is an established framework for computationally expensive problems in other fields. There exist efficient algorithms to solve the MAX-SAT, which is an NP-hard problem. The reason for remodeling various sensing problems to MAX-SAT is to use these algorithms to solve challenging sensing problems. In this paper, we test a binary Biogeography-based (BBBO) algorithm for the MAX-SAT as an optimization problem with a binary search space. The original BBO is a swarm intelligence-based algorithm, which is well-tested for continuous (and nonbinary) integer space optimization problems, but its use for the binary space was limited. Since the exact algorithm to solve the MAX-SAT problem using moderate computing resources is not well-known; therefore, swarm intelligence based evolutionary algorithms (EAs) can be helpful to find better approximate solutions with limited computing resources. Our simulation results demonstrate the experimental exploration of the binary BBO algorithm against binary (enhanced fireworks algorithm) EFWA, discrete ABC (DisABC) and Genetic Algorithm (GA) for several classes of MAX-SAT problem instances.

ISBN

9781728125305

Publisher

Institute of Electrical and Electronics Engineers Inc.

First Page

1092

Last Page

1097

Disciplines

Computer Sciences

Keywords

biogeography, fireworks algorithm, MAX-SAT, optimization, swarm intelligence

Scopus ID

85077962534

Indexed in Scopus

yes

Open Access

no

Link to Full Text

Share

COinS