- author = "Zdenek Vasicek and Vojtech Mrazek",
- title = "Trading between quality and non-functional properties of median filter in embedded systems",
- journal = "Genetic Programming and Evolvable Machines",
- year = "2017",
- volume = "18",
- number = "1",
- month = mar,
- pages = "45--82",
- keywords = "genetic algorithms, genetic programming, Genetic improvement, Cartesian genetic programming, Median function, Comparison network, Permutation principle, Median filter",
- ISSN = "1389-2576",
- language = "english",
-
URL = "
http://www.fit.vutbr.cz/research/view_pub.php.cs?id=11077",
-
URL = "https://rdcu.be/dfOly",
-
DOI = "
doi:10.1007/s10710-016-9275-7",
- size = "38 pages",
-
abstract = "Genetic improvement has been used to improve
functional and non-functional properties of software.
In this paper, we propose a new approach that applies a
genetic programming (GP)-based genetic improvement to
trade between functional and non-functional properties
of existing software. The paper investigates
possibilities and opportunities for improving
non-functional parameters such as execution time, code
size, or power consumption of median functions
implemented using comparator networks. In general, it
is impossible to improve non-functional parameters of
the median function without accepting occasional errors
in results because optimal implementations are
available. In order to address this issue, we proposed
a method providing suitable compromises between
accuracy, execution time and power consumption.
Traditionally, a randomly generated set of test vectors
is employed so as to assess the quality of GP
individuals. We demonstrated that such an approach may
produce biased solutions if the test vectors are
generated inappropriately. In order to measure the
accuracy of determining a median value and avoid such a
bias, we propose and formally analyse new quality
metrics which are based on the positional error
calculated using the permutation principle introduced
in this paper. It is shown that the proposed method
enables the discovery of solutions which show a
significant improvement in execution time, power
consumption, or size with respect to the accurate
median function while keeping errors at a moderate
level. Non-functional properties of the discovered
solutions are estimated using data sets and validated
by physical measurements on physical microcontrollers.
The benefits of the evolved implementations are
demonstrated on two real-world problems---sensor data
processing and image processing. It is concluded that
data processing software modules offer a great
opportunity for genetic improvement. The results
revealed that it is not even necessary to determine the
median value exactly in many cases which helps to
reduce power consumption or increase performance. The
discovered implementations of accurate, as well as
approximate median functions, are available as C
functions for download and can be employed in a custom
application
http://www.fit.vutbr.cz/research/groups/ehw/median",
