авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13)

Раздел I. Эволюционное моделирование, генетические

и бионические алгоритмы

УДК

621.372

В.В. Курейчик, Вл.Вл. Курейчик

ОБЗОР И АНАЛИЗ МЕТОДОВ И МОДЕЛЕЙ, ИНСПИРИРОВАННЫХ

ПРИРОДНЫМИ СИСТЕМАМИ

В статье рассматриваются модели и методы, инспирированные природ-

ными системами. Проведен анализ и обзор основных моделей эволюции. Пред-

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

Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов проектирования на основе методов, инспирированных природными системами и их поведение для схем различной структуры. В лучшем случае временная сложность алгоритмов O(nlogn), в худшем случае - О(n3).

Эволюционный, генетический, квантовый, муравьиный и пчелиный поиск, методы и модели, инспирированные природными системами.

V.V. Kureichik, Vl. Vl. Kureichik OVERVIEW AND ANALYSIS OF METHODS AND MODELS INSPIRED BY NATURAL SYSTEMS This paper describes a method of encoding – decoding solutions for the problem of component placement VLSI evolutionary computation methods have been studies to determine the effectiveness of the proposed method of coding solutions and select the cut points for the modified genetic operators. The results allow to conclude that the proposed method is more efficient encoding of the classical approach of 6-9%.

Accommodation;

genetic algorithm;

bee algorithm, coding, decoding, software implementation.

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

Отметим, что наилучшего решения во всех смыслах быть не может. Оно мо жет быть признано оптимальным на основе критерия или целевой функции (ЦФ).

Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) Часть задач оптимизации относится к классу комбинаторных и, в большин стве случаев, имеют не одно, а множество решений различного качества. Ядром всех комбинаторных алгоритмов являются операции полного или сокращенного перебора подмножеств решений. Для поиска лучшего решения, как правило, осу ществляются направленный, случайный и комбинированный поиск всевозможных значений параметров задачи. До последнего времени не существовало эффектив ного механизма поиска решений на множестве альтернатив, что затрудняло полу чение качественных результатов за приемлемое время. Рассмотрим методы и мо дели, инспирированные природными системами более подробно.

Эволюционные модели. Под эволюцией понимаются медленные, постепен ные, количественные и качественные изменения объекта. При этом каждое новое состояние объекта, как правило, имеет по сравнению с предыдущим более высокий уровень развития и организации. Таким образом, существует взаимосвязь между определением эволюции и оптимизационными алгоритмами.

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

Для описания концепций популяционной генетики Ф. Хедрик предложил ис пользовать различные эволюционные модели [24].

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

Модель эволюции Ж. Ламарка. Она основана на предположении, что харак теристики, приобретенные особью (организмом) в течение жизни, наследуются его потомками. Эти изменения, как утверждал Ж. Ламарк, вызываются прямым влия нием внешней среды, упражнением органов и наследованием приобретенных при жизни признаков.

Модель эволюции Г. де Фриза. В ее основе лежит моделирование социаль ных и географических катастроф, приводящих к резкому изменению видов и попу ляций. Эволюция, таким образом, представляет собой последовательность скачков в развитии популяции. Такой механизм эволюции иногда называют эволюцией катастроф. Он проявляется один раз ориентировочно в несколько тысяч поколений.

Основная идея его состоит во внесении глобальных изменений в генофонд на мо мент катастрофы.

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



М. Кимура предложил модель нейтральной эволюции с нейтральным отбо ром. По его теории на генетическую изменчивость исходно влияют мутации. Тео рия нейтральности предполагает, что большая часть молекулярных вариантов име ет равную приспособленность друг относительно друга. Изменчивость здесь под держивается балансирующим отбором. Рассматриваемый процесс всегда сходится Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) к одному из поглощающих состояний. При большом размере популяции N характерное число поколений TN, требуемое для сходимости к какому либо из по глощающих состояний, равно 2N. Данный эволюционный процесс чисто нейтраль ный, в результате эволюции выбирается только один вид.

