Maximal Equation Satisfying Problem Solving in F2 Field by Velocity Perturbed Particle Swarm Algorithm
Zhao Xinchao · 2009
Consider the problem MAX-SATISFY over F2, that is, given a system of m linear equations with n variables over F2, find a solution satisfying the maximal number of equations. An improved particle swarm optimization (PSO) method is proposed for computing maximal satisfying solution of a polynomial equation system with equation number being far larger than variable number in a finite field. As far as we know, it's the first time to adopt the heuristic intelligent algorithm (PSO) to solve such discrete equations in finite field. It's obvious that there are no solutions satisfying all the equations. So our goal is to find a solution which satisfies as many equations as possible. Four randomly generated Boolean equations are solved with sizes F2100×20, F2300×50, F2500×100and F21000×200. Empirical results show that algorithm has a robust performance and strong exploration and exploitation abilities.