随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB（revisedB）模型是一个非平凡的随机约束满足问题，它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这类具有大值域的随机约束满足问题，提出了两种基于模拟退火的改进算法即RSA（revisedsimulatedannealingalgorithm）和GSA（genetic-simulatedannealingalgorithm）。将这两种算法用于求解RB模型的随机实例，数值实验结果表明，在进入相变区域时，RSA和GSA依然可以有效地找到随机实例的解，并且在求解效率上明显优于随机游走算法。