Поиск по сайту.

AИ, ГА, Нейронные сети: Генетические алгоритмы.


Другие алгоритмы.

Д.И.Батищев, С.А.Исаев

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

(опубликовано в сборнике статей, издаваемом ВГТУ, осень 1997)
.
В работе рассматривается генетический алгоритм для решения многопараметрической непрерывной задачи оптимизации. Предлагается новая, отличная от традиционной, символьная модель и новые генетические операторы, использующие специфику такой модели. Обсуждаются вопросы, связанные с влиянием операторов и значений параметров на поведение ГА.

Введение

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

К началу документа

Постановка задачи

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

К началу документа

Эволюционный поиск

Генетические алгоритмы являются одними из эволюционных алгоритмов, применяемых для поиска глобального экстремума функции многих переменных. Принцип работы генетических алгоритмов основан на моделировании некоторых механизмов популяционной генетики: манипулирование хромосомным набором при формировании генотипа новой биологической особи путем наследования участков хромосомных наборов родителей (кроссинговер), случайное изменения генотипа, известное в природе как мутация. Другим важным механизмом, заимствованным у природы, является процедура естественного отбора, направленная на улучшение от поколения к поколению приспособленности членов популяции путем большей способности к "выживанию" особей, обладающих определенными признаками.
Реализацию базового генетического алгоритма можно представить как итерационный процесс, включающий несколько этапов:
  1. генерация начальной популяции,
  2. воспроизводство "потомков":
    • выбор родительской пары,
    • выбор и реализация одного из операторов кроссовера,
    • выбор и реализация одного из операторов мутации,
  1. создание репродукционной группы,
  2. процедура отбора и формирование на его основе нового поколения,
  3. если не выполнено условие останова, то перейти к п.2.

К началу документа

Тестовые задачи

Оценка качества предлагаемого алгоритма и частных генетических операторов проводилась по нескольким направлениям: во-первых, сравнение эффективности поиска в зависимости от выбранной символьной модели, в том числе от длины хромосомного набора, во-вторых, зависимость улучшения значения приспособленностей особей популяции от параметров генетического алгоритма, прежде всего метода выбора родительских пар и реализации механизма отбора. Кроме того, помимо количественных оценок приводится качественное описание поведения популяции, управляемой генетическим алгоритмом при тех или иных параметрах.
Оценка предлагаемого алгоритма проводилась на ряде тестовых функций. Это прежде всего несколько тестовых функций De Jong'а, которые часто используются для проверки эффективности новых генетических алгоритмов, кроме того, были использованы сложные многоэкстремальные функции высокой размерности, практически нерешаемые классическими методами.

ј

Тестовая задача

Размерность

Свойства

1

De Jong 2

2

 Овражная функция, один глобальный экстремум

2

De Jong 3

5

 Разрывы типа "скачек", максимум достигается на гиперкубе

3

De Jong 5

2

 Один глобальный на гиперкубе, 24 локальных максимума.

4

Растригина

2

 96 локальных экстремумов и 4 глобальных.

5

Griewank

2

 Один глобальный и множество локальных максимумов.

6

Растригина

10

 Один глобальный экстремум и 1010- 1 локальных.

7

Griewank

10

 Один глобальный и множество локальных максимумов
Более подробно используемые тестовые функции представлены в приложении.

К началу документа

Символьная модель

