In multi-label classification problems, some samples belong to multiple classes simultaneously and thus the classes are not mutually exclusive. How to characterize this kind of correlations between labels has been a key issue for designing a new multi-label classification approach. In this paper, we define two objective functions, i.e., the number of relevant and irrelevant label pairs which are ranked incorrectly, and the model regularization term, which depict the correlations between labels and the model complexity respectively. Then a new kernel machine for multi-label classification is constructed using two-objective minimization and solved by fast and elitist multi-objective genetic algorithm, i.e., NSGA-II. Experiments on the benchmark data set Yeast illustrate that our multi-label method is a competitive candidate for multi-label classification, compared with several state-of-the-art methods.