The selection of Software as a Service (SaaS) in cloud computing relies on providers’ ability to semantically describe the non-functional properties of their services and the non-functional requirements specified by customers. In this work, we model the SaaS selection process as a multi-criteria NP-hard optimization problem. To solve this, we propose a hybrid approach that employs a genetic algorithm, leveraging semantically described micro SaaS services using an ontology. Each micro SaaS is stored alongside compatible SaaS offerings with the same functionality within a single cloud, based on the concept of compatibility. While a single micro SaaS may not fulfill all functional requirements in some cases, a composition of multiple SaaS(s), termed virtual SaaS, can meet the customer’s needs. The selected SaaS must be optimal according to the customer’s specified criteria. The proposed multi-criteria approach integrates a QoS ontology tailored to cloud environments. Simulation results further demonstrate that the proposed method efficiently enables significant SaaS selection within a cloud environment.