How to order objects to minimize non-adjacency cost
Your problem is just the problem of finding a maximum-weight Hamiltonian path in a weighted graph.

A candidate way of ordering objects in your array corresponds to a Hamiltonian path.  The total weight of that Hamiltonian path (the sum of the weights on the edges in the path) is exactly the sum of the "non-adjacency costs" you don't pay.  Minimizing the sum of the "non-adjacency costs" you do pay is equivalent to maximizing the sum of the "non-adjacency costs" you don't pay.

Unfortunately, this problem is NP-hard, so you should start looking for approximation algorithms or heuristics or special cases.  For instance, there may be some special kinds of graphs (say, bounded treewidth or bounded clique-width) for which this problem might be solvable in polynomial time.

See also https://en.wikipedia.org/wiki/Hamiltonian_path_problem and https://en.wikipedia.org/wiki/Longest_path_problem.

You might also try looking at simulated annealing, which is often a good candidate approach to explore for these kinds of problems, and is in some ways a generalization of the sort of algorithm that you mention in your question.