Estimation of Distribution Algorithm for the Max-Cut Problem

Abstract.In this paper, we investigate theMax-Cutproblem and pro-pose a probabilistic heuristic to address its classic and weighted version.Our approach is based on the Estimation of Distribution Algorithm(EDA) that creates a population of individuals capable of evolving ateach generation towards the global solution. We have applied theMax-Cutproblem for image segmentation and de ned the edges' weights asa modi ed function of the L2 norm between the RGB values of nodes.The main goal of this paper is to introduce a heuristic forMax-Cutandadditionally to investigate how it can be applied in the segmentation context.