Нейронні мережі.

Біологічний нейрон - це нервова клітина разом з її відростами, структурна і функціональна одиниця нервової системи. Складається із тіла (соми), що містить ядро, і відростків двох типів, що входять до нього - коротких деревовидних віток (дендритів) і одного довгого, що має вітки лише на кінці (аксома). З’єднання нейронів в нервові ланцюги відбувається за допомогою особливих контактів - синапсів. Функціонування нейронів здійснюється на основі нервових процесів, що в них розвиваються – синаптичних процесів і генерації нервових імпульсів. Властивості нейронів є предметом математичного моделювання і використовується при створенні логічнних пристроїв. Нейронні мережі – це схеми з’єднань однорідних елементів – нейронів, а також їх математичні моделі. Схеми з’єднань нейронів дуже різноманітні, але всі вони являють собою багатошарові просторові структури. В однолінійних мережах кожний нейрон верхнього шару впливає на один нейрон шару, що лежить нижче. Прикладом такої мережі є рефлеторна дуга, що складається із послідовно включених трьох нейронів (чутливого, проміжкового і мононейрона). Пороговий нейрон являє собою пристрій з кількома двійковими входами і одним двійковим виходом. Кожному двійковому входу ставиться у відповідність дійсне число, яке називається вагою. Сигнал на вході пристрою дорівнює константі 0 поки вагова сума вхідних сигналів не буде дорівнювати, або поки не стане більше дійсного числа, яке називається порогом, в цьому випадку вихідний сигнал стає рівним 1.

S₁ вихід

S₂

^......

S_n

P<W1*X1+W2*X2+...+Wn*Xn

Функція P називається активуючою функцією нейрона. Для математичного поргового елемента буде вірне наступне співвідношення:

G=1 if (W₁*X₁+W₂*X₂+...+W_n*X_n) T;

(*)

G=1 if (W₁*X₁+W₂*X₂+...+W_n*X_n)<T;

Тут G - це двійковий сигнал на вході порогового елементу - пристрою з декількома двійковими входами і двійковим виходом, X_i-це двійковий сигнал на і-вому вході пристрою,який дорівнює 1 або 0, W_i - це вага і-вого входу, скінчене дійсне число, (i=1,...,n)

n - загальне число входів, Т - поріг, скінчене дійсне число. Вузли, поведінка яких з тим чи іншим степенем точності відповідає такій моделі, були знайдені в нервовій системі живих організмів. В останньому випадку нейрони мають в порівнянні із звичайними елементами ряд переваг, які зв’язані , насамперед із їх великими функціональними можливостями при таких самих затратах і розмірах.

Генетичні алгоритми і моделювання еволюції.

