Искусство в IT-технологиях...

Тавридович Станислав Александрович. Оптимизация WEB-сайта интернет-магазина с использованием генетического алгоритма, 2004

3.3.5.2. Реализация генетических алгоритмов на ЭВМ

Генетический алгоритм - это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются аналоги механизмов естественного отбора, генетического наследования и мутагенеза.
При этом сохраняется биологическая терминология в упрощенном виде.
Под особью (индивидуумом) понимается вариант решения задачи. Под популяцией - множество вариантов решения задачи. Каждая особь представлена в виде набора некоторого числа генов (битовых строк заданной длины) называемого хромосомой. Гены кодируют параметры решения задачи. Уникальные комбинации битов в хромосоме называются генотипом. При взаимодействии особи с внешней средой ее генотип порождает совокупность внешне наблюдаемых признаков (характеристик), включающих степень приспособленности особи к внешней среде и ее фенотип [см. 3, с. 16]. Степень приспособленности особи есть ни что иное, как значение целевой функции соответствующего варианта решения. Фенотип - это, упрощенно говоря, внешний вид особи. В некоторых задачах не делается различий между генотипом и фенотипом, в других между ними устанавливается однозначное соответствие [53, с. 169], в третьих - каждому генотипу может соответствовать целое множество фенотипов (что, вообще говоря, имеет место в природе), и фенотип может принимать случайные значения в зависимости от генотипа (например, фенотип может вырабатываться из генотипа специальным проблемно-ориентированным алгоритмом [43, сс 656-657]).
Блок-схема одной из возможных реализаций генетического алгоритма на ЭВМ представлена на рис. 18.
Алгоритм состоит из начального шага (шаг 1), последовательных итераций - поколений (шаги 2, 3, 4, 5 и условие остановки) и заключительного шага, на котором выдается ответ (шаг 6).
Шаг 1. Создание начальной популяции. На этом шаге происходит формирование начального множества особей. Основная задача данного шага: обеспечить как можно большее разнообразие генотипов особей - богатство генетического материала. Однако может ставиться и другая задача, в определенной степени противоречащая основной: создать начальную популяцию из относительно хорошо приспособленных особей1.
Шаг 2. Выбор родительских пар2. Существует много подходов к выбору родительских пар. Рассмотрим наиболее распространенные из них.
Самый простой подход - случайный выбор родительской пары (пан-миксия): обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, причем любая особь может стать членом нескольких пар3. Случайный выбор родительских пар прост, но он противо-




Этого можно добиться, решая некоторую вспомогательную оптимизационную подзадачу, дающую достаточно хорошее решение.
~ Некоторые алгоритмы выбирают более двух родителей для последующего скрещивания. Но, по аналогии с природой, часто используются два родителя.
* При написании раздела 3.3.5.2 использовалась статья Д.И. Батищсва и СЛ. Исаева «Оптимизация многоэкстремальных функций с помощью генетических алгоритмов». Статья находится по адресу hup //bspu.secna.ru/Docs/saisa/ga/summer97.htmL
Поэтому более логично использовать один из следующих подходов: пропорциональную или турнирную селекцию. При пропорциональной селекции вероятность выбора особи в родительскую пару пропорциональна ее приспособленности (значению целевой функции). При турнирной селекции формируется случайное подмножество из особей популяции и среди них выбирается особь с наибольшим значением целевой функции. Турнирная селекция имеет определенные преимущества перед пропорциональной, так как не теряет своей избирательности, когда в ходе эволюции все элементы популяции становятся примерно равными по значению целевой функции. И пропорциональная, и турнирная селекция строятся таким образом, чтобы с ненулевой вероятностью любая особь популяции могла быть выбрана в качестве одного из родителей. Более того, допускается ситуация, когда оба родителя представлены одной и той же особью популяции.
Хотелось бы обратить внимание и еще на два способа выбора родительской пары: инбридинг и аутбридинг. Эти методы построены на формировании родительской пары на основании близкого и дальнего «родства» соответственно. Мод «родством» понимается геометрическое расстояние между точками в пространстве, задаваемыми генотипами или фенотипами особей. В связи с этим различают генотипный и фенотипный инбридинг и аутбридинг. При инбридинге первый член родительской пары выбирается случайно, а вторым будет с большей вероятностью наиболее «родственная» ему особь. Аутбридинг же, наоборот, формирует пары из наиболее далеких в «родственном» отношении особей. Инбридинг и аутбридинг по-разному влияют на поведение генетического алгоритма. Так инбридинг можно охарактеризовать свойством концентрации поиска в локальных точках пространства решений, что фактически приводит к разбиению популяции на отдельные локальные группы вокруг подозрительных на экстремум точек. Аутбридинг же, напротив, направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя его просматривать новые неисследованные области.
Шаг 3. Скрещивание. К каждой из выбранных родительских пар применяется вероятностный оператор скрещивания. Существует много различных версий данного оператора, среди которых простейшим, видимо, является однородный оператор. Этот оператор моделирует процесс скрещивания в живой природе (см. гл. 3.3.5.1) в том смысле, что хромосома потомка (новой особи) формируется на основании хромосом родителей. При этом соответствующий ген каждого из родителей может попасть в хромосому потомка с вероятностью 0,5. На рис. 19 показан один из возможных результатов работы однородного оператора скрещивания. Хромосомы родителей и потомка состоят из четырех генов. При скрещивании потомок унаследовал от первого родителя гены 1 и 4, от второго - гены 2 и 3.

