Article Contents
Article Contents

# A simplex grey wolf optimizer for solving integer programming and minimax problems

• * Corresponding author: Mohamed A. Tawhid

The reviewing process of the paper was handled by Shengjie Li as Guest Editor

We are thankful to the anonymous reviewers for constructive feedback and insightful suggestions which greatly improved this paper.The research of the 1st author is supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC). The postdoctoral fellowship of the 2nd author is supported by NSERC.
• In this paper, we propose a new hybrid grey wolf optimizer (GWO) algorithm with simplex Nelder-Mead method in order to solve integer programming and minimax problems. We call the proposed algorithm a Simplex Grey Wolf Optimizer (SGWO) algorithm. In the the proposed SGWO algorithm, we combine the GWO algorithm with the Nelder-Mead method in order to refine the best obtained solution from the standard GWO algorithm. We test it on 7 integer programming problems and 10 minimax problems in order to investigate the general performance of the proposed SGWO algorithm. Also, we compare SGWO with 10 algorithms for solving integer programming problems and 9 algorithms for solving minimax problems. The experiments results show the efficiency of the proposed algorithm and its ability to solve integer and minimax optimization problems in reasonable time.

Mathematics Subject Classification: Primary: 90C10, 90C47, 90C56; Secondary: 68U20, 68W20.

 Citation:

• Figure 1.  Social hierarchy of grey wolf

Figure 2.  The general performance of the proposed SGWO algorithm on integer programming problems

Figure 3.  The general performance of the proposed SGWO algorithm on minimax problems

Table 1.  Parameter setting

 Parameters Definitions Values n Search agents no (population size) 20 $\vec{a}$ Coefficient vector 2 $\vec{A}$ Coefficient vector $[-2a,2a]$ $\vec{r_1}, \vec{r_2}$ random vectors [0, 1] $\vec{C}$ Coefficient vector $2\cdot \vec{r_2}$ $N_{elite}$ Number of best solution for final intensification 1 $Max_{itr}$ Maximum number of iterations 2d -3d

Table 2.  Integer programming optimization test problems

 Test problem Problem definition Problem 1 [32] $FI_{1}(x)=\|x\|_1=|x_1|+\ldots+|x_n|$ Problem 2 [32] $FI_{2}(x)=x^Tx= \begin{bmatrix} x_1\cdots x_n \end{bmatrix} \begin{bmatrix} x_1\\ \vdots\\x_n\end{bmatrix}$ Problem 3 [10] $FI_{3}(x)= \begin{bmatrix} 15\;\;27\;\;36\;\;18\;\;12 \end{bmatrix}x+x^T \begin{bmatrix} 35&-20&-10&32&-10\\ -20&40&-6&-31&32\\ -10&-6&11&-6&-10\\ 32&-31&-6&38&-20\\ -10&32&-10&-20&31\\ \end{bmatrix}x$ Problem 4 [10] $FI_{4}(x)=(9x_1^2+2x_2^2-11)^2+(3x_1+4x_2^2-7)^2$ Problem 5 [10] $FI_{5}(x)=(x_1+10x_2)^2+5(x_3-x_4)^2+(x_2-2x_3)^4+10(x_1-x_4)^4$ Problem 6 [32] $FI_{6}(x)=2x_1^2+3x_2^2+4x_1x_2-6x_1-3x_2$ Problem 7 [10] $FI_{7}(x)=-3803.84-138.08x_1-232.92x_2+123.08x_1^2+203.64x_2^2+182.25x_1x_2$

Table 3.  The properties of the Integer programming test functions

 Function Dimension (d) Bound Optimal FI1 5 [-100 100] 0 FI2 5 [-100 100] 0 FI3 5 [-100 100] -737 FI4 2 [-100 100] 0 FI5 4 [-100 100] 0 FI6 2 [-100 100] -6 FI7 2 [-100 100] -3833.12

