ETHOM: An Evolutionary Algorithm for Optimized Feature Models Generation - TECHNICAL REPORT ISA-2012-TR-01 (v. 1.1)

Abstract

A feature model defines the valid combinations of features in a domain. The automated extraction of information from feature models is a thriv ing topic involving numerous analysis operations, techniques and tools. The progress of this discipline is leading to an increasing concern to test and compare the performance of analysis solutions using tough input mod els that show the behaviour of the tools in extreme situations (e.g. those producing longest execution times or highest memory consumption). Cur rently, these feature models are generated randomly ignoring the internal aspects of the tools under tests. As a result, these only provide a rough idea of the behaviour of the tools with average problems and are not sufficient to reveal their real strengths and weaknesses. In this technical report, we model the problem of finding computationally– hard feature models as an optimization problem and we solve it using a novel evolutionary algorithm. Given a tool and an analysis operation, our algorithm generates input models of a predefined size maximizing aspects as the execution time or the memory consumption of the tool when per forming the operation over the model. This allows users and developers to know the behaviour of tools in pessimistic cases providing a better idea of their real power. Experiments using our evolutionary algorithm on a num ber of analysis operations and tools have successfully identified input mod els causing much longer executions times and higher memory consumption than random models of identical or even larger size. Our solution is generic and applicable to a variety of optimization problems on feature models, not only those involving analysis operations. In view of the positive results, we expect this work to be the seed for a new wave of research contributions exploiting the benefit of evolutionary programming in the field of feature modelling.