昂贵优化问题(Expensive Optimization Problem，EOP)是指在评估待选解决方案时，需要付出昂贵甚至难以承担的成本的一类最优化问题。随着社会的不断进步，以及智慧城市、物联网、大数据时代等带来的新兴挑战，更高效地解决EOP问题正成为推动各领域繁荣发展的必要条件。进化计算是一种模拟自然进化现象和生物群体智能行为来求解问题的启发式优化方法，被广泛应用于求解EOP问题。华南理工大学詹志辉教授团队系统全面地综述了面向昂贵优化的进化计算方法，充分回顾和分析如何发展与利用进化计算方法，以高效解决复杂的EOP问题。相关成果发表于Machine Intelligence Research第一期中，全文免费下载。

图片来自Springer

昂贵优化问题(EOP)是指在评估待选解决方案时，需要付出昂贵甚至难以承担的成本的一类最优化问题，这类问题广泛存在于许多重要的实际应用场景中。

昂贵一方面可以指评估本身需要耗费大量的时间、算力、金钱等昂贵成本，另一方面也包括一些在普通情况下评估成本不算昂贵的问题在特定情况下变得昂贵了。

例如，当遭遇疫情暴发或自然灾害等紧急情况时，运输和调度等优化问题的解决能为日常运营和拯救生命提供保障，是紧迫且至关重要的。尽管在正常情况下对这些问题的待选解进行评估的时间成本可能是不昂贵的，但是若在紧急情况下还需要原来的时间成本就会使得评估过程变得十分昂贵、甚至难以接受。因此，随着现实社会的不断进步，以及智慧城市、物联网、大数据时代等带来的新兴挑战，更高效地解决EOP问题正成为推动各领域繁荣发展的必要条件。

昂贵优化问题和相关优化问题的关系

(图片来自论文)

然而，由于评估待选解的成本高昂，基于暴力搜索、随机搜索等的优化算法很难搜索到可以解决EOP问题的满意解。为此，进化计算被广泛应用于解决EOP问题，进而带动该领域的研究蓬勃发展起来。

一般而言，进化计算是模拟自然进化现象和生物群体智能行为来求解问题的启发式优化方法，具有可观察、可理解、可解释、可调控等优势，是人工智能和机器智能最前沿的研究方向之一。常见的进化计算算法包括进化算法(EA)和群体智能算法(SI)，前者主要包括遗传算法(GA)和差分进化(DE)，后者主要包括粒子群优化(PSO)和蚁群优化(ACO)。

基于自然进化中“适者生存”的思想，进化计算方法通过相应的进化算子或群体操作生成新的个体，并选择适应度好的个体作为新的种群进入下一代。因此，进化计算可以在不需要梯度信息的情况下高效找到满意的解，非常适合求解实际问题。

进化计算流程图

(图片来自论文)

迄今为止，不少研究聚焦于解决EOP问题的进化计算方法，并取得了相当大的成功。然而，这些研究工作仍然分散于文献之中，有待进行系统全面的整合。因此，鉴于该研究领域的快速发展和取得的重要成果，对此前相关研究进行回顾就显得十分必要。通过综述前人研究发现、提供研究参考，可以更好地促进相关领域研究的发展。

为此，本文试图给出一个系统且全面的综述，充分回顾和分析如何利用与发展进化计算方法，以高效地解决复杂的EOP问题。

为了更简洁、清晰地进行重点性的综述，本文在选择相关文献时重点考虑文献来源于高水平学术期刊和学术会议、出版于不同年份并聚焦于近几年、具有较高引用和影响力，同时力求这些文献覆盖本文综述主题的三个不同研究方向。总体而言，本文的主要贡献如下：

首先，本文从数学角度分析了使用进化计算方法求解EOP问题的总昂贵成本。而后，在分析的基础上给出了降低总成本的三个方向，包括通过问题代理与替换来降低单次评估成本、通过算法设计与改进来减少总体评估次数和通过并行与分布式计算来减少整体运行时间。

降低优化成本的三个方向

(图片来自论文)

其次，引入系统分类法，系统且结构性地综述了现有研究在如何通过上述三个方向来有效并高效解决EOP问题上做出的努力。

分类法图解

(图片来自论文)

第三，本文探究并讨论了使用进化计算解决EOP问题在未来可能的研究方向和一些有待解决的议题。

未来研究方向

(图片来自论文)

Evolutionary Computation for Expensive Optimization: A Survey

Jian-Yu Li, Zhi-Hui Zhan, Jun Zhang

https://link.springer.com/article/10.1007/s11633-022-1317-4

Abstract: Expensive optimization problem (EOP) widely exists in various significant real-world applications. However, EOP requires expensive or even unaffordable costs for evaluating candidate solutions, which is expensive for the algorithm to find a satisfactory solution. Moreover, due to the fast-growing application demands in the economy and society, such as the emergence of the smart cities, the internet of things, and the big data era, solving EOP more efficiently has become increasingly essential in various fields, which poses great challenges on the problem-solving ability of optimization approach for EOP. Among various optimization approaches, evolutionary computation (EC) is a promising global optimization tool widely used for solving EOP efficiently in the past decades. Given the fruitful advancements of EC for EOP, it is essential to review these advancements in order to synthesize and give previous research experiences and references to aid the development of relevant research fields and real-world applications. Motivated by this, this paper aims to provide a comprehensive survey to show why and how EC can solve EOP efficiently. For this aim, this paper firstly analyzes the total optimization cost of EC in solving EOP. Then, based on the analysis, three promising research directions are pointed out for solving EOP, which are problem approximation and substitution, algorithm design and enhancement, and parallel and distributed computation. Note that, to the best of our knowledge, this paper is the first that outlines the possible directions for efficiently solving EOP by analyzing the total expensive cost. Based on this, existing works are reviewed comprehensively via a taxonomy with four parts, including the above three research directions and the real-world application part. Moreover, some future research directions are also discussed in this paper. It is believed that such a survey can attract attention, encourage discussions, and stimulate new EC research ideas for solving EOP and related real-world applications more efficiently.

▽ 关于Machine Intelligence Research

Machine Intelligence Research（简称MIR，原刊名International Journal of Automation and Computing）由中国科学院自动化研究所主办，于2022年正式出版。MIR立足国内、面向全球，着眼于服务国家战略需求，刊发机器智能领域最新原创研究性论文、综述、评论等，全面报道国际机器智能领域的基础理论和前沿创新研究成果，促进国际学术交流与学科发展，服务国家人工智能科技进步。期刊入选"中国科技期刊卓越行动计划"，已被Ei Compendex, Scopus, 中国科技核心期刊、CSCD等数据库收录。

​征稿启事：

MIR | AI 领域新刊启航，诚向广大科技工作者征稿啦