We propose to utilize a neural network to build transition proposal distributions in simulated annealing (SA), which we use for combinatorial optimization on 2D-binary grids and thereby direct convergence towards states of structurally clustered patterns.To accomplish this we introduce a novel class of network architectures called template networks.A template network learns a template to construct a proposal distribution for state transitions of the stochastic process of the Metropolis algorithm, which forms the basis of SA.Each network represents a single constant pattern and is trained on the evaluation results of intermediate states of a single optimization run, resulting in an architecture not requiring an input layer.Using this learning scheme we equip the Metropolis algorithm with the ability to utilize information about past states, intentionally violating the Markov property of memorylessness, and therefore call our method Memory Metropolis (MeMe).Moreover, the emergence of structural clusters is encouraged by incorporating layers with limited local connectivity in the template network, while the network depth controls the learnable cluster sizes.By violating the Markov property and further dropping the consideration of transition properties when evaluating the Metropolis criterion, we deliberately bias the target distribution towards cluster formation.\Viewing the optimization objective of the Metropolis algorithm as a reward maximization links MeMe to deep reinforcement learning, where the policy is constructed from the discrepancy between the template and the current state.This allows to train the template network to find high-reward template-patterns.Detrimental actions (negative rewards) can be directly reverted by evaluating the Metropolis criterion which saves on computationally costly state evaluations.\We apply our algorithm to combinatorial optimization in nanophotonic inverse design and demonstrate that MeMe results in clustered design patterns suitable for direct optical chip fabrication which can not be found by plain SA or regularized SA. Code is available at https://XXXXXXXX.