文章目录

• 一、理论基础
• • 1、供需优化算法
  • • （1）SDO算法初始化
    • （2）商品均衡数量与均衡价格
    • （3）供给函数和需求函数
  • 2、SDO算法伪代码
• 二、仿真实验与分析
• • 1、函数测试与数值分析
  • 2、求解焊接梁设计优化问题
  • 3、WSN覆盖优化
• 三、参考文献

一、理论基础

1、供需优化算法

供需优化(Supply-demand-based optimization, SDO)算法是Zhao等于2019年受经济学供需机制的启发而提出的一种新型元启发式优化算法。该算法在数学上模拟了消费者的需求关系和生产者的供给关系，通过将供求机制之稳定模式和非稳定模式引入到SDO算法中，利用两种模式在给定空间中进行局部搜索和全局搜索求解待优化问题。与传统群智能算法相比，SDO算法收敛速度快、寻优精度高、调节参数少，具有较好的探索和开发能力。

（1）SDO算法初始化

假设有 n n n个市场，每个市场有 d d d种不同的商品，每种商品都有一定的数量和价格。市场中 d d d种商品价格表示优化问题 d d d维变量的一组候选解，同时将市场中d种商品数量作为一组可行解进行评估，如果可行解优于候选解，则可行解替换候选解。 n n n个市场商品价格和商品数量分别用 X X X、 Y Y Y两个矩阵表： X = [ x 1 x 2 ⋮ x n ] = [ x 1 1 x 1 2 ⋯ ⋯ x 1 d x 2 1 x 2 2 ⋯ ⋯ x 2 d ⋮ ⋮ ⋮ ⋮ ⋮ x n 1 x n 2 ⋯ ⋯ x n d ] (1) X=\begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix}=\begin{bmatrix} x_{1}^1 & x_{1}^2 & \cdots & \cdots & x_{1}^d \\x_{2}^1 & x_{2}^2 & \cdots & \cdots & x_{2}^d\\\vdots & \vdots & \vdots & \vdots & \vdots\\x_{n}^1 & x_{n}^2 & \cdots & \cdots & x_{n}^d \\\end{bmatrix}\tag{1} X=⎣⎢⎢⎢⎡​x1​x2​⋮xn​​⎦⎥⎥⎥⎤​=⎣⎢⎢⎢⎡​x11​x21​⋮xn1​​x12​x22​⋮xn2​​⋯⋯⋮⋯​⋯⋯⋮⋯​x1d​x2d​⋮xnd​​⎦⎥⎥⎥⎤​(1) Y = [ y 1 y 2 ⋮ y n ] = [ y 1 1 y 1 2 ⋯ ⋯ y 1 d y 2 1 y 2 2 ⋯ ⋯ y 2 d ⋮ ⋮ ⋮ ⋮ ⋮ y n 1 y n 2 ⋯ ⋯ y n d ] (2) Y=\begin{bmatrix}y_1\\y_2\\\vdots\\y_n\end{bmatrix}=\begin{bmatrix} y_{1}^1 & y_{1}^2 & \cdots & \cdots & y_{1}^d \\y_{2}^1 & y_{2}^2 & \cdots & \cdots & y_{2}^d\\\vdots & \vdots & \vdots & \vdots & \vdots\\y_{n}^1 & y_{n}^2 & \cdots & \cdots & y_{n}^d \\\end{bmatrix}\tag{2} Y=⎣⎢⎢⎢⎡​y1​y2​⋮yn​​⎦⎥⎥⎥⎤​=⎣⎢⎢⎢⎡​y11​y21​⋮yn1​​y12​y22​⋮yn2​​⋯⋯⋮⋯​⋯⋯⋮⋯​y1d​y2d​⋮ynd​​⎦⎥⎥⎥⎤​(2)其中， x i x_i xi​和 y i y_i yi​分别为第 i i i个商品的价格和数量； x i j x_i^j xij​和 y i j y_i^j yij​分别为第 j j j个商品在第 i i i个市场中的价格和数量。
利用适应度函数分别对每个市场中的商品价格和数量进行评估，对于 n n n个市场，商品价格的适应度为： F x = [ F x 1    F x 2    ⋯    F x n ] T (3) F_x=[F_{x_1}\,\,F_{x_2}\,\,\cdots\,\,F_{x_n}]^T\tag{3} Fx​=[Fx1​​Fx2​​⋯Fxn​​]T(3)商品数量的适应度为： F y = [ F y 1    F y 2    ⋯    F y n ] T (4) F_y=[F_{y_1}\,\,F_{y_2}\,\,\cdots\,\,F_{y_n}]^T\tag{4} Fy​=[Fy1​​Fy2​​⋯Fyn​​]T(4)

