![](https://csdnimg.cn/release/download_crawler_static/19640885/bg1.jpg)
第 26卷第 2期 苏 州 大 学 学 报(自然科学版) Vol26 No.2
2010年 4月 JOURNALOFSUZHOUUNIVERSITY(NATURALSCIENCEEDITION)
Apr.2010
收稿日期:2009-10-22
基金项目:国家自然科学基金(60970055)
作者简介:吴进珍(1984-),男,河北宣化人,硕士研究生,主要从事优化计算、生物信息学等方面的研究.
一个基于蚁群优化解决 2Dpacking问题的算法
吴进珍,吕 强
(苏州大学 计算机科学与技术学院,江苏 苏州 215006)
摘 要:2Dpacking问题是一种二维变量的打包问题,是典型的组合优化问题.本文首先通过贪婪方法得到一
个初始解,然后利用经典的最大、最小蚂蚁算法作为解决问题的主要框架,并针对该问题将一种特定的局部搜
索算法整合到主算法框架中.通过实验结果表明,该算法在解决此类问题上具有一定的优势.
关键词:2Dpacking;蚁群优化;局部搜索
中图分类号:TP301.6 文献标识码:A 文章编号:1000-2073(2010)02-0035-04
Anantalgorithm forsolving2Dpackingproblem
WuJinzhen,LvQiang
(SchoolofComputerScienceandTechnology,SuzhouUniv.,Suzhou215006,China)
Abstract:2Dpackingproblemisa2Dvariationofbinpackingproblem,whichhasbeenprovedasa
veryclassicalcombinatorialoptimizationproblem.Theinitialsolutionsaregeneratedbyagreedyap
proach,thentheMaxMinantsystem isappliedasthemainframeworkofevolvingthesolutions.A
specificlocalsearchisintegratedwithinthemainoptimizationframework.Experimentresultsshow
thatthisalgorithmissignificantforsolvingaprobleminstance.
Keywords:2Dpackingproblem;ACO;localsearch
0 引 言
2Dpacking问题是具有二维变量的打包问题,该问题的数学描述如下
[1]
:给定一个长为 X、宽为 Y的长方
形网格和一个整数 N,再给定一个包含若干个三元组(x,y,Value)的列表,其中 x和 y都为整数,并且在 0~N
-1之间,为了描述方便,在下文将 x或 y称为元素,将(x,y)称为点对,Value表示点对的打分值.如果 x、y都
是位于 0~N-1之间的整数,然而列表中未包含该点对,那么它的 Value为 0.这里规定,三元组(x,y,Value)
和(y,x,Value)是完全等价的.该问题的目标是,在给定的长方形网格的每个格子中放入一个元素,元素为整
数且取值为 0~N-1之间,每个格子中的元素与周围 8个相邻格子中的元素就构成了 8个点对,对应 8个
Value.以此类推,将网格中所有格子与其相邻的格子所对应的 Value相加,最终使得所有相邻格子对应的 Val
ue总和最大,其中约定,每个点对所对应的 Value只能参与计算一次,若再参与计算,该点对的 Value为 0.
2Dpacking问题的搜索空间是巨大的,为 N
XY
.在二维网格中,其中的打分函数可以描述如公式(0.1)所
示.其中 Value
(m,n)(i,j)
表示网格中 m行 n列的元素 x与 i行 j列的元素 y组成点对所对应的 Value,也就是三元
组(x,y,Value)或(y,x,Value)中的 Value.