教学算法及其在几类复杂组合优化问题上的应用研究

发布时间：2020-07-14 01:24

【摘要】：组合优化问题是最优化问题中的一类在离散状态下求极值的问题,实际生活中的许多问题都可以抽象为组合优化问题。典型的组合优化问题有作业车间调度问题、旅行商问题等,由于组合优化问题为NP-hard问题,随着问题规模的增大,采用精确求解的方法所需的计算量和存储空间呈指数增长,难于在有限时间内找到最优解,因此进化算法等近似算法成为组合优化问题求解的热点,很多研究人员利用进化算法在可以接受的时间内寻求这类问题的近似最优解。其中教学算法是一种新兴的群智能进化算法,模拟了课堂中教师对学生授课的影响以及学生之间相互学习的过程。教学算法具有模型简单、计算效率较高等优点。本文对教学算法及其在来自于实际工程的几类组合优化问题上的应用进行研究,针对每一类组合优化问题的特性设计相应的改进教学算法对问题进行求解。本文主要完成如下工作:(1)对经典离散优化问题车间作业调度问题(JSSP)进行研究,针对JSSP问题因其复杂度较高容易导致算法陷入局部最优的不足,提出了一种新颖的多小组协同学习的教学算法(GC-TLBO)。引入了学习小组协同学习策略,通过组内学习和组内交流,使学习过程跳出当前的局限;引入了基于学习能力的深度和广度搜索策略,小组内学生按照学习能力强弱进行学习,较优的学生进行深度的学习,较差的学生进行广度的学习。最后,通过对OR-Library中的标准仿真实例进行实验,结果表明所提出的改进教学算法在JSSP问题上的收敛精度和搜索能力均得到了有效的提高。(2)对一类具有聚类特性的旅行商问题(TSP)进行研究,针对这类TSP问题的聚类特性,在GC-TLBO的初始化阶段结合启发式信息对算法进行初始化。利用该方法对实际应用系统——智能仓储系统中的订单排序优化问题进行研究与分析,将其归纳为一类带约束和聚类性质的TSP问题。最后利用设计的改进教学算法对订单排序优化问题进行仿真实验,验证了结合启发式初始化的GC-TLBO算法求解这一类问题的有效性。(3)对一类多人旅行商问题(MTSP)进行研究,针对MTSP问题涉及到多个任务的分派和优化特性,对GC-TLBO算法进行改进,提出基于批次交叉算子的教学算法(NC-TLBO),在教师阶段和学生阶段采用一种新的基于批次的交叉算子,并在学生自学习阶段采用新的基于批次的自学习算子。针对实际应用系统——智能仓储系统中的四叉机器人拿货顺序问题进行研究与分析,将其归纳为一类带约束的MTSP问题。利用该改进教学算法对四叉机器人的拿货顺序优化问题进行仿真实验,验证了所提出的NC-TLBO算法求解这一类问题的有效性。(4)对一类带有可重入性质的柔性车间调度问题(FJSP)进行研究,由于这类问题带有可重入性与柔性,具有高度复杂度,因此对GC-TLBO算法作出改进,提出一种变步长策略和基于关键路径的邻域搜索相结合的教学算法(CP-TLBO),设计了一种顺序编码方式和工序序号编码方式相结合的编码方式,并在学生阶段设计了一种变步长的局部搜索和基于关键路径的全局搜索相结合的搜索策略。针对符合这一特点的实际问题——免疫检测设备的调度问题进行分析,将其归纳为具有复杂约束和可重入特性的FJSP问题。利用该算法对其进行设备优化调度的仿真实验,验证了CP-TLBO算法求解这一类问题的有效性。
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O224
【图文】：

基本流程,算法,学习过程,学生个体

华南理工大学硕士学位论文生阶段除了会向老师学习以外，还会相互学习相互交流获得新知识，取长补短响共同进步。在学生阶段，学生个体 Xi向 Xj的学习过程按下式进行[38]。(),()()new,i old,iiijijX X rX X当FX FX(),()()new,i old,iijiijX X rX X当FX FX，F(Xi)表示个体 Xi的适应值，ir 为[0,1]间的随机数。当 F(Xnew,i) <F(Xold的学习过程，保留个体 Xnew,i，否则保留 Xold,i。本 TLBO 算法的流程算法的基本流程如图 2-1 所示。

算法流程图,工件

符号 cik和 pik分别为 i 工件在机器 k 上的完成时间和加工时间；M 是一个足够大的正数； aihk和 xijk分别为指示系数和指示变量，其意义如下：非上述情况若机器先于机器加工工件01 hkiaihk（3-5）非上述情况若工件先于工件在机器上加工01 ijkxijk（3-6）式（3-1）表示目标函数，即最大完工时间；式（3-2）表示链式约束条件；式（3-3）为加工工件过程不可中断约束；式（3-4）表示工件在每个机器上都要加工。3.3 基于小组的协同学习教学算法3.3.1 改进的 TLBO 算法基于多小组协同学习的改进教学算法的基本流程图如图 3-1 所示。

自学习,算子,学习能力,学生

适应值（完工时间）由小到大进行排名，将排名在前半部分的学生定义为学习能力较强的学生，将排名在后半部分的学生定义为学习能力较差的学生。对于学习能力较强的学生，进行加强局部搜索能力的深度学习操作，而对于学习能力较弱的学生，则进行加强随机搜索能力的广度学习操作。a）学生深度学习对于学习能力较好的学生，其更善于进行知识的深度挖掘。因此对学习能力较强的个体 Xi，进行 Num(i)次自学习算子操作，根据文献[36]中给予学习能力强的个体更多的学习机会和次数的思想，Num(i)按照公式（3-7）进行计算获得，自学习算子利用文献[67]所提到的三种经典变异算子：单点交叉算子、倒位算子与移位算子，如图 3-2 所示。每次自学习随机选择三种自学习算子中的一种，若本次学习得到的新个体比当前个体 Xi更优，则对当前个体 Xi进行更新，否则本次的学习成果不被接受，个体 Xi不更新，以此类推，个体共完成 Num(i)次学习，学生的深度学习过程如图 3-3 所示。与文献[36]中以当前个体为起点一次性产生多个邻域个体然后取最好个体的差异性自学习不同，本章

【参考文献】