求解二次分配问题的改进的差异鱼群优化算法研究

发布时间：2019-11-11 10:06

【摘要】：在实际生活和工程中,二次分配问题(Quadratic assignment problem,QAP)有着非常多的应用,例如:工厂地址的位置选择、集成电路的线路布局、打字机键盘设计、作业调度等。二次分配问题是一种离散型的组合优化问题,具有NP-hard属性,很难在多项式时间内被求解。因此,自1957年Koopmans和Beckmann提出二次分配问题以来,许多学者一直关注并研究了该问题,并提出了3类有效的算法:经典的数学方法、启发式和演化方法。但前一类只适应于小规模QAP问题的求解,后两类仍然有研究的空间。如何探索高性能的求解方法一直是开放性的课题。人工鱼群算法不需要对初始参数有过多的要求,差异演化算法的收敛速度快,局部搜索能力强。因此,本文在湖南省高校科技成果产业化培育项目基金(编号2015CY010)的资助下,对求解QAP的差异与鱼群混合的演化方法进行研究,主要工作和创新点归纳如下:1.提出一种求解QAP问题的改进的鱼群优化方法。(1)给出了一种步长为1的穷举搜索觅食行为,提高了觅食效率;(2)改进的随机行为中,个体鱼的新状态继承了一部分最优鱼的状态分量,以避免随机行为的盲目性;(3)通过随机选取可视域大小,以保持鱼群的多样性。实验表明:提出的改进的鱼群算法的求解精度优于基本的人工鱼群算法。2.提出一种求解QAP问题的改进差异鱼群优化方法。定义了QAP问题中的差异演化的变异、交叉以及选择算子。与改进的鱼群算法相结合,提高整体的局部寻优能力和收敛速度。数值实验表明:改进差异鱼群优化方法的收敛速度和求解精度明显优于目前已有的其它算法。本文讨论了QAP问题的基本鱼群算法的改进,并与局部搜索能力强的差异演化算法结合。提出的改进差异鱼群优化算法具有比较强的收敛能力,且求解精度高。二次分配基准问题库(QAPLIB)中的算例验证了本文方法的良好性能。最后,希望本文算法能够推广到其他组合优化问题中,能够有助于对这些问题的求解。
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】

相关期刊论文 前10条

1 王丽;芦彩林;宫建平;;一种求解路径优化问题的新型人工鱼群算法[J];数学的实践与认识;2016年20期

2 张惠珍;李倩;Cesar Beltran-Royo;;求解二次分配问题的拉格朗日松弛新方法[J];数学的实践与认识;2016年18期

3 马宪民;刘妮;;自适应视野的人工鱼群算法求解最短路径问题[J];通信学报;2014年01期

4 徐鹏;刘文颖;赵子兰;李波;汪宁渤;;基于改进人工鱼群算法的含大规模风电电网无功优化[J];中国电力;2013年11期

5 王培崇;;人工鱼群算法研究综述[J];中国民航飞行学院学报;2013年04期

6 汪照;李有明;陈斌;邹婷;;基于鱼群算法的OFDMA自适应资源分配[J];物理学报;2013年12期

7 杨淑霞;韩奇;徐琳茜;刘达;路石俊;;鱼群算法与神经网络结合的节能减排效果评价[J];中南大学学报(自然科学版);2012年04期

8 朱命昊;厍向阳;;求解旅行商问题的改进人工鱼群算法[J];计算机应用研究;2010年10期

9 曲良东;何登旭;;一种混沌人工鱼群优化算法[J];计算机工程与应用;2010年22期

10 张惠珍;马良;;基于线性化技术的二次分配问题求解新方法[J];系统工程理论与实践;2010年03期

相关博士学位论文 前2条

1 武志峰;差异演化算法及其应用研究[D];北京交通大学;2009年

2 李晓磊;一种新型的智能优化方法-人工鱼群算法[D];浙江大学;2003年

相关硕士学位论文 前1条

1 杨艺;求解二次分配问题的鱼群算法研究[D];湘潭大学;2014年

，

本文编号：2559207