The quality-of-service (QoS) is a common focus which users and service providers pay close attention to at present. For service providers, it is one of their main targets to find the optimal QoS strategy based on user preferences. However, because of the fuzziness of user preferences and the complexity of service environment, searching an optimal service strategy becomes a difficult problem. In the paper, how the QoS affects a user's satisfaction is analyzed, and then a quantitative relationship between QoS and user satisfaction is built. Based on the relationship, a user utility model of cloud service is established. In order to maximize user utility, a QoS evolutionary algorithm based on user utility model is proposed. In the algorithm, some improvement is designed to balance the contradiction between search scope and search speed in the traditional genetic algorithm. It can be seen through the experiments that the QoS optimization strategy of cloud service output by the QoS evolutionary algorithm is consistent with the target user's preferences, which can effectively enhance the cost effectiveness of service resources.