检索结果-内蒙古大学图书馆

Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2001年第1期134卷 103-119页

作者： Katayama, K Narihisa, H Okayama Univ Sci Fac Engn Dept Informat & Comp Engn Okayama 7000005 Japan

The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： heuristics local search simulated annealing unconstrained binary quadratic programming large-size problems

来源：评论

学校读者我要写书评

暂无评论

Closed-form formulas for evaluating r-flip moves to the unconstrained binary quadratic programming problem

引用

COMPUTERS & OPERATIONS RESEARCH 2020年 113卷 104774-000页

作者： Anacleto, Eduardo A. J. Meneses, Claudio N. Ravelo, Santiago V. Fed Univ ABC Ctr Math Computat & Cognit Santo Andre Brazil Univ Fed Rio Grande do Sul Inst Informat Porto Alegre RS Brazil

The unconstrained binary quadratic programming problem (UBQP) belongs to the NP-hard class and has become a framework for modeling a variety of combinatorial optimization problems. The methods most commonly used to solve instances of the UBQP explore the concept of neighborhood of a solution. Given a binary vector x is an element of{0, 1}(n), solution to a UBQP instance, a neighborhood of x can be defined by flip moves. Flip moves consist on selecting one or more elements (positions) of x and "flip" their values to their complementary values (i.e., from 1 to 0 or from 0 to 1). Normally, those methods compute a large number of flip moves, and so the whole process to solve an instance can be quite time consuming. In order to reduce this time, some works have proposed ways to efficiently evaluate one or two flip moves, and also extensions to higher order moves. In this paper we propose two closed-form formulas for evaluating quickly any order of flip moves. To test our theoretical findings, we executed an extensive set of computational experiments over well-known instances for the problem. Against common belief, our results show that it is possible to compute high order flip moves very fast. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Zero-one optimization unconstrained binary quadratic programming Fast flip moves Computational efficiency

来源：评论

学校读者我要写书评

暂无评论

A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming

引用

APPLIED SOFT COMPUTING 2014年第0期16卷 10-19页

作者： Liefooghe, Arnaud Verel, Sebastien Hao, Jin-Kao Univ Lille 1 LIFL UMR CNRS 8022 F-59655 Villeneuve Dascq France Inria Lille Nord Europe F-59650 Villeneuve Dascq France Univ Littoral Cote dOpale LISIC F-62228 Calais France Univ Angers LERIA F-49045 Angers France

The conventional unconstrained binary quadratic programming (UBQP) problem is known to be a unified modeling and solution framework for many combinatorial optimization problems. This paper extends the single-objective UBQP to the multiobjective case (mUBQP) where multiple objectives are to be optimized simultaneously. We propose a hybrid metaheuristic which combines an elitist evolutionary multiobjective optimization algorithm and a state-of-the-art single-objective tabu search procedure by using an achievement scalarizing function. Finally, we define a formal model to generate mUBQP instances and validate the performance of the proposed approach in obtaining competitive results on large-size mUBQ Pinstances with two and three objectives. (C) 2013 Elsevier B. V. All rights reserved.

关键词： unconstrained binary quadratic programming Multiobjective combinatorial optimization Hybrid metaheuristic Evolutionary multiobjective optimization Tabu search Scalarizing functiona

来源：评论

学校读者我要写书评

暂无评论

Solving Bi-objective unconstrained binary quadratic programming Problem with Multi-objective Backbone Guided Search Algorithm 12th

Solving Bi-objective Unconstrained Binary Quadratic Programm...

引用

12th International Conference on Intelligent Computing (ICIC)

作者： Xue, Li-Yuan Zeng, Rong-Qiang Wang, Yang Shang, Ming-Sheng Univ Elect Sci & Technol China Sch Elect Engn Chengdu 610054 Sichuan Peoples R China Southwest Jiaotong Univ Sch Math Chengdu 610031 Sichuan Peoples R China Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Sichuan Peoples R China Northwestern Polytech Univ Sch Management Xian 710072 Shanxi Peoples R China Chinese Acad Sci Chongqing Inst Green & Intelligent Technol Chongqing 400714 Peoples R China

