启发式优化算法在几类典型优化问题中的应用

摘要

关于启发式优化算法及应用的研究近年来受到人们的广泛关注，并获得了良好的实际效果。本文对差分进化算法、粒子群优化算法、和声搜索算法及其应用进行了研究，主要工作如下: (1)为克服已有二进制和声搜索算法的缺陷，提出了适于求解大规模0-1背包问题的简化二进制和声搜索算法(SBHS)。首先，设计了一种基于和声记忆库差异信息的无参数和声创作模式，该模式不再依赖音调微调概率(PAR)和音调微调幅度(bw)，无需任何参数即可创作出新的和声向量，大大减轻了参数设定的困难。其次，参数和声记忆库考虑概率(HMCR)被设计成了随问题维数动态调整的形式，使得SBHS算法适于求解各种类型的问题。再次，深入研究了0-1背包问题的特性，提取出特殊的启发式信息，以引导算法在不可行解附近进行局部搜索，找到质量更高的可行解。所提出的修复策略既能保证解的可行性，同时能够提高算法的收敛速度和收敛精度。最后，以多组低维和高维0-1背包问题作为测试函数进行对比实验，结果表明SBHS算法无论在精度、收敛速度还是鲁棒性上均优于近期提出的改进和声搜索算法。 (2)针对和声搜索算法做更进一步的研究，提出了一种有效求解多维0-1背包(MKP)问题的新和声搜索算法(NBHS)。与传统求解连续问题的和声搜索算法不同，NBHS算法对和声搜索算法的框架进行了调整，使其能够适应离散问题的特性。与其他和声搜索算法相比，所提NBHS算法主要有以下4点不同:①相比于连续浮点编码，NBHS算法采用了更切合离散问题的二进制编码方法;②NBHS算法在进行和声记忆库考虑时，不再考虑自变量的具体数值，而是重点关注数值的概率分布情况，同时提出一种动态的自适应调整方式来确定参数HMCR的值，使其更加适合搜索过程的需要;③NBHS算法设计了一种新的音调微调策略，该策略无需其他和声搜索算法中使用的音调微调概率(PAR)以及音调微调幅度(bw)两个参数，仅根据和声记忆库中的两个随机和声即可创作出新和声;④基于MKP问题的特殊性，NBHS算法提出了一种简单但有效的修复策路，保证和声的可行性，以此增强算法的开发能力和收敛速度。在两组大规模MKP问题上进行了大量的仿真实验，结果表明NBHS算法的性能优于现有的先进算法，是求解MKP问题的有利选择。 (3)认真研究了粒子群算法在整数规划问题中应用，并以冗余策略可选择的冗余分配问题(RAP-MSC)作为实际应用背景。RAP-MSC将每个子系统使用的冗余策略作为额外的变量来看待，增加了模型的实用性，但急剧扩张的搜索空间也给问题的求解带来了很大困难，尤其是大型系统。为改善求解方法缺乏的现状，提出一种简化的粒子群优化算法(SPSO)，用以求解这个NP难问题。SPSO算法舍弃了速度更新公式，以消除早期速度对搜索的不良影响，同时设计了一种带随机扰动的新位置更新方法。此外，还提出了一个新的部分连接的动态随机拓扑结构，引导粒子间的交流以及粒子的运动，以便更好的均衡局部搜索和全局搜索。与诸多PSO算法以及现有求解算法的大量对比实验表明，SPSO算法明显优于这些对比算法，可以作为复杂RAP-MSC问题的高效求解工具。 (4)根据李普希兹条件提出一种基于预测的约束处理方法，继而提出基于约束预测的自适应分组差分进化算法(AGDE)。该算法在处理约束时不直接计算约束值，而是进行简单的预测，然后进行处理。在约束条件较复杂时，大大减少因计算约束值带来的计算量，同时最大程度的保持解的可行性。对差分进化算法进行改进，为其设计新的差分变异算子，在最优解搜索的过程中，根据种群的动态信息实时的自适应调整交叉率与变异率，使其适应种群进化的需要，提高算法的收敛速度和精度。四组对比实验的结果表明约束预测方法及算法改进是可行的、有效的，能较好地解决约束优化问题。

