基于多智能体进化算法的资源受限项目调度方法

摘要

本发明公开一种基于多智能体进化算法的资源受限项目调度方法，属自动控制与信息技术领域。本发明将多智能体系统与进化计算相结合，用于求解资源受限项目调度问题，其特征在于：首先根据两种算法初始化智能体网格中的每个智能体，然后设计了邻域竞争算子、邻域交叉算子、变异算子、自学算子对智能体进行优化，验证结果表明，本发明在评定求解资源受限项目调度问题方法效用的两个方面：求解到最优解的比例和偏离最优解平均误差，都很有优势，是一种有效的求解资源受限项目调度问题的方法，还能扩展到求解其它带有优先关系限制的组合优化问题。

主权项

1.一种基于多智能体进化算法的资源受限项目调度方法，将多智能体系统与进化计算相结合，用于求解资源受限项目调度问题，其特征在于：首先根据两种算法初始化智能体网格中的每个智能体，然后用设计的邻域竞争算子、邻域交叉算子、变异算子和自学习算子对智能体进行优化，具体步骤如下：(1)参数设定：P_c为邻域交叉概率，P_m为变异概率，t为大于或等于0的整数，表示第t代，L^t表示第t代智能体网格，L^t+1/3和L^t+2/3是L^t和L^t+1间的中间代智能体网格，Best^t是L⁰，L¹，…，L^t中最优的智能体，CBest^t是L^t中最优的智能体，rand指随机产生的0到1之间的实数，L_i，j表示处在智能体网格第i行、第j列的智能体，energy(L_i，j)表示智能体L_i，j的能量；(2)初始化智能体网格L⁰，更新Best⁰，令t＝0，网格大小为L_size*L_size，其中L_size为整数，设计为使网格中智能体个数大于或等于项目中任务个数的最小值，每个智能体用一个可行的任务列表表示，即列表中每个任务的所有紧前任务都必须排在这个任务的前面，循环调用算法1和算法2对智能体网格中每个智能体进行编码；(3)对网格L^t中每个智能体执行邻域竞争算子，得到L^t+1/3，表示智能体L_i，j邻域中能量最大的智能体，如果则智能体L_i，j继续存活在网格上，否则，必须死亡，空出的格点由变异产生一个新智能体占据，变异的方法采用插入变异算子，此插入变异算子与一般组合优化的插入变异算子有所不同，变异后任务列表仍须满足任务间优先关系；(4)对L^t+1/3中的每个智能体，若rand＜P_c，则将邻域交叉算子作用在其上，得到L^t+2/3，如果智能体L_i，j满足交叉条件，则将两点交叉算子作用在L_i，j与上，得到两个智能体c₁和c₂，比较这两个智能体的能量，用能量较大的一个替代L_i，j；(5)对L^t+2/3中的每个智能体，若rand＜P_m，则将变异算子作用在其上，得到L^t+1，如果智能体L_i，j满足变异条件，则将插入变异算子作用在其上，该变异算子与步骤(3)中变异算子相同；(6)从L^t+1中找出CBest^t+1，并将自学习算子作用在其上，若智能体L_i，j满足自学习条件，由L_i，j变异产生智能体h₁，变异方法与步骤(3)中变异方法相同，若energy(h₁)＞energy(L_i，j)，则用h₁替代L_i，j且自学习算子停止，否则由h₁继续变异产生一个智能体h₂，与L_i，j比较能量，如果h₂的能量比L_i，j的大，则用h₂替代L_i，j且自学习算子停止，否则继续由h₂变异产生一个智能体与L_i，j比较能量，按照这种方式一直变异，一旦得到一个大于L_i，j能量的智能体，则用该智能体替代L_i，j且自学习算子停止，最大变异次数为20，若还找不到一个智能体使其能量大于L_i，j的能量，则自学习算子停止，L_i，j保持不变；(7)如果energy(CBest^t+1)＞energy(Best^t)，则把CBest^t+1的值赋予Best^t+1，否则，把Best^t的值赋予Best^t+1和CBest^t+1；(8)如果终止条件满足，即得到RCPSP的最优解或者达到最大进化代数，则解码计算最小项目工期输出，否则，令t的值自加1，并转向步骤(3)。