基于fbs的空间进化算法的不等形面积布局优化研究-凯发娱乐官网

期刊菜单

基于fbs的空间进化算法的不等形面积布局优化研究
research on optimization of unequal area layout based on fbs spatial evolution algorithm

doi: , , html, ,
作者: , ：东北林业大学机电工程学院，黑龙江哈尔滨
关键词: ；；；；；；；

摘要: 多目标车间布局优化是现代制造业发展的必然趋势。通过综合考虑生产效率、成本控制、工作环境和员工满意度等多方面因素，制定科学合理的布局方案，将有助于提升企业的整体竞争力和可持续发展能力。然而，传统的多目标进化算法在布局优化凯发娱乐官网的解决方案的融合性和多样性方面面临着巨大的挑战。本文提出了一种基于柔性隔间结构的空间进化算法(isea)来求解具有多目标的设施布局问题。首先，创建了空间配置库，并使用进化操作(选择、交叉和变异)来产生新的配置，通过引入配置组半径d来控制isea中解的收敛性。其次，将最近和最远候选解方法与快速非主导排序相结合，选择帕累托最优解，以保证所得解的多样性。实验在8个不同的代表性实例和3个参数指标上进行了实验。与现有的moeas相比，isea能够找到更好的结果并具有更好的性能。数值实验验证了isea求解多目标布局优化问题的有效性。

abstract: multi-objective workshop layout optimization is the inevitable trend of the development of modern manufacturing industry. making a scientific and reasonable layout plan by comprehensively considering many factors such as production efficiency, cost control, working environment and employee satisfaction will help to enhance the overall competitiveness and sustainable development ability of enterprises. however, the traditional multi-objective evolutionary algorithm faces great challenges in the integration and diversity of layout optimization solutions. in this paper, a spatial evolution algorithm (isea) based on flexible compartment structure is proposed to solve the facility layout problem with multiple objectives. firstly, the spatial configuration library is created, and new configurations are generated by evolutionary operations (selection, crossover and mutation). the convergence of solutions in isea is controlled by introducing the radius d of configuration group. secondly, the nearest and farthest candidate solution method is combined with fast non-dominant sorting to select pareto optimal solution to ensure the diversity of the obtained solutions. experiments were carried out on 8 different representative examples and 3 parameters. compared with existing moeas, isea can find better results and has better performance. numerical experiments verify the effectiveness of isea in solving multi-objective layout optimization problems.

文章引用：郭小莹, 赵淑苹. 基于fbs的空间进化算法的不等形面积布局优化研究[j]. 计算机科学与应用, 2024, 14(10): 127-140.

1. 引言

布局优化问题为企业降低生产成本，提高企业竞争力的重要研究内容之一。许多学者提出了大量的算法来解决布局优化问题，主要包括：进化算法[1]、粒子群算法[2]、蚁群算法[3]、麻雀搜索算法[4]、头脑风暴优化算法[5]等。在这些算法中，基于ea的一类著名方法是所谓的多目标进化算法(moeas) [6]，适用于求解具有多目标的约束优化问题。palomo等[7]提出了一种岛模型遗传算法，该算法采用了种群并行进化的方法，并行方法有助于避免过早收敛和过多的执行时间，利用自适应惩罚函数将搜索过程引导到可行解区域。此外，该方法增加了搜索多样性，允许其探索更大的搜索空间，获得更好的凯发娱乐官网的解决方案。sa [8]是一种在复杂搜索空间问题中搜索全局最优的概率元启发式方法。针对传统过道布置鲜少考虑快速响应生产需求变化及加工产品组合的灵活性的不足，张则强等[9]构建了一种双目标动态过道布置问题数学模型，并提出了一种基于帕累托(pareto)最优的多目标改进猫群算法通过不同规模的算例验证了该算法的有效性和优越性。hunagund等[10]提出了模拟退火启发式算法来解决具有柔性间隔结构的不等面积动态设施布局问题，与其他的元启发算法相比，所提出的算法给出了新的最佳凯发娱乐官网的解决方案或相同的凯发娱乐官网的解决方案。

对于解决多目标不等面积设施布局问题(ua-flp)，另一个具有挑战性的问题是如何处理设施之间的非重叠约束。传统的求解方法通常采用放线策略[11]或惩罚函数[12]。然而，它们的性能并不总是令人满意的，因为放线方法限制了可能生成的布局的数量，并且很难找到适当的惩罚因子来引导搜索到约束最优解。柔性隔间结构(fbs) [10] [13]是一个连续的设施布局的表达式。根据fbs，布局区域被划分为几个平行的水平或垂直的隔间，即布局含走廊，符合大部分企业现状，因此，本文采用fbs方法，在处理有约束的ua-flp时消除了重叠，以得到可行的布局。

