Rigorous Runtime Analysis of Nature Inspired Meta-heuristics
自然启发式元启发法的严格运行时分析
基本信息
- 批准号:EP/H028900/1
- 负责人:
- 金额:$ 33.67万
- 依托单位:
- 依托单位国家:英国
- 项目类别:Fellowship
- 财政年份:2010
- 资助国家:英国
- 起止时间:2010 至 无数据
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
A rigorous runtime analysis of different nature inspired meta-heuristics will be analysed in this projectin order to gain a deeper understanding of when and why a given meta-heuristic is expected to perform well or poorly. Various nature inspired meta-heuristics have been applied successfully to combinatorial optimisation in many scientific fields.However, their computational complexity is far from being understood in depth. It is still unclear how powerfulthey are for solving combinatorial optimisation problems, and where their real power is in comparison with the more traditional deterministic algorithms.Evolutionary Algorithms (EAs), Ant Colony Optimisation (ACO) and Artificial Immune System (AIS) algorithms will be studied in this project.Since the knowledge level of their computational complexity is at very different stages, two different types of results will be produced.One is the computational complexity results of realistic EAs, not (1+1)-EAs, on selected well-known combinatorial optimisation problems. A setup of complexity classes will be built revealing what classes of problems are hard (or easy) for which kind of EAs.The other is a setup of the first basis for a systematic computational complexity analysis of ACO and AIS other popular nature inspired meta-heuristics for which very few runtime results are available.The expected outcomes of this project will not only provide a solid foundation, but also insights and guidance in understandingwhich meta-heuristic should be preferred for a given problem and in the design of more efficient variants.
本文将对不同性质的元启发式进行严格的运行时分析,以便更深入地了解给定的元启发式何时以及为什么会表现良好或较差。各种自然启发的元启发式已经成功地应用于许多科学领域的组合优化。然而,它们的计算复杂性还远远没有被深入了解。目前还不清楚它们在解决组合优化问题方面有多强大,以及与更传统的确定性算法相比,它们的真正力量在哪里。本项目将研究进化算法(EAs)、蚁群优化(ACO)和人工免疫系统(AIS)算法。由于它们的计算复杂性的知识水平处于非常不同的阶段,因此会产生两种不同类型的结果。一个是实际ea的计算复杂度结果,而不是(1+1)- ea,选择已知的组合优化问题。将构建一个复杂性类的设置,揭示哪类问题对哪类ea来说是困难的(或容易的)。另一个是为ACO和AIS的系统计算复杂性分析的第一个基础设置,其他流行的自然启发的元启发式,很少有运行时结果可用。这个项目的预期结果不仅提供了一个坚实的基础,而且还提供了见解和指导,以理解对于给定的问题应该优先使用哪种元启发式方法,并设计更有效的变体。
项目成果
期刊论文数量(10)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Approximating vertex cover using edge-based representations
- DOI:10.1145/2460239.2460248
- 发表时间:2013-01
- 期刊:
- 影响因子:0
- 作者:T. Jansen;P. S. Oliveto;C. Zarges
- 通讯作者:T. Jansen;P. S. Oliveto;C. Zarges
On Easiest Functions for Somatic Contiguous Hypermutations And Standard Bit Mutations
关于体细胞连续超突变和标准位突变的最简单函数
- DOI:
- 发表时间:2015
- 期刊:
- 影响因子:0
- 作者:Corus Dogan
- 通讯作者:Corus Dogan
Applications of Evolutionary Computation
进化计算的应用
- DOI:10.1007/978-3-642-20520-0_23
- 发表时间:2011
- 期刊:
- 影响因子:0
- 作者:Colton S
- 通讯作者:Colton S
Parallel Problem Solving from Nature, PPSN XI
自然并行问题解决,PPSN XI
- DOI:10.1007/978-3-642-15844-5_39
- 发表时间:2010
- 期刊:
- 影响因子:0
- 作者:Reynolds A
- 通讯作者:Reynolds A
Escaping Local Optima Using Crossover With Emergent Diversity
- DOI:10.1109/tevc.2017.2724201
- 发表时间:2018-08-01
- 期刊:
- 影响因子:14.3
- 作者:Dang, Duc-Cuong;Friedrich, Tobias;Sutton, Andrew M.
- 通讯作者:Sutton, Andrew M.
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Pietro Oliveto其他文献
Pietro Oliveto的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Pietro Oliveto', 18)}}的其他基金
Rigorous Runtime Analysis of Bio-Inspired Computing
仿生计算的严格运行时分析
- 批准号:
EP/M004252/1 - 财政年份:2015
- 资助金额:
$ 33.67万 - 项目类别:
Fellowship
相似海外基金
Rigorous and Efficient Library Compatibility Verification Method based on Runtime Information Analysis of Used Functions
基于所用函数运行时信息分析的严谨高效的库兼容性验证方法
- 批准号:
22K21279 - 财政年份:2022
- 资助金额:
$ 33.67万 - 项目类别:
Grant-in-Aid for Research Activity Start-up
CAREER: A Runtime for Fast Data Analysis on Modern Hardware
职业:现代硬件上快速数据分析的运行时
- 批准号:
1651570 - 财政年份:2017
- 资助金额:
$ 33.67万 - 项目类别:
Continuing Grant
Using GPUs for runtime monitoring and trace analysis
使用 GPU 进行运行时监控和跟踪分析
- 批准号:
479865-2015 - 财政年份:2016
- 资助金额:
$ 33.67万 - 项目类别:
Collaborative Research and Development Grants
Rigorous Runtime Analysis of Bio-Inspired Computing
仿生计算的严格运行时分析
- 批准号:
EP/M004252/1 - 财政年份:2015
- 资助金额:
$ 33.67万 - 项目类别:
Fellowship
Using GPUs for runtime monitoring and trace analysis
使用 GPU 进行运行时监控和跟踪分析
- 批准号:
479865-2015 - 财政年份:2015
- 资助金额:
$ 33.67万 - 项目类别:
Collaborative Research and Development Grants
SHF: Small: Detecting and Mitigating Smartphone Energy Bugs using Compiler and Runtime Analysis
SHF:小型:使用编译器和运行时分析检测和缓解智能手机能源错误
- 批准号:
1320764 - 财政年份:2013
- 资助金额:
$ 33.67万 - 项目类别:
Standard Grant
Analysis of Runtime Profiles of R Code
R 代码运行时概况分析
- 批准号:
450062-2013 - 财政年份:2013
- 资助金额:
$ 33.67万 - 项目类别:
University Undergraduate Student Research Awards
TC: Small: Runtime and Static Analysis for Web Application Security
TC:小型:Web 应用程序安全的运行时和静态分析
- 批准号:
0917392 - 财政年份:2009
- 资助金额:
$ 33.67万 - 项目类别:
Standard Grant
STTR Phase I: Safety-Centric Analysis and Runtime Monitoring for Plug-and-Play Medical Suites
STTR 第一阶段:即插即用医疗套件的以安全为中心的分析和运行时监控
- 批准号:
0712298 - 财政年份:2007
- 资助金额:
$ 33.67万 - 项目类别:
Standard Grant
Experimental runtime complexity analysis of logic programs
逻辑程序的实验运行时复杂度分析
- 批准号:
DP0209846 - 财政年份:2002
- 资助金额:
$ 33.67万 - 项目类别:
Discovery Projects