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

local search algorithms for the Red-Blue Median Problem

ALGORITHMICA 2012年第4期63卷 795-814页

作者： Hajiaghayi, M. Khandekar, R. Kortsarz, G. IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY USA Univ Maryland College Pk MD 20742 USA AT&T Labs Res College Pk MD USA Rutgers State Univ Camden NJ 08102 USA

In this paper, we consider the following red-blue median problem which is a generalization of the well-studied k-median problem. The input consists of a set of red facilities, a set of blue facilities, and a set of clients in a metric space and two integers k (r) ,k (b) a parts per thousand yen0. The problem is to open at most k (r) red facilities and at most k (b) blue facilities and minimize the sum of distances of clients to their respective closest open facilities. We show, somewhat surprisingly, that the following simple local search algorithm yields a constant factor approximation for this problem. Start by opening any k (r) red and k (b) blue facilities. While possible, decrease the cost of the solution by closing a pair of red and blue facilities and opening a pair of red and blue facilities. We also improve the approximation factor for the prize-collecting k-median problem from 4 (Charikar et al. in Proceedings of the ACM-SIAM Symposium on Discrete algorithms, pp. 642-641, 2001) to 3+I mu, which matches the current best approximation factor for the k-median problem.

关键词： Facility location k-median Prize-collecting local search algorithms

来源：评论

学校读者我要写书评

暂无评论

local search algorithms for memetic algorithms: understanding behaviors using biological intelligence 22

Local search algorithms for memetic algorithms: understandin...

引用

22nd International Conference on System Theory, Control and Computing (ICSTCC)

作者： Luca, Beatrice Craus, Mitica Fac Automat Control & Comp Engn Dept Comp Sci Iasi Romania

ISBN: (纸本)9781538644447

Memetic algorithms (MAs) are a class of stochastic global search heuristics in which Evolutionary algorithms (EAs) - based approaches are combined usually with heuristic local searches. This hybridization is meant to reach solutions that would otherwise be unreachable by evolution or a local method alone. In this work, we propose three local search (LS) algorithms for hybridization with an existing Evolutionary Algorithm with Pareto ranking in order to define biological intelligence using the concepts of useful and utility and therefore to zoom on the basin of attraction of promising realistic solutions. Our experimental results with these memetic algorithms in the game of Checkers show how we can learn the organization of behaviors into paths of behaviors of different lengths and frequencies and then reveal the true nature of these behaviors.

关键词： memetic algorithms evolutionary algorithms local search algorithms mechanical and biological intelligence

来源：评论

学校读者我要写书评

暂无评论

Analyzing the complexity of finding good neighborhood functions for local search algorithms

引用

JOURNAL OF GLOBAL OPTIMIZATION 2006年第2期36卷 219-236页

作者： Armstrong, Derek E. Jacobson, Sheldon H. Los Alamos Natl Lab Los Alamos NM 87544 USA Univ Illinois Dept Mech & Ind Engn Urbana IL 61801 USA

A drawback to using local search algorithms to address NP-hard discrete optimization problems is that many neighborhood functions have an exponential number of local optima that are not global optima (termed L-locals). A neighborhood function eta is said to be stable if the number of L-locals is polynomial. A stable neighborhood function ensures that the number of L-locals does not grow too large as the instance size increases and results in improved performance for many local search algorithms. This paper studies the complexity of stable neighborhood functions for NP-hard discrete optimization problems by introducing neighborhood transformations. Neighborhood transformations between discrete optimization problems consist of a transformation of problem instances and a corresponding transformation of solutions that preserves the ordering imposed by the objective function values. In this paper, MAX Weighted Boolean SAT (MWBS), MAX Clause Weighted SAT (MCWS), and Zero-One Integer Programming (ZOIP) are shown to be NPO-complete with respect to neighborhood transformations. Therefore, if MWBS, MCWS, or ZOIP has a stable neighborhood function, then every problem in NPO has a stable neighborhood function. These results demonstrate the difficulty of finding effective neighborhood functions for NP-hard discrete optimization problems.

关键词： computational complexity local search algorithms NP-hard discrete optimization problems

来源：评论

学校读者我要写书评

暂无评论

local++: A C++ framework for local search algorithms

引用

SOFTWARE-PRACTICE & EXPERIENCE 2000年第3期30卷 233-257页

