Введение
Одной из наиболее важных задач окружающей действительности является задача планирования расписания обслуживания, а также задача оптимального распределения ресурсов. Практически все такие задачи могут считаться NP-трудными, и алгоритмы, которые используются для их решения, выполненные программно на компьютерном оборудовании, часто могут потребовать чрезмерно большого времени работы, поскольку это задачи «большой размерности».
Сфера использования решений подобных задач является крайне обширной. Это может быть свой личный график работ отдельного человека, которые запланированы на определенный временной промежуток, а также могут быть и более сложные задачи, к примеру, такие как, формирование расписания движения самолетов или поездов. В каких задачах присутствует большое количество параметров, ограничений и критериев оптимальности.
А, например, при формировании расписания занятий в школе, завуч часто может использовать самодельную панель с ячейками для карточек, где каждая карточка обозначает занятие по определенному предмету, осуществляемое необходимым преподавателем. Всем ячейкам должен ставиться в соответствие определенный кабинет. Причем, для формирования расписания, применяется метод перебора и экспертной оценки, которая основана на опыте формирования расписаний в предыдущие периоды. Этот подход может потребовать значительных затрат времени и не способен дать гарантию какого-либо уровня качества, а оптимальность результата является трудно поддающейся оценке.
Сравнение метода поиска с ограничениями и генетического алгоритма для задачи составления расписания обслуживания
Задача формирования расписания может быть представлена как задача удовлетворения ограничений. Для того чтобы решать такие задачи, было создано много различных алгоритмов, к примеру, классический метод Гаусса, а также другие сложные методы, применяемые в системах доказательства теорем и в системах символьных вычислений. Появилось даже отдельное направление в программировании, названное программированием в ограничениях (constraint programming).
Программирование в ограничениях обладает тесными связями со стандартным логическим программированием, в границах которого оно и было сформировано. Практически все системы программирования в ограничениях являются обычными интерпретаторами Пролога, имеющими встроенный механизм для решения заданного класса задач удовлетворения ограничениям. Программирование в подобных системах именуется логическим программированием в ограничениях CLP (Constraint Logic Programming).
Идея решения задач заключается в том, что программист должен определить некоторое множество переменных x1, …, xn, а также и области их значений X1, …, Xn. Далее ему необходимо выполнить описание дополнительных ограничений, которым должны удовлетворять переменные, а система должна найти необходимые значения переменных, которые будут удовлетворять одновременно всем заданным ограничениям.
Итоговым результатом работы алгоритма должно стать множество значений всех переменных, которое не противоречит всем указанным ограничениям. Причем область определения переменных, которые участвуют в строгих ограничениях, может быть существенно сокращена или вовсе обладать единственным значением. Главным преимуществом, получаемым при применении CLP, является уменьшение пространства поиска, что достигается не путем оценки всех вариантов расписания, а за счет того, что система способна сама исключить из рассмотрения заведомо тупиковые варианты.
Генетические алгоритмы служат, для того чтобы решать задачи оптимизации. В качестве примера такой задачи можно привести обучение нейронной сети, то есть, выбора таких значений весов, при которых может быть достигнуто минимальное значение ошибки. Причем в основу генетического алгоритма заложен метод случайного поиска. Главным недостатком случайного поиска может считаться тот факт, что является неизвестным необходимое время для решения задачи. Для того чтобы исключить такие временные затраты при решении задачи, можно использовать методы, которые проявились в биологии. Причем могут использоваться методы, которые были открыты при исследовании эволюции и происхождения видов. Общеизвестно, что в процессе эволюции способны выжить только самые приспособленные особи. Это ведет к тому, что уровень приспособленности популяции увеличивается, что позволяет этой популяции выжить в изменяющихся условиях.
Впервые такой алгоритм предложил в 1975-ом году Джон Холланд (John Holland), ученый Мичиганского университета. Этот алгоритм был назван «репродуктивным планом Холланда» и стал основой фактически всех дальнейших вариантов генетических алгоритмов. Из биологии известно, что все организмы могут быть представлены своим фенотипом, фактически определяющим, чем будет считаться объект в реальном мире, а также и генотипом, содержащим всю совокупность информации об объекте на уровне хромосомного набора.
Причем любой ген, то есть, компонент информации генотипа, обладает своим отражением в фенотипе. Это значит, что для решения задач следует представить все признаки объекта в формате, который подходит для применения в генетическом алгоритме. Вся дальнейшая работа механизмов генетического алгоритма осуществляется на уровне генотипа, что позволяет обходиться без наличия информации о внутренней структуре объекта. Это обстоятельство и определяет самое широкое использование данного алгоритма в разнообразных задачах. В самой используемой разновидности генетического алгоритма, для того чтобы представить генотип объекта используются битовые строки. Причем всем атрибутам объекта в фенотипе должен соответствовать один ген в генотипе объекта.
