Selection-based Metaheuristics for Large Scale Global Optimization

受自然启发的算法代表了计算机科学中许多问题的一些最成功的方法。人工神经网络（ANN）已经在游戏、药物发现和语言翻译等领域带来了与人类竞争的人工智能应用。进化计算（EC）方法也取得了许多成功，但元启发式领域也被大量基于可疑隐喻（如干扰音乐家、足球风格和蜜蜂舞蹈）的难以区分算法所淹没。在其核心，启发式搜索方法有两个关键项：产生新解决方案的方法和选择这些解决方案中哪些应该存在以影响未来搜索解决方案的产生的方法。尽管隐喻的扩散带来了多样性，但大多数研究都集中在新的解决方案的产生上，而不是在这些解决方案中进行选择的方法。我的研究小组开发了几个新颖的实验，以揭示基于“适者生存”的常见选择技术的失败机制。标准选择技术将保留两种溶液中的滤器，而丢弃另一种。这种比较机制通常会导致“失败的探索”——拒绝更有希望的搜索解决方案（例如，未加工的钻石），因为它不如高度精炼的参考解决方案（例如，抛光的晶体）合适。我们的实验证据表明，导致搜索失败的搜索机制是当前许多技术在高维、多模态搜索空间中表现不佳的主要原因。有几种方法可以解决这种失效机制，例如进行更公平的比较（例如，将未经加工的钻石与未经加工的晶体进行比较）和避免参考溶液的细化（例如，不要抛光未经加工的晶体）。与相关基准相比，这两条道路的初步结果都有所改善，未来五年的资金将支持技术的巨大进步。由于计算资源（例如物联网）的能力和连接性不断增强，搜索和优化算法的改进非常重要。我的研究小组正在研究环境建模、药物设计和能源效率方面的应用。例如，加拿大人关注的一个关键物联网应用是利用风能和太阳能等可再生清洁能源。这些能源的间歇性需要电网模型中的备用发电，在这种模型中，供应必须与需求相匹配。另一种方法是使需求与供给相匹配。由于需求将以数以百万计的物联网设备（例如冰箱）的形式出现，因此实现零排放电网的道路将需要高效的优化技术，例如通过本研究计划开发的技术。

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.