Генетичні алгоритми

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

До еволюційних алгоритмів відносяться:

• Генетичні алгоритми
• Генетичне програмування
• Еволюційні стратегії
• Еволюційне програмування
• Системи класифікаторів

Вони моделюють базові положення в теорії біологічної еволюції - процеси відбору, мутації і відновлення популяції особин.

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

Еволюційні алгоритми успішно використовувалися для завдань типу функціональної оптимізації і можуть легко бути описані математичною мовою.

Симулятори еволюції автомобілів

http://boxcar2d.com/

Програма генерує пристрої з коліс і кузовних деталей, мета яких - проїхати якомога довше. Спеціальний алгоритм оцінює проходження траси кожним автомобілем. Наступні машинки генеруються вже з врахуванням попередніх вдалих, життєздатних екземплярів. Вони ніби еволюціонують - якщо в першому поколінні зразки без коліс не можуть проїхати і метра, то в третьому поколінні у них вже будуть з'являтися колеса і вдосконалюватися форма, а в десятому поколінні утворена машина буде здатна долати пристойні відстані.

http://megaswf.com/serve/102223/

Генетичний алгоритм використовується для створення автомобіля з бібліотеки Box2D. Кольори показують кросинговер і мутацію для кожної особини популяції. Можна вибирати коефіцієнт мутації. Часто генеруються життєздатні моделі.

Ця програма використовує генетичний алгоритм для розробки двовимірного автомобіля, який буде "оптимальним" для конкретної місцевості. Автомобіль має два колеса і два навантаження. Вихідні позиції і радіуси цих чотирьох об'єктів можуть бути вибрані за допомогою алгоритму. Об'єкти пов'язані пружинами, довжина яких так само обирається за алгоритмом. Навантаження ніколи не повинні торкатися землі.

Оптимальність часткового рішення (фітнес-функція придатності) визначається тим, наскільки довго воно існує, перш ніж:

• Маса торкнеться землі.
• Закінчиться час.

На початку, алгоритм навіть не знає, що колеса торкаються поверхні. Іноді можна побачити, як з'являються і зникають різні види - наприклад, "уніцикли", особливо на ранніх стадіях прогресу алгоритму.

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

Перетворення слів за допомогою генетичного алгоритму

http://planetcalc.ru/475/
http://planetcalc.ru/638/

Емулятор покроково перетворює задане слово в інше задане слово, заміною однієї букви в попередньому слові, так щоб на кожному кроці виходило правильне слово. Емулятор працює зі словами, які складаються з 4 або 5 літер.

Користувач задає максимальну кількість поколінь і розмір популяції. Після обчислень на екран виводиться весь ланцюжок перетворень з тлумаченням кожного слова.

Рішення задачі комівояжера з використанням генетичних алгоритмів

http://www.lalena.com/AI/Tsp/

Задача комівояжера (Travelling salesman problem, TSP) - одна з найвідоміших задач комбінаторної оптимізації, що полягає у знаходженні самого вигідного маршруту, що проходить через зазначені міста хоча б по одному разу з наступним поверненням в початкове місто. В умовах задачі вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості і т. п. Як правило, вказується, що маршрут повинен проходити через кожне місто тільки один раз.

Задача колективної роботи з використанням генетичних алгоритмів

http://www.lalena.com/AI/Ant/

ANT є генетичною програмою, яка емулює поведінку мурах у пошуку їжі. Для вирішення такої проблеми мурахи повинні діяти колективно й узгодженно. Програму поведінки мурах закладено в тренажер, який містить такі дії як: Просуватися Вперед, Забирати Їжу тощо. Генетична програма еволюціонує, що дозволяє мурахам швидше дістатися до їжі.

Порядок роботи

1. Запустити програми.
2. Уважно ознайомитися з методиками використання генетичних алгоритмів.
3. Пройти всі кроки тестових завдань і змінити налаштування програм.
4. Проаналізувати отримані результати і зробити висновок.

Зміст звіту

1. Назва та мета виконання лабораторної роботи.
2. Можливості генетичних алгоритмів і суттєві фактори, що впливають на отримані результати.
3. Характеристика основних параметрів налаштування.
4. Скріншоти виконання робіт
5. Аналітичні висновки щодо властивостей програм та отриманих результатів.