Spin Glass Automata (SGA): An Evolutionary Local Search Automata for Solving Optimization Problems

Nowadays, new optimization problems become so complicated that popular classic methods are unable to solve them in a reasonable time. By using heuristic and evolutionary algorithms, these problems can be solved more quickly. Cellular Automata (CA) and Spin Glasses (SG) are examples of such algorithms. A CA is a self-organized machine with a simple structure and complicated behavior. Due to local interactions between its cells, it has a high speed; however, it is unable to solve optimization problems. On the other hand, SGs, due to inter-spin magnetic interaction as well as following thermodynamic rules, continually have the tendency toward lower energy, and this way it can solve optimization problems. The interactions between spins are usually limited and consequently, aforementioned methods cannot solve optimization problems with an expected accuracy and this is a great impact. In this paper, with inspiration from behavior of CA and SG, a new machine named Spin Glass Automata (SGA) is introduced which has behavioral dynamic of SG and CA. It has also the ability of parallel processing while it is rapid enough. It follows rules of a CA too. With these properties at hand, the machine can be used in a vast area of optimization problems. Behavioral dynamic tests of the machine include phase transition, entropy and correlation as well as the comparison to other heuristic algorithms such as (GA, TS, SA and NN) shows the ability of this machine in solving practical optimization problems. It has an appropriate execution speed and accuracy. To test full potential of this machine, the NP problem such as optimal portfolio selection has been solved and compared with the five famous stock market of the world