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

作者： Djakam, William Ngambou The University of Alabama at Birmingham

学位级别：Ph.D., Doctor of Philosophy

This thesis studies combinatorial optimization problems (COPs) on graphs that integrate uncertainty in the problem definition. We focus on Probabilistic combinatorial optimization problems (PCOPs), where uncertainty is associated with the presence or absence of subsets of vertices that describe the problem. In general, combinatorial optimization problems are formulated as a Mixed Integer Linear Programming (MILP) model. This process aims to convert elements of decision-making into variables considering related constraints and choosing an objective function. In such cases, it is recommended to define an objective function that is a linear function with linear constraints. Also, when practical problems are formulated as combinatorial optimization models, one must often include logical implications. Yet, the Least Action Principle (LAP) of information theory has been exploited to achieve optimization goal using the least amount of resources. Therefore, we approach combinatorial optimization problems on graphs by modeling them with a noisy communication channel using the maximum independent set as a tool of the least action of information theory. Subsequently, we propose an information-theoretic modeling approach for a class of PCOP that transformable into bipartite graphs. Using the a priori approach, we construct a communication channel and obtain any sub-instance solution with the noisy communication model. This communication channel model is used to a portfolio optimization problem as a case study.

关键词： Mixed integer linear programming model combinatorial optimization problems Information theory Least action

来源：评论

学校读者我要写书评

暂无评论

A four-decomposition strategies for hierarchically modeling combinatorial optimization problems: framework, conditions and relations 13

A four-decomposition strategies for hierarchically modeling ...

引用

International Conference on High Performance Computing and Simulation (HPCS)

作者： Chaieb, Marouene Jemai, Jaber Mellouli, Khaled LARODEC Inst Super Gest Tunis 41 Rue Liberte Le Bardo 2000 Tunisia

ISBN: (纸本)9781467378130

We address the problem of modeling combinatorial optimization problems (COP). COPs are generally complex problems to solve. So a good modeling step is fundamental to make the solution easier. Our approach orients researches to choose the best modeling strategy from the beginning to avoid any problem in the solving process. This paper aims at proposing a new approach dealing with hard COPs particularly when the decomposition process leads to some well-known and canonical optimization sub-problems. We tried to draw a clear framework that will help to model hierarchical optimization problems. The framework will be composed by four decomposition strategies which are: objective based decomposition;constraints based decomposition, semantic decomposition and data partitioning strategy. For each strategy, we present supporting examples from the literature where it was applied. But, not all combinatorial problems can be benefit from the outcomes and benefits of modeling problems hierarchically, rather only particular problems can be modeled like a hierarchical optimization problem. Thus, we propose a set of decomposability conditions for decomposing COPs. Furthermore, we define the types of relationships between obtained sub-problems and how partial solutions can be merged to obtain the final solution.

关键词： combinatorial optimization problems hierarchiucal optimization constraint relaxation semantic decomposition objective-based decomposition data-partitioning parallel processing sequential processing gradually mixed optimization totally mixed optimization

来源：评论

学校读者我要写书评

暂无评论

Ant-Inspired Metaheuristic Algorithms for combinatorial optimization problems in Water Resources Management

引用

WATER 2023年第9期15卷 1712页

作者： Bhavya, Ravinder Elango, Lakshmanan Anna Univ Dept Geol Chennai 600025 India

