Open Access Open Access  Restricted Access Subscription Access

Improving Genetic Algorithm with Fine-Tuned Crossover and Scaled Architecture


Affiliations
1 Department of Computer Science and Engineering, University of Bridgeport, 126 Park Avenue, Bridgeport, CT 06604, United States
 

Genetic Algorithm (GA) is ametaheuristic used in solving combinatorial optimization problems. Inspired by evolutionary biology, GA uses selection, crossover, and mutation operators to efficiently traverse the solution search space. This paper proposes nature inspired fine-tuning to the crossover operator using the untapped idea of Mitochondrial DNA (mtDNA). mtDNA is a small subset of the overall DNA. It differentiates itself by inheriting entirely from the female, while the rest of the DNA is inherited equally from both parents. This unique characteristic of mtDNA can be an effective mechanism to identify members with similar genes and restrict crossover between them. It can reduce the rate of dilution of diversity and result in delayed convergence. In addition,we scale the well-known Island Model, where instances of GA are run independently and population members exchanged periodically, to a Continental Model. In this model, multiple web services are executed with each web service running an island model.We applied the concept of mtDNA in solving Traveling Salesman Problem and to train Neural Network for function approximation. Our implementation tests show that leveraging these new concepts of mtDNA and Continental Model results in relative improvement of the optimization quality of GA.
User
Notifications
Font Size

Abstract Views: 42

PDF Views: 0




  • Improving Genetic Algorithm with Fine-Tuned Crossover and Scaled Architecture

Abstract Views: 42  |  PDF Views: 0

Authors

Ajay Shrestha
Department of Computer Science and Engineering, University of Bridgeport, 126 Park Avenue, Bridgeport, CT 06604, United States
Ausif Mahmood
Department of Computer Science and Engineering, University of Bridgeport, 126 Park Avenue, Bridgeport, CT 06604, United States

Abstract


Genetic Algorithm (GA) is ametaheuristic used in solving combinatorial optimization problems. Inspired by evolutionary biology, GA uses selection, crossover, and mutation operators to efficiently traverse the solution search space. This paper proposes nature inspired fine-tuning to the crossover operator using the untapped idea of Mitochondrial DNA (mtDNA). mtDNA is a small subset of the overall DNA. It differentiates itself by inheriting entirely from the female, while the rest of the DNA is inherited equally from both parents. This unique characteristic of mtDNA can be an effective mechanism to identify members with similar genes and restrict crossover between them. It can reduce the rate of dilution of diversity and result in delayed convergence. In addition,we scale the well-known Island Model, where instances of GA are run independently and population members exchanged periodically, to a Continental Model. In this model, multiple web services are executed with each web service running an island model.We applied the concept of mtDNA in solving Traveling Salesman Problem and to train Neural Network for function approximation. Our implementation tests show that leveraging these new concepts of mtDNA and Continental Model results in relative improvement of the optimization quality of GA.