Selection-based Metaheuristics for Large Scale Global Optimization

点击翻译按钮获取中文摘要

Nature-inspired algorithms represent some of the most successful approaches to many problems in computer science. Artificial Neural Networks (ANN) have led to human-competitive Artificial Intelligence applications in areas like game playing, drug discovery, and language translation. Evolutionary Computation (EC) methods have many successes as well, but the field of metaheuristics is also overrun by a proliferation of indistinguishable algorithms based on questionable metaphors such as jamming musicians, styles of soccer, and honey bee dances. At their core, heuristic search methods have two key items: a method to produce new solutions and a method to select which of these solutions should survive to influence the future production of search solutions. Despite the diversity expected from the proliferation of metaphors, the majority of research focuses on the production of new solutions as opposed to the methods of selection amongst these solutions. My research team has developed several novel experiments to expose the failure mechanisms of common selection techniques based on "survival of the fittest". Standard selection techniques will have the fitter of two solutions kept and the other discarded. This comparison mechanism often leads to "Failed Exploration" - the rejection of a more promising search solution (e.g a rough diamond) because it is less fit than a highly refined reference solution (e.g. a polished crystal). Our experimental evidence suggests that search mechanisms which lead to failed exploration are the primary cause for the poor performance of many current techniques in high dimensional, multi-modal search spaces. There are several paths to address this failure mechanism such as making fairer comparisons (e.g. comparing rough diamonds with rough crystals) and avoiding the refinement of reference solutions (e.g. don't polish the rough crystal). Preliminary results along both of these paths have led to improvements versus relevant benchmarks, and funding over the next five years will support large advances to the state of the art. Improvements to search and optimization algorithms are important due to the ever increasing power and connectivity of computational resources, e.g. the Internet of Things (IoT). My research team is working on applications in environmental modelling, drug design, and energy efficiency. For example, a key IoT application of concern to Canadians is to harness renewable clean energy such as wind and solar. The intermittent nature of these sources requires stand-by backup generation in an electricity grid model where supply must be matched to demand. An alternative approach is to match demand to supply. Since demand will be in the form of millions of IoT devices (e.g. refrigerators), this path towards a zero-emissions electricity grid will require highly efficient optimization techniques like the ones to be developed through this research program.