Adaptive Genetic Algorithms: Simulation-Based Optimization Techniques

Abstract

In the last three decades, engineers and decision makers expressed a growing interest in the development of effective modeling and simulation methods to understand and predict the behavior of many phenomena in engineering and science. Many of these phenomena are translated into mathematical models for convenience and comparatively elaborative interpretation. Methods commonly employed for this purpose include, neural networks, simulated annealing, particle swarm optimization, ant colony optimization, tabu search, genetic algorithms, and many more. These methods search for the optimal or near optimal values of parameters of a model built a priori. But for such a case, a suitable model should be well known beforehand. When this is not the case, the problem can be seen from another angle where the goal is to find a program or a mathematical representation which can solve the problem. According to this idea the modeling step is performed automatically thanks to a quality criterion which drives the building process. The aim of the research, presented in this thesis, is to use genetic algorithms for large scale optimization and Non-deterministic polynomial (NP-hard) problems. More specifically, binary-based representation of genetic algorithm is used for non-convex function optimization. The path-based representation is used to solve one of the combinatorial optimization problems i.e. traveling salesman problem. Genetic algorithm is meta-heuristic optimization approach based on the principles and mechanisms of natural evolution and can be used to solve problems with higher order of difficulty developed by John Holland. There are three main operators; selection, crossover and mutation for running this algorithm. In this thesis, we focus mainly on crossover operators but a significant consideration is also given to selection operator as well. In third chapter, we develop a selection procedure which gives a reasonable opportunity to worst individuals along with the best ones. Also in chapter five, a new version of rank-based selection operator which is a fine tradeoff between exploration and exploitation is introduced. The effectiveness and the stability of the proposed selection schemes are then evaluated using a wide range of benchmark instances and the solutions are compared and cross checked with the results published in the relevant peer reviewed literature. Rest of the thesis focuses on two crossover representations: binary for function optimization and permutation for traveling salesman problems. All the developed crossover operators showed an improved and significant performance of the genetic algorithm with fewer generations and lower convergence time in achieving optimal solutions. The operators used are capable of introducing new fitter offspring and without being trapped in a local optimum. Therefore it can be stated that all the proposed operators are efficient to solve non-convex benchmark functions and NP-hard problems like traveling salesman problem. We used MATLAB software to compare the performance of all new operators with existing ones. In this thesis, we provide pseudo-codes for all new developed operators along with those that are used for comparison in our study.