Справочная информация
У меня есть проект, в котором мне нужно назначить примерно 200 штатных сотрудников (FTE) на свои рабочие станции.FTE имеют следующие свойства:
- ID (числовая строка)
- Уровень (Администраторы, Старшие, Средний уровень, Юниоры, Партнеры)
- Идентификатор менеджера
- Тип рабочей станции (офис, премиум, новая, средняя, старая) (в порядке убывания качества).
- Отдел
Всем FTE присвоен тип рабочей станциив зависимости от их уровня, поэтому уровни администрирования с большей вероятностью получат офисные типы.Средние уровни, вероятно, получат новые типы, но если их недостаточно, они могут быть увеличены до премии, если есть запасные части.Вероятно, после того, как все назначены, будут пустые рабочие станции.
Рабочие станции также разделены на отдельные секции, пронумерованные от 0 до 9.Каждый раздел имеет различное количество рабочих станций.
Задача
Назначения выполняются со следующими приоритетами (наивысшим первым):
FTE в отделе маркетинга должны находиться в Разделе 2. Если там недостаточно рабочих станций, они могут «переполниться» в соседнюю секцию.
Члены группы (те, кто разделяетодин и тот же менеджер) должен находиться в пределах 5 рабочих единиц друг от друга.
Руководители должны находиться в пределах 10 единиц от ближайшего члена группы.
Те, кто находятся в одном и том же отделе, должны находиться в пределах 5 единиц друг от друга.
Расстояния между одной рабочей станцией к другой представлены в виде структуры данных взвешенного графика.Каждая вершина является рабочей станцией, и каждое ребро имеет расстояние до соседних рабочих станций.
Каков наилучший способ кодирования этой задачи для генетического алгоритма и какие будут подходящие варианты для функций кроссовера, мутации и фитнеса??
В настоящее время у меня есть алгоритм, использующий кроссовер OX1 и случайный обмен, но в целом он работает плохо и медленно.Хромосома закодирована как массив объектов, представляющих FTE, но, поскольку я зеленый для всего этого, это, вероятно, не лучший способ сделать что-либо.