Модель эволюции Шмальгаузена. Шмальгаузен попытался представить эво люцию Дарвина в терминах теории управления и кибернетики. Он выделил объ ект, в котором по каналам прямой и обратной связи передаются от материнской популяции к дочерней сигналы управления. Следуя Шмальгаузену, эволюция это авторегулируемый процесс, основанный на обратной связи. На ее основе происхо дит анализ микроэволюции. Она рассматривает процессы, протекающие на уровне популяций, начиная с механизмов изменчивости. Далее рассматривается наслед ственная изменчивость до возникновения нового вида. В своей схеме Шмальгаузен выделил два основных блока: управляющий (регулятор) и регулируемый. Управ ляющим блоком в эволюции Шмальгаузена (ЭШ) является внешняя среда. Регули руемый блок в ЭШ это элементарная единица эволюции, т.е. популяция. К услови ям внешней среды эта популяция и приспосабливается, т.е. адаптируется.

Модель синтетической эволюции, описанная Н. Дубининым, представляет ин теграцию различных моделей эволюций, в том числе Ч. Дарвина, Ж. Ламарка, Г.

де Фриза, Шмальгаузена. Для эффективного решения оптимизационных задач необходимо объединение всех видов и моделей эволюций. На рис. 1 приведем условную упрощенную интегрированную архитектуру поиска [35]. Отметим, что блоки 1-n соответствуют схемам моделей эволюций Ч. Дарвина, Ж. Ламарка, Г. де Фриза, К. Поппера М. Кимуры и Шмальгаузена соответственно.

Внешняя Популяция среда Шкала эволюции Адаптация (выбор модели) n 1 Блок миграции Поиск (выбор метода) Рис. 1. Упрощенная интегрированная архитектура поиска Основным этапом в каждой модели эволюции является анализ популяции, ее преобразование тем или иным способом и эволюционная смена форм [3, 4]. На основе этой архитектуры можно производить распараллеливание процесса поиска.

Архитектура (рис. 1) при наличии большого количества вычислительных ресурсов может быть доведена до N блоков. Причем, N 1 блоков могут параллельно осу ществлять эволюционную адаптацию и через блок миграции обмениваться лучши ми представителями решений. Последний блок собирает лучшие решения, может Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) окончить результат работы или продолжить поиск на основе различных методов, инспирированных природными системами [6].





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

Генетические методы. В конце 1960-х годов американский исследователь Джон Холланд в качестве принципов комбинаторного перебора вариантов решения оптимизационных задач предложил использовать методы и модели механизма развития органического мира на Земле. Поскольку основные законы эволюции жи вых организмов были исследованы генетикой, то и предложенный механизм полу чил название генетические методы (ГМ) [3, 7, 8].

Основой для возникновения ГМ послужили модель биологической эволюции и методы случайного поиска. Л. Растригин отмечал, что случайный поиск возник как реализация простейшей модели эволюции, когда случайные мутации модели ровались случайными шагами оптимального решения, а отбор – «устранением»

неудачных вариантов [9].

Впервые ГМ были применены к таким научным проблемам, как распознава ние образов и оптимизация [8].

Генетический поиск с точки зрения преобразования информации – это после довательное преобразование одного конечного нечеткого множества промежуточ ных решений в другое. ГМ – это не просто случайный поиск. Эти методы эффек тивно используют информацию, накопленную в процессе эволюции.

Цель ГМ состоит в том, чтобы:

абстрактно и формально объяснить адаптацию процессов в естественных и искусственных системах;

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

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

ГМ отличаются от других оптимизационных и поисковых процедур следую щим:

работают в основном не с параметрами задачи, а с закодированным множе ством параметров;

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

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

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

Для работы ГМ выбирают множество натуральных параметров оптимизаци онной проблемы и кодируют их в последовательность конечной длины в некотором алфавите. Они работают до тех пор, пока не будет выполнено заданное число гене раций (итераций алгоритма) или на некоторой генерации будет получено решение определенного качества, или, когда найден локальный оптимум, то есть возникла Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) преждевременная сходимость и алгоритм не может найти выход из этого состоя ния. В отличие от других методов оптимизации эти методы, как правило, анализи руют различные области пространства решений одновременно и поэтому они более приспособлены к нахождению новых областей с лучшими значениями ЦФ.

Модели роевого интеллекта. Моделирование самоорганизации обществен ных насекомых составляет основу роевых методов. Рой рассматривается как мно гоагентная система, в которой каждый агент функционирует автономно по доволь но примитивным правилам. В противовес почти примитивному поведению аген тов, поведение всей системы получается на удивление разумным [2, 10, 11].

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

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

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

Формализованная модель роя включает следующую систему отношений, ими тирующих эволюцию исследуемого объекта:

создается исходная «случайная» популяция частиц;

рассчитывается целевая функция для каждой частицы;

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

