특수 스케줄링 알고리즘(패턴 확장)

Question

질문
아래 문제를 해결하기 위해 유전 알고리즘을 시도해 볼 가치가 있다고 생각하시나요? 아니면 로컬 최소 문제에 부딪히게 될까요?

제 생각에는 문제의 측면이 발전기/피트니스 기능 스타일 설정에 적합할 수도 있습니다.(만약 당신이 비슷한 프로젝트를 망쳤다면 나는 당신의 의견을 듣고 싶고 비슷한 일은 하지 않을 것입니다)

사물을 구조화하고 올바르게 만드는 방법에 대한 조언을 제공해 주셔서 감사합니다.

문제
나는 다음과 같은 실제 문제에 사용할 좋은 스케줄링 알고리즘을 찾고 있습니다.

다음과 같은 15개의 슬롯이 있는 시퀀스가 ​​있습니다(숫자는 0에서 20까지 다양할 수 있음).

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

(그리고 이 유형에는 총 10개의 서로 다른 시퀀스가 ​​있습니다)

각 시퀀스는 각 슬롯이 1개의 위치를 ​​차지할 수 있는 배열로 확장되어야 합니다.

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 

행렬의 제약 조건은 다음과 같습니다.

• [행별, 즉가로] 배치되는 개수는 11개 또는 111개이어야 합니다.
• [행별] 1로 구성된 두 시퀀스 사이의 거리는 최소 00이어야 합니다.
• 각 열의 합은 원래 배열과 일치해야 합니다.
• 행렬의 행 수는 최적화되어야 합니다.

그런 다음 배열은 서로 다른 행 수를 가질 수 있는 4개의 서로 다른 행렬 중 하나를 할당해야 합니다.

A, B, C, D

A, B, C, D는 실제 부서입니다.부하는 다른 부서 목표를 방해하지 않고 10일 동안 합리적으로 공정하게 배치되어야 합니다.

각 행렬은 10개의 서로 다른 원래 시퀀스의 확장과 비교되므로 다음을 얻을 수 있습니다.

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

이들 중 특정 지점은 예약되어 있을 수 있습니다(예약해야 하는지/예약되지 않도록 설정해야 하는지 또는 기능 기반으로 설정해야 하는지 확실하지 않음). 예약된 장소는 회의 및 기타 행사일 수 있습니다.

각 행의 합(예: 모든 A)은 대략 2% 내에서 동일해야 합니다.즉.sum(A1 ~ A10)은 (B1 ~ B10)과 대략 동일해야 합니다.

행 수는 다양할 수 있으므로 예를 들어 다음과 같습니다.

A1:5 행 A2 :5 행 A3 :예를 들어 단일 행은 다음과 같을 수 있습니다.

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

등..

하위 문제*

문제의 일부만 해결하게 되어 매우 기쁩니다.예를 들어 다음을 입력할 수 있습니다.

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

그리고 위의 제약 조건을 따르는 행 수에서 1과 0이 최소화된 적절한 시퀀스 배열을 얻습니다.

Answer 1

하위 문제 해결 시도

음, 여기에 아이디어가 있습니다.이 솔루션은 유전 알고리즘을 사용하는 것을 기반으로 하지 않지만 그 방향으로 나아가는 데 몇 가지 아이디어가 사용될 수 있습니다.

기초 벡터

우선, 제가 생각하는 기본 벡터를 생성해야 합니다.예를 들어, 시퀀스가 ​​15개가 아닌 3개의 숫자인 경우 기본 벡터는 다음과 같습니다.

v1 = [1 1 0]

v2 = [0 1 1]

v3 = [1 1 1]

시퀀스 길이 3에 대한 모든 솔루션은 양의 정수만 사용하는 세 벡터의 선형 조합입니다.즉, 일반적인 해결책은 다음과 같습니다.

a*v1 + b*v2 + c*v3

여기서 a, b 및 c는 양의 정수입니다.수열 [1 2 1]의 경우 해는 v1 = 1, v2 = 1, v3 = 0입니다.가장 먼저 하고 싶은 일은 길이가 15인 가능한 기본 벡터를 모두 찾는 것입니다.내 대략적인 계산에 따르면 길이가 15인 기본 벡터가 300~400개 정도 있다고 생각됩니다.원하시면 생성에 대한 몇 가지 팁을 드릴 수 있습니다.

해결책 찾기

이제 여러분이 원하는 것은 이러한 기본 벡터를 합/크기별로 정렬하는 것입니다.그런 다음 해를 검색할 때 합이 가장 큰 기본 벡터부터 시작합니다.총 행 수가 적기 때문에 합이 가장 큰 벡터부터 시작합니다.또한 각 기본 벡터에 대한 선형 계수에 대한 항목을 포함하는 veccoefs 배열이 있습니다.해 찾기 시작 시 모든 veccoef는 0입니다.

