一种非线性逆优化算法

An Algorithm of Nonlinear Inverse Optimization

摘要: 针对非线性逆优化问题中最优解难以显式表示、传统方法求解受限的核心挑战，本文提出一种嵌套进化逆优化算法。该算法构建参数种群与解种群双种群框架，通过随机初始化生成参数向量及对应优化子问题的初始解，利用邻域信息协同提升搜索效率；设计保护集与待更新集动态筛选机制，结合差分进化变异、交叉算子实现种群更新，同时通过非支配排序快速逼近帕累托前沿。将算法应用于逆最短路径问题验证，在7节点、15节点和25节点图上的30组实验结果表明，所提算法求得的最优权重与初始权重的欧氏距离显著小于传统方法，平均距离分别低至0.359、1.733和3.162，验证了算法在全局优化与成本控制方面的优越性。该算法为地球物理学、生产计划、路径分配等领域的非线性逆优化问题提供了高效求解方案。

Abstract: Aiming at the core challenge of nonlinear inverse optimization problems—where optimal solutions are difficult to express explicitly and traditional methods face limitations—this paper proposes a nested evolutionary inverse optimization algorithm. The algorithm constructs a dual-population framework comprising parameter and solution populations, generating initial parameter vectors and corresponding solutions for optimization subproblems through random initialization, while leveraging neighborhood information to synergistically enhance search efficiency. A dynamic screening mechanism for protection and update sets is designed, integrating differential evolution mutation and crossover operators for population updating, and rapidly approximating the Pareto frontier through non-dominated sorting. The algorithm is validated on inverse shortest path problems; results from 30 experimental groups on 7-node, 15-node, and 25-node graphs demonstrate that the Euclidean distance between optimal and initial weights obtained by the proposed algorithm is significantly smaller than that of traditional methods, with average distances as low as 0.359, 1.733, and 3.162 respectively, confirming its superiority in global optimization and cost control. This algorithm provides an efficient solution framework for nonlinear inverse optimization problems in geophysics, production planning, and path allocation.