一种基于改进的帝国竞争算法的智能排产算法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN110363368A(43)申请公布日2019.10.22(21)申请号201810320429.7(22)申请日2018.04.11(71)申请人西安邮电大学地址710121陕西省西安市长安区西长安街西安邮电大学长安校区(72)发明人王忠民宋国豪苑庆涛蔺伟张恒山(51)Int.Cl.G06Q10/06(2012.01)G06Q50/04(2012.01)权利要求书2页说明书5页附图2页(54)发明名称一种基于改进的帝国竞争算法的智能排产算法(57)摘要本发明提供一种基于改进的帝国竞争算法的智能排产方法，解决了现有的帝国竞争算法在排产调度问题中的应用不足的问题。每一个国家都是由一个实数组或向量来表示，代表一个特定的优化问题的优化结果。帝国内同化部分采用离散型帝国竞争算法中的内容实现，即交叉变异操作，从而将殖民地国家与帝国主义国家之间通过优良信息进行交换的方式使得优良信息得以共享，有效地引导算法向最优解方向搜索。在帝国竞争之后，增加殖民地改革操作，即借鉴了遗传算法中的变异算子，通过殖民地随机突变来增加算法全局搜索空间。帝国消除部分为了有利于算法收敛，保留较优个体，即失去所有殖民地的帝国，使得进化过程中能够找到更优解。CN110363368ACN110363368A权利要求书1/2页1.一种基于改进的帝国竞争算法的智能排产方法，其特征在于，包括以下步骤：步骤1:参数设置，设置帝国竞争算法求解柔性作业车间调度问题的相关参数，包括：国家数量Npop、帝国主义国家数量Nimp、殖民地国家数量Ncol、迭代次数Niter；步骤2：初始化国家个体，每一个国家代表一组生产排产调度问题的可行方案，随机产生Npop个体；步骤3：通过代价函数，计算每个国家的代价函数值；步骤4：产生帝国主义国家和殖民地国家，按照每个国家的代价函数值计算每个国家的势力大小，依据之前设定的帝国主义国家数量，从中选取势力较大的前Nimp个国家作为帝国主义国家，剩下的Ncol个国家作为这些帝国的殖民地，相应的帝国和殖民地组成一个帝国集团；步骤5：帝国内部进行同化操作，帝国内部的殖民地国家与帝国主义国家之间进行同化操作，使得殖民地国家不断向帝国主义国家移动；步骤6：帝国内部判断是否更换帝国主义国家，当殖民地向帝国移动的过程中，它的势力可能会比其所属帝国的势力更大，在这种情况下，交换帝国和殖民地的位置；步骤7：帝国之间的竞争操作，势力最强的帝国占有势力最弱的帝国中的殖民地，使得强大的帝国更加强大，弱小的帝国更加弱小；步骤8：殖民地改革操作，帝国内部的殖民地国家为防止同化作用造成过早收敛，需要进行革命操作；步骤9：帝国消除操作，帝国之间的竞争，势力较大的帝国通过占有其他帝国的殖民地变得日益强大，而势力较小的帝国其殖民地个数却不断减少，当没有殖民地时，保留该个体并将其归属于占有它最后一个殖民地的帝国；步骤10：重新计算每个国家的代价函数值；步骤11：判断算法是否终止，算法不断迭代，当只存在一个帝国或者达到迭代次数时，算法结束；反之，算法还没有终止，则回到步骤5继续执行。2.如权利要求1所述的一种基于改进的帝国竞争算法的智能排产方法，其特征是，所述步骤5中的帝国内部进行同化操作：借鉴遗传算法中的交叉和变异操作，实现了殖民地向帝国的移动，以及移动过程中的偏移；采用如下所示的两点交叉方法,随机的选择两个基因片段并交换它们的位置。3.如权利要求1所述的一种基于改进的帝国竞争算法的智能排产方法，其特征是，所述步骤8中的殖民地改革操作：表现为随机选取殖民地两个位置的编号进行交换；在避免无效随机搜索的同时,能够充分发挥革命机制保持种群多样性功能,从运算代数和所属帝国权力两方面对革命概率Pminp建立调节公式：(1)其中：Pminp为殖民地所属殖民国家的标准化势力，pmax为所有殖民国家中最大的标准化势力：n为当前运算迭代次数，Niter为总共迭代次数，默认p0=0.3；对于权力越小的殖民国家，该帝国内所有殖民地革命的概率越大，这可以促进解的不断优化。4.如权利要求1所述的一种基于改进的帝国竞争算法的智能排产方法，其特征是，所述2CN110363368A权利要求书2/2页步骤9中的帝国消除操作：帝国之间的竞争，势力较大的帝国通过占有其他帝国的殖民地变得日益强大，而势力较小的帝国其殖民地个数却不断减少；当一个帝国失去所有的殖民地时，消除该帝国；然而这样就损失了优势个体，不利于算法收敛，由于该帝国个体优于一般殖民地国家，因此保留该个体并将其归属于占有它最后一个殖民地的帝国；保留较优个体，使得进化过程中能够找到更优解。3CN110363368A说明书1/5页一种基于改进的帝国竞争算法的智能排产算法技术领域[0001]本发明涉及