따라서 첫 번째 기본 벡터(가장 큰 합/크기를 갖는 벡터)를 취하고 풀 수 없는 결과(예를 들어 0 1 0 포함) 또는 결과의 숫자 중 하나가 생성될 때까지 시퀀스에서 이 벡터를 뺍니다. 부정적이다.벡터를 뺀 횟수를 veccoefs에 저장합니다.시퀀스에서 기본 벡터를 뺀 결과를 다음 기본 벡터의 시퀀스로 사용합니다.결과에 0만 남으면 루프를 중지합니다.

이 방법의 효율성/정확성은 확실하지 않지만 최소한 몇 가지 아이디어를 얻을 수는 있습니다.

다른 가능한 솔루션

이 문제를 해결하기 위한 또 다른 아이디어는 기본 벡터를 사용하여 문제를 최적화/최소 제곱 문제로 구성하는 것입니다.기본 문제가 Sum[(Ax - b)^2]를 최소화하도록 기본 벡터의 행렬을 구성합니다. 여기서 A는 기본 벡터의 행렬이고, b는 입력 시퀀스이고, x는 기본 벡터 계수입니다.그러나 행 수를 최소화하려고 하므로 x^T가 x의 전치인 최소화 함수에 x^T*x와 같은 항을 추가할 수 있습니다.내 생각에 어려운 부분은 정수 벡터 계수를 장려할 추가할 미분 가능한 항을 찾는 것입니다.그렇게 할 수 있는 방법을 생각할 수 있다면 최적화가 이를 수행하는 좋은 방법이 될 수 있습니다.

또한 Metropolis형 Monte Carlo 솔루션을 고려해 볼 수도 있습니다.각 단계에서 벡터를 추가하거나, 벡터를 제거하거나, 벡터를 대체할지 여부를 무작위로 선택합니다.추가/제거/대체할 벡터는 무작위로 선택됩니다.이 변경이 승인될 확률은 변경 전과 변경 후 솔루션의 적합성의 비율입니다.적합성은 현재 솔루션과 제곱 및 합산된 시퀀스 간의 차이에서 솔루션에 포함된 행/기본 벡터 수를 뺀 값과 동일할 수 있습니다.약 50%의 합격률을 얻으려면 다양한 용어에 대해 적절한 상수를 입력해야 합니다.이것이 잘 작동할지는 의문이지만, 가능한 해결책을 찾을 때 여전히 고려해야 한다고 생각했습니다.

Answer 2

GA를 이 문제에 적용할 수 있지만 5분 안에 완료되는 작업은 아닙니다.각각의 어떤 구현이 가장 좋은지 알지 못한 채 여러 가지를 함께 모아야 합니다.
그래서:

1. 솔루션 표현 - 가능한 솔루션을 어떻게 표현할 것인가?행렬을 사용하는 것이 가장 간단한 것 같습니다.1차원 배열을 수집하는 것도 가능합니다.하지만 몇 가지 제약이 있으므로 SuperGene 개념을 고려해 볼 가치가 있을까요?
2. 주어진 유전자 표현에 대해 적절한 돌연변이/교차 연산자를 사용해야 합니다.
3. 솔루션에 대한 제약을 어떻게 적용할 예정인가요?적절하지 않은 것을 파괴하는가?귀중한 정보가 포함되어 있다면 어떨까요?어쩌면 개체 수는 유지하면서 체력에 약간의 페널티를 추가하여 자손에 기여하지만 다음 세대로 넘어가지 않게 할 수 있을까요?

어쨌든 나는 이 문제에 GA를 적용할 수 있다고 생각한다.그만한 가치가 있나요?일반적으로 GA는 최고의 알고리즘은 아니지만 다른 알고리즘이 실패하면 괜찮은 알고리즘입니다.나는 GA가 가장 재미있을 것이기 때문에 GA를 선택하겠지만 만약을 대비해 대체 솔루션을 찾을 것입니다.

추신개인적 통찰력:나는 70 < N < 100(보드 NxN, N 퀸)에 대한 N Queens 문제를 해결하고 있었습니다.알고리즘은 N이 낮은 경우에는 잘 작동했지만(아마도 모든 조합을 시도하고 있었을 것입니다.) 이 범위의 N에서는 적절한 솔루션을 찾을 수 없었습니다.체력은 빠르게 최대치의 90% 정도까지 올라갔지만, 결국엔 항상 두 명의 퀸이 충돌했다.그러나 그것은 매우 순진한 구현이었습니다.