基于复合型链式P系统的粒子群算法及车间调度问题的研究应用

发布时间：2020-11-01 17:39

　　 膜系统是受生物细胞和组织、器官等启发产生的新的并行计算模型,它的提出引发了一大批学者的研究热潮。其最大的特点是具有分布式和极大并行性,可以用空间的复杂度来换取时间的复杂度,从而大大缩短算法运行的时间。很多研究学者尝试用膜系统来实现或者改进各种编程算法,运用膜系统特有的优势来降低算法的时间复杂性,以求获得更快的运行速度。粒子群算法是智能算法的其中一种,它是受鸟群飞行时的状态启发产生的智能优化算法,因为算法比较简单、收敛速度比较快等特点,粒子群算法在提出之后迅速成为了炙手可热的话题,被国内外研究学者广泛用于解决实际应用问题,其应用范围涉及了人工智能、计算机科学、统计规划等多个领域。但由于粒子群算法在运行过程中很容易陷入局部最优,所以现在很多国内外研究者在研究粒子群算法的优化问题。本文针对粒子群算法存在的缺点,将改进的遗传算法嵌入其中,并与膜系统相结合,提出了新的运行算法。车间调度是一个解决组合优化问题的过程,在企业面临各种约束限制下,对车间生产的各道工序进行合理的规划和分配,寻找到一个具有更少生产时间或者更低成本消耗的生产流程,从而达到提高生产效率的目的。车间调度是一个公认的NP-Hard难题,因为涉及到的变量和限制条件较多,使其求解变得比较复杂。本文将提出的新算法应用于不同规模的作业车间调度问题上,结果证明该算法可以有效地解决JSSP。本文的主要创新点如下:(1)设计了复合型链式组织P系统(CTP)。首先提出了正反向单链形式的组织结构,所有细胞单向连接成一条链,链上的细胞之间可以单一正向和单一反向交流。其次将细胞型P系统和组织型P系统的性质和功能相结合,使得组织中的每个细胞都具有活性膜的性质,即衍生性和溶解性。最后将提出的新组织结构用于结合后的系统中,设计了CTP系统,在新系统中,细胞的活动更加灵活,信息的交流更加方便。(2)将克隆选择策略运用到遗传算法的选择操作中,结合精英选择策略,保留匹配度最佳个体,按一定比例将匹配度低的抗体用匹配度高的克隆替换,再进行轮盘赌选择,选出可行解集合。用此法可以选出质量比较高的可行解,使算法的收敛速度被缩短。同时,在交叉操作中,设定一个阈值,使其与重合度相比较,根据比较结果决定是否进行交叉操作。该阈值约束提高了解的多样性,降低了算法陷入局部最优的概率。(3)在PSO算法中,首先基于收缩因子改进惯性权重,再与改进的遗传算法相结合,使粒子的全局及局部搜索能力得到了平衡,提升了精确度。同时将提出的复合型链式组织P系统与改进后的PSO算法结合,利用P系统的极大并行性和分布式特点,大大提高了算法的运行速度。
【学位单位】：山东师范大学
【学位级别】：硕士
【学位年份】：2020
【中图分类】：F273;F224
【部分图文】：

山东师范大学硕士学位论文13第二章复合型链式组织P系统（CTP）本章提出了一种新型的P系统，该系统是以组织P系统为基础系统，结合细胞型P系统活性膜性质和链式P系统链式结构，设计了一种复合型链式组织P系统(CTP)，分别从系统的结构、规则和计算能力三方面进行详细阐述。2.1CTP系统构建2.1.1正反向单链结构链式P系统是组织P系统的一种扩展模型，所有的细胞以单向或双向连接方式形成一条链，本章参考链式P系统的链式结构，设计了一个正反向单链的组织结构，该链式结构同时存在单一正向连接和单一反向连接，其结构图例如图2-1：图2-1正反向单链结构上图是一个由四个细胞构成的正反向链式结构，其中正向链式结构体现为四个细胞之间的信息交流是由前到后的顺序单向进行的，反向链式结构则体现为最后一个细胞与前面三个细胞的信息交流从后往前的，与细胞的连接方向相反。假设细胞1是系统的起始细胞，细胞4为系统的终止细胞，则细胞1产生的对象只能运用交流规则通过连接渠道传递给细胞2，细胞2接收对象后运用规则完成对象进化，生成的新对象只能正向传递给细胞3。同理，细胞3想要传递的所有对象只能给细胞4，但细胞4内的对象，可以通过与其他三个细胞的连接渠道传送到任意一个细胞，当进化结束时，细胞4会将对象直接输出到环境中。前三个细胞的信息传递方向与细胞的连接方向相同，将其称为正向单链，由于细胞4是链上的最后一个细胞，所以它的信息交流方向与细胞连接的方向是相反的，称为反向单链。2.1.2CTP系统设计上一小节介绍了设计的正反向单链结构，本节将完整地、详细地阐述复合型链式组织

