Population-Based Redundancy Control in Genetic Algorithms: Enhancing Max-Cut Optimization

Yong-Hyuk Kim, Zong Woo Geem and Yourim Yoon ()
Additional contact information
Yong-Hyuk Kim: School of Software, Kwangwoon University, 20 Kwangwoon-ro, Nowon-gu, Seoul 01897, Republic of Korea
Zong Woo Geem: Department of Smart City, Gachon University, 1342 Seongnamdaero, Sujeong-gu, Seongnam-si 13120, Republic of Korea
Yourim Yoon: Department of Computer Engineering, Gachon University, 1342 Seongnamdaero, Sujeong-gu, Seongnam-si 13120, Republic of Korea

Mathematics, 2025, vol. 13, issue 9, 1-21

Abstract: The max-cut problem is a well-known topic in combinatorial optimization, with a wide range of practical applications. Given its NP-hard nature, heuristic approaches—such as genetic algorithms, tabu search, and harmony search—have been extensively employed. Recent research has demonstrated that harmony search can outperform genetic algorithms by effectively avoiding redundant searches, a strategy similar to tabu search. In this study, we propose a modified genetic algorithm that integrates tabu search to enhance solution quality. By preventing repeated exploration of previously visited solutions, the proposed method significantly improves the efficiency of traditional genetic algorithms and achieves performance levels comparable to harmony search. The experimental results confirm that the proposed algorithm outperforms standard genetic algorithms on the max-cut problem. This work demonstrates the effectiveness of combining tabu search with genetic algorithms and offers valuable insights into the enhancement of heuristic optimization techniques. The novelty of our approach lies in integrating solution-level tabu constraints directly into the genetic algorithm’s population dynamics, enabling redundancy prevention without additional memory overhead, a strategy not previously explored in the proposed hybrids.

Keywords: genetic algorithm; tabu search; max-cut problem; hybrid metaheuristics; redundant search prevention; combinatorial optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/9/1409/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/9/1409/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:9:p:1409-:d:1642474

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().