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

A Population-Based Iterated greedy Algorithm for Distributed Assembly No-Wait Flow-Shop Scheduling Problem

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2023年第5期19卷 6692-6705页

作者： Zhao, Fuqing Xu, Zesong Wang, Ling Zhu, Ningning Xu, Tianpeng Jonrinaldi, J. Lanzhou Univ Technol Sch Comp & Commun Technol Lanzhou 730050 Peoples R China Tsinghua Univ Dept Automat Beijing 10084 Peoples R China Univ Andalas Dept Ind Engn Padang 25163 Indonesia

This article investigates a distributed assembly no-wait flow-shop scheduling problem (DANWFSP), which has important applications in manufacturing systems. The objective is to minimize the total flowtime. A mixed-integer linear programming model of DANWFSP with total flowtime criterion is proposed. A population-based iterated greedy algorithm (PBIGA) is presented to address the problem. A new constructive heuristic is presented to generate an initial population with high quality. For DANWFSP, an accelerated NR3 algorithm is proposed to assign jobs to the factories, which improves the efficiency of the algorithm and saves CPU time. To enhance the effectiveness of the PBIGA, the local search method and the destruction-construction mechanisms are designed for the product sequence and job sequence, respectively. A selection mechanism is presented to determine, which individuals execute the local search method. An acceptance criterion is proposed to determine whether the offspring are adopted by the population. Finally, the PBIGA and seven state-of-the-art algorithms are tested on 810 large-scale benchmark instances. The experimental results show that the presented PBIGA is an effective algorithm to address the problem and performs better than recently state-of-the-art algorithms compared in this article.

关键词： Production facilities Job shop scheduling Statistics Sociology greedy algorithms Search problems Processor scheduling Distributed assembly scheduling iterated greedy algorithm no-wait flow-shop total flowtime

来源：评论

学校读者我要写书评

暂无评论

On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations

引用

NUMERICAL algorithms 2023年第1期92卷 639-664页

作者： Frommer, Andreas Szyld, Daniel B. Berg Univ Wuppertal Dept Math D-42097 Wuppertal Germany Temple Univ Dept Math Philadelphia PA 19122 USA

We extend results known for the randomized Gauss-Seidel and the Gauss-Southwell methods for the case of a Hermitian and positive definite matrix to certain classes of non-Hermitian matrices. We obtain convergence results for a whole range of parameters describing the probabilities in the randomized method or the greedy choice strategy in the Gauss-Southwell-type methods. We identify those choices which make our convergence bounds best possible. Our main tool is to use weighted l(1)-norms to measure the residuals. A major result is that the best convergence bounds that we obtain for the expected values in the randomized algorithm are as good as the best for the deterministic, but more costly algorithms of Gauss-Southwell type. Numerical experiments illustrate the convergence of the method and the bounds obtained. Comparisons with the randomized Kaczmarz method are also presented.

关键词： Randomized Gauss-Seidel Convergence bounds greedy algorithms Gauss-Southwell algorithm Randomized smoother

来源：评论

学校读者我要写书评

暂无评论

Sensor Selection With Cost Function Using Nondominated-Solution-Based Multiobjective greedy Method

引用

IEEE SENSORS JOURNAL 2023年第24期23卷 31006-31016页

作者： Saito, Yuji Nakai, Kumi Nagata, Takayuki Yamada, Keigo Nonomura, Taku Sakaki, Kazuki Nunome, Yoshio Tohoku Univ Frontier Res Inst Interdisciplinary Sci Sendai Miyagi 9800845 Japan Natl Inst Adv Ind Sci & Technol Dept Energy & Environm Tsukuba Ibaraki 3058564 Japan Tohoku Univ Dept Aerosp Engn Sendai Miyagi 9800845 Japan Japan Aerosp Explorat Agcy Tsukuba Ibaraki 3050047 Japan Japan Aerosp Explorat Agcy Kakuda Miyagi 9811525 Japan