устремляются к этому центру. Чем дальше частица находится от центра, тем большим ускорением она обладает;

рассчитываются новые координаты частиц в пространстве решений;

три предыдущих шага итерационно повторяются заданное число раз;

последний «центр тяжести» соответствует найденному локальному оптимуму.

Рой не знает, где именно находится цель, но на каждой итерации рой знает, как далеко она находится. Эффективной стратегией будет следование за особью, которая на данный момент находится к цели ближе всего.

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

Модель муравьиной колонии. Модель муравьиной колонии, по аналогии с биологической моделью, базируется на непрямом обмене информацией колонии агентов, называемых искусственными муравьями, использующих феромонные следы как коммуникационное средство. Феромонные следы служат распределен ной численной информацией. Она наряду с эвристической информацией о задаче Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) используется муравьями для недетерминированного конструирования решений задачи и отражает опыт, накопленный муравьями в процессе поиска решения [6, 11, 12].

При подобном представлении задачи каждый муравей колонии имеет следу ющие свойства:

он использует граф G = (Х, U) для поиска оптимального решения, передвига ясь по соединениям из U;

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

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

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

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

муравей может обновить феромонный след на компоненте или соответствую щем соединении;

найдя решение, муравей может пройти этот же путь назад и обновить феро монный след на использованных соединениях или компонентах.

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

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

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

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

Модель роя пчел. В моделях поведения пчел и пчелиного роя происходит моделирование поведения пчл в живой природе. Основной идеей положенной в основу функционирования модели является совместное исследование перспектив ных областей пространства допустимых решений и их окрестностей, что позволяет разнообразить популяцию решений на последующих итерациях и увеличивает ве Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) роятность обнаружения близких к оптимальным решений [6, 11, 13, 14]. При этом не стоит задача смоделировать жизнь пчл, создать точную копию существующей природной экосистемы. В данном случае имитация некоторых аспектов жизнедея тельности колонии интересует нас исключительно как механизм поиска и оптими зации решений.

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

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

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

Например, также как в живой природе организация пчелиного улья основывается на чтком распределении обязанностей между отдельными его индивидами. Всех пчл в улье можно разделить на 3 группы: рабочие пчлы;

пчлы-исследователи;

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

Модель отжига. В 1953 г. Метрополис Н. с соавторами предложили вычис лительную процедуру, воспроизводящую механизм отжига металлов, для эффек тивного моделирования состояния равновесия сложных систем при заданной ко нечной температуре [6, 14, 15].

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

Обозначим через S множество состояний системы, через Т температуру си стемы при термическом равновесии. Тогда рТ(а) является вероятностью того, что система при температуре Т находится в состоянии а, независимо от энергетическо го уровня Еа этого состояния. Согласно распределению Больцмана:

Ea pT (a) exp( ), Eb k T ( ) bS k T где k является константой Больцмана.

Предположим, что система находится в момент времени t в состоянии a с энергетическим уровнем Еа. Путем небольшого случайного изменения в момент времени t+1 система переходит в состояние b с энергетическим уровнем Еb. Если разница E=Eb—Ea 0, то актуальным становится состояние b;

если E 0, то состояние b запоминается и выбирается с вероятностью exp((Ea–Eb)/(kT)). При до Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) статочно большом t данное правило обеспечивает переход системы в состояние равновесия. Эта процедура переносится на задачу параметрической оптимизации.

При этом состояния физической системы заменяются конфигурацией системы (в задаче параметрической оптимизации схем РЭА – вектор внутренних параметров), а изменение t заменяется обобщенным понятием температуры Т, которая может рассматриваться как управляющий параметр оптимизационной процедуры и во время проведения оптимизации изменяется по некоторому правилу. Аналогия с физическим процессом здесь заключается в следующем:

решения оптимизационной задачи соответствуют состояниям системы в про цессе охлаждения физической субстанции;

целевая функция F соответствует энергетическому уровню субстанции;

процедура поиска оптимального решения аналогична поиску состояния систе мы с минимальным энергетическим уровнем;

температура T является параметром для управления процедурой оптимизации.

Формализованная модель отжига включает в себя следующие элементы [14]:

выбирается начальная температура Т00;

устанавливается начальное число итераций I0;

t:=0;

выбирается начальное решение х;

вычисляется F(x);

for i=1 to It;

begin;

выполняется копирование (репликация) х;

переход в соседнюю точку х путем мутации (вариации) копии х;

