CCE Theses and Dissertations

Date of Award

2006

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Computer Information Systems (DCIS)

Department

Graduate School of Computer and Information Sciences

Advisor

Sumitra Mukherjee

Committee Member

Michael J. Laszlo

Committee Member

Easwar Nyshadham

Abstract

Multi-Objective Evolutionary Algorithms (MOEAs) are not easy to use because they require parameter tunings of three main parameters - population size, crossover probability, and mutation probability - in order to achieve desirable solutions and performance for an arbitrary complex problem. Moreover, the use of fixed parameter settings may lead to slow convergence and sub-optimal solutions. This dissertation develops a MOEA with self-adaptive crossover, self-adaptive mutation, and adaptive population size parameters for automating the process of adjusting appropriate parameter values in order to make the MOEA more efficient, simple to use and available to more users. The MOEA with adaptable parameters is built on the NSGA-II (Non-dominated Sorting Genetic Algorithm II) and named as ANSGA-JI (Adaptable NSGA-II). The NSGA-II is chosen because it is one of the best-known MOEAs. In the ANSGA-II, the crossover and mutation parameters are attached to each solution in the population and allowed to co-evolve with each solution. This enables the algorithm to carry prior successful crossover and mutation for creating children solutions and for adaptation of the parameters. Since good parameter values are associated with good candidate solutions, better parameter values will survive because they produce better solutions. The ANSGA-II selects the right population size by running several populations with different population sizes simultaneously and allows the smaller populations more time to run. Smaller populations may find diverse non-dominated solution sets close to the Paretooptimal front faster than the larger populations. If a subsequent larger population identifies a better non-dominated solution set then the algorithm stops running the smaller population since it is unlikely to identify better solutions than the larger one due to genetic drift. Two performance metrics are investigated for their effective use in comparing non-dominated solution sets among different populations during the execution of the ANSGA-II. The dissertation evaluates and discusses the performance of the ANSGA-II, in terms of finding a diverse non-dominated solution set and converging to the true Pareto-optimal front, by comparing the results obtained on a suite of thirteen benchmark multi-objective problems with those obtained by the original NSGA-II. The results demonstrate that the ANSGA-II out performs the NSGA-II. The improvement comes with the cost of longer execution time due to overheads of finding good non dominated solutions and learning good parameter values at the same time. However, the execution time appears to be acceptable on all thirteen benchmark multi-objective problems.

Download
Share Feedback

  Link to NovaCat

Share

COinS