约束满足问题是人工智能的核心，约束满足技术越来越广泛地应用在工程技术和计算机科学的诸多领域中。近年来，人们发现随机不完全搜索算法，特别是局部搜索算法，能有效地解决大规模的约束满足问题(CSP)。许多局部搜索算法都加入了跳出局部极小的机制来提高算法性能。 通用的局部搜索算法GENET是一个基于连接主义的约束求解方法。在GENET中，用一个网络来表示CSP，其中节点代表对变量的可能赋值，边代表约束。GENET的创新之一在于它对每条边引入一个可修改的权值，代价函数是所有被违反约束的权值和。它采用的最小冲突启发式修补过程能保证GENET收敛到某些状态，这些状态要么是解，要么是局部极小点。每当收敛到局部极小点时，将被违反的约束的权值减1，重新进行搜索，从而使GENET跳出局部极小，直到找到解或满足终止条件。 本文从多个方面对GENET进行了扩展和改进。首先，我们加入快速确定合理权值和防止代价函数过度变形的方法，构造了RQ-GENET算法。同时引入“启发式替换策略”来提高目标函数值较小时的搜索效率。HRT算法是RQ-GENET和“启发式替换策略”相结合的结果，在解一些出名频率分配问题的的基准测试范例时，RQ-GENET、HRT比GENET快10倍以上。 其次，我们从GENET等权值学习算法中抽象总结出一个直观通用的简单权值学习算法——SWLA。我们对SWLA进行了两方面的改进形成MCWLA算法：为了避免权值持续增大而产生的不利影响，我们引入一个按比例降低权值的过程使权值的平均值保持大致不变；同时，为了尽可能多地利用局部搜索的中间信息，使算法可以在近似最优解的基础上进行范围更广、更接近解的搜索，我们还提出基于权值的交叉算子。MCWLA算法在解特别难的图着色问题实例时，性能超过著名的GSAT算法，并能在合理时间内求得GSAT无法求得的最优解。 最后，我们研究了权值学习算法和领域知识相结合的方法，提出“强约束”和“弱约束”的概念，指出结合问题相关的特性，在算法中加入将“强约束违反”转化为“弱约束违反”的过程，能非常明显地提高解题效率。在该思想指导下， 我们提出求解大学考试时间表问题的＊＊Wl刀算法。在求解一些标准测试范 例的实验中，该算法大大优于GENET，而且比目前被认为最适合于求解时间表 问题的演化算法快了 100多倍。 我们的研究结果表明：为了提高搜索的效率，必须保证搜索的指导性和候选 解的多样性，若在搜索过程中结合多种搜索策略就能较好地平度上述两个要求。 ． 此外，在实际应用中充分利用问题的特性能最大限度地提高效率。． 约束满足问题是知识表示的一个良好模型，我们提出的新算i去在求解CSP 多个领域的著名测试范例时，显示出较高的性能。约束理论和技术将在社会的诸 多方面起着越来越大的作用，本研究工作在约束求解理论及其实际应用上都是很 有意义的。