Doctor of Philosophy (Ph.D.)
Degree Granting Department
Computer Science and Engineering
Alessio Gaspar, Ph.D.
Ali Yalcin, Ph.D.
Lu Lu, Ph.D.
R. Paul Wiegand, Ph.D.
Srinivas Katkoori, Ph.D.
Concept Inventory, Interactive Evolutionary Algorithm, Optimization, Pareto Dominance, Solution Concepts
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.
Scholar Commons Citation
Bari, ATM Golam, "Interactive Fitness Domains in Competitive Coevolutionary Algorithm" (2019). Graduate Theses and Dissertations.