答辩公告
我的位置在: 首页 > 答辩公告 > 正文
NGUYEN HOAI PHUONG答辩公告
浏览次数:日期:2019-07-04编辑:研究生教务办1

答辩公告

论文题目

STUDY NEW METAHEURISTIC   FOR KNAPSACK PROBLEMS

(背包问题的新算法研究)

答辩人

NGUYEN HOAI PHUONG

指导教师

王东教授

答辩委员会

主席

陈浩教授

学科专业

信息与计算机工程  

学院

信息与计算机工程学院

答辩地点

软件大楼 302


答辩时间

20197 5

上午9


学位论文简介


背包问题是最著名的NP难问题之一,它的应用极大地提高了它的声誉。包括运输、物流、切割和包装、电信、可靠性、广告、投资、预算分配和生产管理等许多工业领域的问题。它们要么作为独立问题出现,要么作为更复杂编程模型的子问题出现。

同时,背包问题在信息加密、预算控制、工程选择、材料切割、货物装载、网络信息安全等方面具有重要的应用价值。从计算复杂性理论的角度来看,背包问题是一个经典的NP问题,经过半个多世纪的研究,背包问题一直是算法和复杂性研究的热点问题之一。背包问题有很多变种。研究人员从多选择、多维度、多背包、多目标、二次和非线性目标、相关、无关、随机和模糊参数等多个方面进行了研究,其中大部分是NP难问题。

近年来研究人员已经提出了许多解决背包问题的方法。该问题的方法分为两类:精确算法和近似算法。背包问题的精确算法包括递归算法、动态规划法、分支定界法。对于近似算法,背包问题有许多元启发式算法,如模拟退火算法、禁忌搜索算法、遗传算法、蚁群算法、量子进化算法和蜂群算法等。元启发式算法的优点是在合理的时间内找到问题的近似最优解。

本文的主要贡献包括如下四个方面:

首先,针对0-1背包问题(即KP01问题),提出了一种基于贪婪策略的二元粒子群优化算法。提出了一种求解实码问题的粒子群算法。为了解决类似KP01的二元代码问题,本文使用了一个传递函数将实向量转换为二元向量。将贪婪修复算子与粒子群优化算法相结合,实现了算法的快速收敛和较好的最优解。对五个最先进的基准实例和强相关数据集的仿真结果表明,该算法与以前的算法相比具有更好的性能。新方法在解决大规模实例时提供了更好的质量解决方案。

其次,由于社会蜘蛛算法在探索和开发搜索空间方面表现出良好的能力,针对0-1背包问题,本文进一步提出了一种新的二元社会蜘蛛算法((Binary Social Spider AlgorithmBSSA)。在BSSA中,采用实码向量和二元向量的混合编码方案来表示蜘蛛个体。该算法采用了Sigmoid函数将实变量转换为二元变量,两种约束处理技术在BSSA中相互配合。约束处理技术不仅可以处理冲突解,而且可以提高解的质量。对五个最先进的基准实例和强相关数据集的仿真结果表明,该算法与以前的算法相比具有更好的性能。

第三,针对子集和问题,提出了一种求解子集和问题的二元Bat算法。BAT算法具有良好的搜索能力,在优化元启发式的两个重要特征:强化和多样化方面表现出良好的操作性。子集和问题的解决方案是一个二进制代码,所以本文使用sigmoid传递函数将实码转换为二元代码。约束处理技术与二元BAT算法配合使用,二元BAT算法是一种惩罚函数,有助于算法消除坏解。对九个基准数据集的仿真结果表明,该算法与遗传算法相比具有更好的性能。新方法在解决大规模实例时提供了更好的质量解决方案。

最后,针对多选背包( Multiple-choice knapsack problemMCKP ) 问题,在前面工作的基础之上,提出了一种基于元启发式化学反应优化( Chemical Reaction OptimizationCRO )算法。MCKP问题是一个著名的NP难问题,在现实世界和理论上有着广泛的应用。化学反应优化是模拟化学反应过程的一种新的优化方法,即CRO在连续和离散领域优于许多其他方法。与传统的随机函数相比,混沌函数具有生成随机序列的优点。本文将原启发思想与CRO算法结合,其优势是使用了四种类型的搜索算子和一个罚函数来帮助算法快速、准确地找到最优解。实验结果表明,本文提出的方法在求解MCKP问题的大型测试集上比遗传算法具有更好的性能。

关键词:社会蜘蛛算法;粒子群优化;人工优化;0-1背包问题;多选背包问题;子集和问题;BAT算法

















主要学术成果

1. Phuong Hoai Nguyen, Dong Wang, Tung Khac Truong. New Hybrid Particle Swarm Optimization and Greedy for 0-1 Knapsack Problem, Indonesian Journal of Electrical Engineering and Computer Science, Vol.3, No.1,2016.(Scopus)

2. Phuong Hoai Nguyen, Dong Wang, Tung Khac Truong. A Novel Binary Social Spider Algorithm for 0-1 Knapsack Problem, International Journal of Innovative Computing, Information and Control, Vol. 13, No. 6, 2017.(EI)

3. Phuong Hoai Nguyen, Dong Wang, Tung Khac Truong. A binary BAT algorithm for Subset sum problem, Vol.7, No.4, Journal of Next Generation Information Technology, 2016.


上一篇:
沈潼答辩公告
下一篇:
张鑫答辩公告