10. Понятие генетического алгоритма
Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационные методы, впервые предложенные Холландом (1975). Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином (1857).
ГА работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах.
Таким образом, из поколения в поколение хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи. Преимущество ГА состоит в том, что он находит близкие к оптимальным решения за относительно короткое время.
ГА состоит из следующих компонент:
Хромосома. Решение рассматриваемой проблемы. Состоит из генов и может быть представлена различными способами;
Начальная популяция хромосом – создаётся случайным образом;
Набор операторов (селекция, скрещивание, мутация) - для генерации новых решений из предыдущей популяции;
Целевая функция - для оценки приспособленности (fitness) решений.
11. Основные операции генетического алгоритма
Алгоритм работы ГА
Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не будут достигнуты заданное число поколений или какой-либо иной критерий останова (рис. 4). На каждом поколении ГА осуществляет отбор максимальной величины функции приспособленности, производит скрещивание выбранных хромосом и их мутацию.
Рис. 4. Схема работы классического ГА
Алгоритм работы ГА выглядит следующим образом:
НАЧАЛО /* классический генетический алгоритм */
Создать начальную популяцию
Оценить приспособленность каждой особи
останов = FALSE
ПОКА НЕ останов ВЫПОЛНЯТЬ
НАЧАЛО /* создать популяцию нового поколения */
ПОВТОРИТЬ (размер_популяции/2) РАЗ
НАЧАЛО /* цикл воспроизводства */
Выбрать две особи из предыдущего поколения с более высокой степенью приспособленности
Скрестить выбранные особи и получить два потомка
Оценить приспособленность потомков
Поместить выбранных потомков в новое поколение
КОНЕЦ
ЕСЛИ популяция сошлась, ТО останов = TRUE
КОНЕЦ
КОНЕЦ