Algorithme de composition de groupe par affinité

Code :
DROP TABLE IF EXISTS test_students; -- List of students (temporary table for calculation)

CREATE TABLE test_students (id INT UNSIGNED NOT NULL, classroom INT UNSIGNED NULL, PRIMARY KEY (id)) ENGINE=HEAP;

DROP TABLE IF EXISTS test_students_result; -- List of students (real result you should look to)

CREATE TABLE test_students_result (id INT UNSIGNED NOT NULL, classroom INT UNSIGNED NULL, PRIMARY KEY (id)) ENGINE=HEAP;

DROP TABLE IF EXISTS test_classrooms; -- List of classrooms

CREATE TABLE test_classrooms (id INT UNSIGNED NOT NULL, globalScore DOUBLE NULL, score DOUBLE NULL, PRIMARY KEY (id)) ENGINE=HEAP;



DROP PROCEDURE IF EXISTS test_students_n_classes;

DROP PROCEDURE IF EXISTS test_eval_classrooms_scores;

DELIMITER $$

CREATE PROCEDURE test_eval_classrooms_scores(

        studentsPerClass DOUBLE)

BEGIN

    UPDATE test_classrooms AS c

    INNER JOIN (

        SELECT 

                c.id, 

                SUM(tr.strength)

--             AVG(tr.strength)/(0.1 + STD(tr.strength))

                    AS score

            FROM test_classrooms AS c

            INNER JOIN test_students AS f ON f.classroom = c.id

            INNER JOIN test_students AS t ON t.id > f.id AND t.classroom = c.id

            INNER JOIN test_relations AS tr ON tr.id_from = f.id AND tr.id_to = t.id

            GROUP BY c.id) AS scores ON scores.id = c.id

    SET

        -- If we do some "fake Swaps", then number of students in a classroom may differ from initial distribution, in such case, give this difference a weight

        -- The goal is to have balanced classrooms (globalScore is always negative, and the farther from balanced classroom, the more negative score)

        c.globalScore = -POW( (SELECT SUM(1) FROM test_students AS s WHERE s.classroom = c.id)-studentsPerClass,2 )*SQRT(studentsPerClass),

        c.score = scores.score + c.globalScore

            ;

END$$



CREATE PROCEDURE test_students_n_classes (

        eleves INT UNSIGNED,

        partitionnings INT UNSIGNED,

        tries INT UNSIGNED,

        iterationsPerTry INT UNSIGNED,

        fakeSwapsProportion DOUBLE)

BEGIN

    

    SET @tryScore := NULL;

    SET @tries := tries;

    WHILE (@tries > 0) DO

        -- We create a random partitionning

        SET @currentScore := NULL;

        UPDATE test_students SET classroom = FLOOR(1+RAND()*partitionnings);

        

        -- We try a change, then eval the new partitionning score, and if better, keep that change effective

        SET @iterationsPerTry := iterationsPerTry;

        WHILE (@iterationsPerTry > 0) DO

            SET @randomStud1 := FLOOR(1+RAND()*eleves);

            SET @randomClass1 := (SELECT classroom FROM test_students WHERE id = @randomStud1);

            SET @randomClass2 := (SELECT id FROM test_classrooms AS c WHERE c.id != @randomClass1 ORDER BY RAND() LIMIT 1);

            SET @randomStud2 := (SELECT id FROM test_students AS s WHERE s.classroom = @randomClass2 ORDER BY RAND() LIMIT 1);

            UPDATE test_students AS s SET classroom = @randomClass2 WHERE s.id = @randomStud1;

            IF (RAND() > fakeSwapsProportion) THEN

                UPDATE test_students AS s SET classroom = @randomClass1 WHERE s.id = @randomStud2;

            END IF;

            

            CALL test_eval_classrooms_scores(eleves/partitionnings);

            SET @newScore := (

                SELECT

                        SUM(score)

--                         AVG(score)/(0.01 + STD(score))

                    FROM test_classrooms AS t);

            IF (@newScore > @currentScore OR @currentScore IS NULL) THEN

                SET @currentScore := @newScore;

                SET @iterationsPerTry := iterationsPerTry;

            ELSE

                UPDATE test_students AS s SET classroom = @randomClass1 WHERE s.id = @randomStud1;

                UPDATE test_students AS s SET classroom = @randomClass2 WHERE s.id = @randomStud2;

                SET @iterationsPerTry := @iterationsPerTry - 1;

            END IF;

        END WHILE;

        

        IF (@currentScore > @tryScore OR @tryScore IS NULL) THEN

            TRUNCATE TABLE test_students_result;

            INSERT INTO test_students_result (SELECT * FROM test_students);

            SET @tryScore := @currentScore;

            SET @tries := tries;

        ELSE

            SET @tries := @tries - 1;

        END IF;

    END WHILE;

    COMMIT;

END$$



DELIMITER ;



-- Step 0: values

SET @eleves := 60;

SET @partitionnings := 3;

SET @tries := 20; -- Actually, it's the number of consecurive failed tries

SET @iterationsPerTry := 200; -- Actually, it's the number of consecutive failed iterations in a try

SET @fakeSwapsProportion := 0.2; -- Probability 0(=only swaps)..1(=no swap) of moving student B to class cA when swapping students A and B from classrooms cA and cB



TRUNCATE TABLE test_students;

INSERT INTO test_students (SELECT n AS id, NULL FROM integers WHERE n BETWEEN 1 AND @eleves);

TRUNCATE TABLE test_classrooms;

INSERT INTO test_classrooms (SELECT n AS id, NULL, NULL AS score FROM integers WHERE n BETWEEN 1 AND @partitionnings);



-- Step 1: each pair of student must have an "affinity score", from 0 (they "must" not be together) to 1 (they "must" be together in a class)

-- Commented out are some suggestions to try

TRUNCATE TABLE test_relations;

INSERT INTO test_relations (id_from, id_to, strength) (

    SELECT 

        f.id,

        t.id,

--         IF(FLOOR(f.id / (@eleves/@partitionnings)) = FLOOR(t.id / (@eleves/@partitionnings)), 1, 0)

--         f.id / t.id

        RAND()

    FROM test_students AS f

    INNER JOIN test_students AS t ON t.id > f.id);



-- Step 2: calculate

CALL test_students_n_classes(@eleves, @partitionnings, @tries, @iterationsPerTry, @fakeSwapsProportion);



-- Step 3: results!

SELECT 

    c.id,

    c.score,

    c.globalScore,

    GROUP_CONCAT(s.id ORDER BY s.id ASC) AS students,

    SUM(1) AS studentCount

FROM test_classrooms AS c

INNER JOIN test_students_result AS s ON s.classroom = c.id

GROUP BY c.id

ORDER BY studentCount;



SELECT * FROM test_relations;