In this paper a novel fuzzy cluster analysis algorithm based on simulated annealing (FCASA) is proposed. Instead of the perturbation criterion of the literature in which membership grades of several samples may be changed simultaneously in each perturbation or perhaps each sample has unequal probability of perturbation, the present method changes the membership grades of several samples among all samples in each perturbation cycle at first, then only the membership grade of one sample in each perturbation cycle is changed when the number of iterations at a given temperature (see the Theory section for details) equals half of the desired number (i.e. the Metropolis sampling number). The algorithm is first tested with the Fisher data set and a simulated data set, then it is used for the classification of phenolic compounds, based on their parameters of molecular connectivity index and partition coefficient calculated by the present authors, and Chinese tea samples. The results obtained from both simulated data and practical samples show that the proposed algorithm is more feasible than the general fuzzy cluster analysis (GFCA) algorithm in obtaining a global or near-global optimum. Besides, the present method based on the modified perturbation criterion can save much time in getting the optimal solution of a particular problem.