非线性混合整数规划问题的差分进化算法研究
Research on the Differential Evolution Algorithm for Nolinear Mixed Integer Programming Problems
进化算法是源于自然界中生物进化理论的元启发式优化算法,像遗传算法、和声搜索算法和差分进化算法等.目前,这些算法已经在实际问题中得到了广泛的应用,特别是在非线性混合整数规划问题中.但是任一种算法都具有局限性,对算法的改进是有必要的.本文针对非线性混合整数规划问题,研究了差分进化算法.首先介绍了差分进化算法的起源、主要步骤、改进策略以及应用等方面的情况;然后改进了差分进化算法的参数等,提出了改进的差分进化算法;最后提出了差分遗传协同进化算法.本文的主要研究内容可归纳如下:(1)详细介绍了差分进化算法的基本情况.为后续的研究打下基础.(2)针对约束非线性混合整数规划问题,提出了一种改进的差分进化算法(IDE).算法给出了一定比例的可行解种群、基于约束矩阵的可行判别法和动态非线性缩放因子来加强寻优能力.算法应用了特殊的截断过程处理变量的整数限制和基于Deb约束规则的选择算子更新种群.试验结果表明,对比MI-LXPM算法,改进的差分进化算法成功率高,精度高.(3)研究了带约束的非线性混合整数规划问题,提出了差分遗传协同进化算法(D-GCE).首先,将带有约束的混合整数规划问题转化为无约束的双目标优化问题;其次,选择机制融合Pareto支配和可行解优先法选择优秀个体进入下一代;对于种群的连续部分,D-GCE算法使用差分进化算法进化,对于离散部分采用整数编码方式,使用遗传算法进化,有效地解决了问题中的离散整值变量和连续实值变量混合存在的问题.最后,一组24个常用的测试问题被用来测试D-GCE算法,结果显示D-GCE算法是有效的;D-GCE算法也与文献中多个算法进行了比较,结果显示D-GCE算法是具有竞争性的,在算法的质量、有效性、收敛性等方面优于其他算法.总之,本论文对两种进化算法及在非线性混合整数规划问题中的应用进行了较为全面的分析研究,并对所做工作进行了总结,提出了下一步研究的方向.
- 作者:
- 吴军
- 学位授予单位:
- 北方民族大学
- 专业名称:
- 计算数学
- 授予学位:
- 硕士
- 学位年度:
- 2014年
- 导师姓名:
- 高岳林
- 中图分类号:
- TP18
- 关键词:
- 混合整数规划;差分进化;遗传算法;协同进化;约束优化
- Mixed Integer Programming;Differential Evolution;GeneticAlgorithm;Co-Evolution;Constrained Optimization