Лекція 18. Еволюційні моделі колективної поведінки
1. Принципи побудови еволюційних МКП
- population biology + ecological modeling = computational ecologies
популяційна біологія + екологічне моделювання = обчислювальні екології
- етологія (Конрад Лоренц) – наука про поведінку тварин
(колективний аспект – стада, зграї, колонії (Swarm Intelligence))
колектив ( популяція
агент ( представник популяції
Розглядаються великі колективи відносно простих агентів з обмеженою тривалістю життя, здатних до самовідтворення та пристосування (адаптації) до заданих умов середовища. В переважній більшості випадків мова іде про програмних агентів (software agent).
Основні принципи:
- process of natural selection
процес природнього відбору
- self-regulation of population size
саморегуляція розміру популяції ( популяційна динаміка
- process of self-replication
процес самовідтворення
- приклад змістовної інтерпретації (infoSpiders) ( алгоритм
2. Еволюційні обчислення
Загальний алгоритм:
[initialize population] Ініціалізувати популяцію
[evaluate fitness] Розрахувати придатність кожного представника популяції (моделюється процес керованого природнього відбору)
[applay selection] Здійснити відбір представників на основі проведених розрахунків
[reproduce population] Відтворити відібраних представників для формування нової популяції
[perform evolutionary operations] виконати еволюційні операції: схрещування (crossover), мутація (mutation), випадковий вибір (random variation) ( "народжуються" нова "хвиля" представників популяції
[check condition] перевірити цільову умову: якщо вона досягнута то кінець, інакше перейти на крок 2.
Три області еволюційних обчислень (в порядку зростання складності):
генетичні алгоритми (геном – послідовність бітів – точка в гіперпросторі)
еволюційне програмування (додається поняття середовища (функція середовища) + винаходиться не оптимальна точка у гіперпросторі, а оптимальна лінія (стратегія) поведінки)
генетичне програмування (розглядається популяція програм, кожна з яких представлена у вигляді дерева, відповідно здійснюється природній відбір різних варіантів програми, яка б задовільняла заданим специфікаціям (які розглядаються як середовище))
- приклад змістовної інтерпретації (вирішення задачі комівояжера (travelling salesman problem) за допомогою генетичних алгоритмів)
3. Кліткові автомати.
- запророновані Дж. фон Нейманом
- Це четвірка A={d, Q, N, (}, де
d – розмірність простору (1D, 2D, ...)
Q – кількість станів автомату
N – кількість сусідів
( - локальна функція перходу (зміни стану)
- різні типи оточення сусідами (сусідство по фон Н. (von Neumann neighbourhood), сусідство по Муру (Moore))
- КА працюють паралельно, синхронно у дискретному часі
- самовідтоврення (робота фон Неймана)
- LIFE game (J.H. Conway, 1960)