行窃问题(Traveling Thief Problem,TTP)的提出源于人们在生产实践领域越来越多地遇到与其类似的组合优化问题,例如本文提出的测试用例同步约简与排序问题、具有服务利润的限量弧路由问题、网约车调度和外卖配送等问题。TTP问题是由旅行商问题(Traveling Salesman Problem,TSP)和背包问题(Knapsack Problem,KP)复合而成,综合了二者的复杂度,目前为止仍缺乏高性能的确定性方法对其求解。离散粒子群优化作为典型的群体智能算法,在求解这类组合优化问题时,容易遇到算法陷入局部最优解、组合优化问题表现出的特殊性和复杂性等难题。针对这些问题,本文开展的主要研究内容如下。(1)为了提升离散粒子群优化算法求解TSP问题的性能,本文受基因编辑思想启发提出了一种扰动算法,在粒子群进化陷入停滞状态时加速种群跳出局部最优点。扰动算法利用集合型粒子群优化把集合作为粒子编码单位的特点,将集合中的元素看作粒子包含的基因,提出了对粒子基因的评估和编辑策略。仿真实验表明,融合了扰动算法的离散粒子群优化具有良好的性能。(2)利用优化物品分布的启发式经验和改进粒子群优化算法,提出多目标粒子群算法和混合进化算法两种方法求解TTP问题。已知重量较大的物品在靠近终点时选取可以有效降低租金成本。多目标粒子群算法提出将该经验转化为可量化的物品分布优化函数,将该函数和环游路径长度评估函数构成两目标TSP子问题进行求解。在获得路径后,采用新的启发式规则求解KP子问题。混合进化算法是由改进的离散粒子群和遗传算法混合而成。在测试集上进行仿真实验,发现两种算法均表现出较强的竞争力。(3)软件测试用例同步约简与排序问题可以看作TTP问题的典型应用,本文应用求解TTP问题的离散粒子群优化实现该问题的求解。在求解过程中,先后设计了适应于该问题的粒子编码方式、非支配集的建立和维护策略、解决了粒子编码维度过高出现的数据稀疏问题。最后在工业测试数据集上进行仿真实验,结果显示算法获得的最优解集在解的分布性HV指标方面表现突出,获得的精简测试用例集代表性好、缺陷检测能力强。