вычисляется F(x);

если E=F(x)—F(x)0, то замена x на x. Иначе, если exp(E/Tt) rnd(0,1), то х запоминается и выбирается с вероятностью exp(E/Tt);

end;

t:=t+1;

установка Tt, It ;

проверка условий останова.

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

Потоковая модель может рассматриваться как дальнейшее упрощение порого вой модели [2]. Метафорой для потоковой модели является поведение путеше ственника при наводнении в гористой местности. При медленно растущем уровне воды W новое решение принимается, если значение целевой функции для этого решения выше, нежели W. От скорости подъема потока воды V зависит, сумеет или нет, путешественник найти лучшее решение оптимизационной задачи. В этом Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) состоит отличие данной модели от пороговой модели.

Квантовая модель. Квантовая модель вычислений предполагает, что вычис ления выполняются на гипотетическом вычислительном устройстве (квантовом компьютере) по следующей схеме:

задается система кубитов, на которой записывается начальное состояние;

посредством базовых квантовых операций изменяется состояние системы или е подсистем;

измеряется результирующее состояние системы.

Идея квантовых вычислений была впервые высказана Ю.И. Маниным и Р. Фейнманом. Она состоит в том, что квантовая система из L двухуровневых квантовых частиц (квантовых битов, кубитов) имеет 2L линейно независимых состояний. Вследствие принципа квантовой суперпозиции, пространством со стояний такого квантового регистра является 2L-мерное гильбертово про странство. Операция в квантовых вычислениях соответствует повороту векто ра состояния регистра в этом пространстве. Таким образом, квантовое вычис лительное устройство размером L кубит может выполнять параллельно 2L операций [6, 16, 17].

В ноябре 2009 г. физикам из Национального института стандартов и техноло гий в США впервые удалось собрать программируемый квантовый компью тер, состоящий из двух кубит. Наиболее известными алгоритмами квантовых вычислений являются:

алгоритм Гровера [16], позволяющий найти решение уравнения f (x) = 1, где 0 x N за время O( N );

алгоритм Шора, позволяющий разложить натуральное число n на простые множители за полиномиальное от log(n) время;

алгоритм Дойча-Джоза, который позволяет «за одно вычисление» определить, является ли функция двоичной переменной f(n) постоянной (f1(n) = 0, f2(n) = независимо от n) или «сбалансированной» (f3(0) = 0, f3(1) = 1;

f4 (0) = 1, f4 (1) = 0).

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

Происходит это за счт того, что при запуске квантовых вычислений каждая ча стица «знает» о состоянии всех остальных частиц, участвующих в вычислении.

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

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

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

Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) Очевидно, что полная изоляция невозможна, поскольку каждая частица, каждый квант, изначально «размазаны» в пространстве и тесно связаны между собой. От сюда следует, что квантовые вычисления на высоких мощностях не смогут обеспе чить абсолютно истинными вычислениями, но вполне пригодны для правдоподоб ных решений в искусственном интеллекте.

Неопределнность квантовых вычислений это фактически прямое следствие теоремы Гделя, гласящей, что формальная система не может с абсолютно истин ной точностью познать саму себя. Именно эта особенность квантовых вычислений позволяет причислить их к классу эволюционных вычислений, считать одним из проявлений более общего класса процессов, инспирированных природными систе мами [3, 6].

Алгоритмы квантового поиска весьма чувствительны к изменениям и пере становкам входных параметров исходной модели. Это говорит о том, что для одно го вида модели объекта, например представленного матрицей, можно получить решение с одним локальным оптимумом. А для этой же матрицы с переставлен ными строками и столбцами можно получить другое решение с лучшим локальным оптимумом. Следует отметить, что, изменяя параметры, алгоритмы и схему кван тового поиска, в некоторых случаях, можно выходить из локальных оптимумов.

Эта проблема продолжает оставаться одной из важнейших в методах поисковой оптимизации.

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

Принципиальным отличием предложенных методов является их возможность рас параллеливать процесс поиска на этапы и применять на каждом из этих этапов различные алгоритмы. Разработана программная среда реализующая данные ме тоды. Проведен вычислительный эксперимент. Проведенные серии тестов и экспе риментов позволили уточнить теоретические оценки временной сложности алго ритмов проектирования на основе методов, инспирированных природными систе мами и их поведение для схем различной структуры. В лучшем случае временная сложность алгоритмов O(nlogn), в худшем случае О(n3). Работа выполнена при поддержке грантов РФФИ № 13-01-00371 и № 12-07-00062.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК Северцов Г.А. Теория Эволюции. – М.: Гуманитар. изд. Центре ВЛАДОС, 2005.

