基于免疫遗传算法的货位优化研究

刘琪

沈阳工程学院信息学院, 辽宁 沈阳 110136

1 概述

自动化立体仓库是现代物流仓储管理模式中，所采用的一种高效的，简便的，自动化的仓储模式。使用自动化立体仓库，可以让使用者具备以下几方面特点。

1.1 能够对物品进行合理的储存

提高存储效率。由于自动化立体仓库使用了计算机和自动控制系统。能够对货物的入库，出库，以及货物位置的摆放，进行实时监控。使货物的管理能够做到信息化，现代化管理[1]。

1.2 节约存储空间

自动化立体仓库能够有效的利用立体空间，将原有的平面式存储模式，改变成空间式的立体存储模式。给企业以多种选择仓库地点的机会。可以在合适的地点进行仓库的选址，使库存的周期可以缩短，可以节约运输成本，以提升仓储物流的效率[1]。

1.3 信息化管理

能够将货物的信息通过条码扫描，存储进计算机。由计算机对自动化立体仓库进行统一的管理，能够对库存，货物分布的情况，进行合理的管理。提高企业对货物管理的准确性和效率性。企业领导能够及时，准确的了解货物库存的数目，以便做出对货物相应的入库，出库的调整。能够及时的为企业做出正确的决策。

2 货位优化

自动化立体仓库的一个货架，可以看作平面上的网格。根据从离出入库口最近的货位开始排列，1,2,3………X排，每个货位都有自己的一个平面坐标（X,Y），但一个自动化立体仓库有很多个货架。所以，一个自动化立体仓库货位的坐标，

可以表示成三维坐标（X,Y,Z）。X表示货位所在的货架数，Y表示货位所在的排数，Z表示货位所在的层数。不同的货物，要放在不同的货位，每个货物可以设置一个向量参数。（A，B，C），B可以代表一些货物是否要临近摆放，C可以代表货物的重量[2]，A可以代表货物的出入库频率。将要优化的货物的参数向量组成一个矩阵。再将所有的自动化立体仓库的货位组成一个矩阵。最后得出一个总的权值。这是一个多目标优化的问题。通过免疫遗传算法可以很好地解决这个问题。

3 免疫遗传算法设计

免疫算法是从生物的免疫系统原理总结出来的。生物的免疫系统是防御疾病入侵的主要保卫系统。免疫系统由免疫器官，免疫细胞，免疫分子组成。免疫细胞在免疫系统中发挥着非常重要的作用。抗原是指病毒，细菌，花粉等进入机体内的外来物质。

抗体是抗原刺激机体的免疫系统，由B淋巴细胞和记忆细胞增殖分化成的浆细胞产生的免疫球蛋白，它可与相应抗原发生特异性结合。免疫记忆是指在获得性免疫方面，对某抗原发生反应，下一次相同抗原激励时，反应会更为强烈。

免疫遗传算法比遗传算法具备很多优势，它将免疫算法中的免疫记忆功能，融合到遗传算法中，并结合遗传算法中的全局搜索能力，能够快速的提高抗体的适应度，

免疫遗传算法按照以下步骤设计：

3.1 随机生成要解决问题的解的种群

根据自动化立体仓库的货位，来进行货位优化，可以将自动化立体仓库的货位按照第几个货架，货架的第几排，第几层。作为一个货位的向量，例如第一个货架，第一排，第一层，向量表示为(1,1,1)。将每一个货位，都按照向量表示，这样就形成了一个解的种群。可以把要解决的问题，看作是抗原。解决问题的解，看作抗体。

3.2 选择操作

3.3 交叉操作

在生物进化的历史过程中，两个染色体可以通过交叉操作，使得染色体可以重新构成，组合。从而形成一个新的染色体。生物中的染色体交叉环节是生物学，遗传学中所描述的生物进化过程中的一个非常重要得环节。遗传算法就是通过两个解的交叉操作，产生一个新的解。在自动化立体仓库货位优化的问题中，交叉操作可以是所有自动化立体仓库货位向量之间的一次重新组合。根据种群中适应度的高低，选择适应度相对高的两个解。随机生成交叉点。并以交叉点的货位为基础，交换两个解的某些货位。交叉操作产生子代，子代继承了父代的基本优点。交叉操作的步骤是如何确定交叉货位向量的位置，和如何进行部分货位向量的交换。免疫遗传算法中的交叉操作，是指对两个经过轮盘赌算法选择出来的两个解按照算法的设计交换解的部分货位向量。进而组成两个新的解。遗传算法中的交叉操作是遗传算法区别于其他生物行为算法的一个重要特征。交叉操作是遗传算法中的一个非常重要的操作，是产生一个新解的主要方法。

3.4 变异操作

遗传算法中的变异操作，是从染色体变异启发出来的。以初始解的变异概率为根本，对交叉之后的解，进行变异运算。在自然界的生物进化与遗传行为中，生物的细胞的染色体的变异是由多种因素共同作用的结果，例如各种射线，温度剧变，衰老等。进而变异成新的染色体，呈现出一种新的生命特征。在货位优化的问题中，可以将一个或几个货位进行变异操作，从而形成一个新的货位向量的解。由于变异是小概率事件，所以只能是对交叉操作的一种补充[3]。

3.5 计算种群适应度

在遗传算法中，应用适应度这个名词解释种群中各个解在大范围搜索计算中接近最有利于解决该问题的解的一个适合程度。适应度大的解，能够存活并遗传到下一代的概率相对大一些，而适应度小的解，能够存活并遗传到下一代的概率相对小一些。

3.6 免疫记忆

应用到实际问题中就是根据原来的解，产生一个适应度更高，更为接近最优解的解[4][5]。

4 仿真实验

取八个货物，每个货物用一个向量表示，

将向量a1,a2,a3……a7,a8的转置向量组合成一个矩阵F。选取第1个货架，3排，4层的所有货位组成矩阵G。使两个矩阵相乘，最后算出适应度的总和。分别使用免疫遗传算法和遗传算法进行仿真实验五次，取最佳货位组合的平均适应度。如下表。

?

从上表得出免疫遗传算法效率要优于遗传算法。

5 结束语

自动化立体仓库是今后物流仓储发展的必然趋势。自动化立体仓库和传统仓库相比，能够节省更多空间，更为信息化，智能化。而对自动化立体仓库进行货位优化，也是所有企业必须做的工作，进行货位优化，能够节约经济成本，人力成本。

[1]刘昌祺，董良. 自动化立体仓库设计[M].北京：机械工业出版社,2004

[2]商允伟. 自动化仓库货位分配优化研究.计算机工程与应用[J],2004.26:16-21

[3]田国会, 张攀等. 基于混合遗传算法的固定货架拣选优化问题研究[J].机械工报,2004,40(02)

[4]王磊, 潘进,焦李成. 免疫算法.电子学报[J], 2000, 28(7):158-163

[5]亓霞，陈森发，黄鹤，周振国. 基于免疫算法的物流配送车辆路径优化问题的研究[J].土木工程学报,2003.7