научная статья по теме КВАНТОВЫЕ И ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ - НОВАЯ ТЕХНОЛОГИЯ ЭВОЛЮЦИОННОГО ПОИСКА Общие и комплексные проблемы естественных и точных наук

Текст научной статьи на тему «КВАНТОВЫЕ И ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ - НОВАЯ ТЕХНОЛОГИЯ ЭВОЛЮЦИОННОГО ПОИСКА»

ВЕСТНИК ЮЖНОГО НАУЧНОГО ЦЕНТРА РАН Том I, №2, 2005, стр. 41-50

ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

УДК 628.3 + 621.3

КВАНТОВЫЕ И ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ -НОВАЯ ТЕХНОЛОГИЯ ЭВОЛЮЦИОННОГО ПОИСКА

© 2005 г. В.М. Курейчик

Рассматривается новая технология решения оптимизационных и комбинаторно-логических задач на графовых моделях на основе композитных (интегрированных квантовых и генетических) алгоритмов. Это позволяет получать наборы локально-оптимальных решений и строить эвристические алгоритмы с полиномиальной скоростью роста количества операций в зависимости от объема входных данных.

При решении оптимизационных и комбинатор-но-логических задач проектирования, конструирования и искусственного интеллекта на основе графовых моделей эффективно используются стратегии, концепции, методы, механизмы эволюционного моделирования и бионического поиска [1-6]. Бионический поиск с точки зрения преобразования информации при решении задач на графах - это последовательное преобразование одного конечного нечеткого множества альтернативных решений в другое. Само преобразование называется алгоритмом поиска, или генетическим алгоритмом (ГА). В основе ГА лежит случайный, направленный или комбинированный поиск. Такие алгоритмы эффективно используют информацию, накопленную в процессе эволюции, для получения квазиоптимальных и оптимальных решений [4, 5]. Использование идей квантовой механики позволяет при поиске решений в задачах на графах использовать подходы параллельных вычислений. Согласно известному принципу суперпозиции, система (графовая модель) может как бы одновременно находиться во всех возможных состояниях. Производя над одним состоянием графа произвольные действия, мы производим это одновременно над заданным множеством состояний [7-10]. При решении оптимизационных задач на графах предлагается новая технология на основе совместного бионического и квантового поиска. Описаны новые архитектуры и принципы такого поиска. Это позволяет расширить область поиска решений без увеличения времени работы и сократить преждевременную сходимость алгоритмов, повысить эффективность и качество получаемых решений.

КВАНТОВЫЕ АЛГОРИТМЫ

В последнее время появились новые подходы решения ^-полных проблем, основанные на методах квантового поиска [7-10]. Квантовый поиск анализирует неструктурированные проблемы, которые в общем виде формулируются следующим образом [7]. Задана функция Дх), аргументы х - целые числа д: = 1, 2, ^ причем Дх) принимает значение ноль во всех случаях, кроме х = ж. Необходимо найти значение и\ используя наименьшее число запросов кДх). Задачи такого типа при небольшом х < 100 решаются на основе полного перебора (исчерпывающего поиска) или методом проб и ошибок.

Идею и структуру квантового алгоритма предложил Л. Гровер [7, 8]. Согласно [8], при решении неструктурированной проблемы поиска существует "оракул", определяющий, является ли рассматриваемое решение искомым. Л. Гровер рассматривает N целых чисел индекса х = 1, 2, ..., N как набор ортогональных векторов

х = 1,2, ...,к в М-размерном пространстве Хиль-

берта. Этот шаг алгоритма как бы на языке вычисления кванта ставит в соответствие каждому возможному индексу уникальный собственный вектор. Первоначально готовится пространство

1 N s = — X*,

1 Таганрогский государственный радиотехнический университет, г. Таганрог.

4Ñ х%

т.е. как бы квантовый регистр памяти, содержащий определенное количество суперпозиций, равное количеству всех N [7, 8].

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

между стартовым пространством s и целевым

t, то есть t J U | S Ф 0, тогда можно использовать

унитарную процедуру U для выполнения классического поиска цели. Л. Гровер предлагает использовать U иД*), чтобы построить увеличивающий амплитуду оператор Q, который изменяет амплитуду вероятности от не-цели векторов

в цель S~t [7]. Поведение "оракула" в

алгоритме квантового поиска моделируется возвратной функцией/(х) = 0, для всех д:, w и f(x) = 1, для X = W.

Для решения NP-полных проблем на графах предлагается анализировать структуру графа, чтобы "выращивать" полные решения, рекурсивно расширяя последовательные частичные решения.

Приведем модифицированный алгоритм квантового поиска [11-13].

1. Начало.

2. Ввод исходных данных.

3. Проверка условий существования инвариантных частей в графе.

4. Анализ математической модели и на его основе построение дерева частичных решений.

5. Суперпозиция частичных решений на основе жадной стратегии и квантового поиска.