1.

Курейчик В.М., Курейчик В.В., Родзин С.И. Основы теории эволюционных 2.

вычислений. – Ростов-на-Дону: Изд-во ЮФУ, 2010.

Гладков Л.А, Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.:

3.

Физматлит, 2010.

4. Kureichik V.V., Kureichik V.M., Sorokoletov P.V. Analysis And A Survey Of Evolutionary Models//Journal of Computer and Systems Sciences International. – 2007. – Т. 46. № 5.

– С. 779-791.

Бова В.В., Курейчик В.В. Интегрированная подсистема гибридного и 5.

комбинированного поиска в задачах проектирования и управления // Известия Южного федерального университета. Технические науки. – 2010. – Т. 113. № 12.

– С. 37- Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) Курейчик В.В., Курейчик В.М., Гладков Л.А., Сороколетов П.В. Бионспирированные 6.

методы в оптимизации. – М.: Физмалит, 2009.

Kurejchik V.V., Kurejchik V.M. On Genetic-Based Control//Автоматика и телемеханика.

7.

–2001. – № 10. – С. 174- Редько В.Г. От моделей поведения к искусственному интеллекту. – М.: Комкнига, 8.

2006.

9. Holland John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. – USA: University of Michigan, 1975.

Зайцев А.А., Курейчик В.В., Полупанов А.А. Обзор эволюционных методов 10.

оптимизации на основе роевого интеллекта//Известия Южного федерального университета. Технические науки. – 2010. – Т. 113. № 12. – С. 7-12.

11. Abraham A., Grosan G., Ramos V. Swarm Intelligence in Data Mining. Berlin - Heidel berg: Springer Verlag. 2006.

12. Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a colony of cooperat ing objects // IEEE Trans. on Systems, Man, and Cybernetics. – 1996. – Part B. N 26(1) 13. Karaboga, D. An idea based on honey bee swarm for numerical optimization // Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

14. Kirkpatrick S., Gelatt Jr. C. D., and Vecchi M. P. Optimization by Simulated Annealing // Science, 220. 1983.

15. Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., and Teller E. Equation of State Calculations by Fast Computer Machines // J. Chemical Physics. 21. 6. June. 1953.

16. Grover L.K. Synthesis of Quantum Superpositions by Quantum Computation // Physical Rev. Letters. No.6. 2000.

Курейчик В.В., Сороколетов П.В. Новая технология квантового поиска известия выс 17.

ших учебных заведений // Электромеханика. – 2007. – № 3. – С. 48-52.

Статью рекомендовала к опубликованию д.т.н., профессор Лисицына Л.С.

Курейчик Владимир Викторович Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет».

Факультет «Автоматики и вычислительной техники».

E-mail: vkur@tgn.sfedu.ru.

347928, г. Таганрог, пер. Некрасовский, 44.

Тел.: 8(8634)37-16-51.

Кафедра систем автоматизированного проектирования, заведующий кафедрой САПР, профессор, д.т.н.

Курейчик Владимир Владимирович Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет».

Факультет «Автоматики и вычислительной техники».

E-mail: kureichik@yandex.ru 347928, г. Таганрог, пер. Некрасовский, 44.

Тел.: 8(8634)37-16-51.

Кафедра систем автоматизированного проектирования, ст. гр. А-70.

Kureichik Vladimir Victorovich Federal State-Owned Autonomy Educational Establishment of Higher Vocational Edu cation Southern Federal University.

Информатика, вычислительная техника и инженерное образование. – 2013. № 2 (13) The College of Automation and Computer Engineering E-mail: vkur@tgn.sfedu.ru.

44, Nekrasovskiy, Taganrog, 347928, Russia.

Phone: +7(8634)37-16-51.

The Department of Computer Aided Design;

Dr.Tech.Sci., Professor, Head of CAD Department.

Kureichik Vladimir Vladimirovich Federal State-Owned Autonomy Educational Establishment of Higher Vocational Edu cation Southern Federal University.

The College of Automation and Computer Engineering E-mail: kureichik@yandex.ru 44, Nekrasovskiy, Taganrog, 347928, Russia.

Phone: +7(8634)37-16-51.

The Department of Computer Aided Design;

student.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.