Ant-inspired metaheuristic algorithms known as ant colony optimization (ACO) offer an approach that has the ability to solve complex problems in both discrete and continuous domains. ACOs have gained significant attention in the field of water resources management, since many problems in this domain are non-linear, complex, challenging and also demand reliable solutions. The aim of this study is to critically review the applications of ACO algorithms specifically in the field of hydrology and hydrogeology, which include areas such as reservoir operations, water distribution systems, coastal aquifer management, long-term groundwater monitoring, hydraulic parameter estimation, and urban drainage and storm network design. Research articles, peer-reviewed journal papers and conference papers on ACO were critically analyzed to identify the arguments and research findings to delineate the scope for future research and to identify the drawbacks of ACO. Implementation of ACO variants is also discussed, as hybrid and modified ACO techniques prove to be more efficient over traditional ACO algorithms. These algorithms facilitate formulation of near-optimal solutions, and they also help improve cost efficiency. Although many studies are attempting to overcome the difficulties faced in the application of ACO, some parts of the mathematical analysis remain unsolved. It is also observed that despite its popularity, studies have not been successful in incorporating the uncertainty in ACOs and the problems of dimensionality, convergence and stability are yet to be resolved. Nevertheless, ACO is a potential area for further research as the studies on the applications of these techniques are few.

关键词： ant colony optimization (ACO) combinatorial optimization problems hydrology hydrogeology nature-inspired algorithm

来源：评论

学校读者我要写书评

暂无评论

A hybrid discrete state transition algorithm for combinatorial optimization problems

引用

FRONTIERS IN ENERGY RESEARCH 2023年 11卷

作者： Hu, Enze He, Jianjun Shen, Shuai Cent South Univ Sch Automation Changsha Peoples R China

The discrete state transition algorithm (DSTA) has been wildly applied to deal with combinatorial optimization problems. However, its low convergence accuracy limits its application in large-scale optimization problems. Aiming at the convergence performance and search intensity of the algorithm, a hybrid discrete state transition algorithm (HDSTA) is proposed in this work by introducing tabu search and elite solution set. Firstly, a searching mechanism with the integration of DSTA and tabu search (TS) is established, which allows moving to adjacent solutions at an increased cost to escape from the local optimum. Specifically, a tabu list as adaptive memory is adopted to avoid the loop when deviating from local optima. Secondly, an elite solution set is introduced to integrate the information of the previous optimal solution and the global optimal solution, and the search strategy is modified to expand the range and diversity of candidate solutions. Finally, the proposed HDSTA is verified according to the real data on two well-known optimization problems (staff assignment problem and traveling salesman problem) and the real data of an industrial case. The experimental results show the effectiveness of the proposed algorithm in large-scale optimization problems.

关键词： hybrid discrete state transition algorithm tabu search combinatorial optimization problems elite solution set multi-AGV task assignment problem

来源：评论

学校读者我要写书评

暂无评论

Set-theoretic comparison of mappings of combinatorial optimization problems to Hopfield neural networks

引用

SYSTEMS AND COMPUTERS IN JAPAN 1996年第6期27卷 45-59页

作者： Matsuda, S Member Computer and Communications Research Center Tokyo Electric Power Company Tokyo Japan 100

In solving combinatorial optimization problems by Hopfield neural networks, mappings of the problems to the networks are not made so carefully. Although many mappings of, for example, the traveling salesman problems (TSP) have been proposed, their theoretical comparisons are not yet made. In this paper, taking two typical mappings of TSP as examples, their theoretical comparisons are made to prove the superiority of one over the other by the asymptotical stability and unstability theory of the solutions shown by Matsuda [8, 9]. This theoretical comparison method could be applicable to mappings of many other combinatorial optimization problems.

关键词： Hopfield neural network combinatorial optimization problems traveling salesman problems mapping of the problem to network

来源：评论

学校读者我要写书评

暂无评论

Leveraging Transfer Learning in Deep Reinforcement Learning for Solving combinatorial optimization problems Under Uncertainty

引用

IEEE ACCESS 2024年 12卷 181477-181497页

作者： Ezzahra Achamrah, Fatima Univ Sheffield Sheffield Univ Management Sch Sheffield S10 1FL England

