Для решения заявленного класса задач предлагается генетический алгоритм, сочетающий в себе специальные процедуры и операторы, в основе которых лежат эвристические подходы по построению и оптимизации структуры допустимых решений исходной задачи. Такого рода алгоритм в дальнейшем будем называть гибридным алгоритмом. На рисунке 1 приведена общая схема гибридного алгоритма.
Таким образом, в структуре гибридного алгоритма, по аналогии с генетическим алгоритмом, можно выделить четыре группы операторов: оператор формирования начальной совокупности решений, группа операторов по воспроизводству новых решений, группа операторов по оценке качества найденных решений и оператор отбора решений. Кроме того, гибридная методика допускает включение в состав алгоритма различного рода специальные операторы, такие например, как: оператор прижизненной адаптации, который осуществляет оптимизацию структуры новых построенных решений с целью отстранения от поиска областей с заведомо низким качественным уровнем; оператор генетического всплеска, который осуществляет контроль за эффективностью поиска, и принимает решение о замене части популяции новыми решениями, которые формируются либо случайным образом, либо на основе некоторого конструктивного подхода; оператор коррекции генотипов, осуществляющий такое исправление структуры недопустимых решений, которое позволяет осуществлять поиск исключительно в области допустимых решений исходной задачи.
|
|
Общая схема гибридного алгоритма при прямом представлении |
Рисунок 1 |
Гибридный алгоритм имеет массу разнообразных настроек и параметров. Например, схемы формирования начальной популяции, скрещивания, отбора, алгоритмы размножения и мутации, размер популяции, число брачных пар, вероятность мутации и т.д. От настроек параметров алгоритма во многом будет зависеть и его качество работы. Реализация механизма автоматического подбора режима работы осуществлена стохастическими автоматами, которые подстраивают в процессе поиска отдельные параметры алгоритма.