章 翼， 杜永贵

(太原理工大学 信息工程学院，山西 太原 030024)

应用技术

改进型文化算法在三维空间装载中的应用*

章 翼， 杜永贵

(太原理工大学 信息工程学院，山西 太原 030024)

为提高仓储货运空间利用率，降低成本，提高效率，提出基于改进型文化算法的三维空间最优装载方法。根据装载问题的特点，兼顾各项约束条件建立起一个多约束多目标的数学模型，并且将文化算法单一的信仰空间改进为多层。该算法通过对多层信仰空间择优选取，用其中的经验来提高进化速度和计算性能，同时保持搜索范围广等优良性。仿真结果表明：该算法有良好的结果，与传统算法相比，能够更有效快速地解决三维集装箱装载问题，可应用性好。

文化算法； 三维装载； 约束优化； 智能算法； 多层空间

0 引 言

三维装载问题是一个典型的组合优化问题，通常被人们认为在多项式时间内无法获得最优解，所以,在此研究领域内的学者们都在研究用各种优化算法来解决此类问题，例如:启发式算法、传统进化计算，或者将两者相融合的算法等[1]，虽然这些算法在多约束问题上可以取得一个较好的解，但其研究成果只是集中在种群自然进化选择这一层面，结果仍然不理想，而文化算法(culture algorithms)则用一种显性机制来提取、保存和整合被求解问题的知识经验，使种群进化速度超越单纯依靠种群基因遗传的进化速度，搜索的范围和速度也更优良，在一些问题上，文化算法取得比传统进化计算更好的结果[2,3]，此外，还有文献[4,5]中将传统进化算法与文化算法相结合，但都是单层信仰空间指导进化过程，且单层的信仰空间前后没有优劣之分，在遇到后一代信仰空间比前一代差时容易陷入局部极值，限制了性能的提升。

本文提出一种基于多层信仰空间的文化算法解决三维装载问题，提高算法的性能和产品装箱配载率，优化过程不受限制性条件的约束，不仅在实际应用中满足目前工作的需求，提高解决问题的效率，减少工作时间，对提高物流效率、增加企业收益、减少产品损耗均有意义。

1 三维装载问题模型构建

三维装载问题定义为：对于确定的空间，在待装货物数量无限，满足空间体积、重量、重心、方向等约束情况下装载最多体积的货物。假设所有货物均为规则长方体，待装货物i的长、宽、高分别为li，wi和hi，集装箱空间尺寸为：L(长)，W(宽)，H(高)，则目标函数表示如下

(1)

根据三维装载问题的属性和特点，及实际配载中遇到的问题，求解过程中需满足如下几个约束条件：

1)方向约束：货物的放置一般有3种：可任意旋转、仅水平旋转和不能旋转。为提高效率，本文设货物可任意旋转，相邻方向序号之间货物旋转90°

(2)

式中 di为摆放方向系数。

2)质量约束：装载货物的质量之和不可超过集装箱最大载重量

文中基于核稀疏表示的多模人脸人耳融合识别算法是在基于稀疏表示的识别算法（MSRC）的基础上引入核方法得到。

(3)

式中 gi为第i件货物质量，集装箱最大载重量为G。

3)体积约束：被装载货物的体积之和小于集装箱的容积

(4)

4)重心约束：货物完全装载后整体与单件货物的重心在安全范围内，确保运输安全

(5)

设装载完成后重心坐标为(X，Y，Z)，则重心安全范围为X∈[f1,f2]，Y∈[f3,f4]，Z∈[0,f5][6]，(xi,yi,zi)为货物i摆放位置坐标。

5)承载力约束：货物所能承受的重量有限，避免被上层货物损坏

(6)

式中 ∑gk为压在货物i上的重量和，bir为货箱i承重量阈值上限。

2 基于改进型文化算法的问题求解

三维装箱问题属于不确定多项式问题，随着问题规模的不断扩大，难以在有限的时间中找到最优解。改进文化算法可以对进化信息进行有效的提取和管理，将单一的信仰空间改进为多层信仰空间，有效地避免了经验的倒退[7]，从多层空间中选择最优的信仰空间来指导进化搜索，优质的个体与信息得以获得更大的生存概率，信仰空间与种群空间双层进化方法融合了进化搜索和局部搜索策略，既具有全局搜索范围大的优点，又具有局部搜索的深度优势，双层进化的结构使种群的进化速度大大超越单纯依靠生物基因遗传的进化速度，具有良好的全局优化性能。且优化过程不受约束条件的限制，具有很强的鲁棒性，搜索效率也比传统进化算法更快，是解决工程优化问题的一种高效的优化方法[8]。

2.1 文化算法构架

文化算法是Reynolds在1994年提出的一种双层进化机制，这种算法通过模拟人类社会的演进过程来完成高效寻优的过程，文明社会中，文化是人类所拥有经验的集合，可以供后人直接学习，并用于指导每个个体的行为。文化算法除种群进化空间外还通过-个独立于种群空间的信仰空间，来获取和保存并加以整合解决问题的知识，并且2个空间通过特定的协议进行信息交换，算法构架如图1所示。

