基于遗传算法与蚂蚁算法的矩形件布局问题的研究与应用

摘要

布局问题来源于生产实际，广泛存在于汽车制造、造船、制衣、玻璃加工、家具制造等行业。在当今各种能源材料短缺的情况下，提高板材利用率以节约原材料，降低成本，提高经济效益，对各行业均有重要意义。 布局问题涉及计算几何、计算机图形学、运筹学、逻辑推理等多学科知识，属于具有最高计算复杂性的优化计算问题，即NP完全问题。理论上至今仍没有突破。由于生产实际的需要，人们又迫切需要利用现代科技得到一些能满足生产规模较大的排料需要的求解方法。这些方法能够以较快的速度给出一个较好的解，虽然不是最优解，但接近最优解，并且比人工排样效率高，能达到或超过人们所期望的材料利用率。 怎样选择若干个合适的矩形件进行优化组合，合理确定它们的相对位置和方向，会在很大程度上影响到布局的最终效果，同时这也是矩形件优化组合的难点所在。许多学者提出了很多的方法：遗传算法、启发式算法、模拟退火算法等优化算法。本文在求解布局问题时，首先，取蚂蚁算法和遗传算法的各自长处，采用一套混合的遗传蚂蚁算法；并对相应算法的改进，使新生成的混合算法搜索速度加快、优化程度提高，基本思想是：算法前过程采用遗传算法，充分利用遗传算法的快速性、随机性、全局收敛性，生成布局问题初始解，并将其转化为蚁群算法的初始信息素分布；然后利用蚁群算法正反馈、高效收敛、的优势寻求最优解。然后，针对遗传算法和蚁群算法在矩形件布局问题中的实际特点，并分析了矩形件布局给定排放顺序的排放算法，并提出了一种新的排放算法——最低水平线旋转搜索法，并将这种算法和遗传算法以及遗传蚁群算法结合应用于矩形件布局问题的求解。计算实例表明这种新的排放算法可以和遗传蚁群算法有效的结合。 进一步的研究工作是：如何更好的将遗传算法和蚂蚁算法的融合并应用于矩形件布局问题，以及在求解布局优化问题时，如何更好的控制蚁群算法的各项参数。

目录

文摘

英文文摘

声明

第1章 前言

1.1布局问题概述

1.2布局问题现状

1.3本文的主要工作

1.3.1研究内容

1.3.2重点解决的问题

第2章 矩形件布局问题研究

2.1优化算法的分类

2.2矩形件布局给定排放顺序的排放算法

2.3一种新的矩形件布局排放算法——最低水平线旋转搜索法

第3章 基于遗传算法的矩形件布局问题研究

3.1遗传算法概述

3.2基本遗传算法的实现技术

3.2.1编码

3.2.2适应度函数

3.2.3遗传操作

3.2.4终止条件

3.3基本遗传算法的特点

3.4矩形件优化布局的遗传算法设计

3.4.1基因编码

3.4.2初始种群的产生

3.4.3适应度函数

3.4.4染色体的选择

3.4.5染色体的交叉

3.4.6染色体的变异

3.5实验结果

第4章 基于遗传算法和蚂蚁算法的矩形件布局问题研究

4.1蚁群算法概述

4.2基本蚁群算法原理

4.3基本蚁群算法模型

4.4基本蚁群算法的特点

4.5几种改进的蚁群算法模型

4.5.1蚁群系统

4.5.2最大—最小蚁群系统

4.5.3自适应蚁群算法

4.6遗传算法与蚂蚁算法的融合

4.7矩形件优化排样的遗传蚁群算法设计

4.7.1矩形件优化排样中的遗传算法规则

4.7.2矩形件优化排样中的蚁群算法规则

4.7.3遗传算法与蚂蚁算法的衔接

4.7.4基于遗传蚁群算法的矩形件布局实现流程

4.7.5实验结果

结束语

致谢

参考文献