A quasi-physical algorithm for solving the linear separation problem in n-dimensional space

A quasi-physical algorithm was proposed for solving the linear separation problem of point set in n-dimensional space. The original idea of the quasi-physical algorithm is to find an equivalent physical world for the primitive mathematical problem and to observe the vivid images of the motion of matter in it so as to be inspired to obtain an algorithm for solving the mathematical problem. In this work, the electrostatics with two kinds of matter is found to be the equivalent physical world. As a result, the proposed algorithm is evidently more efficient and robust than the famous LMS algorithm and ETL algorithm. The efficiency of the quasiphysical algorithm is about 10 – 50 times of the LMS algorithm’s for representative instances. A typical Boolean-valued instance shows that it is hard for ETL algorithm but very easy for the quasi-physical algorithm. In this instance, point set A and B is {000, 010, 011, 111} and {001, 100}, respectively. Foundation item: The National Key Basic Research Program (973) (No. G 1998030600) Biography of the author: HUANG Jia-yuan, born in 1979, majoring in intelligent computing.