目 录
第1章 引言 1
第2章 遗传算法概述 3
2.1遗传算法简介 3
2.1.1遗传算法的生物遗传学基础 3
2.1.2 遗传算法的产生与发展 4
2.1.3 遗传算法的基本思想 5
2.1.4遗传算法的特点 5
2.2遗传算法的基本实施步骤 6
2.2.1遗传算法的组成 6
2.2.2 遗传算法的基本流程 6
2.3遗传算法的应用 7
第3章 用GA解决ALB问题 9
3.1初始种群的生成 9
3.2适应函数的构造 9
3.3选择策略的确定 11
3.4交叉算子 12
3.5变异算子 13
3.6交换变异概率的确定 14
第4章 可视化实现 17
4.1开发工具的选择 17
4.2数据结构 17
4.2.1任务关联矩阵 17
4.2.2任务深度数组和任务编号序列数组 18
4.2.3任务执行时间数组 18
4.2.4个体理论的任务执行顺序数组 19
4.3实现基于遗传算法的ALB问题的流程图 19
4.4实现的难点及解决的方法 20
4.4.1任务的深度计算 21
4.4.2违例次数的计算 22
4.4.3遗传算法的未成熟收敛 23
第 5 章 系统运行实例 25
5.1系统的功能结构 25
5.2系统各功能模块简介 25
5.3系统过程演示 28
结 论 31
参考文献 32
致 谢 34
第1章 引言
装配线有多个工位，各工位并行作业，工件串行地依次进入各工位。产品的装配操作可以划分为若干个具有独立工时的单元作业，任一工位的操作都是部分单元作业的组合，其工时等于这些单元作业的工时和。通常希望各工位工时尽可能相等，避免由于工时相差太大而造成某些工位作业堆积，而另外一些工位又有工时流失的现象，以提高整条装配线的效率。单元作业是一个偏序集，即部分单元作业之间存在时间的先后顺序关系；同时各工位的作业时间又受到一定节拍时间（Cycle Time，简称CT）的限制。其顺序约束可以用作业的先后顺序图来表示，其中节点表示作业，连接节点的弧表示作业顺序，如图1.1所示。如何在满足节拍和单元作业之间先后顺序关系的前提下，组合并分配单元作业，以使各工位工时尽可能相等，这就是装配线平衡问题（Assembly Line Balancing Problem,简称ALB问题）。ALB的目的就是尽量减少装配线的闲置时间，提高工人和设备的利用率。它是装配线规划过程中必须首先要解决的基本问题之一。
