2023/07/19 by A. Chaouche, Chaouche, Ali, Menouar Boulif +1
Computer Science · Engineering · #68W50 #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Mathematics #I.2.8 #Neural and Evolutionary Computing (cs.NE) #Optimization and Control (math.OC) #VLSI and FPGA Design Techniques #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2307.10410
openalex publication_date 2023/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The graph partitioning problem (GPP) is among the most challenging models in optimization. Because of its NP-hardness, the researchers directed their interest towards approximate methods such as the genetic algorithms (GA). The edge-based GA has shown promising results when solving GPP. However, for big dense instances, the size of the encoding representation becomes too huge and affects GA's efficiency. In this paper, we investigate the impact of modifying the size of the chromosomes on the edge based GA by reducing the GPP edge set. We study the GA performance with different levels of reductions, and we report the obtained results.