求解多目标无约束二元二次规划问题的元启发式算法研究

发布时间：2020-05-12 15:38

【摘要】：多目标优化作为运筹优化的一个重要分支,主要研究多个目标值同时最优化的问题,在计算机科学、人工智能、金融分析及其他学科和工程领域中,都存在非常广泛的应用。现实世界中的许多问题都可以应用组合优化的方法来解决,而这些问题往往存在相互冲突的目标需要同时优化,为了达到最佳的优化结果,往往需要对各个目标进行折衷。无约束二元二次规划问题,作为一类经典的组合优化问题,一直以来都是研究的热点之一,学术界相继提出了精确算法、启发式算法和元启发式算法。由于无约束二元二次规划问题的NP-难本质,导致精确算法往往无法在可接受的时间内得到满意解,因此,近年来学术界的研究重点集中在启发式和元启发式算法上。由于传统优化方法的不足,学术界近年来提出了许多智能优化方法,比如禁忌搜索算法、遗传算法、蚁群优化算法、模拟退火算法和粒子群优化算法等。这些优化算法更看重计算的速度和效率,不追求得到最优解。本论文以超体积贡献度选择算法框架为基础,分别结合遗传算法和混合扰动策略,提出基于均匀交叉算子的多目标进化算法、基于多父代组合算子的多目标进化算法和基于混合扰动策略的多目标优化算法来求解双目标情形下的无约束二元二次规划问题。其中,超体积贡献度选择算法来为个体进行适应值分配,从而解决多目标情形下的个体优劣判别。在算法陷入局部最优时,通过遗传算法中的交叉组合算子与变异操作来产生质量较高且多样性丰富的子集,从而扩展搜索空间,达到跳出局部最优的目的。混合扰动策略则通过交替地采用禁忌扰动与随机扰动来改变个体的取值来得到得到多样性丰富的解集。在标准算例上的实验测试表明,本论文所提出的算法相比于迭代局部搜索算法、基于二元指标的多目标局部搜索算法和基于超体积指标的多目标局部搜索算法具有较为显著的优越性。
【图文】：

图 2-2 Pareto 最优解及 Pareto 前沿示意图[18,19]集。在单目标优化问题中，存在天然的全序关系，可以很自然的对每个解进而在多目标优化问题中，这样的天然全序关系并不存在。因此，在求解多问题时，我们往往关注的不是一个帕累托最优解，而是一个帕累托最优解 多目标优化问题的处理方法自从多目标优化问题提出以来，多目标优化算法也得到了飞速发展to 最优理论应用到多目标优化问题之前，多目标优化算法的一般做目标通过一定的方式转化为单目标进行求解，代表性方法有基于聚Aggregation Selection)、目标向量法 (Target-vector Approaches) 及字典排xicographic Ordering) 等。这类方法将多目标问题的多个优化目标通过特定成可以被单目标优化算法处理的形式，每次只能得到一种权值情况下的除此之外, 传统的数学规划方法处理多目标优化问题时往往效率不高，这

IBMOLS), 正是充分考虑到个体间的占优关系，通过二元指标为个体值。不同于传统的线性加权法，需要将多目标问题转化为单目标问题，基于 Pareto 占优关系的进化算法，需要对群体进行分层管理。IBMOLS二元指标分配的适应值来实现对群体的有效管理其中，基于 Iε的多目标算法框架如算法2-1所示。2006 年 Knowles 等人提出了另一种新的二元指示器指标[28]，简记为 IHyp如下：IHyp(x1, x2) =H(x2) H(x1) if x2 x1H( x1, x2) H(x1) otherwise其中，，H(x) 表示个体 x 所占优的空间体积，IHyp(x1, x2) 表示为被个体 x2不被个体 x1所占优的那部分空间的体积。当 x2 x1时，，IHyp(x1, x2) (x1) 减去，IHyp(x2) 得到；当 x1与 x2不具有占优关系时，则由 x1和 x2的联减去 x1的超体积得到。图2-4分别给出了这两种情形下的超体积示例。
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 桂洪照;;几种具有代表性的启发式算法研究[J];电子制作;2016年02期

2 王芳,施国洪;商贸服务业选址决策研究——一种基于阿德兰启发式算法的选址方法[J];江苏商论;2004年07期

3 陶光远;周佩德;王强;;最优运输径路选择的启发式算法[J];南京工学院学报;1987年06期

4 许杰锋;;客车调度问题(BSP)的数学模型及一种新的启发式算法[J];上海交通大学学报;1988年06期