Генетичні Алгоритми (ГА) - це адаптивні методи функціональної оптимізації, засновані на комп'ютерному імітаційному моделюванні біологічної еволюції. Основні принципи ГА були сформульовані Голландії (Holland, 1975), і добре описані в багатьох роботах і на ряді сайтів в Internet. В даний час існує ряд теорій біологічної еволюції (Ж.-Б.Ламарка, П.Тейяра де Шардена, К.Е.Бера, Л.С.Берг, А.А.Любищева, С.В.Мейена та ін), однак, жодна з них не вважається загальновизнаною. Найбільш відомою і популярною, звичайно, є теорія Чарльза Дарвіна, яку він представив у роботі "Походження Видів" в 1859 році. Ця теорія, як і інші, містить досить багато невирішених проблем, глибоке розгляд яких далеко виходить за рамки даної роботи. Тут ми можемо відзначити лише деякі найбільш відомі з них. Як це не парадоксально, але незважаючи на те, що сам Чарльз Дарвін назвав свою роботу "Походження Видів" але якраз саме походження видів вона і не пояснює. Справа в тому, що виникнення нового виду "за алгоритмом Дарвіна" є вкрай малоймовірним подією, тому що для цього потрібно випадкове виникнення в одній точці простору і часу відразу не менше 100 особин нового виду, тобто особин, які могли б мати плідне потомство. При меншій кількості особин вид приречений на вимирання. Тому процес видоутворення на основі випадкових мутацій мав би зайняти незграбно багато часу (за деякими оцінками навіть у набагато разів більше, ніж час існування Всесвіту). Крім того, "алгоритм Дарвіна" не пояснює явною системності в різноманітті виникаючих форм, типу закону гомологічних рядів Н.І. Вавілова. Тому Л.С. Берг запропонував дуже цікаву концепцію номогенеза - закономірною або спрямованої еволюції живого. У цій концепції передбачається, що філогенез має певний напрям і зміна форма є не випадковою, а задається деяким вектором, природа якого не ясна. Ідеї ​​номогенеза глибоко розробив і розвинув А.А. Любищев, який висловив гіпотезу про математичні закономірності, які визначають різноманіття живих форм. Крім того, Дарвін не зміг показати механізм успадкування, при якому підтримується і закріплюється мінливість. Це було на п'ятдесят років до того, як генетична теорія спадковості почала поширюватися по світу, і за тридцять років до того, як "еволюційний синтез" зміцнив зв'язок між теорією еволюції і молодий генетикою. Тим ні менш і не дивлячись на свої недоліки, саме теорія Дарвіна традиційно і моделюється в ГА, хоча, звичайно, це не виключає можливості моделювання та інших теорій еволюції в ГА. Більше того, можливо саме таке комп'ютерне моделювання і порівняння його результатів з картиною реальної еволюції життя на Землі може бути і зіграє позитивну роль у подальшій розробці найбільш адекватної теорії біологічної еволюції. Теорія Дарвіна застосовна не до окремих особинам, а до популяцій - великій кількості особин одного виду, тобто здатних давати плідне потомство, перебуває в певній статичною або динамічною зовнішньому середовищі. В основі моделі еволюції Дарвіна лежать випадкові зміни окремих матеріальних елементів живого організму при переході від покоління до покоління. Доцільні зміни, які полегшують виживання і виробництво нащадків в даній конкретній зовнішньому середовищі, зберігаються і передаються потомству, тобто успадковуються. Особини, які не мають відповідних пристосувань, гинуть, не залишивши потомства або залишивши його менше, ніж пристосовані (вважається, що кількість потомства пропорційно ступеня пристосованості). Тому в результаті природного відбору виникає популяція з найбільш пристосованих особин, яка може стати основою нового виду. Природний відбір відбувається в умовах конкуренції особин популяції, а іноді і різних видів, один з одним за різні ресурси, такі, наприклад, як їжа або вода. Крім того, члени популяції одного виду часто конкурують за залучення шлюбного партнера. Ті особини, які найбільш пристосовані до навколишніх умов, будуть мати відносно більше шансів відтворити нащадків. Незадовільно пристосовані особини або зовсім не справлять потомства, або їх потомство буде дуже нечисленним. Це означає, що гени від високо адаптованих або пристосованих особин будуть поширяться в зростаючому кількості нащадків на кожному наступному поколінні. Таким чином, по суті справи кожен конкретний генетичний алгоритм представляють імітаційну модель деякої певної теорії біологічної еволюції або її варіанту. Разом з тим необхідно відзначити, що самі дослідники біологічної еволюції поки ще не до кінця визначилися з критеріями і методами визначення ступеня суттєвості для підтримуваної ними теорії еволюції тих чи інших біологічних процесів, які власне і моделюються в генетичних алгоритмах. Робота ГА являє собою ітераційний процес, який продовжується до тих пір, поки покоління не перестануть істотно відрізнятися один від одного, або не пройде задану кількість поколінь або заданий час. Для кожного покоління реалізуються відбір, кросовер (схрещування) і мутація. Розглянемо цей алгоритм:

Крок 1: генерується початкова популяція, що складається з N особин з випадковими наборами ознак.

Крок 2 (боротьба за існування): обчислюється абсолютна пристосованість кожної особини популяції до умов середовища і сумарна пристосованість особин популяції, характеризує пристосованість всієї популяції. Потім при пропорційному відборі для кожної особини обчислюється її відносний внесок у сумарну пристосованість популяції, тобто відношення її абсолютної пристосованості до сумарної пристосованості всіх особин популяції. Оскільки кількість потомства особини пропорційно її пристосованості, то природно вважати, що якщо це кількість інформації:

- Позитивно, то дана особина виживає і дає потомство, чисельність якого пропорційна цій кількості інформації;

- Дорівнює нулю, то особина доживає до статевозрілого віку, але потомства не дає (його чисельність дорівнює нулю);

- Менше нуля, то особина гине до досягнення статевозрілого віку.

Таким чином, можна зробити фундаментальний висновок, що має навіть світоглядне звучання, про те, що природний відбір являє собою процес генерації та накопичення інформації про виживання і продовження роду в ряді поколінь популяції, як системи. Це нагромадження інформації відбувається на різних рівнях ієрархії популяції, як системи, що включає:

- Елементи системи: окремі особини;

- Взаємозв'язку між елементами: відносини між особинами в популяції, що забезпечують передачу наступним поколінням максимальної кількості інформації про їх виживання і продовження роду (шляхом схрещування найбільш пристосованих особин і спадкування раціональних придбань);

- Мета системи: збереження і розвиток популяції, реалізується через цілі особин: індивідуальне виживання і продовження роду.

Фенотип відповідає генотипу і являє собою його зовнішній прояв в ознаках особини. Особина взаємодіє з навколишнім середовищем та іншими особинами у відповідності зі своїм фенотипом. У разі, якщо це взаємодія вдало, то особина передає генетичну інформацію, визначальну фенотип, наступним поколінням.

Крок 3: початок циклу зміни поколінь.

Крок 4: початок циклу формування нового покоління.

Крок 5 (відбір): здійснюється пропорційний відбір особин, які можуть брати участь у продовженні роду. Відбираються тільки ті особини популяції, у яких кількість інформації у фенотипі і генотипі про виживання і продовження роду позитивно, причому ймовірність вибору пропорційна цій кількості інформації.