ISBN: (纸本)9783319422947;9783319422930

This paper presents a multi-objective backbone guided search algorithm in order to optimize a bi-objective unconstrained binary quadratic programming problem. Our proposed algorithm consists of two main procedures which are hypervolume-based local search and backbone guided search. When the hypervolume-based local search procedure can not improve the Pareto approximation set any more, the backbone guided search procedure is applied for further improvements. Experimental results show that the proposed algorithm is very effective compared with the original multi-objective optimization algorithms.

关键词： Multi-objective optimization Backbone guided search Local search Hypervolume contribution unconstrained binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Evolving Instances of unconstrained binary quadratic programming that Challenge a Tabu Search Heuristic 12

Evolving Instances of Unconstrained Binary Quadratic Program...

引用

14th International Conference on Genetic and Evolutionary Computation Conference (GECCO)

作者： Porta, Michael Julstrom, Bryant A. St Cloud State Univ Comp Sci & Informat Technol St Cloud MN 56301 USA

ISBN: (纸本)9781450311786

A Tabu Search heuristic for unconstrained binary quadratic programming performs perfectly on a range of random problem instances. A genetic algorithm searches spaces of UBQP instances for instances that challenge the heuristic. The GA's evaluation step compares the performance of the Tabu Search to that of a memetic algorithm on the candidate stance being evaluated. On UBQP instances evolved by the GA, the TS heuristic returns solutions that are inferior to those of the memetic algorithm by significant margins.

关键词： Tabu Search difficult instances unconstrained binary quadratic programming genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved Harmony Search Based on Teaching-Learning Strategy for unconstrained binary quadratic programming 33

An Improved Harmony Search Based on Teaching-Learning Strate...

引用

33rd Chinese Control and Decision Conference (CCDC)

作者： Yong, Longquan Shaanxi Univ Technol Sch Math & Comp Sci Hanzhong 723001 Peoples R China Shaanxi Key Lab Ind Automat Hanzhong 723001 Peoples R China

ISBN: (纸本)9781665440899

unconstrained binary quadratic programming (UBQP) problem plays an important role in operational research due to its application potential and its computational challenge. This paper presents a new hybrid algorithm based on Harmony Search (HS) and Teaching-Learning-Based Optimization. The main features of the proposed algorithm called harmony search with teaching-learning (HSTL) are the integration of teaching-learning strategy in the basic harmony search. This hybridization has led to an efficient hybrid framework which achieves better balance between the exploration of HS and the exploitation capabilities of the Teaching-Learning-Based Optimization. Experiments on numerous benchmark problems having 50 to 2500 variables show the effectiveness of the proposed framework and its ability to achieve good quality solutions.

关键词： unconstrained binary quadratic programming Harmony search Teaching-Learning-Based Optimization

来源：评论

学校读者我要写书评

暂无评论

Experiments on Neighborhood Combination Strategies for Bi-objective unconstrained binary quadratic programming Problem 8th

Experiments on Neighborhood Combination Strategies for Bi-ob...

引用

8th International Symposium on Parallel Architectures, Algorithms, and programming (PAAP)

作者： Xue, Li-Yuan Zeng, Rong-Qiang An, Wei Wang, Qing-Xian Shang, Ming-Sheng Univ Elect Sci & Technol China Sch Elect Engn EHF Key Lab Sci Chengdu 611731 Sichuan Peoples R China Southwest Jiaotong Univ Sch Math Chengdu 610031 Sichuan Peoples R China Chinese Acad Sci Chengdu Documentat & Informat Ctr Chengdu 610041 Sichuan Peoples R China Univ Elect Sci & Technol China Sch Informat & Software Engn Chengdu 610054 Sichuan Peoples R China Chinese Acad Sci Chongqing Inst Green & Intelligent Technol Chongqing Key Lab Big Data & Intelligent Comp Chongqing 400714 Peoples R China

ISBN: (纸本)9789811064425;9789811064418

