ACM Transactions on Evolutionary Learning and Optimization

GPUs are used in many settings to accelerate large-scale scientific computation, including simulation, computational biology, and molecular dynamics. However, optimizing codes to run efficiently on GPUs requires developers to have both detailed understanding of the application logic and significant knowledge of parallel programming and GPU architectures. This paper shows that an automated GPU program optimization tool, GEVO, can leverage evolutionary computation to find code edits that reduce the runtime of three important applications, multiple sequence alignment, agent-based simulation and molecular dynamics codes, by 28.9%, 29%, and 17.8% respectively. The paper presents an in-depth analysis of the discovered optimizations, revealing that (1) several of the most important optimizations involve significant epistasis, (2) the primary sources of improvement are application-specific, and (3) many of the optimizations generalize across GPU architectures. In general, the discovered optimizations are not straightforward even for a GPU human expert, showcasing the potential of automated program optimization tools to both reduce the optimization burden for human domain experts and provide new insights for GPU experts.

Jhe-Yu Liou

Muaaz Awan

Kirtus Leyba

Petr Šulc

Steven Hofmeyr

Carole-Jean Wu

Stephanie Forrest

Evolving to find optimizations humans miss: using evolutionary computation to improve GPU code for bioinformatics applications

演化以发现人类遗漏的优化：利用进化计算改进生物信息学应用的GPU代码

Most AI systems are black boxes generating reasonable outputs for given inputs. Some domains, however, have explainability and trustworthiness requirements that cannot be directly met by these approaches. Various methods have therefore been developed to interpret black-box models after training. This paper advocates an alternative approach where the models are transparent and explainable to begin with. This approach, EVOTER, evolves rule sets based on extended propositional logic expressions. The approach is evaluated in several prediction/classification and prescription/policy search domains with and without a surrogate. It is shown to discover meaningful rule sets that perform similarly to black-box models. The rules can provide insight into the domain and make hidden biases explicit. It may also be possible to edit the rules directly to remove biases and add constraints. EVOTER thus forms a promising foundation for building trustworthy AI systems for real-world applications in the future.

Hormoz Shahrzad

Babak Hodjat

Risto Miikkulainen

EVOTER: Evolution of Transparent Explainable Rule sets

EVOTER：透明可解释规则集的演化

Abstract - Research in the explainability of optimisation techniques has largely focused on metaheuristics and their movement of solutions around the search landscape. Hyper-heuristics create a different challenge for explainability as they make use of many more operators, or low-level heuristics and learning algorithms which modify their probability of selection online. This paper describes a set of methods for explaining hyper-heuristics decisions in both online and offline scenarios using selection hyper-heuristics as an example. These methods help to explain various aspects of the function of hyper-heuristics both at a particular juncture in the optimisation process and through time. Visualisations of each method acting on sequences provide an understanding of which operators are being utilised and when, and in which combinations to produce a greater understanding of the algorithm-problem nexus in hyper-heuristic search. These methods are demonstrated on a range of problems including those in operational research and water distribution network optimisation. They demonstrate the insight that can be generated from optimisation using selection hyper-heuristics, including building an understanding of heuristic usage, useful combinations of heuristics and heuristic parameterisations. Furthermore the dynamics of heuristic utility are explored throughout an optimisation run and we show that it is possible to cluster problem instances according to heuristic selection alone, providing insight into the perception of problems from a hyper-heuristic perspective.

William B. Yates

Edward C. Keedwell

Ahmed Kheiri

Explainable Optimisation through Online and Offline Hyper-heuristics

通过在线和离线超启发式方法实现可解释优化

It is imperative to ensure that artificial intelligence models perform well for all groups including those from underprivileged populations. By comparing the performance of models for the protected group with respect to the rest of the population, we can uncover and prevent unwanted bias. However, a significant drawback of such binary fairness evaluation is its dependency on protected group membership attributes. In various real-world scenarios, protected status for individuals is sparse, unavailable, or even illegal to collect. This paper extends the previous work on binary fairness metrics to relax the requirement on deterministic membership to its surrogate counterpart under a probabilistic setting. We show how to conduct binary fairness evaluation when exact protected attributes are not available, but their surrogates as likelihoods are accessible. In theory, we prove that inferred metrics calculated from surrogates are valid under standard statistical assumptions. In practice, we demonstrate the effectiveness of our approach using publicly available data from the Home Mortgage Disclosure Act and simulated benchmarks that mimic real-world conditions under different levels of model disparity. We extend the results from previous work to include comparisons with alternative model-based methods and we develop further practical guidance based on our extensive simulation. Finally, we embody our method in open-source software that is readily available for use in other applications.

Serdar Kadıoğlu

Melinda Thielbar

Surrogate Modeling to Address the Absence of Protected Membership Attributes in Fairness Evaluation

代理建模以解决公平性评估中受保护成员属性缺失的问题

Neural combinatorial optimization (NCO) is a promising learning-based approach to solving complex combinatorial optimization problems such as the traveling salesman problem (TSP), the vehicle routing problem (VRP), and the orienteering problem (OP). However, how to efficiently train a powerful NCO solver for routing problems remains a crucial challenge. The widely used reinforcement learning method suffers from sparse rewards and low data efficiency, while the supervised learning approach requires a large number of high-quality solutions (i.e., labels) that could be costly to obtain. In this work, we find that simple data augmentation operations can drastically reduce the number of required high-quality solutions for supervised learning. Moreover, simple boosting strategies that leverage the property of multiple optima can significantly improve training efficiency. With only a small set of \(50,000\) labeled instances, supervised learning can achieve a competitive in-distribution performance with the widely-used reinforcement learning counterpart. Furthermore, we also investigate the generalization ability for larger out-of-distribution problems. We believe the findings from this work may lead to a rethinking of the value of data-efficient supervised learning for NCO solver training.

Shunyu Yao

Xi Lin

Jiashu Wang

Qingfu Zhang

Zhenkun Wang

Rethinking Supervised Learning based Neural Combinatorial Optimization for Routing Problem

重新思考基于监督学习的神经组合优化在路由问题中的应用

出版信息	出版商: Association for Computing Machinery，出版周期: ，期刊类型: journal，开源期刊: 否
基本数据	创刊年份: 2021，原创研究文献占比: ，自引率:， Gold OA占比:

ACM Transactions on Evolutionary Learning and Optimization

期刊引文格式

有 1 位以上作者的期刊

有 2 位作者的期刊

有 3 位作者的期刊

有 5 位以上作者的期刊

书籍引用格式

学位论文引用格式

网页引用格式

专利引用格式

手工熬夜修改参考文献？研飞自动匹配期刊，一键轻松成稿，支持 Word/WPS

投稿经验分享

Evolving to find optimizations humans miss: using evolutionary computation to improve GPU code for bioinformatics applications

EVOTER: Evolution of Transparent Explainable Rule sets

Explainable Optimisation through Online and Offline Hyper-heuristics

Surrogate Modeling to Address the Absence of Protected Membership Attributes in Fairness Evaluation

Rethinking Supervised Learning based Neural Combinatorial Optimization for Routing Problem

Evolving to find optimizations humans miss: using evolutionary computation to improve GPU code for bioinformatics applications

EVOTER: Evolution of Transparent Explainable Rule sets

Explainable Optimisation through Online and Offline Hyper-heuristics

Surrogate Modeling to Address the Absence of Protected Membership Attributes in Fairness Evaluation

Rethinking Supervised Learning based Neural Combinatorial Optimization for Routing Problem