English

Архив публикаций

Тезисы

XVI-ая конференция

Генетические алгоритмы в теории расписаний.

Родькина М.Б., Аснина А.Я.

Россия, г.Воронеж, Беговая 6/2

1  стр. (принято к публикации)

Рассматривается система обслуживания, состоящая из M машин и N работ. Очередность выполнения операций задаётся перестановкой . Для системы задана матрица длительностей выполнения работ T. Необходимо найти расписание работ минимальной длины. Цель исследования — разработка генетического алгоритма для решения данной задачи.

Особь — перестановка, соответствующая расписанию . В качестве функции приспособленности выступает длина расписания. В алгоритме используется рулеточный отбор. Все особи популяции делятся на две группы по принадлежности в определённому полу. Четная перестановка считается женской особью, нечетная – мужской. Родительская пара формируется из двух особей разного пола. После выбора родителей происходит скрещивание со 100% вероятностью, при этом, если получившаяся особь уже существует в популяции, то происходит мутация путем случайной транспозиции в перестановке. Потомки получаются умножением квадрата одной из перестановок на другую или простым умножением перестановок. Такое скрещивание гарантирует получение до четырех различных перестановок (по две разной четности). Затем и потомки, и родители возвращаются в популяцию, из которой были взяты родители. Каждой особи популяции ставится в соответствие число — её возраст (изначально равный нулю). При каждом скрещивании возраст всей популяции (кроме полученных на данном этапе потомков) возрастает на единицу. Как только возраст особи достигает определенного порога, она заносится в так называемую критическую область. При занесении в эту область особь сохраняет способность к скрещиванию, но подвержена риску смерти при каждом скрещивании особей популяции. При этом на каждое скрещивание приходится смерть от одной до четырех особей критической области. Если популяция вырождается, она принимает решение о слиянии с какой-нибудь другой популяцией или об объявлении войны, исход которой зависит от суммарной приспособленности мужчин и лидеров. Если особей слишком много, то часть их может отделиться и образовать новую популяцию. Если наблюдается слишком большая разница в количествах мужчин и женщин, то возможно объявление войны (как правило, если мужчин больше) или решение о молитве (в этом случае вероятность рождения мужчин при каждом скрещивании возрастает на некоторое время). Алгоритм был протестирован на примерах, требующих полного перебора точными методами. Оптимальное решение было найдено за небольшое количество итераций.



© 2004 Дизайн Лицея Информационных технологий №1533