本文考虑了ua-flps的四个不同目标：(1) 材料处理成本的最小化；(2) 加权紧密度关系的满意度最大化；(3) 距离要求的最大化；(4) 设施高宽比满足需求。提出了一种新的moeas，即基于柔性隔间结构的空间进化算法(isea)，在isea算法中提出了一种基于配置(解)库的进化机制，该算法的收敛性由配置库半径控制，其值逐渐减小以缩小搜索空间。同时，结合基于目标函数归一化和非主导排序的最近和最远最优候选解方法，选择问题的帕累托最优解，能够在帕累托前沿得到良好的分布，并保持所得到的解的多样性。

2. 数学模型建立

本研究包含以下四个目标：

(1) 设施之间的材料处理成本最小化：

$minimize f_{1} (x) = \sum_{i} \sum_{j} (f_{i j} c_{i j}) d m_{i j}$ (1)

式中： $f_{i j}$ 表示设施i和设施j之间的物流量， $c_{i j}$ 为其单位距离移动成本，本文取 $c_{i j} = 1$ ， $d m_{i j}$ 是设施i和j之间的曼哈顿距离。

(2) 设施间的总加权接近关系应最大化：

$minimize f_{2} (x) = \sum_{i} \sum_{j} r_{i j} g_{i j}$ (2)

式中： $r_{i j}$ 是设施间的亲密程度， $g_{i j}$ 是设施与j之间的接触周长长度。

(3) 设施之间的距离最大化：

$minimize f_{3} (x) = \sum_{i} \sum_{j} s_{i j} d e_{i j}$ (3)

式中： $s_{i j}$ 是由设计者的需求与设施之间的环境关系决定的，一般主要考虑到相关环境问题，如振动、污染、噪音或与工人安全风险有关的方面。 $d e_{i j}$ 为欧氏距离。

(4) 高宽比也是一个约束，因为如果任何设施的高宽比超过其限制，任何凯发娱乐官网的解决方案都不可行。设施i的高宽比定义如下：

$r_{i} = \frac{\max (l_{i}, w_{i})}{\min (l_{i}, w_{i})}$ (4)

对于零间隙的设施，如果长宽比超过给定范围，则该设施的形状无法被接受，此时，该长宽比的满意度将降至0，零值意味着不可行的解，本文算例需满足设施的横纵比不超过4。

本研究包括以下约束条件：

(1) 设施之间不嵌入，如图1所示：

$i_{t i} \cap i_{t j} = ϕ$ (5)

(2) 设施i不能置于车间外，如图2所示：

$x_{t i} - 0.5 l_{t i} \geq 0$ (6)

$x_{t i} 0.5 l_{t i} \leq l$ (7)

$y_{t i} - 0.5 w_{t i} \geq 0$ (8)

$y_{t i} 0.5 w_{t i} \leq h$ (9)

3. 配置空间进化算法

3.1. 配置空间进化算法的框架

在本研究中，每个布局被视为由n个图元组成的染色体，每个图元由一个实数 $z_{i} (i = 1, 2, \dots, n)$ 编码，其中 $z_{i}$ 是1到 $(b 1)$ 之间的随机数，b是布局中的隔间总数。 $z_{i}$ 的整数部分表示设施所在的隔间，小数部分表示设施在同一隔间的放置顺序，较小的数字放在下面。在mo-sflp模型中，所有设施都是基于fbs结构从下到上、从左到右依次放置在平面中。图3显示了八个设施的flp布局。在图中，第一个设施的基因是3.67，这意味着该设施将被置于3区。在比较了第四个和第五个设施点的小数位数(3.74和3.49)后，设施点1将被置于该区域的中间。

figure 1. schematic diagram of embedding between facilities i and j

图1. 设施i和j之间的嵌入示意图

figure 2. schematic diagram of embedding facility i and workshop boundary

图2. 设施i与车间边界嵌入示意图

figure 3. layout map obtained from chromosomes

图3. 由染色体得到的布局图

配置空间进化算法步骤如表1所示。

table 1. configuration space evolution algorithm steps

表1. 配置空间进化算法步骤

step1：在算法开始时，我们在配置空间中随机生成 $k_{1} = 50$ 个可行配置(初始配置组p_init)。

step2：基于初始配置组中每个构型的中心，构造一个半径为 $d = d_{a v g} / 2$ 的圆形区域，每个配置的中心o(x,y)的计算方法如式(10)所示，其中d_avg为初始配置中所有构型中心之间欧氏距离的平均值。

$o (x, y) = (\frac{\sum_{i = 1}^{n} x_{i}}{n}, \frac{\sum_{i = 1}^{n} y_{i}}{n})$ (10)

step3：从配置库中随机选择k₂ = 10配置(种子配置库)。

step4：使用进化操作(选择、交叉和突变)生成k₃ = 200新配置(进化配置组)。

step5：使用快速非主导排序方法[14]和最近和最远的候选解方法从进化配置组进化中挑选出k₄ = 10的优秀配置。

step6：更新配置组p_new 50次。

step7：让d_space = d_space/2。

step8：如果p_new中仍然存在配置，则在他们中再随机选择k₂个构型作为种子构型。

step9：重复以上过程，不断迭代，直至配置库p_new中的所有构型都用作种子构型，这样，就完成了cse的一轮迭代。

