几种优化网格算法在智能集装箱中的应用

0 引 言

目前集装箱这种新型、高效率和高效益的运输方式已广泛用于国际贸易，集装箱制造是一门融合机械、冶金、化工、木业、电子、计算机等行业为一体的综合性行业。它是资本密集、管理技术要求高的产业。随着科学技术的不断进步，新技术、新材料在集装箱行业的应用越来越广泛。随着社会进步，科技的发展，集装箱应用新技术、新材料、新工艺、新方法的创新不断出现。而电子、信息、自动识别等新技术的成熟和推广应用，又为提高集装箱运输效率，提供了巨大的空间。业内专家也认为智能化、信息化是今后集装箱业务的重点和发展方向。

智能集装箱 [1] 是在一个集装箱内安装多台服务器机架， 以提供对IT 设备的最大支持，同时包含必要的消防、安防与监控设施，所需动力配套设施在集装箱外部布署。另外RFID 射频技术也被应用其中，再结合 GPS，能把集装箱状态变化发生的时间、地点以及周围的环境信息传递给管理人员的计算机，以实现集装箱的实时跟踪和监控。现在的集装箱都安装了智能电子标签（包括电子封条和传感器封条），通过它可以将集装箱的一些关键信息传给 TSS 系统（Transportation Security System，交通安全信息系统），通过这些大大地提高了集装箱的安全性能。那如何来提高智能集装箱空间和载重能力呢？集装箱中货物多样化、结构特殊化、运载时间和地点变化大等特征，使得智能集装箱中必须要有一种超级处理能力的计算机来帮助其实现这诸多的性能。但它的造价极其昂贵，通常只有一些国家级的部门，如航天、军事、气象等部门才有能力配置这样的设备。而随着人们在日常工作遇到的商业计算越来越复杂，人们迫切需要数据处理能力更强大的计算机，而超级计算机的价格显然阻止了它进入普通人的工作领域。一种造价低廉而数据处理能力超强的计算模式——Grid Computing（网格计算）[2,3]满足了人们的需求。网格也是一种先进的计算基础设施（Advanced Computational Infrastructure，ACI），用于研究与工程应用相结合的项目，学科领域涉及超级计算技术、网络技术、数据库技术、中间件技术、并行算法和各种计算科学研究与应用技术，是一个综合性的跨学科高技术研究课题。

在科学计算领域，网格计算可以在以下几个方面得到广泛应用：

(1) 分布式超级计算。网格计算可以把分布于不同位置的超级计算机集中起来，把众多复杂的大规模的问题联合解决，并且把许多闲置的计算机资源得到了有效的组织，提高了系统资源的利用率，节省了大量的重复投资，使用户的需求能够得到及时满足。

(2) 高吞吐率计算。网格技术能够十分有效地提高计算的吞吐率，它利用CPU的周期窃取技术，将大量闲置的计算机资源集中起来，提供给对那些对时间分配不是很重要的问题，作为计算资源的重要来源。

(3) 数据紧密型计算。对于数据紧密型的问题的求解， 对通讯和计算会生成很大的需求，一般的算法难以解决，需要网格能力才可以解决。而网格计算恰好可以在电子学、生物学、药物分子设计、计算力学、计算材料、核反应、航空航天等众多的领域得到广泛的需求。

(4) 信息共享的人与人交互。网格技术突破了人与人之间地理位置的限制，便于科研者之间沟通，从某种程度上可以说实现人与人之间的智慧共享。

(5) 更广泛的资源贸易。随着大型机性能的提高和微机普及应用，计算机资源的闲置问题也越来越明显，网格技术能够有效地组织这些闲置的资源，使得那些有大量计算需求的用户能及时地获取资源。

1 网格算法

网格计算实际上是一种分布式计算。什么是分布式计算？ 所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机分别进行处理，最后把这些计算结果综合起来得到最终的结果。总的来说网格算法比起其它算法具有以下几个优点：

(1) 共享紧缺资源 ；

