Effective representation and understanding of user preferences play a vital role in various applications such as recommender systems, product customization, resource allocation, configuration, and online auctions. Quantitative preferences are often represented using utility functions, while formalisms such as the semi-ring-based Constraint Satisfaction Problem (CSP) and the Valued CSP extend the CSP framework to handle both quantitative preferences and constraints. However, it might not always be convenient for users to quantify their preferences. A qualitative preference ordering can be more natural in these circumstances. The Conditional Preference Network (CP-net) graphical model is designed to express users’ conditional preferences through Conditional Preference Tables (CPTs). In many real-world combinatorial applications, conditional preferences coexist with hard constraints. In this context, the CP-net has been extended to constraints through the constrained CP-net (CCP-net) model. Solving the CCP-net consists in finding a set of Pareto-optimal solutions that meet all constraints while optimizing the qualitative preferences. Finding Pareto solutions in CCP-nets using exact methods like branch and bound can be time-consuming. Alternative methods, trading the quality of the returned solutions for the execution time, can be found in metaheuristics, including nature-inspired techniques. We introduce three bio-inspired methods to enhance the efficiency of finding Pareto solutions in CCP-nets. Additionally, we experimentally compare these techniques with those derived from an exact method, focusing on the number of Pareto solutions identified and the runtime performance. The results of the experiments, conducted on random CCP-net instances generated by the RB model, are reported and discussed.