发布时间 : 星期一 文章立体仓库中英文对照外文翻译文献更新完毕开始阅读406956a67d1cfad6195f312b3169a4517723e583
个可行的方法计算出行程时间，最终选取其中最小的那个值，即t2阶段。最后，在S/R系统中将t1和t2的和设为最终的解决方案。
Khojasteh-Ghamari详细的对在现有巷道中的货物的拣选顺序的分配方法进行了讨论。如果任何待命的货物存在于现有巷道中，那么就将仓库中现存货物的数目除以解决方案的数目。因此，这项任务目的就是降低总方案的数目，以此来减少CPU时间（程序的处理时间）。
3.1.遗传算法
遗传算法是一种优化过程，它将问题域比作基因类（个体或染色体），基因类是有多个基因体组成，其中基因体成符号形式串行。每一个基因类都有一个可能的解，通过对问题域中的染色体进行评估来寻求可能的解决方案。
在每一代中，我们对每个染色体进行评估，选择一个分布优秀的区域，在其中对染色体进行变异和交叉操作，重新组合，得到新的染色体。这样几代之后，在进一步观察后没有得到新进展的情况下，那么就将所得到最具适应度的染色体视为（所有可能的）最佳解决方案。运算常常会在出现大量的迭代速度和资料后终止（Michalewicz）。
表示法
每一个染色体表示待求解问题的一个可能解，将其中每一个等位基因被归为一个货物序列中。如此类推，在染色体中的每个基因序列表示货物的种类和相对等位基因的存储位置。因此，每个解决方案包括一个染色体，其中基因的数量等于所收到命令的货物数目。如给出一个例子，图 1
如图1可见，一个可行方案中的货物设为A,B,C和D代码，他们被检索位置为：货物C在5号位置，货物B在7号位置，货物A在4号位置，货物D在3好位置。
图1.代表一个可行的解决方案
其表格表示为，货物被拣选的顺寻也显示在其中。在这个例子中，在5号位置中货物C将被首先检索，其次是货物B，再是货物A，最后是货物D。
初始化
初始域是随机产生的。拥有随机序列的指令货物组成了染色体。在染色体中，每个货物被赋予一个随机代号。由此可见，每个可行方案所给予的条件是相同的。然而，在每一次重新运算过程中，都会有一套适合的程序来解决方案。因此，染色体中的指令货物将会无重复的随机分布，货物的地址代码也会随机选取，所分配的代号范围会在1到该货物的总仓库库存数之间。
假设在仓库内现有总共A、B、C和D4件货物，它们分别对应代码是6、9、7和4。为了形成如图1所示的解决方案，首先，指令货物死随机选取的（C,B,A和D），然后，货物C选取[1,7]的随机整数，货物B在[1，9]中选取，A在[1,6]之间选取，最后D在[1，4]中间随机选取一个。
交叉操作
在置换问题的操作描述里，部分匹配交叉（简称PMX）常被用于拣选问题上，部分匹配交叉被视为一种交叉的排列，它确保所有的货物能迅速的被后裔所发现。也就是说，两个后裔全面的接受了父辈基因，接着再填充到其父辈的等位基因上。在图2中，两个父辈用p1和p2来表示，交叉点是1和3。根据在相应的[M,R]和[E,A]之间，重复做货物的取代，这就是说，在第一个父辈中的A和E由R和M所取代，而在第二个父辈中的R和M就由A和E来取代。生成的后代是O1和O2(图2)。
同时，根据PMX中的拣选问题得知，交叉操作的关键是只交换在染色体中的货物区域并且不交换相关的等位基因。
图2.PMX操作
变异操作
我们现在用二进制位(0和1)来表示基因。在拣选的问题上，相关联的等位基因通过变异操作，将库存中一个基因替代另外一个等位基因。换而言之，这个操作并没有对货物的序列起到任何作用，仅仅只是货物选择了另外一个序列代码。
假设在O1中，第三个基因被选为变异基因。由于货物A在各储存位置上的总数有6个，通过变异操作在[1,6]范围里产生随机整数来代替原来的第三个基因(图 3)，当然，产生的代码等于现有代码时(如2)，则操作重复进行，直到取得一个新代码(除了2)。在这个范例中，4就是最后产生的代码。
评估与选择
在每代中，对于染色体的评估使用了一些有效的方法。
图3.变异操作
在大量的优化应用中，适应度是对目标客观本质的计算。在拣选问题中，目标函数的作用是将S/R系统的行程时间降低到最小。通过S/R系统对总行程时间做标准化的计算来得到下一代。Khojasteh-Ghamari对S/R系统计算的行程时间进行做了一下说明。
由于这个问题是最小化的问题，所以我们可以将每个染色体的目标函数值改变成适应值，适应值大的染色体就更具适应能力，这样就能更清晰的表达他们的价值程度(cheng等人提出)：
其中，eval(vk)是第K个染色体的适应函数，f(vk)是第k个染色体在S/R系统下总行程时间。问题域的大小(简称pop size)决定了每个染色体应被给的时间。
现在来做个比喻，我们对下一代染色体的选择比作为(赌台上的)轮盘，适应度大的染色体在下一代遗传中被选的概率更高。在此方案中，行程时间短的更容易被选中作下一代的遗传。赌盘的执行如下：
1.计算对于每个染色体的vk(k=1,2,...,最大范围值)在S/R系统的总行程时间。 2.计算每个染色体的适应度eval(vk)(k=1,2,...,最大范围值)。 3.求得所有适应的总数量
4. 计算对于每个染色体Vk的选择概率pk(k=1,2,...,范围最大值)。
5. 计算每个染色体vk的累积概率qk(k=1,2,...,范围最大值)。
每次选择是在旋转的赌盘中进行的，其结果是动态的，被选中的染色体作为下一代的范围域。
-生成的一个随机实数r在[0，1]范围内；
-如果r≤1，那么选择的第一个染色体v1，否则选择第k个染色体vk(2 ≤ k ≤ pop size)，这样就有qk?1 < r ≤qk。
在上一代中的染色体被新一代的染色体所替代。
4.仿真结果
我们制作了一个拥有36种不同货物的立体仓库，在其中还有5种不同类型的指令，对此比较3种运算法的性能。每个货物首先先用例证法来解决。以获取最佳的行程时间和CPU占用率。接着用另外两种解法来解决。研究结果如下2表。
4.1.仿真模型
我们创建了一个在36种不同物理规格情况下的仓库，通过对于每一个仓库施加5种不同的指令来对这3种算法的性能进行比较。每种情况首先按例证法来得到最佳的行程时间和CPU占用率，然后再通过另外两种计算方法来解决问题。研究结果显示在下面两个表格中。
利用仓库的主要3个参数（仓储容量、密度和形状）来设计36种不同存储的情况。由于仓储容量与仓库中的巷道成比例关系，我们将仓储容量划分为4种情况，分别是1、2、3和4种巷道的形式。每个仓储货架有780个存储位置。因为每个巷道有两个货架，