THESIS
2003
xiv, 111 leaves : ill. ; 30 cm
Abstract
The search for all solutions in the crypto-arithmetic problem is performed with two kinds of adaptive parallel genetic algorithm. Since the performance of genetic algorithms is critically determined by the architecture and parameters involved in the evolution process, an adaptive control is implemented on two parameters governing the relative percentages of preserved (survived) individuals and reproduced individuals (offspring). Adaptive parameter control in the first method involves the estimation of Shannon entropy associated with the fitness distribution of the population. In the second method, parameters are controlled by average values between the extreme and median fitness of individuals. Experiments designed to test two algorithms using crypto-arithmetic problems with ten, eleven...[
Read more ]
The search for all solutions in the crypto-arithmetic problem is performed with two kinds of adaptive parallel genetic algorithm. Since the performance of genetic algorithms is critically determined by the architecture and parameters involved in the evolution process, an adaptive control is implemented on two parameters governing the relative percentages of preserved (survived) individuals and reproduced individuals (offspring). Adaptive parameter control in the first method involves the estimation of Shannon entropy associated with the fitness distribution of the population. In the second method, parameters are controlled by average values between the extreme and median fitness of individuals. Experiments designed to test two algorithms using crypto-arithmetic problems with ten, eleven and twelve alphabets are analyzed using the average first passage time to solutions. Results are compared with exhaustive search and show strong evidence that over 85% of the solutions in each problem can be found using our adaptive parallel genetic algorithms with a considerably faster speed. Furthermore, adaptive parallel genetic algorithm with the second method involving the median is consistently faster than the first method using entropy.
Besides that, I present an approach of applying adaptive genetic algorithm on financial knapsack problem, which aims to maximize the profit from certain amount of investment items, using limited capital. The portion of preserved individuals is kept to a proportion to the difference between the fitness of the best and average values of individuals in the population. Experiments are designed to test the algorithm using knapsack problems with 150, 200, 250 and 300 items, which are analyzed using the mean-absolute deviation generations against the median first passage generations to solutions. Results show evidence that the genetic algorithm can solve knapsack problems with a considerably fast speed, and the risk of finding the global maximum can be minimized by adjusting the size of the persevered proportion, which should be reduced with the increase in difficulty of the problem.
Post a Comment