6. В случае наличия тупиковых решений - последовательный поиск с пошаговым возвращением.

7. Если набор полных решений построен, то переход к 7, если нет, то к 5.

8. Лексикографический перебор полных решений и выбор из него оптимального или квазиоптимального решения.

9. Конец работы алгоритма.

Приведем укрупненный код алгоритма квантового поиска оптимальных решений в графе на Паскале. Алгоритм

begin {основная программа} generation: = 0 {установка} initialize;

repeat {основной цикл} gen: = gen + 1 generation; cycle; return;

statistics (max, avg, min, sumfitness, newsol) report (gen) oldsol: = newsol until (gen ^ maxgen) end {конец основной программы}. Здесь generation (gen) - генерации (итерации) алгоритма; max, avg, min, sumfitness - максимальное, среднее, минимальное, суммарное значение целевой функции; oldsol, newsol - старое и новое решение соответственно. Алгоритм квантового поиска (1 итерация выполняется в блоке repeat).

Работа алгоритма начинается с чтения данных, инициализации случайных решений, вычисления статистических данных и их печати. Процедура report представляет полный отчет обо всех параметрах алгоритма. На основе анализа данных из процедуры report строится график зависимости значений целевой функции от числа генераций. Если функция имеет несколько локальных оптимумов, и мы попали в один из них, то увеличение числа генераций может не привести к улучшению значений целевой функции. В этом случае наступила предварительная сходимость алгоритма. Операция return предусматривает пошаговый возврат до выхода из тупика. Алгоритмы квантового поиска весьма чувствительны к изменениям и перестановкам входных параметров исходной модели. Это говорит о том, что, например, для одного вида модели объекта, представленного матрицей, можно получить решение с одним локальным оптимумом. А для этой же матрицы с переставленными строками и столбцами можно получить другое решение с лучшим локальным оптимумом. Следует отметить, что, изменяя параметры, алгоритмы и схему квантового поиска, в некоторых случаях можно выходить из локальных оптимумов. Эта проблема продолжает оставаться одной из важнейших во всех методах оптимизации.

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

Генетические алгоритмы отличаются от других оптимизационных и поисковых методов и алгоритмов [1-3]:

- анализируют и преобразуют закодированное множество исходных параметров;

- осуществляют поиск из части популяции или множества популяций (множества альтернативных решений), а не из одного решения;

- используют целевую функцию (функцию пригодности или приспособленности), а не ее различные приращения для оценки качества альтернативных решений;

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

В ГА предварительно анализируется множество входных параметров оптимизационной задачи и находится некоторое множество альтернативных решений, которое называется популяцией. Каждое решение кодируется как последовательность конечной длины в некотором алфавите. ГА работает до тех пор, пока не будет получено решение заданного качества или будет выполнено заданное количество генераций, или на некоторой генерации возникает преждевременная сходимость, когда найден локальный оптимум. Процесс эволюции основан на анализе начальной популяции и ГА начинает свою работу с создания исходного множества альтернативных решений. Затем эти "родительские" решения создают "потомков" путем случайных, направленных или комбинированных преобразований. После этого оценивается эффективность каждого альтернативного решения, и они подвергаются селекции. Во всех моделях эволюции используется принцип "выживания сильнейших", т.е. наименее приспособленные решения устраняются, а лучшие решения переходят в следующую генерацию. Затем процесс повторяется вновь [2-6].

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

ГА = (jf, N, Р*к, Т, LJfA, (ЦФ, ОГР, ГУ), ГО, г),

где Р° - исходная популяция хромосом альтернативных решений, Pió = (Piol, Pio2, ..., Pion), Piol g Pio - хромосома (альтернативное решение), принадлежащее i-й исходной популяции; N - мощность популяции, т.е. число входящих в нее хромосом, N = I PiT I; PiTk е PiT - к-я хромосома, принадлежащая i-й популяции, находящейся в Г поколении эволюции; Т = О,1,2,...- номер поколения, проходящего популяцией во время эволюции, иногда число поколений связывают с числом генераций генетического алгоритма, обозначаемых буквой G; Lj- длина г-й хромосомы (альтернативного решения), т.е. число генов (элементов, входящих в закодированное решение, представленное в заданном алфавите), например, I PiT I = Lj; А - произвольный абстрактный алфавит, в котором кодируются хромосомы, например, Al = (0, 1}, А2 = {0, 1, 2, ..., 10}, A3 = {0, 1, 2, *}, А4= {А, В, С, D}, здесь *- метка, означающая любой символ в алфавите А2;

(ЦФ, ОГР, ГУ) - целевая функция, ограничения и граничные условия, которые определяются на основе заданной модели исходной решаемой задачи; ГО - генетические операторы, г - критерий окончания работы ГА.

Рассмотрим возможные случаи окончания работы ГА. Если значение глобального оптимума ЦФ известно, то условием окончания работы ГА можно считать нахождение значения ЦФ, превышающей глобальное значение на заданную величину £

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком