A simulated annealing (Metropolis algorithm) optimization routine named AMETROP, which has been developed for use on realistic nuclear fuel cycle problems, is introduced. Each stage of the algorithm is described and the means by which it overcomes or avoids the difficulties posed to conventional optimization routines by such problems are explained. Special attention is given to innovations that enhance AMETROP’s performance both through artificial intelligence features, in which the routine uses the accumulation of data (experience) to influence its future actions, and through a family of simple performance aids, which allow the designer to use his heuristic knowledge (experience) to guide the routine’s essentially random search. Using examples from a typical fuel cycle optimization problem, the performance of the stochastic Metropolis algorithm is compared to that of the only suitable deterministic routine in a standard software library, showing AMETROP to have many advantages.