Какой самый быстрый алгоритм эвристики разбивает студентов на группы?

Question

У меня есть X учеников, где X кратно 6. Теперь я хочу разбить учащихся на группы по 6.

У меня есть функция, которая измеряет, как «хорошая» группа из 6 (скажем, это черный ящик, который работает в постоянное время). Разбивая студентов, а затем называя мою функцию в каждой группе, чтобы оценить ее доброту, а затем подытоживая доброту каждой группы, я могу измерить, насколько «хорош» определенный набор групп.

Я пытаюсь создать алгоритм, который будет группировать учащихся таким образом, чтобы общая доброта всех групп была максимальной, и ни одна группа не имеет индивидуальной доброты ниже некоторого значения y. Другими словами, сгруппируйте учащихся в группы по 6, чтобы максимизировать общую доброту под ограничением, что все группы имеют доброту выше y.

Число студентов (X) Я ожидаю запустить этот алгоритм примерно на ~ 36.

Проблема, кажется, NP-Complete, поэтому я в порядке с установкой эвристического алгоритма. У меня нет большого опыта в этом, но какой-то генетический алгоритм или симулированный отжиг или даже жадный алгоритм могут работать, я думаю, но я не уверен, с чего начать исследования.

Может ли кто-нибудь указать мне в правильном направлении, пожалуйста? Я провел некоторое исследование, и проблема кажется почти идентичной проблеме Traveling Salesman (проблемное пространство - это все перестановки студентов/узлов), но я не думаю, что могу применить к этому алгоритмы TSP, поскольку число «узлов» «(около 36) будет достаточно большим, чтобы что-то могло быть эффективным.

Answer 1

Я хотел бы начать с очень простого алгоритма «случайного поиска»:

start from a random solution (a partition of X to groups), call it S[0] 

score[0] = black_box_socre(S[0]) 

i = 0 

while (some condition): 
    i++ 
    S[i] = some small permutation on S[i-1] # (1) 
    score[i] = black_box_score(S[i]) 
    if score[i] < score[i-1]: # (2) 
     S[i] = S[i-1] 
     score[i] = score[i-1] 

(1) - небольшая перестановка может быть в вашем случае, переключение 2-х человек между группами.

(2) - Если мы внесли изменения, которые сделали наше решение хуже (нижний балл), мы его отклоним. Вы можете позже заменить это, приняв, с некоторой вероятностью, худшие решения, чтобы сделать этот алгоритм в имитированным отжигом.

Начните с простого запуска этого для 1000 итераций или так, и запишите оценку [i] как функцию i, чтобы понять, как быстро ваше решение улучшается. Запустите это несколько раз (чтобы попробовать разные случайные стартовые точки).

Затем вы можете играть с различными перестановками (1), сделать алгоритм менее жадным (2) или добавить какую-нибудь фантастическую автоматическую логику, чтобы остановить поиск (например, никакого прогресса в последних T итерациях).

Answer 2

Давайте рассмотрим пример 36 студентов, распределенных по 6 группам. Проверка всех комбинаций нецелесообразна, поскольку имеется 3 708 580 189 773 818 390 040. Однако стратегия, которая делает повторные улучшения путем проверки каждого распределения студентов между парами групп, должна быть осуществимой.

Есть 462 способа разделить 12 студентов на 2 группы, поэтому для нахождения оптимального распределения2 требуется только 924 вызова функции «группового качества». Существует 15 возможных групп групп из 6 групп, поэтому 13 860 звонков выявят наилучший способ соединить группы и перераспределить студентов между парами, чтобы получить наибольшее улучшение.

Чтобы иметь возможность писать код для проверки этой стратегии, необходим пример функции «группового качества», поэтому я нумерую студентов от 1 до 36 и используя функцию, которая умножает расстояние между соседними номерами учеников. Так, например, группа [2,7,15,16,18,30] имела бы счет 5*8*1*2*12 = 960. Если вы представляете, что нумерация является ранжированием способности студентов, то высококачественная группа означает группу смешанных способностей. Оптимальное распределение:

 
group A: [1, 7, 13, 19, 25, 31] 
group B: [2, 8, 14, 20, 26, 32] 
group C: [3, 9, 15, 21, 27, 33] 
group D: [4, 10, 16, 22, 28, 34] 
group E: [5, 11, 17, 23, 29, 35] 
group F: [6, 12, 18, 24, 30, 36] 

с каждой группой забил 6*6*6*6*6 = 7776 и общим счетом 46656. На практике я обнаружил, что использование Log(score) дает лучшие результаты, поскольку оно благоприятствует небольшим улучшениям во всех группах при больших улучшениях до одной или двух групп. (Преимущество улучшений для нескольких групп или групп самого низкого качества или просто выбор наилучшего общего улучшения - это то, что вам нужно будет точно настроить на вашу специальную функцию «группового качества».)

Начиная с случайное распределение, алгоритм вычисляет оптимальное распределение для всех 15 пар групп: AB,CD,EF,BC,DE,FA,AC,BD,CE,DF,EA,FB,AD,BE,CF. Затем он сравнивает оценки для всех 15 комбинаций пар, чтобы найти комбинацию с наивысшим баллами, например. DE+AC+FB. Затем он перераспределяет студентов и возвращает новый общий балл. Это является одним из этапов улучшения.

К моему удивлению, алгоритму всегда удается найти оптимальное решение и всего за 4-7 шагов, что означает, что производятся менее 100 000 вызовов группового качества. Алгоритм «группового качества», который я использую, конечно, довольно прост, поэтому вам нужно будет проверить его с помощью реальной вещи, чтобы оценить полезность этого подхода в вашем конкретном случае. Но ясно, что этот алгоритм позволяет полностью перестроить распределение всего за несколько шагов.

