运用协同分布估计算法优化交通调度问题的研究

When dealing with modern transportation scheduling problems with large-scale and high-dimensional problem spaces, traditional centralized optimization algorithms always endure low efficiency and weak global optimization ability. To solve this problem, this project conducts research into cooperatively coevolving estimation of distribution algorithm (EDA). Distributed computational resources are utilized by EDA to improve the computational efficiency in a way of divide-and-conquer, while the cooperative coevolution strategies are adopted to enhance the global exploration ability. First, we apply a density-based clustering approach to decouple the problem space, so as to improve the effectiveness and flexibility of dividing-and-conquering the problem. Then, a hierarchical topology is designed, by which different subcomponents of the problem are optimized from tier to tier, and from global to local. Meanwhile, an asynchronous back-propagation communication protocol is developed to improve the availability of message passing between processors, resulting in high distributed efficiency of the algorithm. Finally, the proposed algorithm will be applied to optimize the urban transportation scheduling problem by fully considering various requirements and conditions of this real-world application. The project is expected to achieve a new and powerful EDA, as well as to improve the intelligence level of urban transportation scheduling.

传统上集中式的智能优化算法在求解大规模高维交通调度问题时的求解效率和寻优效果还有待改进。针对这一问题，本项目开展基于协同分布估计算法的交通调度方案研究，结合分布式计算资源对复杂的调度问题分而治之以提高算法求解效率，并进一步通过协同进化策略加强算法的全局寻优能力。提出基于密度聚类的问题空间解耦策略，提高分治法的有效性和对不同实例的适用性；设计多层树状处理器拓扑结构，实现对交通调度问题空间的逐层剖分优化，有助于同时加强分布估计算法的全局探索和局部寻优；研究异步反馈型通信协议，提高处理器间信息交互的有效性，提高算法分布式处理的效率；最终将所提出的算法运用于城市交通调度优化，充分考虑实际应用中的各项需求，在实践中检验算法性能，并提高城市交通调度的智慧化水平。

本项目面向交通调度这一前沿且重要的应用领域，针对既有方法存在的依赖数学模型、局部寻优、维数障碍等不足之处，开展基于协同演化计算方法的解决方案研究：首先，提出全局、自适应的聚类方法，用于对高维复杂空间进行解耦，提高问题解耦的有效性；其次，针对解耦后的多个子问题，提出小生境多种群分治方法进行处理，提高算法资源分配的有效性；其三，针对异构子种群间的协同，提出异步的分布式演化算法通讯机制，提高多种群协同演化的有效性；最终，将所提出的协同分布式演化计算方法应用于求解实际中的大规模交通调度问题，提高了实际应用的效果。..基于上述研究，项目组共发表/录用标注了本项目基金号的国际期刊和会议论文 27 篇，其中SCI检索论文 16 篇、IEEE Transactions系列国际顶级期刊论文 12 篇。相关成果公开国家发明专利 4 项。通过本课题的研究培养/共同培养了研究生 11 人。圆满地完成了预期任务。项目负责人于2017年入选广东省青年珠江学者。.