Бионический поиск решения задач транспортного типа на основе стратегии адаптации

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

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

Информатика, вычислительная техника и управление

адаптивность, способность к обучению, параллелизм, возможность построения гибридных систем на основе комбинирования.

Основная часть. Задачи об экстремальном пути представляют собой актуальное направление исследований в области информационных технологий, теории и практики систем искусственного интеллекта, теоретических основ информатики. Применение классических методов и алгоритмов решения данных задач с экспоненциальной временной сложностью становится неэффективным из -за сложности преодоления локальных оптимумов, большой размерности задачи, помимо того, эвристические методы, большей частью, не адаптированы к параллельным вычислительным системам [1 -3].

Одним из направлений, позволяющим решить вышеуказанные задачи является разработка алгоритмов последовательного и параллельного бионического поиска, базирующегося на методах эволюционного моделирования [4, 5].

При решении задач об экстремальном пути использован эволюционно -оптимизационный подход к моделированию алгоритмов бионического поиска (БП) [6]. Необходимым условием эффективной работы БП является автоматизированная адаптивная настройка алгоритмов [7, 8]. В качестве начальной популяции используется не одно, а несколько альтернативных решений, причем исходные решения могут быть получены на основе детерминированных алгоритмов. Взаимодействие БП и детерминированных алгоритмов позволяет проводить адаптацию наборов параметров и фокусировать наилучшее решение.

При выполнении бионического поиска нахождении экстремального пути, предлагается выполнить микро-, макро - и метаэволюции [9]. При этом, используя метаэволюцию, создается не одна, а некоторое множество популяций. Поиск решений осуществляется путем объединения хромосом в различных популяциях. На эффективность БП в смысле повышения скорости сходимости алгоритма и процента нахождения глобального или близкого к нему решения влияют методы кодирования потенциальных решений и выбранные параметры популяции.

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

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

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

Nt + 1)- N^+N^-KI ) * z^ I qN ,       1, f ( _t )> f ( _{t +} 1)            u , q ( t ) ₌ q ( t -1)

z ( t )                                  , q\ t )                                ,

1- p\xk )* Rp )                 1-1, F ( t )> F ( t + 1) N^NV) [u 1, q ( t )# q ( t -1)

где KI — количество элитных особей; Rp — размер популяции; N ( t ) — размер популяции в поколении t ; Uk — k -й член последовательности решета Эратосфена [11]; q ( t ) — направление изменения (увеличение или уменьшение) размера популяции в поколении t ; F(t) — значение целевой функции в популяции; k — количество поколений, в течение которых направление q изменения размера популяции остается постоянным.

При дальнейшей реализации алгоритма лучшие и отобранные элементы из родителей и потомков будут выбираться для формирования новой популяции [12].

Определяющими эволюцию, служат модифицированные операторы мутации, реализующиеся под действием естественного отбора, на основе методов «двойного решета» и дихотомии [13, 14]. Предложенные модифицированные генетические операторы, ориентированны на создание алгоритмов бионического поиска, для решения задач об экстремальных путях, увеличивают вероятность «выживания» альтернативных решений с лучшим значением ЦФ на 10%-15%.

Блок адаптации предназначен для выбора и реализации различных стратегий и механизмов адаптации. Еще одно предназначение данного блока состоит в настройке и изменении порядка использования и применения различных генетических операторов и схем поиска. Результаты работы блока адаптации оказывают непосредственное влияние на процесс перестройки текущей популяции альтернативных решений и создания, на ее основе, новой популяции. По сравнению с классической схемой бионического поиска, в предлагаемом бионическом алгоритме добавлен блок анализа неперспективных решений (сортировки и сохранение особей в файл). Данный блок собирает и анализирует решения, получаемые в процессе выполнения алгоритма.

Каждому решению (индивиду) в результате проведенного анализа присваивается определённый ранг (перспективное, неперспективное, тривиальное и др.). При этом принимаются во внимание задаваемые на входе алгоритма ограничения области поиска. Проводимое, в рассматриваемом блоке, ранжирование текущей популяции альтернативных решений позволяет повысить эффективность бионического поиска за счет большей структурированности множества альтернативных решений, и дает возможность динамического регулирования направления поиска. Для накопления статистики работы алгоритма о развитии популяции предусмотрен механизм сохранения в файл перспективных и неперспективных особей [15]. Эта информация может быть использована при повторном решении задачи для изменения её параметров или алгоритма, что и выполняется в блоке анализа полученных решений

Рис. 1. Модифицированная базисная структура оптимизационного процесса

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

Информатика, вычислительная техника и управление

n

t ²Q²

А2,

где n — количество хромосом для обмена; А — предельная ошибка выборки; ст — среднеквадратичное отклонение;

t — коэффициент, определяемый по таблице Лапласа, Ф( t )= р, где р — заданная вероятность, определяемая ЛПР [16]. gy

Заключение . Преимущество разработанной модифицированной базисной структуры оптимизационного процесса состоит в том, что все строительные блоки связаны с блоком адаптации . На основе построенного бионического поиска разработан комплекс программ, реализующий предложенные бионические алгоритмы для решения задач об экстремальном пути. Данный алгоритм позволяет улучшить качество получаемых решений (для рассмотренных тестовых примеров достигается улучшение точности вычисления целевой функции на 20% по сравнению с алгоритмами Дейксры и Белмана) и сократить время работы (на 15% по сравнению с теми же алгоритмами). Такие результаты достигаются за счет внедрения системы управления процессом поиска квазиоптимальных решений, а также с помощью настройки и варьирования параметров предлагаемых алгоритмов, применения параллельных вычислений и механизма синхронизации полученных решений на всех этапах поиска. Предложенные алгоритмы позволяют сократить область поиска допустимых решений на 15%–20% и получить оптимальные результаты за приемлемое время.