TechShape.ru

Информационные технологии

Основные разделы

Генетический алгоритм. Классическая задача комивояжа

Генетический алгоритм (ГА) способен осуществлять оптимальную настройку КНС при размерности поискового пространства достаточной для решения большинства практических задач. При этом спектр рассматриваемых приложений гораздо превосходит возможности алгоритма обратного распространения ошибки.

Обработка информации генетическим алгоритмом использует два основных механизма отбора полезных признаков, заимствованных из современных представлений о естественном отборе: мутации в отдельной цепочке и скрещивание (кроссинговер) между двумя цепочками. Рассмотрим эти механизмы подробнее (табл. 5).

Таблица 5: Мутации и скрещивание

001110101100001001 000110100001101001

а) Исходные генетические цепочки

0011101 .01100001001 .00001101001 0001101

б) Случайное образование области для последующего скрещивания

0011101 .00001101001 .01100001001 0001101

в) Обмен фрагментами кода

001110100001101001 000110101100001001

г) Цепочки после скрещивания

На рисунке представлены последовательные этапы обмена информацией между двумя цепочками при скрещивании. Полученные новые цепочки (или одна из них) могут быть в дальнейшем включены в популяцию, если задаваемый ими набор признаков дает лучшее значение целевой функции. В противном случае они будут отсеяны, а в популяции останутся их предки. Мутация в генетической цепочке носит точечный характер: в некоторой случайной точке цепочки один из кодов заменяется другим (ноль - единицей, а единица - нулем).

С точки зрения искусственных систем обработки информации генетический поиск представляет собой специфический метод нахождения решения задачи оптимизации. При этом такой итерационный поиск является адаптирующимся к особенностям целевой функции: рождающиеся в процессе скрещивания цепочки тестируют все более широкие области пространства признаков и преимущественно располагаются в области оптимума. Относительно редкие мутации препятствуют вырождению генофонда, что равносильно редкому, но не прекращающемуся поиску оптимума во всех остальных областях признакового пространства.

В последние десять лет разработано множество способов контролируемого обучения КНС с помощью ГА. Полученные результаты доказывают большие возможности такого симбиоза. Совместное использование КНС и ГА алгоритмов имеет и идеологическое преимущество потому, что они относятся к методам эволюционного моделирования и развиваются в рамках одной парадигмы заимствования техникой природных методов и механизмов как наиболее оптимальных.

Чтобы смоделировать эволюционный процесс, сгенерируем вначале случайную популяцию - несколько индивидуумов со случайным набором хромосом (числовых векторов). Генетический алгоритм имитирует эволюцию этой популяции как циклический процесс скрещивания индивидуумов и смены поколений (рис. 8.).

Рис. 8. Алгоритм вычислений

Рассмотрим достоинства и недостатки стандартных и генетических методов на примере классической задачи коммивояжера (TSP - travelling salesman problem). Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов).

Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.

Переборный метод наиболее прост по своей сути и тривиален в программировании. Для поиска оптимального решения (точки максимума целевой функции) требуется последовательно вычислить значения целевой функции во всех возможных точках, запоминая максимальное из них. Недостатком этого метода является большая вычислительная стоимость. В частности, в задаче коммивояжера потребуется просчитать длины более 1030 вариантов путей, что совершенно нереально. Однако, если перебор всех вариантов за разумное время возможен, то можно быть абсолютно уверенным в том, что найденное решение действительно оптимально (рис. 9.).

Перейти на страницу: 1 2

Еще статьи

Исследование активного RC-фильтра
1. Найти операторную передаточную функцию фильтра, составив и решив систему узловых уравнений. 2. Получить выражения для АЧХ и ФЧХ фильтра, построить их графики и указать тип фильтра (ФНЧ, ФВЧ, ПФ). . Найти переходную характеристику первого звена фильтра и пос ...

Все права защищены! 2020 - www.techshape.ru