As a new mode of Internet applications, cloud computing will become the future access to the dominant way of services and information. In cloud computing environment is more suitable for virtual enterprise, it is more powerful. In order to study how to measure Agility of Cloud-based Virtual Enterprise (CVE), the relationship between CVE and its member is analyzed first. Base on it, a new method using Bayesian Regularized Neural Network (BRNN) for Agility Evaluation of Virtual Enterprise is developed. A simulative example illustrates the usefulness of the proposed method. In contrast to the standard BP neural network, the result shows that BRNN overcome the over-fitting problems, it can be used to measure any size of CVE.