Variable Neighborhood Search Algorithm to Achieve | Optimal Allocation Design for Known Covariates
Samrat Hore*
Department of Statistics, Tripura University, India
Submission: September 25, 2017; Published: November 20, 2017
*Corresponding author: Samrat Hore, Department of Statistics, Tripura University, India, Email: sam.stat724@gmail.com
How to cite this article: Samrat H. Variable Neighborhood Search Algorithm to Achieve Optimal Allocation Design for Known Covariates. Biostat Biometrics Open Acc J. 2017; 4(1): 555627. DOI: 10.19080/BBOAJ.2017.04.555627
Keywords:
Keywords: Near-optimal Allocation; ANCOVA; D-optimality; A optimality; Iterative Search
Introduction
For obtaining an optimal allocation design of the experimental units with known single or multiple covariates into several treatment groups, has wide applications in the field of agricultural research, clinical trial, medical experiments, chemical industry, etc with a de-tailed reference is available in [1,2] . Such allocation design has been structured in the linear analysis of covariate (ANCOVA)-one way model. According to Morgan & Rubin [3], balanced covariate allocation design has been preferred to achieve, before the physical experiment takes place when the covariate values are known prior to the experiment. Efficient estimation of treatment effect, or covariate effect, or both, with regard to several optimality criteria such as D and A optimality [4] are preferred for such allocation problem. Now, for finding the exact D or A optimal allocation design is generally not practical for a large number of possible allocations. We may consider an example of a single covariate with experimental units to be allocated into two treatments, one need to examine such non-trivial allocation schemes for the exact optimal solution.
The search space increases with a large number of experimental units, a number of treatments and multiple covariates and under consideration the large search space, the problem becomes immensely difficult as well as computationally intractable for deriving the exact solution. Without knowing the response value, to find an optimal allocation design of the experimental units with known covariates information among two or multiple treatment groups were studied by Harville [5], where a multistage iterative search algorithm had been suggested.
Considering such design issue of the experimental units with known covariates into two or multiple treatments, an iterative algorithm through variable neighborhood search method has been suggested in [1,2]. Variable neighborhood search (VNS) algorithm is a well-known meta-heuristic method proposed by Hansen and Mladenovic [6] and successfully applied to wide range of combinatorial optimization problems such as traveling salesman problem, location theory, cluster analysis, scheduling, vehicle routing, network design etc. [7]. Through VNS algorithm in [1,2], for a given initial solution, a set of connected (or nested) neighborhood structures are defined. Starting from an initial allocation design a better allocation among the neighbors of the selected initial may be found or may not be.
If a better solution is found, then select it as next initial, otherwise choose a random allocation as next initial, among the neighbors and previous initial, with certain predefined probability. The procedure continues until a better allocation is found with attaining a threshold probability (say 0.95 or 0.99) stochastically with successive returns. The method has been efficiently estimated with regard to D and A optimality over random allocation design and Harville algorithm [5] through simulation studies and real-life examples and have found that such allocation design is a near-optimal or an optimal allocation design with covariate balanced and equi-replicate properties [1,2].
References
- Hore S, Dewanji A, Chatterjee A (2014) Design issues related to allocation of experimental units with known covariates into two treatment groups. Journal of Statistical Planning and Inference 155: 117-126.
- Hore S, Dewanji A, Chatterjee A (2016) On optimal allocation of experimental units with known covariates into multiple treatment groups. Calcutta Statistical Association Bulletin 68(1- 2): 69-81.?
- Morgan KL, Rubin DB (2012) Rerandomization to improve covariate balance in experiments. The Annals of Statistics 40(2): 1263-1282.
- Kiefer J (1959) Optimum experimental designs. Journal of Royal Statistical Society 21(2): 272-319.
- Harville DA (1974) Nearly optimal allocation of experimental units using observed covariate values. Technometrics 16(4): 589-599.
- Hansen P, Mladenovic N (2001) Variable neighborhood search: Principles and applications. European Journal of Operational Research 130(3): 449-467.
- Hansen P, Mladenovic N, Perez JAM (2008) Variable neighbourhood search: Methods and applications. Annals of Operations Research 175(1): 367- 407.