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

24th International Conference on Computational Science (ICCS)

作者： Djukanovic, Marko Kartelj, Aleksandar Eftimov, Tome Reixach, Jaume Blum, Christian Univ Banja Luka Fac Nat Sci & Math Banja Luka Bosnia & Herceg Univ Belgrade Fac Math Belgrade Serbia Jozef Stefan Inst Comp Syst Ljubljana Slovenia Artificial Intelligence Res Inst IIIA CSIC Campus UAB Bellaterra Spain

ISBN: (纸本)9783031637742;9783031637759

This paper deals with the restricted longest common subsequence (RLCS) problem, an extension of the well-studied longest common subsequence problem involving two sets of strings: the input strings and the restricted strings. This problem has applications in bioinformatics, particularly in identifying similarities and discovering mutual patterns and motifs among DNA, RNA, and protein molecules. We introduce a general search framework to tackle the RLCS problem. Based on this, we present an exact best-first search algorithm and a meta-heuristic Beam Search algorithm. To evaluate the effectiveness of these algorithms, we compare them with two exact algorithms and two approximate algorithms from the literature along with a greedy approach. Our experimental results show the superior performance of our proposed approaches. In particular, our exact approach outperforms the other exact methods in terms of significantly shorter computation times, often reaching an order of magnitude compared to the second-best approach. Moreover, it successfully solves all problem instances, which was not the case with the other approaches. In addition, Beam Search provides close-to-optimal solutions with remarkably short computation times.

关键词： longest common subsequence problem Beam search A* search Restricted Patterns

来源：评论

学校读者我要写书评

暂无评论

A learning search algorithm for the Restricted longest common subsequence problem

引用

EXPERT SYSTEMS WITH APPLICATIONS 2025年 284卷

作者： Djukanovic, Marko Reixach, Jaume Nikolikj, Ana Eftimov, Tome Kartelj, Aleksandar Blum, Christian Univ Banja Luka Fac Nat Sci & Math Mladena Stojanovica 2 Banja Luka 78000 Republic Of Srp Bosnia & Herceg Univ Belgrade Fac Math Studentski Trg 16 Belgrade 104015 Serbia Jozef Stefan Inst Jamova Cesta 39 Ljubljana 1000 Slovenia Artificial Intelligence Res Inst Campus UAB Bellaterra 08193 Spain

This paper addresses the Restricted longest common subsequence (RLCS) problem, an extension of the well-known longest common subsequence (LCS) problem. This problem has significant applications in bioinformatics, particularly for identifying similarities and discovering mutual patterns and important motifs among DNA, RNA, and protein sequences. Building on recent advancements in solving this problem through a general search framework, this paper introduces two novel heuristic approaches designed to enhance the search process by steering it towards promising regions in the search space. The first heuristic employs a probabilistic model to evaluate partial solutions during the search process. The second heuristic is based on a neural network model trained offline using a genetic algorithm. A key aspect of this approach is extracting problem-specific features of partial solutions and the complete problem instance. An effective hybrid method, referred to as the learning beam search, is developed by combining the trained neural network model with a beam search framework. An important contribution of this paper is found in the generation of real-world instances where scientific abstracts serve as input strings, and a set of frequently occurring academic words from the literature are used as restricted patterns. Comprehensive experimental evaluations demonstrate the effectiveness of the proposed approaches in solving the RLCS problem. Finally, an empirical explainability analysis is applied to the obtained results. In this way, key feature combinations and their respective contributions to the success or failure of the algorithms across different problem types are identified.

关键词： longest common subsequence problem Beam search A* search Neural networks Learning heuristics

来源：评论

学校读者我要写书评

暂无评论

A*-Based Compilation of Relaxed Decision Diagrams for the longest common subsequence problem 1

引用

18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Horn, Matthias Raidl, Gunther R. TU Wien Inst Log & Computat Vienna Austria

ISBN: (数字)9783030782306

ISBN: (纸本)9783030782306;9783030782290

We consider the longest common subsequence (LCS) problem and propose a new method for obtaining tight upper bounds on the solution length. Our method relies on the compilation of a relaxed multi-valued decision diagram (MDD) in a special way that is based on the principles of A* search. An extensive experimental evaluation on several standard LCS benchmark instance sets shows that the novel construction algorithm clearly outperforms a traditional top-down construction (TDC) of MDDs. We are able to obtain stronger and at the same time more compact relaxed MDDs than TDC and this in shorter time. For several groups of benchmark instances new best known upper bounds are obtained. In comparison to existing simple upper bound procedures, the obtained bounds are on average 14.8% better.

关键词： longest common subsequence problem Multi-valued decision diagram A* search

来源：评论

学校读者我要写书评

暂无评论

