求解大规模约束满足问题的混合进化算法研究

大规模约束满足问题（CSP）是人工智能、运筹学以及计算机科学研究领域的一个重要分支，是工业应用中广泛面临的困难问题。因此，设计求解CSP问题的高效算法具有重要的理论价值和实际意义。本课题以频率分配问题和大学课程时间表调度问题为研究介质，采用将禁忌算法和进化算法相结合，将问题本质结构融合到启发式算法中，设计求解CSP问题的高效混合进化算法。研究工作主要包括：实现求解CSP问题的自适应禁忌算法，算法根据历史搜索信息动态调整禁忌表长度；实现禁忌算法与进化算法相结合的自适应平衡机制；设计具有语义功能的多亲交叉算符，以产生在未搜索区域内有前途的初始解；群体更新时同时考虑解的优度以及解之间的距离，维护具有多样性的"精英"群体，以达到算法集中性和疏散性的平衡。本课题有望设计出求解频率分配问题和大学课程时间表调度问题的高效混合进化算法，并总结出其在求解大规模CSP问题中的一般规律。

约束满足问题广泛地出现在理论研究和工业应用的各个领域。同时，许多约束优化问题往往可以转化为约束满足问题来进行求解。由于这些问题已被证明为NP难问题，精确算法只能用来求解规模非常小的问题实例或者具有特殊结构的实例。而基于启发式的优化算法可以在有限的计算时间内对大多数不同规模和结构的问题实例找到高质量的解。 本项目主要研究求解约束满足问题的高效混合进行算法。混合进化算法将基于单个解策略的局部搜索算法与基于群体的进化算法相结合，以达到集中性和疏散性之间更好的平衡，往往可以达到更高的搜索效率。..本项目主要围绕几个典型的约束满足问题和约束优化问题进行研究，如频率分配问题、带宽着色问题、人员排班问题、SAT问题、作业调度问题、负载均衡问题。对于这些典型的约束满足问题和约束优化问题，设计了求解这些问题的自适应局部搜索算法和混合进化算法。通过与当前国际文献中的最好的算法结果进行详细地对比和分析，表明了所提出的算法在优度和效率两方面的优势。特别地，本项目中所提出的算法对以上问题均改进了若干国际文献中的最好结果。..同时，针对不同问题的特性，在算法设计方面提出了一些针对问题特性的操作算符，如交叉算符、学习机制、扰动策略等，并对这些针对问题特性的操作算符进行了分析，表明了这些算符或策略对算法性能的重要性和影响。总之，通过本项目的研究，不仅有助于我们设计出求解大规模约束满足问题的高效混合进化算法，还可以帮助我们理解算法中哪些策略是通用的，这些通用策略加以提升就可以用来求解其它的约束满足问题，而哪些策略是针对所求解的具体问题的。