При построении символьной модели множество допустимых решений представляется в виде конечной популяции особей. Каждая особь в популяции обладает мерой приспособленности к окружающей среде. Процесс поиска оптимального решения описывается процессом моделируемой "эволюции", целью которой является нахождение особи (или множества особей), имеющей максимальную приспособленность, т.е. особи, соответствующей оптимальному значению управляемых параметров.
Каждая особь представлена в виде набора некоторого числа генов (битовых строк заданной длины) называемого хромосомой. Число генов в хромосоме соответствует размерности решаемой задачи; каждый ген используется для кодирования небольшого интервала значений одного из управляемыхпараметров проектируемой системы. По существу, такая кодировка соответствует разбиению пространства параметров на гиперкубы, которым соответствуют уникальные комбинации битов в хромосоме (генотип).
Для установления соответствия между гиперкубами разбиения области и бинарными строками, описывающими номера таких гиперкубов, использовался рефлексивный код Грея.
При взаимодействии особи с внешней средой ее генотип порождает внешне наблюдаемые количественные признаки: фенотип и оценку приспособленности. Фенотип особи определяется как точка, принадлежащая гиперкубу пространства поиска соответствующего генотипа. В рассматриваемом алгоритме применялся равномерный закон распределения точек фенотипа в соответствующем гиперкубе. (Более подробно предлагаемая символьнаямодель представлена в [6])
Важно отметить, что в этом и состоит основное отличие предлагаемого способа формирования фенотипа от традиционного (см. [1,2]). Символьная модель, предлагаемых ранее генетических алгоритмов, предусматривала дискретизацию пространства параметров с шагом, соответствующим требуемой точности. При этом фенотип определялся как узел такой пространственной решетки, так что между генотипом и фенотипом особи существовало взаимно однозначное соответствие. Предлагаемая же нами модель не предусматривает однозначности, поскольку каждому генотипу может соответствовать целое множество фенотипов (что, вообще говоря, имеет место в природе). Это позволяет использовать более крупное разбиение пространства параметров, делая при этом длину хромосомногонабора короче.
Для поиска оптимального разбиения пространства параметров на гиперкубы, кодируемые хромосомными наборами соответствующей длины NL (N - размерность задачи, L - длина кодировки одного гена), проводились испытания на четырех тестовых функция: De Jong 2, De Jong 3, De Jong 5 и функция Griewank'а. В качестве рассматриваемых вариантов были выбраны L1=4, L2=6, L3=8, L4=16. Эффективность поиска определялась по отношению среднему (усредн. по 50 запускам) значению приспособленности популяции к максимальному значению после 1000 вычислений функции, что соответствует порядка 23-25 поколениям, при численности популяции 50 и формировании 20 брачных пар на каждом поколении, вероятность мутации была около 0.001. Результаты эксперимента приведены на Рисунок 1.
Как видно из представленной диаграммы уже после L=6 для представленных функций не происходит значительно улучшения эффективности поиска. Вообще, длина кодировки в значительной мере сказывается на функциях, ландшафту которых присущи скачкообразные изменения, как например у De Jong 3 или 5, и наоборот непрерывная функция De Jong 2, а тем более функция Griewank'а слабо чувствительны к длине кодировки. Очевидно, такая особенность объясняется разбросом значений приспособленностей особей, имеющих одинаковые генотипы, этот разброс тем больше, чем крупнее гиперкубы разбиения пространства. Поэтому в процессе поиска для таких функций сложнее определить хромосомные наборы, которые бы соответствовали оптимальному решению.
Однако увеличение длины кодировки ускоряет процесс сходимости всех членов популяции к лучшему найденному решению (см. Рисунок 3). Зачастую такой эффект не желателен, поскольку при этом большая часть пространства поиска остается неисследованной - преждевременная сходимость может не привести к оптимальному решению, кроме того, быстрая сходимость к одной области не гарантирует обнаружения нескольких равных экстремумов. Поэтому в вопросе выбора оптимальной длины кодировки нужно достичь некоторого компромиссного решения - с одной стороны L должно быть достаточно большим, чтобы все-таки обеспечить быстрый поиск, с другой стороны - по возможности малым, чтобы не допускать преждевременной сходимости и оставить алгоритму шанс отыскать несколько оптимальных значений. Мы предлагаем использовать хромосомные наборыдлины 6N - 8N, где N - размерность задачи.
Формирование генотипов особей начальной популяции проводилось по принципу максимального побитого разнообразия (см. [6]). Максимальное побитовое разнообразие призвано обеспечить максимальное богатство генетического материала в начальной популяции.

К началу документа

Влияние параметров генетического алгоритма на эффективность поиска

Операторы кроссовера и мутации

