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

《教学算法及其在几类复杂组合优化问题上的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文教学算法及其在几类复杂组合优化问题上的应用研究作者姓名杨晟轩学科专业控制理论与控制工程指导教师张梅所在学院自动化科学与工程学院论文提交日期2018年4月ResearchonTeaching-learning-basedAlgorithmandApplicationforSeveralKindsofComplexCombinatorialOptimizationProblemsADissertationSubmittedfortheDegreeofMasterCandidate：YangShengxuanS

2、upervisor：ZhangMeiSouthChinaUniversityofTechnologyGuangzhou，China分类号：TP3学校代号：10561学号：201520112789华南理工大学硕士学位论文作者姓名：杨晟轩指导教师姓名、职称：张梅副教授申请学位级别：工学硕士学科专业名称：控制理论与控制工程研究方向：智能进化算法论文提交日期：2018年4月12日论文答辩日期：2018年6月4日学位授予单位：华南理工大学学位授予日期：年月日答辩委员会成员：主席：游林儒委员：陈安、高红霞、陈立定、吴忻生摘要组合

3、优化问题是最优化问题中的一类在离散状态下求极值的问题，实际生活中的许多问题都可以抽象为组合优化问题。典型的组合优化问题有作业车间调度问题、旅行商问题等，由于组合优化问题为NP-hard问题，随着问题规模的增大，采用精确求解的方法所需的计算量和存储空间呈指数增长，难于在有限时间内找到最优解，因此进化算法等近似算法成为组合优化问题求解的热点，很多研究人员利用进化算法在可以接受的时间内寻求这类问题的近似最优解。其中教学算法是一种新兴的群智能进化算法，模拟了课堂中教师对学生授课的影响以及学生之间相互学习的过程。教学算法具有模

4、型简单、计算效率较高等优点。本文对教学算法及其在来自于实际工程的几类组合优化问题上的应用进行研究，针对每一类组合优化问题的特性设计相应的改进教学算法对问题进行求解。本文主要完成如下工作：（1）对经典离散优化问题车间作业调度问题（JSSP）进行研究，针对JSSP问题因其复杂度较高容易导致算法陷入局部最优的不足，提出了一种新颖的多小组协同学习的教学算法（GC-TLBO）。引入了学习小组协同学习策略，通过组内学习和组内交流，使学习过程跳出当前的局限；引入了基于学习能力的深度和广度搜索策略，小组内学生按照学习能力强弱进行学习

5、，较优的学生进行深度的学习，较差的学生进行广度的学习。最后，通过对OR-Library中的标准仿真实例进行实验，结果表明所提出的改进教学算法在JSSP问题上的收敛精度和搜索能力均得到了有效的提高。（2）对一类具有聚类特性的旅行商问题（TSP）进行研究，针对这类TSP问题的聚类特性，在GC-TLBO的初始化阶段结合启发式信息对算法进行初始化。利用该方法对实际应用系统——智能仓储系统中的订单排序优化问题进行研究与分析，将其归纳为一类带约束和聚类性质的TSP问题。最后利用设计的改进教学算法对订单排序优化问题进行仿真实验，验

6、证了结合启发式初始化的GC-TLBO算法求解这一类问题的有效性。（3）对一类多人旅行商问题（MTSP）进行研究，针对MTSP问题涉及到多个任务的分派和优化特性，对GC-TLBO算法进行改进，提出基于批次交叉算子的教学算法（NC-TLBO），在教师阶段和学生阶段采用一种新的基于批次的交叉算子，并在学生自学习阶段采用新的基于批次的自学习算子。针对实际应用系统——智能仓储系统中的四叉机器人拿货顺序问题进行研究与分析，将其归纳为一类带约束的MTSP问题。利用该改进教学算法对四叉机器人的拿货顺序优化问题进行仿真实验，验证了所提

7、出的INC-TLBO算法求解这一类问题的有效性。（4）对一类带有可重入性质的柔性车间调度问题（FJSP）进行研究，由于这类问题带有可重入性与柔性，具有高度复杂度，因此对GC-TLBO算法作出改进，提出一种变步长策略和基于关键路径的邻域搜索相结合的教学算法（CP-TLBO），设计了一种顺序编码方式和工序序号编码方式相结合的编码方式，并在学生阶段设计了一种变步长的局部搜索和基于关键路径的全局搜索相结合的搜索策略。针对符合这一特点的实际问题——免疫检测设备的调度问题进行分析，将其归纳为具有复杂约束和可重入特性的FJSP问题

8、。利用该算法对其进行设备优化调度的仿真实验，验证了CP-TLBO算法求解这一类问题的有效性。关键词：教学算法；协同进化算法；智能仓储系统；免疫检测设备；IIABSTRACTCombinatorialoptimizationisaclassofoptimizationproblems.Manyoptimizationproblemsinreall