Local search is known to be a highly effective metaheuristic framework for solving a number of classical combinatorial optimization problems, which strongly depends on the characteristics of neighborhood structure. In this paper, we integrate the neighborhood combination strategies into the hypervolume-based multi-objective local search algorithm, in order to deal with the bi-objective unconstrained binary quadratic programming problem. The experimental results show that certain combinations are superior to others. The performance analysis sheds lights on the ways to further improvements.

关键词： Multi-objective optimization Hypervolume contribution Neighborhood combination Local search unconstrained binary quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Solving unconstrained binary quadratic programming using binary particle swarm optimization

Solving unconstrained binary quadratic programming using bin...

引用

International Conference on Information Technology and Industrial Engineering

作者： Lin, Geng Minjiang Univ Dept Math Fuzhou Peoples R China

ISBN: (纸本)9781845648442;9781845648435

The unconstrained binary quadratic programming is known to be NP-hard, and is a unified model for a lot of combinatorial optimization problems. This paper presents a binary particle swarm optimization for solving the unconstrained binary quadratic programming. The proposed algorithm adopts a method to update position, and uses mutation operation to produce new solutions. Then, the new solutions are refined by a local search procedure. The algorithm was tested on a benchmark set from the literature. The experimental results show that the proposed algorithm is able to find high-quality solutions within an acceptable runtime.

关键词： unconstrained binary quadratic programming binary particle swarm optimization heuristic

来源：评论

学校读者我要写书评

暂无评论

A Single Deep Neural Network Model for Multiobjective unconstrained binary quadratic programming Problem

引用

INTERNATIONAL JOURNAL OF COGNITIVE INFORMATICS AND NATURAL INTELLIGENCE 2024年第1期18卷

作者： Zhou, Ying Kong, Lingjing Liu, Yong Cai, Yiqiao Liu, Shaopeng Shenzhen Inst Informat & Technol Shenzhen Peoples R China Huaqiao Univ Quanzhou Peoples R China Guangdong Polytech Normal Univ Guangzhou Peoples R China

The multiobjective unconstrained binary quadratic programming problem is an important combinatorial optimization problem with both theory and practical values. Until now, several efforts have been made to design metaheuristic methods to solve the problem. However, designing such effective methods is not trivial and heavily depends on experts' specific knowledge. Meanwhile, due to the iterative nature of metaheuristic methods, they require a long time to find high-quality solutions. From the perspective of machine learning, this paper proposes a deep reinforcement learning method to solve the problem. The method can automatically learn effective heuristics from a large amount of data, thus decreasing the need for experts' knowledge. Meanwhile, by leveraging the power of GPU, the method can quickly obtain high-quality solutions for a batch of instances. Experimental results show the proposed method outperforms two classical metaheuristic methods in terms of solution quality and running time for solving the problem.

关键词： Multiobjective Optimization unconstrained binary quadratic programming Deep Reinforcement Learning

来源：评论

学校读者我要写书评

暂无评论

An Improved Harmony Search Based on Teaching-Learning Strategy for unconstrained binary quadratic programming

An Improved Harmony Search Based on Teaching-Learning Strate...

引用

第33届中国控制与决策会议

作者： Longquan Yong School of Mathematics and Computer Science Shaanxi University of Technology Shaanxi Key Laboratory of Industrial Automation

unconstrained binary quadratic programming(UBQP) problem plays an important role in operational research due to its application potential and its computational *** paper presents a new hybrid algorithm based on Harmony Search(HS) and Teaching-Learning-Based *** main features of the proposed algorithm called harmony search with teaching-learning(HSTL) are the integration of teaching-learning strategy in the basic harmony *** hybridization has led to an efficient hybrid framework which achieves better balance between the exploration of HS and the exploitation capabilities of the Teaching-Leaming-Based *** on numerous benchmark problems having 50 to 2500 variables show the effectiveness of the proposed framework and its ability to achieve good quality solutions.

关键词： unconstrained binary quadratic programming Harmony search Teaching-Learning-Based Optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：