Prescription formulation according to a patient’s syndromes is a core therapeutic method in Traditional Chinese Medicine (TCM). However, classical TCM prescription formulation heavily relies on TCM doctors’ experiences, making it difficult to quantify and standardize and therefore limiting its development with modern information technologies. This paper presents a novel approach for TCM prescription evaluation based on a comprehensive consideration of herb-syndrome effects, herb-herb interactions, prescription-syndrome effects, and prescription-patient effects, and hence models TCM prescription formulation as a complex combinatorial optimization problem, which can be effectively solved by evolutionary algorithms. We develop a set of evolutionary algorithms and test them on real-world instances, the results of which demonstrate the effectiveness of the proposed method in achieving intelligent, personalized, and interpretable TCM prescription formulation that embodies the basic principles of TCM.