Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції
Для задачі адвекції-дифузії-реакції запропоновано відмінний від традиційних підходів алгоритм декомпозиції одновимірної області на скінченні елементи. Для методу скінченних елементів використано апроксимаційні функції-\"бульбашки\". Поділ на елементи вибирається з умови мінімізації нев’язк...
Збережено в:
| Дата: | 2005 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
2005
|
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/20917 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції / Я. Савула, Л. Винницька // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 151-158. — Бібліогр.: 6 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-20917 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-209172011-07-29T21:35:40Z Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції Савула, Я. Винницька, Л. Для задачі адвекції-дифузії-реакції запропоновано відмінний від традиційних підходів алгоритм декомпозиції одновимірної області на скінченні елементи. Для методу скінченних елементів використано апроксимаційні функції-\"бульбашки\". Поділ на елементи вибирається з умови мінімізації нев’язки розв’язку,отриманого методом скінченних елементів. Оптимізаційну задачу розв’язано генетичним алгоритмом. Наведено числові результати для задачі з великим числом Пекле. An alternative algorithm for one-dimensional finite elements domain decomposition for advection-diffusion-reaction problem is proposed. \"Bubble\"-functions are used for finite elements method. The division is chosen in respect of FEM solution error minimization. Optimization is realized by genetic algorithm. Numerical results for \"big\" Peclet number are presented. Для задачи адвекции-диффузии-реакции предложен отличный от традиционных подходов алгоритм декомпозиции одномерной области на конечные элементы. Для метода конечных элементов использовано аппроксимационные функции-\"пузырьки\". Разбиение выбирается из условия минимизации невязки решения, полученного методом конечных элементов. Задача оптимизации решается генетическим алгоритмом. Приведены численные результаты для задачи с большим числом Пекле. 2005 Article Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції / Я. Савула, Л. Винницька // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 151-158. — Бібліогр.: 6 назв. — укр. 1816-1545 http://dspace.nbuv.gov.ua/handle/123456789/20917 519.6 uk Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Для задачі адвекції-дифузії-реакції запропоновано відмінний від традиційних підходів алгоритм декомпозиції одновимірної області на скінченні елементи. Для методу скінченних елементів використано апроксимаційні функції-\"бульбашки\". Поділ на елементи вибирається з умови мінімізації нев’язки розв’язку,отриманого методом скінченних елементів. Оптимізаційну задачу розв’язано генетичним алгоритмом. Наведено числові результати для задачі з великим числом Пекле. |
| format |
Article |
| author |
Савула, Я. Винницька, Л. |
| spellingShingle |
Савула, Я. Винницька, Л. Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції |
| author_facet |
Савула, Я. Винницька, Л. |
| author_sort |
Савула, Я. |
| title |
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції |
| title_short |
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції |
| title_full |
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції |
| title_fullStr |
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції |
| title_full_unstemmed |
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції |
| title_sort |
оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції |
| publisher |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України |
| publishDate |
2005 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/20917 |
| citation_txt |
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу задачі адвекції-дифузії-реакції / Я. Савула, Л. Винницька // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 151-158. — Бібліогр.: 6 назв. — укр. |
| work_keys_str_mv |
AT savulaâ optimízacíâgenetičnimalgoritmomsítkiskínčennihelementívdlâčislovogoanalízuzadačíadvekcíídifuzííreakcíí AT vinnicʹkal optimízacíâgenetičnimalgoritmomsítkiskínčennihelementívdlâčislovogoanalízuzadačíadvekcíídifuzííreakcíí |
| first_indexed |
2025-07-02T21:28:28Z |
| last_indexed |
2025-07-02T21:28:28Z |
| _version_ |
1836572170086514688 |
| fulltext |
Оптимізація генетичним алгоритмом
сітки скінченних елементів для числового аналізу
задачі адвекції-дифузії-реакції
Ярема Савула1, Людмила Винницька2
1 д. ф.-м. н., професор, кафедра прикладної математики Львівського національного університету імені Івана Франка,
вул. Університетська, 1, Львів, e-mail: savula@franko.lviv.ua
2 аспірант, Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів,
e-mail: lyuda_vyn@yahoo.com
Для задачі адвекції-дифузії-реакції запропоновано відмінний від традиційних підходів алго-
ритм декомпозиції одновимірної області на скінченні елементи. Для методу скінченних еле-
ментів використано апроксимаційні функції-«бульбашки». Поділ на елементи вибирається
з умови мінімізації нев’язки розв’язку, отриманого методом скінченних елементів. Оптимі-
заційну задачу розв’язано генетичним алгоритмом. Наведено числові результати для задачі
з великим числом Пекле.
Ключові слова: генетичний алгоритм, метод скінченних елементів, поділ
області, вузлова точка, задача адвекції-дифузії-реакції.
Вступ. У процесі розв’язування задач математичної фізики методом скінченних
елементів (МСЕ) важливу роль у забезпеченні точності наближених розв’язків
посідає декомпозиція області на скінченні елементи. Для задачі адвекції-дифузії-
реакції у випадку великих чисел Пекле побудова «доброї» сітки є дуже важли-
вою, оскільки точність розв’язку, побудованого МСЕ, значною мірою залежить
від вибору вузлових точок [1].
Згідно з традиційним підходом, який зазвичай використовують для побудо-
ви сітки, область ділять на однакові скінченні елементи, а потім шляхом додаван-
ня вузлових точок за певним критерієм оптимізують поділ.
Розглянемо задачу поділу області на фіксовану кількість скінченних еле-
ментів як деяку задачу оптимізації, яку розв’язуватимемо шляхом застосування
генетичного алгоритму [2-4].
1. Задача адвекції-дифузії-реакції
1.1. Формулювання задачі. Розглянемо одновимірний стаціонарний випадок за-
дачі адвекції-дифузії-реакції
,)()()( fxQuxuPexuLu =+′+′′−≡ ( ) ,0)( == buau [ ]ba,=Ω (1)
де fQ, — сталі, 0≥Q ; Pe — число Пекле, 0>Pe .
УДК 519.6
151
Ярема Савула, Людмила Винницька
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу…
152
Задачу (1) легко розв’язати аналітично. Однак, у процесі числового розв’я-
зування МСЕ виникає проблема, оскільки для великих чисел Пекле її розв’язок є
сильно градієнтним в околі точки b [5].
Варіаційне формулювання задачі (1) має такий вигляд:
знайти елемент ( ) ( )( ) ( ) ( ){ }0,:, 1
2 ==Ω∈==∈ bvavWvxvvVVu , що Vv∈∀ викону-
ється рівняння
{ }∫ ∫=+′+′′
b
a
b
a
fvdxdxQuvvuPevu , (2)
де ( ) ( )Ω1
2W — простір функцій Соболєва.
1.2. Розв’язування задачі. Одновимірні апроксимації функціями-«бульбаш-
ками». Задачу (2) розв’язуватимемо МСЕ з використанням апроксимаційних
функцій-«бульбашок» [5, 6].
Нехай здійснено поділ області Ω на N скінченних елементів kΩ множи-
ною точок X
{ }bxaxxxNixX Niii ==<== − ,,;,0: 01 , (3)
{ }kkk xxxx ≤≤=Ω −1: , k = N,1 . (4)
За допомогою співвідношення
kk xxx
2
1
2
1
1
ξ+
+
ξ−
= −
відобразимо кожен скінченний елемент kΩ на «стандартний» скінченний елемент
{ }11:* ≤ξ≤−ξ=Ω .
Обернене відображення має вигляд
1
12
−
−
−
−−
=ξ
kk
kk
xx
xxx .
На *Ω визначимо таку послідовність базисних функцій
( ) ( ) ( ) ( ) 1,3,,
2
1,
2
1
121 +=ξΦ=ξϕ
ξ+
=ξϕ
ξ−
=ξϕ − pjjj , (5)
де р — степінь базисної функції, а ( )ξΦ j визначають через поліноми Лежандра
1−jP за формулою
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2005, вип. 2, 151-158
153
( ) ( )dttPj
jj ∫
ξ
−
−
−
=ξΦ
1
12
12 , j = 2, 3, ... (6)
Відомо, що для поліномів Лежандра, які є ортогональними на проміжку [−1; 1], тобто
=
+
≠
=∫
−
,,
12
2
;,0
)()(
1
1
ji
i
ji
dttPtP ji (7)
справджується рекурентна формула
),()()12()()1( 11 tnPttPntPn nnn −+ −+=+ ...,,2,1=n ,10 =P tP =1 (8)
та виконується співвідношення
),()()()12( 11 tPtPtPn nnn −+ ′−′=+ n = 1, 2, ... . (9)
Тоді
( ) ( ) ( )[ ] ...,4,3,
)12(2
1
2 =ξ−ξ
−
=ξϕ − jPP
j jjj . (10)
З останніх рівностей і властивості ортогональності поліномів Лежандра (7) отри-
муємо формулу
( ) ( )
=
≠
=ξξϕ′ξϕ′∫
−
.,1
;,01
1 ji
ji
dji (11)
Враховуючи запис (6) і властивість (7) дістаємо, що
( ) ( ) 011 =ϕ=−ϕ jj , 1,4,3 += pj . (12)
Власне тому ( )ξϕ j називають функціями-«бульбашками». При записі апрокси-
мованої функції у вигляді суми за базисними функціями
( ) ( )ξϕ=ξ ∑
+
=
j
p
j
jh au
1
1
отримаємо ( ) ( ) 21 1,1 auau hh ==− . Базисні функції ( )ξϕ1 і ( )ξϕ2 називають вузловими.
2. Елементарний генетичний алгоритм
Генетичний алгоритм розв’язування задач оптимізації часто розглядають як аль-
тернативу традиційним методам. Робота алгоритму полягає в генеруванні вели-
кої кількості ймовірних розв’язків та у відборі кращих кандидатів.
Ідея генетичного алгоритму запозичена з теорії еволюції Дарвіна. Алгорит-
му характерна власна термінологія. Основним є поняття особини (ймовірний
Ярема Савула, Людмила Винницька
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу…
154
розв’язок), що має дві складові: хромосому й пристосованість. Хромосома (аргу-
мент функції мети) складається з гена (генів). Якщо ми здійснюємо оптимізацію
функції ( )nxxxff ...,,, 21= , то кожній змінній ),1( nixi = відповідає ген — двій-
кове подання її значення (набори, що містять лише 0 і 1), причому 0 чи 1 на-
зивають алеллю. Пристосованість — значення функції f для заданої хромосоми.
Множина, елементами якої є хромосоми, утворює популяцію.
Механізм роботи елементарного генетичного алгоритму надзвичайно простий.
Основні дії полягають у здійсненні обміну інформацією, що містять хромосоми.
Алгоритм розпочинає свою роботу з деякої початкової популяції, а хромосоми
особин генеруються випадковим чином. Генетичний алгоритм є ітераційним про-
цесом і складається з таких трьох операцій:
1) репродукція (селекція);
2) схрещування;
3) мутація.
Рис. 1. Блок-схема генетичного алгоритму
На кожній ітерації створюється нова популяція, яка враховує досвід попе-
редніх «поколінь».
Репродукція — це процес, що залежить від функції мети f. Ця функція є мі-
рилом пристосованості кожного з наборів кодів до вимог певної задачі. Особини
з вищою пристосованістю мають більшу ймовірність введення одного чи кількох
нащадків до наступного покоління. Ця операція в своїй основі має дарвінівські
Утворити нащадків
за допомогою
випадкових змін
Ініціалізувати
популяцію
Обчислити пристосо-
ваність кожного з
можливих розв’язків
Застосувати вибір
Визначити
розв’язок
так
ні
Припинити ?
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2005, вип. 2, 151-158
155
засади природного відбору, згідно з якими виживають і дають потомство ті, що
найкраще пристосовані.
Схрещування — це генерація нових розв’язків на основі відібраних бать-
ківських пар. Класична схема полягає у створенні одного або декількох нащадків
за допомогою різноманітних комбінацій батьківських алелей.
Загалом, мутація — це інвертування кількох алелей хромосоми (0 заміню-
ють на 1 і навпаки), вибраних випадковим чином. У більшості випадків оператор
мутації застосовується до нащадка з деякою ймовірністю.
Вважається, що селекція в генетичному алгоритмі є основним пошуковим
механізмом, а мутація дозволяє внести в цей процес елемент випадковості, що
знижує ймовірність зупинки алгоритму в локальному екстремумі.
Наприкінці роботи алгоритму з-поміж усіх особин вибирається та, що при-
стосована найкраще.
Зауважимо, що оскільки генетичні операції є випадковими змінами, то при
одних і тих самих початкових даних їх результати, зазвичай, не співпадають.
3. Застосування генетичного алгоритму до побудови сітки скінченних
елементів
3.1. Формулювання задачі оптимізації. Задачу поділу області Ω на скінченні
елементи сформулюємо як задачу оптимізації
min,)( →XM ,,)(
1
)(2
∑
=
Ω
−==
N
k
Lhkk
k
fLummXM (13)
де hu — наближений розв’язок задачі (2), ( )Ω2L – простір функцій, інтегровних з
квадратом.
3.2. Алгоритм розв’язування
Крок 1. Задача адвекції-дифузії-реакції (2) розв’язується для рівномірної сітки
з J вузлових точок.
Крок 2. Для кожного скінченного елемента ( )Jkk ,0=Ω обчислюється нев’язка
km і величина %100⋅=
M
mr k
k .
Крок 3. Елементи, для яких rrk ≥ , де r — деякий рівень похибки, міститимуть
kn вузлових точок
( ) ∑
≥
≤≤
=
−=
rr
Jk
k
k
k
k
mRN
R
mn
1
,1 ,
де ⋅ — ціла частина числа.
Ярема Савула, Людмила Винницька
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу…
156
Крок 4. Для розв’язування задачі (13), тобто пошуку 1−N вузлових точок, засто-
совується генетичний алгоритм.
Перших три кроки алгоритму є підготовчими. Вони лише дають змогу ви-
значити «проблемні» ділянки області. Тому на першому кроці рекомендуємо зна-
чення J вибирати досить «великим». Кожна особина — це хромосома, що містить
1−N ген, для якої обчислено пристосованості М. За критерій зупинки виберемо
виконання генетичним алгоритмом певної кількості ітерацій.
4. Результати числових експериментів
Для задачі (1) виберемо такі дані: 12;1,0;1000;1;0 ===== fQPeba . Будемо
шукати оптимальний поділ області на 10 скінченних елементів.
Задачу (2) розв’язуємо МСЕ з використанням апроксимаційних функцій-
«бульбашок» четвертого порядку.
При заданих %20,15 == rJ три вузлових точки міститимуться на відрізку
(0,867; 0,933) і шість точок на відрізку (0,933; 1).
За критерій зупинки генетичного алгоритму вибираємо виконання трьох
ітерацій. При популяції з 4 особин задача адвекції-дифузії-реакції (2) розв’язува-
тися 12 разів.
Рис. 2. Розподіл вузлових точок (І)
Таблиця 1. Вузлові точки (І)
№ 0 1 2 3 4 5 6 7 8 9 10
х 0 0,895 0,897 0,933 0,94 0,953 0,957 0,974 0,995 0,998 1
a б
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2005, вип. 2, 151-158
157
Рис. 3. Розподіл вузлових точок (ІІ)
Таблиця 2. Вузлові точки (ІІ)
№ 0 1 2 3 4 5 6 7 8 9 10
х 0 0,884 0,893 0,925 0,964 0,977 0,981 0,993 0,995 0,999 1
На рис. 2а і рис. 3а зображено наближений і точний розв’язки задачі (2) і
позначено вузлові точки при різних варіантах декомпозиції області за тих самих
вхідних даних. На рис. 2б і рис. 3б у збільшеному вигляді показано ті частини
області, де скупчуються вузлові точки. За даного поділу наближений і точний
розв’язки практично співпадають.
Таблиці 1, 2 містять знайдені поділи Х.
Висновки. Запропонований алгоритм є відмінним від традиційних підходів до
декомпозиції одновимірних областей. Поділ області здійснюється на заздалегідь
задану кількість елементів. Вузлові точки за такого підходу скупчуються в
«проблемній» частині області.
Даний алгоритм можна застосовувати для задач, розв’язкам яких властива
сильна градієнтність у деякій частині області.
Література
[1] Козаревська Ю. С. Застосування h-адаптивної схеми методу скінченних елементів
до розв’язування нестаціонарних задач мігрування // Вісник Львівського універси-
тету. Серія прикладна математика та інформатика. — 2004. — Вип. 8. — С. 141-151.
[2] Arabas J. Wyklady z algorytmow ewolucyjnych. — Warszawa: Wydawnictwo Nauko-
wo-Techniczne, 2004. — 303 s.
[3] Goldberg D. Algorytmy genetyczne i ich zastosovania. — Warszawa: Wydawnictwo
Naukowo-Techniczne, 2003. — 408 s.
[4] Holder M., Richardson J. Genetic Algorithms, Another Tool for Quad Mesh Optimiza-
tion // Proceedings. — 7th International Meshing Roundtable, Sandia National Lab.,
1998. — P. 497-594.
Ярема Савула, Людмила Винницька
Оптимізація генетичним алгоритмом сітки скінченних елементів для числового аналізу…
158
[5] Савула Я. Г. Числовий аналіз задач математичної фізики варіаційними методами. —
Львів: видавничий центр ЛНУ імені Івана Франка, 2004. — 221 с.
[6] Szabo B., Babushka І. Finite element analysis. — New York: John Wiley & Sons, inc.,
1991. — 368 p.
Optimization by Genetic Algorithm of Finite Elements Mesh
for Numerical Analysis of Advection-Diffusion-Reaction Problem
Yarema Savula, Lyudmyla Vynnytska
An alternative algorithm for one-dimensional finite elements domain decomposition for advection-
diffusion-reaction problem is proposed. «Bubble»-functions are used for finite elements method.
The division is chosen in respect of FEM solution error minimization. Optimization is realized by
genetic algorithm. Numerical results for «big» Peclet number are presented.
Оптимизация генетическим алгоритмом
сетки конечных элементов для численного анализа
задачи адвекции-диффузии-реакции
Ярема Савула, Людмила Винницка
Для задачи адвекции-диффузии-реакции предложен отличный от традиционных подходов
алгоритм декомпозиции одномерной области на конечные элементы. Для метода конечных
элементов использовано аппроксимационные функции-«пузырьки». Разбиение выбирается
из условия минимизации невязки решения, полученного методом конечных элементов. Зада-
ча оптимизации решается генетическим алгоритмом. Приведены численные результаты
для задачи с большим числом Пекле.
Отримано 28.09.05
|