| Август 2008 | ||||||
| ПН | ВТ | СР | ЧТ | ПТ | СБ | ВС |
| 1 | 2 | 3 | ||||
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 |
Использование генетических алгоритмов в проблеме автоматического написания программ
- именно так звучит тема моей дипломной работы 2006 года.
Если вкратце, то идея такова. (Предполагается, что читателю известен принцип работы генетического алгоритма (ГА) - метода эволюционного поиска. Дополнительную информацию о ГА можно найти в .)
Перед ЭВМ ставится задача самой отыскать необходимый алгоритм для решения той или иной задачи.
Имеется модель этой самой ЭВМ, которая в работе называется "вычислитель". Каждая хромосома ГА представляет собой некоторую программу для этого вычислителя, а каждый ген - инструкцию языка программирования, который понимает "вычислитель". Таким образом, нахождение оптимального алгоритма сводится к оптимизации популяции прогамм. Фитнесс-функцией является оценка эффективности той или иной программы-хромосомы, основанная на: 1) критерии, достигнута ли цель или нет и насколько близко программа достигла цели, 2) время, потраченное программой, 3) длина программы.
Небольшая иллюстрация работы программы:
График зависимости эффективности алгоритма от длины программы
Здесь на оси X расположена длина программы в байтах, на оси Y - значение фитнесс-функции.
Для простоты в качестве цели использовалась хорошо изученная задача сортировки массива.
Выкладываю во всеобщий доступ:
- Пояснительную записку (250Kb, ZIP) с описанием работы программы, которая представлена ниже,
- Исходные коды программы: Интерпретатор (16Kb, ZIP) | Интерпретатор+ГА (18Kb, ZIP),
- Сама программа: Интерпретатор (203Kb, ZIP) | Интерпретатор+ГА (912Kb, ZIP) .
Для удобства программа разделена на две практически независимые программы: одна - наглядно демонстрирует работу "вычислителя", выполняя (интерпретируя) какую-либо программу-хромосому, а вторая - собственно реализует вышеизложенные идеи, представляя собой Интерпретатор+ГА.
Для запуска "Интерпретатора", скорее всего, понадобится установленный Delphi 7 версии (не проверялось). "Интерпретатор+ГА" можно запускать на любой Windows - системе.
Все написано на Delphi 7, ОС Windows. При реализации ГА использовался модуль для Delphi от . (Если вы хотите откомпилировать приведённые выше примеры, этот модуль нужно установить как написано в инструкции.) Там же вы найдёте, что такое генетические алгоритмы, а также много интересного на тему искусственного интеллекта.
| Прикрепленный файл | Размер |
|---|---|
| diplom2006.zip | 243.53 кб |
| interpretator.zip | 16.74 кб |
| interpretatorga.zip | 18.81 кб |
| interpretator_exe.zip | 203.5 кб |
| interpretatorga_exe.zip | 912.53 кб |
| genebase.zip | 83.38 кб |
- Блог пользователя andyceo
- версия для печати
- Комментировать
- 2469 просмотров
Комментарии
Очень
Очень интересная тема! Сам пробовал как-то. К сожалению у меня ничего путного не получилось.
Посмотрел исходные коды. Коментариев в коде почти нету... Жаль ;(
Сейчас копаю тему построения нейросети и её обучение методами ГА.
Очень хотелось бы пообщаться! ICQ 205429136 или по почте.
Приветствую! Я
Приветствую!
Я думаю, у меня тоже не очень выдающиеся результаты. По-поему, все в пределах статистической погрешности.
Чем длиннее программа, тем больше времени надо на ее выполнение, и тем больше вероятность того, что хромосома-программа содержит бессмысленные участки кода. Поэтому, как видно на графике, с увеличением длины программы эффективность практически не растет и держится на одном каком-то уровне.
Письмо у вас на почте должно быть.
Клёво
Это гениально, но пока не реализовано на уровне процессорных команд занимает больше времени, если я не ошибаюсь.
Уже реализовано давно
Насколько мне известно, специализированные чипы под те или иные алгоритмы уже давно серийно-массово выпускаются. По крайней мере, точно слышал о платах-ускорителях нейронных сетей для обычного писюка. Слышал об экспериментальных схемах, построенных на генетических алгоритмах. И уж точно есть микросхемы-кодеры-декодеры MP3, в наших плейерах и телефонах.
Но это всё неважно, ведь сама суть генетических алгоритмов заключается в том, что они работают гораздо быстрее точных математических методов в задачах, где требуется много вычислений дл определения максимума (минимума) - т.е. оптимального решения, но в то же время дают ошибку примерно 15-20% от самого оптимального значения. Такова цена за скорость вычислений. Если сказать математически ещё точнее, то генетические алгоритмы идеальны для задач оптимизации многопараметрических функций. Если функция зависит от, скажем, десятков или даже сотен аргументов, то стандартными математическими моделями вычислять её экстремум будет крайне затратно, тогда как для генетического алгоритма это просто увеличенная длина хромосомы и переписанная фитнесс-функция.