О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах
Рассматриваются потенциальные возможности использования генетического алгоритма для глобальной оптимизации произвольных мультимодальных функций, зависящих от многих переменных, заданных на множествах дискретных и/или непрерывных значений Розглядаються потенційні можливості використання генетичних ал...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/161681 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах / В.А. Пепеляев, Ю.М. Черный // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 100-108. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-161681 |
|---|---|
| record_format |
dspace |
| spelling |
Пепеляев, В.А. Черный, Ю.М. 2019-12-18T13:12:06Z 2019-12-18T13:12:06Z 2019 О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах / В.А. Пепеляев, Ю.М. Черный // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 100-108. — Бібліогр.: 9 назв. — рос. 2616-5619 https://nasplib.isofts.kiev.ua/handle/123456789/161681 519.6, 519.8 Рассматриваются потенциальные возможности использования генетического алгоритма для глобальной оптимизации произвольных мультимодальных функций, зависящих от многих переменных, заданных на множествах дискретных и/или непрерывных значений Розглядаються потенційні можливості використання генетичних алгоритмів для глобальної оптимізації довільних мультимодальних функцій, що залежать від багатьох змінних, визначених на множинах дискретних та/або неперервних значень. The potential possibilities of using a genetic algorithm for the global optimization of arbitrary multimodal functions depending on many variables defined on sets of discrete and/or continuous values are considered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах Про можливість використання генетичних алгоритмів в оптимізаційно-імітаційних експериментах The possibilities of the using genetic algorithms in simulation optimization Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах |
| spellingShingle |
О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах Пепеляев, В.А. Черный, Ю.М. |
| title_short |
О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах |
| title_full |
О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах |
| title_fullStr |
О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах |
| title_full_unstemmed |
О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах |
| title_sort |
о возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах |
| author |
Пепеляев, В.А. Черный, Ю.М. |
| author_facet |
Пепеляев, В.А. Черный, Ю.М. |
| publishDate |
2019 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Про можливість використання генетичних алгоритмів в оптимізаційно-імітаційних експериментах The possibilities of the using genetic algorithms in simulation optimization |
| description |
Рассматриваются потенциальные возможности использования генетического алгоритма для глобальной оптимизации произвольных мультимодальных функций, зависящих от многих переменных, заданных на множествах дискретных и/или непрерывных значений
Розглядаються потенційні можливості використання генетичних алгоритмів для глобальної оптимізації довільних мультимодальних функцій, що залежать від багатьох змінних, визначених на множинах дискретних та/або неперервних значень.
The potential possibilities of using a genetic algorithm for the global optimization of arbitrary multimodal functions depending on many variables defined on sets of discrete and/or continuous values are considered.
|
| issn |
2616-5619 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/161681 |
| citation_txt |
О возможностях применения генетических алгоритмов в оптимизационно-имитационных экспериментах / В.А. Пепеляев, Ю.М. Черный // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 100-108. — Бібліогр.: 9 назв. — рос. |
| work_keys_str_mv |
AT pepelâevva ovozmožnostâhprimeneniâgenetičeskihalgoritmovvoptimizacionnoimitacionnyhéksperimentah AT černyiûm ovozmožnostâhprimeneniâgenetičeskihalgoritmovvoptimizacionnoimitacionnyhéksperimentah AT pepelâevva promožlivístʹvikoristannâgenetičnihalgoritmívvoptimízacíinoímítacíiniheksperimentah AT černyiûm promožlivístʹvikoristannâgenetičnihalgoritmívvoptimízacíinoímítacíiniheksperimentah AT pepelâevva thepossibilitiesoftheusinggeneticalgorithmsinsimulationoptimization AT černyiûm thepossibilitiesoftheusinggeneticalgorithmsinsimulationoptimization |
| first_indexed |
2025-11-26T23:50:53Z |
| last_indexed |
2025-11-26T23:50:53Z |
| _version_ |
1850783904727826432 |
| fulltext |
100 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Рассматриваются потенциальные
возможности использования гене-
тического алгоритма для глобаль-
ной оптимизации произвольных
мультимодальных функций, зави-
сящих от многих переменных,
заданных на множествах диск-
ретных и/или непрерывных зна-
чений.
© В.А. Пепеляев, Ю.М. Черный,
2019
УДК 519.6, 519.8
В.А. ПЕПЕЛЯЕВ, Ю.М.ЧЕРНЫЙ
О ВОЗМОЖНОСТЯХ ПРИМЕНЕНИЯ
ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
В ОПТИМИЗАЦИОННО-
ИМИТАЦИОННЫХ ЭКСПЕРИМЕНТАХ
Введение. При исследовании сложных си-
стем с использованием методов и средств
имитационного моделирования необходимо
иметь в наличии инструментарий, позволя-
ющий автоматизировать процесс поиска оп-
тимальных проектов и решений [1]. Крите-
рий (критерии) оптимальности, согласно
которому сравниваются исследуемые проек-
ты, задается исследователем – лицом, при-
нимающим решения (ЛПР). Такой критерий
принято называть целевой функцией (ЦФ)
или функцией цели.
ЦФ зависит от значений входных парамет-
ров (или факторов) модели, которые ЛПР
задает перед началом сеанса имитации, и от
значений ограниченного множества выход-
ных результатов моделирования (откликов
модели на набор входных параметров). Вхо-
дные переменные определяют конфигурацию
сложной системы, влияют на характер функ-
ционирования модели в целом и ее отдель-
ных частей и объектов, и, следовательно, от-
клики модели также зависят от входных
параметров. Однако явную функциональную
зависимость значений выходных данных от
значений входных переменных в задачах мо-
делирования задать невозможно из-за слож-
ных связей и зависимостей между состав-
ными частями сложной системы. Также
выход-ные данные, как правило, являются
случайными величинами, так как при моде-
лировании учитывается возможное влияние
на реальную систему внешних случайных
воз-действий.
О ВОЗМОЖНОСТЯХ ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 101
Множество допустимых значений для каждого фактора определяется струк-
турой и назначением моделируемой системы и задается ЛПР. Среди факторов
могут присутствовать параметры, задающие как количественные характеристи-
ки системы, так и качественные (условия обмена информацией между частями и
объектами модели, приоритеты, переключатели режимов и т. п.). Область опре-
деления допустимых значений факторов может быть задана как конечным мно-
жеством дискретных значений, так и на ограниченном непрерывном отрезке.
Неявная зависимость ЦФ в моделировании от входных переменных, нали-
чие одновременно дискретных и непрерывных переменных существенно огра-
ничивают выбор методов оптимизации при проведении имитационно-
оптимизационных экспериментов. Необходимо также учитывать, что ЦФ при
исследовании сложных систем являются мультимодальными, т. е. имеют более
одного глобального и множество локальных экстремумов. Поэтому использова-
ние градиентных, субградиентных и подобных им методов в рассматриваемых
задачах практически невозможно. Одним из возможиых вариантов является
применение различных метаэвристических подходов [1, 2], которые используют
в работе предлагаемых алгоритмов информацию только о типе переменных (не-
прерывный или дискретный), значениях переменных, множестве допустимых
значений для каждой переменной и значении ЦФ, которое достигается при за-
данном входном векторе-решении. К настоящему времени предложено и иссле-
довано значительное количество разнообразных эвристических методов оптими-
зации, одним из которых является генетический алгоритм (ГА) [3, 4].
В предлагаемой работе представлен анализ различных аспектов применения
ГА в качестве метода безусловной оптимизации мультимодальных функций
многих переменных.
Задача оптимизации. Пусть имеется набор (вектор) переменных { x1, …,
xi, …, xn }, i = 1,n. Каждая переменная может принимать значения из своего
множества определения Di. Множества допустимых значений могут быть заданы
одним из трех способов [5]:
1) непрерывным отрезком [ai, bi]
1R , ai < bi ;
2) конечным отрезком [ai, bi]
1R и шагом si < bi – ai для выбора дискрет-
ных значений из отрезка;
3) конечным множеством, состоящим из k целых или действительных чисел
{a1, …, ai, …, ak}.
На множестве переменных неявно задана некоторая ЦФ F( x ), которая
для вектора значений ),...,(
1 n
xxx выдает число – значение функции. Задача
глобальной оптимизации, в частности, минимизации, заключается в поиске
такого (таких) вектора значений x *, для которого:
niDDxFxFxF
i
,1,,)()( *
*
.
В.А. ПЕПЕЛЯЕВ, Ю.М. ЧЕРНЫЙ
102 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18
Генетический алгоритм использует в своей работе заимствованную из
природы живых организмов концепцию эволюции популяции решений [3]. Каж-
дое решение представляется в виде вектора значений переменных-факторов,
прямо или косвенно (через отклики модели) влияющих на значение ЦФ, которое
используется в качестве оценки степени «приспособленности» отдельной особи-
решения, что влияет на «выживаемость» особи в процессе эволюции. В задачах
минимизации более приспособленной считается особь с меньшим значением
ЦФ, а в задачах максимизации – с большим значением. Поэтому при примене-
нии ГА оптимизации ЦФ принято называть функцией приспособленности (fitness
function – ФП).
Вектор входных переменных задачи принято называть хромосомой или осо-
бью, поскольку в работе алгоритм использует одновременно не одно решение,
а целую популяцию из M векторов. Факторы, которые формируют вектор реше-
ния, называются генами, а набор их текущих (на очередной итерации) значений
– генотипом. Текущее значение ФП особи также называют фенотипом.
Работа ГА заключается в искусственной эволюции популяции из M особей-
решений. Начальная популяция может быть задана ЛПР или генерируется алго-
ритмом случайным образом из множества допустимых значений каждого гена.
Для начальной популяции и на очередной итерации алгоритма производится
вычисление функций приспособленности особей-решений из нового поколения.
Эволюция популяции и генерация новых поколений осуществляется с помощью
специальных операторов – скрещивания (crossover, иногда – crossingover), мута-
ции (mutation) и отбора (селекции – selection).
Оператор отбора, используя значения ФП и выбранную заранее стратегию,
на очередной итерации алгоритма определяет, какие из особей-решений «выжи-
вут», т. е. останутся в популяции на следующую итерацию, а остальные решения
заменяются новым поколением. Особи в новое поколение формируются или пу-
тем скрещивания двух или более решений (родителей) из текущей популяции с
возможной мутацией новой особи, или непосредственной мутацией одного ро-
дителя без скрещивания.
Операция скрещивание заключается в том, что новая особь-потомок слу-
чайным образом получает от каждого из своих родителей значения части гено-
типа, наследуя информацию, накопленную от «выживших» на предыдущей ите-
рации особей. Оператор мутации с случайным образом выбирает от одного до
нескольких генов в потомке и также случайным образом меняет их текущие зна-
чения на другие допустимые для каждого гена значения.
За несколько десятилетий исследования и применения ГА для решения
задач разного типа было предложено множество возможных стратегий отбора,
скрещивания и мутаций [4].
Базовый принцип, положенный в основу ГА, заключается в репродукции ча-
стей генотипа (значений только нескольких переменных) от «лучших»
найденных на очередной итерации решений-родителей в новые генерируемые
решения-потомки. С помощью мутаций предполагается разнообразить поиск
по всей области допустимых решений, не ограничиваясь накопленным в попу-
О ВОЗМОЖНОСТЯХ ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 103
ляции «генофондом». Таким способом алгоритм пытается собрать оптимальное
решение как бы «по частям». Одинаковые значения части генотипа у нескольких
особей называются шаблоном.
Дж. Холланд [3], один из пионеров в разработке теории ГА, описавший
репродуктивный план эволюции решений, сформулировал и доказал теорему
шаблонов о возможности сходимости алгоритма путем отбора особей с лучши-
ми ФП и дальнейшего наследования их «генетического материала».
Формат представления и использования данных в оптимизационно-
имитационных экспериментах. Теоретически ГА может работать с перемен-
ными любого типа – дискретными и непрерывными. На начальном этапе разви-
тия теории генетических алгоритмов последние работали, как правило, с бито-
выми строками, в которые кодировались и декодировались значения перемен-
ных других типов. В работе [3] такому преобразованию посвящен целый раздел.
В дальнейшем генетическими стали называть и алгоритмы, работающие и непо-
средственно со значениями переменных.
Однако, при больших размерностях задачи и большом количестве допусти-
мых значений переменных пространство поиска для ГА возрастает экспоненци-
ально, что значительно усложняет и замедляет работу алгоритма. При оптими-
зации функций от непрерывных переменных решение ищется с некоторой
допустимой точностью, что позволяет заменять непрерывный отрезок значений
его аналогом с применением некоторого шага дискретизации (квантования).
В задачах моделирования, особенно на начальных этапах исследования си-
стем, допустимые интервалы значений, если позволяет тип данных, разбиваются
на конечное количество уровней квантования, каждый из которых может содер-
жать не одно значение, а множество значений. При квантовании данных предпо-
лагается, что значения ФП не очень чувствительны к вариации переменной
в пределах одного уровня. Таким образом, в оптимизационно-имитационных
экспериментах ГА работает в первую очередь с индексами уровней квантования,
а лишь затем непосредственно со значениями переменных. В работе [5] рас-
сматриваются структуры шаблонов представления входных данных для оптими-
зационно-имитационных экспериментов и возможность использования предла-
гаемых шаблонов при применении ГА в качестве метода оптимизации.
Генерация тестовых функций приспособленности (целевых функций)
для сравнительного анализа эффективности применения ГА в задачах моделиро-
вания осуществлялась с использованием предложенной в работе [6] методике.
ФП F( x ) для задачи глобальной оптимизации строится с помощью m специаль-
ных функций gi ( x ) следующим образом:
)(min)( xgxF
ii
, (1)
где
)*exp(*)()(
iiii
QuCHHxg , ui > 0, Ci < H , Ci , H 1R , (2)
n
j
p
ijjji
jaxkxQ 1 ||*)( , kj > 0, pj > 0,
В.А. ПЕПЕЛЯЕВ, Ю.М. ЧЕРНЫЙ
104 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18
jj Dx , jij Da , i = 1,m, j = 1,n. (3)
Каждая из функций gi ( x ) имеет один минимум со значением Ci в точке
x = (ai1,…,ain), а функция F( x ) имеет m минимумов, локальных или глобальных
в зависимости от значений Ci .
Параметры kj и pj позволяют при тестировании алгоритмов изменять чув-
ствительность ЦФ к отдельной переменной, а с помощью коэффициента ui име-
ется возможность увеличивать и уменьшать вероятность попадания пробных
решений в окрестности точек экстремумов.
Функцию, заданную по формулам (1) – (2), принято называть «полем для
гольфа», так как она имеет практически постоянное значение H почти на всей
области определения, за исключением точек минимумов функций gi( x ) и их
окрестностей, образующих как бы «лунки» на ровной поверхности. Чтобы
усложнить для различных алгоритмов, в том числе и ГА, задачу поиска опти-
мальных решений, для задания ФП (1) кроме функций типа (2) также возможно
использовать периодическую функцию в виде
g0( x ) = K – (K – L)*cos(φ( x )), maxi Ci < L < K ≤ H, (4)
где φ( x ) - некоторая функция, зависящая от всех или нескольких входных пе-
ременных. Функция (4) имеет множество локальных минимумов со значением L
в точках, в которых φ( x ) = 2πs (s = 0, ±1, ±2,…), что позволяет создавать
«взрыхленную» поверхность для ФП. Условия, заданные при определении
функции g0( x ) гарантируют, что все значения Ci будут меньше любого значения
g0( x ).
Если исследователя при проведении экспериментов для оценивания эффек-
тивности алгоритмов оптимизации не интересует расположение точек миниму-
мов функции (4), то тип функции φ( x ) не имеет особого значения. Это может
быть линейная, полиномиальная, тригонометрическая или иная функция от
переменных задачи, как, например, предлагается в [7].
Организация экспериментов. Исследование возможностей применения ГА
в качестве метода оптимизации в задачах имитационного моделирования прово-
дилось на четырех целевых функциях, которые отличались типом входных пе-
ременных и имели схожие параметры для конфигурации поверхности отклика
(значений ЦФ).
В частности, все функции имели по 50 входных переменных:
– функция-1 F1: все переменные булевого типа, могли принимать только два
значения - 0 или 1;
– функция-2 F2: все переменные дискретного типа, количество допустимых
значений - от 2 до 1000 для разных переменных в одной задаче;
– функция-3 F3: все переменные заданы как непрерывные с допустимыми
интервалами значений (в одной задаче) от 10 до 10000, но с дискретизацией до
0,1 % от ширины интервала значений каждой переменной;
О ВОЗМОЖНОСТЯХ ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 105
– функция-4 F4: переменные смешанного типа: присутствуют данные всех
типов – от булевых (дискретных с двумя значениями) до непрерывных.
Для всех четырех функций случайным образом на множествах их определе-
ния были сгенерированы 10 точек минимумов с известными (контролируемыми)
для экспериментатора значениями переменных – 1 глобальный минимум со зна-
чением ЦФ равным 400 и 9 локальных минимумов с различными значениями
ЦФ в интервале от 450 до 750. Различные значения глобального и локальных
минимумов позволяли легко определять по ходу процесса оптимизации какие
решения находит алгоритм.
Параметры k и p в функциях (3) подбирались таким образом, чтобы для пе-
ременных с малым количеством допустимых значений (до 5) каждое значение
было бы относительно «изолировано» от остальных (например, при p < 1), а для
переменных с большим количеством допустимых значений при p > 1 выполня-
лось бы, например, условие *| | 0,03pk x y (x и y – соседние допустимые зна-
чения переменной). Начальные значения параметров ui для всех функций
gi ( x ) были заданы равными, что обеспечивало приблизительно равные вероят-
ности попадания алгоритма в окрестности всех заданных экстремальных точек.
На некоторых этапах экспериментов использовалась также функция g0( x )
вида (4) с параметром L = 1000.
Сложность задачи оптимизации в рассматриваемых примерах можно оце-
нить такими основными параметрами:
– количество всех возможных комбинаций значений переменных (альтерна-
тивных вариантов для алгоритма) – от 1,12*1015 для функции-1 до более,
чем 1080 (в зависимости от уровня дискретизации) для функции-3;
– максимальное количество значений для одной переменной (с учетом дис-
кретизации непрерывных) – 1001;
- количество переменных – 50.
Общее количество всех возможных комбинаций значений переменных поз-
воляет оценить потенциальное количество возможных альтернатив в случае
прямого перебора вариантов, а количество допустимых значений для одной пе-
ременной является важной характеристикой для оценки вероятности выбора
конкретного значения при мутации гена.
Эксперименты по оптимизации заданных функций проводились для иссле-
дования поведения ГА с такими параметрами:
– вероятность скрещивания – 0,8;
– тип скрещивания – равномерное скрещивание;
– вероятность мутации после скрещивания – 0,2;
– максимальное количество одновременно мутирующих генов – до 10
(20 % от общего количества);
– размер популяции – 100 (для функций F1,2,3,4 ) или 300 (для функций F3,4 );
– часть нового поколения в популяции – 50 % от размера популяции;
– рассматривались две стратегии отбора: элитный или равномерный отбор.
В.А. ПЕПЕЛЯЕВ, Ю.М. ЧЕРНЫЙ
106 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18
Равномерный тип скрещивания был выбран потому, что все переменные рас-
сматривались как независимые одна от другой, и их индексация (порядок распо-
ложения в векторе-решении) осуществлялась произвольным образом.
В качестве стратегий отбора исследовались:
1) элитный отбор – особи с наилучшими значениями ФП принимают уча-
стие в создании нового поколения и остаются на следующий этап эволюции,
а особи с худшими значениями ФП удаляются из популяции, не оставляя потом-
ков и освобождая место для особей нового поколения;
2) равномерный отбор – из популяции удаляются «близкие» по генотипу
особи независимо от значений ФП, но перед удалением все особи популяции
с одинаковой вероятностью могут принять участие в создании нового поколе-
ния. «Близость» особей в алгоритме определялась по одной из двух метрик –
расстоянию Хэмминга или расстояние городских кварталов (манхэттенское рас-
стояние) [8]. Если одна из метрик имела значение меньше 5 (10 % от длины
хромосомы), то особи считались «близкими».
Проведение экспериментов для анализа поведения ГА на задачах разной
сложности осуществлялось в три этапа.
Этап 1. Все четыре целевые функции F1,2,3,4 имели вид «поля для гольфа»
с ровной поверхностью отклика и в одном варианте экспериментов с тремя
известными точками экстремума (один глобальный), а затем в другом варианте –
с десятью точками экстремума. При этом коэффициенты ui при построении каж-
дой из ЦФ имели равные значения, и, следовательно, точки экстремумов имели
примерно равные вероятности нахождения их алгоритмом.
Этап 2. Коэффициент u изменялся (уменьшался) у одной или нескольких то-
чек, чтобы увеличить вероятность попадания алгоритма в окрестность данной
точки.
Этап 3. При построении по формулам (1) – (3) функций F1,2,3,4 к известным
контролируемым экстремальным точкам добавлялась функция вида (4), что ко-
ренным образом изменяло ландшафт поверхности отклика ЦФ.
На всех этапах отдельно исследовалось применение обеих стратегий отбора.
Для обнаружения устойчивых тенденций и характерных свойств в работе
ГА для каждой конфигурации ЦФ F1,2,3,4 или изменении параметров настройки
ГА (стратегии отбора и размера популяции) выполнялось по 80 –120 запусков
алгоритма для набора минимальных статистических данных.
При проведении экспериментов не ставилась задача обязательно найти
с помощью ГА глобальный минимум ЦФ. Основной целью было получить ин-
формацию об эффективности поиска и обнаружения новых лучших решений
при различной геометрии поверхности отклика ЦФ и разных размерах областей
допустимых решений. Поэтому в качестве критерия остановки работы алгорит-
ма задавалось предельное значение рассмотренных алгоритмом в ходе эволюции
вариантов (количество вычислений ЦФ), которое не превышало 300000, а в не-
которых экспериментах было менее 50000. Выбор таких порядков чисел для
количества рассмотренных вариантов был обусловлен тем обстоятельством, что
в имитационных экспериментах для получения значения ЦФ для одного вариан-
О ВОЗМОЖНОСТЯХ ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 107
та решения требуется выполнять прогон модели, что часто требует значитель-
ных вычислительных и временных затрат. Поэтому алгоритмы, требующие для
нахождения оптимального или хотя бы приближения к оптимальному решению
более 104 – 5*105 вычислений ЦФ независимо от сложности решаемой задачи, не
могут рассматриваться для использования в оптимизационно-имитационных
экспериментах.
Результаты экспериментов и их анализ. На этапе 1, как и ожидалось, для
всех функций алгоритм с примерно равной вероятностью обнаруживал одну из
экстремальных точек. Скорость нахождения такой точки существенно зависела
от типа данных, на которых была задана тестовая ЦФ, т. е. от общего количества
допустимых вариантов. Если обнаруженная точка оказывалась локальным экс-
тремумом, то алгоритму в дальнейшей работе до момента останова практически
не удавалось перейти к глобальному минимуму или к лучшему локальному.
Алгоритм продолжал порождать похожие по генотипу решения, которые не
могли быть существенно изменены с помощью оператора мутации, который
в проводимых экспериментах мог изменить не более 20 % генов в особи.
На этапе 2 алгоритм чаще находил ту точку, для которой повышалась веро-
ятность ее обнаружения. При этом участились случаи перехода в эту точку из
других локальных экстремумов с худшими значениями ЦФ. Однако, если для
повышения вероятности обнаружения выбиралась точка локального экстремума,
то переход из нее к глобальному экстремуму оставался практически неосуще-
ствимым, если вероятность обнаружения глобального экстремума была ниже
вероятности попадания в этот локальный минимум.
Добавление на этапе 3 функции вида (4) существенно осложнило и замедли-
ло работу алгоритма даже для относительно простой задачи оптимизации
ЦФ F1 . Алгоритм подолгу «застревал» в локальных минимумах функции (4),
особенно, если вероятности обнаружить контролируемые экстремальные точки
были относительно малыми.
Проведенные эксперименты показали низкую эффективность ГА при гло-
бальном поиске новых вариантов решений в задачах оптимизации произвольных
функций. Но при локальном поиске среди решений с близкими генотипами
и значительно ограниченном количестве доступных значений для мутаций ГА
показал хорошую производительность и точность нахождения решений. Для по-
вышения эффективности глобального поиска при использовании ГА за многие
годы были предложены и продолжают предлагаться различные стратегии
повышения популяционного разнообразия [9], однако специфические свойства
работы ГА таковы, что применение таких стратегий несколько повышает воз-
можности глобального поиска, но существенно не влияет на его эффективность.
Выводы. Применение генетического алгоритма в качестве основного мето-
да глобальной оптимизации при проведении имитационно-имитационных экс-
периментов не может рассматриваться как эффективный инструмент глобальной
оптимизации. ГА стремится воспроизводить значения переменных из «лучших»
на очередном этапе решений при генерации новых поколений, однако такая
В.А. ПЕПЕЛЯЕВ, Ю.М. ЧЕРНЫЙ
108 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18
стратегия не позволяет вести активный поиск по всему пространству решений.
ГА может применяться как вспомогательный инструмент уточнения найденных
другими алгоритмами глобального поиска «оптимальных» решений.
В.А. Пепеляєв, Ю.М. Чорний
ПРО МОЖЛИВІСТЬ ВИКОРИСТАННЯ ГЕНЕТИЧНИХ АЛГОРИТМІВ В
ОПТИМІЗАЦІЙНО-ІМІТАЦІЙНИХ ЕКСПЕРИМЕНТАХ
Розглядаються потенційні можливості використання генетичних алгоритмів для глобальної
оптимізації довільних мультимодальних функцій, що залежать від багатьох змінних,
визначених на множинах дискретних та/або неперервних значень.
V.А. Pepeliayev, Yu.M. Czornyy
THE POSSIBILITIES OF THE USING GENETIC ALGORITHMS IN SIMULATION
OPTIMIZATION
The potential possibilities of using a genetic algorithm for the global optimization of arbitrary
multimodal functions depending on many variables defined on sets of discrete and/or continuous
values are considered.
Список литературы
1. Пепеляев В.А. К вопросу об интеграции методов оптимизации и имитационного
моделирования. Теория оптимальных решений. К.: Ин-т кибернетики имени
В.М. Глушкова НАН Украины. 2003. № 2. С. 51 – 60.
2. Пепеляев В.А., Сахнюк М.А., Черный Ю.М., Шваб Н.Д. К вопросу о реализации мета-
эвристических стратегий оптимизации моделирования. Компьютерная математика. К.:
Ин-т кибернетики имени В.М. Глушкова НАН Украины. 2005. № 2. С. 26–33.
3. Holland J.H. Adaptation in natural and artificial systems: An introductory analysis with
applications to biology, control, and artificial intelligence. Univ. Michigan Press. 1975. 226 p.
4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: ФИЗМАТ-
ЛИТ, 2010. 368 с.
5. Бигдан В.Б., Криковлюк А.А., Пепеляев В.А. Унификация структур входных данных для
оптимизационных алгоритмов в имитационных экспериментах. Компьютерная
математика. К.: Ин-т кибернетики имени В.М. Глушкова НАН Украины. 2017. № 1.
С. 45 – 54.
6. Пепеляев В.А., Черный Ю.М. Принципы построения целевых функций для тестирования
алгоритмов глобальной оптимизации. Компьютерная математика. К.: Ин-т кибернетики
имени В.М. Глушкова НАН Украины. 2017. № 2. С. 62 – 71.
7. Rönkkönen J., Li X., Kyrki V., Lampinen J. A generator for multimodal test functions with
multiple global optima. Proceedings of the 7th International Conference on Simulated Evolu-
tion and Learning (SEAL ’08), Berlin, Heidelberg. Springer-Verlag. 2008. P. 239 – 248.
8. Деза Е.И., Деза М.-М. Энциклопедический словарь расстояний. М.: Наука, 2008. 446 с.
9. Gupta D., Ghafir Sh. An Overview of methods maintaining Diversity in Genetic Algorithms.
International Journal of Emerging Technology and Advanced Engineering. 2012. Vol. 2,
Issue 5. P. 56 – 60.
Получено 12.03.2019
|