作者： Schaerf, A Cadoli, M Lenzerini, M Univ Udine Dipartimento Ingn Elettr Gest & Meccan I-33100 Udine Italy Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

local search is an emerging paradigm for combinatorial search which has recently been shown to be very effective for a large number of combinatorial problems. It is based on the idea of navigating the search space by iteratively stepping from one solution to one of its neighbors, which are obtained by applying a simple local change to it. In this paper we present local++, an object-oriented framework to be used as a general tool for the development and implementation of local search algorithms in C++, The framework comprises a hierarchy of abstract template classes, one for each local search technique taken into account (i.e. hill-climbing, simulated annealing and tabu search). Each class specifies and implements the invariant part of the algorithm built according to the technique, and is supposed to be specialized by a concrete class once a given search problem is considered, so as to implement the problem-dependent part of the algorithm, local++ comprises also a set of abstract classes for creating new techniques by combining different search techniques and different neighborhood relations, The architecture of local++ provides a principled modularization for the solution of combinatorial search problems, and helps the designer deriving a neat conceptual scheme of the application, thus facilitating the development and debugging phases. local++ proved to be flexible enough for the implementation of the algorithms solving various scheduling problems. Copyright (C) 2000 John Wiley & Sons, Ltd.

关键词： object-oriented frameworks local search algorithms applications

来源：评论

学校读者我要写书评

暂无评论

Learning cooperative linguistic fuzzy rules using fast local search algorithms

Learning cooperative linguistic fuzzy rules using fast local...

引用

2010 IEEE World Congress on Computational Intelligence

作者： delaOssa, Luis Gamez, Jose A. Puerta, Jose M. Univ Castilla La Mancha Dept Comp Syst Albacete 02071 Spain

ISBN: (纸本)9781424469208

The COR methodology allows the learning of Linguistic Fuzzy Rule-Based Systems by considering cooperation among rules. In order to do this, it uses search techniques, such as Genetic algorithms, to find the set of candidate rules which will be used to build the final rule base. The performance of COR algorithms, in terms of the quality of the solutions and cost of the search, decreases as the problem size grows. In this paper, several local search algorithms for learning the rule base are tested, as an alternative to population-based methods. Experiments show that, in most cases, the results for the error of prediction improve upon those obtained with Genetic algorithms. Moreover, this proposal allows a drastic reduction in the computational effort required to find the solutions.

关键词： COR methodology cooperative rules methodology fuzzy set theory genetic algorithms genetic algorithms knowledge based systems linguistic fuzzy rule-based system learning local search algorithms population-based methods search problems search techniques

来源：评论

学校读者我要写书评

暂无评论

local search Proximal algorithms as Decision Dynamics with Costs to Move

引用

SET-VALUED AND VARIATIONAL ANALYSIS 2011年第1期19卷 157-177页

作者： Attouch, H. Soubeyran, A. Univ Montpellier 2 CNRS UMR 5149 I3M F-34095 Montpellier France Univ Mediterranee Chateau Lafarge CNRS GREQAM UMR 6579 F-13290 Les Milles France

Acceptable moves for the "worthwhile-to-move" incremental principle are such that "advantages-to-move" are higher than some fraction of "costs-to-move". When combined with optimization, this principle gives raise to adaptive local search proximal algorithms. Convergence results are given in two distinctive cases, namely low local costs-to-move and high local costs-to-move. In this last case, one obtains a dynamic cognitive approach to Ekeland's I mu-variational principle. Introduction of costs-to-move in the algorithms yields robustness and stability properties.

关键词： Costs-to-move Decision dynamics Exploration process Friction Inertia local optimization local search algorithms Proximal algorithms Worthwhile-to-move incremental process

来源：评论

学校读者我要写书评

暂无评论

Path bridging: A novel local search methodology for optimizing scheduling in highly constrained continuous galvanizing line operations

引用

EXPERT SYSTEMS WITH APPLICATIONS 2025年 276卷

作者： Alvarez-Garcia, Segundo Alvarez-Gil, Nicolas Rosillo, Rafael Univ Oviedo Business Management Dept Edificio Dept Este1 planta Gijon 33204 Asturias Spain ArcelorMittal Global R&D Asturias POB 90 Aviles 33400 Asturias Spain

