Real jumping gene genetic algorithm (RJGGA) for evolutionary multiobjective optimization problems

用於演化多目標最佳化的實編碼跳躍基因演算法

Student thesis: Master's Thesis

View graph of relations

Author(s)

  • Kazi Shah Nawaz RIPON

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date3 Oct 2006

Abstract

Real-world applications often involve the satisfaction of multiple conflicting objectives simultaneously. The problems with two or more objectives are called “multiobjective” problems that usually have a set of trade-off solutions. Evolutionary multiobjective optimization is currently gaining significant attention from researchers in various fields due to its effectiveness and robustness in solving multiobjective problems. The Jumping Gene Genetic Algorithm (JGGA) is a relatively recent multiobjective evolutionary algorithm (MOEA), which is proven to be in the leading edge over many existing MOEAs. In its initial formulation, the search space solutions are binary-coded and it inherits the customary problems of conventional binary-coded genetic algorithm (BCGA). For this reason, it is very important to remodel the JGGA into a real-coded genetic algorithm (RCGA). The primary focus of this thesis is to present the Real Jumping Gene Genetic Algorithm (RJGGA) as an improvement on the JGGA to remove the shortcomings associated with the original JGGA. In order to introduce the concept and verification of RJGGA, this thesis comprised the basic concept of jumping gene phenomenon and the necessary modification required for transforming JGGA into RJGGA. To validate the performance of the proposed approach, we systematically compare the RJGGA with various existing MOEAs using some carefully chosen benchmark test functions. Simulation results justify that the proposed approach is able to generate non-dominated solutions with a wider spread along the Pareto-optimal front and better address the issues regarding convergence and diversity in multiobjective optimization. This thesis also presents the applications of RJGGA on two different practical multiobjective problems to justify its efficiency in solving such problems. First, we illustrate the application of the proposed method in case of multiobjective data clustering. Traditional clustering algorithms are limited to optimizing single clustering objective only and often fail to detect meaningful clusters because most practical data sets are characterized by a high-dimensional, inherently sparse, data space. Inspired by the inherent multiobjective nature of data clustering, we devise an explicit multiobjective data clustering approach to deal with a range of complex data properties including overlapping clusters, elongated cluster shapes, unequal sized clusters, etc. For these reasons, we present a novel multiobjective evolutionary clustering approach using the Variable-Length Real Jumping Genes Genetic Algorithms (VRJGGA), which evolves clustering solutions using multiple clustering criteria without any prior knowledge of the actual number of clusters. Finally, we investigate the application of RJGGA in solving the multiobjective Job-Shop Scheduling Problem (JSSP). During the last decades, various evolutionary approaches were investigated in solving the JSSPs. However, most of them are limited to a single objective, which is not suitable for real-world scheduling problems as they naturally involve multiple objectives. The proposed scheduling approach heuristically searches for the near-optimal schedules that optimize multiple criteria simultaneously. Experimental results for both of the above two applications confirm that the RJGGA consistently finds solutions with better diversity and convergence as compared to other existing evolutionary based approaches.

    Research areas

  • Evolutionary programming (Computer science), Genetic algorithms, Evolutionary computation, Mathematical optimization