（2）商品均衡数量与均衡价格

假设每种商品的均衡价格 x 0 x_0 x0​和均衡数量 y 0 y_0 y0​在每次迭代过程中都是可变的，从每个市场商品数量集合中选择一种商品数量作为其数量均衡向量，其市场适应度值越大，表示每个市场所选商品数量的概率就越大。同时，每个市场也可以根据其概率从商品价格集合中选择一种商品价格或以所有市场商品价格的平均值作为均衡价格。商品均衡数量 y 0 y_0 y0​表示如下： N i = ∣ F y i − 1 n ∑ i = 1 n F y i ∣ (5) N_i=\left|F_{y_i}-\frac1n\sum_{i=1}^nF_{y_i}\right|\tag{5} Ni​=∣∣∣∣∣​Fyi​​−n1​i=1∑n​Fyi​​∣∣∣∣∣​(5) Q = N ∑ i = 1 n N i (6) Q=\frac{N}{\displaystyle\sum_{i=1}^nN_i}\tag{6} Q=i=1∑n​Ni​N​(6) y 0 = y k , k = RouletteWheelSelection ( Q ) (7) y_0=y_k,\quad k=\text{RouletteWheelSelection}(Q)\tag{7} y0​=yk​,k=RouletteWheelSelection(Q)(7)商品均衡价格 x 0 x_0 x0​表示如下： M i = ∣ F x i − 1 n ∑ i = 1 n F x i ∣ (8) M_i=\left|F_{x_i}-\frac1n\sum_{i=1}^nF_{x_i}\right|\tag{8} Mi​=∣∣∣∣∣​Fxi​​−n1​i=1∑n​Fxi​​∣∣∣∣∣​(8) P = M ∑ i = 1 n M i (9) P=\frac{M}{\displaystyle\sum_{i=1}^nM_i}\tag{9} P=i=1∑n​Mi​M​(9) x 0 = { r 1 ⋅ ∑ i = 1 n x i n    i f    r a n d < 0.5 x k ,    k = RouletteWheelSelection ( P ) i f    r a n d ≥ 0.5 (10) x_0=\begin{dcases}r_1\cdot\frac{\displaystyle\sum_{i=1}^nx_i}{n}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\, if \,\,rand<0.5\\x_k,\,\,k=\text{RouletteWheelSelection}(P)\quad if \,\,rand≥0.5\end{dcases}\tag{10} x0​=⎩⎪⎪⎪⎨⎪⎪⎪⎧​r1​⋅ni=1∑n​xi​​ifrand<0.5xk​,k=RouletteWheelSelection(P)ifrand≥0.5​(10)其中， r 1 r_1 r1​是 [ 0 , 1 ] [0,1] [0,1]中的随机数。

（3）供给函数和需求函数

依据均衡数量 y 0 y_0 y0​、均衡价格 x 0 x_0 x0​分别给出供给函数和需求函数： y i ( t + 1 ) = y 0 + α ⋅ ( x i ( t ) − x 0 ) (11) y_i(t+1)=y_0+\alpha\cdot(x_i(t)-x_0)\tag{11} yi​(t+1)=y0​+α⋅(xi​(t)−x0​)(11) x i ( t + 1 ) = x 0 − β ⋅ ( y i ( t + 1 ) − y 0 ) (12) x_i(t+1)=x_0-\beta\cdot(y_i(t+1)-y_0)\tag{12} xi​(t+1)=x0​−β⋅(yi​(t+1)−y0​)(12)其中， x i ( t ) x_i(t) xi​(t)和 y i ( t ) y_i(t) yi​(t)分别为第 t t t次迭代第 i i i个商品价格和数量； α \alpha α和 β \beta β分别为需求权重和供给权重，通过调整 α \alpha α、 β \beta β对均衡价格和均衡数量进行更新。
将式(11)插入式(12)中，可以将需求算式重写为： x i ( t + 1 ) = x 0 − α β ⋅ ( x i ( t ) − x 0 ) (13) x_i(t+1)=x_0-\alpha\beta\cdot(x_i(t)-x_0)\tag{13} xi​(t+1)=x0​−αβ⋅(xi​(t)−x0​)(13)可以发现，从这个方程中，商品价格实际上是根据均衡价格相对于其当前价格进行更新的。通过调整权重 α \alpha α和 β \beta β的值，可以得到不同的商品价格向量。为了在SDO中进行勘探和开发，需要适当地给出供给权重 α \alpha α和需求权重 β \beta β。这两个权重可以表示为： α = 2 ⋅ ( T − t + 1 ) T ⋅ sin ⁡ ( 2 π r ) (14) \alpha=\frac{2\cdot(T-t+1)}{T}\cdot\sin(2\pi r)\tag{14} α=T2⋅(T−t+1)​⋅sin(2πr)(14) β = 2 ⋅ cos ⁡ ( 2 π r ) (15) \beta=2\cdot\cos(2\pi r)\tag{15} β=2⋅cos(2πr)(15)其中， T T T为最大迭代次数， r r r为 [ 0 , 1 ] [0,1] [0,1]中的随机数。用变量 L L L表示供应权重 α \alpha α和需求权重 β \beta β的乘积，可以得到： L = α β = 4 ⋅ ( T − t + 1 ) T ⋅ sin ⁡ ( 2 π r ) ⋅ cos ⁡ ( 2 π r ) (16) L=\alpha\beta=\frac{4\cdot(T-t+1)}{T}\cdot\sin(2\pi r)\cdot\cos(2\pi r)\tag{16} L=αβ=T4⋅(T−t+1)​⋅sin(2πr)⋅cos(2πr)(16)变量 L L L有助于SDO算法在勘探和开发之间平稳过渡。 ∣ L ∣ < 1 |L|<1 ∣L∣<1属稳定模式，通过调整供应权重 α \alpha α和需求权重 β \beta β得到均衡价格 x 0 x_0 x0​周围不同的商品价格，这些商品价格可以通过随机数r在当前价格和均衡价格之间随机变化，稳定模式机制强调“开发”以改善SDO算法的局部勘探能力。 ∣ L ∣ > 1 |L|>1 ∣L∣>1属非稳定模式，它允许任何市场中的商品价格远离均衡价格，非稳定模式机制迫使每个市场在搜索空间中加强“勘探”未知区域以提高SDO算法的全局搜索能力。
图1描述了变量 L L L迭代的值，其中最大迭代次数 T T T设置为1000。如图所示，在早期迭代中， L L L值大于1或小于-1的概率很高。随着迭代次数的增加，这种高概率开始减少，函数值在 [ − 1 , 1 ] [-1,1] [−1,1]中的概率也在增加。在以后的迭代中， L L L值在 [ − 1 ， 1 ] [-1，1] [−1，1]中的概率越来越高。显然，SDO在迭代的早期阶段得到了高度的探索，并在迭代的后期阶段平滑地切换到高度开发。

图1 L L L随迭代次数变化的值

2、SDO算法伪代码

SDO通过随机创建一组市场开始优化。在每次迭代中，市场的每个商品数量都会根据均衡价格和均衡数量进行更新，然后市场的每个商品价格都会根据均衡价格进行更新。均衡价格可以根据其在价格数组中的概率和商品价格的平均值在价格数组中选择的商品价格之间随机切换。均衡数量根据其概率从商品数量中选择。商品价格和数量的更新是通过调整 α \alpha α和 β \beta β的权重值来实现的。为了进行探索或开发，变量 L L L的值随随机波动而降低。当 ∣ L ∣ > 1 | L |>1 ∣L∣>1时，市场商品价格倾向于偏离均衡价格，当 ∣ L ∣ < 1 | L |<1 ∣L∣<1时，市场商品价格趋向于接近均衡价格。然后通过适应度函数对更新后的价格向量和数量向量进行评估。对于每个市场，如果其商品数量的适应度值优于其商品价格的适合度值，则其商品价格将替换为商品数量作为候选解决方案。最终，当满足停止标准时，返回市场的最佳商品价格向量，作为迄今为止找到的最佳解决方案。SDO算法的伪代码如图2所示。

图2 SDO算法伪代码

二、仿真实验与分析

1、函数测试与数值分析

将SDO与DE、CS和GSA进行对比，以文献[1]中的F1、F2(单峰函数/30维)、F10、F11(多峰函数/30维)、F18、F19(固定维度多峰函数/2维、3维)为例，种群规模设置为50，最大迭代次数设置为1000，每个算法独立运算30次。结果显示如下：

函数：F1
SDO：最差值: 0,最优值: 0,平均值: 0,标准差: 0
DE：最差值: 3.2459e-12,最优值: 5.1533e-13,平均值: 1.6181e-12,标准差: 7.0789e-13
CS：最差值: 0.018637,最优值: 0.0041907,平均值: 0.00925,标准差: 0.0035382
GSA：最差值: 3.6491e-17,最优值: 1.1564e-17,平均值: 2.1624e-17,标准差: 6.1163e-18
函数：F2
SDO：最差值: 1.3562e-221,最优值: 8.3254e-250,平均值: 7.4562e-223,标准差: 0
DE：最差值: 5.7666e-08,最优值: 2.3806e-08,平均值: 3.7317e-08,标准差: 7.4574e-09
CS：最差值: 3.9717,最优值: 0.57752,平均值: 1.4775,标准差: 0.79205
GSA：最差值: 3.266e-08,最优值: 1.6686e-08,平均值: 2.367e-08,标准差: 3.7802e-09
函数：F10
SDO：最差值: 8.8818e-16,最优值: 8.8818e-16,平均值: 8.8818e-16,标准差: 0
DE：最差值: 4.571e-07,最优值: 1.6143e-07,平均值: 3.3331e-07,标准差: 6.7617e-08
CS：最差值: 10.2657,最优值: 1.8735,平均值: 4.2762,标准差: 1.7889
GSA：最差值: 4.5218e-09,最优值: 2.813e-09,平均值: 3.6258e-09,标准差: 4.4603e-10
函数：F11
SDO：最差值: 0,最优值: 0,平均值: 0,标准差: 0
DE：最差值: 1.3385e-10,最优值: 2.8634e-12,平均值: 2.7485e-11,标准差: 3.4877e-11
CS：最差值: 0.16107,最优值: 0.031708,平均值: 0.10017,标准差: 0.029381
GSA：最差值: 7.3898,最优值: 2.1345,平均值: 4.2402,标准差: 1.4944
函数：F18
SDO：最差值: 3,最优值: 3,平均值: 3,标准差: 1.1516e-15
DE：最差值: 3,最优值: 3,平均值: 3,标准差: 1.9877e-15
CS：最差值: 3,最优值: 3,平均值: 3,标准差: 1.0066e-15
GSA：最差值: 3,最优值: 3,平均值: 3,标准差: 1.7897e-15
函数：F19
SDO：最差值: -3.8628,最优值: -3.8628,平均值: -3.8628,标准差: 2.7101e-15
DE：最差值: -3.8628,最优值: -3.8628,平均值: -3.8628,标准差: 2.7101e-15
CS：最差值: -3.8628,最优值: -3.8628,平均值: -3.8628,标准差: 2.7101e-15
GSA：最差值: -3.0822,最优值: -3.8628,平均值: -3.5463,标准差: 0.25706

结果表明，SDO算法能够在探索、开发、避免局部最优和收敛速度方面得到很好的结果。

2、求解焊接梁设计优化问题

焊接梁设计问题具体请参考这里。仿真实验中，5种算法的运行次数、种群规模和最大迭代次数都保持一致，即 N = 50 , T = 500 N=50,T=500 N=50,T=500，每种算法分别独立运行30次。结果显示如下：

DE：最差值: 3.3615,最优值: 1.9778,平均值: 2.7004,标准差: 0.39933,秩和检验: 3.0199e-11
CS：最差值: 1.7015,最优值: 1.6957,平均值: 1.6975,标准差: 0.0014562,秩和检验: 3.0199e-11
GSA：最差值: 4.1401,最优值: 2.0054,平均值: 2.9979,标准差: 0.55662,秩和检验: 3.0199e-11
SDO：最差值: 1.6952,最优值: 1.6952,平均值: 1.6952,标准差: 9.0225e-08,秩和检验: 1

实验结果表明：SDO在求解焊接梁设计约束优化问题时具有优越的性能。

3、WSN覆盖优化

本文采用0/1覆盖模型。设监测区域为 50 m × 50 m 50 m×50 m 50m×50m的二维平面，传感器节点个数 N = 35 N=35 N=35，其感知半径是 R s = 5 m R_s=5m Rs​=5m，通信半径 R c = 10 m R_c=10m Rc​=10m，迭代500次。初始部署、SDO优化覆盖、SDO算法覆盖率进化曲线如下图所示。
初始部署和最终部署的节点位置及对应的覆盖率分别为：

初始位置：
5.6582     37.4245
23.1577     34.8591
13.2724     24.4803
24.8642     12.5946
32.7883     46.4487
7.8353     18.4138
18.3774     3.5258
45.8099     36.9291
44.0056     21.116
18.9288     41.8486
3.3807     14.3399
26.4406     37.2905
45.614     47.6354
19.0823     6.0845
24.7767     48.3064
0.37507     23.0336
3.4123     46.5971
40.1028     0.58516
15.0606     38.449
7.1656     26.5867
18.9867     30.3204
19.7615     16.8684
44.2607     28.5768
18.9665     9.827
12.8224     36.2787
34.4507     24.5613
42.4493     39.2337
25.6159     26.5446
35.0056     35.9155
1.704     2.3365
22.2871     32.6603
28.7723     47.0198
12.7802     45.1629
48.4652     2.7958
38.0223     34.0163
初始覆盖率：0.71434
最优位置：
18.2297     17.9504
46.7946     27.2327
22.4647     1.391
40.6251     40.5068
33.4091     3.8476
27.6412     46.6652
27.3794     15.8952
20.737     38.5994
45.3512     18.2282
3.7902     5.3513
14.9054     31.161
17.3529     46.7079
36.5573     12.9072
33.2656     31.4272
29.3992     40.5606
9.3408     13.7054
46.8982     32.6605
11.3766     39.3557
9.9051     25.4657
12.6419     2.6447
4.1495     45.4464
40.237     24.8203
45.8554     10.4365
17.888     9.546
25.0576     21.2343
34.3161     21.9932
24.7155     31.6475
37.1252     46.899
3.5699     22.2425
42.872     5.7517
18.1397     25.8205
37.4114     34.7203
26.4583     9.4486
3.3356     35.3194
47.1419     45.7288
最优覆盖率：0.89081

实验结果表明，SDO能够有效提升WSN的覆盖率，使节点分布更加均匀。

三、参考文献

[1] W. Zhao, L. Wang, Z. Zhang. Supply-Demand-Based Optimization: A Novel Economics-Inspired Algorithm for Global Optimization[J]. IEEE Access, 2019, 7: 73182-73206.
[2] 崔东文, 李代华. 基坑变形预测的改进供需优化算法-指数幂乘积模型[J]. 水利水电科技进展, 2020, 40(4): 43-50.