A Policy-Based Learning Beam Search for Combinatorial Optimization 1

引用

23rd European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCOP) Held as Part of EvoStar Conference

作者： Ettrich, Rupert Huber, Marc Raidl, Guenther R. TU Wien Inst Log & Computat Algorithms & Complex Grp Vienna Austria

ISBN: (数字)9783031300356

ISBN: (纸本)9783031300349;9783031300356

Beam search (BS) is a popular incomplete breadth-first search widely used to find near-optimal solutions to hard combinatorial optimization problems in limited time. Its central component is an evaluation function that estimates the quality of nodes encountered on each level of the search tree. While this function is usually manually crafted for a problem at hand, we propose a Policy-Based Learning Beam Search (P-LBS) that learns a policy to select the most promising nodes at each level offline on representative random problem instances in a reinforcement learning manner. In contrast to an earlier learning beam search, the policy function is realized by a neural network (NN) that is applied to all the expanded nodes at a current level together and does not rely on the prediction of actual node values. Different loss functions suggested for beam-aware training in an earlier work, but there only theoretically analyzed, are considered and evaluated in practice on the well-studied longest common subsequence (LCS) problem. To keep P-LBS scalable to larger problem instances, a bootstrapping approach is further proposed for training. Results on established sets of LCS benchmark instances show that P-LBS with loss functions "upper bound" and "cost-sensitive margin beam" is able to learn suitable policies for BS such that results highly competitive to the state-of-the-art can be obtained.

关键词： Beam Search Machine Learning Reinforcement Learning longest common subsequence problem

来源：评论

学校读者我要写书评

暂无评论

Learning Beam Search: Utilizing Machine Learning to Guide Beam Search for Solving Combinatorial Optimization problems 7th

Learning Beam Search: Utilizing Machine Learning to Guide Be...

引用

7th International Conference on Machine Learning, Optimization, and Data Science (LOD) / 1st Symposium on Artificial Intelligence and Neuroscience (ACAIN)

作者： Huber, Marc Raidl, Guenther R. TU Wien Inst Log & Computat Algorithms & Complex Grp Vienna Austria

ISBN: (纸本)9783030954703;9783030954697

Beam search (BS) is a well-known incomplete breadth-first-search variant frequently used to find heuristic solutions to hard combinatorial optimization problems. Its key ingredient is a guidance heuristic that estimates the expected length (cost) to complete a partial solution. While this function is usually developed manually for a specific problem, we propose a more general Learning Beam Search (LBS) that uses a machine learning model for guidance. Learning is performed by utilizing principles of reinforcement learning: LBS generates training data on its own by performing nested BS calls on many representative randomly created problem instances. The general approach is tested on two specific problems, the longest common subsequence problem and the constrained variant thereof. Results on established sets of benchmark instances indicate that the BS with models trained via LBS is highly competitive. On many instances new so far best solutions could be obtained, making the approach a new state-of-the-art method for these problems and documenting the high potential of this general framework.

关键词： Beam search Combinatorial optimization Machine learning longest common subsequence problem

来源：评论

学校读者我要写书评

暂无评论

Traffic speed mapping with cellular network signaling data by FOSS4G

引用

SPATIAL INFORMATION RESEARCH 2022年第1期30卷 131-142页

作者： Wang, Weifeng Zhu, Kemin Liu, Junli Hu, Jinghao Raganvan, Venkatesh Xu, Jiang Song, Xianfeng Chinese Acad Sci Coll Resources & Environm Beijing 100049 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Osaka City Univ Grad Sch Engn Osaka 5588585 Japan Beijing Homcom Technol Co Ltd Beijing 100086 Peoples R China

Mapping traffic speed on road networks is crucial for urban traffic management and the development of intelligent transportation systems. Traditionally, information regarding traffic speed can be obtained from location-fixed sensors, such as loop detectors and cameras;however, these methods are limited to major road crosses. Recently, a considerable attention has been paid to utilizing vehicles with mobile phones as probes for collecting traffic information. This study proposes an open-source GIS approach to map traffic speeds in a road network. First, public service vehicles (PSVs) were identified from cellular network signaling data by measuring the similarity between cell-ID trajectories and bus routes. Then, the cell-ID trajectories of PSVs were refined into high-quality spatiotemporal trajectories, and projected onto the road network via heuristic global optimization. Finally, hourly traffic speed maps were computed by weighing the speeds of the PSVs in the road network. The approach was implemented using free and open source software for geospatial mapping stacks of toolkits (Python, TimescaleDB/PostGIS, Pandas/Pygmo2, and Matplotlib/Seaborn);this application demonstrated good results using cellular network signaling data and GPS trajectories collected in Huilongguan district, Beijing, China. Moreover, this demonstration illustrates that probe mobile monitoring is emerging as a critical technology for traffic monitoring supplements, which can help develop a comprehensive view of the roads and reduce the cost of monitoring a large area.

