A multi-agent optimization algorithm for resource constrained project scheduling problem

In this paper, a multi-agent optimization algorithm (MAOA) is proposed for solving the resourceconstrained project scheduling problem (RCPSP). In the MAOA, multiple agents work in a grouped environment where each agent represents a feasible solution. The evolution of agents is achieved by using
four main elements in the MAOA, including social behavior, autonomous behavior, self-learning, and
environment adjustment. The social behavior includes the global one and the local one for performing
exploration. Through the global social behavior, the leader agent in every group is guided by the global
best leader. Through the local social behavior, each agent is guided by its own leader agent. Through the
autonomous behavior, each agent exploits its own neighborhood. Through the self-learning, the best
agent performs an intensified search to further exploit the promising region. Meanwhile, some agents
perform migration among groups to adjust the environment dynamically for information sharing. The
implementation of the MAOA for solving the RCPSP is presented in detail, and the effect of key parameters of the MAOA is investigated based on the Taguchi method of design of experiment. Numerical testing
results are provided by using three sets of benchmarking instances. The comparisons to the existing algorithms demonstrate the effectiveness of the proposed MAOA for solving the RCPSP.

本文针对资源受限项目调度问题（Resource-Constrained Project Scheduling Problem，RCPSP），提出了一种多智能体优化算法（Multi-Agent Optimization Algorithm，MAOA）。在该算法中，多个智能体运行于分组化环境内，每个智能体对应一个可行解。智能体的演化通过算法四大核心要素实现，分别为社会行为、自主行为、自学习与环境调整。其中，社会行为包含全局社会行为与局部社会行为，用于执行探索操作：全局社会行为下，各分组内的领导者智能体受全局最优领导者引导；局部社会行为下，各智能体接收其所属分组领导者的引导。自主行为环节中，各智能体对自身邻域进行开发探索。自学习环节中，最优智能体执行强化搜索，以进一步开发高潜力区域。与此同时，部分智能体将在不同分组间迁移，动态调整环境以实现信息共享。本文详细阐述了针对RCPSP的MAOA实现流程，并基于田口实验设计法对算法关键参数的影响开展了研究。本文采用三组基准测试实例完成数值测试并给出相关结果，与现有算法的对比实验验证了所提MAOA在求解RCPSP上的有效性。