Development and Analysis of Metaheuristics for Challenging Large-Scale Optimization Problems

用于解决大规模优化问题的元启发法的开发和分析

• 批准号: RGPIN-2022-05418
• 负责人: OmbukiBerman, Beatrice
• 金额: $ 1.75万
• 依托单位: Brock University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749886
• 关键词: Development; Analysis; Metaheuristics; Challenging; Large

The benefits of optimization can be observed in almost all aspects of life, from science, healthcare, economics, to engineering problems. Important problems in these areas are computationally intractable by exact methods. My research uses computational intelligence, a branch of artificial intelligence to solve problems that are either too challenging or impossible to solve using conventional optimization methods. Specifically, I use algorithms that simulate the emergent behaviour of flocking birds (particle swarm optimization, PSO) and evolutionary algorithms (EAs) inspired by Darwinian evolution and population genetics: I use biological processes such as selection, crossover, and mutation to quickly find solutions that are acceptable in practice, or "near perfect" where the optimal solution may require a lifetime to compute. The majority of real-world optimization problems involve simultaneous optimization of two or more, often conflicting objectives, e.g., minimizing transportation costs while maximizing safety and efficiency; this is called a multi-objective optimization problem (MOP). The successes in the role played by optimizing algorithms based on EAs and PSOs, among other metaheuristics in solving MOPs are well documented. Increasingly we are faced with problems that have more than three objectives, i.e., a special case of MOPs, termed many-objective optimization problems (MaOPs). However, the performance of the aforementioned algorithms deteriorates severely with increase in the number of objectives (beyond three) and the number of problem dimensions or decision variables, i.e., for large-scale many-objective optimization problems, which present new challenges for optimization techniques. The proposed research will tackle efficient algorithm design, solution evaluation, and data/algorithm activity visualizations that have not been adequately addressed for MaOPs. Both well-known benchmark functions for MaOPs and large-scale real-world optimization problems arising in network science, such as finding critical nodes in complex networks, will be investigated. The critical node detection problem has many practical applications: e.g., targeting specific proteins in protein interaction networks for use in drug design, in computer network security so as to protect or attack important areas, in determining smart grid vulnerability, and in identifying individuals for vaccination or quarantine when mitigating disease spread. Providing efficient algorithmic solutions for important problems, and by improving our understanding of appropriate algorithms and techniques for different classes of challenging optimization problems, this research will benefit many researchers and practitioners that utilize optimization across different domains. I will involve graduate and senior undergraduate students to find cutting-edge solutions to challenging optimization problems and to advance the theoretical aspects and development of EAs and PSOs.

优化的好处可以在生活的几乎所有方面观察到，从科学，医疗保健，经济学到工程问题。在这些领域的重要问题是计算棘手的精确方法。我的研究使用计算智能，人工智能的一个分支来解决那些太具挑战性或无法使用传统优化方法解决的问题。具体来说，我使用的算法模拟集群鸟类的紧急行为（粒子群优化，PSO）和进化算法（EA）的灵感来自达尔文进化论和种群遗传学：我使用生物过程，如选择，交叉和突变，以快速找到解决方案，在实践中是可以接受的，或“接近完美”的最佳解决方案可能需要一生的计算。大多数现实世界的优化问题涉及两个或更多个经常冲突的目标的同时优化，例如，最小化运输成本，同时最大化安全和效率;这被称为多目标优化问题（MOP）。基于EA和PSO的优化算法在解决MOPs中所扮演的角色以及其他元算法的成功都有很好的记录。我们越来越多地面临具有三个以上目标的问题，即，MOPs的一种特殊情况，称为多目标优化问题（MaOP）。然而，上述算法的性能随着目标数量（超过三个）和问题维度或决策变量的数量的增加而严重恶化，即，对于大规模多目标优化问题，这对优化技术提出了新的挑战。拟议的研究将解决有效的算法设计，解决方案评估和数据/算法活动可视化尚未充分解决的MaOP。将研究MaOP的著名基准函数和网络科学中出现的大规模现实世界优化问题，例如在复杂网络中找到关键节点。关键节点检测问题具有许多实际应用：例如，针对蛋白质相互作用网络中的特定蛋白质，用于药物设计、计算机网络安全以保护或攻击重要区域、确定智能电网脆弱性以及在减轻疾病传播时识别接种疫苗或检疫的个人。为重要问题提供有效的算法解决方案，并通过提高我们对不同类别的具有挑战性的优化问题的适当算法和技术的理解，这项研究将使许多研究人员和实践者受益，利用不同领域的优化。我将让研究生和高年级本科生参与进来，为具有挑战性的优化问题找到最前沿的解决方案，并推进EA和PSO的理论方面和发展。