检索结果-南通市图书馆

Experimental analyses on phase transitions in compiling satisfiability problems

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2015年第3期58卷 80-90页

作者： GAO Jian WANG JiaNan yin minghao College of Information Science and Technology Dalian Maritime University College of Computer Science Northeast Normal University

In the past decade,a kind of well-known phenomena in many complex combinatorial problems such as satisfiability problem,called phase transition,have been widely *** this paper,the phase transition phenomena are investigated during compiling k-satisfiability problems into tractable languages with empirical *** binary decision diagram and deterministic-decomposable negation normal form are selected as the tractable target languages for the *** intensive experiments,it can be concluded that an easy–hard–easy pattern exists during the compilations,which is only related to the ratio of the number of clauses to that of variables if we set k to a fixed value,rather than to the target ***,it can be concluded that the space exhausted during the compilations grows exponentially with the number of variables growing,whereas there is also a phase transition separating the polynomial-increment region from the exponential-increment ***,it can be observed that there is a phase transition of prime implicants around peak points of the easy–hard–easy pattern and the ratios of random instances whose average lengths of prime implicants are larger than the threshold 0.5 change *** these analyses,it can be concluded that prime implicant length and solution interchangeability are crucial impacts on sizes of compilation results.

关键词： phase transition knowledge compilation random k-SAT prime implicants easy–hard–easy pattern

A randomized diversification strategy for solving satisfiability problem with long clauses

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2017年第9期60卷 121-131页

作者： Jian GAO Ruizhi LI minghao yin College of Computer Science Northeast Normal University College of Information Science and Technology Dalian Maritime University Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education Jilin University

Satisfiability problem(SAT) is a central problem in artificial intelligence due to its computational complexity and usefulness in industrial applications. Stochastic local search(SLS) algorithms are powerful to solve hard instances of satisfiability problems, among which CScore SAT is proposed for solving SAT instances with long clauses by using greedy mode and diversification mode. In this paper, we present a randomized variable selection strategy to improve efficiency of the diversification mode, and thus propose a new SLS *** perform a number of experiments to evaluate the new algorithm comparing with the recently proposed algorithms, and show that our algorithm is comparative with others for solving random instances near the phase transition threshold.

关键词： SAT local search randomized diversification strategy phase transition long clause

A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2017年第6期60卷 145-158页

作者： Yiyuan WANG Dantong OUYANG Liming ZHANG minghao yin Symbol Computation and Knowledge Engineer of Ministry of Education Jilin University College of Computer Science and Technology Jilin University School of Computer Science and Information Technology Northeast Normal University

The unicost version of well-known set covering problem(SCP) is central to a wide variety of practical applications for which finding an optimal solution quickly is crucial. In this paper, we propose a new local searchbased algorithm for the unicost SCP which follows the general framework of the popular stochastic local search with a particular focus on the hyperedge selection strategy and weight diversity strategy. Specifically, a strategy as called hyperedge configuration checking strategy is proposed here to avoid the search trajectory which leads to local optima. Additionally, a new weight diversity strategy is proposed for the diversification of search results,by changing the weight of both covered and uncovered vertices in the current solution. The experimental results show that our algorithm significantly outperforms the state-of-the-art heuristic algorithm by one to two orders of magnitudes on the 85 classical instances. Also, our algorithm improves the current optimal solutions of11 instances.

关键词： unicost set covering problem hyperedge configuration checking local search weight diversity strategy hyperedge selection strategy

Solving multi-objective constrained minimum weighted bipartite assignment problem: a case study on energy-aware radio broadcast scheduling

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2022年第8期65卷 23-38页

作者： Yupeng ZHOU Mingjie FAN Feifei MA minghao yin College of Information Science and Technology Northeast Normal University Laboratory of Parallel Software and Computational Science Institute of Software Chinese Academy of Sciences State Key laboratory of Computer Science Institute of Software Chinese Academy of Sciences

This paper proposes a multi-objective constrained minimum weighted bipartite assignment problem(MCMWBAP), which is considered an extension of the classical bipartite matching problem(BMP). We first provide the formulation of the MCMWBAP and prove that it is an NP-hard combinatorial optimization problem. Based on this formulation, multi-objective energy-aware shortwave radio broadcast resource allocation problem(MSRBRAP) application is studied. The goal of this problem is to allocate radio programs to transmission devices to broadcast all radio programs felicitously with a maximized objective of total qualified monitoring sites and a minimized objective of energy consumption. Then, a novel multi-objective hybrid evolutionary algorithm(MOHEA), which is integrated with push and pull initialization, the dynamic resource allocation strategy, and the aggregate local search procedure, is developed to solve the *** proposed method is evaluated using two categories of benchmarks for MCMWBAP together with a real scenario case study for MSRBRAP. Furthermore, the key components of MOHEA are analyzed, and the experimental results demonstrate that MOHEA outperforms two classical multi-objective evolutionary algorithms(NSGA-II and MOEA/D), improving working efficiency.