Рис. 19. Однородный оператор скрещивания
Хотя однородный оператор воспроизводит основную идею скрещивания, в результате которого потомок случайным образом приобретает гены обоих родителей, его процедура не имеет ничего общего с процессами скрещивания, происходящими в природе.
В этом отношении наиболее соответствующим действительности является так называемый одноточечный опера-тор скрещивания, при котором хромосомы родителей обмениваются не отдельными генами, а двумя участками хромосом относительно случайным образом выбранной точки. Одноточечный оператор скрещивания подробно описан в классической работе Дж. Холланда [49, с. 98]. Пусть хромосомы родителей содержат по МСл генов. Выбирается точка -V из множества
[1, MG -1] (выбор производится случайным образом). В результате скрещивания можно получить две новые хромосомы. Одна будет содержать гены первого родителя до гена с номером х включительно, а далее гены второго родителя, начиная с гена с номером х +1. Вторая хромосома получит гены второго родителя до гена с номером х, а далее гены первого родителя, начиная с гена с номером х +1. Далее можно случайным образом выбрать одну из хромосом.
Существуют и другие виды операторов скрещивания, например, многоточечный оператор^ при котором хромосомы обмениваются не двумя, а большим числом участков относительно некоторых случайно выбранных точек (в частности, при весьма распространенном двухточечном операторе происходит обмен тремя участками хромосом). О различных операторах скрещивания можно прочитать в [9, сс. 23-24].
В некоторых реализациях генетического алгоритма операция скрещивания применяется к каждой из выбранных родительских пар с заданной вероятностью - так называемой вероятностью кроссовера. Обычно она назначается на уровне 0,6 [47, с. 239]. Если родительская пара не подвергается скрещиванию, вместо потомка в следующее поколение переходит одна из родительских особей [50, с. 1064]. Это позволяет поддерживать численность популяции на постоянном уровне.
Хотя в природе в процессе скрещивания участвует только пара родительских особей, при работе генетического алгоритма возможно скрещивание более двух родителей. В потенциале в процессе скрещивания и передачи своей генетической информации потомку могут участвовать все особи популяции (так называемая глобальная рекомбинация [см. 51, с. 145]).
Шаг 4. Мутации новых особей. После скрещивания хромосома каждого из потомков подвергается мутации. Наиболее часто применяются точен-ные и генные мутации. При точечной мутации изменяются значения отдельных битов в генах, при генной - отдельных генов в хромосоме. Существуют и другие виды мутаций [см., например, 3, сс. 49-56].
При точечной мутации каждый бит в каждом из генов хромосомы может изменить свое значение на противоположное (с 0 на 1 и наоборот) с заданной вероятностью - вероятностью мутации. Обычно вероятность мутации достаточно мала и может составлять, например, около 0,005 (это означает, что только полпроцента генов в хромосоме изменяют свои значения в ре-
зультате мутации). При вероятности мутации 0,5 генетический алгоритм вырождается в алгоритм случайного поиска [46, с.
161].
При генной мутации каждый из генов хромосомы может изменить свое значение случайным образом с заданной вероятностью мутации. На рис. 20 изображен пример генной мутации. Гены 1, 2 и 4 после мутации остались неизменными, а ген 3 изменил свое значение с 3 на 6.

