《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (5): 1372-1377.DOI: 10.11772/j.issn.1001-9081.2023121865

所属专题: 进化计算专题(2024年第5期“进化计算专题”导读,全文即将上线)

• 进化计算专题 • 上一篇    

概率驱动的动态多目标多智能体协同调度进化优化

刘晓芳, 张军()   

  1. 南开大学 人工智能学院,天津 300350
  • 收稿日期:2024-01-05 接受日期:2024-01-23 发布日期:2024-04-26 出版日期:2024-05-10
  • 通讯作者: 张军
  • 作者简介:刘晓芳(1993—),女,广东汕头人,讲师,博士,CCF会员,主要研究方向:群体智能、进化计算、多智能体系统
    第一联系人:张军(1967—),男,天津人,教授,博士,CCF会员,主要研究方向:群体智能、演化计算、云计算。
  • 基金资助:
    国家自然科学青年基金资助项目(62103202);天津市科技计划项目(24JRRCRC00030)

Probability-driven dynamic multiobjective evolutionary optimization for multi-agent cooperative scheduling

Xiaofang LIU, Jun ZHANG()   

  1. College of Artificial Intelligence,Nankai University,Tianjin 300350,China
  • Received:2024-01-05 Accepted:2024-01-23 Online:2024-04-26 Published:2024-05-10
  • Contact: Jun ZHANG
  • About author:LIU Xiaofang, born in 1993, Ph. D., lecturer. Her research interests include swarm intelligence, evolutionary computation, multi-agent systems.
  • Supported by:
    National Natural ScienceFoundation of China(62103202)

摘要:

在多智能体系统中,协作任务往往动态变化,且存在多个冲突的优化目标,因此动态多目标多智能体协同调度问题已经成为亟须解决的关键问题之一。针对动态环境下多智能体协同调度需求,提出了概率驱动的动态预测策略,旨在有效利用历史环境概率分布,预测决策解在新环境的概率分布,从而生成新的多智能体调度方案,实现调度算法在动态环境下的快速响应。具体来讲,设计了基于元素的概率分布表达,以表示解的构成元素在动态环境的适应性,并根据优化算法迭代最优解逐步更新概率分布以趋近实际分布;构建了基于融合的概率分布预测机制,考虑到环境变化的连续性和相关性,当环境变化时,通过融合历史概率分布预测新环境的概率分布,为新环境优化提供先验知识;提出了基于启发式的新解采样机制,结合概率分布和启发式信息,生成解方案以更新过时种群。将概率驱动的动态预测策略嵌入新型的多目标进化算法,获得概率驱动的动态多目标进化算法。在10个动态多目标多智能体协同调度问题实例上,实验结果表明,所提算法在解最优性和多样性上显著优于已有多目标进化算法,所提的概率驱动的动态预测策略能够提高多目标进化算法对动态环境的适应能力。

关键词: 动态多目标优化, 粒子群优化, 进化计算, 多智能体协同调度, 概率驱动

Abstract:

In multi-agent systems, there are multiple cooperative tasks that change with time and multiple conflict optimization objective functions. To build a multi-agent system, the dynamic multiobjective multi-agent cooperative scheduling problem becomes one of critical problems. To solve this problem, a probability-driven dynamic prediction strategy was proposed to utilize the probability distributions in historical environments to predict the ones in new environments, thus generating new solutions and realizing the fast response to environmental changes. In detail, an element-based representation for probability distributions was designed to represent the adaptability of elements in dynamic environments, and the probability distributions were gradually updated towards real distributions according to the best solutions found by optimization algorithms in each iteration. Taking into account continuity and relevance of environmental changes, a fusion-based prediction mechanism was built to predict the probability distributions and to provide a priori knowledge of new environments by fusing historical probability distributions when the environment changes. A new heuristic-based sampling mechanism was also proposed by combining probability distributions and heuristic information to generate new solutions for updating out-of-date populations. The proposed probability-driven dynamic prediction strategy can be inserted into any multiobjective evolutionary algorithms, resulting in probability-driven dynamic multiobjective evolutionary algorithms. Experimental results on 10 dynamic multiobjective multi-agent cooperative scheduling problem instances show that the proposed algorithms outperform the competing algorithms in terms of solution optimality and diversity, and the proposed probability-driven dynamic prediction strategy can improve the performance of multiobjective evolutionary algorithms in dynamic environments.

Key words: dynamic multiobjective optimization, particle swarm optimization, evolutionary computation, multi-agent cooperative scheduling, probability driven

中图分类号: