An iterated local coordinate-exchange algorithm for constructing experimental designs for multi-dimensional constrained spaces

doi:10.23919/JSEE.2021.000103

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (5): 1212-1220.doi: 10.23919/JSEE.2021.000103

• SYSTEMS ENGINEERING • Previous Articles Next Articles

An iterated local coordinate-exchange algorithm for constructing experimental designs for multi-dimensional constrained spaces

Yang YOU^1,²(), Guang JIN¹(), Zhengqiang PAN¹(), Rui GUO^2,*()

¹ College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
² Institute of Systems Engineering, Academy of Military Sciences, Beijing 102300, China

Received:2020-11-16 Online:2021-10-18 Published:2021-11-04
Contact: Rui GUO E-mail:362797786@qq.com;jinguang@nudt.edu.cn;panzhengqiang@nudt.edu.cn;934425166@qq.com
About author:|YOU Yang was born in 1990. She received her B.S. and M.S. degrees in 2012 and 2015 respectively. She is an engineer at the Academy of Military Sciences and she is currently pursuing her Ph.D. degree at the National University of Defense Technology. Her research interests include equipment system engineering, experimental design and evaluation. E-mail: 362797786@qq.com||JIN Guang was born in 1973. He received his B.S., M.S., and Ph.D. degrees from the National University of Defense Technology. Currently he is a researcher and doctoral supervisor at the National University of Defense Technology. His research interests include equipment system engineering and experimental design and evaluation. E-mail: jinguang@nudt.edu.cn||PAN Zhengqiang was born in 1981. He received his B.S., M.S., and Ph.D. degrees from the National University of Defense Technology. Currently he is an associate professor at the National University of Defense Technology. His research interests include equipment system engineering and experimental design and evaluation. E-mail: panzhengqiang@nudt.edu.cn||GUO Rui was born in 1989. He received his B.S. degree from China University of Petroleum in 2011. He received his M.S. and Ph.D. degrees from Army Logistics University in 2014 and 2018 respectively. Currently he is an engineer at the Academy of Military Sciences. His research interests include system engineering of petroleum, oils, and lubricants equipment. E-mail: 934425166@qq.com
Supported by:
This work was supported by the National Natural Science Foundation of China (72171231)

Abstract

Abstract:

Iterated local search (ILS) is used to construct the optimal experimental designs for multi-dimensional constrained spaces, in which the inner loop is based on the stochastic coordinate-exchange (SCE) algorithm. Every time a local optimal solution is found by the SCE algorithm, the perturbation operator is applied to it, and then a new solution is explored in the areas where the exchange of coordinates may produce improvement, so as to retain the features and attributes of the current optimal solution and avoid the defects of random restart. We implement the iterated local coordinate-exchange algorithm for experimental designs in the multi-dimensional constrained spaces. In addition, sensitivity analysis was conducted to analyze the impacts of the parameters on the performance of the proposed algorithm. Also we compared the performance of the proposed algorithm to the SCE algorithm using the random restart strategy. The analysis shows that the proposed algorithm is better than the SCE algorithm in terms of efficiency and quality, especially in the experimental designs for high-dimensional constrained space.

Key words: constrained space, experimental design, coordinate-exchange, iterated local search (ILS)

Yang YOU, Guang JIN, Zhengqiang PAN, Rui GUO. An iterated local coordinate-exchange algorithm for constructing experimental designs for multi-dimensional constrained spaces[J]. Journal of Systems Engineering and Electronics, 2021, 32(5): 1212-1220.

Figures/Tables 15

Fig 1

Fig 2

Table 1

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11-1

Fig 11

Fig 12-1

Fig 12

References 30

