Quality of Service (QoS)-aware cloud service composition is one of the pivotal problems in cloud computing. With the seamless proliferation of cloud services, it becomes challenging to obtain an optimal cloud service for composition that satisfies a user's requirements. Many composition models available in the literature compose cloud services based on one or two QoS parameters of the candidate services without considering the complete set. These composition models do not consider the connectivity constraints between the candidate cloud services for satisfying a workflow/function in a service composition. In this paper, we present a novel Optimal Fitness Aware Cloud Service Composition using Modified Invasive Weed Optimization dealing with multiple QoS parameters and satisfying the balancing of QoS parameters and the connectivity constraints of cloud service composition. We evaluate the performance of our approach on a data set of real world cloud services, to select the best optimal fitness aware cloud service composition. By performing the parametric and non-parametric test at 1% level of significance, our proposed method is statistically more accurate than the other methods compared.