Одной из особенностей предлагаемого генетического алгоритма является отход от традиционной схемы "размножения", используемой в большинстве реализованных ГА-мах [3] и повторяющих классическую схему, предложенную Голландом [1]. Классическая схема предполагает ограничение численности потомков путем использования так называемой вероятности кроссовера. Такая модель придает величине, соответствующей численности потомков, вообще говоря, недетерминированный характер. Мы предлагаем отойти от вероятности кроссовера и использовать фиксированное число брачных пар на каждом поколении, при этом каждая брачная пара "дает" двух потомков. Такойподход хорош тем, что делает процесс поиска более управляемым и предсказуемым в смысле вычислительных затрат.
В качестве генетических операторов получения новых генотипов "потомков", используя генетическую информацию хромосомных наборов родителей мы применяли два типа кроссоверов - одно- и двухточечный. Вычислительные эксперименты показали, что даже для простых функций нельзя говорить о преимуществе того или иного оператора. Более того было показано, что использование механизма случайного выбора одно- или двух точечного кроссовера для каждой конкретной брачной пары подчас оказывается более эффективным, чем детерминированный подход к выбору кроссоверов, поскольку достаточно трудно априорно определить который из двух операторов более подходит для каждого конкретного ландшафта приспособленности. Из диаграмм, представленных на Рисунок 4 видно, что нельзя однозначно отдавать предпочтение одно- или двухточечному кроссоверу. Одноточечный оказался более эффективным на тестовых функциях De Jong'а 2 и 5, на двумерной функции Griewank'а и на двумерной функции Растригина, однако для функции De Jong'а 3, функции Griewank'а и Растригина от 10 переменных можно говорить о преимуществе выбора двухточечного оператора. Использование же случайного выбора преследовало целью прежде всего сгладить различия этих двух подходов и улучшить показатели среднего ожидаемого результата. Для всех представленных тестовых функций так и произошло, - случайного выбор оказался эффективнее худшего. Кроме того, в ряде случаев (функции Griewank'а, 10-мерная функция Растригина) применение случайного механизма в выборе кроссовера дало лучшие результаты по сравнению с детерминированными подходами.
Повышение эффективности поиска при использовании случайного выбора операторов кроссовера повлияло на то, чтобы применить аналогичный подход при реализации процесса мутагинеза новых особей, однако в этом случае преимущество перед детерминированным подходом не так очевидно в силу традиционно малой вероятности мутации (в наших экспериментах вероятность мутации составляла 0.001 - 0.01).

Выбор родительской пары

Как уже отмечалось, мы решили не использовать вероятность кроссовера в качестве одного из параметров алгоритма, ограничивая число воспроизводимых потомков фиксированным числом брачных пар. В связи с этим встал вопрос о том, каким образом из всего многообразия всех возможных пар выбрать лишь несколько. Предлагалось несколько подходов, однако мы рассмотрим здесь несколько показавшихся нам наиболее интересными.
Первый подход самый простой - это случайный выбор родительской пары ("панмиксия"), когда обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, причем любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.
Второй способ выбора особей в родительскую пару - так называемый селективный. Его суть состоит в том, что "родителями" могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции, при равной вероятности таких кандидатов составить брачную пару. Такой подход обеспечивает более быструю сходимость алгоритма. Однако из-за быстрой сходимости селективный выбор родительской пары не подходит тогда, когда ставиться задача определения нескольких экстремумов, поскольку для таких задач алгоритм, как правило, быстро сходится к одному из решений. Кроме того, для некоторого класса задач со сложным ландшафтом приспособленности быстрая сходимость может превратиться в преждевременную сходимость к квазиоптимальному решению. Этот недостаток может быть отчасти компенсирован использованием подходящегомеханизма отбора (о чем будет сказано ниже), который бы "тормозил" слишком быструю сходимость алгоритма.
Другие два способа формирования родительской пары, на которые хотелось бы обратить внимание, это инбридинг и аутбридинг. Оба эти метода построены на формировании пары на основе близкого и дальнего "родства" соответственно. Под "родством" здесь понимается расстояние между членами популяции как в смысле геометрического расстояния особей в пространстве параметров (для фенотипов), так и в смысле хэмминингого расстояния между хромосомными наборами особей (для генотипов). В связи с этим будем различать генотипный и фенотипный (или географический) инбридинг и аутбридинг. Под инбридингом понимается такой метод, когда первый член пары выбирается случайно, а вторым с большей вероятностью будет максимально близкая к нему особь. Аутбридинг же, наоборот, формирует брачные пары из максимально далеких особей. Использование генетических инбридинга и аутбридинга оказалось более эффективным по сравнению с географическим для всех тестовых функций при различных параметрах алгоритма. Наиболее полезно применение обоих представленных методов для многоэкстремальных задач. Однако два этих способа по-разному влияют на поведение генетического алгоритма. Так инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что фактически приводит к разбиению популяции на отдельные локальные группы вокруг подозрительных на экстремум участков ландшафта, напротив аутбридинг как раз направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области.

Механизм отбора

Обсуждение вопроса о влиянии метода создания родительских пар на поведение генетического алгоритма невозможно вести в отрыве от реализуемого механизма отбора при формировании нового поколения. Сразу же отметим, что метод пропорционального отбора, как и другие методы, основанные на включение особи в новую популяцию по вероятностному принципу, давали настолько плохие результаты, что здесь даже не рассматриваются. В своих экспериментах мы использовали другие механизмы отбора, из которых выделим два: элитный и отбор с вытеснением.
Идея элитного отбора, в общем, не нова, этот метод основан на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. В литературе, посвященной генетическим алгоритмам, например в [3], элитному отбору отводят место как достаточно слабому с точки зрения эффективности поиска. В основном это объясняют потенциальной опасностью преждевременной сходимости, отдавая предпочтение пропорциональному отбору. Однако наш опыт говорит о напрасности таких опасений. Быстрая сходимость, обеспечиваемая элитным отбором, может быть, когда это необходимо, с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом. Как видно из результатов, приведенных в Таблица 1, именно такая комбинация "аутбридинг - элитный отбор" является одной из наиболее эффективных для рассматриваемых тестовых функций.
Второй метод, на котором хотелось бы остановиться, это отбор вытеснением. Отбор, построенный на таком принципе, носит бикритериальный характер - то, будет ли особь из репродукционной группы заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с аналогичным хромосомным набором. Из всех особей с одинаковыми генотипами предпочтение сначала, конечно же, отдается тем, чья приспособленность выше. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие. Вытеснение в данном случае формирует новую популяцию скорее из далеко расположенных особей, вместо особей, группирующихся около текущего найденного решения. Этот метод особенно хорошо себя показал при решении многоэкстремальных задач, при этом помимо определения глобальных экстремумов появляется возможность выделить и те локальные максимумы, значения которых близки к глобальным.

К началу документа

Три задачи генетического алгоритма

Представленный алгоритм обладает достаточно широкими возможностями, - настроив соответствующим образом параметры системы, можно управлять процессом поиска в зависимости от поставленной задачи. Как уже отмечалось, существует, по крайней мере, три класса задач, которые могут быть решены представленным алгоритмом:
  • задача быстрой локализации одного оптимального значения,
  • задача определения нескольких (или всех) глобальных экстремумов,
  • задача описания ландшафта исследуемой функции, которая может сопровождаться выделением не только глобальных, но и локальных максимумов.
Основное различие в методах решения этих трех задач лежит в реализации различных уровней соотношения, которое в теории генетических алгоритмов называется как соотношение "исследование - использование".
Быстрый поиск одного экстремума, как правило, достигается использованием параметров, которые способствуют максимально быстрой сходимости за счет манипулирования только особями, обладающими лучшей приспособленностью, при этом более "слабые" члены популяции не участвуют в формировании родительских пар и не выживают после процедуры отбора. Этого можно достичь путем применения селективного выбора пар и элитного метода отбора. Понятно, что больший акцент в паре "исследование - использование" при этом делается именно на "использование".
Для решения второй задачи, очевидно, вопросу "исследования" пространства поиска должно уделяться гораздо большее внимание. Оно достигается за счет другого сочетания параметров и достаточно большой численности популяции, при этом ГА сможет выделить несколько (или даже все) глобальные экстремумы. В качестве примера решения такой задачи приведем экспериментальные данные, полученные при поиске максимумов двумерной функции Растригина. Параметры генетического алгоритма, использовавшиеся для максимизации этой функции, такие же, как и для решения других тестовых задач (см. комментарий к таблице 1.) Итак, средние показатели процесса поиска по 50 испытаниям, в скобках для сравнения приведены результаты, опубликованные в [6]:
  • среднее значение приспособленности - 80.694,
  • число вычислений функции - 652 (1282), что составляет порядка 15 поколений,
  • частота локализации всех 4 точек глобального экстремума равна 1 (в [6] локализовывался один максимум).
Для выделения нескольких глобальных максимумов, лучше использовать такую комбинацию: аутбридинг в сочетании с инбридингом, в качестве естественного отбора достаточно использовать элитный отбор или отбор с вытеснение (последний более надежный). Максимальная эффективность поиска достигается в сочетании аутбридинга и инбридинга, причем аутбридинг рекомендуется использовать в начале поиска, достигая максимально широкого "исследовании", а завершать поиск лучше уточнением решения в локальных группах, используя инбридинг.
И наконец третья задача. Особенность ее решения состоит в том, что при достаточно большом размере популяции и небольшом заданном количестве брачных пар проявляется интересное свойство поведения генетического алгоритма: в процессе поиска проявляются черты рельефа ландшафта функции приспособленности (овраги, холмы, долины). На Рисунок 5 видно, что оставляя области, которым соответствуют меньшая приспособленность, ГА группирует особи ближе к вершинам холмов, в область притяжения которых они попали. Это эквивалентно определению локальных экстремумов, значения которых близки к оптимальным. Продолжение поиска ведет к тому, что особи, сгруппировавшиеся вокруг локальных экстремумов, постепенно "вымирают", а их место в популяции начинают занимать особи с лучшей приспособленностью близкие к глобальным максимумам. Использование же отбора с вытеснение в какой-то мере может препятствовать этому процессу, давая шанс "выжить" особям около локальных экстремумов.

К началу документа

Приложение А

Тестовая функция ј1

, .
.

Тестовая функция ј2

, .
на гиперплоскости .

Тестовая функция ј3

, где a1j = 16[(j mod 5)-2], a2j = 16[(j % 5)-2],
0002, при.

Тестовая функция ј4

, .
= F (4.52299, 4.52299) = F (-4.52299, 4.52299) =
= F (-4.52299, -4.52299) = F (4.52299, -4.52299) = 80.7065.

Тестовая функция ј5

, .
= F (0.00, 0.00) = 1.0.

Тестовая функция ј6

,
= F (0.00, 0.00,:0.00) = 0.00, при .

Тестовая функция ј7

, .
= F (0.00, 0.00,:0.00) = 10.00.

К началу документа

Приложение Б

Рисунок 1


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

Рисунок 2

На рисунке представлены графики изменения приспособленности лучшей особи в популяции при различной длине кодировки; непрерывная линия - L = 10, разрывная - L=6, пунктирная - L=4.

Рисунок 3

De Jong 2 (L=4)
De Jong 2 (L=10)
 
De Jong 5 (L=4)
De Jong 5 (L=10)
На диаграммах представлены изменение лучшей, средней и худшей приспособленностей особей в популяции. Нетрудно видеть, что увеличение длины хромосомного набора не столько ускоряет процесс поиска наилучшего значения приспособленности, сколько влияет на улучшение приспособленностей наихудших особей в популяции, что приводит к более быстрой сходимости алгоритма в ущерб исследованию пространства поиска.

Рисунок 4

De Jong 2
 De Jong 3
 Griewank (n=10)

Эффективность ГА при использовании различных операторов кроссовера. На диаграммах представлены результаты, усредненные по 50 запускам (каждый запуск - около 5000 вычислений для 10-мерных функций или 1000 для остальных).

Рисунок 5

 
 Быстрый
поиск
 Описание
ландшафта
 Быстрый
поиск
 Описание
ландшафта
  
De

Jong 2
De
Jong 5

 
 Быстрый
поиск
 Описание
Ландшафта
 Быстрый
поиск
 Описание
ландшафта
  
 
Griewank
 n=2
Растригин
 n=2
  
На рисунке представлены популяции особей в пространстве поиска для тестовых функций на 25-ом поколении генетического алгоритма при параметрах, настроенных на быстрый поиск одного максимума и для задачи описания ландшафта.

Таблица 1


 панм-элит
 панм-выт
 селек-элит
 селект-выт
 инбр-элит
 инбр-выт
 аутбр-элит
 аутбр-выт

De Jong 2

Макс
 99,999
 99,964
 99,998
 99,982
 99,999
 99,983
 99,986
 99,980
Мин
 92,254
 90,735
 83,529
 80,211
 83,725
 88,445
 91,754
 94,843
ср.знач
 98,038
 98,666
 96,595
 96,903
 98,464
 98,833
 98,811
 98,639

De Jong 3

Макс
 29,000
 29,000
 30,000
 30,000
 28,000
 29,000
 30,000
 30,000
Мин
 27,000
 27,000
 27,000
 29,000
 24,000
 25,000
 28,000
 28,000
ср.знач
 28,320
 28,160
 29,280
 29,180
 26,880
 27,180
 28,780
 28,620

De Jong 5

макс
 1,002
 1,002
 1,002
 1,002
 1,002
 1,002
 1,002
 1,002
мин
 0,502
 0,550
 0,202
 0,966
 0,202
 0,715
 0,988
 0,910
ср.знач
 0,982
 0,981
 0,985
 1,000
 0,962
 0,978
 1,001
 0,991

Griewank n=2

макс
 1,000
 1,000
 1,000
 1,000
 1,000
 1,000
 1,000
 1,000
мин
 0,836
 0,871
 0,871
 0,871
 0,871
 0,869
 0,872
 0,906
ср.знач
 0,963
 0,977
 0,953
 0,960
 0,946
 0,970
 0,993
 0,988

Растригин n=10

макс
 -4,989
 -7,225
 -8,594
 -7,982
 -7,561
 -11,740
 -4,937
 -6,447
мин
 -24,932
 -18,666
 -25,632
 -21,839
 -28,717
 -30,851
 -14,996
 -17,816
ср.знач
 -12,077
 -12,759
 -14,842
 -13,671
 -19,245
 -20,613
 -9,432
 -9,840

Griewank n=10

макс
 9,356
 9,479
 9,476
 9,396
 9,260
 9,255
 9,586
 9,467
мин
 9,027
 9,034
 9,051
 9,078
 8,708
 8,445
 9,069
 9,069
ср.знач
 9,158
 9,173
 9,198
 9,203
 8,936
 8,912
 9,235
 9,212
В таблице приведены результаты поиска по 50 запускам при различных параметрах генетического алгоритма. Для всех примеров: L=6, численность популяции 50, число брачных пар 20, вероятность мутации 0.01. Число вычислений функции: для первых четырех около1000, для двух последних около 5000.

К началу документа

Литература
  1. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975.
  2. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine learning. Addison-Wesley, 1989.
  3. Mitchell M. An introduction to Genetic Algorithm. MIT Press, 1996.
  4. Батищев Д. И. Методы оптимального проектирования. - М.: Радио и связь, 1984.
  5. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995.
  6. Батищев Д.И., Скидкина Л.Н., Трапезникова Н.В. Глобальная оптимизация с помощью эволюционно - генетических алгоритмов / Мужвуз. сборник, ВГТУ, Воронеж, 1994.
  7. Батищев Д.И., Гуляева П.А., Исаев С.А. Генетический алгоритм для решения задач невыпуклой оптимизации / Тез.докл. Междунар. конф. "Новые информационные технологии в науке, образовании и бизнесе", Гурзуф, 1997.

Исаев Сергей
e-mail: mailto:sergey.isaev@mailcity.com
web: http://www.chat.ru/~saisa/index.html


Вверх по странице, к оглавлению и навигации.