Two recent papers, published at GECCO 2014 and PPSN 2014 described some improved results from our NELLI system, whose goal is to provide fast, reasonable solution to problems that are presented to the system in a continuous stream, possibly changing in characteristics over time.
NELLI has two novel features:
- A mechanism to continuously generate novel heuristics to solve problems
- A cooperative mechanism that sustains set of heuristics that collaborate to solve all problems that the system has been exposed to, adapting autonomously over time as the nature of the problems changes.
The system was described previously in an article in ECJ 2014. Since then, we have made two modifications that significantly improve results. The first modification simplifies the representation, facilitating the search for new heuristics. The second mechanism enables a better balance between exploitation and exploration, by introducing a second method to generate new heuristics that uses mutation to exploit heuristics that are already sustained, inspired by clonal selection processes in the immune system.
The new representation uses a variable length sequences of nodes – 9 possible nodes represent packing heuristics taken from the literature, such as ‘pack the biggest item’ of ‘pack the largest combination of 2 items that fit exactly’. NELLI evolves new sequences – a pointer moves across the sequence, applying each heuristic before moving to the next heuristic, cycling back to the beginning when it reaches the end.
Continuous Learning and Adaptation to Environment
The new system is presented with alternating sets of problems. The two problem sets are taken from the literature and are known to have completely different characteristics. Heuristics tuned to work well on one set do not perform well on the other.
The figure track performance over epochs over which the sets are
1. The system retains memory: at the start of a new epoch, there is no significant difference in performance when compared to the best value obtained at the end of the previous epoch
2. The system continues to learn over an epoch: there is a significant difference between the performance at the start of an epoch and the (better) performance at the end of an epoch
3. The system continues to learn over its lifetime: there is significant difference between the best value obtained during the first epoch the dataset appears and the best value obtained at the end of the final epoch
NELLI is compared to a set of known heuristics in which one is selected greedily each iteration based on the problem at hand and to the previous version showing clear improvements.
We believe this goes some way towards creating a new kind of optimisation system: one in which problems can be presented continuously, and in which the system autonomously adapts to new problem characteristics. Of course, specialist algorithms tuned to specific problem sets may well outperform NELLI*, however we believe that in the real-world, systems that do not need extensive tuning and produce quick, reasonable solutions to problems are of more interest to the practitioner.