Asim’s Blog

PhD Thesis

Still need to write my thesis 😦 . Anyways, I worked in the following areas during my PhD. I will explain only a few of them. Most of my word during the PhD was associated with the design and implementation of a genetic algorithm that is suitable for modern parallel architectures like GPU, Cell BE etc. However, during the last year I shifted my focus to a new kind of genetic algorithm designed specifically to solve mixed integer nonlinear problems (also know as MINLPs). Given below are some of the major topics i studied during my PhD:

Genetic Algorithms to solve MINLPs (Published in LION5, 2011)

Non convex mixed integer non-linear programming problems (MINLPs) are the most general form of global optimization problems. Such problems involve both discrete and continuous variables with several active non-linear equality and inequality constraints. In this paper, a new approach for solving MINLPs is presented using adaptive resolution based micro genetic algorithms with local search. Niching is incorporated in the algorithm by using a technique inspired from the tabu search algorithm. The proposed algorithm adaptively controls the intensity of the genetic search in a given sub-solution space, i.e. promising regions are searched more intensely as compared to other regions. The algorithm reduces the chances of convergence to a local minimum by maintaining a list of already visited minima and penalizing their neighborhoods. This technique is inspired from the tabu list strategy used in the tabu search algorithm. The proposed technique was able to find the best-known solutions to extremely difficult MINLP/NLP problems in a competitive amount of time. The results section discusses the performance of the algorithm and the effect of different operators by using a variety of MINLP/NLPs from different problem domains.

Genetic Algorithms for CUDA compatible GPUs (Published in GPEM 2009, 10:391-415)

General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design and software development. In this paper we describe the challenges and design choices involved in parallelizing a hybrid of Genetic Algorithm (GA) and Local Search (LS) to solve MAXimum SATisfiability (MAX-SAT) problem on a state-of-the-art nVidia Tesla GPU using nVidia Compute Unified Device Architecture (CUDA). MAX-SAT is a problem of practical importance and is often solved by employing metaheuristics based search methods like GAs and hybrid of GA with LS. Almost all the parallel GAs (pGAs) designed in the last two decades were designed for either clusters or MPPs. Unfortunately, very little research is done on the implementation of such algorithms over commodity graphics hardware. GAs in their simple form are not suitable for implementation over the Single Instruction Multiple Thread (SIMT) architecture of a GPU, same is the case with conventional LS algorithms. In this paper we explore different genetic operators that can be used for an efficient implementation of GAs over nVidia GPUs. We also design and introduce new techniques/operators for an efficient implementation of GAs and LS over such architectures. We use nVidia Tesla C1060 to perform several numerical tests and performance measurements and show that in the best case we obtain a speedup of 25x. We also discuss the effects of different optimization techniques on the overall execution time.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: