Применение генетического алгоритма для решения краевых задач

Запропоновано генетичний алгоритм для розв’язання крайових задач для звичайних диференціальних рівнянь другого порядку і крайових задач для еліптичних рівнянь. Наведено результати чисельних експериментів розв’язання лінійних і нелінійних задач. Знайдені розв'язки подаються в аналітичній формі....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2015
Автор:	Вакал, Л.П.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Назва видання:	Проблемы управления и информатики
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/208019
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Применение генетического алгоритма для решения краевых задач / Л.П. Вакал // Проблемы управления и информатики. — 2015. — № 4. — С. 51-59. — Бібліогр.: 14 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208019
record_format	dspace
spelling	irk-123456789-2080192025-10-19T00:18:43Z Применение генетического алгоритма для решения краевых задач Застосування генетичного алгоритму для розв'язання крайових задач Using genetic algorithm for solving boundary value problems Вакал, Л.П. Оптимальное управление и методы оптимизации Запропоновано генетичний алгоритм для розв’язання крайових задач для звичайних диференціальних рівнянь другого порядку і крайових задач для еліптичних рівнянь. Наведено результати чисельних експериментів розв’язання лінійних і нелінійних задач. Знайдені розв'язки подаються в аналітичній формі. Досліджено вплив параметрів генетичного алгоритму на точність розв’язків і швидкість збіжності. A genetic algorithm for solving boundary value problems for second-order ordinary differential equations and boundary value problems for elliptic equations is proposed. Results of numerical experiments for solving linear and nonlinear problems are presented. The obtained solutions are presented in the analytical form. The influence of genetic algorithm parameters on the solutions accuracy and convergence rate is investigated. 2015 Article Применение генетического алгоритма для решения краевых задач / Л.П. Вакал // Проблемы управления и информатики. — 2015. — № 4. — С. 51-59. — Бібліогр.: 14 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208019 519.6:004.021 10.1615/JAutomatInfScien.v47.i8.50 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Вакал, Л.П. Применение генетического алгоритма для решения краевых задач Проблемы управления и информатики
description	Запропоновано генетичний алгоритм для розв’язання крайових задач для звичайних диференціальних рівнянь другого порядку і крайових задач для еліптичних рівнянь. Наведено результати чисельних експериментів розв’язання лінійних і нелінійних задач. Знайдені розв'язки подаються в аналітичній формі. Досліджено вплив параметрів генетичного алгоритму на точність розв’язків і швидкість збіжності.
format	Article
author	Вакал, Л.П.
author_facet	Вакал, Л.П.
author_sort	Вакал, Л.П.
title	Применение генетического алгоритма для решения краевых задач
title_short	Применение генетического алгоритма для решения краевых задач
title_full	Применение генетического алгоритма для решения краевых задач
title_fullStr	Применение генетического алгоритма для решения краевых задач
title_full_unstemmed	Применение генетического алгоритма для решения краевых задач
title_sort	применение генетического алгоритма для решения краевых задач
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2015
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/208019
citation_txt	Применение генетического алгоритма для решения краевых задач / Л.П. Вакал // Проблемы управления и информатики. — 2015. — № 4. — С. 51-59. — Бібліогр.: 14 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT vakallp primeneniegenetičeskogoalgoritmadlârešeniâkraevyhzadač AT vakallp zastosuvannâgenetičnogoalgoritmudlârozvâzannâkrajovihzadač AT vakallp usinggeneticalgorithmforsolvingboundaryvalueproblems
first_indexed	2025-10-19T01:07:22Z
last_indexed	2025-10-20T01:08:39Z
_version_	1846461092177379328
fulltext	© Л.П. ВАКАЛ, 2015 Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 51 УДК 519.6:004.021 Л.П. Вакал ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ КРАЕВЫХ ЗАДАЧ Введение Генетические алгоритмы — это современный мощный инструмент реше- ния сложных многопараметрических задач оптимизации. Идея генетического алгоритма (ГА) взята из живой природы и заключается в компьютерной орга- низации эволюционного процесса создания, модификации и отбора лучших решений (в терминах ГА — особей) в целях появления новых, еще лучших вари- антов решения задачи [1]. Каждая особь в ГА кодируется в виде строки (хромосо- мы), состоящей из генов, в которых хранится информация о соответствующих па- раметрах решения. Оценкой качества закодированного в геноме решения служит значение функции приспособленности. Генетические алгоритмы обладают рядом преимуществ: поиск решений осу- ществляется в них сразу из целого множества точек — популяции особей, исполь- зуют только значения функции приспособленности и не требуют другой информации о поведении функции, относительно стойки к попаданию в локальные оптимумы, просты в реализации, могут использоваться для широкого класса задач и др. [2]. Первые публикации о применении принципов биологической эволюции к решению оптимизационных задач появились в конце 1960-х гг. А в 1975 году вышла известная работа Дж. Холланда «Адаптация в естественных и искусствен- ных системах» [3], где собственно и был предложен первый генетический алго- ритм. В дальнейшем в силу своей универсальности и высокой эффективности ге- нетические алгоритмы получили широкое распространение для решения задач поиска и оптимизации в различных областях науки и техники [1, 2, 4, 5]. Недавно появились первые публикации об использовании ГА для решения некоторых краевых задач математической физики [6, 7]. В данной статье предлагается ГА для нахождения приближенного реше- ния (в виде аналитического выражения) краевых задач для обыкновенных диф- ференциальных уравнений второго порядка и краевых задач для эллиптических уравнений, а также анализируются результаты численных экспериментов по ре- шению тестовых задач и по исследованию влияния ряда параметров ГА на точ- ность результатов и скорость сходимости алгоритма. Постановки задач Исследования физических процессов в баллистике, теории упругости, теории колебаний, механике жидкостей и газов, динамике твердого тела, оптимальном управлении и других областях науки и техники часто приводят к краевым задачам для обыкновенных дифференциальных уравнений второго порядка. Эта задача ставится следующим образом: найти функцию ),(xuu  удовлетворяющую внут- ри отрезка ],[ ba дифференциальному уравнению ,0),,,(  uuuxf (1) а на концах отрезка — краевым условиям ,0)](),([1  auaug .0)](),([2  bubug (2) В общем случае и уравнение (1), и краевые условия (2) могут быть нелинейными. Найти точное решение задачи (1), (2) (предполагается, что решение существует) в эле- 52 ISSN 0572-2691 ментарных функциях удается только в отдельных случаях. Поэтому актуальной оста- ется проблема нахождения приближенного решения, особенно нелинейных задач. При решении краевой задачи (1), (2) приближенно-аналитическими методами поступают таким образом. Выбирают дважды непрерывно дифференцируемую на ],[ ba функцию ),,,,;( 21 ncccxvv  которая при любых значениях входящих в нее параметров nccc ,,, 21  точно удовлетворяет краевым условиям (2). Эту функ- цию подставляют в левую часть уравнения (1) и получают дифференциальную невязку ),,,,(),,,;( 21 vvvxfcccxR n  (3) являющуюся определенной характеристикой уклонения приближенного реше- ния v от неизвестного точного решения u краевой задачи. Далее стараются най- ти такие значения параметров ,,,, 21 nccc  чтобы сделать функцию R наименее уклоняющейся от нуля в каком-то смысле в интересующей нас области [8]. Раз- личные реализации этого требования приводят к различным методам решения краевой задачи: метод коллокации, Галеркина, наименьших квадратов (инте- гральный и дискретный), чебышевский метод и др. [8–10]. Исследования стационарных процессов разной физической природы (теплопро- водность, диффузия, равновесие, задачи электростатики, магнитостатики, гидродина- мики и т.д.) приводят к краевым задачам для дифференциальных уравнений с частны- ми производными эллиптического типа [11]. В случае двух независимых переменных x и y эта задача формулируется следующим образом: найти функцию ),( yxuu  класса ),()( 12 DCDC  которая в области 2RD  удовлетворяет уравнению ),,(),(),(),( 2 2 2 2 yxguyxr y u yxq x u yxp y u x u Lu              (4) а на ее границе  — краевому условию ),,( yxw n u u      (5) где ,p ,q ,r ,f g — непрерывные функции, n  — внешняя нормаль к ,  и  — заданные числа, причем .022  Для решения краевой задачи (4), (5) можно использовать упомянутые выше приближенно-аналитические методы, подобно тому, как они применялись для приближенного решения обыкновенных дифференциальных уравнений. В этом случае подбирают функцию ),,,,;,( 21 ncccyxvv  которая при любых значени- ях параметров kc удовлетворяет краевым условиям (5), и определяют постоян- ные kc так, чтобы дифференциальная невязка R ),(),,,;,( 21 yxgLvcccyxR n  (6) принимала возможно меньшее значение. В итоге определение оптимальных значений параметров kc решений за- дач (1), (2) и (4), (5) сводится в приближенно-аналитических методах к решению систем алгебраических уравнений. В случае нелинейных задач системы также бу- дут нелинейными, и для их решения необходимо применение численных методов. Кроме того, вычисление матриц коэффициентов и координат векторов правых частей систем уравнений требует в ряде методов интегрирования по всему отрез- ку. Явное вычисление интегралов возможно только в отдельных несложных слу- чаях, как правило, интегралы приходится вычислять приближенно. В силу того, что традиционные приближенно-аналитические методы имеют сла- бые стороны, для нахождения решений краевых задач (1), (2) и (4), (5) предлагается другой подход. Он заключается в том, что задача определения наилучших значений параметров nccc ,,, 21  рассматривается как оптимизационная задача поиска мини- Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 53 мума функции уклонения (чебышевского, среднеквадратического или др.) дифферен- циальной невязки R от нуля, и для решения оптимизационной задачи применяется ге- нетический алгоритм. При таком подходе искомое решение представляется в виде хромосомы, генами которой являются значения параметров .kc В этой работе исполь- зуется чебышевское уклонение, определяемое как максимальное значение модуля не- вязки в рассматриваемой области [10, 12]. Кроме того, в численном эксперименте для сравнения приведены результаты решения задачи минимизации среднеквадратическо- го уклонения. Генетический алгоритм для решения поставленных краевых задач Схема стандартного ГА состоит из таких основных шагов. 1. Инициализация (создание начального поколения популяции). 2. Оценивание особей популяции по их значениям функции приспособленности. 3. Моделирование эволюционного процесса: отбор родителей для создания потомства, создание потомков отобранных родительских пар (скрещивание), му- тация потомков, формирование нового поколения из расширенной популяции ро- дителей и потомков (редукция и селекция). 4. Проверка критерия окончания алгоритма, и в случае его невыполнения по- вторение эволюционного процесса с шага 2. Существуют различные варианты реализации стандартной схемы ГА, отли- чающиеся формой представления хромосом (двоичное и вещественное кодирование), операторами скрещивания, мутации и селекции, процедурами отбора родителей, кри- териями завершения алгоритма и т.д. Выбор того или иного варианта реализации стандартных составляющих при разработке ГА для решения конкретной задачи зави- сит, в частности, от особенностей предметной области, структуры данных и др. Для решения поставленной задачи определения оптимальных значений пара- метров nccc ,,, 21  нами разработан ГА, в котором используется представление генов хромосомы напрямую в виде вещественных чисел. Алгоритмы такого типа называются ГА с вещественным кодированием или непрерывными ГА. Они были созданы специально для поиска в непрерывных пространствах большой размер- ности. В большинстве случаев ГА с вещественным кодированием выполняют по- иск оптимума лучше и быстрее, чем ГА с двоичным кодированием [13]. В предлагаемом алгоритме хромосома ,kS кодирующая k-ю особь, состоит из n генов ),,,,( 21 knkkk sssS  .,1 Nk  Значение гена kis соответствует неко- торому значению параметра ic приближенного решения ,v т.е. каждый ген отвеча- ет за одну переменную. Эволюция популяции особей (хромосом) моделируется по- следовательностью поколений )},({ tSk где t — номер поколения ( ,2,1,0t ). Функция ,v которая задается пользователем, должна точно удовлетворять краевым условиям при любых значениях параметров. Если краевые условия (2) линейны (при этом уравнение (1) может быть и нелинейным), то обычно полагают ),()(),,;( 1 01 xcxccxv kk n k n     где k — линейно независимые, дважды непрерывно дифференцируемые на ],[ ba функции, удовлетворяющие однородным краевым условиям, а функция 0 — неод- нородным краевым условиям. В качестве функций k обычно выбирают много- члены, тригонометрические функции и т.п. Предлагаемый алгоритм имеет такие особенности реализации стандартной схемы ГА. 1. Инициализация. В начальное (нулевое) поколение )}0({ kS включаются N особей .,,, 21 NSSS  Гены knkk sss ,,, 21  хромосомы kS ( Nk ,1 ) — это случайные числа, генерируемые с помощью датчика случайных чисел из заданно- 54 ISSN 0572-2691 го числового интервала (по умолчанию задается интервал ).]1,1[ Границы этого интервала имеют значение лишь на шаге инициализации, в дальнейшей эволюции пространство поиска является в принципе неограниченным. 2. Оценивание. Каждая особь ,kS ,,1 Nk  оценивается по ее значению функ- ции приспособленности Fit (фитнесс-функции), которое вычисляется по формуле ),()( kk SSFit  (7) где )( kS — чебышевское уклонение ),,,;,(max)( 21 1 knkkii mi k sssyxRS    . (8) При этом для краевой задачи (1), (2) дифференциальная невязка R определяется по формуле (3), а для краевой задачи (4), (5) — по формуле (6). Чем ближе значение фитнесс-функции (7) к нулю, тем более приспособленной является особь и тем ближе закодированные в ее генах значения параметров к оптимальным. Для вычисления ук- лонения (8) расчетная область покрывается сеткой, состоящей из m точек ix в случае задачи (1), (2) или m точек ),( ii yx в случае задачи (4), (5), и затем в этих точках вы- числяются значения производных дифференциальной невязки .R Значения производ- ных можно вычислить двумя способами: численным (с определенным порядком мало- сти) и аналитическим. Так как дифференцирование всегда выполняется по строгим правилам, то аналитическое вычисление производной не представляет особых трудно- стей. Кроме того, аналитически вычисленная производная может быть точнее. В про- граммной реализации ГА используется аналитическое вычисление производных. 3. Моделирование эволюционного процесса. Отбор родителей для скрещи- вания осуществляется в соответствии с процедурой парного турнирного отбора. Из популяции случайным образом выбираются две особи, и та из них, значение фитнесс-функции которой больше, помещается в промежуточный массив. После повторения этой операции N раз скрещиванию подвергаются все последователь- ные пары особей из промежуточного массива. Скрещивание выполняется на основе смешанного BLX кроссовера с 0,5. В этом случае пара родителей ),,,( 21 jnjjj sssS  и ),,,( 21 knkkk sssS  про- изводит одного потомка, у которого значением i-го гена является случайное число из интервала ],5,0,5,0[ 21 dzdz  где ),,(min1 kiji ssz  ),,(max2 kiji ssz  ,12 zzd  .,1 ni  Особенность этого кроссовера в том, что значение гена по- томка может лежать в области, выходящей за пределы значений родительских ге- нов на величину .5,0 d Показано [13], что BLX кроссовер при  0,5 превос- ходит по эффективности большинство операторов скрещивания. На шаге мутации случайным образом выбирается один потомок, у которого меняется значение одного случайного гена. Если мутации подвергается, напри- мер, ген lis особи ,lS ,Nl  то новое значение lis этого гена определяется по правилу: , lili ss где знаки  или  выбираются с равной вероятностью, d 5,0 (величина интервала d находится через значения соответствующих родительских генов), а величина  вычисляется по формуле [2] ,2)( 1 i i i      где 1)(  i с вероятностью ,/1  в противном случае ,0)(  i  — заданный па- раметр (по умолчанию ).10 Оператор мутации обеспечивает генетическое раз- нообразие популяции и таким образом помогает предотвратить застревание попу- ляции в локальных минимумах. На шаге формирования следующего поколения из расширенной популяции родителей и потомков с помощью редукции и селекции в новое поколение вклю- чаются только N особей с наименьшим значением функции приспособленности Fit (элитарный отбор). Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 55 4. Критерий окончания. Алгоритм завершает работу, если выполняется одно из двух условий: 1) значение фитнесс-функции наилучшей особи в поколении меньше заданной величины ; 2) достигнуто заданное максимальное число поколений .maxt При выполнении первого условия найденное решение будет близким к точ- ному решению задачи, но при выполнении второго условия этого утверждать нельзя (см. обсуждение результатов задачи 2). Поэтому при программной реали- зации ГА целесообразно предусмотреть выдачу сообщения о номере выполненно- го терминального условия. Предложенный алгоритм для решения краевых задач имеет ряд преимуществ: не требует модификации при переключении от линейных задач к нелинейным и от краевых задач для обыкновенных дифференциальных уравнений к краевым задачам для уравнений с частными производными эллиптического типа, находит решения нелинейных задач без применениях каких-либо численных методов, прост в реали- зации, слабо связан с конкретной структурой задачи, что позволяет использовать его для решения других подобных задач. Обсуждение результатов численных экспериментов Для проверки эффективности применения разработанного ГА для нахожде- ния решений краевых задач выполнены численные эксперименты по решению за- дач, для которых были известны их точные решения, а также проведено исследо- вание влияния контролируемых параметров (настроек) ГА на результат и ско- рость сходимости алгоритма. В качестве иллюстрации рассмотрим четыре краевые задачи и сравним ре- шения, полученные с помощью ГА, с точными решениями этих задач. Задача 1. Линейная краевая задача ,0122  uuux .0)1()0(  uu Точное решение .2 xxu  Задача 2. Линейная краевая задача ,0 xuu .0)1()0(  uu Точное решение xxu  1sin/)(sin [9]. Задача 3. Краевая задача для нелинейного дифференциального уравнения с линейными краевыми условиями ,044)( 2  uuxu ,2)0( u .4)1( u Точное решение .293 2  xxu Задача 4. Краевая задача для уравнения эллиптического типа ),1(2 2 2 2 2 xx y u x u       ,10  x ;10  y ,0),0( yu ,0),1( yu ;10  y ,0)0,( xuy ,0)1,( xuy .10  x Это задача о стационарном распределении температуры в однородной квад- ратной пластине, в середине которой действуют источники тепла интенсивностью ),1(2 xx  если коэффициент внутренней теплопроводности равен 1, края 0x и 1x пластинки поддерживаются при нулевой температуре, а другие два края теп- лоизолированы. Точное решение задачи 6/)2()( 43 xxxxu  [11]. 56 ISSN 0572-2691 Для приближенного решения краевых задач 14 выбираем функцию ,v кото- рая при любых значениях входящих в нее параметров удовлетворяет заданным краевым условиям. Пусть число параметров .2n Тогда приближенное решение в задаче 1 и 2 ищем в виде ),1()1()( 2 21 xxcxxcxv  в задаче 3 —  xxv 62)( )1()1( 2 21 xxcxxc  и в задаче 4 — )1()1()( 3 2 2 1 xxcxxcxv  (решение ищем в виде функции только переменной ,x поскольку свободный член в дифференциальном уравнении этой задачи является функцией только пере- менной x и условия на краях 0x и 1x не зависят от переменной ).y Для реализации предложенного алгоритма и решения поставленных краевых задач в системе программирования Borland Delphi была разработана соответст- вующая программа. В программе имеется две группы настроек: 1) настройки, оп- ределяющие текущую краевую задачу (само уравнение, границы области, число точек сетки, покрывающей заданную область); 2) настройки (параметры) собст- венно ГА (размер популяции, максимальное число поколений и др.). Значения па- раметров ГА определяются из потребности найти решение за наименьшее время или с наибольшей точностью и надежностью. Численные эксперименты выполнялись при следующих настройках алго- ритма: размер популяции ,150N число генов ,2n значение величины 001000000,0 (первое терминальное условие), максимальное число поколений 500max t (второе терминальное условие), расчетная область краевой задачи — отрезок ],1,0[ число точек сетки ,101m все остальные настройки ГА по умол- чанию. Поскольку в основе ГА лежит вероятностный подход, то приемлемое решение задачи можно получить только при многократных пусках алгоритма. В численном эксперименте для каждой задачи осуществлялось 15 пусков алго- ритма, и в качестве оптимального выбиралось лучшее за все пуски решение. Результаты решения краевых задач 14 с помощью предложенного алгорит- ма представлены в табл. 13. В табл. 1 приведены характеристики оптимальных решений всех четырех задач, в табл. 2 — результаты численного сравнения точ- ного и приближенного решений задачи 4 в некоторых точках расчетной области и в табл. 3 — усредненные результаты по каждой задаче за все пуски алгоритма. Анализ данных этих таблиц показывает, что полученные решения задач 1, 3 и 4 хорошо согласуются с их точными решениями. В случае задачи 2 окончание алго- ритма произошло в результате достижения максимального числа поколений по- пуляции (терминальное условие 2). И хотя найденное решение не дает высокой точности приближения, оно, тем не менее, является наилучшим приближением заданного вида (кубический многочлен) к точному решению задачи 2, что под- тверждается его полным совпадением с решением, найденным чебышевским ме- тодом [14]. Для получения более точного решения задачи 2 следует выбрать функцию v другого вида. Если решение искать, например, в виде ),1()1()1()( 3 3 2 21 xxcxxcxxcxv  то погрешность этого решения (с опти- мальными значениями ),, 321 ccc будет равна 2,010 –4 [14], что на порядок мень- ше, чем погрешность приведенного в табл. 1 решения. Таблица 1 Задача Коэффициенты решения v Значение функции Fit Абсолютная погрешность c1 c2 1  0,999999999988 2,03410 –11 4,89873510 –11 1,30423410 –12 2 0,18374688185 0,1666666667 3,416043010 –2 2,99816710 –3 3 – 3,000000000004  2,80310 –13 8,58588310 –11 9,82547410 –13 4  0,166666666692 0,166666666706 8,41578510 –11 7,25676510 –12 Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 57 Таблица 2 Значение x Точное решение )(xu Приближенное решение )(xv Абсолютная погрешность Невязка )(xR 0 0 0 0 — 0,2  0,03093333333333  0,03093333333794 4,6110 –12 5,87210 –11 0,4  0,0496  0,04960000000700 7,010 –12 7,96810 –11 0,6  0,0496  0,04960000000633 6,3310 –12 6,28810 –11 0,8  0,03093333333333  0,03093333333660 3,26810 –12 8,32010 –11 1 0 0 0 — Таблица 3 Задача Среднее число поколений Среднее значение функции Fit Среднее значение абсолютной погрешности 1 118 5,40910310 –10 7,82623610–11 2 500 3,416043010 –2 2,99816710 –3 3 109 6,81186310 –10 3,79232910 –12 4 133 6,86383810 –10 4,49304110 –11 Поскольку ГА является стохастической процедурой, оценка его эффективно- сти (надежности) осуществляется усреднением полученных результатов по мно- гократным пускам (см. табл. 3). Среднее число поколений, необходимых для вы- полнения критерия окончания алгоритма, является показателем скорости сходи- мости ГА. Как показывают расчеты, для нахождения решения краевой задачи требуется в среднем 215 поколений. Если при вычислении фитнесс-функции вместо чебышевского уклонения (8) взять среднеквадратическое уклонение, вычисляемое по формуле ,),,,;,( 1 )( 1 21 2    m i knkkiik sssyxR m S  то получим результаты, приведенные в табл. 4. В этом случае для нахождения решения необходимо в среднем 209 поколений. Таблица 4 Задача Среднее число по- колений Среднее значение функции Fit Среднее значение абсолют- ной погрешности 1 107 6,12067210 –10 1,26605010 –10 2 500 2,09556510 –2 1,74996810 –3 3 111 5,47137510 –10 4,25081110 –12 4 117 5,52598410 –10 6,37209910 –11 На рисунке наглядно представлен процесс оптимизации значений парамет- ров 1c (а) и 2c (б) в ГА. Его можно разбить на две фазы: фазу грубой настройки, ха- рактеризующейся осцилляциями кривой; и фазу тонкой настройки [6, 7]. В первой фазе, на которую приходится в среднем 30 % поколений, преобладают крупномас- штабные изменения, обеспечивающие широкую область поиска, а во второй фазе, за- нимающей 70 % поколений, происходит уточнение найденных «хороших» значений. – 0,015 20 40 60 80 100 t – 0,005 – 0,000 c2 – 0,010 0,005 0,010 0,015 0,020 б 0 – 1,10 20 40 60 80 100 t – 1,00 – 0,90 – 0,80 – 0,70 – 0,60 c1 а 58 ISSN 0572-2691 В эксперименте было выявлено, что процесс минимизации функции приспо- собленности тоже разбивается на две фазы длительностью в среднем 30 % и 70 % поколений соответственно. В первой фазе значение фитнесс-функции наилучшей особи поколения уменьшается очень быстро, а во второй это уменьшение значи- тельно замедляется [5]. Исследовалось влияние на результат и скорость сходимости ГА таких его контролируемых настроек, как размер популяции N и величина  из первого терминального условия. При изучении влияния размера популяции ее числен- ность увеличивалась от 50N до 400N с шагом 50. При этом остальные на- стройки ГА оставались неизменными (значение ).1000000,0 Приведенные в табл. 5 результаты решения задачи 1 показывают, что при малых размерах попу- ляции для сходимости ГА требуется большее число поколений, в то же время при использовании популяций большого размера увеличивается время выполнения ал- горитма из-за существенного роста количества вычислений значений фитнесс- функции. После 300N рост скорости сходимости ГА становится незначительным. Аналогичное исследование проводилось относительно величины  из первого терминального условия (проверка выполнения неравенства ).Fit При этом значе- ние  уменьшалось каждый раз на порядок, а остальные настройки ГА, в том числе и размер популяции N =150, оставались неизменными. Приведенные в табл. 6 результа- ты для задачи 3 показывают, что с уменьшением  растет число поколений, необхо- димых для сходимости алгоритма (поскольку увеличивается продолжительность про- цесса поиска более точного решения), при этом абсолютная погрешность постепенно уменьшается. Таблица 5 Размер популяции Среднее число поколений Среднее значение функции Fit Среднее значение абсолютной погрешности 50 139 6,63294510 –5 1,22581310 –5 100 114 6,94249910 –8 8,43947910 –9 150 91 5,54741010 –8 8,05751910 –9 200 86 6,58381910 –8 7,80380910 –9 250 82 5,50564610 –8 8,81472810 –9 300 78 5,40893910 –8 8,14421310 –9 350 77 5,93569610 –8 7,49080510 –9 400 76 5,25395610 –8 7,23778310 –9 Таблица 6 Значение  Среднее число поколений Среднее значение функции Fit Среднее значение абсолютной погрешности 0,000 01 67 5,71297910 –6 3,76117710 –8 0,000 001 76 5,79145210 –7 4,28659010 –9 0,000 000 1 89 5,78826210 –8 4,07740010 –10 0,000 000 01 99 6,30200110 –9 3,65941910 –11 0,000 000 001 109 6,81186310 –10 3,79232910 –12 0,000 000 000 1 120 5,90369110 –11 4,11646310 –13 0,000 000 000 01 135 6,12061610 –12 3,68369210 –14 Заключение Предложенный в статье ГА позволяет находить в аналитической форме при- ближенные решения краевых задач для обыкновенных дифференциальных урав- нений второго порядка и краевых задач для уравнений эллиптического типа. Ре- зультаты численного эксперимента показали, что полученные с его помощью ре- шения тестовых задач хорошо согласуются с их точными решениями. Алгоритм не требует модификации при переключении от линейных задач к нелинейным, Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 4 59 находит решения нелинейных задач без применения численных методов, прост в реализации и может использоваться для решения других подобных задач. В статье проанализировано влияние некоторых контролируемых параметров ГА на точ- ность решений и скорость сходимости алгоритма, что позволяет пользователю на- страивать ГА в зависимости от потребности найти решение краевой задачи за наименьшее время или с наибольшей точностью и надежностью. Л.П. Вакал ЗАСТОСУВАННЯ ГЕНЕТИЧНОГО АЛГОРИТМУ ДЛЯ РОЗВ’ЯЗАННЯ КРАЙОВИХ ЗАДАЧ Запропоновано генетичний алгоритм для розв’язання крайових задач для звичайних диференціальних рівнянь другого порядку і крайових задач для еліптичних рівнянь. Наведено результати чисельних експериментів розв’язання лінійних і нелінійних за- дач. Знайдені розв'язки подаються в аналітичній формі. Досліджено вплив парамет- рів генетичного алгоритму на точність розв’язків і швидкість збіжності. L.P. Vakal USING GENETIC ALGORITHM FOR SOLVING BOUNDARY VALUE PROBLEMS A genetic algorithm for solving boundary value problems for second-order ordinary differ- ential equations and boundary value problems for elliptic equations is proposed. Results of numerical experiments for solving linear and nonlinear problems are presented. The ob- tained solutions are presented in the analytical form. The influence of genetic algorithm pa- rameters on the solutions accuracy and convergence rate is investigated. 1. Триус Ю.В., Триус В.Ю. Оптимізація багатоекстремальних функцій за допомогою гібрид- них методів у середовищі MATLAB R2007A // Вісник Черкаського університету. Приклад- на математика. Інформатика. — 2010. — Вип. 172. — С. 104–122. 2. Панченко Т.В. Генетические алгоритмы. — Астрахань: Издательский дом «Астраханский университет», 2007. — 87 с. 3. Holland J.H. Adaptation in natural and artificial systems. — Ann Arbor: Univ. of Michigan Press, 1975. — 219 p. 4. Казаков В.Ю., Пейгин С.В., Тимченко С.В. Оптимизация по интегральному тепловому по- току траектории входа в атмосферу Земли затупленного тела // Прикладная механика и техническая физика. — 2000. — 41, № 4. — С. 112–123. 5. Вакал Л.П. Генетичні алгоритми для чебишовської апроксимації // Комп’ютерні засоби, мережі та системи. — 2013. — № 12. — С. 20–26. 6. Abu-Arqub Omar, Abo-Hammour Zaer, Momani Shaher, Shawagfeh Nabil. Solving singular two- point boundary value problems using continuous genetic algorithm. — http://www.hindawi. com/journals/aaa/2012/205391. 7. Abu-Arqub Omar, Abo-Hammour Zaer, Momani Shaher. Application of continuous genetic algo- rithm for nonlinear system of second-order boundary value problems // Appl. Math. Inf. Sci. — 2014. — 8, N 1. — P. 235–248. 8. Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. — М. : Наука, 1967. — 368 с. 9. Волков Е.А. Численные методы. — М. : Наука, 1987. — 248 с. 10. Вакал Л.П. Розв’язання крайових задач з використанням програмних засобів чебишовських наближень // Комп’ютерні засоби, мережі та системи. — 2010. — № 9. — С. 47–53. 11. Перестюк М.О., Маринець В.В., Рего В.Л. Збірник задач з математичної фізики. — Кам'я- нець-Подільський: Аксіома, 2012. — 249 с. 12. Вакал Л.П., Каленчук-Порханова А.О. Аналітична обробка даних на основі чебишовської апроксимації // Математичні машини і системи. — 2006. — № 2. — С. 15–24. 13. Herrera F., Lozano M., Verdegay J.L. Tackling real-coded genetic algorithms: operators and tools for the behaviour analysis // Artificial Intelligence Review. — 1998. — 12, N 4. — P. 265–319. 14. Каленчук-Порханова А.О., Вакал Л.П. Застосування найкращої чебишовської апроксимації для моделювання деяких фізичних процесів // Математичне та комп’ютерне моделювання. Серія технічні науки. — 2010. — № 4. — С. 111–118. Получено 23.04.2015 ftp://decsai.ugr.es/pub/arai/tech_rep/ga-fl/AIRE96.ps.Z ftp://decsai.ugr.es/pub/arai/tech_rep/ga-fl/AIRE96.ps.Z

Применение генетического алгоритма для решения краевых задач

Репозитарії

Схожі ресурси