Table 4.  The efficiency of invoking the Nelder-Mead method in the final stage of SGWO algorithm for FI1FI7 integer programming problems

 Function Standard NM SGWO GWO method FI1 660.4 1988.35 227.3 FI2 560.2 678.15 225.6 FI3 4920.5 819.45 701.24 FI4 2860.3 266.14 283.5 FI5 1520.6 872.46 508.15 FI6 3760.2 254.15 364.27 FI7 1200.3 245.47 235.16

Table 5.  Experimental results (min, max, mean, standard deviation and rate of success) of function evaluation for FI1FI7 test problems

 Function Algorithm Min Max Mean St.D Suc FI1 RWMPSOg 17,160 74,699 27,176.3 8657 50 RWMPSOl 24,870 35,265 30,923.9 2405 50 PSOg 14,000 261,100 29,435.3 42,039 34 PSOl 27,400 35,800 31,252 1818 50 SGWO 225 275 227.3 24.95 50 FI2 RWMPSOg 252 912 578.5 136.5 50 RWMPSOl 369 1931 773.9 285.5 50 PSOg 400 1000 606.4 119 50 PSOl 450 1470 830.2 206 50 SGWO 215 250 225.6 18.52 50 FI3 RWMPSOg 361 41,593 6490.6 6913 50 RWMPSOl 5003 15,833 9292.6 2444 50 PSOg 2150 187,000 12,681 35,067 50 PSOl 4650 22,650 11,320 3803 50 SGWO 715 750 701.24 37.52 50 FI4 RWMPSOg 76 468 215 97.9 50 RWMPSOl 73 620 218.7 115.3 50 PSOg 100 620 369.6 113.2 50 PSOl 120 920 390 134.6 50 SGWO 275 290 283.5 7.63 50 FI5 RWMPSOg 687 2439 1521.8 360.7 50 RWMPSOl 675 3863 2102.9 689.5 50 PSOg 680 3440 1499 513.1 43 PSOl 800 3880 2472.4 637.5 50 SGWO 510 540 508.15 16.07 50 FI6 RWMPSOg 40 238 110.9 48.6 50 RWMPSOl 40 235 112 48.7 50 PSOg 80 350 204.8 62 50 PSOl 70 520 256 107.5 50 SGWO 355 370 361.6 7.63 50 FI7 RWMPSOg 72 620 242.7 132.2 50 RWMPSOl 70 573 248.9 134.4 50 PSOg 100 660 421.2 130.4 50 PSOl 100 820 466 165 50 SGWO 215 250 235.16 18.02 50

Table 6.  SGWO and other meta-heuristics and swarm intelligence algorithms embedded with NM algorithm for FI1FI7 integer programming problems

 Function GA+NM DE+NM PSO+NM FF+NM CS+NM SGWO FI1 Avg 1106.56 935.48 1160.12 975.23 845.68 227.3 SD 457.96 256.12 423.56 235.69 115.48 24.95 FI2 Avg 947.42 914.58 1125.56 911.25 984.69 225.6 SD 110.07 246.24 285.46 115.48 254.89 18.52 FI3 Avg 2053.43 1846.23 1915.35 1825.23 1115.12 701.24 SD 41.64 115.47 235.69 245.56 158.42 37.52 FI4 Avg 866.73 745.78 875.69 796.23 414.26 283.5 SD 284.48 125.26 145.36 175.28 118.54 7.63 FI5 Avg 954.54 923.18 1115.24 960.43 1142.58 508.15 SD 74.93 126.21 114.56 124.56 215.48 16.07 FI6 Avg 554.35 515.24 535.46 498.75 458.49 361.6 SD 115.14 125.36 223.52 113.58 118.35 7.63 FI7 Avg 485.14 454.36 514.12 435.47 390.78 235.16 SD 117.12 148.12 90.14 142.58 118.62 18.02