图1 文化算法构架Fig 1 Framework of cultural algorithm

其中，接受函数():收集群体中被选择的经验，传递至信仰空间；更新函数():更新信仰空间，形成种群经验；影响函数():利用经验知识对种群空间进行指导；种群操作():对种群进行交叉、变异等操作，生成下一代个体；选择函数():选择优良个体；目标函数():得到每个个体适应值，性能评价。

2.2 个体编码与适应度函数

为更好地解决装载问题，编码时考虑货物装载的先后顺序和放置方向，设置长度为2n的数字串S=(s1,s2，…,sn,sn+1,…,sn+1,…,s2n)对应不同的装载方案。其中，基因s1～sn表示货物装载顺序编号，由[1,n]间产生的任意整数排列组成，且整数无重复，基因s1～sn所在位置1,2，…，n与货物编号相对应，基因sn+1～s2n表示货物方向约束的编号，由集合[1,2,3,4,5,6]中随机产生的任意整数组成，sn+1～s2n中的整数可重复，数字分别代表货物的6种摆放方向[10]。基因s1～sn与基因sn+1～s2n之间的对应关系为：sn+i代表货物si的装载摆放方向[11]，不装载均为0。

以个体适应值大小来评价群体中个体所对应装载方案的优劣，较优个体有更大的生存机会。装载优化问题属于最大化问题，填充率越高解越优质，函数表示为

(7)

2.3 接受函数

接受函数accept()在群体空间内按照一定比例选择可以影响当前信仰空间的个体，在文化算法中标准化的经验和约束知识被不同个体影响。accept()按照适应度函数值选择前20 %的个体融入信仰空间，接受函数如下

(8)

其中,P为种群规模；α为接受比率，本文取α=0.2；t为进化代数。

2.4 多层信仰空间结构

2.5 多层信仰空间更新和知识更新

多层信仰空间同时保存前几代评价值最优的信仰空间，每次指导种群进化时从多层空间中通过评价值函数筛选出最优一层来操作，如图2所示。只需要对信仰空间进行评价就能有效地避免优质经验被劣质经验所迭代的危险，优质的信仰空间知识有更大的概率生存，多层信仰空间的策略比仅有单层信仰空间指导的进化更加完备。

图2 多层信仰空间文化算法构架Fig 2 Framework of multilayer belief space cultural algorithm

新一层信仰空间由更新函数update()在上一代信仰空间基础上进行知识更新。

标准知识N更新规则如下

(9)

(10)

(11)

(12)

最新产生的信仰空间与前几代信仰空间通过评价值函数选出最优层和最差层，最优一层信仰空间指导种群空间进化过程，删除最差的一层，信仰空间层数保持不变。

2.6 影响函数

影响函数influence()根据标准知识设定，以调整变量变化方向和步长，函数定义如下

(13)

其中，N(0,1)为标准正态分布变量，size()为信仰空间中变量i调整区间的长度，λ为变量变化步长因子。

文化算法通过函数对信仰空间进行更新，并且实现群体空间与信仰空间之间的通信，2个空间是两个相互独立的进化过程，但是又相互影响促进，对进化信息进行有效的提取和管理。

2.7 算法实现流程

根据上述文化算法各种函数和准则定义，将改进型文化算法应用于三维集装箱装载问题的具体实现中，算法流程如下：

1)初始化各项参数，初始化种群空间，初始化信仰空间，根据参数取值，生成改进文化算法初始种群空间；

2)通过适应度函数对初始种群中的个体进行评价；

3)根据初始种群评价值，提取优秀个体，由接受函数accept()选择这些评价值高的优良个体进入信仰空间，生成初始信仰空间；

4)根据式(9)～式(12)更新当前信仰空间，对多层信仰空间进行评价，从中选择生成最优信念空间；

5)根据影响函数influence()，对种群空间中的个体进行影响和变异，父代根据最优层信仰空间知识产生子代，对每个个体进行评价；

6)t=t+1；

7)通过接受函数accept()从种群空间中选出优秀个体；

8)判断是否满足终止条件，若不满足终止条件，则转至步骤(4)循环，若满足，即达到最大迭代次数，则结束；

9)输出装载问题的最佳装载方案。

3 算法实例仿真

用Matlab编程仿真，采用3层信仰空间，群体规模100，最大迭代次数500，以20ft(1ft=304.80mm)标准集装箱为例，尺寸为2 352mm×2 388mm×5 899mm，30件不同类货物尺寸和改进型文化算法运行结果如表1。

将3种不同方法的运行结果，包括所得的平均解、空间利用率和运算时间列于表2，改进文化算法的空间利用率为90.72 %，装入84 %的货物，运算时间均在90s以内。

