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

A genetic algorithm based framework for local search algorithms for distributed constraint optimization problems

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2020年第2期34卷 41-41页

作者： Chen, Ziyu Liu, Lizhen He, Jingyuan Yu, Zhepeng Chongqing Univ Coll Comp Sci Chongqing Peoples R China

local search algorithms are widely applied in solving large-scale Distributed constraint optimization problems (DCOPs) where each agent holds a value assignment to its variable and iteratively makes a decision on whether to replace its assignment according to its neighbor states. However, the value assignments of their neighbors confine their search to a small space so that agents in local search algorithms easily fall into local optima. Fortunately, Genetic algorithms (GAs) can direct a search process to a more promising space and help the search process to break up the confine of local states. Accordingly, we propose a GA-based framework (LSGA) to enhance local search algorithms, where a series of genetic operators are redesigned for agents in distributed scenario to accommodate DCOPs. First, a fitness function is designed to evaluate the assignments for each agent, considering the balance of local benefits and global benefits. Then, a new method is provided to decide crossover positions in terms of agent-communication and topological structure of DCOPs. Besides, a self-adaptive crossover probability and a self-adaptive mutation probability are proposed to control the uses of crossover operator and mutation operator, respectively. And more importantly, the LSGA framework can be easily applied in any local search algorithm. The experimental results demonstrate the superiority of the use of LSGA in the typical search algorithms over state-of-the-art incomplete algorithms.

关键词： Multi-agent system Distributed constraint optimization problem Incomplete algorithm Genetic algorithm local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Multi-objective Aggregate Production Planning for Multiple Products: A local search-Based Genetic algorithm Optimization Approach

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS 2021年第1期14卷 1页

作者： Liu, Lan-Fen Yang, Xin-Feng Lanzhou Jiaotong Univ Sch Traff & Transportat Engn Lanzhou Gansu Peoples R China

The diversity of products and fierce competition make the stability and production cost of manufacturing industry more important. So, the purpose of this paper is to deal with the multi-product aggregate production planning (APP) problem considering stability in the workforce and total production costs, and propose an efficient algorithm. Taking into account the relationship of raw materials, inventory cost and product demand, a multi-objective programming model for multi-product APP problem is established to minimize total production costs and instability in the work force. To improve the efficiency of the algorithm, the feasible region of the planned production and the number of workers in each period are determined and a local search algorithm is used to improve the search ability. Based on the analysis of the feasible range, a genetic algorithm is designed to solve the model combined with the local search algorithm. For analyzing the effect of this algorithm, the information entropy strategy, NSGA-II strategy and multi-population strategy are compared and analyzed with examples, and the simulation results show that the model is feasible, and the NSGA-II algorithm based on the local search has a better performance in the multi-objective APP problem.

关键词： Aggregate production planning Multi-product Stabilities in the work force Multi-objective Genetic algorithm local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Replicating the performance of a portfolio of stocks using minimum dominating set

引用

EXPERT SYSTEMS WITH APPLICATIONS 2025年 263卷

作者： Biswas, Subhojit Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA

Analyzing a portfolio with many assets (stocks) is mathematically challenging. This article considers a large portfolio within a graph theory framework to obtain a tracking portfolio of the actual network. Each asset forms a vertex (node), and the correlation between assets forms the weight of the edges in the graphical network. The large graphical network is efficiently managed using Minimum Dominating Sets (MDS). Finding the MDS of a given portfolio is a well-known NP-hard problem in graph theory. An integer linear programming formulation of MDS is used, and the optimal solution is found using a Gurobi solver. Additionally, greedy and local search algorithms are developed to find the MDS, reducing computation time for extensive portfolios without significantly compromising solution quality. The MDS obtained by the solver and the algorithms are directly compared with an alternative portfolio selection strategy of randomly sub-sampling a certain percentage of the actual portfolio based on size. The expected return of the tracking portfolio is compared to the actual portfolio's expected return graphically, and a statistical significance t-test is performed to confirm the validity of the MDS, . Further, a sensitivity analysis of the expected return of the tracking portfolio obtained from the algorithms is conducted for three different threshold values of the pairwise correlation between assets. Computational results are performed on eight independent instances, with the universe of stocks varying throughout the computation.

