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

Effective anytime algorithm for multiobjective combinatorial optimization problems

INFORMATION SCIENCES 2021年 565卷 210-228页

作者： Angel Dominguez-Rios, Miguel Chicano, Francisco Alba, Enrique Univ Malaga ITIS Software Malaga Spain

In multiobjective optimization, the result of an optimization algorithm is a set of efficient solutions from which the decision maker selects one. It is common that not all the efficient solutions can be computed in a short time and the search algorithm has to be stopped prematurely to analyze the solutions found so far. A set of efficient solutions that are well-spread in the objective space is preferred to provide the decision maker with a great variety of solutions. However, just a few exact algorithms in the literature exist with the ability to provide such a well-spread set of solutions at any moment: we call them anytime algorithms. We propose a new exact anytime algorithm for multiobjective combinatorial optimization combining three novel ideas to enhance the anytime behavior. We compare the proposed algorithm with those in the state-of-the-art for anytime multiobjective combinatorial optimization using a set of 480 instances from different well-known benchmarks and four different performance measures: the overall non-dominated vector generation ratio, the hypervolume, the general spread and the additive epsilon indicator. A comprehensive experimental study reveals that our proposal outperforms the previous algorithms in most of the instances. (c) 2021 Elsevier Inc. All rights reserved.

关键词： multiobjective combinatorial optimization Anytime algorithm Well-spread non-dominated points

来源：评论

学校读者我要写书评

暂无评论

Identifying preferred solutions in multiobjective combinatorial optimization problems

引用

TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES 2019年第3期27卷 1970-1981页

作者： Lokman, Banu Koksalan, Murat Univ Portsmouth Portsmouth Business Sch Portsmouth Hants England Middle East Tech Univ Dept Ind Engn Fac Engn Ankara Turkey

We develop an evolutionary algorithm for multiobjective combinatorial optimization problems. The algorithm aims at converging the preferred solutions of a decision-maker. We test the performance of the algorithm on the multiobjective knapsack and multiobjective spanning tree problems. We generate the true nondominated solutions using an exact algorithm and compare the results with those of the evolutionary algorithm. We observe that the evolutionary algorithm works well in approximating the solutions in the preferred regions.

关键词： Evolutionary algorithm preferred region nondominated frontier multiobjective combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights

引用

EURO JOURNAL ON DECISION PROCESSES 2018年第3-4期6卷 283-319页

作者： Benabbou, Nawal Perny, Patrice Natl Univ Singapore COM1 NUS Sch Comp 13 Comp Dr Singapore 117417 Singapore Sorbonne Univ CNRS LIP6 F-75005 Paris France

We propose an introduction to the use of incremental preference elicitation methods in the field of multiobjective combinatorial optimization. We consider three different optimization problems in vector-valued graphs, namely the shortest path problem, the minimum spanning tree problem and the assignment problem. In each case, the preferences of the decision-maker over cost vectors are assumed to be representable by a weighted sum but the weights of criteria are initially unknown. We then explain how to interweave preference elicitation and search to quickly determine a near-optimal solution with a limited number of preference queries. This leads us to successively introduce an interactive version of dynamic programming, greedy search, and branch and bound to solve the problems under consideration. We then present numerical tests showing the practical efficiency of these algorithms that achieve a good compromise between the number of queries asked and the solution times.

关键词： multiobjective combinatorial optimization Preference elicitation Imprecise weights Minimax regret

来源：评论

学校读者我要写书评

暂无评论

Easy to say they are Hard, but Hard to see they are Easy-Towards a Categorization of Tractable multiobjective combinatorial optimization Problems

引用

JOURNAL OF MULTI-CRITERIA DECISION ANALYSIS 2017年第1-2期24卷 82-98页

作者： Figueira, Jose Rui Fonseca, Carlos M. Halffmann, Pascal Klamroth, Kathrin Paquete, Luis Ruzika, Stefan Schulze, Britta Stiglmayr, Michael Willems, David Univ Lisbon Inst Super Tecn CEG IST Lisbon Portugal Univ Coimbra Dept Informat Engn CISUC Coimbra Portugal Univ Koblenz Landau Math Inst Koblenz Germany Univ Wuppertal Sch Math & Nat Sci Gaussstr 20 D-42119 Wuppertal Germany

multiobjective combinatorial optimization problems are known to be hard problems for two reasons: their decision versions are often NP-complete, and they are often intractable. Apart from this general observation, are there also variants or cases of multiobjective combinatorial optimization problems that are easy and, if so, what causes them to be easy? This article is a first attempt to provide an answer to these two questions. Thereby, a systematic description of reasons for easiness is envisaged rather than a mere collection of special cases. In particular, the borderline of easy and hard multiobjective optimization problems is explored. Copyright (C) 2016 John Wiley & Sons, Ltd.

关键词： multiobjective combinatorial optimization tractability complexity theory bottleneck objective binary coefficients dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Cross entropy for multiobjective combinatorial optimization problems with linear relaxations

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第2期243卷 362-368页

