Campus Connection

A UW-La Crosse student may hold the key to solving some of the world’s most complex problems. And that’s thanks to student-faculty research opportunities available to students in many majors. 

Kaelan Engholdt, a senior majoring in computer science, has created a method by which computers can more effectively pinpoint the optimal solutions to a wide range of issues. 

“In computer science, we like to use the biological world for inspiration for things we can try in the computational world,” Engholdt explains. “Genetic algorithms are a perfect example. They’re based on Darwinian evolution, like you see in nature. Basically, you give a computer a population of possible solutions, and over time, they evolve into better and better solutions.” 

This type of problem-solving takes hours or days to complete. Without genetic algorithms, even the world’s fastest computers would take thousands — perhaps millions — of years to find an optimal solution. 

Engholdt’s contribution is a new type of extinction event operator — similar to an asteroid impact or infectious disease in the natural world — that helps genetic algorithms eliminate inferior solutions and replace them with stronger alternatives. 

Previously, when an extinction event occurred in a genetic algorithm, the solutions would quickly repopulate. But, as Engholdt points out, this isn’t reflective of biological extinction events. 

“In biology, it may take many generations for a population to return to its normal size,” he notes. “This means you’ll have less biodiversity immediately after an extinction event, but you’ll also have all these niches for new species to fill, which actually increases evolution.” 

With the help of his mentor, Assistant Professor David Mathias, Engholdt has recreated this phenomenon in genetic algorithms and packaged the extinction model so that it can be plugged into any genetic algorithm in any field. 

Engholdt presented his research in late June during the Congress on Evolutionary Computation, an international conference held virtually this year due to COVID-19. His appearance included a 20-minute, pre-recorded video, as well as a live, six-minute talk followed by a question-and-answer portion. 

While the extinction event operator is a relatively recent development, Engholdt and Mathias have been collaborating on genetic algorithms for the past few years. 

They used one algorithm to train a drone to self-navigate through an obstacle course. They used another to address airlines’ longtime strategy of overbooking flights. 

In a vast majority of cases, not everyone with a plane ticket will show up for their flight. Instead of leaving seats unoccupied, airlines will sell more tickets than they have seats, allowing them to maximize profits. 

The difficulty comes when too many passengers show up, forcing airlines to pay passengers to wait for another flight.  

Engholdt and Mathias used a co-evolutionary genetic algorithm to seek solutions that make sense for airlines and passengers.