This week’s BEACON Researchers at Work blog post is by MSU graduate student Brian Goldman.
Brian visits Austria as part of his research collaboration.
I teach computers to be better at guess, check, and revise. At least, that is the short version of my research. More precisely, I develop optimization algorithms based on evolutionary principles for the purpose of finding high quality solutions to challenging real-world problems. Most of the time this involves staring at white boards, pacing back and forth, and muttering to myself, with occasional rushes of pure excitement caused by some new revelation. However, thanks to months of hard work and the generous support of BEACON, I recently got to travel to Austria to share my ideas with the open source community.
For the last 18 months I have been working to develop what I call the Parameter-less Population Pyramid, or P3 for short. P3 is built on the idea that it is often easier to determine how good a solution is than to find the best possible solution. To understand how P3 works, let’s apply it to the problem of packing a moving truck. It’s pretty easy to measure how good a packing configuration is (how much stuff fits in the truck) but pretty hard to find the best configuration (getting everything in the truck). To solve this problem, P3 starts with an initial guess (random solution) for how to pack the truck, and then makes minor changes to that guess (hill climbing) until doing so can’t make it any better. For instance, you might get to the point where moving any chair will not make things better, but if you could move all of them at once into a big stack it would be a lot better.
Algorithm overview of P3.
Unfortunately, trying to test all ways to make larger changes to a guess can take a lot of time. To overcome this problem, P3 stores multiple good guesses (population) and tries to learn what makes them good. To further improve, P3 tries to take the good parts of previous guesses and combine them to create new ones (mixing). In our example, this could mean putting together the box stacking from one guess and the furniture layout of another. In order to focus learning, P3 filters guesses based on how much effort went into producing each guess, storing them separately (pyramid of populations). This design also lets P3 learn as it goes (parameter-less), unlike most evolutionary systems where you need to know how many guesses to store before starting optimization.
This method of iterative solution improvement is designed to be applicable to a wide range of problems. The exact same algorithm can, for instance, be applied to making better crumple zones in cars and to reducing power consumption in electronics. Unlike many previous methods which rely on people to provide problem specific information, P3 is focused on learning everything it needs from the problem itself. On top of being easier to use, all of the initial results suggest that P3 is actually more effective than existing methods for performing this kind of optimization.
Brian and members of the HEAL group.
The challenge now is to get P3 in the hands of people who have problems they need solved, which brings us back to my trip to Austria. HeuristicLab is an open source tool developed by the Heuristic and Evolutionary Algorithms Laboratory (HEAL) at the University of Applied Sciences Upper Austria. Built to be user friendly, HeuristicLab provides a graphical interface which allows users to test out a wide variety of optimization algorithms and is currently in use by many researchers and practitioners world wide.
Example P3 optimization using HeuristicLab.
Last December I flew to Austria to further BEACON’s collaboration with HEAL and to integrate P3 into HeuristicLab. This in-person interaction was essential to ensuring the smooth transition of my work into their toolbox as I was the first non HEAL member to significantly expand HeuristicLab. That is to say I asked a lot of questions and got a lot of help, but I think in the process we made it easier for future researchers to add their work. I am proud to say we were completely successful, and P3 is now available for download as part of HeuristicLab 3.3.11. By integrating into their software, I gained access to their real time data visualization and analysis tools, which will definitely help me better understand how P3 works and how to make it even better. Doing so also makes P3 more accessible to the optimization community, a critical step toward increasing its utilization.
For more information about Brian’s work, you can email him at goldma72 at msu dot edu.
