APP下载

一种基于评价函数的三维矩形布局遗传算法

2014-07-20甄士刚王金敏

天津职业技术师范大学学报 2014年1期
关键词:规则评价

甄士刚,王金敏

(天津职业技术师范大学机械工程学院,天津 300222)

布局问题广泛存在于生产生活实际中,例如货物的运输、机械零部件的分布、车间厂房的布置等,对布局问题的有效解决,具有极大的现实意义。长期以来,人们主要通过启发式算法[1]解决布局问题。例如张德富等[2]将构造启发式算法与模拟退火算法结合,提出一种求解三维布局问题的混合模拟退火算法;Bortfeldt等[3]将多线程搜索应用于禁忌搜索算法,提出一种并行禁忌搜索算法;Gehring等[4]提出了解决三维布局问题的并行遗传算法;Parreno等[5]基于最大空间概念的构造堆算法,进一步发展和改进了一种贪心随机自适应搜索算法;He等[6]基于古语“金角银边草肚皮”提出一种针对三维矩形布局问题的高效定位启发式算法。本文针对三维矩形布局问题,通过将构造启发式算法的定位和定序结合,提出一种基于评价函数的布局遗传算法。

1 三维矩形布局问题

三维矩形布局问题的数学模型描述如下:

设布局空间的体积为V,布局空间的体积利用率为f,则目标函数

式中:lk、wk、hk分别为第k个已布入矩形块的长、宽、高;n为布入的矩形块块数。布局结果由体积利用率f来衡量,f值越大布局结果越好。约束条件

式中:L、W、H分别表示布局容器的长、宽、高;(xi,yi,zi)和(xj,yj,zj)分别为第i个和第j个已布入物体的中心点坐标,且i≠j,i、j∈k。这里布局容器的左下前角为坐标原点(0,0,0)。li、wi、hi和lj、wj、hj分别为第i个和第j个已布入矩形块的长、宽、高。式(2)(3)(4)保证物体完全布入到布局空间中,式(5)(6)(7)保证两布入物体之间不发生干涉。……

登录APP查看全文

猜你喜欢

规则评价
撑竿跳规则的制定
SBR改性沥青的稳定性评价
数独的规则和演变
中药治疗室性早搏系统评价再评价
规则的正确打开方式
让规则不规则
TPP反腐败规则对我国的启示
搜索新规则
基于Moodle的学习评价
关于项目后评价中“专项”后评价的探讨