﻿ 基于遗传蚁群算法的矩形件排样问题研究 Research on Rectangular Packing Optimization Based on Genetic Ant Colony Algorithm

Dynamical Systems and Control
Vol.06 No.03(2017), Article ID:21336,5 pages
10.12677/DSC.2017.63017

Research on Rectangular Packing Optimization Based on Genetic Ant Colony Algorithm

Jie Liu, Nanbo Liu

Henan University of Technology, Zhengzhou Henan

Received: Jun. 18th, 2017; accepted: Jul. 9th, 2017; published: Jul. 12th, 2017

ABSTRACT

In recent years, enterprises have been seeking ways to improve their efficiency .In this paper, a genetic ant colony algorithm is proposed to solve the sample problem of rectangular parts. The results show that compared with single genetic algorithm and ant colony algorithm, this method can wait for better layout effect and greatly improve the economic efficiency and competitiveness of enterprises.

Keywords:Rectangular, Genetic Ant Colony Algorithm

1. 引言

2. 二维排样(板材、玻璃等下料)问题简述

(2-1)

(2-2)

(2-3)

3. 遗传蚁群算法

3.1. 遗传算法设计如下

3.2. 蚁群算法

Dorigo提出了蚁群算法(ACO)。蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得到的一种放生算法。蚂蚁在运动过程中，能够在它经过的路径留下一种称之为外激素的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此直到自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现为一种正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率最大。基本的ACO模型可以通过以下公式进行描述：

(3-1)

(3-2)

(第k个蚂蚁经过由i到j的路径) (3-3)

3.2.1. 适应度函数

3.2.2. 信息素的初始化

3.2.3. 信息素的更新

(3-4)

-初始参数()： -信息素浓度的初始值，也对赋的初始值。

(3-5)

(3-6)

—为矩形件i上的信息素浓度；—信息素挥发系数—信息素强度常数；—待排矩形件总数；—第i个矩形件在最优排样中的次序；—待排样矩形件的总面积；—全局最优排样序列所对应的排样图的板材面积。

3.3. 基于遗传蚁群算法的矩形排样实现流程如下：

4. 实验结果

Table 1. The parameters of the rectangulars

Figure 1. The flowchart of genetic and ant colony algorithm

5. 结论

Research on Rectangular Packing Optimization Based on Genetic Ant Colony Algorithm[J]. 动力系统与控制, 2017, 06(03): 136-140. http://dx.doi.org/10.12677/DSC.2017.63017

1. 1. Lodi, A., Martello, S., Monaci, M., et al. (2002) Two Dimensional Packing Problems: A Survey. European Journal of Operational Research, 141, 241-252. https://doi.org/10.1016/S0377-2217(02)00123-6

2. 2. Turtonbch, H. (2001) An Empirical Investigation of Meta-Heurstic and Heurstic Algorithms for a 2D Packing Problem. European Journal of Operational Research, 128, 34-57. https://doi.org/10.1016/S0377-2217(99)00357-4

3. 3. 陈洁琼, 樊留群, 杨剑. 遗传算法在风管制造排样中的应用[J]. 制造业自动化, 2017(5): 113-116.

4. 4. 杨卫波, 王万良, 张景玲, 赵燕伟. 基于遗传模拟退火算法的矩形件优化排样[J]. 计算机工程与应用, 2016, 52(7): 259-263.

5. 5. 马康, 高尚. 分布估计算法求解矩形件排样优化问题[J]. 电子设计工程, 2017, 25(1): 49-54.