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