Table 7.  Experimental results (mean, standard deviation and rate of success) of function evaluation between BB and SGWO for FI1FI7 test problems

 Function Algorithm Mean St.D Suc FI1 BB 1167.83 659.8 30 SGWO 223.15 22.35 30 FI2 BB 139.7 102.6 30 SGWO 220.26 15.26 30 FI3 BB 4185.5 32.8 30 SGWO 690.55 34.56 30 FI4 BB 316.9 125.4 30 SGWO 279.85 8.56 30 FI5 BB 2754 1030.1 30 SGWO 498.25 15.48 30 FI6 BB 211 15 30 SGWO 361.75 9.45 30 FI7 BB 358.6 14.7 30 SGWO 233.45 21.45 30

Table 8.  Minimax optimization test problems

 Test problem Problem definition Problem 1 [41] $FM_{1}(x)=\text{max}\;\; {f_i(x)}, \;\; i=1,2,3,$$f_1(x)=x_1^2+x_2^4,$$f_2(x)=(2-x1)^2+(2-x_2)^2,$$f_3(x)=2exp(-x_1+x_2) Problem 2 [41] FM_{2}(x)=\text{max}\;\; {f_i(x)}, \;\; i=1,2,3,$$f_1(x)=x_1^4+x_2^2$$f_2(x)=(2-x1)^2+(2-x_2)^2,$$f_3(x)=2exp(-x_1+x_2)$ Problem 3 [41] $FM_{3}(x)=x_1^2+x_2^2+2x_3^2+x_4^2-5x_1-5x_2-21x_3+7x_4,$$g_2(x)=-x_1^2-x_2^2-x_3^3-x_4^2-x_1+x_2-x_3+x_4+8,$$g_3(x)=-x_1^2-2x_2^2-x_3^2-2x_4+x_1+x_4+10,$$g_4(x)=-x_1^2-x_2^2-x_3^2-2x_1+x_2+x_4+5 Problem 4 [41] FM_{4}(x)=\text{max}{f_i(x)}\;\; i=1,\ldots,5$$f_{1}(x)=(x_1-10)^2+5(x_2-12)^2+x_3^4+3(x_4-11)^2$$+10x_5^6+7x_6^2+x_7^4-4x_6x_7-10x_6-8x_7,$$f_2(x)=f_1(x)+10(2x_1^2+3x_2^4+x_3+4x_4^2+5x_5-127),$$f_3(x)=f_1(x)+10(7x_1+3x_2+10x_3^2+x_4-x_5-282),$$f_4(x)=f_1(x)+10(23x_1+x_2^2+6x_6^2-8x_7-196),$$f_5(x)=f_1(x)+10(4x_1^2+x_2^2-3x_1x_2+2x_3^2+5x_6-11x_7 Problem 5 [34] FM_{5}(x)=\text{max}\;\; {f_i(x)},\;\;i=1,2,$$f_1(x)=|x_1+2x_2-7|$, $f_2(x)=|2x_1+x_2-5|$ Problem 6 [34] $FM_{6}(x)=\text{max} \;\; {f_i(x)}, $$f_i(x)=|x_i|,\;\;i= 1,\ldots,10 Problem 7 [22] FM_{7}(x)= \text{max}\;\; {f_i(x)},\;\;i=1,2,$$f_1(x)=(x_1-\sqrt{(x_1^2+x_2^2)}cos\sqrt{x_1^2+x_2^2})^2+0.005(x_1^2+x_2^2)^2,$$f_2(x)=(x_2-\sqrt{(x_1^2+x_2^2)}sin\sqrt{x_1^2+x_2^2})^2+0.005(x_1^2+x_2^2)^2 Problem 8 [22] FM_{8}(x)= \text{max}\;\; {f_i(x)},\;\;i=1,\ldots,4,$$f_1(x)=\big(x_1-(x_4+1)^4\big)^2+\Big(x_2-\big(x_1-(x_4+1)^4\big)^4\Big)^2+2x_3^2+x_4^2$$\;\;\;\;\;\;\;\;\;\;-5\big(x_1-(x_4+1)^4\big)-5\Big(x_2-\big(x1-(x_4+1)^4\big)^4\Big)-21x_3+7x_4,$$f_2(x)=f_1(x)+10\Big[\big(x_1-(x_4+1)^4\big)^2+\Big(x_2-\big(x_1-(x_4+1)^4\big)^4\Big)^2+x_3^2+x_4^2$$\;\;\;\;\;\;\;\;\;\;+\big(x_1-(x_4+1)^4\big)-\Big(x_2-\big(x_1-(x_4+1)^4\big)^4\Big)+x_3-x_4-8\Big],$$f_3(x)=f_1(x)+10\Big[\big(x_1-(x_4+1)^4\big)^2+2\Big(x_2-\big(x_1$$\;\;\;\;\;\;\;\;\;\;-(x_4+1)^4\big)^4\Big)^2+x_3^2+2x_4^2-\big(x_1-(x_4+1)^4\big)-x_4-10\Big], f_4(x)=f_1(x)+10\Big[\big(x_1-(x_4+1)^4\big)^2+\Big(x_2-\big(x_1-(x_4+1)^4\big)^4\Big)^2$$\;\;\;\;\;\;\;\;\;\;+x_3^2+2\big(x_1-(x_4+1)^4\big)-\Big(x_2-\big(x_1-(x_4+1)^4\big)^4\Big)-x_4-5\Big]$ Problem 9 [22] $FM_{9}(x)= \text{max}\;\; {f_i(x)},\;\;i=1,\ldots,5, $$f_1(x)=(x_1-10)^2+5(x_2-12)^2+x_3^4+3(x_4-11)^2+10x_5^6+7x_6^2+x_7^4 \; \; \; \; \; \; \; \; \; \ -4x_6x_7-10x_6-8x_7, f_2(x)=-2x_1^2-2x_3^4-x_3-4x_4^2-5x_5+127, f_3(x)=-7x_1-3x_2-10x_3^2-x_4+x_5+282, f_4(x)=-23x_1-x_2^2-6x_6^2+8x_7+196, f_5(x)=-4x_1^2-x_2^2+3x_1x_2-2x_3^2-5x_6+11x_7 Problem 10 [22] FM_{10}(x)=\text{max} {|f_i(x)|}, \;\;\; i=1,\ldots,21,$$f_i(x)=x_1exp(x_3t_i)+x_2exp(x_4t_i)-\frac{1}{1+t_i}, \ t_i=-0.5+\frac{i-1}{20}$

Table 9.  Minimax test functions properties.

 Function Dimension(d) Desired error goal FM1 2 1.95222245 FM2 2 2 FM3 4 -40.1 FM4 7 247 FM5 2 10−4 FM6 10 10−4 FM7 2 10−4 FM8 4 -40.1 FM9 7 680 FM10 4 0.1

Table 10.  The efficiency of invoking the Nelder-Mead method in the final stage of SGWO for FM1FM10 minimax problems

 Function Standard NM SGWO GWO method FM1 2940.2 290.35 210.23 FM2 3740.1 286.47 195.15 FM3 1120.2 537.46 381.75 FM4 4940.3 19,147.15 806.45 FM5 3520.4 273.36 215.36 FM6 2080.3 18,245.48 1602.18 FM7 1020.4 736.14 138.62 FM8 1620.4 1652.17 373.25 FM9 3760.5 19,857.69 942.45 FM10 1630.4 867.26 349.46

Table 11.  Evaluation function for the minimax problems FM1FM10

 Algorithm Problem Avg SD %Suc HPS2 FM1 1848.7 2619.4 99 FM2 635.8 114.3 94 FM3 141.2 28.4 37 FM4 8948.4 5365.4 7 FM5 772.0 60.8 100 FM6 1809.1 2750.3 94 FM7 4114.7 1150.2 100 FM8 - - - FM9 283.0 123.9 64 FM10 324.1 173.1 100 UPSOm FM1 1993.8 853.7 100 FM2 1775.6 241.9 100 FM3 1670.4 530.6 100 FM4 12,801.5 5072.1 100 FM5 1701.6 184.9 100 FM6 18,294.5 2389.4 100 FM7 3435.5 1487.6 100 FM8 6618.50 2597.54 100 FM9 2128.5 597.4 100 FM10 3332.5 1775.4 100 RWMPSOg FM1 2415.3 1244.2 100 FM2 - - - FM3 3991.3 2545.2 100 FM4 7021.3 1241.4 100 FM5 2947.8 257.0 100 FM6 18,520.1 776.9 100 FM7 1308.8 505.5 100 FM8 - - - FM9 - - - FM10 4404.0 3308.9 100 SGWO FM1 210.23 25.54 100 FM2 195.15 36.69 100 FM3 381.75 15.39 100 FM4 806.45 249.55 100 FM5 215.36 75.68 100 FM6 1602.18 425.18 100 FM7 932.6 12.6 100 FM8 138.62 15.23 100 FM9 942.45 55.68 100 FM10 349.46 25.45 100

Table 12.  SGWO and other meta-heuristics and swarm intelligence algorithms for FM1FM10 minimax problems

 Function GA+NM DE+NM PSO+NM FF+NM CS+NM SGWO FM1 Avg 486.25 458.47 490.78 445.42 391.16 210.23 SD 153.69 114.58 128.87 98.47 95.48 25.54 FM2 Avg 469.58 459.28 485.46 483.47 346.58 195.15 SD 115.45 112.86 135.486 115.78 125.48 36.69 FM3 Avg 635.48 590.46 610.76 598.48 359.42 381.75 SD 186.92 211.48 184.35 115.46 112.58 15.39 FM4 Avg 2158.69 2214.78 1985.46 1965.48 1846.35 806.45 SD 354.76 387.45 453.84 536.44 458.75 249.55 FM5 Avg 476.58 436.48 469.85 456.48 315.36 215.36 SD 114.79 113.58 135.48 112.47 114.56 75.68 FM6 Avg 5383.49 4952.36 5148.46 4856.24 2952.14 1602.18 SD 486.58 425.85 415.68 364.58 358.45 425.18 FM7 Avg 487.48 495.48 496.58 468.12 295.48 138.62 SD 127.85 142.36 185.26 169.35 85.34 12.6 FM8 Avg 2180.35 2049.15 2185.46 1954.15 1665.28 373.25 SD 487.54 475.69 519.48 413.68 98.62 15.23 FM9 Avg 5982.48 5846.48 5948.47 5634.65 3158.46 942.45 SD 487.14 356.84 458.36 368.47 256.48 55.68 FM10 Avg 845.71 795.26 876.29 863.45 563.58 349.46 SD 248.27 195.47 112.84 158.58 158.16 25.45

Table 13.  Experimental results (mean, standard deviation and rate of success) of function evaluation between SQP and SGWO for FM1FM10 test problems

 Function Algorithm Mean St.D Suc FM1 SQP 4044.5 8116.6 24 SGWO 211.45 31.56 30 FM2 SQP 8035.7 9939.9 18 SGWO 191.58 45.36 30 FM3 SQP 135.5 21.1 30 SGWO 385.75 27.42 30 FM4 SQP 20,000 0.0 0.0 SGWO 825.36 250.36 30 FM5 SQP 140.6 38.5 30 SGWO 210.45 85.65 30 FM6 SQP 611.6 200.6 30 SGWO 1648.23 512.34 30 FM7 SQP 15,684.0 7302.0 10 SGWO 152.34 15.48 30 FM8 SQP 20,000 0.0 0.0 SGWO 380.26 36.89 30 FM9 SQP 20,000 0.0 0.0 SGWO 936.48 62.35 30 FM10 SQP 4886.5 8488.4 22 SGWO 356.89 39.85 30

Figures(3)

Tables(13)