Maximal Equation Satisfying Problem Solving in F2 Field by Velocity Perturbed Particle Swarm Algorithm

Consider the problem MAX-SATISFY over F₂, that is, given a system of m linear equations with n variables over F₂, 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 F₂ ^100×20, F₂ ^300×50, F₂ ^500×100 and F₂ ^1000×200. Empirical results show that algorithm has a robust performance and strong exploration and exploitation abilities.