A multi-level grammar approach to grammar-guided genetic programming: the case of scheduling in heterogeneous networks

摘要

The scale at which the human race consumes data has increased exponentially in recent years. One key part in this increase has been the usage of smart phones and connected devices by the populous. Multi-level heterogeneous networks are the driving force behind this mobile revolution, but these are constrained with limited bandwidth and over-subscription. Scheduling users on these networks has become a growing issue. In recent years grammar-guided genetic programming (G3P) has shown its capability to evolve beyond human-competitive network schedulers. Despite the performance of the G3P schedulers, a large margin of improvement is demonstrated to still exist. In the pursuit of this goal we recently proposed a multi-level grammar approach to generating schedulers. The complexity of the grammar was increased at various stages during evolution, allowing for individuals to add more complex functions through variation operations. The goal is to evolve good quality solutions before allowing the population to specialise more as the grammar functionality increased in a layered learning way. In this paper the results of this initial study are replicated, and confirmed, and it is seen that this approach improves the quality of the evolved schedulers. However, despite the gain in performance, we notice that the proposed approach comes with an acute sensitivity to the generation at which the grammar complexity is increased. Therefore, we put forward a novel seeding strategy and show that the seeding strategy mitigates the shortcomings of the original approach. The use of the seeding strategy outperforms the original approach in all the studied cases, and thus yields a better overall performance than the state-of-the-art G3P generated schedulers.