Melola Discovery

← Melola Discovery

Open access Jurnal SINTA 1

Binary BAT algorithm with greedy repair for the discounted 0-1 knapsack problem

International Journal of Electrical and Computer Engineering (IJECE) · Vol. 16 No. 5 (2026)

DOI
10.11591/ijece.v16i5.pp2680-2687
ISSN
2722-2578, 2088-8708
Published
2026-10-01
Publisher
Institute of Advanced Engineering and Science
License
creativecommons.org/licenses/by-sa/4.0

Abstract

The discounted 0-1 knapsack problem (D0-1KP) generalizes the classical knapsack problem by partitioning items into groups of three, in which the third item of every group represents a discounted bundle of the first two and at most one item per group may be loaded. This grouping constraint enlarges the search space and makes the problem markedly harder than its classical counterpart. This paper presents BBAT, a binary bat algorithm for the D0-1KP. Bat velocities are mapped to selection probabilities through a sigmoid transfer function, and a greedy repair-and-optimization operator restores feasibility while raising the profit of every candidate solution. The algorithm keeps the small parameter set of the original bat metaheuristic, which limits the tuning effort required before deployment. BBAT was assessed on 14 benchmark instances drawn from the inverse strongly correlated and strongly correlated families, with 30 independent runs per instance. Against two elite genetic algorithms, BBAT improved the best profit found on 12 of the 14 instances and improved the mean profit on 7 of them. The gain in mean profit is concentrated on the inverse strongly correlated family, whereas on strongly correlated instances BBAT attains better peaks at the cost of higher run-to-run variance. These results identify BBAT as a competitive but variance-sensitive solver for the D0-1KP.

Collaboration network of the authors

No co-authors found in Melola yet.

This record comes from Crossref (what the publisher deposited), because the journal's own OAI-PMH endpoint could not be harvested.

Metadata source: Crossref API (cadangan, berdasarkan ISSN) https://api.crossref.org/journals/2088-8708/works, first harvested 27 Okt 2026, last seen 27 Okt 2026.
Metadata as oai_dc, converted from Crossref
<oai_dc:dc xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/"><dc:title>Binary BAT algorithm with greedy repair for the discounted 0-1 knapsack problem</dc:title><dc:creator>Truong, Tung Khac</dc:creator><dc:description>&lt;jats:p&gt;The discounted 0-1 knapsack problem (D0-1KP) generalizes the classical knapsack problem by partitioning items into groups of three, in which the third item of every group represents a discounted bundle of the first two and at most one item per group may be loaded. This grouping constraint enlarges the search space and makes the problem markedly harder than its classical counterpart. This paper presents BBAT, a binary bat algorithm for the D0-1KP. Bat velocities are mapped to selection probabilities through a sigmoid transfer function, and a greedy repair-and-optimization operator restores feasibility while raising the profit of every candidate solution. The algorithm keeps the small parameter set of the original bat metaheuristic, which limits the tuning effort required before deployment. BBAT was assessed on 14 benchmark instances drawn from the inverse strongly correlated and strongly correlated families, with 30 independent runs per instance. Against two elite genetic algorithms, BBAT improved the best profit found on 12 of the 14 instances and improved the mean profit on 7 of them. The gain in mean profit is concentrated on the inverse strongly correlated family, whereas on strongly correlated instances BBAT attains better peaks at the cost of higher run-to-run variance. These results identify BBAT as a competitive but variance-sensitive solver for the D0-1KP.&lt;/jats:p&gt;</dc:description><dc:publisher>Institute of Advanced Engineering and Science</dc:publisher><dc:date>2026-10-01</dc:date><dc:type>info:eu-repo/semantics/article</dc:type><dc:format>application/pdf</dc:format><dc:identifier>https://doi.org/10.11591/ijece.v16i5.pp2680-2687</dc:identifier><dc:identifier>10.11591/ijece.v16i5.pp2680-2687</dc:identifier><dc:source>International Journal of Electrical and Computer Engineering (IJECE); Vol 16 No 5 (2026); 2680</dc:source><dc:source>2722-2578</dc:source><dc:source>2088-8708</dc:source><dc:relation>https://ijece.iaescore.com/index.php/IJECE/article/viewFile/42153/18889</dc:relation><dc:rights>http://creativecommons.org/licenses/by-sa/4.0</dc:rights></oai_dc:dc>