变邻域搜索算法研究及在组合优化中的应用
|
摘要
对变邻域搜索算法做出改进,提出了一种解决连续优化问题的变邻域搜索算法和一种结合粒子群算法的变邻域搜索混合算法。并将改进的算法应用于旅行商问题和0-1非线性混合整数规划问题中。主要的研究成果和创新点包括:
首先,针对因连续优化问题的可行解空间特点而无法直接应用变邻域搜索算法的问题,将SQP算法与变邻域搜索算法结合,用SQP问题求解局部最优解,用变邻域搜索算法跳出局部最优解,进而求得全局最优解。通过数据仿真,证明变邻域搜索算法比其他启发式算法在全局收敛性等方面更好。
其次,针对一般变邻域搜索算法计算时间长的问题,借鉴粒子群优化算法的思想,提出一种结合粒子群算法的变邻域搜索混合算法。通过调整变邻域搜索算法中的扰动过程和邻域变换过程,减少变邻域搜索算法中的局部搜索数量,提高扰动过程的效果。通过数据仿真,证明混合算法的有效性。
最后,将改进的变邻域搜索算法应用于旅行商问题和0-1非线性混合整数规划两个组合优化问题中。其中,对于旅行商问题,引入新的粒子群算法运算法则,得到适合旅行商问题的变邻域搜索混合算法,通过数据仿真证明混合算法比一般变邻域搜索算法和其他启发法效果更好;对于0-1非线性混合整数规划,把它转化为一般约束优化问题,利用罚函数法和变邻域搜索算法在连续空间中求解,通过实例证明方法是可行的。
This paper makes improvements to the variable neighborhood search algorithm, and presents a variable neighborhood search algorithm solving continuous optimization problems and a hybrid variable neighborhood search algorithm combining particle swarm optimization. Besides, the improved algorithm is also applied to the traveling salesman problems and the 0-1 mixed integer nonlinear programming problems. The research results and innovations are as follows:
Firstly, due to the problems which can not directly apply variable neighborhood search algorithm for characteristics of feasible solution space of the continuous optimization problems, combining SQP algorithm with variable neighborhood search algorithm, this article uses the SQP algorithm to solve local optimal solution, and uses variable neighborhood search algorithm to elect local optimal solution, then obtains the global optimal solution. Data simulation shows that the variable neighborhood search algorithm is better than the other heuristic algorithms in aspect of the global convergence.
Secondly, general variable neighborhood search algorithm takes longer time, so drawing on the idea of Particle Swarm Optimization, this paper proposes a hybrid variable neighborhood search algorithm with combination of particle swarm. Adjust the disturbance process and the neighborhood transformation process of the variable neighborhood search algorithm, to reduce the number of local search of the variable neighborhood search algorithm and enhance the effects of disturbance process. Data simulation shows the effectiveness of hybrid algorithm.
Thirdly, the improved algorithm is applied to the traveling salesman problems and the 0-1 mixed integer nonlinear programming problems. Among them, for the traveling salesman problems, this article introduces new PSO algorithms to get a hybrid variable neighborhood search algorithm which is appropriate for traveling salesman problems. The data simulation shows hybrid algorithm is better than the average variable neighborhood search algorithms and other heuristics. For the 0-1 mixed integer nonlinear programming problems, this paper firstly puts it into general optimization problems, and then solve them in the continuous space by the use of the penalty function method and variable neighborhood search algorithm. Finally, the examples prove this method is feasible.
首先,针对因连续优化问题的可行解空间特点而无法直接应用变邻域搜索算法的问题,将SQP算法与变邻域搜索算法结合,用SQP问题求解局部最优解,用变邻域搜索算法跳出局部最优解,进而求得全局最优解。通过数据仿真,证明变邻域搜索算法比其他启发式算法在全局收敛性等方面更好。
其次,针对一般变邻域搜索算法计算时间长的问题,借鉴粒子群优化算法的思想,提出一种结合粒子群算法的变邻域搜索混合算法。通过调整变邻域搜索算法中的扰动过程和邻域变换过程,减少变邻域搜索算法中的局部搜索数量,提高扰动过程的效果。通过数据仿真,证明混合算法的有效性。
最后,将改进的变邻域搜索算法应用于旅行商问题和0-1非线性混合整数规划两个组合优化问题中。其中,对于旅行商问题,引入新的粒子群算法运算法则,得到适合旅行商问题的变邻域搜索混合算法,通过数据仿真证明混合算法比一般变邻域搜索算法和其他启发法效果更好;对于0-1非线性混合整数规划,把它转化为一般约束优化问题,利用罚函数法和变邻域搜索算法在连续空间中求解,通过实例证明方法是可行的。
This paper makes improvements to the variable neighborhood search algorithm, and presents a variable neighborhood search algorithm solving continuous optimization problems and a hybrid variable neighborhood search algorithm combining particle swarm optimization. Besides, the improved algorithm is also applied to the traveling salesman problems and the 0-1 mixed integer nonlinear programming problems. The research results and innovations are as follows:
Firstly, due to the problems which can not directly apply variable neighborhood search algorithm for characteristics of feasible solution space of the continuous optimization problems, combining SQP algorithm with variable neighborhood search algorithm, this article uses the SQP algorithm to solve local optimal solution, and uses variable neighborhood search algorithm to elect local optimal solution, then obtains the global optimal solution. Data simulation shows that the variable neighborhood search algorithm is better than the other heuristic algorithms in aspect of the global convergence.
Secondly, general variable neighborhood search algorithm takes longer time, so drawing on the idea of Particle Swarm Optimization, this paper proposes a hybrid variable neighborhood search algorithm with combination of particle swarm. Adjust the disturbance process and the neighborhood transformation process of the variable neighborhood search algorithm, to reduce the number of local search of the variable neighborhood search algorithm and enhance the effects of disturbance process. Data simulation shows the effectiveness of hybrid algorithm.
Thirdly, the improved algorithm is applied to the traveling salesman problems and the 0-1 mixed integer nonlinear programming problems. Among them, for the traveling salesman problems, this article introduces new PSO algorithms to get a hybrid variable neighborhood search algorithm which is appropriate for traveling salesman problems. The data simulation shows hybrid algorithm is better than the average variable neighborhood search algorithms and other heuristics. For the 0-1 mixed integer nonlinear programming problems, this paper firstly puts it into general optimization problems, and then solve them in the continuous space by the use of the penalty function method and variable neighborhood search algorithm. Finally, the examples prove this method is feasible.
引文
[1] Hansen, Mladenovic. Variable neighborhood search: methods and applications[J]. A Quarterly Journal of Operations Research. 2008(12): 319-360.
[2] Hansen, Mladenovic. Variable neighborhood search: principles and applications[J]. European Journal of Opertional Research. 2001 (130): 449-467.
[3] Hansen, Mladenovic. Variable Neighborhood Decomposition Search[J]. Journal of Heuristics. 2001 (7): 335–350.
[4] Hemmelmayr, Doerner, Hartl. A variable neighborhood search heuristic for periodic routing problems[J]. European Journal of Operational Research. 2009 (195): 791–802.
[5] Hansen, Mladenovic. Variable neighborhood search for the p-median[J]. Location Science. 1997 (5): 207-226.
[6] Crainic, Gendreau, Hansen, Mlanenovic. Cooperative Parallel Variable Neighborhood Search for the p-Median[J]. Journal of Heuristics. 2004 (10): 293-314.
[7] Avanthay, Hertz, Zufferey. A variable neighborhood search for graph coloring[J]. European Journal of Operational Research. 2003 (151): 379-388.
[8] Ribeiro, Souza. Variable neighborhood search for the degree-constrained minimum spanning tree problem[J]. Discrete Applied Mathematics. 2002 (118): 43-54.
[9] Jie Gao, Linyan Sun, Mitsuo Gen. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems[J]. Computers & Operations Research. 2008 (35): 2892-2907.
[10] GARCIA-LOPEZ, Melian-Batista, Moreno-Perez, Moreno-Vega. The Parallel Variable Neighborhood Search for the p-Median Problem[J]. Journal of Heuristics. 2002 (8): 375-388.
[11] Edmund K. Burke,Timothy Curtois,Gerhard Post,Rong Qu,Bart Veltman. A hybrid heuristic ordering and variable neighborhood search for the nurse roistering problem[J]. European Journal of Operational Research. 2008 (188) 330–341.
[12] Michael Polacek,Karl F. Doerner,Richard F. Hartl,Vittorio Maniezzo. A variable neighborhood search for the capacitated arc routing problem with intermediate facilities[J]. Journal of Heuristics. 2008 (14): 405–423.
[13] Lazic, Hanafi, Mladenovic, Urosevic. Variable neighborhood decomposition search for 0–1mixed integer programs[J]. Computers & Operations Research. 2009 (37): 1055-1067.
[14] Bin Hu, Markus, Leitner, Gunther, Raidl. Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem[J]. Journal of Heuristics. 2008 (14): 473-499.
[15] Brimberg, Mladenovic, U. Local and variable neighborhood search for the k -cardinality subgraph problem[J]. Journal of Heuristics. 2008 (14): 501-517.
[16] Mladenovic, Drazic, Kovacevic-Vujcic, Cangalovic. General variable neighborhood search for the continuous optimization[J]. European Journal of Operational Research. 2008 (191): 753-770.
[17] Drazic, Lavor,Maculan. A continuous variable neighborhood search heuristic for finding the three-dinensional structure of amolecule[J]. European Journal of Operational Research. 2008 (185): 1265-1273.
[18] Garcia, Perez-Brito, Campos, Marti. Variable neighborhood search for the linear ordering problem[J]. Computers & Operations Research. 2006 (33): 3549-3565.
[19] Toksar,Guner. Solving the unconstrained optimization problem by a variable neighborhood search[J]. Mathematical Analysis and Applications. 2007 (328): 1178-1187.
[20]袁亚湘、孙文瑜.最优化理论与方法[M].北京,科学出版社.1997.
[21]刑文训、谢金星.现代优化计算方法[M].北京,清华大学出版社,2005.
[22]高雷阜.最优化理论与方法[M].沈阳,东北大学出版社,2005.
[23]杨盛、吴澄、崔亚军.用变邻域搜索法求解生产制造系统中的整数规划[J].中国控制会议[C], 1995,安徽黄山.
[24]林耿、朱兴文.整数规划的一类变邻域填充函数算法[J].中国运筹学会第八届学术交流会[C], 2006,广州深圳.
[25]孙元凯、刘民、吴澄.变邻域结构Tabu搜索算法及其在JobShop调度问题上的应用[J].电子学报.2001 (5): 622-625.
[26]汪翼、孙林岩、李刚.集装箱车辆调度问题的变邻域禁忌搜索算法[J].工业工程与管理2008 (5): 6-10.
[27]周雅兰,王甲海,闭玮等.结合变邻域搜索的竞争Hopfield神经网络解决最大分散度问题[J].计算机科学.2010(37):208-211.
[28]刘士新,刘玲,张涛.求解VRPBTW的变邻域搜索算法[J].东北大学学报.2008(29):316-319.
[29]夏福全,吴仆.一种推广的UFCLP的变邻域搜索算法[J].贵州大学学报.2010(27):18-27.
[30]董红宇,黄敏,王兴伟,郑秉霖.变邻域搜索算法综述[J].控制工程.2009.
[31]梁黎明.群论与变换邻域搜索方法[D].华南理工大学:应用数学.2002.
[31]王明星.连续禁忌搜索算法改进及应用研究[D].浙江大学:系统工程.2005.
[32]陈震亦.粒子群优化算法研究及其在TSP问题中的应用[D].福州大学:计算机系统结构.2004.
[33]刘林炬.引入禁忌搜索的双种群粒子群算法及其应用研究[D].江南大学:计算机软件与理论.2008.
[34]孙晶晶,雷秀娟.求解TSP的改进自组织PSO算法[J].计算机工程与应用2009,45(31):30-33.
[35]武妍,周欣.一种适用于求解TSP问题的改进的禁忌算法[J].计算机工程与应用2008 (44): 57-59.
[36]阳明盛,罗长童.最优化理论、方法及求解软件[M].北京:科学出版社.2007.
[37]陈国华,廖小莲. 0-1非线性混合整数规划的罚函数解法[J].应用数学与计算数学学报2007(21):111-115.
[38] George L. Nemhauser, Laurence A. Wolsey. A recursive procedure to generate all cuts for 0-1 mixed integer programs[J]. Mathematical Programming. 1990(46):379-390.
[39] E. Balas, S. Ceria. A lift-and-project cutting plane algorithm for mixed 0–1 programs[J]. Mathematical Programming. 1993(58):295-324.
[40] Z. Gu, G. Nemhauser. Lifted flow cover inequalities for mixed 0-1 integer programs[J]. Mathematical Programming. 1999(85):439-467.
[41] A. Frangioni, C. Gentile. Perspective cuts for a class of convex 0–1 mixed integer programs[J]. Mathematical Programming. 2006(106):225-236.
[42]董颖,唐加福.一种求解非线性规划问题的混合粒子群优化算法[J].东北大学学报(自然科学版), 2003, 24(12)
[43]蔡立军,林亚平,易叶青等.一类特殊整数规划问题的DNA计算[J].湖南大学学报(自然科学版), 2008, 35(1)
[44]孟志青,胡奇英,杨晓琪.一种求解整数规划与混合整数规划非线性罚函数方法[J].控制与决策, 2002, 17(3)
[45]李铭明,张连生,梁玉梅.求解整数规划的单参数填充函数[J].运筹学学报, 2008,12(2)
[46]谭瑛,高慧敏,曾建潮.求解整数规划问题的微粒群算法[J].系统工程理论与实践, 2004,24(5)
[47]祁荣宾.求解一类0-1整数规划问题的新方法--混沌搜索算法[J].控制与决策,2003,18(6)
[48]李宏,焦永昌,张莉.一种求解混合整数规划的混合进化算法[J].控制与决策2008(23)1098-1101.
[49]杨敬.禁忌搜索与SQP相结合的混合优化算法研究[D].浙江大学:系统工程.2006
[50]粟塔山等.最优化计算原理与算法程序设计[M].长沙:国防科技大学出版社.2001.
[2] Hansen, Mladenovic. Variable neighborhood search: principles and applications[J]. European Journal of Opertional Research. 2001 (130): 449-467.
[3] Hansen, Mladenovic. Variable Neighborhood Decomposition Search[J]. Journal of Heuristics. 2001 (7): 335–350.
[4] Hemmelmayr, Doerner, Hartl. A variable neighborhood search heuristic for periodic routing problems[J]. European Journal of Operational Research. 2009 (195): 791–802.
[5] Hansen, Mladenovic. Variable neighborhood search for the p-median[J]. Location Science. 1997 (5): 207-226.
[6] Crainic, Gendreau, Hansen, Mlanenovic. Cooperative Parallel Variable Neighborhood Search for the p-Median[J]. Journal of Heuristics. 2004 (10): 293-314.
[7] Avanthay, Hertz, Zufferey. A variable neighborhood search for graph coloring[J]. European Journal of Operational Research. 2003 (151): 379-388.
[8] Ribeiro, Souza. Variable neighborhood search for the degree-constrained minimum spanning tree problem[J]. Discrete Applied Mathematics. 2002 (118): 43-54.
[9] Jie Gao, Linyan Sun, Mitsuo Gen. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems[J]. Computers & Operations Research. 2008 (35): 2892-2907.
[10] GARCIA-LOPEZ, Melian-Batista, Moreno-Perez, Moreno-Vega. The Parallel Variable Neighborhood Search for the p-Median Problem[J]. Journal of Heuristics. 2002 (8): 375-388.
[11] Edmund K. Burke,Timothy Curtois,Gerhard Post,Rong Qu,Bart Veltman. A hybrid heuristic ordering and variable neighborhood search for the nurse roistering problem[J]. European Journal of Operational Research. 2008 (188) 330–341.
[12] Michael Polacek,Karl F. Doerner,Richard F. Hartl,Vittorio Maniezzo. A variable neighborhood search for the capacitated arc routing problem with intermediate facilities[J]. Journal of Heuristics. 2008 (14): 405–423.
[13] Lazic, Hanafi, Mladenovic, Urosevic. Variable neighborhood decomposition search for 0–1mixed integer programs[J]. Computers & Operations Research. 2009 (37): 1055-1067.
[14] Bin Hu, Markus, Leitner, Gunther, Raidl. Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem[J]. Journal of Heuristics. 2008 (14): 473-499.
[15] Brimberg, Mladenovic, U. Local and variable neighborhood search for the k -cardinality subgraph problem[J]. Journal of Heuristics. 2008 (14): 501-517.
[16] Mladenovic, Drazic, Kovacevic-Vujcic, Cangalovic. General variable neighborhood search for the continuous optimization[J]. European Journal of Operational Research. 2008 (191): 753-770.
[17] Drazic, Lavor,Maculan. A continuous variable neighborhood search heuristic for finding the three-dinensional structure of amolecule[J]. European Journal of Operational Research. 2008 (185): 1265-1273.
[18] Garcia, Perez-Brito, Campos, Marti. Variable neighborhood search for the linear ordering problem[J]. Computers & Operations Research. 2006 (33): 3549-3565.
[19] Toksar,Guner. Solving the unconstrained optimization problem by a variable neighborhood search[J]. Mathematical Analysis and Applications. 2007 (328): 1178-1187.
[20]袁亚湘、孙文瑜.最优化理论与方法[M].北京,科学出版社.1997.
[21]刑文训、谢金星.现代优化计算方法[M].北京,清华大学出版社,2005.
[22]高雷阜.最优化理论与方法[M].沈阳,东北大学出版社,2005.
[23]杨盛、吴澄、崔亚军.用变邻域搜索法求解生产制造系统中的整数规划[J].中国控制会议[C], 1995,安徽黄山.
[24]林耿、朱兴文.整数规划的一类变邻域填充函数算法[J].中国运筹学会第八届学术交流会[C], 2006,广州深圳.
[25]孙元凯、刘民、吴澄.变邻域结构Tabu搜索算法及其在JobShop调度问题上的应用[J].电子学报.2001 (5): 622-625.
[26]汪翼、孙林岩、李刚.集装箱车辆调度问题的变邻域禁忌搜索算法[J].工业工程与管理2008 (5): 6-10.
[27]周雅兰,王甲海,闭玮等.结合变邻域搜索的竞争Hopfield神经网络解决最大分散度问题[J].计算机科学.2010(37):208-211.
[28]刘士新,刘玲,张涛.求解VRPBTW的变邻域搜索算法[J].东北大学学报.2008(29):316-319.
[29]夏福全,吴仆.一种推广的UFCLP的变邻域搜索算法[J].贵州大学学报.2010(27):18-27.
[30]董红宇,黄敏,王兴伟,郑秉霖.变邻域搜索算法综述[J].控制工程.2009.
[31]梁黎明.群论与变换邻域搜索方法[D].华南理工大学:应用数学.2002.
[31]王明星.连续禁忌搜索算法改进及应用研究[D].浙江大学:系统工程.2005.
[32]陈震亦.粒子群优化算法研究及其在TSP问题中的应用[D].福州大学:计算机系统结构.2004.
[33]刘林炬.引入禁忌搜索的双种群粒子群算法及其应用研究[D].江南大学:计算机软件与理论.2008.
[34]孙晶晶,雷秀娟.求解TSP的改进自组织PSO算法[J].计算机工程与应用2009,45(31):30-33.
[35]武妍,周欣.一种适用于求解TSP问题的改进的禁忌算法[J].计算机工程与应用2008 (44): 57-59.
[36]阳明盛,罗长童.最优化理论、方法及求解软件[M].北京:科学出版社.2007.
[37]陈国华,廖小莲. 0-1非线性混合整数规划的罚函数解法[J].应用数学与计算数学学报2007(21):111-115.
[38] George L. Nemhauser, Laurence A. Wolsey. A recursive procedure to generate all cuts for 0-1 mixed integer programs[J]. Mathematical Programming. 1990(46):379-390.
[39] E. Balas, S. Ceria. A lift-and-project cutting plane algorithm for mixed 0–1 programs[J]. Mathematical Programming. 1993(58):295-324.
[40] Z. Gu, G. Nemhauser. Lifted flow cover inequalities for mixed 0-1 integer programs[J]. Mathematical Programming. 1999(85):439-467.
[41] A. Frangioni, C. Gentile. Perspective cuts for a class of convex 0–1 mixed integer programs[J]. Mathematical Programming. 2006(106):225-236.
[42]董颖,唐加福.一种求解非线性规划问题的混合粒子群优化算法[J].东北大学学报(自然科学版), 2003, 24(12)
[43]蔡立军,林亚平,易叶青等.一类特殊整数规划问题的DNA计算[J].湖南大学学报(自然科学版), 2008, 35(1)
[44]孟志青,胡奇英,杨晓琪.一种求解整数规划与混合整数规划非线性罚函数方法[J].控制与决策, 2002, 17(3)
[45]李铭明,张连生,梁玉梅.求解整数规划的单参数填充函数[J].运筹学学报, 2008,12(2)
[46]谭瑛,高慧敏,曾建潮.求解整数规划问题的微粒群算法[J].系统工程理论与实践, 2004,24(5)
[47]祁荣宾.求解一类0-1整数规划问题的新方法--混沌搜索算法[J].控制与决策,2003,18(6)
[48]李宏,焦永昌,张莉.一种求解混合整数规划的混合进化算法[J].控制与决策2008(23)1098-1101.
[49]杨敬.禁忌搜索与SQP相结合的混合优化算法研究[D].浙江大学:系统工程.2006
[50]粟塔山等.最优化计算原理与算法程序设计[M].长沙:国防科技大学出版社.2001.