Feature weighting for data analysis via evolutionary simulation

Applying the concepts and formalism from Evolutionary Game Theory to the data regime, the fundamental paradigms of Evolutionary Data Theory are introduced. It is shown that essential definitions and results such as replicator equations, evolutionary strategies, the Bishop-Cannings theorem and the analogy to Lotka-Volterra systems can be mapped to the data interpretation. Understanding data in matrix form as evolutionary entities, input data is mapped to genes and organisms. Steered by genetic fitness and two evolutionary strategies, Dominant-Balanced and Altruistic-Selfish, data records and features conduct an evolutionary game. It is shown that this evolutionary interpretation remains universally meaningful, by proving convergence to a unique rest point, where all data features persist in the population. A basic example of multi-objective optimization is shown as well as a related distribution problem and machine learning applications.

Evolutionary algorithms have been used for a wide range of multi-objective combinatorial optimization problems. Despite practical success, theoretical results on the runtime of evolutionary algorithms for multi-objective combinatorial problems are rather limited. One classical problem that has been investigated is the multi-objective minimum spanning tree problem for which runtime bounds have been obtained to compute all extremal corner points of the Pareto front. With this paper, we provide some more detailed insights into the structure of the Pareto front when the edge weights take on a small number of distinct values. Based on these insights, we derive new runtime results for evolutionary multi-objective algorithms and complement our theoretical results with experimental investigations.

Scalarization is widely used in multi-objective optimization owing to its simplicity and scalability. In many applications, the goal is to generate solutions that represent diverse user preferences, ideally with uniform coverage of the Pareto front (PF). However, uniformly sampling scalarization weights usually induces non-uniform coverage of the PF. We explain this mismatch through a geometric analysis of the scalarization path. As the scalarization weight varies, the corresponding solutions trace the PF with a generally non-uniform traversal speed. This speed induces an arc-length cumulative distribution function (CDF); inverting this CDF map yields a principled rule for selecting weights that produce uniform PF coverage. Building on this insight, we propose SURF (Sampling Uniformly along the PaReto Front). For structured problems, including bi-objective bandits, we derive closed-form expressions for this CDF map and the resulting PF-aware weight sampling rule. For general problems, SURF alternates between CDF reconstruction and weight sampling. Theoretically, we show that under provable conditions, SURF converges linearly to an unavoidable finite-sampling floor. Empirically, experiments on bandits, multi-objective-gymnasium, and multi-objective LLM alignment demonstrate that SURF efficiently achieves more uniform PF coverage than baselines.