摘要
自上世纪五十年代以来，组合优化问题逐渐引起各领域学者的关注，其广泛存在于工业、制造、通信、交通等与人类生产生活息息相关的领域，因此研究组合优化问题的求解算法具有重要的理论意义和实际价值。在深度学习技术兴起之前，传统优化方法是解决组合优化问题的主要途径，但随着实际应用中问题规模的不断扩大，传统方法已无法应对大批量且高频的求解需求。随着近十年来硬件算力的极大提升，深度学习技术被更多的应用到实际问题的求解中，由于深度学习不需要专家设计特征，而是从数据中直接学习得到待求解问题的内在结构和特征，以此为基础的求解方法有超越传统解法的趋势。但是，学习模型的泛化性成了深度学习方法的瓶颈。本文研究求解P-中值问题和旅行商问题的强化学习算法，重点是提高算法的泛化性能。 第二章针对P中值问题，提出了基于强化学习和图注意力网络的求解方法，其中深度学习模型采用“编码器.解码器”框架，编码器为带交流机制的多头注意力图神经网络，在多头注意力的基础上加入不同注意力头之间的交流机制，从而使编码器学习到更加有意义的特征;解码器为基于注意力的自回归模型，整个模型使用REINFORCE算法进行训练，在小规模的生成数据和真实数据上都取得了超越传统启发式算法的效果;在大规模问题上，在保证一定求解质量的同时，求解时间要远远快于传统的启发式方法。除此之外，我们根据求解算法在生成数据和实际数据上性能的差异，通过实验揭示了影响学习模型泛化性能的关键因素。 第三章提出了用于提升深度学习求解算法泛化性能的博弈框架，该博弈框架适用于任何组合优化问题和任何深度学习求解算法，该框架基于Policy SpaceResponse Oracle构造学习算法和数据生成器之间的二人零和元博弈，经过多轮博弈后可得到一组在不同分布上具有不同泛化能力的学习算法，再通过模型融合的方法将各个算法进行合并，从而得到一个具有最强泛化能力的模型。在提升模型泛化能力的同时，我们发现随着模型性能的提升，该博弈框架得到的策略逐渐接近纳什均衡，从而体现出该博弈框架的合理性。该框架应用于旅行商问题的求解，实验结果表明，对于同一个学习算法，在使用此框架训练时，其泛化能力有明显的提升。
NETL