关键词： Minimum dominating set local search algorithm Stock selection Greedy algorithm Gurobi solver

来源：评论

学校读者我要写书评

暂无评论

A Partial Decision Scheme for local search algorithms for Distributed Constraint Optimization Problems 16

A Partial Decision Scheme for Local Search Algorithms for Di...

引用

16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

作者： Yu, Zhepeng Chen, Ziyu He, Jingyuan Deng, Yancheng Chongqing Univ Coll Comp Sci Chongqing Peoples R China

ISBN: (纸本)9781510855076

local search algorithms are widely adopted in solving large-scale Distributed Constraint Optimization Problems (DCOPs). However, since each agent always makes its value decision based on the values of its neighbors in local search, those algorithms usually suffer from local premature convergence. More concretely, an agent cannot make a wise decision with poor values of its neighbors since its decision space is bound up with those poor values. In this paper, we propose a Partial Decision Scheme (PDS) to relax the decision space of an agent by ignoring the value of its neighbor which has the bad impact on its local benefits. The PDS comprises two partial decision processes: trigger partial decision and recursive partial decision. The former is iteratively performed by agents who cannot enhance their local benefits unilaterally to break out of potential local optima. The latter is recursively performed by neglected agents to improve global benefits. Besides, the trigger conditions along with a self-adaptive probability are introduced to control the use of PDS. The PDS can be easily applied to any local search algorithm to overcome its local premature convergence with a small additional overhead. In our theoretical analysis, we prove the feasibility and convergence of PDS. Moreover, the experimental results also demonstrate the superiority of the use of PDS in the typical local search algorithms over state-of-the-art local search algorithms.

关键词： Multi-agent System Distributed Constraint Optimization Problem Incomplete algorithm local search algorithm Partial Decision

来源：评论

学校读者我要写书评

暂无评论

Evolutionary deployment and local search-based movements of 0th responders in disaster scenarios

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2018年 88卷 61-78页

作者： Reina, D. G. Camp, T. Munjal, A. Toral, S. L. Engn Dept Campus Palmas AltasEdificio E Seville 41014 Spain Colorado Sch Mines Div Comp Sci 1500 Illinois St Golden CO 80401 USA CableLabs Louisville CO USA Univ Seville Elect Engn Dept Camino Descubrimientos S-N Seville 41092 Spain

establishment of communications in disaster scenarios is of paramount importance, especially because preexisting communication infrastructure is likely to be destroyed or malfunctioning. Consequently, there is a need for an alternative and self-organizing communication infrastructure that can be rapidly deployed in disaster situations. In this paper, we propose to use drones or unmanned aerial vehicles as 0th responders to form a network that provides communication services to victims. Finding the best positions of the 0th responders is a non-trivial problem and is, therefore, divided into two phases. The first phase is the initial deployment, where the 0th responders are placed using partial information on the disaster scenario. In the second phase, which we call the adaptation to real conditions, the drones move according to a local search algorithm to find positions that provide better coverage to the victims. We conduct extensive simulations to validate our proposed approach for rural disaster scenarios under different conditions. We show that our proposed initial deployment based on genetic algorithm provides coverage for up to 94% (maximum) and 86% (mean) of victims if complete knowledge of the disaster scenario is known and 10 drones are used. When the adaptation to the real condition phase is used, this percentage is increased to 95% (maximum). If no knowledge of the scenario and 10 UAVs are used 80% (maximum) and 59% (mean) of victims are found and successfully covered. The proposed approach outperforms in 6.4% the random deployment method, and in 2.4% the best grid deployment approach. Finally, we show that by using different numbers of drones for the two phases of the proposed approach, the percentage of victims is increased up to 51% for low values of knowledge of the scenario. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Disaster scenarios Communications Evolutionary algorithm local search algorithm 0th responders

来源：评论

学校读者我要写书评

暂无评论

An Hybrid local search for the Direct Aperture Optimisation Problem

