Computer Science Colloquium: Eitan Frachtenberg, Reed College

The Locality of Binary Representations in Genetic and Evolutionary Algorithms - 

Genetic and evolutionary algorithms (GEAs) are a family of search and optimizations heuristics inspired by natural selection. By emulating evolutionary processes in silico, they can often search exponential solution spaces and find near-optimal solutions quickly. But their success hinges on the digital representation of the problem space and the evolutionary operators map to an easy-to-search solution space.

In this talk, we'll discuss one aspect of this mapping, namely, how sensitive the representation is to "genetic" operators like mutation and crossover. After explaining the basic mechanisms, we'll formalize this notion of sensitivity and present our theoretical results on its bounds. Then, we'll compare the theoretical results to three different experimental results, replicated from older papers, and explain the old results with the perspective of the newly proven bounds. In particular, we focus on comparing standard binary encoding with Gray encoding, which are the two most common digital representations in GEAs.

This talk is introductory in nature, so no prior knowledge required. Joint work with Hrishee Shatri.

Tuesday, October 27, 2020 at 5:00pm to 6:00pm

Virtual Event
Event Type

Lecture

Audience

Faculty, Students, Staff

Department
Computer Science, Division of Mathematical and Natural Sciences
Subscribe
Google Calendar iCal Outlook

Recent Activity