Protein-Protein Interactions (PPIs) play an important role in various cellular processes. This paper attempts to solve the PPI prediction problem in a multi-objective optimization framework. The scoring functions for the trial solution deal with simultaneous minimization of functional dissimilarity, intra- as well as inter-molecular energy and the difference in phylogenetic profiles of interacting proteins. The above optimization problem is solved using Firefly Algorithm with Non-dominated Sorting. The proposed technique outperforms existing methods, including gene-ontology based Relative Specific Similarity, Fuzzy SVM, phylogenetic profile and evolutionary/swarm algorithm based approaches, with respect to sensitivity, specificity and F1 score.