作者： Caballero, Rafael Hernandez-Diaz, Alfredo G. Laguna, Manuel Molina, Julian Univ Malaga Dept Appl Econ Math E-29071 Malaga Spain Pablo de Olavide Univ Dept Econ Quantitat Methods & Econ Hist Seville Spain Univ Colorado Leeds Sch Business Boulder CO 80309 USA

While the cross entropy methodology has been applied to a fair number of combinatorial optimization problems with a single objective, its adaptation to multiobjective optimization has been sporadic. We develop a multiobjective optimization cross entropy (MOCE) procedure for combinatorial optimization problems for which there is a linear relaxation (obtained by ignoring the integrality restrictions) that can be solved in polynomial time. The presence of a relaxation that can be solved with modest computational time is an important characteristic of the problems under consideration because our procedure is designed to exploit relaxed solutions. This is done with a strategy that divides the objective function space into areas and a mechanism that seeds these areas with relaxed solutions. Our main interest is to tackle problems whose solutions are represented by binary variables and whose relaxation is a linear program. Our tests with multiobjective knapsack problems and multiobjective assignment problems show the merit of the proposed procedure. (C) 2014 Elsevier B.V. All rights reserved.

关键词： multiobjective combinatorial optimization Cross entropy EMO Linear relaxation

来源：评论

学校读者我要写书评

暂无评论

Enhancing Branch-and-Bound for multiobjective 0-1 Programming

引用

INFORMS JOURNAL ON COMPUTING 2024年第1期36卷 1-304, C2页

作者： Forget, Nicolas Parragh, Sophie N. Aarhus Univ Sch Business & Social Sci Dept Econ & Business Econ DK-8210 Aarhus 5 Denmark Johannes Kepler Univ Linz Inst Prod & Logist Management A-4040 Linz Austria

In the biobjective branch-and-bound literature, a key ingredient is objective branching, that is, to create smaller and disjoint subproblems in the objective space, obtained from the partial dominance of the lower bound set by the upper bound set. When considering three or more objective functions, however, applying objective branching becomes more complex, and its benefit has so far been unclear. In this paper, we investigate several ingredients that allow us to better exploit objective branching in a multiobjective setting. We extend the idea of probing to multiple objectives for the 0-1 case, enhance it in several ways, and show that, when coupled with objective branching, it results in significant speedups in terms of CPU times. We also show how to adapt it to the general integer case. Furthermore, we investigate cut generation based on the objective branching constraints. Besides, we generalize the best bound idea for node selection to multiple objectives, and we show that the proposed rules outperform, in the multiobjective literature, the commonly employed depth-first and breadth-first strategies. We also analyze problem specific branching rules. We test the proposed ideas on available benchmark instances for three problem classes with three and four objectives, namely, the capacitated facility location problem, the uncapacitated facility location problem, and the knapsack problem. Our enhanced multiobjective branch-and-bound algorithm outperforms the best existing branch-and-bound-based approach and is the first to obtain competitive and even slightly better results than a state-of-the-art objective space search method on a subset of the problem classes.

关键词： multiple criteria integer programming branch and bound algorithms multiobjective combinatorial optimization probing node selection rules

来源：评论

学校读者我要写书评

暂无评论

A Cooperative Hybrid Quantum-Inspired Salp Swarm and Differential Evolution for Solving CEC 2022 Benchmark and Controller Placement Problems in Software Defined Networks

引用

IEEE ACCESS 2024年 12卷 90331-90344页

作者： Pathak, Sanjai Mani, Ashish Chatterjee, Amlan Amity Univ Amity Innovat & Design Ctr Noida 201313 Uttar Pradesh India Calif State Univ Dominguez Hills Dept Comp Sci Carson CA 90747 USA

This paper introduces a Cooperative Model of Salp Swarm optimization (CMSSO), which combines four algorithms: Salp Swarm Algorithm (SSA), Elite Opposition Learning-based SSA (EOSSA), Elite Opposition Quantum-inspired SSA (EQSSA), and Individual Dependent Approach for Differential Evolution (IDA-DE). These algorithms collaborate to tackle single-objective numerical optimization benchmarks from CEC-2022. SSA is a robust population-based metaheuristic renowned for its efficacy in practical optimization tasks. EOL and Quantum-inspired evolutionary algorithms exhibit enhanced capabilities in navigating search spaces compared to standard evolutionary algorithms. The objective of this cooperative model is to preserve the diversity and computational prowess of SSA while leveraging the strengths of these advanced algorithms. The multiobjective controller placement problem in Software Defined Networks (SDN) involves assigning switches to controllers, impacting network Quality of Service (QoS). Previous studies often focused on propagation latency for this assignment. However, our paper addresses this problem considering propagation latency between switches and controllers, inter-controller latency, and load balancing as multiobjective optimization. The experimental results confirmed the effectiveness of the proposed approach and showed that CMSSO is competitive with the standard SSA approaches.

关键词： Control systems Quantum computing optimization Benchmark testing Standards Search problems Particle swarm optimization Computational intelligence multiobjective combinatorial optimization SSA computational intelligence SDN controller placement problem