由表2可见，采用改进型文化算法得到的最优解比采用遗传算法(GA)和启发式算法(HA)得到的最优解更好，由于改进文化算法在进化计算的过程中将求解多约束问题的约束知识提取出来，根据优秀的区域对进化过程进行指导，有效地避免了对不可行解和不良的个体的无效搜索，对适应值函数的计算量大大减少，少走“弯路”，从而提高搜索效率，节约大量时间，图3列出了4种方法的收敛曲线，改进文化算法迭代至158代开始趋于平稳。

由表2和图3可以看出：利用改进型文化算法能够达到比单层信仰空间文化算法、遗传算法和传统启发式算法更高的空间利用率，有效地减少了布局空间浪费，稳定性也有所改善，多层信仰空间有效地避免了经验知识的倒退和易陷入局部最优的缺陷，性能得到充分的发挥，当货物数量增大时，多层信仰空间文化算法的优势更为明显。

表1 货物尺寸与运行结果表Tab 1 Size of cargo and operating result

表2 3种算法结果比较Tab 2 Comparison of results by three kinds of algorithms

图3 算法搜索过程Fig 3 Search process of algorithms

4 结束语

本文构建了一个解决三维集装箱装载问题的数学模型，全面地分析三维集装箱装载问题，并运用基于多层信仰空间的改进型文化算法对问题进行求解，通过仿真来验证，结果表明：运用改进文化算法求解三维集装箱装载问题具有较好的结果和相对少的计算量，克服了传统进化算法效率不高和易陷入局部最优的缺点，多层信仰空间保证了指导种群进化的经验知识的质量，确保种群空间的发展，更加准确地接近最优解，双层进化机制扩大了解的搜索空间，并且节省计算资源和时间，改进文化算法对装载问题具有良好的适用性和全局优化性能。

[1] 李建华，李锦文.多约束三维装箱问题的研究综述[J].计算机光盘软件与应用，2012,17：1-3.

[2] Yuan X H,Yuan Y B.Application of cultural algorithm to generation scheduling of hydrothermal system [J].Energy Conversion and Management,2006,47:2192-2201.

[3] Coello C A,Becerra R I.Evolutionary multi-objective optimization using a cultural algorithm[C]∥Proceedings of 2003 IEEE Swarm Intelligence Symposium,Indianapolis,Indiana,IEEE Service Center,2003：6-13.

[4] Ricardo L B,Carlos A,Coello C A.Cultural algorithm with diffe-rential evolution to solve constrained optimization problems[J].Lecture Notes in Computer Science,Springer,2004,3315:881-890.

[5] Gao F,Cui G,Liu H W.Integration of genetic algorithm and culture algorithms for constrained optimization[J].Lecture Notes in Computer Science,Springer,2006,4234:817-825.

[6] He Chuan,Zhang Yuanbiao,Wu Jianwen,et al.Research of three-dimensional container-packing problems based on discrete particle swarm optimization algorithm[C]∥International Conference on Test and Measurement：[s.n.],2009:425-428.

[7] 黄海燕，顾幸生，刘漫丹.求解约束优化问题的文化算法研究[J].自动化学报，2007,33(10)：1115-1120.

[8] 刘漫丹.文化基因算法(memetic algorithm)研究进展[J].控制理论与应用，2007,26(11)：1-4.

[9] 王友钊，彭宇翔，潘芬兰.基于贪心算法和遗传算法的仓储车辆调度算法[J].传感器与微系统，2012，31(10)：125-128.

[10] 许光泞，俞金寿.改进遗传算法求解三维集装箱装载问题[J].华东理工大学学报:自然科学版，2007，33(3)：425-428.

[11] 卜 雷，袁新江，蒲 云，等.基于遗传算法的集装箱单箱三维装载优化问题[J].中国铁道科学，2004，25(4)：108-111.

Application of modified cultural algorithm in 3D space loading*

ZHANG Yi， DU Yong-gui

(College of Information Engineering,Taiyuan University of Technology,Taiyuan 030024，China)

To improve utilization of space of logistic distribution,reduce costs and improve efficiency,modified cultural algorithm for 3D space optimal loading method is proposed.According to characteristics of loading problems,take multiple constraints into account,a multi-constrained and multi-objective mathematical model is established,the single belief space of cultural algorithm is improved to multilayer.This algorithm improves computing performance and speed of evolution through the experience selected from multi-layer belief space,and keep good performance of wide searching range.Simulation result proves that the algorithm produces better result,more efficient and faster than traditional algorithms in solving 3D container loading problem,applicability is good.

cultural algorithm; 3D loading; constrained optimization; intelligent algorithm; multilayer spaces

10.13873/J.1000—9787(2014)08—0145—05

2014—01—06

材料强度与结构冲击山西省重点实验室开放基金资助项目(4015—04110004)

TP 301.6

A

1000—9787(2014)08—0145—05

章 翼(1989-)，女，山西太原人，硕士研究生，研究方向为智能控制理论与应用﹑优化控制。