step10：如果最大迭代次数没有达到，基于fbs随机产生50个新的可行配置p_init，并根据快速非支配排序方法和最近和最远的候选解方法，从p_new∪p_init中选择50个适应度值较好的配置来重置新的初始配置库。

step11：重复整个过程，直到达到最大的迭代次数为止。

step12：然后，使用快速非支配排序方法和多属性决策方法选择几个优秀的配置作为问题的帕累托最优解集。

3.2. 生产的配置的进化

(1) 选择。本文取精英率为k_elite = 0.2，被精英策略所选择的个数是：

$n_{e l i t e} = n_{s e e d} \times k_{e l i t e}$ (11)

其中，n_seed表示p_seed中的个体数量。

(2) 交叉。连续均匀交叉操作被应用于种子配置库p_seed。种子配置库p_seed和新配置库p_new被选为交叉操作的父配置。常见的交叉方法有单点交叉(opc)和多点交叉(mpc)。cse算法中简单的单点交叉或多点交叉方法，在算法前期不能很好地探索解的多样性。此外，算法迭代中每个交叉模式都以随机概率出现，不利于提高算法搜索解空间的能力。为此，提出了一种混合交叉策略，包括单点交叉、多点交叉和算术交叉(ac)。同时，设计了交叉模式的动态权重计算方法，在每次迭代中，根据权重概率选择一种模式进行交叉操作。

首先，引入算术交叉。随机数 $a_{i} = (a_{1}, a_{2}, a_{3}, \dots, a_{n})$ 在(0, 1)区间生成，其中n是车间中设施的数量。假设有两个亲本 $x_{1 i}$ 和 $x_{2 i}$ ，它们对应的随机数都是 $a_{i}$ ，那么交叉操作后的后代可以表示为公式(12)和公式(13)。以五个设施为例，算术交叉的结果如表2所示。

$x_{1 i}^{;} = a_{i} x_{1 i} (1 - a_{i} x_{2 i}), \forall_{i} = 1, 2, \dots, n$ (12)

$x_{2 i}^{;} = (1 - a_{i}) x_{1 i} a_{i} x_{2 i}, \forall_{i} = 1, 2, \dots, n$ (13)

table 2. arithmetic crossover operation

表2. 算术交叉运算

parent 1	parent 2	random values	child 1	child 2
1.23	2.54	0.26	2.20	1.57
1.54	3.21	0.12	3.01	1.74
2.09	2.87	0.53	2.46	2.50
2.89	4.65	0.22	4.26	3.28
4.51	1.08	0.12	1.49	4.10

当算法开始迭代时，单点交叉、多点交叉和算术交叉的初始权重设置为p_opc、p_mpc和p_ac = 0.3、0.3和0.4。一次迭代后，p_opc、p_mpc和p_ac更新为单点交叉、多点交叉和算术交叉产生的个体数与三种交叉方式产生的总个体数的比值，这个权重作为下一次迭代中各种交叉方式出现的概率。因此，一次迭代中交叉操作产生的个体数为：

$n_{o p c} = 2 \times k_{i n i t} \times p_{s e e d} \times p_{o p c}$ (14)

$n_{m p c} = 2 \times k_{i n i t} \times p_{s e e d} \times p_{m p c}$ (15)

$n_{a x} = 2 \times k_{i n i t} \times p_{s e e d} \times p_{a x}$ (16)

$n_{o p c} = 1 - p_{m p c} - p_{a x}$ (17)

(3) 变异。对通过选择和交叉得到的构型进行快速非主导排序，对快速非主导排序后的构型进行突变，通过突变概率k_mutate随机选择一个基因，然后用1到b 1之间的随机数替换，结果如下：

