Real World Optimisation with Life-Long Learning

通过终身学习进行现实世界的优化

• 批准号: EP/J021628/1
• 负责人: Emma Hart
• 金额: $ 30.33万
• 依托单位: Edinburgh Napier University
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2013
• 资助国家: 英国
• 起止时间: 2013 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FJ021628%2F1
• 关键词: Real; World; Optimisation; Life; Long

Many practical problems arising in industrial domains concerned with operating sustainably, meeting demand and minimising costs cannot be solved exactly. Meta-heuristic optimisation techniques have been widely developed in academia to solve such problems with much success reported in the literature. However, there remains a worrying void between scientific research into optimisation techniques and those problems faced by end-users and addressed by commercial optimisation software vendors. From a commercial perspective, the problems addressed by academia are too simplistic compared to those faced in the real-world, failing to embrace many real-world constraints. From the scientific perspective, researchers have also identified a "lack of advanced metaheuristic techniques in commercial software'' which has been attributed in part to the academic community failing to demonstrate that their solutions are applicable to the needs of the commercial world, and in part to academics failing to impart their message the industrial community.Meta-heuristic approaches can be costly to develop as they generally require human expertise to integrate specialist knowledge into an algorithm, and expertise in heuristic methods to design and tune algorithms. Recent research has therefore focused on automated algorithm design and configuration which produce tuned solvers that perform well on either individual problems or across suites of problems. One branch of this field is hyper-heuristics, which operates on a space of low-level heuristics, searching for combinations of heuristics which exploit the strength and compensate for the weaknesses of individual known heuristics. The resulting algorithms are cheap to implement, require less human expertise, have robust performance within a problem class, and are portable across problem domains. These features compensate for some reduction in solution quality compared to tailor-made approaches, while still ensuring solutions of acceptable quality. However, most automated design approaches fail to incorporate or recognise a crucial human competence; human beings continuously learn from experience - by generalising observations and feedback, they are able to update their internal problem-solving models in order to continuously improve them, and adapt to changing circumstances. The failure of computational solvers to exploit previous knowledge both wastes useful knowledge and potentially hinders the discovery of good solutions. Furthermore, if the characteristics of instances of problems in the domain change over time, solvers may need to be completely re-tuned or in the worst case redesigned periodically.This proposal addresses these dual concerns raised above. We propose a novel lifelong-learning hyper-heuristic system which addresses current deficiencies inherent in current systems: it will exhibit short-term learning, producing fast and effective solutions to individual problems and at the same time, long-term learning processes will enable the system to autonomously adapt to new problem characteristics over time. It therefore exploits existing knowledge whilst simultaneously adapting to new information. Secondly, by working closely with two collaborators, a commercial routing software vendor and a forestry expert, our research will be directly informed by real-world problems, accounting for real constraints and performance criteria, thereby producing economic impact. Future advances in optimisation techniques will be facilitated by the development of a problem generator and a number of problem suites which reflect real-world priorities and constraints, derived from actual problem data provided through our collaborators and defined in conjunction with metrics which reflect not only economic drivers but also address environmental impact and the reduction of carbon emissions. This information database will be widely disseminated to provide an extensive platform for future research.

在工业领域中出现的许多实际问题涉及可持续运营，满足需求和最小化成本，无法准确解决。元启发式优化技术已在学术界得到广泛发展，以解决这些问题，在文献中报道了很多成功。然而，在优化技术的科学研究和最终用户面临的问题以及商业优化软件供应商解决的问题之间仍然存在令人担忧的空白。从商业角度来看，学术界解决的问题与现实世界中面临的问题相比过于简单，未能接受许多现实世界的约束。从科学的角度来看，研究人员还发现了“商业软件中缺乏先进的元启发式技术”，部分原因是学术界未能证明他们的解决方案适用于商业世界的需求，部分原因是学术界未能向工业界传达他们的信息。Meta-启发式方法的开发成本可能很高，因为它们通常需要人类的专业知识来将专业知识集成到算法中，并且需要启发式方法的专业知识来设计和调整算法。因此，最近的研究集中在自动算法设计和配置，产生调谐的求解器，无论是个别问题或跨套件的问题。该领域的一个分支是超概率论，它在低级别概率论的空间上操作，寻找利用单个已知概率论的优点并补偿其缺点的概率论组合。由此产生的算法是廉价的实现，需要较少的人力专业知识，具有强大的性能在一个问题类，并跨问题域的便携式。与定制方法相比，这些功能弥补了解决方案质量的一些下降，同时仍然确保解决方案的质量可接受。然而，大多数自动化设计方法未能纳入或认识到人类的关键能力;人类不断从经验中学习-通过概括观察和反馈，他们能够更新其内部解决问题的模型，以不断改进它们，并适应不断变化的环境。计算求解器未能利用先前的知识既浪费了有用的知识，也可能阻碍发现好的解决方案。此外，如果域中问题实例的特征随时间而改变，则求解器可能需要完全重新调整，或者在最坏的情况下定期重新设计。我们提出了一种新的终身学习超启发式系统，解决了当前系统固有的缺陷：它将表现出短期学习，产生快速有效的解决方案，以个别问题，同时，长期的学习过程将使系统能够随着时间的推移自主适应新的问题特征。因此，它利用现有的知识，同时适应新的信息。其次，通过与两个合作者，商业路由软件供应商和林业专家密切合作，我们的研究将直接了解现实世界的问题，占真实的约束和性能标准，从而产生经济影响。优化技术的未来进步将通过开发问题生成器和一些问题套件来促进，这些问题套件反映了现实世界的优先级和约束条件，这些问题套件来自于我们的合作者提供的实际问题数据，并结合反映经济驱动因素的指标进行定义，同时也解决了环境影响和碳排放的减少。这一信息数据库将得到广泛传播，为今后的研究提供一个广泛的平台。

项目成果

Artificial Immunology for Collective Adaptive Systems Design and Implementation

• DOI: 10.1145/2897372
• 发表时间: 2016-06
• 期刊: ACM Transactions on Autonomous and Adaptive Systems (TAAS)
• 作者: Nicola Capodieci;E. Hart;Giacomo Cabri

A hybrid method for feature construction and selection to improve wind-damage prediction in the forestry sector

一种用于改进林业部门风害预测的特征构建和选择的混合方法

• DOI: 10.1145/3071178.3071217
• 发表时间: 2017
• 作者: Hart E

A real-world employee scheduling and routing application

现实世界的员工调度和路由应用程序

• DOI: 10.1145/2598394.2605447
• 发表时间: 2014
• 作者: Hart E

An improved immune inspired hyper-heuristic for combinatorial optimisation problems

• DOI: 10.1145/2576768.2598241
• 发表时间: 2014-07
• 期刊: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation
• 作者: Kevin Sim;E. Hart

For Flux Sake: The Confluence of Socially- and Biologically-Inspired Computing for Engineering Change in Open Systems

• DOI: 10.1109/fas-w.2017.119
• 发表时间: 2017-09
• 期刊: 2017 IEEE 2nd International Workshops on Foundations and Applications of Self* Systems (FAS*W)
• 作者: J. Pitt;E. Hart