SEQuence-Analysis Based Hyperheuristics (SEQAH) for Real-World Optimisation Problems

针对现实世界优化问题的基于序列分析的超启发式 (SEQAH)

• 批准号: EP/K000519/1
• 负责人: Edward Keedwell
• 金额: $ 32.68万
• 依托单位: UNIVERSITY OF EXETER
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2012
• 资助国家: 英国
• 起止时间: 2012 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FK000519%2F1
• 关键词: SEQuence; Analysis; Based; Hyperheuristics; SEQAH

Selective hyperheuristics are a set of optimisation techniques that effectively optimise the search algorithm during an optimisation run by selecting combinations of lower level heuristic operations (e.g. mutation, crossover & replication). They operate at the level above metaheuristics (e.g. evolutionary algorithms) and are thus able to react to changes in the search space by modifying the heuristics that are applied to the search problem. Traditional selective hyperheuristics consider single heuristics and heuristic pair performance when determining the heuristic to select next. This project will develop new methods known as a sequence analysis based hyperheuristics (SEQAH) and will investigate the use of sequence analysis techniques, taken from other computational domains such as bioinformatics and natural-language processing, to determine heuristic selection. SEQAH methods will record the search process as a sequence of pairs of heuristic application and performance, and will process this information to inform the selection of the next heuristic to apply in the optimisation. This will allow the technique to automatically select the best heuristics to apply for a given problem - effectively tuning the algorithm to new optimisation problem types, regardless of the underlying application area. By selecting from a set of heuristics, the SEQAH techniques can combine ordinary heuristic operations (e.g. mutation and crossover) with more problem-specific heuristics such as human-designed 'rules-of-thumb' into one coherent algorithm that is able to generate near-optimal solutions in less computational time.The developed techniques will be tested on problems from the literature and a suite of real-world problems in water distribution optimisation including the design, rehabilitation and operation of large-scale water systems. The optimisation of these systems has the potential to offer improved services in terms of reliability and water quality and to reduce the future cost and environmental impact of providing clean, safe drinking water to homes across the country. The SEQAH technique also has the potential to extend beyond the water industry and should be applicable to any number of optimisation problems in many application areas due to its ability to adapt to new problem spaces online.

选择性超启发式是一组优化技术，可在优化运行期间通过选择较低级别启发式操作（例如变异、交叉和复制）的组合来有效优化搜索算法。它们在元启发法（例如进化算法）之上的级别上运行，因此能够通过修改应用于搜索问题的启发法来对搜索空间的变化做出反应。传统的选择性超启发式在确定下一步选择的启发式时会考虑单个启发式和启发式对的性能。该项目将开发基于超启发式序列分析 (SEQAH) 的新方法，并将研究使用来自生物信息学和自然语言处理等其他计算领域的序列分析技术来确定启发式选择。 SEQAH 方法将搜索过程记录为启发式应用和性能对的序列，并将处理此信息以通知选择要在优化中应用的下一个启发式。这将使该技术能够自动选择适用于给定问题的最佳启发式方法 - 有效地将算法调整为新的优化问题类型，而不管底层应用领域如何。通过从一组启发式中进行选择，SEQAH 技术可以将普通的启发式操作（例如变异和交叉）与更多针对具体问题的启发式（例如人类设计的“经验法则”）结合成一个连贯的算法，能够在更短的计算时间内生成接近最优的解决方案。所开发的技术将针对文献中的问题和一系列配水方面的实际问题进行测试 优化，包括大型供水系统的设计、修复和运行。这些系统的优化有可能在可靠性和水质方面提供改进的服务，并降低未来为全国各地家庭提供清洁、安全饮用水的成本和环境影响。 SEQAH 技术还具有扩展到水行业之外的潜力，并且由于其能够在线适应新的问题空间，因此应该适用于许多应用领域中的任意数量的优化问题。

项目成果

Sequence Analysis-based Hyper-heuristics for Water Distribution Network Optimisation

基于序列分析的超启发式供水管网优化

• DOI: 10.1016/j.proeng.2015.08.993
• 发表时间: 2015
• 期刊: Procedia Engineering
• 作者: Kheiri A

A general multi-objective hyper-heuristic for water distribution network design with discolouration risk

具有变色风险的配水管网设计的通用多目标超启发式

• DOI: 10.2166/hydro.2012.022
• 发表时间: 2013
• 期刊: Journal of Hydroinformatics
• 影响因子: 2.7
• 作者: Randall-Smith M

An analysis of the interface between evolutionary algorithm operators and problem features for water resources problems. A case study in water distribution network design

水资源问题的进化算法算子与问题特征之间的接口分析。

• DOI: 10.1016/j.envsoft.2014.12.023
• 发表时间: 2015
• 期刊: Environmental Modelling & Software
• 影响因子: 4.9
• 作者: McClymont K

A Hidden Markov Model Approach to the Problem of Heuristic Selection in Hyper-Heuristics with a Case Study in High School Timetabling Problems

超启发式启发式选择问题的隐马尔可夫模型方法及其高中时间表问题的案例研究

• DOI: 10.1162/evco_a_00186
• 发表时间: 2017
• 期刊: Evolutionary Computation
• 影响因子: 6.8
• 作者: Kheiri A

A Sequence-based Selection Hyper-heuristic Utilising a Hidden Markov Model

利用隐马尔可夫模型的基于序列的选择超启发式

• DOI: 10.1145/2739480.2754766
• 发表时间: 2015
• 作者: Kheiri A