Swap between two sub array of an array

Swap between two sub sequences. Position one and two are selected randomly first and then position three and four. Provided these selections do not overlap then element sequence between position one and two and element sequence between position three and four are swapped.

Example: idx1 = [2 4], idx2 = [7 10], A = [2 5 3 4 7 1 6 9 8 10 11 12] would become Anew=[2 6 9 8 10 7 1 5 3 4 11 12]

Thank you

[Stephan]

Is this a homework?

[Amine Ne]

Noooo, I'm trying to improve the local search of my algorithm by using some local search operators such as swapping, reversing...

[Stephan]

i guess it will improve your Chance getting an answer if you accept the working answers you have got so far for the other (similary) questions you asked.

[Amine Ne]

Ok Stephan

[Stephan]

do you want idx1 to be another length then idx2 - im asking because idx1 has length = 3 and idx2 is length = 4

[Amine Ne]

Sorry to be late, Yes Stephan, I want idx1 to be another length then idx2, but not always. So we have two possibilties: length of idx1 = length of idx2 OR length of idx1 =! length of idx2

Thank you Stephan

Answer 1

[Stephan]

If i assume that you want to swap idx which have the same length:

A = [2 5 3 4 7 1 6 9 8 10 11 12] 
idx1 = [2 4];
idx2 = [7 9];

A_new = A;
A_new(idx1(1):idx1(2)) = A(idx2(1):idx2(2));
A_new(idx2(1):idx2(2)) = A(idx1(1):idx1(2))

gives:

A =

       2     5     3     4     7     1     6     9     8    10    11    12

A_new =

       2     6     9     8     7     1     5     3     4    10    11    12

EDIT:

This works for your example:

A = [2 5 3 4 7 1 6 9 8 10 11 12] 
idx1 = [2 4];
idx2 = [7 10];

A_new = A(1:idx1(1)-1);
A_new = [A_new, A(idx2(1):idx2(2))];
A_new = [A_new, A(idx1(2)+1:idx2(1)-1)];
A_new = [A_new, A(idx1(1):idx1(2))];
A_new = [A_new, A(idx2(2)+1:end)]

result:

A =

       2     5     3     4     7     1     6     9     8    10    11    12

A_new =

       2     6     9     8    10     7     1     5     3     4    11    12

I did not test other examples.

Best regards

Stephan

[Amine Ne]

Thank you Stephan, but idx1 and idx2 are choosen randomly (are not predefined). For example idx1 = randi(12, 1, 2) = [12 9] and idx2 = randi(12, 1, 2) = [4 10]

[Stephan]

In this example idx1 intersects with idx2.

If:

• idx1(2) < idx2(1) and
• idx1 and idx2 are sorted ascending

then they do not overlap eachother and it should work.

idx1 = [4 5];
idx2 = [9 12];

Did work when i tested. Your example (which not meets the conditions above) did not work. So when creating the random numbers it is needed to make sure meeting this conditions.

[Amine Ne]

Thank you Stephan Jung, The solution is:

nVar = 12;
A = randperm(nVar);
idx1 = randi([1,nVar-2], 1, 2);
idx1 = sort(idx1);
idx2 = randi([idx1(2)+1,nVar], 1, 2);
idx2 = sort(idx2);
A_new = A(1:idx1(1)-1);
A_new = [A_new, A(idx2(1):idx2(2))];
A_new = [A_new, A(idx1(2)+1:idx2(1)-1)];
A_new = [A_new, A(idx1(1):idx1(2))];
A_new = [A_new, A(idx2(2)+1:end)];

Result:

A =

     1     6     4     8    10    11     3    12     2     5     7     9

idx1 =

     5     6

idx2 =

     9    12

A_new =

     1     6     4     8     2     5     7     9     3    12    10    11

Answer 2

[Amine Ne]

Thank you Stephan Jung, The solution is:

nVar = 12;
A = randperm(nVar);
idx1 = randi([1,nVar-2], 1, 2);
idx1 = sort(idx1);
idx2 = randi([idx1(2)+1,nVar], 1, 2);
idx2 = sort(idx2);
A_new = A(1:idx1(1)-1);
A_new = [A_new, A(idx2(1):idx2(2))];
A_new = [A_new, A(idx1(2)+1:idx2(1)-1)];
A_new = [A_new, A(idx1(1):idx1(2))];
A_new = [A_new, A(idx2(2)+1:end)];

Result:

A =

     1     6     4     8    10    11     3    12     2     5     7     9

idx1 =

     5     6

idx2 =

     9    12

A_new =

     1     6     4     8     2     5     7     9     3    12    10    11

[Stephan]

Nice,

but i guess it is a pretty expensive calculation if you use it for local search. I think about TSP for example to use it and how many times it has to be calculated to get a better result...

However, the code is working so far.

[Amine Ne]

For my algorithm, at each local search step, I chooses one method randomly from: 1/ Swapping between two jobs selected randomly. 2/ Reversing job order in a selected sub sequence. 3/ Swapping between two sub sequences. 4/ Swapping between three jobs and 5/ insert operator.

The algorithm is applied to solve the scheduling problem.

[Amine Ne]

Do you have any suggestions or anothers methods to improve the local search?

[Stephan]

Do you have to write your own algorithm? If not i would suggest to use Global Optimization Toolbox (if you have access to it), since there are possibilities of parallelisation (if you have access to Parallel omputing Toolbox) and the code is optimized by professionals.

If you have or want to write your own code i would suggest to do the following:

I think it would be worthwhile to search the forum and the documentation for vectorization, parallelization and performance enhancement and related topics.

There are numerous contributions (accepted answers) specifically from the MVP contributers (e.g. Walter Roberson, Jan, Stephen Cobeldick, John D'Errico, Star Strider, Guillaume, dpb, KSSV ... and many others) in which people have asked for options on their code to optimize and speed up.

Especially James Tursa (according to his profile) is interested in speed and performance and has certainly given some good hints in his answers.

These are certainly good sources to get suggestions for your project.

Another way (you can do by yourself) is to check and improve your code by using the Profiler feature and the Analyze Code Button. These tools show you where in your code how much time is spent or where you have typical errors. This may provide evidence of improvement.

I suggest you to try these ways and in places where you have questions to come back with a new question here. It's always amazing to see how well some people can deal with Matlab and how much knowledge is available here.

As an example read this link where i asked for the possibilities of improvement from a matlab code. The answer John D'Errico gave me brought me a lot of insight to this topic.

Thats what i can suggest you.

Best regards

Stephan

[Amine Ne]

Hi Stephan,

Thank you very much for your detailed and helpful explanation. I have already implemented an algorithm with my own code. I work on bio-inspired algorithms such as ABC, BA, PSO...

I will take your suggestions into consideration. Thank you again