在计算机应用领域,许多工程实践问题可以被建模成离散约束优化问题,其中包括生产规划问题、调度问题、背包问题以及蛋白质结构预测等等。该类问题多具有搜索空间不连续、约束条件复杂以及多局部最优等特点,寻找合适的优化算法求解离散约束优化问题一直是研究工作的重点。本文主要研究设计适应性Memetic算法,求解离散约束优化问题,具体包括集合覆盖问题以及带容量约束的单源设施选址问题。在求解集合覆盖问题时,本文设计了一种基于混合编码的适应性Memetic算法。首先,将集合覆盖问题建模成0-1矩阵中的行列覆盖问题。然后,采用遗传算法框架,将局部搜索策略与遗传算法的突变操作相结合,进行求解。主要工作包括以下四点:(1)设计了一种混合编码的方式来编码解基因以及文化基因,由解基因和文化基因共同组成完整的个体基因。其中,文化基因由行的权值信息组成,反映了每一行被覆盖的难易程度,并随着进化过程不断更新;(2)设计了基于行权值信息调整相关列优先权的机制,进一步提出了一个基于列权值信息的突变操作,同时结合了相应的启发式随机局部搜索策略改善解的质量;(3)为了避免处理由传统交叉操作带来的大量不可行解,本文提出了发生在文化基因上的交叉重组操作,让文化基因参与到进化的过程中,增加种群内部的信息交流以避免搜索陷入局部最优;(4)通过对OR-Library实例集中65个非单位代价实例以及70个单位代价实例的测试,得出实验结果,且对比实验结果表明,基于混合编码的适应性Memetic算法可以高效求解集合覆盖问题。本文进一步设计了一种基于可行性进化的适应性Memetic算法,用于求解带容量约束的单源设施选址。首先,将目标函数看做一个新的约束条件,并在进化过程中,逐步缩减,直到达到最优值。定义一个适应性阈值变量β,并且随着算法的进行自行调节。算法执行过程中淘汰阈值外的个体。对于阈值内的个体,执行随机局部搜索操作改善个体解质量。为了维持种群规模,本文还设计了一个贪心划分交叉操作(Greedy Partition Crossover,GPX)以生成新的个体。主要工作包括以下四点:(1)为了避免对每一个新生成的个体执行局部搜索策略所带来的巨大计算量,本文用可行性进化策略(Viability Evolution)取代遗传算法中的选择操作;(2)为客户与每个设施之间维护了一个基于耗费代价的分数项,分数项随着进化过程更新。进一步提出基于分数项信息的随机局部搜索策略,用于改善解的质量;(3)为了避免由单纯片段交换的交叉操作带来的冗余和冲突问题,针对单源设施选址问题,本文设计了 GPX操作进行基因重组,生成新的个体;(4)通过在OR-Library和Yang实例集上的测试,得出实验结果。对比实验的结果证明,适应性Memetic算法在求解大规模带容量约束的单源设施选址问题时效率高于Cut-and-Solve算法。通过对集合覆盖问题和带容量约束的单源设施选址问题的高效求解,适应性Memetic算法已初步展现出在求解离散约束优化问题上的潜力。