基于改进遗传算法的混合车间调度问题研究1(20)

基于改进遗传算法的混合车间调度问题研究

对象的科学新范式得到学术界普遍认同。由于遗传算法能有效求解属于

ＮＰ＿ｈａｒｄ类型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的广泛重视。一些学者也认识到求解复杂问题最优解是不现实的，故寻求满意解，而遗传算法是最佳工具之一。

２．３遗传算法的理论基础

２．３．１遗传算法的生物学背景

遗传算法借鉴了生物界中进化与遗传的机理，用于解决复杂的工程技术问题。首先介绍一下生物学中进化和遗传的概念。

（１）生物的进化

地球上的生物，都是经过长期的进化而形成的。根据达尔文的自然选择学说，地球上的生物具有很强的繁殖能力。在繁殖的过程中，大多数生物通过遗传，事物中保持相似的后代，部分生物由于变异，后代具有明显差别，甚至形成新物种。正是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资源却是有限的，因此，为了生存，生物就需要竞争。生物在生存竞争中，根据对环境的适应能力，适者生存，不适者消亡，自然界中的生物，就是根据这种优劣的原则，不断的进行进化。遗传算法就是借用生物进化的规律，通过繁殖一竞争一再繁殖一再竞争，实现优胜劣汰，一步一步的逼近问题的最优解。

（２）遗传物质

众所周知，细胞是生物结构和功能的基本单位，细胞通常由细胞膜，细胞质与细胞核三部分组成。细胞核位于细胞的最内层，由核膜，染色质，核液三者组成，是遗传物质储存和复制的场所。细胞核中的染色质，在细胞分裂时形成光学显微镜可以看到的染色体。染色体主要由蛋白质和ＤＮＡ组成。ＤＮＡ又称脱氧核糖核酸，是一种高分子化合物，组成它的基本单位是脱氧核普酸。ＤＮＡ可以传递遗传信息。它是生物上下代之间传递遗传信息的物质。绝大多数生物的遗传物质是ＤＮＡ。由于细胞里的ＤＮＡ大部分在染色体上，因此，遗传物质的主要载体是染色体。控制生物遗传的物质单元称作基因，它是有遗传效应的ＤＮＡ片段。每个基因含有成百上千个脱氧核昔酸。它们在染色体上呈现线性排列，这种排列顺序就代表遗传信息。在遗传算法中，为了形成具有遗传物质的染色体，就用不同字符组成的字符串表达所研究的问题。这种字符串相当于染色体，其上的字符就相当于基因。

（３）遗传方式

生物的主要遗传方式是复制。在遗传过程中，父代的遗传物质ＤＮＡ分子被复制到子代，以此传递遗传信息。生物在遗传过程中还会发生变异。变异的方