In this paper, the performances of two popular stochastic methods, the genetic algorithm (GA) and simulated annealing (SA), are verified in the optimization of low-temperature gas separation processes. While the feasibility of GA optimization of low-temperature processes has recently been addressed, our work studied the quality of GA solutions. Having optimized the solutions of three different case studies, it was observed that SA is more robust and reliable than GA when applied to such systems, and by adjusting the key parameters in the SA method, the optimization process can avoid pre-mature convergence and is able to give the best near-global results.