The Boolean Satisfiability(SAT) problem is the key problem in computer theory and ***-programmable gate array(FPGA) has been addressed frequently to accelerate the SAT solving process in the last few years owing to it...
详细信息
The Boolean Satisfiability(SAT) problem is the key problem in computer theory and ***-programmable gate array(FPGA) has been addressed frequently to accelerate the SAT solving process in the last few years owing to its parallelism and *** have proposed a novel SAT solver based on an improved local search algorithm on the reconfigurable hardware platform. The new software preprocessing procedure and hardware architecture are involved to solve large-scale SAT problems instances. As compared with the past solvers, the proposed solver has the following advantages: the preprocessing technology can strongly improve the efficiency of solver; the strategy of strengthening the variable selection can avoid the same variable flipped continuously and repeatedly. It reduces the possibility of search falling into local minima. The experimental results indicate that the solver can solve problems of up to 32 K variables/128 K clauses without off-chip memory banks, and has better performance than previous works.
As an important technique to solve distributed constraint optimization problems, Max-sum has drawn a lot of attention and successfully been deployed in real applications. Unfortunately, Max-sum fails to converge in cy...
详细信息
As an important technique to solve distributed constraint optimization problems, Max-sum has drawn a lot of attention and successfully been deployed in real applications. Unfortunately, Max-sum fails to converge in cyclic problems and usually traverses states with low quality. Max-sum_AD and Max-sum_ADVP were proposed to guarantee the single phase convergence and the cross phase convergence respectively, and greatly improve the solution quality of Max-sum. However, the solution quality is closely related to the timing for starting value propagation in Max-sum_ADVP. In other words, low-quality initial assignments will lead to a poor result. In this paper, we prove that value propagation could restrict the exploration ability brought by Max-sum and eventually makes Max-sum_ADVP equivalent to a sequential greedy local search algorithm. For getting a balance between exploration and exploitation, several non-consecutive value propagation strategies are proposed to relax the restriction caused by value propagation: single-side value propagation which executes value propagation and Max-sum_AD in an interleaved way, probabilistic value propagation which performs value propagation stochastically and hybrid belief/value propagation where agents perform Max-sum_AD and value propagation in one round. We illustrate that agents in our algorithms can make decisions beyond local functions. Our empirical evaluations demonstrate the superiority of our methods over Max-sum and its variants. It also can be found that our methods are independent of the value propagation timing which is a major concern in Max-sum_ADVP.
Max-sum ADVP is a message-passing algorithm for solving Distributed Constraint Optimization Problems (DCOPs) able to obtain a convergent solution in a cyclic factor graph. Nevertheless, the solution quality is closely...
详细信息
ISBN:
(纸本)9781510855076
Max-sum ADVP is a message-passing algorithm for solving Distributed Constraint Optimization Problems (DCOPs) able to obtain a convergent solution in a cyclic factor graph. Nevertheless, the solution quality is closely related to the timing for starting value propagation in Max-sum ADVP. In other words, low-quality initial assignments will lead to a poor result. In this paper, we illustrate that value propagation can eliminate the inconsistent contexts in Max-sum AD and break ties among utilities, but it also restricts the exploration brought by Max-sum. For balancing between the exploration and the accuracy, we propose a new iterative refined Max-sum AD algorithm with single-side value propagation, called Max-sum ADSSVP. It performs two phases in every two convergences, one phase which enables the exploration to find high-quality initial assignments and the other phase which enables value propagation to guarantee solution quality. Max-sum ADSSVP tackles the timing selection problem by iteratively refining initial assignments in every exploration phase. Besides, local search is introduced after the value propagation phase to speed up the convergence process. Our empirical evaluation indicates that our methods are independent of initial assignments and less likely to get stuck in local optima.
As the first NP-complete problem, the Boolean satisfiability (SAT) problem is the key problem in computer theory and application. FPGA has been address frequently to accelerate the SAT solving process in the last few ...
详细信息
ISBN:
(纸本)9781509047550
As the first NP-complete problem, the Boolean satisfiability (SAT) problem is the key problem in computer theory and application. FPGA has been address frequently to accelerate the SAT solving process in the last few years, owing to its parallelism and flexibility. In this paper, we have proposed a novel SAT solver adopting an improved local search algorithm on the reconfigurable hardware platform. The new software preprocessing procedure and hardware architecture are involving to solve large-scale SAT problem instances. As compared with the past solver, the solver has the following advantages:(1) the preprocessing technology can strongly improve the efficiency of solver;(2) the strategy of strengthening the variable selection can avoid the same variable flipped continuously and repeatedly. It reduces the possibility of searching into local optimum. The experiments have shown that our solver has better performance than previous works.
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...
详细信息
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.
Local search algorithms are widely applied in solving large-scale distributed constraint optimization problem (DCOP). Distributed stochastic algorithm (DSA) is a typical local search algorithm to solve DCOP. However, ...
详细信息
Local search algorithms are widely applied in solving large-scale distributed constraint optimization problem (DCOP). Distributed stochastic algorithm (DSA) is a typical local search algorithm to solve DCOP. However, DSA has some drawbacks including easily falling into local optima and the unfairness of assignment choice. This paper presents a novel local search algorithm named VLSs to solve the issues. In VLSs, sampling according to the probability corresponding to assignment is introduced to enable each agent to choose other promising values. Besides, each agent alternately performs a greedy choice among multiple parallel solutions to reduce the chance of falling into local optima and a variance adjustment mechanism to guide the search into a relatively good initial solution in a periodic manner. We give the proof of variance adjustment mechanism rationality and theoretical explanation of impact of greed among multiple parallel solutions. The experimental results show the superiority of VLSs over state-of-the-art DCOP algorithms.
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 whet...
详细信息
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.
Max-sum_ADVP is a message-passing algorithm for solving Distributed Constraint Optimization Problems (DCOPs) able to obtain a convergent solution in a cyclic factor graph. Nevertheless, the solution quality is closely...
详细信息
ISBN:
(纸本)9781510855076
Max-sum_ADVP is a message-passing algorithm for solving Distributed Constraint Optimization Problems (DCOPs) able to obtain a convergent solution in a cyclic factor graph. Nevertheless, the solution quality is closely related to the timing for starting value propagation in Max-sum_ADVP. In other words, low-quality initial assignments will lead to a poor result. In this paper, we illustrate that value propagation can eliminate the inconsistent contexts in Max-sum_AD and break ties among utilities, but it also restricts the exploration brought by Max-sum. For balancing between the exploration and the accuracy, we propose a new iterative refined Max-sum_AD algorithm with single-side value propagation, called Max-sum_ADSSVP. It performs two phases in every two convergences, one phase which enables the exploration to find high-quality initial assignments and the other phase which enables value propagation to guarantee solution quality Max-sum_ADSSVP tackles the timing selection problem by iteratively refining initial assignments in every exploration phase. Besides, local search is introduced after the value propagation phase to speed up the convergence process. Our empirical evaluation indicates that our methods are independent of initial assignments and less likely to get stuck in local optima.
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 ...
详细信息
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.
暂无评论