Graduation Year

2019

Document Type

Dissertation

Degree

Ph.D.

Degree Name

Doctor of Philosophy (Ph.D.)

Degree Granting Department

Computer Science and Engineering

Major Professor

Alessio Gaspar, Ph.D.

Committee Member

Ali Yalcin, Ph.D.

Committee Member

Lu Lu, Ph.D.

Committee Member

R. Paul Wiegand, Ph.D.

Committee Member

Srinivas Katkoori, Ph.D.

Keywords

Concept Inventory, Interactive Evolutionary Algorithm, Optimization, Pareto Dominance, Solution Concepts

Abstract

Evolutionary Algorithms (EA) have been successfully applied to a wide range of optimization and search problems where no mathematical model of the quality of a candidate solution is available. Interactive Evolutionary Algorithms (IEA) and Competitive Coevolutionary Algorithms (CCoEA) go one step further by being able to tackle problems where the only means to evaluate the quality of a candidate solution is via interactions. In a typical IEA, interactions take place between the solution being evolved and human evaluators. In a CCoEA, interactions take place between solutions themselves, without need for human interaction. This dissertation identifies computer-aided learning as an application domain that exemplifies the overlap of both fields. In particular, this work first develops a novel interactive and competitive (co)evolutionary approach to evolve candidate solutions. To do so, we identify viable algorithms, analyze them and author new variants of hill climber algorithms. Then, we design and implement a competitive coevolutionary interaction-based algorithm. The performance of the resulting heuristic is evaluated with respect to its ability to approximate a full Coevolutionary Dimension Extraction (CDE) process. This allows us to ensure that the proposed approach evolves candidate solutions that have pedagogically relevant in an educational application. However, the underlying hill climber algorithm produces some candidate solutions that exhibit the same interaction outcomes against opponent solutions. So, we also propose different approaches to improve the diversity of the solutions being evolved. To this end, we relax the strict acceptance condition in existing hill climbing algorithms relying on Pareto dominance. The proposed variant draw its inspiration from the Non-dominated Sorted Genetic Algorithm (NSGA), commonly used in evolutionary multixobjectives optimization. We also introduce selection methods based on competitive shared fitness, and the analysis of the interaction space among solutions. Finally, we study Pareto dominance relations of coevolutionary interactions by looking at the interaction matrix of both coevolutionary benchmarks and our educational application. This results in a unique perspective to understanding both structural and relational dominance in coevolutionary interactions. This method can be applied in any open-ended problems where the quality of solutions can not be defined mathematically. It reveals the applicability of CDE, its sensitivity to dominance relations, and its robustness to noisy outcomes.

Download

Share

COinS