${z^{'}}_{i} = {\begin{cases} z_{i} ((b 1) - z_{i}) \tanh (k u), if \tanh (k u) \geq 0 \\ z_{i} (z_{i} - 1) \tanh (k u), else \end{cases}$ (18)

其中，z_i是随机选择的基因的值，u为标准正态分布随机数，k为其系数。

3.3. 最近最远候选解法

本文用最近最远候选解法来维持解的分布，给定候选解集c，其中包含p个非支配个体，从c中选择q个帕累托最优解，得到一个最优解集a。首先，计算所有目标函数值 $f_{i} (x_{j})$ ，求集合c中每个解 $x_{j} (j = 1, 2, \dots, p)$ 的最小值，其中m为目标函数的个数。有两种情况：

(1) 如果 $q < m$ ，根据不同目标的偏好，随机选择目标函数值最小的q个解到集合a中，并将候选解集c中的q个解从c中删除。

(2) 如果 $q \geq m$ ，对于每个目标，选择一个目标值最小的解，并将其放入a中；同时将其从c剩下的u (等于q − m)个个体从更新后的候选解集c中选择。对于此时c中的每个解 $x_{s} (| c | = u)$ ，计算x_s与最优解集a中的所有个体之间的最近距离。选择距离c最远解x_far，将其加入最优解集a中，然后从集合中删除c。重复上述操作，直到集合a中的解数达到q。

在最近和最远的候选解方法中，对于两个解x_s和x_t，需要定义一种基于目标函数的距离计算方法，将这些目标函数进行归一化处理，解x_s和x_t之间的距离的计算方法为：

$distance (x_{s}, x_{t}) = \sqrt{\sum_{i = 1}^{m} {({\vec{f}}_{i} (x_{s}) - {\vec{f}}_{i} (x_{t}))}^{2}}$ (19)

其中， ${\vec{f}}_{i} (x)$ 为归一化后的目标函数值。

3.4. 更新配置库

对于每个新的测试配置t，计算它与配置库p_new中的每个配置之间的欧氏距离，选择距离最近的配置，用y命名。配置t和y之间的距离用d (t, y)表示。cse在配置空间中的搜索过程如图4所示。

(1) 如果d (t, y) ≤ d_space，t在以y为中心的圆内，这意味着这两种构型是相似的。如果t优于y，我们将t添加到配置库p_new中，并从p_new中删除配置y，使p_new中的配置总数保持不变。圆心从y的圆心移动到t的圆心。如果y优于t，我们保持y并放弃构型t。如果配置t和y不相互优于，我们从t和y中随机选择一个来更新配置库。当选择t时，圆心移到t的圆心。

(2) 如果d (t, y) > d_space，则测试配置t落在所有现有的圆圈之外。如果t在p_new中优于某个配置z，我们从p_new中删除z，并将t添加到配置库p_new中。圆心从z的圆心移动到t的圆心。如果t在p_new中不优于其他的任何配置，则配置t将被删除。

figure 4. search process of cse in configuration space

图4. cse在配置空间中的搜索过程

3.5. 目标函数归一化

本文使用了nsga-iii [15]中目标函数的归一化方法。首先，计算候选解集c中每个目标函数 $f_{i} (i = 1, 2, \dots, m)$ 的最小目标值 $g_{1}^{\min}$ ，然后构造理想点集g,目标值表示为：

${f^{'}}_{i} (x) = f_{i} (x) - g_{1}^{\min}$ (20)

其中：x是n个设施的布局，即一个配置。函数asf (由 ${f^{'}}_{i} (x)$ 和接近第i个轴方向的权重向量w组成)最小：

$asf (x, w) = \max_{i = 1}^{m} \frac{{f^{'}}_{i} (x)}{w_{i}}$ (21)

其中，设置目标向量 $f_{i} (i = l)$ 的权重为1，对于其余目标向量 $f_{i} (i \neq l)$ 设置 $w_{i} = 0$ (本文用一个小的数字10⁻⁶替换)，目标函数可以用公式(22)进行归一化：

${\vec{f}}_{i} (x) = \frac{{f^{'}}_{i} (x)}{a_{i}}, i = 1, 2, \dots, m$ (22)

4. 配置空间进化算法性能测试

4.1. 实例验证

为了评估isea算法的性能，选取了外文文献中出现频率较高的8个测试实例进行实验。分别被gonçalve [16]，bozer [17]，ulutas [18]等学者引用，参数值如表3所示，实例来源见表4，为了避免随机效应，每个实例被独立地执行了10次。由不同算法imbo [19]、isa [20]、nsga-ii [21]对不同设施数目的算例结果比较见表5。在此列举案例1和案例8中的三个目标函数的迭代过程，如图5和图6所示。采用isea方法得到的最佳染色体见表6。案例1和案例8的最优解布局如图7所示。

table 3. parameter values of isea

表3. isea参数值

参数	值	参数	值
初始配置大小(k₁)	50	交叉概率(k_cross)	0.7
种子配置大小(k₂)	10	突变概率(k_mutate)	0.2
演化配置大小(k₃)	200	d_space的更新频率	0.5
测试配置大小(k₄)	10	物轴权重(w_i)	10⁻⁶
精英率(k_elite)	0.2

table 4. test set and instance information table

表4. 测试案例信息表

实例	设施数量	面积规格	数据来源
1	9	12.00 * 13.00	meller et al. (1998) [22]
2	10	25.00 * 51.00	van camp et al. (1992) [23]
3	14	6.00 * 8.00	komarudin and wong (2010) [24]
4	20	20.00 * 30.00	armour and buffa (1963) [25]
5	30	12.00 * 15.00	liu and meller (2007) [26]
6	35	16.00 * 15.00	liu and meller (2007) [26]
7	62	140.00 * 100.00	dunker et al. (2003) [27]
8	20	25.00 * 15.20	aiello et al. (2012) [28]

table 5. comparison of calculation results of different algorithms for different facilities

表5. 不同算法对不同设施数目的算例结果比较

实例	算法	f₁(x) (min)			f₂(x) (max)			f₃(x) (max)			时间(s)
实例	算法	最值	平均值	标准差	最值	平均值	标准差	最值	平均值	标准差	时间(s)
1	isea	217.61	231.21	12.09	255.72	180.90	27.61	931.6	907.07	48.357	4312
	imbo	219.71	234.26	10.01	241.21	199.25	33.59	925.26	874.22	51.04	4218
	isa	233.85	257.58	11.58	233.13	189.75	30.55	885.42	766.28	59.47	4759
	nsga-ii	259.42	274.33	15.72	183.73	162.13	22.04	810.34	722.76	47.38	5145
2	isea	19267.21	24586.75	2475.42	776.25	663.47	109.48	3876.15	3243.58	304.21	4087
	imbo	26758.68	26425.47	2954.48	710.48	648.54	112.12	3775.99	3114.84	376.48	4437
	isa	23545.25	28755.11	3041.23	778.94	642.16	115.18	3654.28	3048.75	300.44	4159
	nsga-ii	27485.47	31758.47	2458.39	686.10	602.14	135.48	3314.76	3185.41	385.18	4972
3	isea	3547.28	4037.39	876.14	375.15	304.48	41.26	678.49	607.15	50.17	5143
	imbo	3649.14	4235.67	904.28	348.64	398.41	47.75	684.28	610.43	55.61	5318
	isa	3884.17	4473.19	947.24	368.19	401.72	47.18	637.14	587.24	53.48	5247
	nsga-ii	4137.84	4976.28	847.57	271.43	223.97	51.34	554.27	500.47	63.43	6148
4	isea	6842.55	7351.25	824.27	99.25	68.14	5.64	925.14	856.22	42.06	6257
	imbo	7254.58	7964.58	1102.65	80.10	65.10	7.82	875.56	826.91	49.76	6425
	isa	7822.73	8532.74	1017.28	64.13	40.10	8.84	801.07	743.94	44.07	6294
	nsga-ii	8103.85	8663.48	1304.27	54.21	38.47	8.89	694.57	634.27	52.17	7318
5	isea	5863.57	6484.28	387.47	601.42	527.39	25.34	18471.35	17542.34	607.42	6872
	imbo	6524.55	6647.21	375.82	576.40	497.89	22.41	17842.34	16899.21	635.95	6941
	isa	6758.25	7614.27	476.21	510.81	490.58	22.18	17058.75	16624.63	690.41	7210
	nsga-ii	7024.64	8014.87	489.34	488.14	441.19	28.17	15453.27	13247.58	742.36	7627
6	isea	7104.41	7853.24	8214.07	804.52	721.08	32.15	34518.34	29756.48	930.47	6749
	imbo	7715.36	8142.84	884.31	746.31	723.15	33.17	33142.15	29452.24	933.48	6793
	isa	7651.25	8814.58	865.23	754.90	695.24	35.21	33845.42	29675.36	921.65	6972
	nsga-ii	8242.36	10452.74	1104.29	704.52	612.45	49.28	30147.58	27954.46	1286.43	7610
7	isea	3458753.53	3578566.10	45967.44	6102.84	5847.22	194.38	394587.72	359784.61	12052.47	14357
	imbo	3758569.41	3854256.81	52463.48	5904.27	5526.45	259.15	365624.44	347672.23	13059.46	14972
	isa	3847559.24	3978542.58	53478.28	5437.94	5075.48	254.78	378459.74	357841.28	13475.92	15349
	nsga-ii	4014672.65	4157869.85	58647.54	4883.45	4573.75	297.35	334751.67	324785.94	15347.95	177341
8	isea	99.42	102.53	5.48	154.20	136.57	10.58	538.62	465.21	20.14	2458
	imbo	108.51	115.34	6.85	154.83	124.75	14.28	531.47	451.87	25.43	2735
	isa	115.60	126.84	4.77	147.25	112.31	17.02	486.44	427.25	23.11	2689
	nsga-ii	158.73	174.59	6.21	106.12	110.74	24.28	449.21	409.14	27.59	3547

从表5的结果可以看出，10个测试案例使用cse算法得到的3个目标的最优值与文献中的nsga-ii，imbo和isa的最佳结果相比都取得了令人满意的结果，实例8中，使用isea的物料搬运成本比传统的nsga-ii得到的结果降低了37.36%，亲密关系增加了45.31%，距离增加了19.90%。说明该启发式算法具有良好的稳定性和良好的收敛性。除此之外从8个案例可以看出，设施数量越多，isea找到最佳凯发娱乐官网的解决方案所需的时间越长，所提出的isea算法在较少的迭代中获得了更好的凯发娱乐官网的解决方案，证明了isea的有效性。

4.2. 性能指标

此外，还设计了对比实验来测试和验证这些参数在isea中的效果。isea中的测试参数包括初始配

figure 5. iterative process of three objective functions in case 1

图5. 案例1中三个目标函数迭代过程

figure 6. iterative process of three objective functions in case 8

图6. 案例8中三个目标函数迭代过程

table 6. the best chromosomes obtained by isea

表6. 采用isea方法得到的最佳染色体

算例	染色体编码
1	{2.21, 1.86, 1.97, 2.59, 1.17, 1.54, 2.88, 2.11, 1.32}
2	{2.73, 3.42, 3.77, 3.35, 2.41, 3.54, 2.15, 1.33, 2.81, 1.42}
3	{4.68, 1.57, 2.87, 1.37, 3.30, 3.51, 2.28, 1.98, 2.51, 4.10, 4.30, 4.63，2.46，3.47}
4	{2.9, 1.6, 1.7, 1.3, 5.0, 3.4, 3.1, 2.0, 3.6, 2.7, 6.2, 6.0, 3.9, 3.8, 5.6, 4.7, 4.5, 5.3, 6.1, 2.3}
5	{6.04, 5.17, 5.58, 4.61, 4.32, 5.48, 7.85, 7.51, 6.63, 6.52, 7.18, 8.62, 4.89, 6.80, 1.57, 2.79, 5.93, 3.47, 8.74, 3.37, 5.74, 8.97, 3.64, 2.13, 2.72, 1.13, 7.66, 1.41, 2.48}
6	{2.33, 4.79, 4.93, 4.82, 1.42, 4.73, 1.79, 2.47, 3.42, 3.79, 1.31, 3.31, 3.47, 6.34, 5.46, 5.55, 4.97, 3.74, 3.53, 3.62, 2.13, 6.51, 6.83, 1.81, 6.27, 6.72, 2.59, 6.13, 1.59, 1.63, 5.14, 5.33, 2.73, 1.72, 4.41}
7	{1.66, 6.89, 3.68, 1.15, 4.15, 1.94, 2.93, 6.73, 2.11, 4.57, 3.41, 5.71, 3.49, 3.71, 5.27, 5.38, 6.84, 6.68, 6.09, 2.50, 1.55, 1.73, 2.23, 3.10, 4.48, 4.77, 3.36, 4.66, 6.14, 3.25, 6.35, 4.29, 5.18, 4.04, 1.91, 5.74, 6.61, 2.38, 2.14, 1.49, 1.51, 1.88, 6.81, 3.55, 2.84, 1.04, 5.74, 4.92, 2.28, 2.47, 4.26, 5.51, 2.72, 3.18, 4.19, 2.69, 3.88, 6.30, 3.21, 5.11, 4.33, 5.90}
8	{6.3, 2.6, 5.9, 3.1, 2.0, 3.8, 3.7, 3.3, 5.3, 5.1, 4.8, 4.6, 1.3, 3.0, 4.2, 6.1, 1.8, 1.5, 2.5, 5.7}

figure 7. the optimal solution layout of case 1(a) and case 8(b) obtained by isea

图7. 案例1(a)、案例8(b)由isea得到的最优解布局图

table 7. when w_i = 10⁻⁶, d_space = d_space/2, the obtained calculation results of different initial configurations k_i

表7. 当w_i = 10⁻⁶，d_space = d_space/2时，不同的初始配置k_i得到的计算结果

实例	k₁	f₁(x) (min)			f₂(x) (max)			f₃(x) (max)			时间(s)
实例	k₁	最值	平均值	标准差	最值	平均值	标准差	最值	平均值	标准差	时间(s)
1	20	228.62	245.21	17.25	223.54	156.65	34.586	913.55	867.07	54.684	1405
	50	217.61	231.21	12.09	255.72	180.90	27.615	931.60	907.07	48.357	2485
	100	215.60	234.74	10.62	251.46	145.75	28.994	931.60	872.11	37.102	3947
	200	215.60	238.05	14.47	251.33	159.08	22.353	931.60	870.65	52.454	5856
8	20	5048.58	5172.57	501.82	211.44	175.16	13.875	3297	2778	175.485	5987
	50	4729.74	5099.24	478.56	223.47	199.45	11.985	3329	2759	169.877	8548
	100	4729.74	5098.06	483.74	223.47	145.85	12.587	3329	2718	171.528	9145
	200	4729.74	5084.48	497.17	223.47	187.52	13.157	3329	2732	173.548	11,258

table 8. when k₁ = 50, d_space = d_space/2, the obtained calculation results with different weights w_i

表8. 当k₁ = 50，d_space = d_space/2时，不同的权重w_i得到的计算结果

实例	w_i	f₁(x) (min)			f₂(x) (max)			f₃(x) (max)			时间(s)
实例	w_i	最值	平均值	标准差	最值	平均值	标准差	最值	平均值	标准差	时间(s)
1	10⁻⁵	217.61	246.52	12.86	255.72	180.21	27.785	931.60	902.57	48.875	2468
	10⁻⁶	217.61	242.66	12.04	255.72	180.84	27.658	931.60	909.45	48.358	2485
	10⁻⁷	217.61	244.86	12.75	255.72	180.65	27.765	931.60	904.58	48.758	2538
	10⁻⁸	217.61	239.58	12.58	255.72	180.36	27.702	931.60	907.44	48.985	2529
8	10⁻⁵	4730.01	5132.25	497.82	214.62	185.85	12.874	3321	2617	173.358	8087
	10⁻⁶	4729.74	5099.24	478.56	223.47	195.45	11.911	3329	2778	169.877	8548
	10⁻⁷	4929.98	5078.41	475.25	221.35	188.82	13.015	3324	2754	170.369	9058
	10⁻⁸	4730.38	5184.35	509.74	211.45	177.17	13.458	3316	2628	174.523	10,456

table 9. when k₁ = 50, w_i = 10⁻⁶, the obtained calculation results of different weights w_i

表9. 当 k₁ = 50，w_i = 10⁻⁶时，不同的权重w_i得到的计算结果

实例	d_space	f₁(x) (min)			f₂(x) (max)			f₃(x) (max)			时间(s)
实例	d_space	最值	平均值	标准差	最值	平均值	标准差	最值	平均值	标准差	时间(s)
1	2/3	217.61	243.45	12.88	255.72	181.33	27.687	931.60	908.01	48.901	2578
	1/2	217.61	243.26	12.04	255.72	180.84	27.658	931.60	909.45	48.358	2385
	1/3	217.61	245.36	12.37	255.72	175.64	27.821	931.60	913.44	48.621	2256
	1/5	217.61	248.58	12.95	255.72	171.42	27.944	931.60	905.71	49.874	2017
8	2/3	4729.74	5162.51	500.41	223.47	193.75	19.243	3329	2483	177.258	10,058
	1/2	4729.74	5099.24	478.56	223.47	195.22	11.911	3329	2578	169.456	8548
	1/3	4787.66	5240.25	488.22	220.65	193.23	16.485	3301	2575	172.520	8421
	1/5	4837.52	5133.45	588.28	209.52	189.57	12.875	3277	2581	188.102	8210

置k₁、权重w_i和d_space的更新频率。为了检验参数对实验结果的影响，选择一些有代表性的值来试验每个参数对解的影响。将最大迭代次数设置为3000次，以确保算法达到收敛性，并能得到每个目标的最优解。该算法对两个实例的每个参数独立运行10次，结果如表7~9。

从表7可以看出，对于两个实例，当初始配置的数量k₁分别设置为50、100和200时，所有目标的最优值、平均值和标准差都略有不同。但随着k₁的增加，平均运行时间也会增加。当k₁为20时，其结果比其他值的结果要差。对于进化算法，初始构型的产生是很重要的，因为后续的交叉和突变都是基于进化和更新的初始构型。当k₁为20时，算法容易过早收敛，获得最优解的概率较低。当k₁为100或200时，虽然初始配置的多样性增加了，但结果并没有好转，而且运行时间也大大增加了。总的来说，当k₁为50时，算法的结果略优于其他k₁值时的结果。

由表8可知，w_i的变化对两个实例的结果影响不大。但总的来说，当w_i为10⁻⁶时，算法的结果略优于其他w_i值的算法。对于实例1和2，可以看到，虽然这两个实例的所有目标的最佳值、平均值和标准差对不同的不同参数差异很小，如w_i的减少，因为精度逐渐提高，算法的运行时间也相应延长。

从表9中可以看出，对于数量较少的算例1，当更新频率变化时，三个目标的最佳值、平均值、标准差和平均运行时间都相似。对于较大的算例2，当d_space分别为2/3、1/2和1/3，所得到的三个目标的最优值相似。然而，当d_space为2/3时，算法的运行时间相对较长。当d_space为1/5时，算法结果略比其他三个更新频率差。当d_space为2/3，解空间收缩缓慢，导致算法收敛缓慢，使算法的运行时间更长。相反当d_space为1/5，解空间无需完全更新就会迅速缩小，使算法容易过早收敛，导致运行时间变短，结果变得更差。

测试实例的实验结果说明了isea中参数设置的有效性。为了使算法能够有效地找到帕累托最优解，通常可以将参数设置在一定范围内。

5. 结论

对于多目标设施布局优化，gas所采用的多目标算法(如moga，nsga-ii)是目前最有前途和研究最广泛的研究领域之一。这些方法能够找到一组帕累托最优布局，在整个进化过程中同时优化多个目标函数，给决策者一个有限数量的凯发娱乐官网的解决方案，其中人们可以选择其认为最好的凯发娱乐官网的解决方案。本文提出的基于柔性隔间结构的空间进化算法(isea)可以有效地搜索解空间，找到良好的解分布，以求解具有多目标的静态设施布局优化。在8个典型案例上的实验结果表明，所提出的isea算法是求解多目标布局优化的一种有效的算法。

致谢

桃李不言，下自成蹊。首先感谢我的导师，知识渊博，为学严谨认真，待人和蔼可亲，是我的良师益友，人生之幸，得遇良师。其次，衷心感谢在百忙之中抽出时间来审阅本文的各位老师和专家。我对所有帮助与支持我的人表示由衷的感谢。

参考文献

[1]	garcía-hernández, l., palomo-romero, j.m., salas-morera, l., arauzo-azofra, a. and pierreval, h. (2015) a novel hybrid evolutionary approach for capturing decision maker knowledge into the unequal area facility layout problem. expert systems with applications, 42, 4697-4708.
[2]	muhayat, h. and utamima, a. (2024) solving unequal area facility layout problems with differential evolution and particle swarm optimization. procedia computer science, 234, 302-309.
[3]	lin, j., shen, a., wu, l. and zhong, y. (2023) learning-based simulated annealing algorithm for unequal area facility layout problem. soft computing, 28, 5667-5682.
[4]	bi, s., shao, l., zheng, j. and yang, r. (2024) workshop layout optimization method based on sparrow search algorithm: a new approach. journal of industrial and production engineering, 41, 324-343.
[5]	zuniga, e.r., moris, m.u., syberfeldt, a., fathi, m. and rubio-romero, j.c. (2020) a simulation-based optimization methodology for facility layout design in manufacturing. ieee access, 8, 163818-163828.
[6]	高贵兵, 岳文辉, 张道兵. 基于模糊决策与进化算法的生产设备布局优化[j]. 计算机工程与应用, 2017, 53(17): 241-248.
[7]	palomo-romero, j.m., salas-morera, l. and garcía-hernández, l. (2017) an island model genetic algorithm for unequal area facility layout problems. expert systems with applications, 68, 151-162.
[8]	郭轶男, 姜雪松, 张宇晨, 等. 基于sa-qpso算法的多层制造单元内部布局方法[j]. 中国新技术新产品, 2024(5): 5-8.
[9]	张则强, 赵敏捷, 刘思璐, 等. 面向智能车间的动态过道布置问题建模与优化[j]. 华中科技大学学报(自然科学版), 2024, 52(6): 17-23 101.
[10]	hunagund, i.b., madhusudanan pillai, v. and kempaiah, u.n. (2018) a simulated annealing algorithm for unequal area dynamic facility layout problems with flexible bay structure. international journal of industrial engineering computations, 9, 307-330.
[11]	vitayasak, s., pongcharoen, p. and hicks, c. (2017) a tool for solving stochastic dynamic facility layout problems with stochastic demand using either a genetic algorithm or modified backtracking search algorithm. international journal of production economics, 190, 146-157.
[12]	姚明钊, 陈鹏飞, 裴小兵. 基于slp和改进遗传算法优化c企业车间布局[j]. 有色金属工程, 2023, 13(9): 99-109.
[13]	曾强, 陈永锋, 袁瑞甫, 等. 基于iaga的多行设施布局优化方法[j]. 机床与液压, 2024, 52(3): 106-112.
[14]	singh, d. and ingole, s. (2019) multi-objective facility layout problems using bbo, nsbbo and nsga-ii metaheuristic algorithms. international journal of industrial engineering computations, 10, 239-262.
[15]	jain, h. and deb, k. (2014) an evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part ii: handling constraints and extending to an adaptive approach. ieee transactions on evolutionary computation, 18, 602-622.
[16]	gonçalves, j.f. and resende, m.g.c. (2015) a biased random-key genetic algorithm for the unequal area facility layout problem. european journal of operational research, 246, 86-107.
[17]	bozer, y.a. and wang, c. (2012) a graph-pair representation and mip-model-based heuristic for the unequal-area facility layout problem. european journal of operational research, 218, 382-391.
[18]	haktanirlar ulutas, b. and kulturel-konak, s. (2012) an artificial immune system based algorithm to solve unequal area facility layout problem. expert systems with applications, 39, 5384-5395.
[19]	张思奇, 于登辉, 郑一明, 等. 改进候鸟迁徙算法的车间布局优化[j]. 机械设计与制造, 2024, 399(5): 369-374.
[20]	卢义桢, 李西兴, 朱传军, 等. 基于自适应遗传模拟退火算法的多目标车间布局优化[j]. 制造技术与机床, 2022(7): 173-179.
[21]	童锡宇, 郑路, 杨金昌, 等. 基于服装吊挂系统协同的车间混合流水线布局优化[j]. 纺织学报, 2024, 45(3): 169-176.
[22]	meller, r.d., narayanan, v. and vance, p.h. (1998) optimal facility layout design. operations research letters, 23, 117-127.
[23]	van camp, d.j., carter, m.w. and vannelli, a. (1992) a nonlinear optimization approach for solving facility layout problems. european journal of operational research, 57, 174-189.
[24]	kulturel-konak, s. and konak, a. (2011) a new relaxed flexible bay structure representation and particle swarm optimization for the unequal area facility layout problem. engineering optimization, 43, 1263-1287.
[25]	allahyari, m.z. and azab, a. (2018) mathematical modeling and multi-start search simulated annealing for unequal-area facility layout problem. expert systems with applications, 91, 46-62.
[26]	liu, j. and li, g. (2010) basin filling algorithm for the circular packing problem with equilibrium behavioral constraints. science china information sciences, 53, 885-895.
[27]	dunker, t., radons, g. and westkämper, e. (2003) a coevolutionary algorithm for a facility layout problem. international journal of production research, 41, 3479-3500.
[28]	aiello, g., la scalia, g. and enea, m. (2012) a multi objective genetic algorithm for the facility layout problem based upon slicing structure encoding. expert systems with applications, 39, 10352-10358.

为你推荐

凯发娱乐官网的友情链接