use global optimizer to solve sorting problem

I have an optimization task that involves choosing the ordering of some magnets. A solution is a list of N integers taken from a larger set of N+S integers where S=# of spares. Each number in the list occurs once and must be unique. For example, if N=3, S=0, then the possible choices are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2] and [3,2,1]. For each choice there is a complex objective that depends on the ordering. For example, one part of the objective is to calculate a sum of sums then do a linear regression and calculate deviations from the line while imposing a constraint on the slope and offset. LIkewise, constraints are also complex, non-linear functions.

The actual problem involves about 200 magnets with 200 factorial combinations. The "optimum" will be one that is "good enough". Algorithms I have used in the past with other programming languages and environments are simulated annealing and genetic algorithm.

How would I set up this kind of permutation/combinatoric optimization in MatLab?

[Mathieu NOE]

hello

when you say 200 magnets , do you mean 200 possible locations are available for magnets , but you test (N< 200 magnets) for N+S = 200 locations ? that does not make 200 combinations

anyway , there are either "brute force " approaches like random search (create randow integer test vectors) or test all combinations (the vectors can be generated using MakeComb.m function.

Otherwise, but I have not yet practices it, there are optimization methods for integer / combination problems :

• Binary Dragonfly Algorithm (BDA) : https://www.mathworks.com/matlabcentral/fileexchange/51032-bda-binary-dragonfly-algorithm
• Binary optimization using hybrid particle swarm optimization and gravitational search algorithm,https://www.mathworks.com/matlabcentral/fileexchange/48314-binary-hybrid-particle-swarm-optimization-and-gravitational-search-algorithm-bpsogsa?s_tid=srchtitle

• and I probably forget tons of others ...

[John D'Errico]

I assume you are looking for an optimization where the search space is limited to a permutation of the integers 1:N? With N being roughly 200? That would be consistent with what you said about factorial(N).

Is that the case?

Of course, brute force ould be a complete waste of time in anything even remotely that large, even a brute force search through a space of size factorial(20) would be a waste of effort.

[John D'Errico]

Please, there is a difference between an answer, and a comment. You made a comment. You did not resolve your own question. Moving your comment:

"Yes, my problem space is 200 factorial in size, so impractical to search all cases. (The spares make it even a bit more permutations, more like 220 with the goal function calculated using the 1st 200 values). With an earlier simulated annealing it was just permute, check, do the SA thing to reject/accept, continue until a set number of permutations was done. Reapeat with a new starting random seed.

At the opposite extreme I've used a genetic code (Evolver from Palisade) that is a black box. Excel add-in with only crossover, mutation, population size and number of generation controls, but it handles the bookkeeping. The method is called order, i.e. order items. I let it run a certain number of times until the diversity gets small (determined by some tests), then restart at the last, best point with high diversity and repeat. Do that a 10X or so times to get a "good enough" answer. All calcs are done in spreadsheets. This is limited by Excel and is bordeline too cumbersome without mixed language programming thru VBA.

On a new project there are more complexities in the calculations due to magnet fabrication technologies being different. That is why I'm looking into using MatLab.

I'll check into the techinques Mathieu suggested.

Thanks"

[John D'Errico]

This is literally the perfect problem for a genetic algoritm to solve. However, I lack the Global Optimization toolbox, so I can only hope that someone else knows how to set up GA to solve it. What I don't know is how to set up GA to intelligently restrict the population to the set of permutations. You could also use the simulated annealing tool in the same TB, at least in theory. So at best, I would advise looking carefuly at the Global Optimization TB.