4.4.4.2 联合调度模型求解
联合调度优化问题是多目标优化问题,因此,引入Pareto非支配排序,提出一种基于Pareto人工蜂群的多目标调度算法,解决灌片相互竞争的水资源调度问题,获得非支配集合,并根据模型寻找非支配集合中的最优解,从而获得存在多个灌片情况下的权衡调度方案。具体求解原理如下:
(1)食物源初始化
由于传统人工蜂群算法无法直接作用于调度问题的求解,现对问题解进行预编码操作,所提算法使用不定长一维向量编码方式,以解决防汛物资调度决策问题。
①需求优先:不同灌片的灌水需求不同。在同一集合内,根据各个灌片的需求大小,按轮盘赌规则优先将水资源调配给水量需求大的灌片。
②随机分配:随机分配水资源。
每个初始解均由上述2种规则产生,其解集比例设置为30%、30%、40%。然而,上述3种操作均可能会造成部分食物源不满足约束。因此,初始化食物源后,需要检查食物源是否符合约束条件。若不符合约束条件,则均需削减被过多分配的水资源。经过食物源修正,可获得满足约束条件的水资源。
(2)适应度值计算
针对调度的紧急性和公平性,建立调度优化模型。在雇佣蜂阶段和跟随蜂阶段,需要计算每一个救援点的适应度Fj,进行小生境和最小支配集选择等操作,计算如下:
![]()
完成算法求解后,根据获得的最小支配集,计算其集合内所有食物源的总体评价值Fz,选择具有最大值的食物源,作为本算法的最优解,计算如下:(https://www.daowen.com)
![]()
(3)雇佣蜂阶段
按照生成食物源,雇佣蜂在小生境中根据灌区数量,将整个食物源分成多个子类,随后通过变邻域局部搜索操作对每一个食物源附近未知解空间进行搜索,获得多个子代食物源。分析子代食物源和父代食物源的支配关系,获得下一代种群。再通过小生境中的精英保留和排挤策略使得食物源集合大小恢复至初始规模。小生境操作和变邻域局部搜索操作如下。
①小生境操作
小生境来自生物学的一个概念,是指特定环境下的一种生存环境。生物在其进化过程中,一般总是与自己相同的物种生活在一起,共同繁衍后代。小生境操作就是将每一代个体划分为若干类,每个类中选出若干适应度较高的个体作为一个类的优秀代表组成一个种群,再在种群中以及不同种群之间,采用精英保留和排挤策略产生新一代个体群。
计算各个食物源的适应度值Fj,对其进行归一化处理,将食物源划入归一化后其适应度值Fj最大的子类种群,由此将整个食物源种群划分为多个子类。在其子类种群内部针对最大适应度值Fj,对食物源进行变邻域局部搜索操作,增强算法的局部寻优能力,获得多个新食物源。若新食物源支配旧食物源,则更新旧食物源;如果旧食物源支配新食物源,则删除该新食物源,或不改变旧食物源,将新食物源放到临时食物源集合。完成变邻域搜索操作后,将食物源集合与临时食物源集合合并成下一代种群。
最后,计算下一代种群中食物源的数量,如果该食物源数量超过初始规模,则在种群中随机选取多个食物源组成排挤成员集合,计算下一代群体中其他食物源和排挤成员的相似性:选择当前食物源,计算该食物源与排挤成员集合中每一个排挤成员在食物源编码相同位置上数值相同的个数,选择最大值作为该食物源的相同度Ai,计算在食物源编码相同位置上数值的差值和,选择最大值作为该食物源的差异度Bi。根据相同度对种群中除排挤成员以外的食物源进行从大到小排序,存在多个食物源相同度一致时,则根据差异度对这些食物源进行从小到大的排序,最终获得排序的食物源。依次淘汰排在前面的食物源,直至种群数量恢复至初始规模,且如果被淘汰食物源为子代种群中的局部最优解或全局最优解,则跳过该食物源,以实现精英解的保留。
②变邻域局部搜索操作
变邻域搜索方法是一种改进的局部搜索方法,它利用不同的动作构成的邻域结构进行交替搜索,在集中性和疏散性之间达到很好的平衡。为方便实现变邻域搜索操作,须将初始食物源转化为多维实数矩阵Qijv。其中,i代表储备仓库(即行a),j代表救援点(即列b),v代表防汛物资种类(即b下属各列),Q值为防汛物资数量。若某储备仓库无某类防汛物资数量储备,其Q值用Nan标识符代替0值,使得在计算时自动跳过Nan标识,以提高搜索效率。根据小生境策略,食物源基于救援点数量被划分为类(即b1,b2,b3,…,bn类),对隶属于bi类的食物源中救援点bi进行变邻域搜索,从而提高该救援点的资源调度最优化,提高救援点之间的相互竞争性,得到局部最优食物源。