Крок 6 (кросовер): відібрані для продовження роду на попередньому кроці особини із заданою вірогідністю піддаються схрещуванню або кросоверу (рекомбінації). Якщо кросовер відбувається, то нащадки отримують по половині випадковим чином певних ознак від кожного з батьків. Чисельність потомства пропорційна сумарній пристосованості батьків. У деяких варіантах ГА нащадки після своєї появи замінюють собою батьків і переходять до мутації. Якщо кросовер не відбувається, то вихідні особини - не відбулися батьки, переходять на стадію мутації.

Крок 7 (мутація): виконуються оператори мутації. При цьому ознаки нащадків з деякою імовірністю випадковим чином змінюються на інші. Зазначимо, що використання механізму випадкових мутацій ріднить генетичні алгоритми з таким широко відомим методом імітаційного моделювання, як метод Монте-Карло.

Крок 8 (боротьба за існування): оцінюється пристосованість нащадків (за тим же алгоритмом, що і на кроці 2).

Крок 9: перевіряється, чи всі відібрані особини дали потомство. Якщо ні, то відбувається перехід на крок 5 і продовжується формування нового покоління, інакше - перехід на наступний крок 10.

Крок 10: відбувається зміна поколінь:- Нащадки поміщаються в нове покоління;- Найбільш пристосовані особини зі старого покоління переносяться в нове, причому для кожної з них це можливо не більше заданої кількості разів;- Отримана нова популяція заміщає собою стару.

Крок 11: перевіряється виконання умови зупину генетичного алгоритму. Вихід з генетичного алгоритму відбувається або тоді, коли нові покоління перестають істотно відрізнятися від попередніх, тобто, як кажуть, "алгоритм сходиться", або коли пройдено задану кількість поколінь або заданий час роботи алгоритму (щоб не було "зациклення" і динамічного зависання у разі, коли рішення не може бути знайдено в заданий час). Якщо ГА зійшовся, то це означає, що рішення знайдено, тобто отримано покоління, ідеально пристосоване до умов даної фіксованої середовища проживання. Інакше - перехід на крок 4 - початок формування нового покоління.

У реальному біологічної еволюції цим справа не обмежується, тому що будь-яка популяція крім освоєння деякої екологічної ніші намагається також вийти за її межі освоїти і інші ніші, як правило "суміжні". Саме за рахунок цих процесів життя вийшло з моря на сушу, проникла в повітряний простір і поверхневий шар грунту, а зараз освоює космічний простір. Звичайно, реальні генетичні алгоритми, на яких проводяться наукові дослідження, найчастіше мало схожі на наведений приклад. Дослідники експериментують з різними параметрами генетичних алгоритмів, наприклад: способами відбору особин для схрещування; критеріями пристосованості і жорсткістю впливу факторів середовища; способами вибору ознак, що передаються від батьків нащадкам (рецесивні і не рецесивні гени і т.д.); інтенсивністю, видом випадкового розподілу і спрямованістю мутацій; різними підходами до відтворення та відбору. Тому під терміном "генетичні алгоритми" по суті справи треба розуміти не одну модель, а досить широкий клас алгоритмів, часом мало схожих один на одного. В даний час розглядається багато різних операторів відбору, кросовера і мутації: турнірний відбір (Brindle, 1981; Goldberg і Deb, 1991), реалізує n турнірів, щоб вибрати n особин, при цьому кожен турнір побудований на вибірці k елементів з популяції, і вибору кращої особини серед них (найбільш поширений турнірний відбір з k = 2); елітний відбір (De Jong, 1975) гарантують, що при відборі обов'язково будуть виживати кращий або кращі члени популяції сукупності (найбільш поширена процедура обов'язкового збереження тільки однієї кращої особини, якщо вона не пройшла як інші через процес відбору, кросовера і мутації); двоточковий кросовер (Cavicchio, 1970; Goldberg, 1989c) і рівномірне кросовер (Syswerda, 1989) відрізняються способами успадкування нащадками ознак батьків. Не дивлячись на те, що моделі біологічної еволюції, реалізовані в ГА, зазвичай сильно спрощені в порівнянні з природним оригіналом, тим ні менш ГА є потужним засобом, який може з успіхом застосовуватися для вирішення широкого класу прикладних задач, включаючи ті, які важко, а іноді і зовсім неможливо, вирішити іншими методами. Однак, ГА не гарантує виявлення глобального рішення за прийнятний час. ГА не гарантують і того, що знайдене рішення буде оптимальним рішенням. Тим ні менш вони застосовні для пошуку "досить хорошого" рішення задачі за "досить короткий час". ГА являють собою різновид алгоритмів пошуку і мають переваги перед іншими алгоритмами при дуже великих розмірностях завдань і відсутності впорядкованості у вихідних даних, коли альтернативою їм є метод повного перебору варіантів. У випадках, коли задача може бути вирішена спеціально розробленим для неї методом, практично завжди такі методи будуть ефективніше ГА як за швидкодією, так і за точністю знайдених рішень. Головним же достоїнством ГА є те, що вони можуть застосовуватися для вирішення складних неформалізованих завдань, для яких не розроблено спеціальних методів, тобто ГА забезпечують вирішення проблем. Але навіть у тих випадках, для яких добре працюють існуючі методики, можна досягти цікавих результатів поєднуючи їх з ГА.

15