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

The problem of sensor placement for triangulation-based localisation

INTERNATIONAL JOURNAL OF AUTOMATION AND CONTROL 2011年第3期5卷 245-253页

作者： Gorbenko, Anna Mornev, Maxim Popov, Vladimir Sheka, Andrey Ural State Univ Dept Intelligent Syst & Robot Lenin St51 Ekaterinburg 620083 Russia

Recent technological advances have facilitated the widespread use of sensor networks in many applications. In particular, deploying many sensors in a workspace provides a valuable alternative to on-board localisation for mobile robots. Coverage and placement problems for sensors which jointly estimate the states of targets received considerable attention recently. In this paper, we consider the problem of sensor placement for triangulation-based localisation. The problem is non-deterministic polynomial-time hard in its most general form. We present a reformulation of an existing integer linear programme for the problem where we transform the original to an equivalent integer linear programme with less number of variables. We consider an approach to solve the problem that is based on constructing a logical model for the problem. In particular, we give explicit polynomial reductions from the decision version of the problem to satisfiability problem (SAT) and 3-satisfiability problem (3SAT).

关键词： sensor networks robot localisation triangulation-based localisation sensor placement integer linear programme NP-hardness logical model satisfiability problem GAs genetic algorithms local search algorithms

来源：评论

学校读者我要写书评

暂无评论

Estimating attraction basin sizes of combinatorial optimization problems

引用

PROGRESS IN ARTIFICIAL INTELLIGENCE 2018年第4期7卷 369-384页

作者： Elorza, Anne Hernando, Leticia Mendiburu, Alexander Lozano, Jose A. Univ Basque Country UPV EHU Intelligent Syst Grp Dept Comp Sci & Artificial Intelligence San Sebastian 20018 Spain Univ Basque Country UPV EHU Intelligent Syst Grp Dept Comp Architecture & Technol San Sebastian 20018 Spain

Given a particular instance of a combinatorial optimization problem, the knowledge about the attraction basin sizes can help to analyze the difficulty encountered by local search algorithms while solving it. As calculating these sizes exhaustively is computationally intractable, we focus on methods for their estimation. The accuracy of some of these estimation methods depends on the way in which the sample of solutions of the search space is chosen. In this paper, we propose a novel sampling method, which incorporates the knowledge obtained by the already explored solutions into the sampling strategy. So, in contrast to those that already exist, our method can adapt its behavior to the characteristics of the particular attraction basin. We apply our proposal to a number of instances of three famous problems: the quadratic assignment problem, the linear ordering problem and the permutation flow shop scheduling problem. We consider permutation sizes n = 10 and n = 12 and three different neighborhoods: adjacent swap, 2-exchange and insert, and observe that the new method generally outperforms those that already exist.

关键词： Combinatorial optimization problems Neighborhoods Attraction basins local optima local search algorithms Estimators

来源：评论

学校读者我要写书评

暂无评论

Parallelizing local search for CNF satisfiability using vectorization and PVM

引用

ACM Journal of Experimental Algorithmics 2002年 7卷

作者： Iwama, Kazuo Kawai, Daisuke Miyazaki, Shuichi Okabe, Yasuo Umemoto, Jun Graduate School of Informatics Kyoto University Japan

The purpose of this paper is to speed up the local search algorithm for the CNF Satisfiability problem. Our basic strategy is to run some 105 independent search paths simultaneously using PVM on a vector supercomputer VPP800, which consists of 40 vector processors. Using the above parallelization and vectorization together with some improvement of data structure, we obtained 600-times speedup in terms of the number of flips the local search can make per second, compared to the original GSAT by Selman and Kautz. We ran our parallel GSAT for benchmark instances and compared the running time with those of existing SAT programs. We could observe an apparent benefit of parallelization: Especially, we were able to solve two instances that have never been solved before this paper. We also tested parallel local search for the SAT encoding of the class scheduling problem. Again we were able to get almost the best answer in reasonable time. © 2015 Association for Computing Machinery. All rights reserved.

关键词： algorithms CNF satisfiability D.1.3 [programming techniques]: concurrent programming - distributed programming, parallel programming Distributed computing Experimentation G.2.1 [discrete mathematics]: combinatorics - combinatorial algorithms local search algorithms Parallelization PVM Vector supercomputer Vectorization

来源：评论

学校读者我要写书评

暂无评论

ANALYZING WALKSAT ON RANDOM FORMULAS

引用

SIAM JOURNAL ON COMPUTING 2014年第4期43卷 1456-1485页

作者： Coja-Oghlan, Amin Frieze, Alan Goethe Univ Frankfurt Math Inst D-60325 Frankfurt Germany Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA

