Введение
Задача формирования оптимального расписания, пожалуй, может считаться наиболее важной для всех деловых людей. Правильно созданным начальником цеха графиком работ может определяться эффективность работы цеха и производственной организации в целом. Каждый человек, когда он планирует свой день или определенный временной промежуток, должен решить задачу расписания. Данную задачу при относительно небольшом промежутке времени, имеющемся опыте и незначительной погрешности, может решить один человек, но если речь идет о крупном производстве в рыночных условиях, то любая, даже незначительная погрешность может оказаться фатальной.
По этой причине, с развитием вычислительных технологий осуществляется проектирование автоматизированных систем формирования расписания. В отдельных случаях удавалось создавать алгоритмы, которые были способны находить решение за вполне приемлемое время. Однако так как практически все задачи выступают как многокритериальные и относятся к классу NP-полных, то задача формирования оптимального алгоритма может значительно усложниться.
Алгоритмы, созданные для различных общественных сфер, могут иметь много общего. К примеру, в задачах составления расписания занятий в вузах и графиков работы на промышленных предприятиях существует определенный набор аналогий между ресурсами:
- Наличие групп студентов и служащих.
- Наличие преподавателей и смен.
- Наличие аудиторий и квалификации служащих.
- Наличие предметов и работодателей.
Это означает, что методы, которые разработаны для одного подкласса задач, в некоторых случаях могут быть перенесены на другие классы задач.
Сравнение метода отжига и генетического алгоритма для задачи составления расписания обслуживания
Идею алгоритма имитации отжига специалисты позаимствовали из исследования поведения атомов металла при его отжиге. В металле, который был нагрет до температуры выше точки его плавления, атомы пребывают в состоянии хаотичного движения. Причем, как и в любых физических системах, они устремлены к состоянию минимальной энергии, то есть, к единому кристаллу, но при высоких температурах энергия атомных передвижений может препятствовать этому.
При постепенном охлаждении металла появляются все более низкоэнергетические состояния до тех пор, пока не будет достигнут глобальный минимум, то есть, самое низкое из возможных состояний. Если теперь перейти к математической модели, то следует определить, что в исследуемой задаче формирования расписания способно сыграть роль энергии и состояние какого из объектов подобная «энергия» способна охарактеризовать. Одним из вероятных вариантов является рассмотрение в качестве энергии целевой функции, которая основана на штрафах, прибавляемых к имеющемуся расписанию за все неудобные в нем моменты, а в качестве низкоэнергетического состояния использовать корректное, пока являющееся неизвестным, расписание.
Рассмотренный выше, а также некоторые другие методы, в своей основе применяют итерационную технологию улучшения итоговых результатов. В течение одной итерации ищется решение, которое является лучшим в окрестностях данного решения. Когда подобное решение находится, то оно определяется как текущее и далее должна начинаться новая итерация. Этот процесс должен продолжаться до тех пор, пока приращение целевой функции не сократиться фактически до нуля или не будет выполнено предписанное число итераций. Является очевидным тот факт, что подобные методики обладают ориентацией на обнаружение лишь локальных оптимумов, при этом положение вычисленного оптимума имеет зависимость от стартовой точки. Получается, что обнаружить наличие глобального оптимума можно лишь случайно. Для того чтобы повысить вероятность обнаружения глобального оптимума, можно использовать многократный эксперимент с разными стартовыми точками, что может значительно увеличить продолжительность поиска.
По этой причине представляет особый интерес создание алгоритмов, которые сохраняют все достоинства описанного метода и свободны от указанного недостатка. К числу таких алгоритмов следует отнести генетические алгоритмы. Генетическим алгоритмом является эвристический алгоритм поиска, который используется для решения задач оптимизации и моделирования методом случайного подбора, комбинирования и вариаций искомых параметров с применением различных механизмов.
Они базируются на генетических процессах биологических организмов, а именно, биологические популяции могут развиваться в период времени, равный жизни нескольких поколений. Это развитие подчиняется законам естественного отбора, где главенствует принцип «выживают самые приспособленные», который открыл Чарльз Дарвин. Если подражать данному процессу, то генетические алгоритмы могут оказаться способными «развивать» решения реальных задач, в случае, когда эти задачи будут необходимым образом закодированы.
К примеру, генетические алгоритмы можно использовать, для того чтобы выполнить проектирование структуры моста, для определения максимального соотношения прочности и веса, или находить наименее расточительное расположение для нарезки форм из ткани. Генетические алгоритмы также можно использовать для интерактивного управления процессом, к примеру, на химическом заводе, или балансировании загрузки на многопроцессорном компьютере.
Генетические алгоритмы представляют собой разновидность эволюционных вычислений. Главной отличительной особенностью генетического алгоритма является акцент на применение оператора «скрещивания», который выполняет операцию рекомбинации решений-кандидатов, роль которой является аналогичной роли скрещивания в живой природе.