5 邢琳;;一种启发式识别被积函数算法的设计与实现[J];中南矿冶学院学报;1988年01期

6 郭耀煌,范莉莉;货运汽车调度的一种启发式算法[J];系统工程;1989年01期

7 杨英杰;;单体型装配问题的启发式算法研究[J];数字技术与应用;2017年01期

8 陈燕;谢琪琦;刘咏;崔耀东;;圆形件下料顺序分组启发式算法的设计与实现[J];图学学报;2017年01期

9 潘立军;符卓;;求解带硬时间窗车辆路径问题的时差插入启发式算法[J];计算机应用;2012年11期

10 高尚,陈钢;可靠性优化的一种新的启发式算法[J];工程设计学报;2004年03期

相关会议论文 前10条

1 冯德鸿;唐加福;郭琦;李辉;;订货批量问题改进的相关策略启发式算法与仿真分析[A];2007系统仿真技术及其应用学术会议论文集[C];2007年

2 罗守成;唐国春;;二维集装箱问题的一个启发式算法[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

3 刘嘉敏;马广煜;黄有群;;基于组合的三维集装箱装入启发式算法的研究[A];全国第13届计算机辅助设计与图形学（CAD/CG）学术会议论文集[C];2004年

4 戴娜;肖杰;邸瑞华;;异构计算环境下任务调度模型的启发式算法研究[A];2006年全国开放式分布与并行计算机学术会议论文集（三）[C];2006年

5 许争争;;自有和租用车辆并存条件下基于协作的启发式算法研究[A];第十九届中国管理科学学术年会论文集[C];2017年

6 刘青松;孔云峰;党兰学;王震;;元启发式算法在校车路径规划中的应用[A];第七届全国地理学研究生学术年会论文摘要集[C];2012年

7 何正文;徐渝;;多模式项目支付进度问题的优化模型及启发式算法[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

8 黄忠圣;;高等启发式算法在桁架结构优化中的应用[A];北京力学会第21届学术年会暨北京振动工程学会第22届学术年会论文集[C];2015年

9 李兵;蒋慰孙;;改进的遗传算法及在一类组合优化问题中的应用[A];1995中国控制与决策学术年会论文集[C];1995年

10 张建勇;李军;;模糊需求VRP的一种Sweeping启发式算法[A];第九届中国管理科学学术年会论文集[C];2007年

相关重要报纸文章 前1条

1 褚会会;建立数学模型 启发式算法求解[N];东方烟草报;2016年

相关博士学位论文 前10条

1 古继兴;KOD多播技术与Steiner树启发式算法[D];上海交通大学;2007年

2 董兴业;启发式算法及其在同顺序流水作业问题中的应用[D];北京交通大学;2008年

3 马华伟;带时间窗车辆路径问题及其启发式算法研究[D];合肥工业大学;2008年

4 胡大伟;设施定位和车辆路线问题模型及其启发式算法研究[D];长安大学;2008年

5 石文;空中交通管理优化问题研究[D];天津大学;2014年

6 杨玉珍;基于元启发式算法的带生产约束作业车间调度问题若干研究[D];华东理工大学;2014年

7 邓冠龙;基于元启发式算法的调度问题若干研究[D];华东理工大学;2012年

8 郑君玺;一类混合生产线调度与数值仿真技术的研究[D];华南理工大学;2016年

9 李常敏;两层规划的逼近理论及算法研究[D];复旦大学;2010年

10 符卓;开放式车辆路径问题及其应用研究[D];中南大学;2003年

相关硕士学位论文 前10条

1 霍超;求解多目标无约束二元二次规划问题的元启发式算法研究[D];电子科技大学;2018年

2 罗云凤;基于启发式智能搜索的货运列车节能优化研究[D];江西理工大学;2018年

3 苗晓燕;基于启发式算法边坡及支挡结构稳定性分析方法[D];湖南大学;2017年

4 边哲永;基于两种改进策略的亚启发式算法求解路径相关问题研究[D];天津大学;2016年

5 刘畅;基于混合启发式算法的单线公交车辆调度问题研究[D];北京交通大学;2016年

6 姜毅;扰动型超启发式算法的适应度地貌分析[D];大连理工大学;2013年

7 赵强;启发式算法在自动文本分类中的研究与应用[D];电子科技大学;2017年

8 张仁星;基于启发式算法的集装箱堆场优化研究[D];大连海事大学;2011年

9 徐o

本文编号：2660443