Authors: Šević, Irina
Jovanovic, Raka
Urošević, Dragan 
Davidović, Tatjana 
Affiliations: Computer Science 
Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Fixed Set Search Applied to the Max-Cut Problem
Journal: 2024 IEEE 8th Energy Conference, ENERGYCON 2024 - Proceedings
Issue Date: 1-Jan-2024
Rank: M33
ISBN: 9798350382150
DOI: 10.1109/ENERGYCON58629.2024.10488777
Abstract: 
The Max-Cut Problem (MCP) is a classical NP-hard combinatorial optimization problem for graph partitioning, which has many applications such as optimizing electrical grids, or wireless sensor networks. In the context of this paper, the fixed set search (FSS) which is novel metaheuristic that uses a population-based approach is applied for solving the MCP. Initially, the greedy randomized adaptive search procedure (GRASP) is formulated to address the given problem. Subsequently, the FSS incorporates a learning procedure into the GRASP by identifying common elements within high-quality solutions. The primary benefit of this metaheuristic is the simplicity of implementation. The algorithms are tested on standard benchmark instances. The conducted computational experiments validate that the learning procedure of the FSS enhances the effectiveness of the base GRASP method, and outperforms other population based metaheuristics that include local search procedures like the AntCut and the hierarchical social metaheuristics.
Keywords: Graph partitioning | learning mechanisms | optimizing electrical microgrids | optimizing wireless sensor network | population-based metaheuristics
Publisher: IEEE
Project: 451-03-47/2023-01/200029

Show full item record

Page view(s)

25
checked on Dec 13, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.