Dynamic runtime optimization is a means to tune the performance of operations on a given platform while executing the application itself. However, most approaches discussed in literature so far fail for applications which have an adaptive and irregular behavior. In this paper, we present an algorithm which is able to incorporate knowledge gathered from previous optimizations to speed up the dynamic tuning procedure. We present the integration of the algorithm within a dynamic runtime optimization library along with a smoothing mechanism of the historic data entries to deal with outliers and inaccuracies in the knowledge base. The approach is evaluated for two separate parallel adaptive application kernels on three different platforms.