Шаг 5. Отбор новой популяции. На этом шаге производится формирование новой популяции из особей старой популяции и их потомков, после чего старая популяция погибает. Существует много способов отбора новой популяции. Рассмотрим некоторые из них.
Пропорциональный отбор основывается на вероятностном принципе. При этом виде отбора вероятность попадания особи в новую популяцию пропорциональна ее приспособленности (по аналогии с пропорциональной селекцией, см. выше).
При элитном отборе новая популяция строится из лучших, наиболее приспособленных особей старой популяции и их потомков. Элитный отбор характеризуется более быстрой сходимостью, чем пропорциональный, и это часто вменяют ему в недостаток.
И, наконец, последний метод - это отбор с вытеснением. Он носит бикритериальный характер: то, будет ли особь заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с аналогичным генотипом. Из всех особей с одинаковыми генотипами предпочтение отдается тем, чья приспособленность выше. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие. Вытеснение в данном случае формирует новую популяцию скорее из далеко расположенных особей, нежели из особей, группирующихся около текущего найденного решения.
Условие остановки. Как правило, генетический алгоритм продолжает свою работу до тех пор, пока либо не сгенерирует указанного пользователем числа поколений, либо популяция не достигнет заранее заданного качества решения, либо не будет достигнут некоторый уровень сходимости (т. е. такое состояние, когда все индивидуумы из популяции оказываются настолько подобными, что поиск становится чрезвычайно медленным) [10, с. 589]. Работа алгоритма может быть прекращена как автоматически - при выполнении заданного условия, так и вручную - оператором ЭВМ, следящим за работой алгоритма.
Шаг 6. Получение ответа. На этом шаге выбирается наиболее приспособленная особь - это и есть решение оптимизационной задачи.
Как мы видим, генетический алгоритм действительно комбинирует элементы переборного и локально-градиентного метода (см. гл. 3.3.4). Механизмы формирования начальной популяции, скрещивания и мутации реализуют переборную часть алгоритма, а выбор родительских пар и отбор новой популяции - градиентный спуск.
предыдущий следующий
= К содержанию =


3.3.5.2. Реализация генетических алгоритмов на ЭВМ - релевантная информация:

  1. Задачи исследования
    реализации адаптивных свойств корпоративного сайта, разработкой методики оптимизации информационной структуры сайта, созданием комплекса оценок эффективности сайта и интерактивных инструментальных средств для поддержки принятия решений и анализа информационной структуры корпоративного сайта с целью повышения его эффективности. Объектом исследований являются экономические системы корпоративного
  2. Обучение НС с использованием генетического алгоритма
    реализацией данного метода является алгоритм обратного распространения ошибки - ВРЕ (Back Propagation of Error) [2, 5,83,
  3. Выводы по главе 1
    реализации адаптивных свойств корпоративного сайта, разработка комплекса оценок для поддержки принятия решений и анализа эффективности информационной структуры корпоративного сайта, создание интерактивных инструментальных средств и алгоритма их применения для поддержки принятия решений и анализа информационной структуры корпоративного сайта с целью повышения его
  4. 2.4.3. Генетический алгоритм адаптации нейро-нечетких сетей в составе корпоративного сайта
    генетические алгоритмы часто применяются при решении практических задач [62, 92-94]. В задачах интеллектуального анализа данных первые два подхода используют для извлечения знаний из информации. В адаптивном сайте нейро-нечеткие классификаторы необходимы для извлечения знаний из входных векторов признаков посещения сайта и интересов (в процессе обучения НС), а генетические алгоритмы - для
  5. Выводы по главе 2
    реализации адаптивных свойств корпоративного сайта являются: 1) нечеткий логический вывод, который позволяет использовать опыт экспертов в виде системы классификационных правил логического вывода для предварительного обучения нейро-нечеткой сети; 2) способность нейронных и нейро-нечетких сетей к классификации и кластеризации; 3) способность информационного ноля нейронных и нейро-нечетких сетей к
  6. Тавридович Станислав Александрович. Оптимизация WEB-сайта интернет-магазина с использованием генетического алгоритма, 2004
    генетический
  7. Цель н задачи исследования.
    генетический алгоритм. В роли объекта исследования выступает Интернет-магазин. Предметом исследования являются модели, методы и алгоритмы для количественного обоснования принимаемых руководством Интернет-магазина
  8. Научная новизна исследования
    генетического алгоритма; изучено влияние различных параметров на работу генетического алгоритма при решении задачи оптимизации транспортной сети
  9. Выводы по второй главе
    реализацией заложенного в этом приеме алгоритма является создание инструментария (информационная система таргетинга по типу восприятия), делающего возможным описанный способ повышения эффективности рекламных сообщений.Еще раз отметим, что методика оценки эффективности рекламногоинтернет-сообщения является универсальной и может применяться дляулучшения любого показателя (в данном
  10. В предыдущих параграфах речь шла о том воздействии цвета на че-ловеческий организм и человеческую ментальность,
    реализации общественных связей и отношений как на уровне социальных структур и институтов, так и на уровне личности. Эти цветовые системы -часть современной цивилизованной жизни, ее наиболее яркая и эйфорическая составляющая компонента . Чувство цвета в культуре столь же исторично, как и человеческая чувственность вообще. Создание искусственной цветовой реальности шло от цветовых систем,