Measurement principle of axis straightness error of cylindrical parts was introduced based on their roundness profiles. The evaluation models of the center coordinates of four kinds of the reference circles were built, and the evaluation models of the axis straightness errors were established by using the least-square and minimum zone criteria. The roundness profiles of eight simulated cylinders, eight holes, and eight shafts were extracted, and their axis straightness errors were evaluated based on the different reference circles and evaluation criteria. The “minimax” issues in the evaluation process of axis straightness errors were be solved by using Equilibrium Optimizer, and its implementation flows were given. Their evaluation results were analyzed under the used reference circles and evaluation criteria. The analysis results showed that both reference circles and evaluation criteria have much influence on the evaluation results, and that among the evaluation results based on the centers’ coordinates of four reference circles and two evaluation criteria, the axis straightness errors evaluated based on the center coordinates of least-square reference circle and the minimum zone criteria is the least one for most of cylindrical parts, the roundness profiles of which may have no singularities, and the differences among the axis straightness errors evaluated on the basis of different reference circles and different evaluation criteria are very large sometimes, which should be noted in checking whether the axis straightness errors of parts are qualified.