来源：评论

学校读者我要写书评

暂无评论

RM-MOCO: A Fast-Solving Model for Neural Multi-Objective combinatorial optimization Based on Retention

引用

COMPLEX SYSTEM MODELING AND SIMULATION 2025年第2期5卷 125-137页

作者： Wei, Huiqing Han, Fei Liu, Qing Han, Henry Jiangsu Univ Sch Comp Sci & Commun Engn Zhenjiang 212013 Peoples R China West Anhui Univ Sch Elect & Informat Engn Luan 237012 Peoples R China Baylor Univ Sch Engn & Comp Sci Waco TX 76798 USA

multiobjective combinatorial optimization (MOCO) problems have a wide range of applications in the real world. Recently, learning-based methods have achieved good results in solving MOCO problems. However, most of these methods use attention mechanisms and their variants, which have room for further improvement in the speed of solving MOCO problems. In this paper, following the idea of decomposition strategy and neural combinatorial optimization, a novel fast-solving model for MOCO based on retention is proposed. A brand new calculation of retention is proposed, causal masking and exponential decay are deprecated in retention, so that our model could better solve MOCO problems. During model training, a parallel computation of retention is applied, allowing for fast parallel training. When using the model to solve MOCO problems, a recurrent computation of retention is applied, enabling quicker problem-solving. In order to make our model more practical and flexible, a preference-based retention decoder is proposed, which allows generating approximate Pareto solutions for any trade-off preferences directly. An industry-standard deep reinforcement learning algorithm is used to train RM-MOCO. Experimental results show that, while ensuring the quality of problem solving, the proposed method significantly outperforms some other methods in terms of the speed of solving MOCO problems.

关键词： Computational modeling optimization Training Decoding Problem-solving Mathematical models Linear programming Learning systems Heuristic algorithms Deep reinforcement learning multiobjective combinatorial optimization learning-based method retention model deep reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

An Opposition Learning-based Quantum Inspired Salp Swarm optimization for The multiobjective Controller Placement Problem 10

An Opposition Learning-based Quantum Inspired Salp Swarm Opt...

引用

10th IEEE Uttar Pradesh Section International Conference on Electrical, Electronics and Computer Engineering, UPCON 2023

作者： Pathak, Sanjai Mani, Ashish Chatterjee, Amlan Amity University Uttar Pradesh Noida India California State University Dominguez Hills CarsonCA United States

ISBN: (纸本)9798350382471

This paper tackles the multiobjective controller placement problem in Software Defined Networks (SDN), a complex optimization challenge affecting network Quality of Service (QoS). In contrast to prior approaches focusing solely on propagation latency, our method considers propagation latency, inter-controller latency, and load balancing when allocating switches to controllers. We introduce EQSSA, a hybrid model that combines Elite Opposition Learning (EOL), Quantum Computing, and the Salp Swarm optimization Algorithm (SSA). SSA is a powerful meta-heuristic for real-world optimization problems, while EOL adds cost-effectiveness and efficiency to problem-solving. Quantum-inspired techniques enhance exploration and exploitation compared to standard methods. The hybridization aims to maintain SSA's diversity and computing power. We formulate the multiobjective controller placement problem (MOCPP) based on Pareto optimality and employ EQSSA for evaluation. Experimental results, compared to standard SSA and tested on well-known benchmarks, affirm the effectiveness of our approach, demonstrating EQSSA's competitiveness in solving MOCPP and offering a promising solution to SDN controller placement challenges. © 2023 IEEE.

关键词： Computational Intelligence Controller Placement Problem multiobjective combinatorial optimization SDN SSA

来源：评论

学校读者我要写书评

暂无评论

Learning to Balance Exploration and Exploitation in Pareto Local Search for Multi-objective combinatorial optimization 22

Learning to Balance Exploration and Exploitation in Pareto L...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Zhang, Haotian Shi, Jialong Sun, Jianyong Xu, Zongben Xi An Jiao Tong Univ Xian Shaanxi Peoples R China

ISBN: (纸本)9781450392686

As a natural extension of local search, Pareto local search (PLS) is a basic building block in many state-of-the-art metaheuristics for multi-objective combinatorial optimization problems (MCOPs). However, the basic PLS suffers from a low convergence rate, since it always fully explores the neighborhood of each unexplored solution, which is unnecessary. Some studies tried to introduce heuristic design in PLS to balance exploration and exploitation. In this paper, we handle this issue by a learning based framework. In the framework, PLS applies the firstK strategy, namely it stops exploring a solution's neighborhood when it obtains K non-dominated solutions, where K is adaptively controlled by a neural network based on observations collected during the search. Training the neural network is modeled as a reinforcement learning problem. Thus the proposed PLS variant is called PLSNN. In the experiments, we compared the performance of PLSNN and several PLS variants with heuristic design on the multi-objective unconstrained binary quadratic programming problem (mUBQP). The experimental results show that PLSNN performed significantly better than its counterparts on all test instances.

关键词： multiobjective combinatorial optimization Pareto local search reinforcement learning neural networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：