基于单亲遗传算法的设备布局问题研究

《基于单亲遗传算法的设备布局问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一章绪论(以一个较差方案的接受概率下降)以及迭代次数。近期，Balakrishnan等(2003)[251提出了一种混合遗传算法对DMLP进行优化计算。AlanR和JinShang(2006)[261提出了一种混合蚁群算法，国内目前暂时还没有找到关于动态设备布局方面的研究成果。1．3本文的研究思路本文在阅读大量国内外设备布局问题文献的基础上，并且对智能方法遗传算法和单亲遗传算法的原理进行了充分的学习和研究，分别探讨了等面积设备单行及多行布局优化问题。采用单亲遗传算法的思想，分别构造了对静态设备布局及动态设备布局

2、的启发式算法。首先是将单亲遗传算法的思想用于静态设备布局设计，利用了其适用于序号编码问题的特点，通过仿真试验与传统遗传算法进行比较研究；其次在总结和分析国外关于动态设备布局算法的很多研究成果基础上，对它们的特点进行比较，并以此为基础提出了一种改进的单亲遗传算法，并通过大量仿真试验，来说明提出算法的性能。分别根据对算法运算时间和取得优化解的质量的衡量，给出两个用于算法性能比较的指标，与其它已有研究成果的性能进行分析比较，得出所提出方法的适用性。具体的研究思路总结如下。1．3．1研究对象本文研究对象包括静态设备布局问

3、题(SMLP)和动态设备布局问题(DMLP)。根据布局是否随时问调整，设备布局分为静态布局和动态布局。静态布局又称为传统布局，对此已有较多研究。企业为了对多变的环境做出响应，就要在产品功能、数量、所需技术以及品种等改变的基础上重新布局或者调整系统结构。当设备之间的物流随时间而变化，布局也做出相应的调整时，SMLP就转化为DMLP。DMLP是在对未来可能发生的物流变化做出预测的基础上所设计的布局。将未来时间划分为一系列时间段(如年、月、周等)，预测每个时间段的物流数据并假定在此时问段内为常量。一系列的静态布局经扩展

4、即得到动态布局，动态布局的每个时间期内的布局可作为静态布局单独处理。1．3．2采用方法及研究思路本文研究方法采用单亲遗传算法以及一种针对动态设备布局的改进遗传算法。首先构造了单亲遗传算法来解决多行设备静态稚局，并与传统遗传算法作对4第一章绪论比，由此也观察了单亲遗传算法对设备布局问题的优化性能；然后进一步探索将单亲遗传算法原理应用于动态设备布局问题的可能性和可行性。13．3研究方法与已有方法的比较对于静态设备布局，遗传算法曾被多次使用，但之前没有出现单亲遗传算法的应用。本文研究了设备布局问题的特征，其遗传算法编码

5、形式采用序列编码，因为传统遗传算法的遗传算子必须要考虑子代个体的可行性，使得操作复杂，计算量增大；而单亲遗传算法适用于序列编码，并且遗传操作较传统遗传算法更简单和高效。对于动态设备布局，先前的启发式方法包括遗传算法和其他算法，一是需要考虑进化或迭代过程中个体的可行性问题；二是算法构造比较复杂，计算时间复杂度较高，往往不能在合理的时间内得到较好的优化解。本文采用的单亲遗传算法，首先从初始化合法个体开始，遗传操作不会得到不可行个体，省去了可行性检验：其次算法构造简单，也比较容易实现，基本可以在合理的时间内得到较好的优

6、化解。1．4本文的主要工作具体研究内容如下：(1)第一章中，对本文研究的工作背景进行了阐述；同时简单介绍了目前关于设备布局设计问题的研究现状；最后给出了本文的主要T作。(2)基于阅读的大量文献，在第■章中我们较详尽的给出了本文工作中进行研究探讨的理论基础，包括：单亲遗传算法原理及其遗传操作算子的特点：设备布局相关概念；设备布局问题的模型分类及各种模型的介绍；曾用于设备布局问题的各种算法及它们的特点。(3)第三章中，基于单亲遗传算法的特性，构造了一种针对多行设备静态布局的算法。由于单亲遗传算子操作简单、效率较高，即

7、使初始种群多样性很差也不易落入局部最优，性能优于传统遗传算法的各种交叉算子。所建模型考虑了多行设备布局的一般情况，并且构造不同规模的实例进行模拟计算(对于大规模问题采用单点、多点基因换位的混合策略)，进一步和传统遗传算法进行了比较。试验结果表明，本文提出的算法对大规模多行布局问题具有较强的全局寻优效果和较好的寻优效率。(4)基于PGA在第三章静态设备布局问题的运用经验，以及单亲遗传算法解决设备布局问题较好的效率，第四章中，在总结和分析国外关于动态设备布局算法第一章绪论的很多研究成果基础上，对它们的特点进行比较，进

8、一步运用单亲遗传算法的思想来解决动态设备布局问题。由于动态设备布局问题编码时需要把各个时期的布局染色体串联，我们提出了在单期布局子串上进行单亲遗传操作的策略，保证了遗传操作后染色体的可行性。在模拟试验中，对文献中出现的多个数据样本进行了仿真计算，同时对结果进行了分析，并提出两个指标对算法在时间和优化解质量方面的综合性能进行比较。(5)作为研究拓展，第五章简要介绍了不等面积