The Interactive Effects of Operators and Parameters to GA Performance Under Different Problem Sizes
|
 |
|
Post a Comment
|
|
|
|
|
CONTRIBUTORS:
|
|
|
JOURNAL:
|
Philippine Computing Journal,
??(??),
?? - ??.
|
|
|
|
YEAR:
|
forthcoming
|
|
PUB TYPE:
|
Journal Article
|
|
SUBJECT(S):
|
genetic algorithms; traveling salesman problem; experimental models; combinatorial optimization
|
|
DISCIPLINE:
|
Computer Science
|
|
HTTP:
|
|
|
LANGUAGE:
|
English
|
|
PUB ID:
|
103-444-108
(Last edited on
2008/07/23 00:52:14 GMT-6)
|
|
SPONSOR(S):
|
|
|
ABSTRACT:
The complex effect of genetic algorithm's (GA) operators and parameters to its performance has been studied extensively by researchers in the past but none studied their interactive effects while the GA is under different problem sizes. In this paper, We present the use of experimental model (1)~to investigate whether the genetic operators and their parameters interact to affect GA performance, (2)~to find what combination of genetic operators and parameter settings will provide the optimum performance for GA, and (3)~to investigate whether these operator-parameter combination is dependent on the problem size. We designed a GA to optimize a family of traveling salesman problems (TSP), each of known optimum. Our GA was set to use different algorithms in simulating selection (Omega_s), different algorithms (Omega_c) and parameters (p_c) in simulating crossover, and different parameters (p_m) in simulating mutation. We used several n-city TSPs (n={5, 7, 10, 100, 1000}) to represent the different problem sizes. Using analysis of variance of 3-factor factorial experiments, we found out that GA performance is affected by Omega_s at small problem size (5-city TSP) where the algorithm Partially Matched Crossover significantly outperforms Cycle Crossover at 95% confidence level. Under intermediate problem sizes (7-city and 10-city TSPs), we found out that the mean GA performance is affected by the Omega_s x Omega_c interaction where the average performance of GA across p_c and p_m varies at different Omega_s-Omega_c combinations. At big problem sizes (100-city and 1000-city TSPs), we observed that a 3-way interaction among Omega_s, Omega_c, and p_m exist to affect the GA performance averaged across different p_c. Similarly, we also observed that the 3-way interaction among Omega_s, p_c and p_m affects the GA performance averaged across all Omega_c. To explain these three-way interactions, we used the Duncan's Multiple Range Test at 5% probability level to perform pairwise comparison of means of GA performance.
|
|
|
|
STATISTICS
|
|
Click on # to view
|
|
Citations
|
|
0
|
|
References
|
|
0
|
|
Comments
|
|
0
|
|
Quality
|
|
0/0.00
|
|
Interest
|
|
0/0.00
|
|
View(er)s
|
|
2/96
|
|
|
|
|
|
|
| Prev |
Next |
|