引用

IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE 2024年第1期8卷 95-109页

作者： Moyano, Mauricio Cabrera-Guerrero, Guillermo Tello-Valenzuela, Gonzalo Lagos, Carolina Pontificia Univ Catolica Valparaiso Escuela Ingn Informat Valparaiso 2950 Chile

Radiotherapy is a cancer treatment that uses high levels of radiation to destroy cancerous cells and shrink tumours while minimising harm to surrounding organs at risk (OARs). One of the techniques used in radiotherapy is Intensity Modulated Radiation Therapy (IMRT). Usually, the IMRT problem is approached sequentially, that is, we first need to determine the set of beam angles from which radiation will be delivered. Then, the radiation intensities for each selected beam angle are computed. Finally, the sequence of aperture shapes needed to deliver the computed treatment plan is generated. Unfortunately, the treatment plans generated by this approach have many apertures, which leads to longer treatment times. In contrast, the Direct Aperture Optimisation (DAO) problem considers constraints associated with the number of deliverable aperture shapes and physical constraints of the machine during the optimisation process of the intensities. The DAO approach generates, in general, better treatments with fewer apertures for IMRT. This is important because fewer apertures usually means shorter delivery times. In this work, we propose an hybrid local search strategy with mathematical programming to efficiently solve the DAO problem. We apply our proposed local search algorithm to a set of prostate cases, obtaining very competitive results.

关键词： Apertures Shape Optimization search problems Tumors Radiation therapy Stochastic processes Direct aperture optimisation intensity modulated radiation therapy local search algorithm

来源：评论

学校读者我要写书评

暂无评论

A Partial Decision Scheme for local search algorithms for Distributed Constraint Optimization Problems 17

A Partial Decision Scheme for Local Search Algorithms for Di...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Zhepeng Yu Ziyu Chen Jingyuan He Yancheng Deng College of Computer Science Chongqing University

ISBN: (纸本)9781510855076

local search algorithms are widely adopted in solving large-scale Distributed Constraint Optimization Problems (DCOPs) However, since each agent always makes its value decision based on the values of its neighbors in local search, those algorithms usually suffer from local premature convergence More concretely, an agent cannot make a wise decision with poor values of its neighbors since its decision space is bound up with those poor values In this paper, we propose a Partial Decision Scheme (PDS) to relax the decision space of an agent by ignoring the value of its neighbor which has the bad impact on its local benefits. The PDS comprises two partial decision processes trigger partial decision and recursive partial decision The former is iteratively performed by agents who cannot enhance their local benefits unilaterally to break out of potential local optima. The latter is recursively performed by neglected agents to improve global benefits Besides, the trigger conditions along with a self-adaptive probability are introduced to control the use of PDS The PDS can be easily applied to any local search algorithm to overcome its local premature convergence with a small additional overhead In our theoretical analysis, we prove the feasibility and convergence of PDS Moreover, the experimental results also demonstrate the superiority of the use of PDS in the typical local search algorithms over state-of-the-art local search algorithms.

关键词： Multi-agent System Distributed Constraint Optimization Problem Incomplete algorithm local search algorithm Partial Decision searchING algorithm Multi-agent systems pendrin Planetary Data System Constrained optimization Agents Neighbor bouse Partial

来源：评论

学校读者我要写书评

暂无评论

Towards a distributed local-search approach for partitioning large-scale social networks

引用

INFORMATION SCIENCES 2020年 508卷 200-213页

作者： Zheng, Bin Liu, Ouyang Li, Jing Lin, Yong Chang, Chong Li, Bo Chen, Tefeng Peng, Hao State Grid Zhejiang Elect Power Co Beijing Zhejiang Peoples R China State Grid Jiaxing Elect Power Supply Co Jiaxing Peoples R China State Grid Taizhou Elect Power Supply Co Taizhou Peoples R China State Grid Shaoxing Elect Power Supply Co Shaoxing Peoples R China Beihang Univ Sch Comp Sci & Engn Beijing 100191 Peoples R China

