# Renormalization for Discrete Optimization

## Discussion —

For both the traveling salesman and the spin glass problems, our genetic renormalization algorithm finds solutions whose quality is far better than those found by local search. In a more general context, our approach may be considered as a systematic way to improve upon state of the art local searches. A key to this good performance is the treatment of multiple scales by renormalization and recursion. The use of a population of configurations then allows us to self-consistently optimize the problem on all scales. Just as in divide and conquer strategies, combinatorial complexity is handled by considering a hierarchy of problems. But contrary to those strategies, information in our system flows both from small scales to large scales and back. Clearly such a flow is necessary as a choice or selection of a pattern at small scales may be validated only at much larger scales.

In this work, we put such principles together in a simple manner; nevertheless, the genetic renormalization algorithm we obtained compared very well with the state of the art heuristics specially developed for the problems investigated. Improvements in the population dynamics and in the local search can make our approach even more powerful. We thus expect genetic renormalization algorithms to become widely used in the near future, both in fundamental  and applied research.

###### Acknowledgements.

We are grateful to O. Bohigas for his comments and to J. Mitchell for providing the spin glass exact solutions. O. C. M. acknowledges support from the Institut Universitaire de France. J. H. acknowledges support from the M.E.N.E.S.R.