(В примере кода ниже жестко закодировано для случая 36 студентов для простоты. Сортировка студентов в каждой группе делается для упрощения функции качества.)

function improve(groups) { 
 
    var pairs = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,0],[0,2],[1,3],[2,4],[3,5],[4,0],[5,1],[0,3],[1,4],[2,5]]; 
 
    var combi = [[0,2,4],[1,3,5],[0,3,14],[1,4,12],[2,5,13],[0,8,9],[1,9,10],[2,10,11],[3,6,11],[4,6,7],[5,7,8],[7,10,14],[6,9,13],[8,11,12],[12,13,14]]; 
 
    // FIND OPTIMAL DISTRIBUTION FOR ALL PAIRS OF GROUPS 
 
    var optim = []; 
 
    for (var i = 0; i < 15; i++) { 
 
     optim[i] = optimise(groups[pairs[i][0]], groups[pairs[i][1]]); 
 
    } 
 
    // FIND BEST COMBINATION OF PAIRS 
 
    var best, score = -1; 
 
    for (var i = 0; i < 15; i++) { 
 
     var current = optim[combi[i][0]].score + optim[combi[i][1]].score + optim[combi[i][2]].score; 
 
     if (current > score) { 
 
      score = current; 
 
      best = i; 
 
     } 
 
    } 
 
    // REDISTRIBUTE STUDENTS INTO GROUPS AND RETURN NEW SCORE 
 
    groups[0] = optim[combi[best][0]].group1.slice(); 
 
    groups[1] = optim[combi[best][0]].group2.slice(); 
 
    groups[2] = optim[combi[best][1]].group1.slice(); 
 
    groups[3] = optim[combi[best][1]].group2.slice(); 
 
    groups[4] = optim[combi[best][2]].group1.slice(); 
 
    groups[5] = optim[combi[best][2]].group2.slice(); 
 
    return score; 
 
} 
 

 
// FIND OPTIMAL DISTRIBUTION FOR PAIR OF GROUPS 
 
function optimise(group1, group2) { 
 
    var optim = {group1: [], group2: [], score: -1}; 
 
    var set = group1.concat(group2).sort(function(a, b) {return a - b}); 
 
    var distr = [0,0,0,0,0,1,1,1,1,1,1]; 
 
    // TRY EVERY COMBINATION 
 
    do { 
 
     // KEEP FIRST STUDENT IN FIRST GROUP TO AVOID SYMMETRIC COMBINATIONS 
 
     var groups = [[set[0]], []]; 
 
     // DISTRIBUTE STUDENTS INTO GROUP 0 OR 1 ACCORDING TO BINARY ARRAY 
 
     for (var j = 0; j < 11; j++) { 
 
      groups[distr[j]].push(set[j + 1]); 
 
     } 
 
     // CHECK SCORE OF GROUPS AND STORE IF BETTER 
 
     var score = quality(groups[0]) + quality(groups[1]); 
 
     if (score > optim.score) { 
 
      optim.group1 = groups[0].slice(); 
 
      optim.group2 = groups[1].slice(); 
 
      optim.score = score; 
 
     } 
 
    } while (increment(distr)); 
 
    return optim; 
 

 
    // GENERATE NEXT PERMUTATION OF BINARY ARRAY 
 
    function increment(array) { 
 
     var digit = array.length, count = 0; 
 
     while (--digit >= 0) { 
 
      if (array[digit] == 1) ++count 
 
      else if (count) { 
 
       array[digit] = 1; 
 
       for (var i = array.length - 1; i > digit; i--) { 
 
        array[i] = --count > 0 ? 1 : 0; 
 
       } 
 
       return true; 
 
      } 
 
     } 
 
     return false; 
 
    } 
 
} 
 

 
// SCORE FOR ONE GROUP ; RANGE: 0 ~ 8.958797346140275 
 
function quality(group) { 
 
    // LOGARITHM FAVOURS SMALL IMPROVEMENTS TO ALL GROUPS OVER LARGE IMPROVEMENT TO ONE GROUP 
 
    return Math.log((group[5] - group[4]) * (group[4] - group[3]) * (group[3] - group[2]) * (group[2] - group[1]) * (group[1] - group[0])); 
 
} 
 

 
// SUM OF SCORES FOR ALL 6 GROUPS ; RANGE: 0 ~ 53.75278407684165 
 
function overallQuality(groups) { 
 
    var score = 0; 
 
    for (var i = 0; i < 6; i++) score += quality(groups[i]); 
 
    return score; 
 
} 
 

 
// PREPARE RANDOM TEST DATA 
 
var students = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36]; 
 
var groups = [[],[],[],[],[],[]]; 
 
for (var i = 5; i >=0; i--) { 
 
    for (var j = 5; j >= 0; j--) { 
 
     var pick = Math.floor(Math.random() * (i * 6 + j)); 
 
     groups[i].push(students[pick]); 
 
     students[pick] = students[i * 6 + j]; 
 
    } 
 
    groups[i].sort(function(a, b) {return a - b}); 
 
} 
 

 
// DISPLAY INITIAL SCORE AND DISTRIBUTION 
 
var score = overallQuality(groups); 
 
document.write("<PRE>Initial: " + score.toFixed(2) + " " + JSON.stringify(groups) + "<BR>"); 
 

 
// IMPROVE DISTRIBUTION UNTIL SCORE NO LONGER INCREASES 
 
var prev, step = 0; 
 
do { 
 
    prev = score; 
 
    score = improve(groups); 
 
    document.write("Step " + ++step + " : " + score.toFixed(2) + " " + JSON.stringify(groups) + "<BR>"); 
 
} while (score > prev && score < 53.75278407684165); 
 
if (score >= 53.75278407684165) document.write("Optimal solution reached.</PRE>");