This study addresses the scheduling optimization of a Continuous Galvanizing Line (CGL) within a steel factory. By conceptualizing coil sequences as paths through nodes in a directed weighted graph, our objective is to identify a minimum-cost Hamiltonian path. The problem is characterized by its asymmetry and constraints, and we analyze it using highly constrained benchmark instances where the current algorithms in use struggle to provide feasible solutions. This research explores the applicability of local search (LS) methods to the CGL scheduling problem. We introduce a novel and efficient LS algorithm, termed Path Bridging (PB), specifically designed to address constraints and asymmetry. It uniquely separates the overall optimization into two distinct phases: feasibility optimization and cost optimization. In a Lin-Kernighan heuristic fashion, the PB algorithm employs a series of 3opt moves strategically designed to avoid infeasibilities. Key features of the PB algorithm include the deliberate design of base 3-opt moves, tabu-list backtracking, and comprehensive checks for chain consolidation. These enhancements render the PB algorithm highly effective in constrained environments. The additional computational effort required by the PB proves to be advantageous: empirical evaluations on challenging benchmark instances demonstrate that the PB outperforms the algorithms in use. We report new best costs in 75% of the tested instances and an average 88% reduction in computation time in comparable scenarios. As part of a rigorous stress test, we reduced the benchmark computation time from 120 s to 1 s, confirming that the PB algorithm consistently identifies feasible solutions across all the test instances.

关键词： Combinational optimization Steel industry Sequencing Metaheuristics local search algorithms Ant colony optimization

来源：评论

学校读者我要写书评

暂无评论

A local search algorithm for ray-convex polyhedron intersection

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2012年第2期51卷 533-550页

作者： Llanas, Bernardo Javier Sainz, Francisco Univ Politecn Madrid ETSI Caminos Dept Matemat Aplicada E-28040 Madrid Spain

In this paper we present a new algorithm (LSABV) for determining the intersection between a ray and a convex polyhedron (RCPI) in a fast way. LSABV is based on local search and the concept of visibility. LSABV requires only the boundary description of the polyhedron and it does not need additional data structures. Numerical experiments show that LSABV is faster than Haines's algorithm in the case of polyhedra with moderate or large number of faces.

关键词： Ray-convex polyhedron intersection local search algorithms Visibility High combinatorial complexity

来源：评论

学校读者我要写书评

暂无评论

Survey and unification of local search techniques in metaheuristics for multi-objective combinatorial optimisation

引用

JOURNAL OF HEURISTICS 2018年第6期24卷 853-877页

作者： Blot, Aymeric Kessaci, Marie-Eleonore Jourdan, Laetitia Univ Lille CNRS CRIStAL Cent LilleCite SciUMR 9189 F-59655 Villeneuve Dascq France

Metaheuristics are algorithms that have proven their efficiency on multi-objective combinatorial optimisation problems. They often use local search techniques, either at their core or as intensification mechanisms, to obtain a well-converged and diversified final result. This paper surveys the use of local search techniques in multi-objective metaheuristics and proposes a general structure to describe and unify their underlying components. This structure can instantiate most of the multi-objective local search techniques and algorithms in literature.

关键词： Multi-objective optimisation Combinatorial optimisation Metaheuristics Unification local search algorithms

来源：评论

学校读者我要写书评

暂无评论

Multiple Scattered local search for Course Scheduling Problem 5

Multiple Scattered Local Search for Course Scheduling Proble...

引用

International Conference on Soft Computing, Intelligent System and Information Technology (ICSIIT)

作者： Jamal, Ade Al Azhar Univ Indonesia Dept Informat Jakarta Indonesia

ISBN: (纸本)9780769561639

Course scheduling problem is a nondeterministic polynomial time-complete problem which is hard to solve. One of the popular method for solving the problem is the so-called local search algorithm family, which is basically search a better solution in the neighborhood of previously known potential solution iteratively. local search technique has a weakness that it gets stuck easily in a local optimum or on a plateau. Various efforts have been done in many literatures to circumvent this weakness. Current work investigates an already improved scattered local search by augmenting randomly generated initial population of schedules in the local search algorithm. This algorithm will be compared to an originally population based genetic algorithm which is enhanced by letting local search technique on each individual schedule in every generation. The result has shown that the population based local search performs better than the hybrid genetic algorithm.

关键词： course scheduling optimization local search algorithms genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：