In recent years, addressing the inherent uncertainties within combinatorial optimization problems (COPs) reveals the limitations of traditional optimization methods. Although these methods are often effective in deterministic settings, they may lack flexibility and adaptability to navigate the uncertain nature of real-world COP/s. Deep Reinforcement Learning (DRL) has emerged as a promising approach for dynamic decision-making within these complex environments. Yet, the application of DRL in solving COP/s highlights key limitations for the generalization process across various problem instances without extensive retraining and customization for each new variant, leading to notable computational costs and inefficiencies. To address these challenges, this paper introduces a novel framework that combines the adaptability and learning capabilities of DRL with the efficiency of Transfer Learning (TL) and Neural Architecture Search. This framework enables the leveraging of knowledge gained from solving COP/s to enhance the solving of different but related COP/s, thereby eliminating the necessity for retraining models from scratch for each new problem variant to be solved. The framework was evaluated on over 1,500 benchmark instances across 10 stochastic and deterministic variants of the vehicle routing problem. Across extensive experiments, the approach consistently improves solution quality and computational efficiency. On average, it achieves at least a 5% improvement in solution quality and a 20% reduction in CPU time compared to state-of-the-art methods, with some variants showing even more substantial gains. For large-scale instances over 200 customers, the TL process requires only 10-15% of the time needed to train models from scratch, while maintaining solution quality, laying the groundwork for future research in this area.

关键词： optimization Deep reinforcement learning Uncertainty Transfer learning Heuristic algorithms Adaptation models Stochastic processes Computational modeling Vehicle dynamics Routing combinatorial optimization problems uncertainty deep reinforcement learning transfer learning vehicle routing problem

来源：评论

学校读者我要写书评

暂无评论

Multi-center variable-scale search algorithm for combinatorial optimization problems with the multimodal property

引用

APPLIED SOFT COMPUTING 2019年 84卷 105726-000页

作者： Lu, Hui Zhou, Rongrong Cheng, Shi Shi, Yuhui Beihang Univ Sch Elect & Informat Engn Beijing 100191 Peoples R China Shaanxi Normal Univ Sch Comp Sci Xian 710119 Shaanxi Peoples R China Southern Univ Sci & Technol Dept Comp Sci & Engn Shenzhen Key Lab Computat Intelligence Shenzhen 518055 Peoples R China

combinatorial optimization problems (COPs) are discrete problems arising from aerospace, bioinformatics, manufacturing, and other fields. One of the classic COPs is the scheduling problem. Moreover, these problems are usually multimodal optimization problems with a quantity of global and local optima. As a result, many search algorithms can easily become trapped into local optima. In this article, we propose a multi-center variable-scale search algorithm for solving both single-objective and multi-objective COPs. The algorithm consists of two distinct points. First, the multi-center strategy chooses several individuals with better performance as the only parents of the next generation, which means that there are a number of separate searching areas around the searching center. Second, the next generation of the population is produced by a variable-scale strategy with an exponential equation based on the searching center. The equation is designed to control the neighborhood scale, and adaptively realize the large-scale and small-scale searches at different search stages to balance the maintenance of diversity and convergence speed. In addition, an approach of adjusting centers is proposed concerning the number and distribution of centers for solving multi-objective COPs. Finally, the proposed algorithm is applied to three COPs, including the well-known flexible job shop scheduling problem, the unrelated parallel machine scheduling problem, and the test task scheduling problem. Both the single-objective optimization algorithm and the multi-objective optimization algorithm demonstrate competitive performance compared with existing methods. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Multi-center strategy Variable-scale search strategy Recursive strategy Multimodal property combinatorial optimization problems

来源：评论

学校读者我要写书评

暂无评论

Adaptive elitist-ant system for solving combinatorial optimization problems

引用

APPLIED SOFT COMPUTING 2021年 105卷 107293-107293页

作者： Abuhamdah, Anmar Taibah Univ Coll Business Adm Dept Management Informat Syst Medina Saudi Arabia

