- •Глава 1. Генетические алгоритмы
- •Глава 2. Задачи оптимизации
- •Глава 3. Программная реализация. Создание пособия по генетическим алгоритмам
- •Глава 1: генетические алгоритмы
- •1.1. Естественный отбор в природе
- •1.2. Представление объектов. Кодирование признаков
- •1.3 Основные генетические операторы
- •1.4. Схема функционирования генетического алгоритма
- •2.1 Задачи, решаемые с помощью генетических алгоритмов
- •2.2 Математическая постановка задачи оптимизации
- •2.3 Решение Диофантова уравнения
- •Глава 2. Задачи оптимизации.
- •2.4. Пути решения задач оптимизации
- •2.5 Решение задачи коммивояжера.
- •Глава 3. Программная реализация. Создание пособия по генетическим алгоритмам.
- •3.1 Обоснование выбора программного обеспечения
- •3.2 Описание программной реализации
- •Заключение
- •Библиография
Заключение
Мы с вами проделали большой путь, открывая для себя генетические алгоритмы, их, казалось бы, тривиальную и одновременно с этим гениальную идею, взятую из природы. В ходе изучения мы многократно указывали на достоинства и недостатки генетических алгоритмов. Среди наиболее значимых положительных сторон, можно отметить:
Первый случай: когда не известен способ точного решения задачи. Если мы знаем, как оценить приспособленность хромосом, то всегда можем заставить генетический алгоритм решать эту задачу.
Второй случай: когда способ для точного решения существует, но он очень сложен в реализации, требует больших затрат времени и денег, то есть, попросту говоря, дело того не стоит. Пример - создание программы для составления персонального расписания на основе техники покрытия множеств с использованием линейного программирования.
Что же касается недостатков, то в общем случае генетические алгоритмы не находят оптимального решения очень трудных задач. Если оптимальное решение задачи (например, задача коммивояжера с очень большим числом городов) не может быть найдено традиционными способами, то и генетический алгоритм вряд ли найдет оптимум
Наряду с генетическими алгоритмами известны и другие методы решения задач оптимизации, основанные на природных механизмах, такие как моделирование отжига (simulated annealing) и табу-поиск (taboo search). Но эффект случайности, который безусловно присутствует при решении генетическим алгоритмом, очень воодушевляет.
Несмотря на небольшое количество задач, которое мы с вами рассмотрели: решение Диофантова уравнения и задачу коммивояжера, мы полностью подтверждаем нашу гипотезу. Задачи оптимизации (и не только) успешно решаются при помощи генетических алгоритмов.
Библиография
Вентцель Е.С. «Исследование операций», - М.: 1972 г.
Гальцына О.Л., Попов И.И. «Основы алгоритмизации и программирования».
Грешилов А.А. «Как принять наилучшее решение в реальных условиях», - М.: 1991 г., стр. 164-170
Корнеев В.В., Гареев А.Ф. «Базы данных. Интеллектуальная обработка данных», М.: 2001г., стр. 220
Коршунов Ю.М. «Математические основы кибернетики. Для студентов вузов», - М.: 1987 г., стр. 67-89
Леонов О.И. «Теория графов».
Майника Э., «Алгоритмы оптимизации на сетях и графах.» - М.: 1981
Новиков Ф.А. «Дискретная математика для программистов».
«Генетические алгоритмы: почему они работают?»/ Компьютерра, № 11, 1999 год
Де Джонг К. А. Введение ко второму специальному выпуску по генетическим алгоритмам. Машинное обучение, №5(4), с. 351-353
Электронные источники:
«Генетические алгоритмы по-русски» - http://www.chat.ru/~saisa
«Нейропроект. Аналитические технологии XXI века» - http://www.neuroproject.ru
«Научное издательство ТВП» - http://www.tvp.ru/mathem3.htm
«Факультет вычислительной математики и кибернетики МГУ (ВМиК)» - http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html
«Neural Bench Development» - http://www.neuralbench.ru/rus/theory/genetic.htm
«Журнал "Автоматизация Проектирования"» - http://www.opensystems.ru/ap/1999/01/08.htm
«(EHIPS) Генетические алгоритмы» - http://www.iki.rssi.ru/ehips/genetic.htm
«SENN Генетические Алгоритмы» - http://fdmhi.mega.ru/ru/senn_ga.htm
Хорева Е.В. Курсовая работа. Тема «Применение генетических алгоритмов для решения задач оптимизации»-КГПУ.: 2007г.
«Лекции по нейронным сетям и генетическим алгоритмам» - http://infoart.baku.az/inews/30000007.htm