Let Phi be a uniformly distributed random k-SAT formula with n variables and m clauses. We prove that the Walksat algorithm from Papadimitriou [On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1991, pp. 163-169] and Schoning [A probabilistic algorithm for k-SAT and constraint satisfaction problems, in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 410-414] finds a satisfying assignment of Phi in polynomial time with high probability if m/n <= rho.2(k)/k for a certain constant rho > 0. This is an improvement by a factor of Theta(k) over the best previous analysis of Walksat from Coja-Oghlan et al. [On smoothed k-CNF formulas and the Walksat algorithm, in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2009, pp. 451-460].

关键词： random structures phase transitions k-SAT local search algorithms

来源：评论

学校读者我要写书评

暂无评论

APPLICATION OF HYBRID META-HEURISTIC ALGORITHM FOR ASSIGNING REAL-TIME TASKS TO HETEROGENEOUS PROCESSORS 6

APPLICATION OF HYBRID META-HEURISTIC ALGORITHM FOR ASSIGNING...

引用

6th International Conference on Computing, Communication and Networking Technologies (ICCCNT)

作者： Marimuthu, Poongothai Arumugam, Rajeswari Coimbatore Inst Technol Dept Elect & Commun Engn Coimbatore 641014 Tamil Nadu India

ISBN: (纸本)9781479979837

Heterogeneous multiprocessor system has the capability for providing low cost and high performance. Nevertheless, in order to take advantage of computing power of heterogeneous system, it is essential to use an efficient scheduling algorithm for task allocation to the available processors. This research mainly focuses on the development of task assignment algorithm for heterogeneous multiprocessor system. Assigning real-time tasks in heterogeneous multiprocessor are in general a challenging problem and NP hard. In this paper, Hybrid Max-Min Ant colony optimization algorithm (H-MMAS) is proposed to solve the real-time task assignment problem in heterogeneous multiprocessor. The objective of the proposed algorithm is to get a feasible task assignment solution, and to optimize energy consumption of every feasible task assignment solution. The performance of the proposed H-MMAS algorithm has been tested for consistent and inconsistent heterogeneous multiprocessor systems. Experimental comparisons with existing Modified BPSO algorithm demonstrate the effectiveness of the proposed H-MMAS algorithm.

关键词： ACO Real-time task assignment Heterogeneous processors meta-heuristic algorithm local search algorithms

来源：评论

学校读者我要写书评

暂无评论

Designing Urban Transit Network using Memetic Algorithm

Designing Urban Transit Network using Memetic Algorithm

引用

IEEE Congress on Evolutionary Computation (IEEE CEC)

作者： Ali, Hanan Ba Roman, Adam Jagiellonian Univ Fac Math & Comp Sci Krakow Poland

ISBN: (纸本)9781728183923

Urban transit network design (UTND) problem represents a challenge in designing routes, with a trade-off between serving passengers and operators benefits. In this study, a Memetic Algorithm (MA) is proposed to solve the UTND problem. The algorithm uses the hill climbing local search (HCLS) algorithm as an additional operator for Genetic Algorithm (GA) to improve routes construction during the global search. The proposed method consists of two phases. In the first phase, a set of solutions (transit network designs) is generated as an initial population for MA, where each solution consists of a set of routes. The predefined set of solutions satisfies the constraints such as route length or number of routes, and requirements like lack of loops, and that all nodes are covered by at least one route. In the second phase, the suggested Memetic Algorithm (MA) is used to generate all possible solutions from the predefined set. The MA tries to find the best structured solution that represents the flawless transit network. The proposed MA is applied on the widely examined benchmark problems: Mandl and Mumford networks. The experiment results show that the suggested MA provides significant improvements in terms of the direct trip percentage and average travel time compared to the previous studies.

关键词： Transit Network Design local search algorithms Evolutionary algorithms

来源：评论

学校读者我要写书评

暂无评论

Multi-objective Neutral Neighbors? What could be the definition(s)? 16

Multi-objective Neutral Neighbors? What could be the definit...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Marmion, Marie-Eleonore Aguirre, Hernan Dhaenens, Clarisse Jourdan, Laetitia Tanaka, Kiyoshi Univ Lille CNRS Cent Lille UMR 9189CRIStALInria Lille France Shinshu Univ Fac Engn Matsumoto Nagano Japan

ISBN: (纸本)9781450342063

There is a significant body of research on neutrality and its effects in single-objective optimization. Particularly, the neutrality concept has been precisely defined and the neutrality between neighboring solutions efficiently exploited in local search algorithms. The extension of neutrality to multi-objective optimization is not straightforward and its effects on the dynamics of multi-objective optimization methods are not clearly understood. In order to develop strategies to exploit neutral neighbors in multi-objective local search algorithms, it is important and necessary to clearly define neutrality in the multi-objective context. In this paper, we propose several definitions of the neutrality property between neighboring solutions. A natural definition comes from the Pareto-dominance, widely used in multi-objective optimization. In addition, definitions derived from epsilon and hypervolume indicators are also proposed as such indicators are usually used to compare sets of solutions. We analyze permutation problems under the proposed definitions of neutrality and show that each definition of neutrality leads to a particular structure of the problem.