目录

声明

摘要

1．1研究背景及意义

1．2几种典型启发式优化算法的研究现状

1．2．1差分进化算法

1．2．2粒子群优化算法

1．2．3和声搜索算法

1．3本文主要工作

第2章和声搜索算法在0-1背包问题中的应用

2．1 0-1背包问题及其研究现状

2．2基本和声搜索算法

2．3求解0-1优化问题的典型改进和声搜索算法

2．3．1二进制编码的和声搜索算法

2．3．2离散二进制和声搜索算法

2．3．3新颖和声搜索算法

2．3．4自适应二进制和声搜索算法

2．4简化二进制和声搜索算法(SBHS)

2．4．1新的和声创作模式

2．4．2用于修复不可行解的两阶段贪婪策略

2．4．3参数的自适应调整策略

2．4．4 SBHS算法的具体流程

2．5实验结果与分析

2．5．1实验设计

2．5．2在低维0-1背包问题上的对比实验

2．5．3在高维0-1背包问题上的对比实验

2．5．4鲁棒性及收敛性分析

2．6本章小结

第3章和声搜索在多维0-1背包问题中的应用

3．1多维0-1背包问题(MKP)

3．2 MKP问题的研究现状

3．3求解MKP问题的新二进制和声搜索算法(NBHS)

3．3．1和声的编码方法

3．3．2新颖的基于概率分布的和声记忆库考虑策略

3．3．3无参数的新颖音调微调策略

3．3．4基于新启发式信息的不可行解修复策略

3．3．5参数的自适应调整策略

3．3．6所提NBBS算法的工作流程

3．4实验结果与对比分析

3．4．1参数对NBHS算法性能的影响

3．4．2 NBHS算法与QIHS算法的性能比较

3．4．3 NBHS算法与其他算法在测试集1上的性能比较

3．4．4 NBHS算法与HEDA算法在测试集2上的进一步比较

3．4．5算法复杂度分析与讨论

3．5本章小结

第4章粒子群优化算法在整数规划中的应用

4．1引言

4．2冗余策略可选择的冗余分配问题

4．2．1建模前的一些假设

4．2．2建模中用到的符号

4．2．3系统可靠性模型

4．2．4系统可靠性的近似计算

4．3基本粒子群优化算法

4．4简化粒子群优化算法(SPSO)

4．4．1解的编码方法

4．4．2约束处理和目标函数

4．4．3新的动态随机拓扑结构

4．4．4新的粒子运动方程

4．5对比实验与分析

4．5．1 SPSO算法的参数分析

4．5．2 SPSO算法与现有RAP-MSC求解算法的对比

4．5．3 SPSO算法与其他PSO算法的对比

4．6本章小结

第5章差分进化算法在约束优化问题中的应用

5．1引言

5．2常用的约束处理方法

5．2．1罚函数法

5．2．2多目标转化法

5．2．3非典型方法

5．3基于预测的约束处理方法

5．3．1基本思想

5．3．2约束的预测与处理

5．4基本差分进化算法

5．5基于约束预测的自适应分组差分进化算法(AGDE)

5．5．1种群的聚类与新变异算子的提出

5．5．2参数的选择与自适应调整

5．5．3算法流程

5．6实验结果及分析

5．6．1与现有DE算法在无约束优化问题上的比较

5．6．2与其他算法在无约束优化问题上的比较

5．6．3约束预测方法与罚函数法在约束优化问题上的比较

5．6．4 AGDE算法与其他算法在约束优化问题上的比较

5．7本章小结

6．1结论

6．2展望

参考文献

致谢

攻读学位期间发表的论著及获奖情况