Min-SEIS-Cluster is an optimization problem which aims at minimizing the infection spreading in networks. In this problem, nodes can be susceptible to an infection, exposed to an infection, or infectious. One of the main features of this problem is the fact that nodes have different dynamics when interacting with other nodes from the same community. Thus, the problem is characterized by distinct probabilities of infecting nodes from both the same and from different communities. This paper presents a new genetic algorithm that solves the Min-SEIS-Cluster problem. This genetic algorithm surpassed the current heuristic of this problem significantly, reducing the number of infected nodes during the simulation of the epidemics. The results therefore suggest that our new genetic algorithm is the state-of-the-art heuristic to solve this problem.