Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 12

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

Текст из файла (страница 12)

Из полученных строк сформировать новую популяцию.Схема рулетки может давать большие ошибки, в том смысле, что конечное числопотомков данной строки может сильно отличаться от ожидаемого числа потомков.Конечное число приближается к ожидаемому числу только в популяциях очень большихразмеров.Операция скрещивания (рис )заключается в выполнении следующих действий:1)выбрать пары строк для скрещивания; 2)для каждой выбранной пары: с заданнойвероятностью выполнить скрещивание, получить двух потомков и произвести впопуляции замену родителей на их потомков или просто добавить в популяцию двухпотомков. Параметр операции - вероятность скрещивания ( pc ). Простейший вариантоперации (одноточечное скрещивание) выполняется следующим образом:1.

Вся популяция случайным образом разбивается на пары.2. Для каждой пары случайным образом генерируется число pc , если pc  pc , товыбирается случайное целое число i в интервале (1, l-1), где l - длина строки, и строкиобмениваются фрагментами, находящимися после i-го бита, в противном случае ничего непроисходит.При многоточечном скрещивании выбирается несколько точек разрыва строки.Операция мутации (рис ) заключается в инвертировании каждого бита с заданнойвероятностью.

Параметр операции - вероятность мутации ( pm ). Операция выполняетсяследующим образом:1. Для каждого бита генерируется случайное число pm .2. Если pm  pm , то бит инвертируется.591LFipc  pcFj(бит ивертируется, еслиpm  pm )Рис. Схема выполнения операций мутации и скрещиванияКритерий останова. В большинстве алгоритмов используется один или некотораякомбинация следующих способов останова: выполнение алгоритмом априорно заданного числа итераций; выполнение алгоритмом априорно заданного числа итераций без улучшенияфункции выживаемости; достижение некоторого априорно заданного значения функции выживаемости.Эволюционныеалгоритмыиспользуютцелочисленноеиливещественноекодирование решений. Операции выполнения операций скрещивания и мутации для этихспособов кодирования решений приведены в приложении 1.Среди основных проблем использования ГА и ЭА можно выделить следующие:1. Выбор способа кодирования решений.2.

Определение операций скрещивания и мутации для работы с используемымпредставлением решения.3. Определение параметров алгоритма:размера популяции;вероятностей скрещивания и мутации.4. Задание целевой функции и критерия останова.4.2. Теория схем. Гипотеза строительных блоковНесмотря на успешное использование ГА, до сих пор нет полной ясности какработает ГА. Теория схем и гипотеза строительных блоков, предложенные Холландом иГолдбергом [(Holland J.N.

Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. ofMichigan Press, 1975.), (Golberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning.60Addison-Wesley, Reading, Mass., 1989.)],отражают основные механизмы работы ГА, объясняют:почему все-таки ГА могут работать.Схема - представляет подмножество всех возможных строк, которые имеют те жесамые биты в некоторых фиксированных позициях. Схема **000 представляет все строкис 0 в последних трёх позициях: 00000, 01000, 10000 и 11000.

Подобным же образом схема1*00* представляет строки: 10000, 10001, 11000 и 11001. Каждая строка представленнаясхемой называется примером схемы. Количество фиксированных позиций в схеме - это еёпорядок (**000 имеет 3 порядок). Определяющая длина схемы - это расстояние междусамыми дальними фиксированными позициями.

Так у схемы **000 определяющая длинаравна 2, у 1*00* - равна 3. Каждая строка одновременно является примером в 2l схем (l длина строки). Так как схема определяет набор строк, то можно ввести понятие среднегозначения целевой функции схемы. В очередной популяции оно определяется среднимзначением целевых функций примеров схемы в популяции. Среднее значение целевойфункции схемы варьируется вместе с составом популяции на различных итерацияхалгоритма.Представим схему c k фиксированными позициями. Существует 2k-1 других схем стеми же самыми фиксированными позициями, которые могут быть получены,перестановками 0 и 1 в этих k позициях. Каждый такой набор фиксированных позицийобразует соревнование схем, борьбу за выживание среди 2k схем. Так как существует 2lвозможных комбинаций фиксированных позиций - следовательно, возможно 2l различныхсоревнований.

ГА одновременно пытается решить 2l соревнований схем и выделитьлучшую схему для каждого набора фиксированных позиций. Мы можем представить себепоиск оптимального решения как одновременное соревнование между схемами заувеличение количества их примеров в популяции.Следующее уравнение известно как теорема схем:N h, t  1  N h, t  h F h, t  1  pc p m oh  ,l 1F t  где N  h, t  1 - ожидаемое количество примеров схемы h на шаге t+1, F h, t  - среднеезначение целевой функции схемы h на шаге t, F t  - средние значение целевой функции впопуляции на шаге t, pc - вероятность скрещивания,   h - определяющая длина схемы h,pm - вероятность мутации, o h - порядок схемы h, l - количество бит в строке.61Выражение N h, t f  h, t определяет ожидаемое число примеров схемы h в новойf t  h pm o h  определяет вероятность выживания схемы hпопуляции, выражение 1  pcl 1после выполнения операций скрещивания и мутации, слагаемое pc  hl 1определяетвероятность того, что пример схемы h будет разрушен скрещиванием, слагаемое pmo hопределяет вероятность того, что пример будет разрушен мутацией.Данная теорема описывает несколько важных аспектов поведения ГА.

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

Увеличение pc , pmили уменьшение меры давления селекции увеличивает разнообразие популяции, но непозволяет использовать все хорошие схемы, имеющиеся в популяции. Уменьшение pc ,pm или увеличение меры давления селекции приводит к улучшению использованиянайденных схем, но замедляет исследование пространства решений в поисках новыххороших схем. Поддержание равновесия известно как проблема “баланса исследования ииспользования”. Проблема выбора параметров ГА (вероятность скрещивания и мутации,размер популяции и т.п.) является для многих приложений сложной задачей, так какпараметры не могут быть определены независимо, без учета взаимодействия операций,способа кодирования и размера популяции. Какие-либо теоретические результаты длярешения данной проблемы (за исключением качественного анализа работы ГА) нанастоящий момент времени отсутствуют.Если мы опишем оптимальную строку в виде комбинации схем с маленькимиопределяющими длинами, низким порядком и высокими значениями средних целевыхфункций, тогда победители индивидуальных соревнований схем потенциально могутсформировать оптимальную строку (это не всегда справедливо, очень плохие строкимогут быть созданы из хороших схем).

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

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

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

В большинствеслучаев проблема выбора способа кодирования и значений параметров операций решаетсяв настоящее время путем формирования эвристических гипотез и проверке ихэкспериментальным путем.Описание динамики работы ГА с помощью цепей Маркова. При описаниидинамики работы ГА с помощью цепей Маркова проблема размерности и размера моделистановится сдерживающей. Данный подход предполагает [(Vose M.D., Liepins G.E.

Характеристики

Список файлов лекций