1	GOLCHI S, LOEPPKY J L. Monte Carlo based designs for constrained domains. Eprint ArXiv, 2015. http://arxiv.org.nudtproxy.yitlink.com:80/abs/1512.07328.
2	PRATOLA M T, HARARI O, BINGHAM D, et al Design and analysis of experiments on nonconvex regions. Technometrics, 2017, 59 (1): 36- 47. doi: 10.1080/00401706.2015.1115674
3	LEKIVETZ R, JONES B Fast flexible space-filling designs for nonrectangular regions. Quality and Reliability Engineering International, 2015, 31 (5): 829- 837. doi: 10.1002/qre.1640
4	BENKOVA E, HARMAN R, MULLER W G Privacy sets for constrained space-filling. Journal of Statistical Planning and Inference, 2016, 171, 1- 9. doi: 10.1016/j.jspi.2015.12.004
5	TROSSET M W. Approximate maximin distance designs. Proc. of the Section on Physical and Engineering Sciences, 1999: 223–227.
6	BEAL A, CLAEYS-BRUNO M C Constructing space-filling designs using an adaptive WSP algorithm for spaces with constraints. Chemometrics and Intelligent Laboratory Systems, 2014, 133, 84- 91. doi: 10.1016/j.chemolab.2013.11.009
7	NACHTSHEIM M C J The coordinate-exchange algorithm for constructing exact optimal experimental designs. Technometrics, 1995, 37 (1): 60- 69. doi: 10.1080/00401706.1995.10485889
8	MYLONA K, GILMOUR S G, GOOS P Optimal blocked and split-plot designs ensuring precise pure-error estimation of the variance components. Technometrics, 2020, 62 (1): 57- 70. doi: 10.1080/00401706.2019.1595153
9	SAMBO F, BORROTTI M, MYLONA K A coordinate-exchange two-phase local search algorithm for the D- and I-optimal designs of split-plot experiments. Computational Statistics and Data Analysis, 2014, 71, 1193- 1207. doi: 10.1016/j.csda.2013.03.015
10	CAO Y, SMUCKER B, ROBINSON T A hybrid elitist pareto-based coordinate exchange algorithm for constructing multi-criteria optimal experimental designs. Statistics & Computing, 2017, 27 (2): 423- 437.
11	TRINCA L A, GILMOUR S G Improved split-plot and multistratum designs. Technometrics, 2015, 57 (2): 145- 154. doi: 10.1080/00401706.2014.915235
12	HUANG Y, GILMOUR S G, MYLONA K, et al Optimal design of experiments for non-linear response surface models. Journal of the Royal Statistical Society, 2019, 68, 623- 640.
13	KANG L L Stochastic coordinate-exchange optimal designs with complex constraints. Quality Engineering, 2019, 31 (3): 401- 416. doi: 10.1080/08982112.2018.1508695
14	JONES B. Computer aided designs for practical experimentation. Antwerp: University of Antwerp, 2008.
15	LOURENO H R, MARTIN O C. Iterated local search: framework and applications. GENDREAU M, POTVIN J Y, ed. Handbook of Metaheuristics. Boston: Springer, 2010: 363−397.
16	MARTI R, RESENDE M G C, RIBEIRO C C Multi-start methods for combinatorial optimization. European Journal of Operational Research, 2013, 226 (1): 1- 8. doi: 10.1016/j.ejor.2012.10.012
17	CUERVO D P, GOOS P, SORENSEN K Optimal design of large-scale screening experiments: a critical look at the coordinate-exchange algorithm. Statistics and Computing, 2016, 26 (1/2): 15- 28. doi: 10.1007/s11222-014-9467-z
18	LOURENCO H R. Iterated local search: applications and extensions. Proc. of the 8th International Conference on Operations Research and Enterprise Systems, 2019: 7–15.
19	CORDEAU J F, GENDREAU M, LAPORTE G, et al A guide to vehicle routing heuristics. Journal of the Operational Research Society, 2002, 53 (5): 512- 522. doi: 10.1057/palgrave.jors.2601319
20	GENDREAU M. Handbook of metaheuristics. Boston: Springer, 2018.
21	MESTRIA M A hybrid heuristic algorithm for the clustered traveling salesman problem. Computers & Industrial Engineering, 2018, 116 (2): 1- 12.
22	SHAO Z, SHAO W S, PI D C Effective constructive heuristic and metaheuristic for the distributed assembly blocking flow-shop scheduling problem. Applied Intelligence, 2020, 50 (1): 4647- 4669.
23	SUBRAMANIAN A, BATTARRA M An iterated local search algorithm for the travelling salesman problem with pickups and deliveries. Journal of the Operational Research Society, 2013, (64): 402- 409.
24	ALVAREZ A, MUNARI P, MORABITO R Iterated local search and simulated annealing algorithms for the inventory routing problem. International Transactions in Operational Research, 2018, 25 (6): 1785- 1809. doi: 10.1111/itor.12547
25	MORRIS M D, MITCHELL T J Exploratory designs for computational experiments. Journal of Statistical Planning & Inference, 1995, 43 (3): 381- 402.
26	SUTZLE T, HOOS H H. Analyzing the run-time behaviour of iterated local search for the TSP. RIBEIRO C C, HANSEN P, ed. Essays and Surveys in Metaheuristics. Boston: Springer, 2002: 589−611.
27	AARTS E H L, LENSTRA J K. Local search in combinatorial optimization. London: Springer, 1997.
28	KERNIGHAN S L W An effective heuristic algorithm for the travelling-salesman problem. Operations Research, 1973, 21 (2): 498- 516. doi: 10.1287/opre.21.2.498
29	CHARLES A S. An exploration of unmanned aerial vehicles in the army’s future combat systems family of systems. Monterey: Naval Postgraduate School, 2005.
30	DANEL D, ANGELA M D Non-collapsing maximin designs for hyper-polygonal regions. Technometrics, 2012, 54 (2): 169- 178. doi: 10.1080/00401706.2012.676951

Parameter	Range
Number of local searches	(50,300)
Number of iterations	(10,200)
Perturbation object	coordinate, point
Perturbation type	deterministic, random

An iterated local coordinate-exchange algorithm for constructing experimental designs for multi-dimensional constrained spaces

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 15

References 30

Related Articles 1

Recommended Articles

Metrics

Comments