学术研究报告：改进遗传算法在非线性规划问题中的应用

一、研究作者及发表信息
本研究的作者为Kezong Tang（第一作者兼通讯作者）、Jingyu Yang、Haiyan Chen（均来自南京理工大学计算机科学与技术学院）以及Shang Gao（江苏科技大学计算机科学与工程学院）。论文标题为《Improved Genetic Algorithm for Nonlinear Programming Problems》，发表于《Journal of Systems Engineering and Electronics》2011年6月第22卷第3期（页码540–546）。

二、学术背景与研究目标
本研究属于计算智能与优化算法领域，聚焦于非线性规划（Nonlinear Programming, NLP）问题的求解。NLP问题的核心在于寻找满足约束条件的最优解，其目标函数和约束通常为非线性形式，传统方法（如罚函数法）需手动调整罚因子，易陷入局部最优或计算效率低下。遗传算法（Genetic Algorithm, GA）因其全局搜索能力被广泛应用于此类问题，但传统GA在个体选择策略上存在局限性，例如忽略不可行解邻域的潜在可行解。

本研究的目标是提出一种改进遗传算法（Improved Genetic Algorithm, IGA），通过以下创新提升性能：
1. 新型选择策略：将个体特征量化为三维向量（目标函数值、约束违反程度、约束违反数量），以更精准地区分优劣个体；
2. 局部搜索（Local Search, LS）机制：在不可行解邻域内搜索潜在可行解，增强种群多样性。

三、研究方法与流程
1. 算法框架设计
- 初始种群生成：随机生成200个个体（q=200），初始化外部集合（External Set, ES）用于存储非支配解。
- 特征向量定义：每个个体x的特征向量v(x)=(f, p, s)，其中f为目标函数值，p为约束违反程度（公式2），s为约束违反数量（公式4）。
- 支配关系判定：通过强度值（iv，个体支配其他个体的数量）和支配计数（dc，被其他个体支配的数量）比较个体优劣（定义4-5）。

1. 选择策略

   • 四类比较场景：
     
     • 双方可行：比较iv值；
       
     • 一方可行：可行解优先；
       
     • 双方不可行：比较特征向量；
       
     • 不可比不可行解：选择dc较小者。
       
   • 局部搜索（LS）：对不可行解邻域生成临时子集（TS，大小ls=30），通过改进差分进化变异（公式9）生成新解，若优于ES或当前种群则替换。
     

2. 遗传操作

   • 交叉与变异：采用离散交叉（交叉率0.6）和高斯变异（变异率1/n，n为变量数）。
     
   • 种群更新：每代从当前种群随机选择20个个体（u=20），生成40个子代（η=2），经选择后替换旧种群。
     

3. 实验验证

   • 测试问题：选用5个标准NLP问题（g1–g5），涵盖等式与不等式约束。
     
   • 对比算法：Pareto强度进化算法（ZW）、随机排序算法（RY）和同态映射法（KM）。
     
   • 评估指标：最优解误差、平均解误差、最差解误差及成功率（100次运行）。
     

四、主要结果
1. 性能优势
- 最优解精度：IGA在g1、g4、g5中均达到理论最优（误差<0.0001%），优于ZW、RY和KM（表2）。例如，g4的平均解误差为0，而ZW为0.02776%。
- 鲁棒性：g4的成功率100%（表3），显著高于ZW（46%）和RY（15%）。
- 计算效率：IGA求解时间普遍低于对比算法（如g2仅需31.04秒）。

1. 局部搜索的贡献
   
   • LS机制使IGA在不可行解邻域发现可行解，如g3的均值误差仅0.00003%，而KM因忽略邻域搜索导致误差达0.37464%。
     

五、结论与价值
1. 科学价值
- 提出基于特征向量和支配关系的选择策略，为约束优化问题提供通用评估框架；
- 结合LS的IGA突破了传统GA仅依赖可行解的局限，提升了搜索效率与多样性。

1. 应用价值
   
   • 可扩展至组合优化（如旅行商问题）和多目标优化领域；
     
   • 在工程优化（如资源分配、调度）中具有潜在应用前景。
     

六、研究亮点
1. 方法创新：首次将三维特征向量与局部搜索结合，平衡解的质量与多样性；
2. 实验验证：通过多基准问题验证IGA的普适性，结果显著优于现有算法；
3. 理论贡献：重新定义个体支配关系，为约束处理提供新思路。

七、其他价值
作者指出未来可将IGA与粒子群优化（PSO）、蚁群算法（ACO）等混合，进一步拓展其应用范围。这一方向对复杂优化问题的求解具有重要启示意义。