A microservice-based system is composed of a set of microservices that are developed and deployed independently for agile DevOps. Intensive and iterative adaptations/upgrades of microservices are essential for such systems to adapt to user requirement changes and DevOps, and as a consequence, result in the phenomenon of "multi-version microservice coexistence" in a system. Besides traditional API-based functional dependencies between different microservices, there appear complicated dependencies between different versions of difference microservices, which dramatically deteriorate the maintainability of microservice systems, especially when systems evolve to adapt to user requirement changes and DevOps. To meet this challenge, a version dependency model is proposed for describing the complex dependencies between different versions of microservices, and greedy-based optimization algorithms are developed for generating an optimal evolution plan according to changes in user requirements and DevOps at different scenarios. A programming framework (MF4MS) and cloud-edge based infrastructure (MI4MS) are implemented to facilitate microservice systems to automatically execute the evolution plan. Experiments show that the proposed approach performs well on service down time, service availability, and the developers' cost of DevOps coping with self-adaptation in the situation where complicated version dependencies exist.