Today, on 2023-04-06, I gave the invited talk Frequency Fitness Assignment (FFA) [频率适应度分配] at the group workshop of the Chair of AI and Aerodynamics led by Prof. Dr. Bernd R. NOACK at the Harbin Institute of Technology in Shenzhen, Guangdong, China [哈尔滨工业大学（深圳）]. The workshop had two sessions and featured eleven more highly interesting presentations, each outlining another exciting approach to aerodynamics and control. It was very cool to see the enormous progress that research has made in this field. Drones and air taxis will certainly have a huge and transformative impact on our society in the near future — and the talks clearly showed that optimization, machine learning, and AI will play an important role in both their design and control. It was a great honor to be invited by Prof. Noack to join this event and to have a chance to show our research there.
The talk on FFA is also available on our website, as slides pdf, as pre-packaged forty-minute video, and as a fifty-minute live recording from the workshop.
Abstract
Optimization problems are situations where we have to pick one of many possible choices and want to do this in such a way that we reach a pre-defined goal at a minimum cost. Classical optimization problems include the Traveling Salesperson Problem, the Maximum Satisfiability Problem (MaxSat), and the Bin Packing problem, for example. Since these problems are NP-hard and solving them to optimality would require exponential runtime in the worst case, metaheuristic algorithms have been developed that deliver near-optimal solutions in acceptable runtime. Examples for classical metaheuristics are the (1+1) EA (also known as randomized local search), Simulated Annealing (SA), and the Standard Genetic Algorithm (SGA). Since we want that such algorithms should behave the same both in quick benchmarking experiments and in practical applications, we would like them to exhibit invariance properties. SA, however, is not invariant under scaling of the objective function and the SGA with fitness-proportionate selection is not invariant under translations of the objective function. The (1+1) EA is invariant under all order-preserving transformations of the objective function value. All heuristic optimization methods are biased to prefer, or at least to select with higher average probability, better solutions over worse ones in their sampling process. They therefore cannot have any stronger invariance property that the (1+1) EA. Frequency Fitness Assignment (FFA) is an algorithm module that can be plugged into existing algorithms. It makes them invariant under all injective transformations of the objective function value, which goes far beyond order-preserving transformations (encryption is, for instance, a bijective transformation…). FFA allows for efficient optimization without bias towards better solutions. We plug FFA into the (1+1) EA. We show that the resulting (1+1) FEA can solve the non-NP-hard Trap, TwoMax, and Jump problems in polynomial runtime, whereas the (1+1) EA needs exponential runtime. Moreover, the (1+1) FEA performs significantly faster on the NP-hard MaxSat problem. We conclude the presentation with an outline of other properties of FFA and our other recent works.
Photos
Invited Talk
This is the live recording (fifty minutes) of the talk given on April 6, 2023, at the Chair of AI and Aerodynamics in the Harbin Institute of Technology in Shenzhen, Guangdong, China [哈尔滨工业大学（深圳）]. The live recording is somewhat more comprehensive, but since you cannot see where the laser pointer is pointing, some things may be slightly harder to see. There also is a pre-packaged 40 minute version where a mouse pointer is visible. Here you can download the slides PDF (in English).