Recent studies have shown that the violation of the Interface Segregation Principle (ISP) is critical for maintaining and evolving software systems. Fat interfaces (i.e., interfaces violating the ISP) change more frequently and degrade the quality of the components coupled to them. According to the ISP the interfaces’ design should force no client to depend on methods it does not invoke. Fat interfaces should be split into smaller interfaces exposing only the methods invoked by groups of clients. However, applying the ISP is a challenging task when fat interfaces are invoked differently by many clients. In this paper, we formulate the problem of applying the ISP as a multi-objective clustering problem and we propose a genetic algorithm to solve it. We evaluate the capability of the proposed genetic algorithm with 42,318 public Java APIs whose clients’ usage has been mined from the Maven repository. The results of this study show that the genetic algorithm outperforms other search based approaches (i.e., random and simulated annealing approaches) in splitting the APIs according to the ISP