In this study, a new greedy sensor selection algorithm with a cost constraint is proposed based on a nondominated-solution-based multiobjective greedy (NMG) method, and its performance is investigated by comparing it with a previously proposed method. The cost function is simultaneously considered with the D-optimality criterion, and the sensor set is selected based on the idea of the nondominated solution. Although a multiobjective optimization method for sensor selection with a cost constraint was previously considered based on the linear combination of the objectives, it requires a hyperparameter that determines the balance between the actual objective and the cost of the optimization. On the other hand, the proposed algorithm can obtain the Pareto solution without tuning the balance between the actual objective and the cost. We demonstrate the effectiveness of the proposed algorithm on the three different real datasets that are related to the sea surface temperature field, the flowfield around an airfoil, and the combustion field in a rocket chamber. A binary cost function is virtually imposed for each potential sensor location, and a sensor selection problem with a cost constraint is simulated. The results of the numerical experiments demonstrated that the NMG method could field a Pareto solution, and the objective values of almost all the sensor sets at a certain cost selected by the proposed method are superior to those selected by the previous method.

关键词： Sensors Costs Sensor phenomena and characterization Cost function greedy algorithms Sensor placement Sea measurements Cost constraint data-driven sensor selection greedy algorithm multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

A Survey on greedy Based algorithms for Biclustering of Gene Expression Microarray Data

A Survey on Greedy Based Algorithms for Biclustering of Gene...

引用

International Conference on Information Technology (ICIT)

作者： Bhawani Sankar Biswal Prateeka Mishra Anjali Mohapatra Swati Vipsita Dept. of CSE IIIT Bhubaneswar Bhubaneswar India

ISBN: (纸本)9781509035854

In the context of gene expression microarray data, biclustering is a technique to identify clusters of genes that are co-expressed under clusters of conditions. It usually has high computational complexity (NP-Hard). In computer science domain, combinatorial problems like biclustering, refer to the tasks associated with the discovery of grouping, ordering or assigning a discrete set of objects fulfilling some fixed constraints. greedy Search approach is a popular method often used for solving combinatorial problems. It is adoptable in this context because of its variety aspects of search performance. Its variability caused by randomization and the robustness in parameter settings improves the search performance. This review article presents a brief survey of various greedy based biclustering algorithms that are being frequently applied on gene expression microarray data. These algorithms are further classified into iterative greedy approach and stochastic greedy approach based on their search criteria.

关键词： biology computing computational complexity data handling genetics greedy algorithms iterative methods pattern clustering randomised algorithms search problems stochastic processes biology computing greedy algorithm tabu search data processing greedy method iterative methods Markov chain complexity classes Cluster Analysis randomized algorithms Genetics Stochastic Processes

来源：评论

学校读者我要写书评

暂无评论

Stability of convergence rates: kernel interpolation on non-Lipschitz domains

引用

IMA JOURNAL OF NUMERICAL ANALYSIS 2025年第2期45卷 777-798页

作者： Wenzel, Tizian Santin, Gabriele Haasdonk, Bernard Univ Stuttgart Inst Appl Anal & Numer Simulat D-70569 Stuttgart Germany Ca Foscari Univ Venice Dept Environm Sci Informat & Stat I-30123 Venice Italy

Error estimates for kernel interpolation in Reproducing Kernel Hilbert Spaces usually assume quite restrictive properties on the shape of the domain, especially in the case of infinitely smooth kernels like the popular Gaussian kernel. In this paper we prove that it is possible to obtain convergence results (in the number of interpolation points) for kernel interpolation for arbitrary domains $\varOmega \subset{\mathbb{R}} <^>{d}$, thus allowing for non-Lipschitz domains including e.g., cusps and irregular boundaries. Especially we show that, when going to a smaller domain $\tilde{\varOmega } \subset \varOmega \subset{\mathbb{R}} <^>{d}$, the convergence rate does not deteriorate-i.e., the convergence rates are stable with respect to going to a subset. We obtain this by leveraging an analysis of greedy kernel algorithms. The impact of this result is explained on the examples of kernels of finite as well as infinite smoothness. A comparison to approximation in Sobolev spaces is drawn, where the shape of the domain $\varOmega $ has an impact on the approximation properties. Numerical experiments illustrate and confirm the analysis.

关键词： kernel methods greedy algorithms convergence rates

来源：评论

学校读者我要写书评

