Special scheduling algorithm (template extension)

Question

Question
Do you think genetic algorithms are worth a try for the problem below, or will I remove the problems of local minima?

I think aspects of the problem are great for customizing the style of the generator / fitness function. (If you violated a similar project, I would like to hear from you, and not do something like that)

Thanks for any tips on how to structure things and stick this right.

Problem
I am looking for a good scheduling algorithm to use for the next real problem.

I have a sequence with 15 slots like this (numbers can vary from 0 to 20):

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 

(And there are only 10 different sequences of this type)

Each sequence should expand into an array, where each slot can occupy 1 position.

 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 

The limitations on the matrix are as follows:

• [horizontally, i.e. horizontal] The number of placed should be equal to 11 or 111
• [row-wise] The distance between two sequences 1 must be at least 00
• The sum of each column must match the original array.
• The number of rows in the matrix should be optimized.

Then the array should select one of 4 different matrices, which can have a different number of rows:

 A, B, C, D 

A, B, C and D are departments of the real world. The load should be placed well enough over a 10-day period so as not to interfere with other goals of the department.

Each of the matrices is compared with an extension of 10 different source sequences, so you have:

 A1, A2, A3, A4, A5, A6, A7, A8, A9, A10 B1, B2, B3, B4, B5, B6, B7, B8, B9, B10 C1, C2, C3, C4, C5, C6, C7, C8, C9, C10 D1, D2, D3, D4, D5, D6, D7, D8, D9, D10 

Certain spots on them can be reserved (not sure if I should make it just reserved / not reserved or function-based). Reserved places can be meetings and other events.

The sum of each row (for example, all A) should be approximately the same within 2%. i.e. the sum (from A1 to A10) should be about the same as (from B1 to B10), etc.

The number of rows can vary, so you, for example:

A1: 5 lines A2: 5 lines A3: 1 line, where this single line can, for example, be:

 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 

etc..

Subprogram *

I am very happy to solve only part of the problem. For example, the ability to enter:

 1 1 2 3 4 2 2 3 4 2 2 3 3 2 3 

And we get the corresponding array of sequences with 1 and 0, minimized by the number of lines following the above restrictions.

Answer 1

Attempt to solve a subtask

Well, here is the idea. This solution is not based on the use of a genetic algorithm, but some ideas can be used when moving in this direction.

Basic vectors

First of all, you should generate what I think are basic vectors. For example, if your sequence was 3 numbers longer than 15, the base vectors would be:

 v1 = [1 1 0] v2 = [0 1 1] v3 = [1 1 1] 

Any solution for sequence length 3 would be a linear combination of these three vectors using only positive integers. In other words, a general solution would be

 a*v1 + b*v2 + c*v3 

where a, b and c are natural numbers. For the sequence [1 2 1], the solution is v1 = 1, v2 = 1, v3 = 0. What you first want to do is find all possible base vectors of length 15. From my rough calculations, I think that somewhere between 300-400 basis vectors of length 15. I can give you some advice on creating them if you want.

Searching of decisions

Now, what you want to do is sort these basis vectors by their sums / values. Then, in search of your solution, you start with the basis vectors that have the largest amounts. Let's start with the vectors that have the largest amounts, because they result in fewer lines. We also have an array, veccoefs, which contains an entry for the linear coefficient for each basis vector. At the beginning of the solution search, all veccoefs are 0.

So, we take the first basis vector (the one that has the largest amount / value), and subtract this vector from the sequence until we create an unsolvable result (for example, 0 0 0 in it) or any of the numbers as a result is negative. We save the number of vector deductions in veccoefs. We use the result after subtracting the basis vector from the sequence as a sequence for the next basis vector. If the result is only zeros, then we will stop the cycle.

I am not sure about the effectiveness / accuracy of this method, but it can at least give you some ideas.

Other possible solutions

Another idea for solving this problem is to use basis vectors and formulate the problem as a problem of optimization / least squares. You form the matrix of basis vectors so that the main task will minimize Sum [(Ax - b) ^ 2], where A is the matrix of basis vectors, b is the input sequence, and x are the basis vector coefficients. However, you also want to minimize the number of lines, so you can add a term, such as x ^ T * x, to the minimize function, where x ^ T is the transposition of x. The hard part, in my opinion, is finding differentiable terms to add that will stimulate integer vector coefficients. If you can figure out how to do this, optimization can be a good way to do it.

Alternatively, you might consider a Monte Carlo Monte Carlo solution. You would arbitrarily choose whether to add a vector, delete a vector, or substitute a vector at each step. The vector to be added / deleted / replaced will be randomly selected. The likelihood that this change will be accepted will be the ratio of the acceptability of decisions before and after the change. Suitability may be equal to the difference between the current solution and the sequence, square and sum, minus the number of rows / basis vectors involved in the solution. You will need to set the appropriate constants for different conditions in order to try to get an acceptance rate of about 50%. I doubt that this will work very well, but I thought that you should still consider this when looking for possible solutions.

Answer 2

GA can be applied to this problem, but it will not be a 5 minute task. You need to collect several things, not knowing which implementation of each of them is best.
So:

• Representativeness of the solution - how will you present a possible solution? Using a matrix seems the most direct. Assembly of one-dimensional arrays is also possible. But you have some limitations, so maybe you should consider the concept of SuperGene?
• You must use the appropriate mutation / crossover operators for the given gene representation.
• How will you apply decision restrictions? Destroy those that are not right? What if they contain valuable information? Maybe let them remain in the population, but add a fine to fitness, so they will promote offspring, but will not go to the next generation?

In any case, I think GA can be applied to this problem. Is it worth it? GA is usually not the best algorithm, but they are a decent algorithm if others fail. I would go with GA, simply because it would be a lot of fun, but I would look for an alternative solution (just in case).

PS Personal understanding: I solved the N Queens Problem, for 70 <N <100 (NxN board, N queens). The algorithm worked fine for a lower N (maybe he tried to use all the combinations?), But with N in this range I could not find the correct solution. Fitness quickly jumped up to about 90% of the maximum, but in the end there were always two queens. But it was a very naive implementation.