山东师范大学硕士学位论文14P系统。细胞型P系统是以单个细胞为单位完成计算的，细胞膜具有衍生性，可以直接在膜内生成新膜，也可以直接在膜内溶解，而组织型P系统则是由多个细胞按照一定的结构组成的，组织内的细胞一般不具有活性膜的性质。本文将细胞型P系统活性膜性质运用在组织P系统中，构成一种复合型组织P系统，通过运行衍生规则和溶解规则，可以实现系统中单个细胞的衍生和溶解，更大限度地发挥P系统的极大并行性。将正反向链式结构用于复合型组织P系统，可以简化系统的拓扑结构，增强系统的简洁性，使计算过程更加简单明了。CTP系统的拓扑结构如图2-2：图2-2CTP结构图上图是一个含有n个膜的复合型链式组织P系统，h是整个系统存在的环境，膜c1为系统初始膜（第一个细胞），用于输入数据和初始化参数，膜cn为系统的输出膜（最后一个细胞），其余的膜均为进化膜。所有膜按照正反向链式结构进行连接，每个膜可以根据运行要求执行膜的衍生规则和溶解规则，生成新膜（用虚线圆形表示）或者将膜溶解。外层膜ci内生成的各个新膜之间通过膜ci内的环境进行信息交流，而外层膜ci之间则通过连接渠道直接进行信息交换。根据P系统的形式化定义，将一个含有m个细胞的CTP系统定义为：()120=,,,,,,,,,,miORsynQi+其中：（1）O是对象的非空有限集，是一个字母表；（2）12,,,m是系统中含有的m个细胞，1,2,,m为细胞个数的标签；（3）,+表示了系统的正反向链式结构，+表示了正向链式结构，表示了反向链式结构；

山东师范大学硕士学位论文24（6）对上一步形成的新种群，对抗体的字符串随机选取一个位点采取取反操作，实现基因的突变，形成新的抗体种群。（7）满足终止条件，输出结果，否则，返回第三步，进行新一轮的迭代，直到迭代终止。（8）结束运算。基于克隆选择的遗传算法的流程图如图3-1：图3-1CSGA算法流程图
【参考文献】

相关期刊论文 前5条

1 葛安华;周晏明;李权章;;改进遗传算法求解作业车间提前/拖期调度问题[J];森林工程;2013年03期

2 王军强;陈剑;翟颖妮;张松飞;杨建斌;孙树栋;;扰动情形下瓶颈利用对作业车间调度的影响[J];计算机集成制造系统;2010年12期

3 马鑫;李琴;;克隆选择算法的研究与实现[J];改革与开放;2010年12期

4 吴澄;现代集成制造系统的理论基础——一类复杂性问题及其求解[J];计算机集成制造系统-CIMS;2001年03期

5 何霆,刘飞,马玉林,杨海;车间生产调度问题研究[J];机械工程学报;2000年05期

相关博士学位论文 前3条

1 王鹏飞;群智能优化算法及在流水车间调度问题中的应用研究[D];吉林大学;2019年

2 周瑞红;基于群智能优化理论的聚类改进方法及应用研究[D];吉林大学;2017年

3 薛洁;两类生物计算问题及其在数据挖掘中的应用研究[D];山东师范大学;2015年

相关硕士学位论文 前7条

1 陈毅;L公司柔性车间调度与预防性维护集成优化[D];贵州大学;2019年

2 张超;粒子群算法与蚁群算法的改进研究[D];西安工程大学;2019年

3 马庆吉;基于改进灰狼算法的柔性作业车间调度方法研究[D];华中科技大学;2019年

4 张晓寒;基于混合粒子群算法的车间调度研究及管理系统设计[D];武汉科技大学;2019年

5 任彩乐;基于候鸟优化算法的混合流水车间调度问题研究[D];华中科技大学;2019年

6 任硕;基于膜计算的输电线路路径优化问题的研究与应用[D];山东师范大学;2015年

7 孙杰;细胞型膜系统在聚类算法中的研究[D];山东师范大学;2014年

本文编号：2865872