暂无评论

Informative Path Planning for Active Regression With Gaussian Processes via Sparse Optimization

引用

IEEE TRANSACTIONS ON ROBOTICS 2025年 41卷 2184-2199页

作者： Dutta, Shamak Wilde, Nils Smith, Stephen L. Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2G 1V8 Canada Dalhousie Univ Dept Comp Sci Halifax NS B3H 4R2 Canada

We study informative path planning for active regression in Gaussian Processes (GP). Here, a resource constrained robot team collects measurements of an unknown function, assumed to be a sample from a GP, with the goal of minimizing the trace of the M-weighted expected squared estimation error covariance (where M is a positive semidefinite matrix) resulting from the GP posterior mean. While greedy heuristics are a popular solution in the case of length constrained paths, it remains a challenge to compute optimal solutions in the discrete setting subject to routing constraints. We show that this challenge is surprisingly easy to circumvent. Using the optimality of the posterior mean for a class of functions of the squared loss yields an exact formulation as a mixed integer program. We demonstrate that this approach finds optimal solutions in a variety of settings in seconds and when terminated early, it finds sub-optimal solutions of higher quality than existing heuristics.

关键词： Robots Robot sensing systems greedy algorithms Path planning Sensor placement Routing Gaussian processes Estimation error Computational modeling Robot kinematics Gaussian processes (GP) informative path planning (IPP) robot information gathering

来源：评论

学校读者我要写书评

暂无评论

greedy Conjecture for the Shortest Common Superstring Problem and Its Strengthenings 31st

Greedy Conjecture for the Shortest Common Superstring Proble...

引用

31st International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Nikolaev, Maksim S. Russian Acad Sci Steklov Inst Math St Petersburg St Petersburg Russia

ISBN: (纸本)9783031721991;9783031722004

In the Shortest Common Superstring problem, one needs to find the shortest superstring for a set of strings. This problem is APX-hard, and many approximation algorithms were proposed, with the current best approximation factor of 2.466. Whereas these algorithms are technically involved, for more than thirty years the greedy Conjecture remains unsolved, that states that the greedy Algorithm "take two strings with the maximum overlap;merge them;repeat" is a 2-approximation. This conjecture is still open, and one way to approach it is to consider its stronger version, which may make the proof easier due to the stronger premise or provide insights from its refutation. In this paper, we propose two directions to strengthen the conjecture. First, we introduce the Locally greedy Algorithm (LGA), that selects a pair of strings not with the largest overlap but with the locally largest overlap, that is, the largest among all pairs of strings with the same first or second string. Second, we change the quality metric: instead of length, we evaluate the solution by the number of occurrences of an arbitrary symbol. Despite the double strengthening, we prove that LGA is a uniform 4-approximation, that is, it always constructs a superstring with no more than four times as many occurrences of an arbitrary symbol as any other superstring. At the same time, we discover the limitations of the greedy heuristic: we show that LGA is at least 3-approximation, and the greedy Algorithm is at least uniform 2.5-approximation. These result show that if the greedy Conjecture is true, it is not because the greedy Algorithm is locally greedy or is uniformly 2-approximation.

关键词： approximation greedy algorithms greedy conjecture shortest common superstring superstring

来源：评论

学校读者我要写书评

暂无评论

Enhancing the intelligibility of decision trees with concise and reliable probabilistic explanations

引用

DATA & KNOWLEDGE ENGINEERING 2025年 156卷

作者： Bounia, Louenas Setitra, Insaf UTC Compiegne Lab Heudiasyc UMR CNRS 7253 Compiegne France

This work deals with explainable artificial intelligence (XAI), specifically focusing on improving the intelligibility of decision trees through reliable and concise probabilistic explanations. Decision trees are popular because they are considered highly interpretable. Due to cognitive limitations, abductive explanations can be too large to be interpretable by human users. When this happens, decision trees are far from being easily interpretable. In this context, our goal is to enhance the intelligibility of decision trees by using probabilistic explanations. Drawing inspiration from previous work on approximating probabilistic explanations, we propose a greedy algorithm that enables us to derive concise and reliable probabilistic explanations for decision trees. We provide a detailed description of this algorithm and compare it to the state-ofthe-art SAT encoding. In the order to highlight the gains in intelligibility while emphasizing its empirical effectiveness, we will conduct in-depth experiments on binary decision trees as well as on cases of multi-class classification. We expect significant gains in intelligibility. Finally, to demonstrate the usefulness of such an approach in a practical context, we chose to carry out additional experiments focused on text classification, in particular the detection of emotions in tweets. Our objective is to determine the set of words explaining the emotion predicted by the decision tree.

