最小化差别疏散性问题（Min-Diff DP）是一个有着广泛应用的组合优化问题,属于NP难问题。给定n个元素及元素之间的距离矩阵,最小化差别疏散性问题的目标是确定m（m<n）个元素的子集,使得子集中各个元素跟子集中其它元素节点的距离之和的差距最小。这样通过最小化所选元素之间的距离差异,保证了所选子集的均衡性。此类问题在实际生活中的应用范围很广,例如在城市公共设施的选址问题中,为了尽可能让所有民众都能接触到学校医院和公园等设施,需要保证公共设施选址的公平性。此外在同质群的选择、基于公平的网络流量计量、稠密子图的识别问题中也有重大应用价值。因此,该问题在生活生产中的应用广泛,研究解决该问题的算法对于解决实际问题有着重要的价值。本文在IDTS算法[1]和HEAD算法[2]的基础上提出了强扰动的禁忌搜索算法（SPDTS）和基于两个解的混合进化算法（TIHE）,强扰动的禁忌搜索算法采用了受约束的邻域空间、基于解的禁忌策略和强扰动搜索机制,不同于典型的禁忌属性策略,基于解的禁忌使得搜索过程更加集中,同时使用哈希函数能够快速确定解的禁忌状态,强扰动策略的搜索能够使搜索区域跳转到一个更远的搜索空间。基于两个解的混合进化算法使用禁忌搜索和种群内部的交叉操作来搜索更好的解,保证了算法的分散性和集中性。在250个基准算例的测试对比中,强扰动的禁忌搜索算法（SPDTS）改进了35个算例,101个算例与目前最优的求解结果相同;而基于两个解的混合进化算法（TIHE）改进了44个算例,103个算例与目前最优的求解结果相同。通过测试比较基于解的禁忌策略和扰动策略对算法搜索能力的影响,证明了两个策略的重要性。同时由于基于两个解的混合进化算法（TIHE）框架的通用性,因此对于求解其它疏散性问题也有一定的价值意义。