.NET 4.x Разработка генетического алгоритма составления расписания ВУЗа - C#

Формулировка задачи:

Доброго времени суток! Очень нужна помощь в разработке ГА для составления расписания ВУЗа, с учетом множества условий. Никогда до этого с ГА не сталкивался, но прочитав пару статей и посидев на форумах принцип понял, а разработать свой - никак. У меня программа, которая написана на C#. Полностью формирует нагрузку ВУЗа. Учитывая деление групп на подгруппы. Теперь задача состоит в том, чтобы эту нагрузку распределить на неделю, чтобы у студентов было максимально меньше "окон". Можно и другие алгоритмы, которые относятся к оптимизации. Очень буду благодарен.
Решение задачи: «.NET 4.x Разработка генетического алгоритма составления расписания ВУЗа»

textual
                            Листинг программы 
                        
 
                            
                        
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace LessonPlanNS
{
    static class Program
    {
        static void Main()
        {
            int[] groups   = new int[]{1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5};
            int[] teachers = new int[]{4,1,2,5,3,2,5,4,3,3,1,2,2,4,3,3,3,1,5,1,5,2,2,5,1,4,5,4,1,4};
 
            var list = new List<Lessоn>();
            for (int i = 0; i < groups.Length; i++)
                list.Add(new Lessоn(groups[i], teachers[i]));
 
            var solver = new Solver();//создаем решатель
 
            Plan.DaysPerWeek = 2;//устанавливаем только два учебных дна - это нужно лишь для данной тестовой задачи, в реальности - выставьте нужное число учебных дней!
            Plan.HoursPerDay = 6;
 
            solver.FitnessFunctions.Add(FitnessFunctions.Windows);//будем штрафовать за окна
            solver.FitnessFunctions.Add(FitnessFunctions.LateLesson);//будем штрафовать за поздние пары
 
            var res = solver.Solve(list);//находим лучший план
 
            Console.WriteLine(res);
            Console.ReadLine();
        }
    }
 
    /// <summary>
    /// Фитнесс функции
    /// </summary>
    static class FitnessFunctions
    {
        public static int GroupWindowPenalty = 10;//штраф за окно у группы
        public static int TeacherWindowPenalty = 7;//штраф за окно у преподавателя
        public static int LateLessonPenalty = 1;//штраф за позднюю пару
 
        public static int LatesetHour = 3;//максимальный час, когда удобно проводить пары
 
        /// <summary>
        /// Штраф за окна
        /// </summary>
        public static int Windows(Plan plan)
        {
            var res = 0;
 
            for (byte day = 0; day < Plan.DaysPerWeek; day++)
            {
                var groupHasLessions = new HashSet<int>();
                var teacherHasLessions = new HashSet<int>();
 
                for (byte hour = 0; hour < Plan.HoursPerDay; hour++)
                {
                    foreach (var pair in plan.HourPlans[day, hour].GroupToTeacher)
                    {
                        var group = pair.Key;
                        var teacher = pair.Value;
                        if (groupHasLessions.Contains(group) && !plan.HourPlans[day, hour - 1].GroupToTeacher.ContainsKey(group))
                            res += GroupWindowPenalty;
                        if (teacherHasLessions.Contains(teacher) && !plan.HourPlans[day, hour - 1].TeacherToGroup.ContainsKey(teacher))
                            res += TeacherWindowPenalty;
 
                        groupHasLessions.Add(group);
                        teacherHasLessions.Add(teacher);
                    }
                }
            }
 
            return res;
        }
 
        /// <summary>
        /// Штраф за поздние пары
        /// </summary>
        public static int LateLesson(Plan plan)
        {
            var res = 0;
            foreach (var pair in plan.GetLessons())
                if (pair.Hour > LatesetHour)
                    res += LateLessonPenalty;
 
            return res;
        }
    }
 
    /// <summary>
    /// Решатель (генетический алгоритм)
    /// </summary>
    class Solver
    {
        public int MaxIterations = 1000;
        public int PopulationCount = 100;//должно делиться на 4
 
        public List<Func<Plan, int>> FitnessFunctions = new List<Func<Plan, int>>();
 
        public int Fitness(Plan plan)
        {
            var res = 0;
 
            foreach (var f in FitnessFunctions)
                res += f(plan);
 
            return res;
        }
 
        public Plan Solve(List<Lessоn> pairs)
        {
            //создаем популяцию
            var pop = new Population(pairs, PopulationCount);
            if (pop.Count == 0)
                throw new Exception("Can not create any plan");
            //
            var count = MaxIterations;
            while (count-- > 0)
            {
                //считаем фитнесс функцию для всех планов
                pop.ForEach(p => p.FitnessValue = Fitness(p));
                //сортруем популяцию по фитнесс функции
                pop.Sort((p1, p2) => p1.FitnessValue.CompareTo(p2.FitnessValue));
                //найден идеальный план?
                if (pop[0].FitnessValue == 0)
                    return pop[0];
                //отбираем 25% лучших планов
                pop.RemoveRange(pop.Count / 4, pop.Count - pop.Count / 4);
                //от каждого создаем трех потомков с мутациями
                var c = pop.Count;
                for (int i = 0; i < c; i++)
                {
                    pop.AddChildOfParent(pop[i]);
                    pop.AddChildOfParent(pop[i]);
                    pop.AddChildOfParent(pop[i]);
                }
            }
 
            //считаем фитнесс функцию для всех планов
            pop.ForEach(p => p.FitnessValue = Fitness(p));
            //сортруем популяцию по фитнесс функции
            pop.Sort((p1, p2) => p1.FitnessValue.CompareTo(p2.FitnessValue));
 
            //возвращаем лучший план
            return pop[0];
        }
    }
 
    /// <summary>
    /// Популяция планов
    /// </summary>
    class Population : List<Plan>
    {
        public Population(List<Lessоn> pairs, int count)
        {
            var maxIterations = count * 2;
 
            do
            {
                var plan = new Plan();
                if (plan.Init(pairs))
                    Add(plan);
            } while (maxIterations-- > 0 && Count < count);
        }
 
        public bool AddChildOfParent(Plan parent)
        {
            int maxIterations = 10;
 
            do
            {
                var plan = new Plan();
                if (plan.Init(parent))
                {
                    Add(plan);
                    return true;
                }
            } while (maxIterations-- > 0);
            return false;
        }
    }
 
    /// <summary>
    /// План занятий
    /// </summary>
    class Plan
    {
        public static int DaysPerWeek = 6;//6 учебных дня в неделю
        public static int HoursPerDay = 6;//до 6 пар в день
 
        static Random rnd = new Random(3);
 
        /// <summary>
        /// План по дням (первый индекс) и часам (второй индекс)
        /// </summary>
        public HourPlan[,] HourPlans = new HourPlan[DaysPerWeek, HoursPerDay];
 
        public int FitnessValue { get; internal set; }
 
        public bool AddLesson(Lessоn les)
        {
            return HourPlans[les.Day, les.Hour].AddLesson(les.Group, les.Teacher);
        }
 
        public void RemoveLesson(Lessоn les)
        {
            HourPlans[les.Day, les.Hour].RemoveLesson(les.Group, les.Teacher);
        }
 
        /// <summary>
        /// Добавить группу с преподом на любой день и любой час
        /// </summary>
        public bool AddToAnyDayAndHour(int group, int teacher)
        {
            int maxIterations = 30;
            do
            {
                var day = (byte)rnd.Next(DaysPerWeek);
                if (AddToAnyHour(day, group, teacher))
                    return true;
            } while (maxIterations-- > 0);
 
            return false;//не смогли добавить никуда
        }
 
        /// <summary>
        /// Добавить группу с преподом на любой час
        /// </summary>
        bool AddToAnyHour(byte day, int group, int teacher)
        {
            for (byte hour = 0; hour < HoursPerDay; hour++)
            {
                var les = new Lessоn(day, hour, group, teacher);
                if (AddLesson(les))
                    return true;
            }
 
            return false;//нет свободных часов в этот день
        }
 
        /// <summary>
        /// Создание плана по списку пар
        /// </summary>
        public bool Init(List<Lessоn> pairs)
        {
            for (int i = 0; i < HoursPerDay; i++)
                for (int j = 0; j < DaysPerWeek; j++)
                    HourPlans[j, i] = new HourPlan();
 
            foreach (var p in pairs)
                if (!AddToAnyDayAndHour(p.Group, p.Teacher))
                    return false;
            return true;
        }
 
        /// <summary>
        /// Создание наследника с мутацией
        /// </summary>
        public bool Init(Plan parent)
        {
            //копируем предка
            for (int i = 0; i < HoursPerDay; i++)
                for (int j = 0; j < DaysPerWeek; j++)
                    HourPlans[j, i] = parent.HourPlans[j, i].Clone();
 
            //выбираем два случайных дня
            var day1 = (byte)rnd.Next(DaysPerWeek);
            var day2 = (byte)rnd.Next(DaysPerWeek);
 
            //находим пары в эти дни
            var pairs1 = GetLessonsOfDay(day1).ToList();
            var pairs2 = GetLessonsOfDay(day2).ToList();
 
            //выбираем случайные пары
            if (pairs1.Count == 0 || pairs2.Count == 0) return false;
            var pair1 = pairs1[rnd.Next(pairs1.Count)];
            var pair2 = pairs2[rnd.Next(pairs2.Count)];
 
            //создаем мутацию - переставляем случайные пары местами
            RemoveLesson(pair1);//удаляем
            RemoveLesson(pair2);//удаляем
            var res1 = AddToAnyHour(pair2.Day, pair1.Group, pair1.Teacher);//вставляем в случайное место
            var res2 = AddToAnyHour(pair1.Day, pair2.Group, pair2.Teacher);//вставляем в случайное место
            return res1 && res2;
        }
 
        public IEnumerable<Lessоn> GetLessonsOfDay(byte day)
        {
            for (byte hour = 0; hour < HoursPerDay; hour++)
                foreach (var p in HourPlans[day, hour].GroupToTeacher)
                    yield return new Lessоn(day, hour, p.Key, p.Value);
        }
 
        public IEnumerable<Lessоn> GetLessons()
        {
            for (byte day = 0; day < DaysPerWeek; day++)
                for (byte hour = 0; hour < HoursPerDay; hour++)
                    foreach (var p in HourPlans[day, hour].GroupToTeacher)
                        yield return new Lessоn(day, hour, p.Key, p.Value);
        }
 
        public override string ToString()
        {
            var sb = new StringBuilder();
            for (byte day = 0; day < Plan.DaysPerWeek; day++)
            {
                sb.AppendFormat("Day {0}\r\n", day);
                for (byte hour = 0; hour < Plan.HoursPerDay; hour++)
                {
                    sb.AppendFormat("Hour {0}: ", hour);
                    foreach (var p in HourPlans[day, hour].GroupToTeacher)
                        sb.AppendFormat("Gr-Tch: {0}-{1} ", p.Key, p.Value);
                    sb.AppendLine();
                }
            }
 
            sb.AppendFormat("Fitness: {0}\r\n", FitnessValue);
 
            return sb.ToString();
        }
    }
 
    /// <summary>
    /// План на час
    /// </summary>
    class HourPlan
    {
        /// <summary>
        /// Хранит пару группа-преподаватель
        /// </summary>
        public Dictionary<int, int> GroupToTeacher = new Dictionary<int, int>();
 
        /// <summary>
        /// Хранит пару преподаватель-группа
        /// </summary>
        public Dictionary<int, int> TeacherToGroup = new Dictionary<int, int>();
 
        public bool AddLesson(int group, int teacher)
        {
            if (TeacherToGroup.ContainsKey(teacher) || GroupToTeacher.ContainsKey(group))
                return false;//в этот час уже есть пара у препода или у группы
 
            GroupToTeacher[group] = teacher;
            TeacherToGroup[teacher] = group;
 
            return true;
        }
 
        public void RemoveLesson(int group, int teacher)
        {
            GroupToTeacher.Remove(group);
            TeacherToGroup.Remove(teacher);
        }
 
        public HourPlan Clone()
        {
            var res = new HourPlan();
            res.GroupToTeacher = new Dictionary<int, int>(GroupToTeacher);
            res.TeacherToGroup = new Dictionary<int, int>(TeacherToGroup);
 
            return res;
        }
    }
 
    /// <summary>
    /// Пара
    /// </summary>
    class Lessоn
    {
        public byte Day = 255;
        public byte Hour = 255;
        public int Group;
        public int Teacher;
 
        public Lessоn(byte day, byte hour, int group, int teacher)
            : this(group, teacher)
        {
            Day = day;
            Hour = hour;
        }
 
        public Lessоn(int group, int teacher)
        {
            Group = group;
            Teacher = teacher;
        }
    }
}