改进的并行遗传算法在知识库中的应用研究

摘要

生产调度问题属于组合优化问题。将优化方法的理论研究引入到车间生产调度领域中，改进算法性能、拓宽算法应用领域、完善算法体系，是一个同时具有理论意义和应用价值的课题，具有重要的意义。 本文在传统的粗粒度并行遗传算法的基础上，提出了一种改进的并行遗传算法。新算法主要在两个方面对传统的粗粒度并行遗传算法做出了改进：改进后的算法采用了一种根据各个岛屿平均适应度的大小动态的调整该岛屿的迁移率，使得当某个岛屿的平均适应度较高时通过调高其它岛屿到该岛屿的迁移率来增加它的多样性，从而避免了该岛屿发生早熟现象；改进后的算法对参加迁移的染色体引入了存活期的思想，不但确保了适应度较高的染色体拥有较长的存活期，而且避免了某个岛屿的种群规模过度膨胀。这些改进措施对避免算法出现早熟、提高算法的收敛速度和全局搜索能力有重要意义。应用标准测试集中的测试用例和实际调度中的问题对改进后的算法进行了测试，仿真程序表明，该算法能以较快速度完成给定范围的搜索和全局优化任务。同时，针对制造企业的实际情况，设计了一种新的适用于实际车间调度问题的种群初始化方法，相较与传统并行遗传算法只是随机划分初始种群的缺点，提出的划分方法使种群具有了更高的多样性。针对某工厂的实际问题，运用上述技术，设计并实现了一个车间调度知识库系统平台，并将改进后的算法嵌入至知识库系统平台中，运用改进后的算法，针对实际问题进行求解，得到的结果是可行的和有效的。

目录

文摘

英文文摘

声明

绪 论

第一章调度问题与知识库研究

1.1调度理论的研究与发展

1.2调度问题的描述

1.2.1单双机调度问题

1.2.2调度问题的分类

1.3车间调度问题的研究现状

1.4遗传算法在车间调度问题中的应用现状

1.5知识库系统

1.5.1知识库的概念

1.5.2知识库系统的研究现状

1.5.3知识库系统的功能

本章小结

第二章并行遗传算法的研究

2.1并行遗传算法概述

2.2粗粒度并行遗传算法

2.3主从式并行遗传算法

2.4混合模型的并行遗传算法

2.4.1粗粒度-主从式并行遗传算法

2.4.2粗粒度-粗粒度并行遗传算法

2.4.3粗粒度-细粒度并行遗传算法

2.5并行遗传算法的研究现状

2.6并行遗传算法的优缺点

本章小结

第三章改进的并行遗传算法

3.1引言

3.2改进算法的关键思想与技术

3.2.1设计改进算法的主要原因

3.2.2改进算法的理论基础

3.2.3改进算法的主要思想

3.2.4迁移率的动态调整方法

3.2.5生命周期的计算

3.2.6种群初始化

3.3改进算法的流程

3.3.1编码和解码

3.3.2适应度计算

3.3.3初始种群的建立

3.3.4算法相关参数

3.3.5改进的两点交叉策略

3.3.6选择操作

3.3.7改进的精英选择策略

3.3.8变异操作

3.3.9算法步骤

3.4改进算法性能验证

3.4.1 MT10标准问题

3.4.2实际生产问题

本章小结

第四章车间调度知识库系统的设计与应用

4.1引言

4.2系统总体设计思想

4.2.1知识库系统初步设计

4.2.2知识库系统的详细设计

4.2.3编程实现

4.2.4接口设计

4.3系统功能模块设计

4.3.1基础信息管理模块

4.3.2专家知识管理模块

4.3.3推理机管理模块

4.3.4算法运行模块

4.4系统平台实例运行

4.4.1算法管理平台

4.4.2算法分析平台

4.4.3算法运行平台

4.5数据库表清单

本章小结

结 论

参考文献

攻读硕士学位期间发表的学术论文

致谢