1626434812-e667f6b6e7e69d3a0798830a58e9075b (844135), страница 42
Текст из файла (страница 42)
Для поиска генетический алгоритм использует несколько точек поискового пространства одновременно, а не переходит от точки к точке, как это делается в традиционных методах. Это позволяет преодолеть один из их недостатков — опасность попадания в локальный экстремум целевой функции, если она не является унимодальной, то сеть имеет несколько таких экстремумов.
Использование нескольких точек одновременно значительно снижает такую возможность. Третье. Генетические алгоритмы в процессе работы не используют никакой дополнительной информации, что повышает скорость работы. Единственной используемой информацией может быть область допустимых значений параметров и целевой функции в произвольной точке. ги Базы оаннык. Интеллектуальная обработки информации Четвертое. Генетический алгоритм использует как вероятностные правила для порождения новых точек анализа, так и детерминированные правила для перехода от одних точек к другим. Выше уже говорилось, что одновременное использование элементов случайности и детерминированности дает значительно больший эффект, чем раздельное.
Прежде чем рассматривать непосредственно работу генетического алгоритма, введем ряд терминов, которые широко используются в данной области. Выше было показано, что генетический алгоритм работает с кодами безотносительно их смысловой интерпретации. Поэтому сам код и его структура описываются понятием генотип, а его интерпретация, с точки зрсния решаемой задачи. понятием фенотип. Каждый код представляет, по сути, точку пространства поиска. С целью максимально приблизиться к биологическим терминам, экземпляр кода называют хромосомой, особью или индивидуумом.
Далее для обозначения строки кода мы будем в основном использовать термин "особь". На каждом шаге работы генетический алгоритм использует несколько точек поиска одновременно Совокупность этих точек является набором особей, который называется популяцией. Количество особей в популяции называют размером популяции. Поскольку в данном параграфе мы рассматриваем классические гснстические алгоритмы, то можем сказать, что размер популяции является фиксированным и представляет одну из характеристик генетического алгоритма. На каждом шаге работы генетический алгоритм обновляет популяцшо путем создания новых особей и уничтожения старых.
Чтобы отличать популяции на каждом из шагов и сами эти шаги, их называют поколениями и обычно идентифицируют по номеру. Например, популяция, полученная из исходной популяции после первого шага работы алгоритма, будет первым поколением, после следующего шага — вторым, и т.д. В процессе работы алгоритма генерация новых особей происходит на основе моделирования процесса размножения. При этом, естественно, порождающие особи называются родителями, а порожденные — потомками. Родительская пара, как правило, порождает пару потомков.
Непосредственная генерация новых кодовых строк из двух выбранных происходит за счет работы оператора скрещивания, который также называют кроссинговером (от англ. сговво~ег). При порождении новой популяции оператор скрещивания может применяться нс ко всем парам родителей. Часть этих пар может переходить в популяцию следующего поколения непосредственно. Насколько часто будет возникать такая ситуация„зависит от значения вероятности применения оператора скрещивания, которая является одним из параметров генетического алгоритма.
Моделирование процесса мутации новых особей осуществляется за счет работы оператора мутации, Основным параметром оператора мутации также является вероятность мутации. Глава 8. Геиетичеекие алгоритмы Поскольку размер популяции фиксирован, то порождение потомков долж- но сопровождаться уничтожением других особей.
Выбор пар родителей из по- пуляции для порождения потомков производит оператор отбора, а выбор осо- бей для уничтожения — оператор редукции. Основным параметром их работы является, как правило, качество особи, которое определяется значением целе- вой функции в точке пространства поиска, описываемой этой особью. Таким образом, можно перечислить основные понятия и термины, исполь- зуемые в области генетических алгоритмов: ° генотип н фенотип, ° особь и качество особи, ° популяция и размер популяции, ° поколение, ° родители и потомки. К характеристикам генетического алгоритма относятся: ° размер популяции, ° оператор скрещивания и вероятность его использования, ° оператор мутации и вероятность мутации, ° оператор отбора, оператор редукции, ° критерий останова.
Операторы отбора, скрещивания, мутации и редукции называют еще гене- тическими операторами. Критерием останова работы генетического алгоритма может быть одно из трех событий: Сформировано заданное пользователем число поколений. ° Популяция достигла заданного пользователем качества (например, значение качества всех особей превысило заданный порог).
° Достигнут некоторый уровень сходимости. То есть особи в популяции стали настолько подобными, что дальнейшее их улучшение происходит чрезвычайно медленно. Характеристики генетического алгоритма выбираются таким образом, что- бы обеспечить малое время работы, с одной стороны, и поиск как можно луч- шего решения, с другой. Рассмотрим теперь непосредственно работу генетического алгоритма. Об- щая схема его работы представлена на рис. 8.1. Формирование исходной популяции происходит, как правило, с использо- ванием какого-либо случайного закона, на основе которого выбирается нужное количество точек поискового пространства.
Исходная популяция может также быть результатом работы какого-либо другого алгоритма оптимизации, Все здесь зависит от разработчика конкретного генетического алгоритма. Базы данных. Интеллектуальная обработка информации Создание исходной популяции Выбор родителей для процесса размножения (работает оператор отбора) Создание потомков выбранных пар родителей (работает оператор скрещивания) Мутация новых особей (работает оператор мутации) Расширение популяции за счет добавления новых, только что порожденных„особей Сокращение расширенной популяции до исходного размера ~работает оператор редукции) Нет Критерий останова работы алгоритма выполнен? Поиск лучшей достигнутой особи в конечной популяции- результата работы алгоритма Рис. 8.1. Процесс работы генетического тгоргнпма: Хлава 8. Геиетические алгоритмы В основе оператора отбора, который служит для выбора родительских пар и уничтожения особей, лежит принцип "выживает сильнейший".
В качестве примера можно привести следующий оператор. Выбор особи для размножения производится случайно. Вероятность участия особи в процессе размножсния вычисляется по формуле: (8.1) где и — размер популяции, 1 — номер особи, Р, — вероятность участия особи в процессе размножения, à — значение целевой функции для 1-й особи. Очевидно, что одна особь может быть задействована в нескольких родительских парах. Аналогично может быть решен вопрос уничтожения особей. Только вероятность уничтожения, соответственно, должна быть обратно пропорциональна качеству особей. Однако обычно происходит просто уничтожение особей с наихудшим качеством.
Таким образом, выбирая для размножения наиболее качественные особи и уничтожая наиболее слабые, генетический алгоритм постоянно улучшает популяцию, ведя к нахождению все лучших решений. Оператор скрещивания призван моделировать природный процесс наследования, то есть обеспечивать передачу свойств родителей потомкам. Опишем простейший оператор скрещивания. Он выполняется в два этапа. Пусть особь представляет собой строку из и элементов.
На первом этапе равновероятно выбирается натуральное число Е от 1 до и-1. Это число называется точкой разбиения. В соответствии с ним обе исходные строки разбиваются на две подстроки. На втором этапе строки обмениваются своими подстроками, лежащими после точки разбиения, то есть элементами с 1+1-го по и-й. Так получаются две новые строки, которые наследовали частично свойства обоих родителей. Этот процесс проиллюстрирован ниже. строка1 Х1Х2...Х1Хк+1...Хп Х1Х2...Х1Т1с+1...Ул + строка2 У1У2...УЕУ1+1...Уп У1У2...У1Х1с+1...Хп Вероятность применения оператора скрещивания обычно выбирается достаточно большой, в пределах от 0,9 до 1, чтобы обеспечить постоянное появление новых особей, расширяющих пространство поиска. При значении вероятности меньше 1 часто используют элитизм. Это особая стратегия, которая предполагает переход в популяцию следующего поколения элиты, то есть лучших особей текущей популяции, без всяких изменений. Применение элитизма способствует сохранению общего качества популяции на высоком уровне.
При этом элитные Базы данных. Интеллектуальная обработка информации особи участвуют еще и в процессе отбора родителей для последующего скрещивания, Количество элитных особей определяется обычно по формуле: К=(1-Р) ~ И, (8.2) где К вЂ” количество элитных особей, Р— вероятность применения оператора скрещивания, И вЂ” размер популяции. В случае использования элитизма все выбранные родительские пары подвергаются скрещиванию, несмотря на то, что вероятность применения оператора скрещивания меньше 1.
Это позволяет сохранять размер популяции постоянным. Оператор мутации служит для моделирования природного процесса мутации. Его применение в генетических алгоритмах обусловлено следующими соображениями. Исходная популяция, какой бы большой она ни была„охватывает ограниченную область пространства поиска. Оператор скрещивания, безусловно, расширяет эту область, но все же до определенной степени„ поскольку использует ограниченный набор значений, заданный исходной популяцией. Внесение случайных изменений в особи позволяет преодолеть это ограничение и иногда значительно сократить время поиска или улучшить качество результата.
Как правило, вероятность мутации, в отличие от вероятности скрещивания, выбирается достаточно малой. Сам процесс мутации заключается в замене одного из элементов строки на другое значение. Это может быть перестановка двух элементов в строке, замена элемента строки значением элемента из другой строки, в случае битовой строки может применяться инверсия одного из битов и т.д. В процессе работы алгоритма все указанные выше операторы применяются многократно и ведут к постепенному изменению исходной популяции. Поскольку операторы отбора, скрещивания, мутации и редукции по своей сути направлены на улучшение каждой отдельной особи, то результатом их работы является постепенное улучшение популяции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