关键词： constrained minimum weighted bipartite assignment multi-objective energy-aware radio broadcast scheduling evolutionary algorithms dynamic resource allocation aggregate local search

An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Frontiers of Computer Science 2023年第4期17卷 1-14页

作者： Shiwei PAN Yiming MA Yiyuan WANG Zhiguo ZHOU Jinchao JI minghao yin Shuli HU School of Computer Science and Information Technology Northeast Normal UniversityChangchun 130117China Key Laboratory of Applied Statistics of MOE Northeast Normal UniversityChangchun 130117China

The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other *** this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called *** proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution *** is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of *** show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world *** results show that the MAE-PB algorithm achieves high *** particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 *** investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.

关键词： evolutionary algorithm combinatorial optimization minimum independent dominating set local search master apprentice path breaking

JLU-RLAO和JLU-QLAO:两个不确定智能规划求解系统

在线全文

学校读者我要写书评

暂无评论

计算机研究与发展 2009年第4期46卷 667-675页

作者：孙吉贵殷明浩吕帅吉林大学计算机科学与技术学院长春130012 吉林大学教育部符号计算与知识工程重点实验室长春130012 东北师范大学计算机学院长春130117

不确定环境下的智能规划问题往往假设世界状态的转移概率是确切可知的,然而规划建模专家有时只能在信息不完备的条件下进行建模,从而只能通过猜测或者不完全统计的方法来获取不完备的有关状态转移不确定性的定量信息,有时甚至只能获取... 详细信息

不确定环境下的智能规划问题往往假设世界状态的转移概率是确切可知的,然而规划建模专家有时只能在信息不完备的条件下进行建模,从而只能通过猜测或者不完全统计的方法来获取不完备的有关状态转移不确定性的定量信息,有时甚至只能获取相关的定性信息.在2004年概率规划比赛冠军LAO系统的基础上设计了JLU-RLAO系统和JLU-QLAO系统.它们可以在无法获得精确的状态转移概率条件下,依然保证规划求解的健壮性.实验结果表明,JLU-RLAO系统和JLU-QLAO系统可以快速高效地解决上述不确定智能规划问题.

关键词：智能规划不确定规划最坏模型最好模型定性决策

在线全文

学校读者我要写书评

暂无评论

不可满足子式研究

智能系统学报 2013年第6期8卷 497-504页

作者：殷明浩李欣东北师范大学计算机科学与信息技术学院吉林长春130117

为了广泛有效地将不可满足子式应用于知识验证、产品规划、硬件和软件的设计与验证等领域,对不可满足子式进行了相关研究.对当前不可满足子式的主要相关算法进行了概述评论、分类归纳,并从计算复杂性角度介绍了其子类、参数复杂性以及QB... 详细信息

为了广泛有效地将不可满足子式应用于知识验证、产品规划、硬件和软件的设计与验证等领域,对不可满足子式进行了相关研究.对当前不可满足子式的主要相关算法进行了概述评论、分类归纳,并从计算复杂性角度介绍了其子类、参数复杂性以及QBF中的极小不可满足子式.总结了近10年来不可满足子式的理论与算法,讨论了不可满足子式的未来研究发展方向.研究有利于进一步发现不可满足的根本原因,从而进行有针对性地改进,并对相关人员的研究提供帮助.

关键词：可满足性问题不可满足子式可满足模理论局部搜索

在线全文

学校读者我要写书评

暂无评论

智能规划识别及其应用的研究

计算机工程 2005年第15期31卷 169-171页

作者：刘日仙谷文祥殷明浩东北师范大学计算机系长春130024

智能规划识别已经被广泛地用于自然语言理解、知识推理、情景演算等计算机系统的许多方面。文章介绍了国内外学者的相关研究,包括规划识别研究的历史与现状、问题与展望。并介绍了规划识别的各种方法及规划识别的应用。

关键词：人工智能规划识别智能规划

在线全文

学校读者我要写书评

暂无评论

最坏情况下X_2SAT问题的上界

计算机研究与发展 2014年第3期51卷 598-605页

作者：周俊萍姜蕴晖殷明浩东北师范大学计算机科学与信息技术学院长春130117

最坏情况下XSAT问题上界的研究已成为一个热门的研究领域.针对XSAT的泛化问题X2SAT提出了算法X2SAT-N,该算法首先利用简化算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.证明了该算法可以将X2SAT问题的时... 详细信息

最坏情况下XSAT问题上界的研究已成为一个热门的研究领域.针对XSAT的泛化问题X2SAT提出了算法X2SAT-N,该算法首先利用简化算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.证明了该算法可以将X2SAT问题的时间复杂度由目前最好的O(1.451 1n)提高到O(1.420 3n),其中n为X2SAT公式中变量的数目.X2SAT问题实例的大小不仅依赖于变量的数目还依赖于公式的长度,时间复杂性是根据问题实例的大小所组成的函数计算所得.因此又提出了算法X2SAT-L,并从公式长度的角度证明了X2SAT问题在O(1.364 3l)时间上界内可解.

关键词：最坏情况上界复杂性分析分支树