Сравнительный анализ методов эволюционного поиска
Исследуются методы эволюционного поиска при решении оптимизационных задач. Определены задачи, которые являются трудно разрешимыми с помощью эволюционных методов. Выявлены комбинации эволюционных операторов, позволяющие эффективно решать различные задачи оптимизации. Досліджуються методи еволюційн...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/6709 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Сравнительный анализ методов эволюционного поиска / С.А. Субботин, А.А. Олейник // Штучний інтелект. — 2008. — № 2. — С. 44-49. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859814726776651776 |
|---|---|
| author | Субботин, С.А. Олейник, А.А. |
| author_facet | Субботин, С.А. Олейник, А.А. |
| citation_txt | Сравнительный анализ методов эволюционного поиска / С.А. Субботин, А.А. Олейник // Штучний інтелект. — 2008. — № 2. — С. 44-49. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| description | Исследуются методы эволюционного поиска при решении оптимизационных задач. Определены
задачи, которые являются трудно разрешимыми с помощью эволюционных методов. Выявлены
комбинации эволюционных операторов, позволяющие эффективно решать различные задачи
оптимизации.
Досліджуються методи еволюційного пошуку при розв’язку оптимізаційних задач. Визначено задачі,
які є важко розв’язуваними за допомогою еволюційних методів. Виявлено комбінації еволюційних
операторів, що дозволяють ефективно вирішувати різні задачі оптимізації.
Evolutionary search methods for the decision of optimization problems are investigated. Problems which are
difficultly solved with the help of evolutionary methods are determined. The combinations of evolutionary
operators allowing effectively to solve various problems of optimization are revealed.
|
| first_indexed | 2025-12-07T15:21:20Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 2’2008 44
2С
УДК 519.6:004.93
С.А. Субботин, А.А. Олейник
Запорожский национальный технический университет, Украина
subbotin@zntu.edu.ua
Сравнительный анализ методов
эволюционного поиска
Исследуются методы эволюционного поиска при решении оптимизационных задач. Определены
задачи, которые являются трудно разрешимыми с помощью эволюционных методов. Выявлены
комбинации эволюционных операторов, позволяющие эффективно решать различные задачи
оптимизации.
Введение
Большинство технических, экономических и биомедицинских задач связаны с
необходимостью поиска глобального оптимума целевой функции в многомерном
пространстве управляемых переменных. Классические методы многомерной опти-
мизации [1], [2] являются методами локального поиска и сильно зависят от выбора
начальной точки поиска. При поиске решений задач глобальной оптимизации могут
быть использованы методы эволюционного поиска [3-5], которые основаны на
аналогии с естественными процессами эволюции. Применение таких методов
позволяет перейти от моделей поиска с жестко заданными правилами к моделям с
динамически изменяющейся структурой на каждой итерации в зависимости от
эффективности ранее найденного решения.
Для работы эволюционных методов в качестве информации об оптимизируемой
функции используются её значения в рассматриваемых точках пространства поиска, и
не требуется вычислений значений производных. Поэтому данные методы применимы
к широкому классу функций, в частности к функциям, не имеющим аналитического
описания.
Постановка задачи
На данный момент известно достаточно большое количество эволюционных
методов [3-8]. Очевидно, что ни один из методов эволюционного поиска не может
считаться наилучшим по сравнению с другими при решении любых типов
оптимизационных задач и при любых обстоятельствах. Целесообразность выбора
одного из методов в целях практического использования определяется его эффектив-
ностью при решении конкретного класса оптимизационных задач.
Целью статьи является проведение сравнительного анализа методов эволю-
ционного поиска при решении оптимизационных задач с целью определения классов
задач, которые являются трудно решаемыми с помощью эволюционного поиска, а
также выявления комбинаций эволюционных операторов, позволяющих эффективно
решать различные задачи оптимизации.
Сравнительный анализ методов эволюционного поиска
«Штучний інтелект» 2’2008 45
2С
Условия и порядок проведения экспериментов
Для сравнения эволюционных методов предлагается использовать функции f1 – f7,
позволяющие объективно оценить качество работы того или иного метода. Объективность
сравнения методов оптимизации достигается за счет различных свойств (унимодаль-
ность, непрерывность, гладкость, монотонность, дифференцируемость) функций
выбранной совокупности.
Аналитическое описание тестовых функций приведено в табл. 1.
Таблица 1 – Тестовые функции для сравнения эволюционных методов
Аналитическое описание х*
f1 (x1,x2) = (x2 – x1
2)2 + (1 – x1)2 (1; 1)
>+
≤<−⋅+
−≤<−+⋅+
−≤+
=
.5,3
,55,sin3
,510,sin3
,10,3
)(
2
2
2
2
xx
xxx
xxxx
xx
xf
π
π
π
π
–3π ≈ –9,4248
f3 (x1, x2,…, x10) = ( )( )∑
=
−−
10
1
22cos10100
i
ii xxπ (0; 0; 0; 0; 0; 0; 0; 0; 0; 0)
( )
1
2
1
2
2
2
1
214 2
2
coscos
200
1),(
−
+
⋅−
+
−=
xxxxxxf
(0; 0)
( ) ( )2
2
2
121215 )5,5(5,0)5,5(4,001,02,0)sin()sin(391,0),( −⋅+−⋅⋅+⋅⋅+⋅−= xxxxxxf ππ (4,5; 4,5), (6,5; 6,5)
( )22
2
2
1
2
1
2
2
2
1216 )(001,015,01sin1sin4388,1),( xxxxxxxf +⋅+
−+⋅+++= (1,211; 4,413), (–1,211; 4,413)
(1,211; – 4,413), (–1,211; – 4,413)
( ) ( )2
2
2
1
2
2
2
1
2
2
2
1 )1()(5
2
3
11
)1(2
1217 3
1)2,0(10)1(31063,8),( xxxxxx eexxxexxxf −+−−−+−− +⋅−−⋅⋅+⋅−⋅−= (0; 1,58)
Минимальные значения fmin (х*) в точках оптимума х* всех представленных
функций равны нулю.
Параметры методов эволюционного поиска устанавливались следующими:
размер популяции – 20 особей, максимально допустимое количество итераций
(поколений) – 100, допустимая точность правильного решения – εт = 10-3, вероятность
скрещивания – 0,8, вероятность мутации – 0,1, количество элитных особей – 2, отбор –
пропорциональный, скрещивание – арифметическое, мутация – гауссова и простая
одноточечная.
Сравнение математических методов эволюционной оптимизации проводилось
с помощью пакета MatLab на компьютере с процессором Athlon 2,5 ГГц и ОЗУ 512 Мб.
В связи с вероятностным характером работы эволюционных методов каждое
испытание повторялось 1000 раз, после чего получали средние значения иссле-
дуемых параметров.
Исследование различных эволюционных методов
Для обозначения различных методов эволюционного поиска (используемые
эволюционные операторы и стратегии их работы) поставим в соответствие четверку
{abcd} следующим эволюционным операторам:
а – оператор отбора (1 – пропорциональный, 2 – отбор с использованием рулетки, 3 –
турнирный отбор);
b – оператор скрещивания (1 – равномерное, 2 – одноточечное, 3 – арифметическое);
Субботин С.А., Олей ник А.А.
«Искусственный интеллект» 2’2008 46
2С
с – оператор мутации (1 – мутация с заданной вероятностью и плотностью, 2 –
одноточечная мутация с вероятностью 0,01);
d – количество островов (1 – один остров с 20-ю особями – островная модель не
используется; 2 – три острова – два острова по 7 особей и один остров с 6-ю особями,
миграции проходят через каждые 20 поколений, особи мигрируют с вероятностью 0,2).
Графически полученные результаты экспериментов по сравнению различных
методов эволюционного поиска представлены в виде гистограмм (рис. 1 – 3), на которых
ось абсцисс отображает тип метода, а ось ординат – среднее значение для всех
тестовых функций рассматриваемого параметра (усредненное минимальное значе-
ние целевой функции fmin, количество вычислений функции f (х), время выполнения).
0
1
2
3
4
5
6
7
8
9
10
11
11
11
21
12
11
12
21
13
11
13
21
21
11
21
21
22
11
22
21
23
11
23
21
31
11
31
21
32
11
32
21
33
11
33
21
11
12
11
22
12
12
12
22
13
12
13
22
21
12
21
22
22
12
22
22
23
12
23
22
31
12
31
22
32
12
32
22
33
12
33
22
Метод
У
ср
ед
не
нн
ое
н
ай
де
нн
ое
м
ин
им
ал
ьн
ое
зн
ач
ен
ие
ф
ун
кц
ий
Рисунок 1 – Усредненное найденное минимальное значение целевой функции fmin,
получаемое при различных эволюционных методах
800
900
1000
1100
1200
1300
1400
1500
1600
1700
1800
11
11
11
21
12
11
12
21
13
11
13
21
21
11
21
21
22
11
22
21
23
11
23
21
31
11
31
21
32
11
32
21
33
11
33
21
11
12
11
22
12
12
12
22
13
12
13
22
21
12
21
22
22
12
22
22
23
12
23
22
31
12
31
22
32
12
32
22
33
12
33
22
Метод
К
ол
ич
ес
тв
о
вы
чи
сл
ен
ий
ц
ел
ев
ой
ф
ун
кц
ии
Рисунок 2 – Среднее количество вычислений функции f (х) для различных
эволюционных методов
Сравнительный анализ методов эволюционного поиска
«Штучний інтелект» 2’2008 47
2С
0,00
0,05
0,10
0,15
0,20
0,25
11
11
11
21
12
11
12
21
13
11
13
21
21
11
21
21
22
11
22
21
23
11
23
21
31
11
31
21
32
11
32
21
33
11
33
21
11
12
11
22
12
12
12
22
13
12
13
22
21
12
21
22
22
12
22
22
23
12
23
22
31
12
31
22
32
12
32
22
33
12
33
22
Метод
В
ре
мя
в
ы
по
лн
ен
ия
, с
Рисунок 3 – Среднее время выполнения различных эволюционных методов
Как видно, эволюционные методы типа {**2*}, использующие одноточечную
мутацию, работали дольше и чаще обращались к целевой функции по сравнению с
методами {**1*}. Это объясняется более быстрым достижением методов {**1*}
заданного минимально допустимого значения целевой функции (10-3), что приводило
к прекращению их работы. Кроме того, эти методы получали более оптимальное
усредненное минимальное значение целевой функции по сравнению с методами {**2*}.
Аналогичная ситуация наблюдается также при сравнении методов {***1},
использующих единую популяцию, и методов {***2}, использующих островную
модель эволюционного метода в виде трех независимых островов c периодически
мигрирующими из одной популяции в другую особями. Полученные данные
показывают, что при оптимизации функций, аналогичных использованным тестовым
функциям, целесообразнее применять модель эволюционного метода без при-
менения островной модели. Это объясняется тем, что островная модель повышает
эффективность поиска для достаточно сложных функций, обладающих большей
нелинейностью и имеющих большее количество независимых переменных.
Результаты экспериментов по всем тестовым функциям показывают, что
эволюционные методы, позволяющие наиболее точно найти минимум целевой
функции, являются более быстрым по сравнению с аналогичными методами и
соответственно нуждаются в меньшем количестве вычислений целевой функции.
К таким методам относятся прежде всего методы {*31*}, показавшие наилучшие
результаты по всем рассматриваемым параметрам. В качестве наихудших можно
выделить методы {*32*}.
Также в результате экспериментов благодаря использованию различных
тестовых функций выявлено, что методы эволюционного поиска способны
оптимизировать функции любой сложности при любых заданных ограничениях, не
выдвигая при этом дополнительных требований к целевой функции. Однако все
эволюционные методы недостаточно хорошо оптимизируют функции типа f2
(проблема «узкого горла»), что делает их сложно применимыми для задач, целевая
Субботин С.А., Олей ник А.А.
«Искусственный интеллект» 2’2008 48
2С
функция которых имеет резкие скачки или спады. Несмотря на это, при
многократном запуске или при хорошо подобранных параметрах эволюционный
поиск способен отыскать глобальный оптимум даже в «узком горле».
Таким образом, применение эволюционных методов является целесообразным
при оптимизации сложных функций с большим количеством переменных, которые
обладают высокой степенью нелинейности и описывают сложные объекты и
процессы.
Более детальный анализ работы различных эволюционных методов проведем с
помощью функции f4, поскольку она имеет один глобальный минимум и позволяет
объективно оценить различные конфигурации эволюционных методов, обеспечивая
усредненные показатели среди функций других тестовых функций для большинства
рассматриваемых эволюционных методов. Дополнительно к уже имеющимся
показателям рассчитаем среднеквадратическое отклонение σ для среднего по испытаниям
минимального значения fmin, ср и количества вычислений целевой функции К.
Определим наилучшее fmin, min и наихудшее fmin, max значения целевой функции f(х), а
также соответствующие им векторы х* среди всех испытаний для каждого из
рассматриваемых эволюционных методов.
Результаты исследования для всех эволюционных методов выявили, что
значения среднеквадратического отклонения составляют порядка 50 % от средних
значений исследуемых критериев, что подтверждает вероятностный характер
эволюционных методов. Таким образом, при решении практических оптимизационных
задач можно рекомендовать производить эволюционный поиск несколько раз, что
позволит получить улучшенные результаты по сравнению с однократным запуском
эволюционного метода.
Гистограмма, отображающая вероятность появления правильного решения при
εт = 10-3 для различных эволюционных методов, приведена на рис. 4, из которого
видно, что вероятность правильных решений методов {**1*} значительно выше по
сравнению с методами {**2*}.
0
10
20
30
40
50
60
70
80
90
100
11
11
11
21
12
11
12
21
13
11
13
21
21
11
21
21
22
11
22
21
23
11
23
21
31
11
31
21
32
11
32
21
33
11
33
21
11
12
11
22
12
12
12
22
13
12
13
22
21
12
21
22
22
12
22
22
23
12
23
22
31
12
31
22
32
12
32
22
33
12
33
22
Метод
В
ер
оя
тн
ос
ть
п
оя
вл
ен
ия
п
ра
ви
ль
но
го
р
еш
ен
ия
, %
Рисунок 4 – Вероятность появления правильного решения при εт = 10-3 для
различных эволюционных методов
Сравнительный анализ методов эволюционного поиска
«Штучний інтелект» 2’2008 49
2С
Заключение
В результате проведенных экспериментов выявлено, что эволюционные методы
способны решать широкий спектр оптимизационных задач и способны оптимизировать
функции любой сложности при любых заданных ограничениях, не выдвигая при этом
дополнительных требований к целевой функции (унимодальность, непрерывность,
гладкость, монотонность, дифференцируемость и аналитическое задание не требуются).
Однако такие методы недостаточно хорошо оптимизируют функции с
оптимумом, расположенном в так называемом «узком горле», – участке, на котором
наблюдается резкий спад или скачок значений целевой функции. Результаты
экспериментов показали, что проблема «узкого горла» может быть эффективно
решена путем многократного запуска эволюционного поиска или с помощью хорошо
подобранных параметров эволюционный метод способен отыскать глобальный оптимум
даже в «узком горле».
Исследование методов эволюционного поиска показало, что наибольшее
влияние на эффективность эволюционного поиска оказывают операторы скрещивания
и мутации. Кроме того, выявлено, что применение эволюционных методов является
целесообразным при оптимизации сложных функций, обладающих высокой степенью
нелинейности и большим количеством переменных, описывающих сложные объекты
и процессы.
Литература
1. Химмельблау Д. Прикладное нелинейное программирование. – М.: Мир, 1974. – 534 с.
2. Дубровін В.І., Субботін С.О. Методи оптимізації та їх застосування в задачах навчання нейронних
мереж: Навчальний посібник. – Запоріжжя: ЗНТУ, 2003. – 136 с.
3. Holland J.H. Adaptation in natural and artificial systems. – Аnn Arbor: The University of Michigan
Press, 1975. – 97 p.
4. Haupt R., Haupt S. Practical Genetic Algorithms. – New Jersey: John Wiley & Sons, 2004. – 261 p.
5. Yao X. An Overview of Evolutionary Computation // Chinese Journal of Advanced Software
Research. – 1996. – № 3. – P. 12-29.
6. The Practical Handbook of Genetic Algorithms. Volume I. Applications / Ed. by L.D. Chambers. –
Florida: CRC Press, 2000. – 520 p.
7. The Practical Handbook of Genetic Algorithms. Volume II. New Frontiers / Ed. by L.D. Chambers. –
Florida: CRC Press, 2000. – 421 p.
8. The Practical Handbook of Genetic Algorithms. Volume III. Complex Coding Systems / Ed. by Lance
D. Chambers. – Florida: CRC Press LLC, 2000. – 659 p.
С.О. Субботін, А.О. Олійник
Порівняльний аналіз методів еволюційного пошуку
Досліджуються методи еволюційного пошуку при розв’язку оптимізаційних задач. Визначено задачі,
які є важко розв’язуваними за допомогою еволюційних методів. Виявлено комбінації еволюційних
операторів, що дозволяють ефективно вирішувати різні задачі оптимізації.
S.А. Subbotin, A.А. Oleynik
The Comparative Analysis of Evolutionary Search Methods
Evolutionary search methods for the decision of optimization problems are investigated. Problems which are
difficultly solved with the help of evolutionary methods are determined. The combinations of evolutionary
operators allowing effectively to solve various problems of optimization are revealed.
Статья поступила в редакцию 18.09.2007.
|
| id | nasplib_isofts_kiev_ua-123456789-6709 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T15:21:20Z |
| publishDate | 2008 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Субботин, С.А. Олейник, А.А. 2010-03-15T13:37:34Z 2010-03-15T13:37:34Z 2008 Сравнительный анализ методов эволюционного поиска / С.А. Субботин, А.А. Олейник // Штучний інтелект. — 2008. — № 2. — С. 44-49. — Бібліогр.: 8 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/6709 519.6:004.93 Исследуются методы эволюционного поиска при решении оптимизационных задач. Определены задачи, которые являются трудно разрешимыми с помощью эволюционных методов. Выявлены комбинации эволюционных операторов, позволяющие эффективно решать различные задачи оптимизации. Досліджуються методи еволюційного пошуку при розв’язку оптимізаційних задач. Визначено задачі, які є важко розв’язуваними за допомогою еволюційних методів. Виявлено комбінації еволюційних операторів, що дозволяють ефективно вирішувати різні задачі оптимізації. Evolutionary search methods for the decision of optimization problems are investigated. Problems which are difficultly solved with the help of evolutionary methods are determined. The combinations of evolutionary operators allowing effectively to solve various problems of optimization are revealed. ru Інститут проблем штучного інтелекту МОН України та НАН України Моделирование объектов и процессов Сравнительный анализ методов эволюционного поиска Порівняльний аналіз методів еволюційного пошуку The Comparative Analysis of Evolutionary Search Methods Article published earlier |
| spellingShingle | Сравнительный анализ методов эволюционного поиска Субботин, С.А. Олейник, А.А. Моделирование объектов и процессов |
| title | Сравнительный анализ методов эволюционного поиска |
| title_alt | Порівняльний аналіз методів еволюційного пошуку The Comparative Analysis of Evolutionary Search Methods |
| title_full | Сравнительный анализ методов эволюционного поиска |
| title_fullStr | Сравнительный анализ методов эволюционного поиска |
| title_full_unstemmed | Сравнительный анализ методов эволюционного поиска |
| title_short | Сравнительный анализ методов эволюционного поиска |
| title_sort | сравнительный анализ методов эволюционного поиска |
| topic | Моделирование объектов и процессов |
| topic_facet | Моделирование объектов и процессов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6709 |
| work_keys_str_mv | AT subbotinsa sravnitelʹnyianalizmetodovévolûcionnogopoiska AT oleinikaa sravnitelʹnyianalizmetodovévolûcionnogopoiska AT subbotinsa porívnâlʹniianalízmetodívevolûcíinogopošuku AT oleinikaa porívnâlʹniianalízmetodívevolûcíinogopošuku AT subbotinsa thecomparativeanalysisofevolutionarysearchmethods AT oleinikaa thecomparativeanalysisofevolutionarysearchmethods |