Генетические алгоритмы
В этом разделе собраны работы по Генетическим Алгоритмам (ГА).
Генетический алгоритм - метод эволюционного поиска, алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым проблемам через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «кроссовера», который производит операцию, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд (англ. John Holland), книга которого «Адаптация в естественных и искусственных системах» (англ. Adaptation in Natural and Artificial Systems) является основополагающим трудом в этой области исследований.
Для более подробной информации смотрите статью в Википедии.
Использование генетических алгоритмов в проблеме автоматического написания программ
- именно так звучит тема моей дипломной работы 2006 года.
Если вкратце, то идея такова. (Предполагается, что читателю известен принцип работы генетического алгоритма (ГА) - метода эволюционного поиска. Дополнительную информацию о ГА можно найти в .)
Перед ЭВМ ставится задача самой отыскать необходимый алгоритм для решения той или иной задачи.
Имеется модель этой самой ЭВМ, которая в работе называется "вычислитель". Каждая хромосома ГА представляет собой некоторую программу для этого вычислителя, а каждый ген - инструкцию языка программирования, который понимает "вычислитель". Таким образом, нахождение оптимального алгоритма сводится к оптимизации популяции прогамм. Фитнесс-функцией является оценка эффективности той или иной программы-хромосомы, основанная на: 1) критерии, достигнута ли цель или нет и насколько близко программа достигла цели, 2) время, потраченное программой, 3) длина программы.
Небольшая иллюстрация работы программы:
График зависимости эффективности алгоритма от длины программы
Здесь на оси X расположена длина программы в байтах, на оси Y - значение фитнесс-функции.
Для простоты в качестве цели использовалась хорошо изученная задача сортировки массива.
Выкладываю во всеобщий доступ:
- Пояснительную записку (250Kb, ZIP) с описанием работы программы, которая представлена ниже,
- Исходные коды программы: Интерпретатор (16Kb, ZIP) | Интерпретатор+ГА (18Kb, ZIP),
- Сама программа: Интерпретатор (203Kb, ZIP) | Интерпретатор+ГА (912Kb, ZIP) .
Для удобства программа разделена на две практически независимые программы: одна - наглядно демонстрирует работу "вычислителя", выполняя (интерпретируя) какую-либо программу-хромосому, а вторая - собственно реализует вышеизложенные идеи, представляя собой Интерпретатор+ГА.
Для запуска "Интерпретатора", скорее всего, понадобится установленный Delphi 7 версии (не проверялось). "Интерпретатор+ГА" можно запускать на любой Windows - системе.
Все написано на Delphi 7, ОС Windows. При реализации ГА использовался модуль для Delphi от . (Если вы хотите откомпилировать приведённые выше примеры, этот модуль нужно установить как написано в инструкции.) Там же вы найдёте, что такое генетические алгоритмы, а также много интересного на тему искусственного интеллекта.
Реализация генетических алгоритмов в среде MATLAB v6.12
- а это одна из ранних моих работ, курсовая за 2003 год.
В пакете MATLAB v6.12 есть такие разделы искусственного интеллекта, как нечёткая логика и нейронные сети, однако нет такого пакета, как генетические алгоритмы. Данная работа призвана восполнить это пробел, и представляет собой пакет, который реализует генетические алгоритмы в MATLAB v6.12.
Иллюстрация работы ГА для задачи коммивояжёра:
Данный модуль даёт возможность строить в МатЛабе системы искусственного интеллекта с привлечением всех его разделов.
Как обычно, выкладываю:
1) Пояснительную записку (ZIP, 35Kb)
2) Исходные коды модуля для МатЛаб (ZIP, 25Kb)
Для установки модуля в МатЛаб читайте документацию МатЛаба!