关键词： neutrality multi-objective optimization local search algorithms

来源：评论

学校读者我要写书评

暂无评论

A Study of Pure Random Walk algorithms on Constraint Satisfaction Problems with Growing Domains

A Study of Pure Random Walk Algorithms on Constraint Satisfa...

引用

8th International Frontiers of Algorithmics Workshop (FAW)

作者： Xu, Wei Gong, Fuzhou Univ Sci & Technol Beijing Sch Automat & Elect Engn Beijing 100083 Peoples R China Chinese Acad Sci Inst Appl Math Acad Math & Syst Sci Beijing Peoples R China

ISBN: (纸本)9783319080161;9783319080154

The performances of two types of pure random walk (PRW) algorithms for a model of constraint satisfaction problems with growing domains (called Model RB) are investigated. Threshold phenomenons appear for both algorithms. In particular, when the constraint density r is smaller than a threshold value r(d), PRW algorithms can solve instances of Model RB efficiently, but when r is bigger than the rd, they fail. Using a physical method, we find out the threshold values for both algorithms. When the number of variables N is large, the threshold values tend to zero, so generally speaking PRW does not work on Model RB.

关键词： constraint satisfaction problems Model RB random walk local search algorithms

来源：评论

学校读者我要写书评

暂无评论

Beyond the Lovasz local Lemma: Point to Set Correlations and Their Algorithmic Applications 60

Beyond the Lovasz Local Lemma: Point to Set Correlations and...

引用

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Achlioptas, Dimitris Iliopoulos, Fotis Sinclair, Alistair UC Santa Cruz Dept Comp Sci Santa Cruz CA 95064 USA Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA USA

ISBN: (纸本)9781728149523

Following the groundbreaking algorithm of Moser and Tardos for the Lovasz local Lemma (LLL), there has been a plethora of results analyzing local search algorithms for various constraint satisfaction problems. The algorithms considered fall into two broad categories: resampling algorithms, analyzed via different algorithmic LLL conditions;and backtracking algorithms, analyzed via entropy compression arguments. This paper introduces a new convergence condition that seamlessly handles resampling, backtracking, and hybrid algorithms, i.e., algorithms that perform both resampling and backtracking steps. Unlike previous work on the LLL, our condition replaces the notion of a dependency or causality graph by quantifying point-to-set correlations between bad events. As a result, our condition simultaneously: (i) captures the most general algorithmic LLL condition known as a special case;(ii) significantly simplifies the analysis of entropy compression applications;(iii) relates backtracking algorithms, which are conceptually very different from resampling algorithms, to the LLL;and most importantly (iv) allows for the analysis of hybrid algorithms, which were outside the scope of previous techniques. We give several applications of our condition, including a new hybrid vertex coloring algorithm that extends the recent breakthrough result of Molloy for coloring triangle-free graphs to arbitrary graphs.

关键词： Lovasz local Lemma local search algorithms backtracking graph coloring random graphs

来源：评论

学校读者我要写书评

暂无评论

Diversity Maximization Under Matroid Constraints 13

Diversity Maximization Under Matroid Constraints

引用

19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Abbassi, Zeinab Mirrokni, Vahab S. Thakur, Mayur Columbia Univ New York NY 10027 USA Google Res New York NY USA Google New York NY USA

ISBN: (纸本)9781450321747

Aggregator websites typically present documents in the form of representative clusters. In order for users to get a broader perspective, it is important to deliver a diversified set of representative documents in those clusters. One approach to diversification is to maximize the average dissimilarity among documents. Another way to capture diversity is to avoid showing several documents from the same category (e.g. from the same news channel). We combine the above two diversification concepts by modeling the latter approach as a (partition) matroid constraint, and study diversity maximization problems under matroid constraints. We present the first constant-factor approximation algorithm for this problem, using a new technique. Our local search 0:5-approximation algorithm is also the first constant-factor approximation for the max-dispersion problem under matroid constraints. Our combinatorial proof technique for maximizing diversity under matroid constraints uses the existence of a family of Latin squares which may also be of independent interest. In order to apply these diversity maximization algorithms in the context of aggregator websites and as a preprocessing step for our diversity maximization tool, we develop greedy clustering algorithms that maximize weighted coverage of a predefined set of topics. Our algorithms are based on computing a set of cluster centers, where clusters are formed around them. We show the better performance of our algorithms for diversity and coverage maximization by running experiments on real (Twitter) and synthetic data in the context of real-time search over micro-posts. Finally we perform a user study validating our algorithms and diversity metrics.

关键词： Diversity Maximization Approximation algorithms local search algorithms Matroid Constraints Clustering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：