Large-scale social graph data poses significant challenges for social analytic tools to monitor and analyze social networks. A feasible solution is to parallelize the computation and leverage distributed graph computing frameworks to process such big data. However, it is nontrivial to partition social graphs into multiple parts so that they can be computed on distributed platforms. In this paper, we propose a distributed local search algorithm, named dLS, which enables quality and efficient partition of large-scale social graphs. With the vertex-centric computing model, dLS can achieve massive parallelism. We employ a distributed graph coloring strategy to differentiate neighbor nodes and avoid interference during the parallel execution of each vertex. We convert the original graph into a small graph, Quotient Network, and obtain local search solution from processing the Quotient Network, thus further improving the partition quality and efficiency of dLS. We have evaluated the performance of dLS experimentally using real-life and synthetic social graphs, and the results show that dLS outperforms two state-of-the-art algorithms in terms of partition quality and efficiency. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Graph partitioning Social network local search algorithm

来源：评论

学校读者我要写书评

暂无评论

Stable Resolving - A Randomized local search Heuristic for MaxSAT 43rd

Stable Resolving - A Randomized Local Search Heuristic for M...

引用

43rd German Conference on Artificial Intelligence (KI)

作者： Reisch, Julian Grossmann, Peter Kliewer, Natalia Synopt GmbH Chemnitzer Str 48b D-01187 Dresden Germany Free Univ Berlin Garystr 21 D-14195 Berlin Germany

ISBN: (纸本)9783030582845;9783030582852

Many problems from industrial applications and AI can be encoded as Maximum Satisfiability (MaxSAT). Often, it is more desirable to produce practicable results in very short time compared to optimal solutions after an arbitrary long computation time. In this paper, we propose Stable Resolving (SR), a novel randomized local search heuristic for MaxSAT with that aim. SR works for both weighted and unweighted instances. Starting from a feasible initial solution, the algorithm repeatedly performs the three steps of perturbation, improvements and solution checking. In the perturbation, the search space is explored at the cost of possibly worsening the current solution. The local improvements work by repeatedly flipping signs of variables in over-satisfied clauses. Finally, the algorithm performs a solution checking in a simulated annealing fashion. We compare our approach to state-of-the-art MaxSAT solvers and show by numerical experiments on benchmark instances from the annual MaxSAT competition that SR performs comparable on average and is even the best solver for particular problem instances.

关键词： Maximum Satisfiability MaxSAT Incomplete solving Randomized algorithm local search algorithm Simulated annealing

来源：评论

学校读者我要写书评

暂无评论

Common Object Discovery as local search for Maximum Weight Cliques in a Global Object Similarity Graph 1

引用

21st IAPR International Conference on Discrete Geometry for Computer Imagery (DGCI)

作者： Rao, Cong Fan, Yi Su, Kaile Latecki, Longin Jan Temple Univ Philadelphia PA 19122 USA Guilin Univ Elect Technol Guangxi Key Lab Trusted Software Guilin 541004 Peoples R China Griffith Univ Brisbane Qld Australia

ISBN: (数字)9783030140854

ISBN: (纸本)9783030140854;9783030140847

In this paper, we consider the task of discovering the common objects in images. Initially, object candidates are generated in each image and an undirected weighted graph is constructed over all the candidates. Each candidate serves as a node in the graph while the weight of the edge describes the similarity between the corresponding pair of candidates. The problem is then expressed as a search for the Maximum Weight Clique (MWC) in this graph. The MWC corresponds to a set of object candidates sharing maximal mutual similarity, and each node in the MWC represents a discovered common object across the images. Since the problem of finding the MWC is NP-hard, most research of the MWC problem focuses on developing various heuristics for finding good cliques within a reasonable time limit. We utilize a recently very popular class of heuristics called local search methods. They search for the MWC directly in the discrete domain of the solution space. The proposed approach is evaluated on the PASCAL VOC image dataset and the YouTube-Objects video dataset, and it demonstrates superior performance over recent state-of-the-art approaches.

关键词： Common Object Discovery Visual Similarity Maximum Weight Clique local search algorithm

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：