You are here
METARAPS: PARAMETER SETTING AND NEW APPLICATIONS
 Date Issued:
 2006
 Abstract/Description:
 ABSTRACT Recently metaheuristics have become a popular solution methodology, in terms of both research and application, for solving combinatorial optimization problems. Metaheuristic methods guide simple heuristics or priority rules designed to solve a particular problem. Metaheuristics enhance these simple heuristics by using a higher level strategy. The advantage of using metaheuristics over conventional optimization methods is metaheuristics are able to find good (near optimal) solutions within a reasonable computation time. Investigating this line of research is justified because in most practical cases with medium to large scale problems, the use of metaheuristics is necessary to be able to find a solution in a reasonable time. The specific metaheuristic studied in this research is, MetaRaPS; Metaheuristic for Randomized Priority Search which is developed by DePuy and Whitehouse in 2001. MetaRaPS is a generic, high level strategy used to modify greedy algorithms based on the insertion of a random element (Moraga, 2002). To date, MetaRaPS had been applied to different types of combinatorial optimization problems and achieved comparable solution performance to other metaheuristic techniques. The specific problem studied in this dissertation is parameter setting of MetaRaPS. The topic of parameter setting for metaheuristics has not been extensively studied in the literature. Although the parameter setting method devised in this dissertation is used primarily on MetaRaPS, it is applicable to any metaheuristic's parameter setting problem. This dissertation not only enhances the power of MetaRaPS by parameter tuning but also it introduces a robust parameter selection technique with widespread utility for many metaheuristics. Because the distribution of solution values generated by metaheuristics for combinatorial optimization problems is not normal, the current parameter setting techniques which employ a parametric approach based on the assumption of normality may not be appropriate. The proposed method is Nonparametric Based Genetic Algorithms. Based on statistical tests, the Nonparametric Based Genetic Algorithms (NPGA) is able to enhance the solution quality of MetaRaPS more than any other parameter setting procedures benchmarked in this research. NPGA sets the best parameter settings, of all the methods studied, for 38 of the 41 Early/Tardy Single Machine Scheduling with Common Due Date and SequenceDependent Setup Time (ETP) problems and 50 of the 54 01 Multidimensional Knapsack Problems (01 MKP). In addition to the parameter setting procedure discussed, this dissertation provides two MetaRaPS combinatorial optimization problem applications, the 01 MKP, and the ETP. For the ETP problem, the MetaRaPS application in this dissertation currently gives the best metaheuristic solution performance so far in the literature for common ETP test sets. For the large ETP test set, MetaRaPS provided better solution performance than Simulated Annealing (SA) for 55 of the 60 problems. For the small test set, in all four different small problem sets, the MetaRaPS solution performance outperformed exiting algorithms in terms of average percent deviation from the optimal solution value. For the 01 MKP, the present MetaRaPS application performs better than the earlier MetaRaPS applications by other researchers on this problem. The MetaRaPS 01 MKP application presented here has better solution quality than the existing MetaRaPS application (Moraga, 2005) found in the literature. MetaRaPS gives 0.75% average percent deviation, from the best known solutions, for the 270 01 MKP test problems.
Title:  METARAPS: PARAMETER SETTING AND NEW APPLICATIONS . 
15 views
9 downloads 

Name(s): 
Hepdogan, Seyhun, Author Whitehouse, Gary, Committee Chair University of Central Florida, Degree Grantor 

Type of Resource:  text  
Date Issued:  2006  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  ABSTRACT Recently metaheuristics have become a popular solution methodology, in terms of both research and application, for solving combinatorial optimization problems. Metaheuristic methods guide simple heuristics or priority rules designed to solve a particular problem. Metaheuristics enhance these simple heuristics by using a higher level strategy. The advantage of using metaheuristics over conventional optimization methods is metaheuristics are able to find good (near optimal) solutions within a reasonable computation time. Investigating this line of research is justified because in most practical cases with medium to large scale problems, the use of metaheuristics is necessary to be able to find a solution in a reasonable time. The specific metaheuristic studied in this research is, MetaRaPS; Metaheuristic for Randomized Priority Search which is developed by DePuy and Whitehouse in 2001. MetaRaPS is a generic, high level strategy used to modify greedy algorithms based on the insertion of a random element (Moraga, 2002). To date, MetaRaPS had been applied to different types of combinatorial optimization problems and achieved comparable solution performance to other metaheuristic techniques. The specific problem studied in this dissertation is parameter setting of MetaRaPS. The topic of parameter setting for metaheuristics has not been extensively studied in the literature. Although the parameter setting method devised in this dissertation is used primarily on MetaRaPS, it is applicable to any metaheuristic's parameter setting problem. This dissertation not only enhances the power of MetaRaPS by parameter tuning but also it introduces a robust parameter selection technique with widespread utility for many metaheuristics. Because the distribution of solution values generated by metaheuristics for combinatorial optimization problems is not normal, the current parameter setting techniques which employ a parametric approach based on the assumption of normality may not be appropriate. The proposed method is Nonparametric Based Genetic Algorithms. Based on statistical tests, the Nonparametric Based Genetic Algorithms (NPGA) is able to enhance the solution quality of MetaRaPS more than any other parameter setting procedures benchmarked in this research. NPGA sets the best parameter settings, of all the methods studied, for 38 of the 41 Early/Tardy Single Machine Scheduling with Common Due Date and SequenceDependent Setup Time (ETP) problems and 50 of the 54 01 Multidimensional Knapsack Problems (01 MKP). In addition to the parameter setting procedure discussed, this dissertation provides two MetaRaPS combinatorial optimization problem applications, the 01 MKP, and the ETP. For the ETP problem, the MetaRaPS application in this dissertation currently gives the best metaheuristic solution performance so far in the literature for common ETP test sets. For the large ETP test set, MetaRaPS provided better solution performance than Simulated Annealing (SA) for 55 of the 60 problems. For the small test set, in all four different small problem sets, the MetaRaPS solution performance outperformed exiting algorithms in terms of average percent deviation from the optimal solution value. For the 01 MKP, the present MetaRaPS application performs better than the earlier MetaRaPS applications by other researchers on this problem. The MetaRaPS 01 MKP application presented here has better solution quality than the existing MetaRaPS application (Moraga, 2005) found in the literature. MetaRaPS gives 0.75% average percent deviation, from the best known solutions, for the 270 01 MKP test problems.  
Identifier:  CFE0001206 (IID), ucf:46949 (fedora)  
Note(s): 
20060801 Ph.D. Engineering and Computer Science, Department of Industrial Engineering and Management Systems Doctorate This record was generated from author submitted information. 

Subject(s): 
combinatorial optimization MetaRaPS operations research parameter setting 

Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFE0001206  
Restrictions on Access:  public  
Host Institution:  UCF 