(2) 平衡计算负载；

(3) 可以把程序放在最适合运行它的计算机上。

其中，共享紧缺资源和平衡负载是计算机分布式计算的核心思想之一。参与这种计算的不只是一台计算机，而是一个计算机网络，所以这种“蚂蚁搬山”的方式具有很强的数据处理能力。网格算法的实质就是组合与共享资源并确保系统安全。

2 集装箱常用的网格算法

(1) 遗传算法 [4-6] ：是模拟生物进化过程的计算模型，是自然遗传学与计算机科学相互结合、相互渗透而形成的新的计算方法。通常用来生成有用的解决方案来优化和搜索问题。

(2) 多重网格算法（MultiGrid）：是一种用于求解方程组的方法，可用于插值、解微分方程等。从专业角度讲多重网格法实际上是一种多分辨率的算法，由于直接在高分辨率（用于求解的间隔小）上进行求解时对于低频部分收敛较慢，与间隔的平方成反比。

(3) 海量数据三角网格算法 ：以最近邻域快速搜索边界点的最近邻域，以增量算法的边界环为基础向外生成三角形， 实现点云数据点间合理的三角剖分网格。

(4) 矩形网格生成等值线算法 ：该算法思想是建立矩形网格的关联表，不用找线头和线尾就可一次追踪到某一高程的多条等值线。

(5) 协克里金算法（CollocatedCokriging）：适合层位、断层、网格、XYZ 数据、层段属性、钻井分层。

2.1 遗传算法在智能集装箱中应用

2.1.1 优化搜索

遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：

(1) 首先组成一组候选解 ；

(2) 依据某些适应性条件测算这些候选解的适应度；

(3) 根据适应度保留某些候选解，放弃其他候选解 ；

(4) 对保留的候选解进行某些操作，生成新的候选解。

但是遗传算法的局部搜索能力较差，导致单纯的遗传算 法比较费时，在进化后期搜索效率较低。在实际应用中，遗传 算法容易产生早熟收敛的问题，不能很好地解决大规模计算 量问题。可将局部搜索能力强的爬山算法与传统的遗传算法 相结合，形成混合遗传算法来替代。混合遗传算法是一种更 全局优化的算法，还具有以下几方面的优点 ：

(1) 混合遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的，容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。

(2) 混合遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险， 同时算法本身易于实现并行化。

(3) 混合遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。此特点使得遗传算法的应用范围大大扩展。

(4) 混合遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。

(5) 混合遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式，从而保证算法的有效性。

(6) 混合遗传算法对所求解的优化问题没有太多的数学要求，由于他的进化特性，搜素过程中不需要问题的内在性质， 对于任意形式的目标函数和约束，无论是线性的还是非线性的， 离散的还是连续的都可处理。

(7) 进化算子的各态历经性使得遗传算法能够非常有效地进行概率意义的全局搜素。

混合遗传算法具有摆脱局部最优解的能力，能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。

2.1.2 函数优化

函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。遗传算法的适应度函数[7-9] 也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。目标函数是求解的优化变量的函数形式，为了得到好的搜索性能，经过一些变化就可以得到适应度函数，而适应度函数是求解的优化变量的一种度量，由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。它的设计直接影响到遗传算法的性能。下面来讨论一下改进的适应度函数：

另一种情况下：

在理想情况下，设 β=2，α 值分别取 0.5、1、1.5，就可在 a， b值确定的情况下得到 3种适应度函数。当 α=1时，适应度值在（0.5～1）之间是线性的 ；当 α=1.5 时，适应度值则是相反的情况。

2.1.3 分类组合优化

