小组成员：
白浩 2022202210054
田昊丽 2022202210063
物流公司在流通过程中，需要将打包完毕的箱子装入到一个货车的车厢中，为了提高物流效率，需要将车厢尽量填满，显然，车厢如果能被100%填满是最优的，但通常认为，车厢能够填满85%，可认为装箱是比较优化的。 设车厢为长方形，其长宽高分别为 L, W, H；共有 n 个箱子，箱子也为长方形，第 i 个箱子的长宽高为 l_i,w_i,h_i（n 个箱子的体积总和是要远远大于车厢的体积），做以下假设和要求：
- 长方形的车厢共有8个角，并设靠近驾驶室并位于下端的一个角的坐标为（0，0，0），车厢共6个面，其中长的4个面，以及靠近驾驶室的面是封闭的，只有一个面是开着的，用于工人搬运箱子；
- 需要计算出每个箱子在车厢中的坐标，即每个箱子摆放后，其和车厢坐标为（0，0，0）的角相对应的角在车厢中的坐标，并计算车厢的填充率。
- 参数考虑小数点后两位；
- 需要考虑箱子的摆放顺序，即箱子是从内到外，从下向上的摆放顺序；
- 因箱子共有6个不同的面，所有每个箱子有6种不同的摆放状态；
- 算法需要实时得出结果，即算法时间小于等于2秒。
在三维装箱问题中，不同体积的箱子必须以使用最小容器总数的方式，正交地装入一组固定体积的容器中。“三维”是指每件物品的体积由3个维度组成，即长度、宽度和高度。这个问题是NP困难问题，这意味着即使存在能够保证最优解的混合整数规划公式，也更倾向于使用更快的启发式方案解决问题。有了这个想法，遗传算法就可以在可接受的时间内解决问题，尽管它不能保证得到最优解，但是得到的可行解比较接近最优解。
在三维装箱中，有n个长度为三维(d, w, h)的箱子，以及一个固定大小的容器作为放置容器。在不丧失一般性，假设所有要包装的箱子都比容器小。为了实现，只需使用一个带有两个三维向量数组的对象来分别表示箱子和容器的形状。需要在代码中修改对应的数据部分的注释信息。
L_box , W_box, H_box = 587, 233, 220
box_max = 2
inputs = {
# # 3种箱子
'p': [l1] * n1 + [l2] * n2 + [l3] * n3,
'q': [w1] * n1 + [w2] * n2 + [w3] * n3,
'r': [h1] * n1 + [h2] * n2 + [h3] * n3,
# # 5种箱子
# 'p': [l1] * n1 + [l2] * n2 + [l3] * n3 + [l4] * n4 + [l5] * n5,
# 'q': [w1] * n1 + [w2] * n2 + [w3] * n3 + [w4] * n4 + [w5] * n5,
# 'r': [h1] * n1 + [h2] * n2 + [h3] * n3 + [h4] * n4 + [h5] * n5,
# # 8种箱子
# 'p': [l1] * n1 + [l2] * n2 + [l3] * n3 + [l4] * n4 + [l5] * n5 + [l6] * n6 + [l7] * n7 + [l8] * n8,
# 'q': [w1] * n1 + [w2] * n2 + [w3] * n3 + [w4] * n4 + [w5] * n5 + [w6] * n6 + [w7] * n7 + [w8] * n8,
# 'r': [h1] * n1 + [h2] * n2 + [h3] * n3 + [h4] * n4 + [h5] * n5 + [h6] * n6 + [h7] * n7 + [h8] * n8,
# # 10种箱子
# 'p': [l1] * n1 + [l2] * n2 + [l3] * n3 + [l4] * n4 + [l5] * n5 + [l6] * n6 + [l7] * n7 + [l8] * n8 + [l9] * n9 + [l10] * n10,
# 'q': [w1] * n1 + [w2] * n2 + [w3] * n3 + [w4] * n4 + [w5] * n5 + [w6] * n6 + [w7] * n7 + [w8] * n8 + [w9] * n9 + [w10] * n10,
# 'r': [h1] * n1 + [h2] * n2 + [h3] * n3 + [h4] * n4 + [h5] * n5 + [h6] * n6 + [h7] * n7 + [h8] * n8 + [h9] * n9 + [h10] * n10,
# # 15种箱子
# 'p': [l1] * n1 + [l2] * n2 + [l3] * n3 + [l4] * n4 + [l5] * n5 + [l6] * n6 + [l7] * n7 + [l8] * n8 + [l9] * n9 + [l10] * n10 + [l11] * n11 + [l12] * n12 + [l13] * n13 + [l14] * n14 + [l15] * n15,
# 'q': [w1] * n1 + [w2] * n2 + [w3] * n3 + [w4] * n4 + [w5] * n5 + [w6] * n6 + [w7] * n7 + [w8] * n8 + [w9] * n9 + [w10] * n10 + [w11] * n11 + [w12] * n12 + [w13] * n13 + [w14] * n14 + [w15] * n15,
# 'r': [h1] * n1 + [h2] * n2 + [h3] * n3 + [h4] * n4 + [h5] * n5 + [h6] * n6 + [h7] * n7 + [h8] * n8 + [h9] * n9 + [h10] * n10 + [h11] * n11 + [h12] * n12 + [h13] * n13 + [h14] * n14 + [h15] * n15,
'L': [L_box] * box_max,
'W': [W_box] * box_max,
'H': [H_box] * box_max
}
# # 3种箱子
volume_num = l1 * w1 * h1 * n1 + l2 * w2 * h2 * n2 + l3 * w3 * h3 * n3
# # 5种箱子
# volume_num = l1 * w1 * h1 * n1 + l2 * w2 * h2 * n2 + l3 * w3 * h3 * n3 + l4 * w4 * h4 * n4 + l5 * w5 * h5 * n5
# # 8种箱子
# volume_num = l1 * w1 * h1 * n1 + l2 * w2 * h2 * n2 + l3 * w3 * h3 * n3 + l4 * w4 * h4 * n4 + l5 * w5 * h5 * n5 + l6 * w6 * h6 * n6 + l7 * w7 * h7 * n7 + l8 * w8 * h8 * n8
# # 10种箱子
# volume_num = l1 * w1 * h1 * n1 + l2 * w2 * h2 * n2 + l3 * w3 * h3 * n3 + l4 * w4 * h4 * n4 + l5 * w5 * h5 * n5 + l6 * w6 * h6 * n6 + l7 * w7 * h7 * n7 + l8 * w8 * h8 * n8 + l9 * w9 * h9 * n9 + l10 * w10 * h10 * n10
# # 15种箱子
# volume_num = l1 * w1 * h1 * n1 + l2 * w2 * h2 * n2 + l3 * w3 * h3 * n3 + l4 * w4 * h4 * n4 + l5 * w5 * h5 * n5 + l6 * w6 * h6 * n6 + l7 * w7 * h7 * n7 + l8 * w8 * h8 * n8 + l9 * w9 * h9 * n9 + l10 * w10 * h10 * n10 + l11 * w11 * h11 * n11 + l12 * w12 * h12 * n12 + l13 * w13 * h13 * n13 + l14 * w14 * h14 * n14 + l15 * w15 * h15 * n15
之后运行 python main.py，即可获得对应方案的结果
算法由两个部分组成，一个是搜索解空间的有偏随机密钥遗传算法，另一个是在遗传算法中评估每个解表示的启发式算法(称为箱子打包过程)。简单地说，该算法将每个解(装箱顺序和箱子摆放方向)用一个序列进行编码，该序列可以通过启发式算法进行评估，使遗传算法能够通过选择找到好的可行解。
该算法本质上是一个衍生的基于扩展随机密钥和从种群中有偏选择个体的遗传算法。在大多数三维装箱的元启发式算法中，它们不是表示放置箱子的每个坐标，而是为寻找最佳打包顺序（箱子打包的顺序）设计一个基于某种规则的包装过程算法，如最深的底部-左侧-填充方法。这样，在获得高质量解的同时，可以大大简化解的表示。此外，包装序列总是可以映射到一个可行的包装方案，而无需担心坐标重叠，这意味着在此遗传算法实现中不需要进行染色体修复。
随机密钥是一种编（解）码染色体的方法，其中解表示为[0, 1]内的实数向量。假设要打包的箱子数为n。在这个实现中，一个随机密钥的长度总是2n。利用Numpy的随机数生成，可以轻松地生成随机密钥。
# 初始化种群信息，进行编码，种群信息表示为在[0,1]范围之内矢量
population = np.random.uniform(low=0.0, high=1.0, size=(self.num_individuals, self.num_gene))每个解决方案中，前n个基因，为装箱顺序，代表了n个要打包箱子的放入容器中的顺序，可以通过按相应基因值的升序排序来解码。可以使用argsort()方法获取已排序数组的索引。
# 前n个基因定义为货物的摆放顺序，利用 np.argsort函数进行升序排列，之后获取对应的索引
sorted_indexs = np.argsort(fitness_list)后n个基因，为箱子方向矢量，代表了箱子的摆放方向。在三维的设置中，总共有六个方向来放置一个箱子。在某些情况下，一些箱子不能颠倒放置，也不能被垂直方向所限制。要考虑所有可能的方向，每个基因的方向编码称为BO。
# 确定货物的摆放状态
def orient(self, box, BO=1):
d, w, h = box
# BO表示货物的摆放状态
if BO == 1:
return (d, w, h)
elif BO == 2:
return (d, h, w)
elif BO == 3:
return (w, d, h)
elif BO == 4:
return (w, h, d)
elif BO == 5:
return (h, d, w)
elif BO == 6:
return (h, w, d)
def selecte_box_orientaion(self, VBO, box, EMS):
# 在每一种编码解决方案中，前n个基因定义为货物的摆放顺序（BPS）
# 随机密钥后n个基因编码表示为货物的摆放状态（6种之一）
# BOs表示了货物所有可能的摆放状态，货物摆放状态向量
BOs = []
for direction in [1, 2, 3, 4, 5, 6]:
if self.fitin(self.orient(box, direction), EMS):
BOs.append(direction)
# 依据货物摆放状态向量，选择货物的具体摆放状态
selectedBO = BOs[math.ceil(VBO * len(BOs)) - 1]
# if self.verbose:
# print('选择货物的摆放状态:', selectedBO,' (所有可能的摆放状态',BOs, ', 货物的状态向量', VBO,')')
return selectedBO综上所述，有偏随机密钥遗传算法用一个在[0, 1]之间的实数向量来表示一个解，它的长度为2n，由长度为n的装箱顺序和长度为n的箱子方向矢量组成。有了一个箱子包装过程，就可以对该解决方案的质量效果进行评估。
有偏随机密钥遗传算法和其他遗传算法之间的区别是，在每一代种群基于适应度值被划分为两个组，精英组和非精英组。这种有偏差的选择将极大地影响遗传算法中的操作，如交叉操作和种群进化。定义一个函数，根据适应度值和精英个体的数量将种群划分为精英组和非精英组。
# 每一代种群根据适应度函数值，分为精英种群和非精英种群
def partition(self, population, fitness_list):
# 前n个基因定义为货物的摆放顺序，利用 np.argsort函数进行升序排列，之后获取对应的索引
sorted_indexs = np.argsort(fitness_list)
return population[sorted_indexs[:self.num_elites]], population[sorted_indexs[self.num_elites:]], \
np.array(fitness_list)[sorted_indexs[:self.num_elites]]在该算法中，对于每一次杂交，父母中总有一个来自精英组中而另一个来自非精英组。然后，它产生一个后代的基因是来自精英组或非精英组的基因，由基于预先确定的概率确定。一般来说，这种概率设置更有利于从精英组中继承基因。杂交后代的数目取决于每个种群中的个体数和突变体的数量。
def crossover(self, elite, non_elite):
# 交叉操作，对于每一个基因都有一定的概率从精英组或者非精英组中进行选择
return [elite[gene] if np.random.uniform(low=0.0, high=1.0) < self.eliteCProb else non_elite[gene] for gene in
range(self.num_gene)]没有执行变异操作(例如交换变异)，而是在新一代中创建了随机生成的新个体，以此作为增加种群随机性的手段。确定种群变异个体的数目，定义一个函数来创建新的个体，就像初始化种群。
# 突变操作，没有在原本的基因的基础之上产生突变基因，而是产生新的个体插入到种群之中
def mutants(self):
return np.random.uniform(low=0.0, high=1.0, size=(self.num_mutants, self.num_gene))对于每一代，所有的精英组个体都被保留给下一个种群，不做任何修改。此外，变异产生的新个体直接添加到下一个种群中。由于这个问题是关于最小化使用的容器的数量，我们将在每一代更新最小适应值。我们可以将进化过程的函数定义为：
# 有偏的选择父辈其中包括一个来自精英组，另一个来自非精英组
def mating(self, elites, non_elites):
# 子代的数量取决于每个种群的个体的数量和突变体的数量
num_offspring = self.num_individuals - self.num_elites - self.num_mutants
return [self.crossover(random.choice(elites), random.choice(non_elites)) for i in range(num_offspring)]
# 进化过程：所有的精英组的个体都被保留到下一代种群中，在交叉和突变中产生的新的个体也保留到下一代种群中，评估每一代的适应度函数，保留最优值
def fit(self, patient=15, verbose=True):
# 初始化种群信息，进行编码，种群信息表示为在[0,1]范围之内矢量
population = np.random.uniform(low=0.0, high=1.0, size=(self.num_individuals, self.num_gene))
# 初始化适应度函数值
fitness_list = self.cal_fitness(population)
# 重复进行遗传迭代
best_iter = 0
for g in range(self.num_generations):
# 如果当前种群与最优种群满足一定条件，提前终止迭代，搜索结束
if g - best_iter > patient:
self.used_bins = math.floor(best_fitness)
self.best_fitness = best_fitness
self.solution = best_solution
if verbose:
print('提前停止迭代', g, '(结束搜索)')
return '有解'
# 选择精英组，非精英组，以及适应度函数
elites, non_elites, elite_fitness_list = self.partition(population, fitness_list)
# 有偏的进行交叉，产生后代新的个体
offsprings = self.mating(elites, non_elites)
# 进行变异产生后代中新的个体
mutants = self.mutants()
# 产生所有新的后代以及对应后代的适应度函数值
offspring = np.concatenate((mutants, offsprings), axis=0)
offspring_fitness_list = self.cal_fitness(offspring)
# 新的种群由所有的精英组和产生新的后代组成
population = np.concatenate((elites, offspring), axis=0)
fitness_list = list(elite_fitness_list) + list(offspring_fitness_list)
# 更新最优的适应度函数值
for fitness in fitness_list:
if fitness < best_fitness:
best_iter = g
best_fitness = fitness
best_solution = population[np.argmin(fitness_list)]如何评估一个解决方案的适应值（用函数计算适应度值)。一个解决方案告诉箱子打包顺序和摆放方向。为了评估每个解决方案的适应度函数，只需严格按照解决方案中提供的信息来打包这些箱子，然后计算使用了多少个容器。因此，需要一个按照解决方案将三维箱子包装到固定尺寸的容器。这个解决方案称为放置箱子程序。
首先，需要一个函数来反映箱子和容器的三维空间，同时判定重叠和越界。其次，必须定义一个函数来放置箱子。
# 1、在一个剩余可用空间中放置一个货物
boxToPlace = np.array(box)
# 在剩余可用空间中选择一个剩余可用空间
selected_min = np.array(selected_EMS[0])
# 计算货物在所选择的剩余可用空间中留下的最大空间
ems = [selected_min, selected_min + boxToPlace]
self.load_items.append(ems)最大空间是一个概念来表示一个矩形空间的最低限度和最大坐标，它只有在物体垂直于三维的情况下才起作用，因此适用于三维装箱问题。
通过记录容器中剩余的可用空间来记录箱子的放置情况的最大空间。随着使用空间管理，可以将容器中的盒子放置看作是以下过程：
1、在一个剩余可用空间中放置一个货物；
2、生成新的剩余可用空间，此由货物之间的交叉点产生；
3、消除掉完全被其他剩余可用空间包含的新产生的剩余可用空间；
4、新产生的剩余可用空间不能小于剩余货物的体积；
5、新产生的剩余可用空间尺寸不能小于剩余货物中最小的尺寸；
6、如果有效，则添加新的剩余可用空间。
在第二步，可以计算新的剩余空间。注意，在三维空间中有六个由交点产生的空间。然而，在实践中，将盒子的最小坐标相对于选定的扩展空间，因为两个盒子之间的间隙通常会导致不适合其他盒子的间隙。
# 相交的剩余可用空间最小和最大坐标
x1, y1, z1 = EMS[0]
x2, y2, z2 = EMS[1]
# 货物的最小和最大坐标
# x3, y3, z3 = ems[0]
x4, y4, z4 = ems[1]
# 三维空间下产生新的剩余可用空间
# new_EMSs = [
# [(x1, y1, z1), (x3, y2, z2)],
# [(x4, y1, z1), (x2, y2, z2)],
# [(x1, y1, z1), (x2, y3, z2)],
# [(x1, y4, z1), (x2, y2, z2)],
# [(x1, y1, z1), (x2, y2, z3)],
# [(x1, y1, z4), (x2, y2, z2)]
# ]
# 在实际中，把盒子的最小坐标与剩余可用空间相等，因为通常情况下两个货物之间留下的空隙难以放下新的货物
new_EMSs = [
[np.array((x4, y1, z1)), np.array((x2, y2, z2))],
[np.array((x1, y4, z1)), np.array((x2, y2, z2))],
[np.array((x1, y1, z4)), np.array((x2, y2, z2))]
]若要检查一个扩展空间重叠或完全被另一个扩展空间包含，可以定义以下函数来计算两个条件。
# 检查一个剩余可用空间是否与另一个剩余可用空间重叠
def overlapped(self, ems, EMS):
if np.all(ems[1] > EMS[0]) and np.all(ems[0] < EMS[1]):
return True
return False
# 检查一个剩余可用空间是否包含于另一个剩余可用空间之中
def inscribed(self, ems, EMS):
if np.all(EMS[0] <= ems[0]) and np.all(ems[1] <= EMS[1]):
return True
return False现在，有了一种方法来更新容器和盒子的状态，以及在每个盒子放置后的三维空间。接下来，介绍一个放置箱子启发式规则，以决定在一个箱子放置在哪个剩余空间中。
最深最左填充是一个打包一系列箱子的启发式规则，在这个规则中，它总是选择最小坐标的空间放置箱子。启发式算法的目标是在每次迭代中将盒子放置在最深的空间，希望最终所有的盒子都能紧密地放置在一起。但是一些最优解不能由这种启发式规则构造。为了解决这个问题，改进了放置箱子的启发式规则，规则命名为到容器右上角的距离最大化。该启发式算法总是将盒子放置在可用剩余可用空间中，使得盒子与容器的右上角的距离最大化。
# 启发式规则：与集装箱（货车）的前顶角距离
def DFTRC_2(self, box, k):
maxDist = -1
selectedEMS = None
for EMS in self.Bins[k].EMSs:
# D, W, H 是一个集装箱（货车）的深度、宽度、高度
D, W, H = self.Bins[k].dimensions
# 遍历货物的摆放状态
for direction in [1, 2, 3, 4, 5, 6]:
d, w, h = self.orient(box, direction)
# 如果货物满足当前的剩余可用空间
if self.fitin((d, w, h), EMS):
# 剩余可用空间的最小坐标
x, y, z = EMS[0]
# 剩余可用空间与集装箱（货车）距离
distance = pow(D - x - d, 2) + pow(W - y - w, 2) + pow(H - z - h, 2)
# 找到最大距离的剩余可用空间
if distance > maxDist:
maxDist = distance
selectedEMS = EMS
return selectedEMS该启发式规则用于选择一个扩展空间从现有的剩余可用空间用于放置箱子。如果箱子不能放置在现有的空间，将打开一个新的空容器，并恢复正在进行的放置过程。
所有箱子根据以上算法装入容器中，接下来需要定义一个函数计算解决方案的适应度值。可以将使用过的容器数作为解决方案的适应度值。但是如果两个解决方案使用的容器数相同，它们将得到相同的适应度值。因此需要将适应度值进行一个小的调整，附加了最小装填容器的正则项来修正。这种计算适应度值的基本原理是，如果两个解决方案使用的容器数相同，在未装满的容器中装载量较少的容器，在其他容器中箱子摆放的更加紧凑。因此，提升改进以此得到更好解的潜力更大。
"""
适应度函数：利用使用集装箱的数量进行计算
原理：如果两个方案使用了相同的数量的集装箱，以及产生了相同的适应度函数的值，在没有装满的货物里面如果货物数量最少，在满的的集装箱里是摆放的更加紧凑
"""
def evaluate(self):
if self.infisible:
return INFEASIBLE
leastLoad = 1
for k in range(self.num_opend_bins):
load = self.Bins[k].load()
if load < leastLoad:
leastLoad = load
return self.num_opend_bins + leastLoad % 1根据箱子的种类和个数的不同，考虑了参数的小数点后两位，箱子的摆放顺序（从内到外、从下到上）以及箱子的6种不同摆放状态，本方案分别测试得到对应情况的空间利用率，大约在70%左右，基于遗传算法本方案得到可行解的运行时间有一定的随机性，但是在数百秒时间范围之内给出可行解方案。
| 3种箱子情况 | 情况1 | 情况2 | 情况3 | 情况4 | 情况5 |
|---|---|---|---|---|---|
| 使用车厢数量 | 2 | 2 | 2 | 2 | 2 |
| 空间利用率 | 69.29% | 72.89% | 70.64% | 67.15% | 68.93% |
| 算法运行时间 | 369.62s | 159.82s | 77.46s | 337.01s | 795.94s |
| 5种箱子情况 | 情况1 | 情况2 | 情况3 | 情况4 | 情况5 |
|---|---|---|---|---|---|
| 使用车厢数量 | 2 | 2 | 2 | 2 | 2 |
| 空间利用率 | 70.63% | 73.97% | 71.26% | 74.57% | 65.36% |
| 算法运行时间 | 173.16s | 345.35s | 338.49s | 534.36s | 219.48s |
| 8种箱子情况 | 情况1 | 情况2 | 情况3 | 情况4 | 情况5 |
|---|---|---|---|---|---|
| 使用车厢数量 | 2 | 2 | 2 | 2 | 2 |
| 空间利用率 | 70.35% | 61.86% | 71.47% | 70.21% | 60.06% |
| 算法运行时间 | 339.08s | 452.30s | 406.52s | 359.21s | 785.09s |
| 10种箱子情况 | 情况1 | 情况2 | 情况3 | 情况4 | 情况5 |
|---|---|---|---|---|---|
| 使用车厢数量 | 2 | 2 | 2 | 2 | 2 |
| 空间利用率 | 78.37% | 62.98% | 66.26% | 62.43% | 64.83% |
| 算法运行时间 | 863.09s | 513.37s | 286.75s | 822.55s | 213.68s |
| 15种箱子情况 | 情况1 | 情况2 | 情况3 | 情况4 | 情况5 |
|---|---|---|---|---|---|
| 使用车厢数量 | 2 | 2 | 2 | 2 | 2 |
| 空间利用率 | 70.32% | 67.50% | 69.15% | 64.45% | 65.24% |
| 算法运行时间 | 292.62s | 820.53s | 684.23s | 233.05s | 887.86s |