关键词： eXplainable AI Decision trees Probabilistic explanations greedy algorithms Tweet Sentiment Extraction

来源：评论

学校读者我要写书评

暂无评论

Edge Selections in Bilinear Dynamic Networks

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第1期69卷 331-338页

作者： de Oliveira, Arthur Castello B. Siami, Milad Sontag, Eduardo D. Northeastern Univ Dept Elect & Comp Engn Boston MA 02115 USA Northeastern Univ Dept Bioengn Boston MA 02115 USA

We develop some basic principles for the design and robustness analysis of a continuous-time bilinear dynamical network, where an attacker can manipulate the strength of the interconnections/edges between some of the agents/nodes. We formulate the edge protection optimization problem of picking a limited number of attack-free edges and minimizing the impact of the attack over the bilinear dynamical network. In particular, the H-2-norm of bilinear systems is known to capture robustness and performance properties analogous to its linear counterpart and provide valuable insights for identifying which edges are most sensitive to attacks. The exact optimization problem is combinatorial in the number of edges, and brute-force approaches show poor scalability. However, we show that the H-2-norm as a cost function is supermodular and, therefore, allows for efficient greedy approximations of the optimal solution. We illustrate and compare the effectiveness of our theoretical findings via numerical simulations.

关键词： Nonlinear systems Optimization Vehicle dynamics Kernel Convergence Task analysis Robustness Bilinear dynamical network greedy algorithms networked control systems nonlinear control systems optimization robustness analysis

来源：评论

学校读者我要写书评

暂无评论

Mixed Criticality Reward-Based Systems Using Resource Reservation

引用

IEEE ACCESS 2024年 12卷 49134-49150页

作者： Ali, Amjad Zeb, Shah Alruwaili, Madallah Khattak, Asad Masood Hayat, Bashir Kim, Ki-Il Univ Swat Dept Comp & Software Technol Swat 19120 Khyber Pakhtunk Pakistan Jouf Univ Coll Comp & Informat Sci Sakaka 2014 Aljouf Saudi Arabia Zayed Univ Coll Technol Innovat Dubai U Arab Emirates Inst Management Sci Ctr Excellence IT Peshawar 25000 Khyber Pakhtunk Pakistan Chungnam Natl Univ Dept Comp Sci & Engn Daejeon 34134 South Korea

Real-time systems mostly interact with the external world and each input operation must meet predetermined deadlines to be useful. However, in many real-time applications, a partial result is also acceptable. We developed a reward-based mixed criticality system based on the resource reservation approach to address the problem of ensuring the effective execution of low- and high-criticality tasks in both low- and high modes, even under heavy workloads. Using dedicated servers with pessimistic resource allocation for each high criticality task ensured their execution in both modes unaffected by low criticality tasks. The surplus resources are reclaimed and assigned to low critical tasks' server by utilizing a greedy reclamation of unused bandwidth (GRUB) algorithm. Three strategies were suggested for server allocation to low criticality tasks: a dedicated server for all low criticality tasks, a single server for each low criticality task, and two servers (mandatory and optional) for each low criticality task. Our analysis revealed efficiency of the first approach by achieving 100% schedulability at a 1.1 target utilization, scheduling 20% and 50% more task sets than the second and third approaches, respectively. Moreover, the effectiveness of the proposed approach over existing imprecise mixed criticality approaches were demonstrated through comprehensive experimentation.

关键词： Task analysis Real-time systems Servers Processor scheduling Job shop scheduling Multicore processing Schedules greedy algorithms Resource management greedy reclamation imprecise computation imprecise mixed criticality (IMC) systems mixed criticality systems real-time systems resource reservation reward-based scheduling servers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：