Exploring testing possibilities at an early software life cycle is becoming increasingly necessary to improve the reliability of a system. It facilitates the removal of most of the errors at the earliest, thereby avoiding propagation of defects to the subsequent phases. Constraint-Based Testing (CBT) is a prominent form of functional testing approach that can be performed at the earliest. The efficiency of CBT can be improved by combining it with the Search Based Testing (SBT) technique, in which case SBT can be used to produce test suites while the constraints can be used to guide the test case generation process. Hence, the proposed work combines OCL (Object Constraint Language) and hybrid Harmony Search – Quick Artificial Bee Colony (HS-qABC) algorithm to generate efficient test cases. Furthermore, a novel predicate-based fitness function named as exit-predicate-wise branch coverage (EPWBC) is defined to evaluate the generated test data. The experimental results indicate that OCL constraint-based testing adopting hybrid HS-qABC algorithm forms an excellent combination to produce more test coverage and optimal test suite. Furthermore, it has been inferred that hybrid HS-qABC algorithm outperforms the other search approaches in test suite optimization.