随着数据规模的扩大，分类组合优化的问题也急剧增大， 目前其他搜索法很难求出最优解。对这种复杂的问题，我们只要能求出最优解就可以了，而遗传算法是寻求这种最优解的最佳算法之一。所谓组合优化是从有限个可行解中找出使某个目标函数达到最优的解的优化问题。可分为连续优化和离散优化。而组合优化是一种离散最优化问题，典型的有旅行商问题、加工调度问题、背包问题、装箱问题、类聚问题、车辆路径问题等。现以装箱问题作为例子来描述组合优化。设有许多长为 L 的一维箱子及长分别为 ：Wi，i=1，2，…，n 的 n 件物品，且 0<Wi<L，欲把这些物品全部装入箱中，为了给出它的整数线性规划描述，先引入一些变量：如果第 i 个箱子使用， 则 yi=1，否则 yi=0，第 j 个物品放入第 j 个箱子中 xij=1，否则xij=0。用数学方法来描述即：

2.2 多重网格算法在智能集装箱中应用

2.2.1 并行全局最优化

集装箱的装箱问题实际上是NP 完全问题，求解是十分困难的，而多重网格方法是一种快速计算方法，该方法采用不同尺度的网格，不同疏密的网格消除不同波长的误差分量， 首先在细网格上采用迭代法，当收敛速度变缓慢时暗示误差已经光滑，则转移到较粗的网格上消除与该层网格上相对应的较易消除的那些误差分量，这样逐层进行下去直到消除各种误差分量，再逐层返回到细网格上。多重网格法是迭代法与

粗网格修正的组合，经过证明，迭代法可迅速地将那些高频 分量去掉，粗网格修正则可以帮助消除那些光滑了的低频分量， 而对那些高频分量基本不起作用。如果把集装箱当成一个数 学模型，首先可将各参数变量值的区间，划分成一片片的小网 格，由计算机算出各参数变量值的组合情况，再对所对应的 目标值进行逐一比较择优，从而得出该区间的最小目标值及对 应的最佳参数值，也就得出了装箱的全局最优解，而 Powell 算法 [10] 具有在局部求解最优解的能力，它是一种方向集方法， 专门针对当目标函数特别复杂，没有办法掌握目标函数特性的 一类优化问题，在集装箱装箱过程中，可用多重网格并行优化 搜索法来确定装箱模型中的各个待定参数，把集装箱采用均 匀分布点的方法，让这些点在变量空间中均匀分布，再把这 分布点作为 Powell 算法的初始点，通过 Powell 算法从各初始 点开始对整个集装箱模型进行优化计算，即可得到局部最优 点和最优值，再取所有局部最优值中的最优值，就得到了全局 最优值，这样把这种具有全局和局部最优解的算法结合起来， 形成了并行全局最优化算法，避免了装箱中空间浪费、物品归 类不当等问题，从而提高集装箱装箱率。

2.2.2 网格融合技术创建三维模型

网格可分为自由网格和映射网格，自由网格适合那些不 太规则的模型 ；而映射网格就是建立的网格都是比较规则的， 这样计算出来结果非常接近实际问题，而且可以根据自己的 意愿建立生成一定的、确定的单元个数，从而加快后期计算 速度等 ；另外，映射网格技术可以避免产生一些特别畸形的 单元等，也是映射网格的好处。在集装箱装箱物品的过程中， 有不规则的也有规则的，或者是两种混合的，这就需要把这 两种网格技术都相互结合起来，那么就可采用一种网格模型 融合算法 [11-13]，该算法首先将需要的部分网格从源模型上交 互剪切下来，并将其配准对齐 ；然后将两网格模型转化成点 模型表示，并将点模型转化成 RBF 隐函数表示 ；再对两隐函 数进行布尔运算 ；最后将布尔运算生的隐函数曲面在两网格 接合区域进行三角形化 ；得到最终的网格模型。这种算法具 有很好的网格融合效果，可用于集装箱的三维立体构造，便 于装箱人员更好地利用集装箱空间。

结 语

本文主要从网格算法的优化搜索和改进函数出发，提出的混合遗传算法，是一种更全局优化的算法，在求解适应度函数时能够得到更合适的最优解，而优化的多重网格算法能够提高全局和局部的最优化搜索，使集装箱变成可视化的三维结构， 解决了装箱的空间浪费问题，提高了智能集装箱的利用率。