关键词： Cellular network signaling data Public service vehicles longest common subsequence problem Traffic speed mapping

来源：评论

学校读者我要写书评

暂无评论

Finding longest common subsequences: New anytime A* search results

引用

APPLIED SOFT COMPUTING 2020年 95卷 106499-106499页

作者： Djukanovic, Marko Raidl, Guenther R. Blum, Christian TU Wien Inst Log & Computat Vienna Austria Artificial Intelligence Res Inst IIIA CSIC Campus UAB Bellaterra Spain

The longest common subsequence (LCS) problem aims at finding a longest string that is a subsequence of each string from a given set of input strings. This problem has applications, in particular, in the context of bioinformatics, where strings represent DNA or protein sequences. Existing approaches include numerous heuristics, but only a few exact approaches, limited to rather small problem instances. Adopting various aspects from leading heuristics for the LCS, we first propose an exact A* search approach, which performs well in comparison to earlier exact approaches in the context of small instances. On the basis of A* search we then develop two hybrid A*-based algorithms in which classical A* iterations are alternated with beam search and anytime column search, respectively. A key feature to guide the heuristic search in these approaches is the usage of an approximate expected length calculation for the LCS of uniform random strings. Even for large problem instances these anytime A* variants yield reasonable solutions early during the search and improve on them over time. Moreover, they terminate with proven optimality if enough time and memory is given. Furthermore, they yield upper bounds and, thus, quality guarantees when terminated early. We comprehensively evaluate the proposed methods using most of the available benchmark sets from the literature and compare to the current state-of-the-art methods. In particular, our algorithms are able to obtain new best results for 82 out of 117 instance groups. Moreover, in most cases they also provide significantly smaller optimality gaps than other anytime algorithms. (C) 2020 Elsevier B.V. All rights reserved.

关键词： longest common subsequence problem Hybrid metaheuristic A* search Beam search Anytime column search

来源：评论

学校读者我要写书评

暂无评论

Analysis of Evolutionary Algorithms for the longest common subsequence problem

引用

ALGORITHMICA 2010年第1期57卷 170-186页

作者： Jansen, Thomas Weyland, Dennis Tech Univ Dortmund Fak Informat LS Effiziente Algorithmen & Komplexitatstheorie D-44221 Dortmund Germany IDSIA Dalle Molle Inst Artificial Intelligence CH-6928 Manno Lugano Switzerland

In the longest common subsequence problem the task is to find the longest sequence of letters that can be found as a subsequence in all members of a given finite set of sequences. The problem is one of the fundamental problems in computer science with the task of finding a given pattern in a text as an important special case. It has applications in bioinformatics;problem-specific algorithms and facts about its complexity are known. Motivated by reports about good performance of evolutionary algorithms for some instances of this problem a theoretical analysis of a generic evolutionary algorithm is performed. The general algorithmic framework encompasses EAs as different as steady state GAs with uniform crossover and randomized hill-climbers. For all these algorithms it is proved that even rather simple special cases of the longest common subsequence problem can neither be solved to optimality nor approximately be solved up to an approximation factor arbitrarily close to 2.

关键词： Evolutionary algorithms longest common subsequence problem Run time analysis Crossover

来源：评论

学校读者我要写书评

暂无评论

Dynamic Signature Verification through the longest common subsequence problem and Genetic Algorithms

Dynamic Signature Verification through the Longest Common Su...

引用

2010 IEEE World Congress on Computational Intelligence

作者： Flores-Mendez, Alejandro Bernal-Urbina, Manuel IPN CINVESTAV Dept Math Mexico City DF Mexico Ijam Consult Mexico City DF Mexico

ISBN: (纸本)9781424481262

The following paper includes an automated system that shows the use of signature data for biometric verification. The verification uses the dynamic distinctiveness of the signature, thus this method lies within those referred as dynamic or on-line signature verification. This proposal makes use of a variation of the longest common subsequence problem together with Genetic Algorithm for this purpose.

关键词： biometric verification digital signatures dynamic signature verification genetic algorithm genetic algorithms handwriting recognition learning (artificial intelligence) longest common subsequence problem online signature verification

来源：评论

学校读者我要写书评

暂无评论

Analysis of Evolutionary Algorithms for the longest common subsequence problem 07

Analysis of Evolutionary Algorithms for the Longest Common S...

引用

Annual Conference of Genetic and Evolutionary Computation Conference

ISBN: (纸本)9781595936974

关键词： Evolutionary algorithms longest common subsequence problem Run time analysis Crossover

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：