This work investigates the effects achieved by using an adaptive elite pool over a basic population-based approach, such as, the ant system approach, to different combinatorial optimization problems (COPs). optimization methods are generally considered a good methodology for solving COPs, while population-based approaches are considered better for exploring the search space and local-based approaches are considered better for exploiting the search space. However, some of these approaches are also hybridized in order to balance between exploiting and exploring the search space. Using an adaptive elite pool offers further balance while also adaptively tuning the importance parameter. Taken together, these three processes may improve and enhance the efficiency of any given search. In this work, three COPs (i.e. CVRP, STSP and 0-1 MKP) are used as test domains. In order to evaluate the effectiveness of using an adaptive elite pool, a comparison is made among the original ant system algorithm, the hybrid Elitist-Ant system algorithm, and other approaches drawn from the literature. Experimental results indicate that using an adaptive elite pool enhances the algorithm and is often able to produce better-quality solutions than other approaches. Where the adaptive elitist-ant system approach obtained 10 out of 14 best known results for CVRP, 20 out of 29 optimal solution results for STSP, 9 out of 11 best known results for 0-1 MKP, and generally better than other individuals approaches in term of better, worse, and similar results. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Meta-heuristic Ant Colony optimization Hybrid Elitist-Ant System Adaptive elitist-ant system combinatorial optimization problems

来源：评论

学校读者我要写书评

暂无评论

Methods for solving combinatorial optimization problems: a review

International Core Journal of Engineering

引用

International Core Journal of Engineering 2021年第11期7卷 360-364页

作者： Hongling Ma

With the emergence of new fields of social networks and biological networks and the advancement of theoretical computer science, the research on combinatorial optimization problems has experienced explosive growth. combinatorial optimization problems are an important branch of computer science and operations research, which mainly studying the solution methods of discrete structure optimization problems. The research of combinatorial optimization problem involves the fields of information technology, communication network, computer vision and so on. In this paper, we introduced typical combinatorial optimization problems: minimum vertex cover problem, minimum weighted vertex cover problem, maximum clique problem, and summarized various algorithms for solving combinatorial optimization problems. Finally, the shortcomings of each algorithm are shown.

关键词： combinatorial optimization problems Minimum vertex cover problem Minimum weighted vertex cover problem Maximum clique problem

来源：评论

学校读者我要写书评

暂无评论

Performance Improvement of Heuristic Algorithms for Large Scale combinatorial optimization problems using Lebesgue Spectrum Filter

Performance Improvement of Heuristic Algorithms for Large Sc...

引用

International Joint Conference on Neural Networks

作者： Tomohiro Kato Mikio Hasegawa Kazuyuki Aihara Department of Electrical Engineering Tokyo University of Science Institute of Industrial Science The University of Tokyo

ISBN: (纸本)9781467314886

In this paper, we analyze effectiveness of a new metaheuristic approach, which utilizes ideal spatio-temporal chaotic dynamics generated by Lebesgue Spectrum Filter (LSF). In the previous researches on the additive chaotic noise to the heuristic searches for combinatorial optimization problems, it has been shown that the chaotic sequences with negative autocorrelation improve the performance of asynchronously updated algorithms, such as mutually connected neural networks, asynchronous heuristic searches and so on. The effectiveness of chaos can be understood by the conventional theory of the chaotic CDMA, which showed that the cross-correlation between the sequences with negative autocorrelation becomes lowest. The spatio-temporal chaotic searching dynamics with such lowest cross-correlation has been shown effective to improve asynchronously updated combinatorial optimization algorithms. In this paper, as such asynchronously updated combinatorial optimization algorithms, we introduce the 2-exchange method, the k-opt method, the Lin-Kernighan method, and the Or-opt method, and improve the performance of them by applying the LSF. Our numerical simulation results show that the performances of all above heuristic methods could be improved by using negative autocorrelation.

关键词： Component combinatorial optimization problems K-opt Lin-Kernighan Or-opt Nonlinear Dynamics Lebesgue Spectrum Filter

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：