Использование генетических алгоритмов в проблеме автоматического написания программ
- именно так звучит тема моей дипломной работы 2006 года.
Если вкратце, то идея такова. (Предполагается, что читателю известен принцип работы генетического алгоритма (ГА) - метода эволюционного поиска. Дополнительную информацию о ГА можно найти в .)
Перед ЭВМ ставится задача самой отыскать необходимый алгоритм для решения той или иной задачи.
Имеется модель этой самой ЭВМ, которая в работе называется "вычислитель". Каждая хромосома ГА представляет собой некоторую программу для этого вычислителя, а каждый ген - инструкцию языка программирования, который понимает "вычислитель". Таким образом, нахождение оптимального алгоритма сводится к оптимизации популяции прогамм. Фитнесс-функцией является оценка эффективности той или иной программы-хромосомы, основанная на: 1) критерии, достигнута ли цель или нет и насколько близко программа достигла цели, 2) время, потраченное программой, 3) длина программы.
Небольшая иллюстрация работы программы:
График зависимости эффективности алгоритма от длины программы
Здесь на оси X расположена длина программы в байтах, на оси Y - значение фитнесс-функции.
Для простоты в качестве цели использовалась хорошо изученная задача сортировки массива.
Выкладываю во всеобщий доступ:
- Пояснительную записку (250Kb, ZIP) с описанием работы программы, которая представлена ниже,
- Исходные коды программы: Интерпретатор (16Kb, ZIP) | Интерпретатор+ГА (18Kb, ZIP),
- Сама программа: Интерпретатор (203Kb, ZIP) | Интерпретатор+ГА (912Kb, ZIP) .
Для удобства программа разделена на две практически независимые программы: одна - наглядно демонстрирует работу "вычислителя", выполняя (интерпретируя) какую-либо программу-хромосому, а вторая - собственно реализует вышеизложенные идеи, представляя собой Интерпретатор+ГА.
Для запуска "Интерпретатора", скорее всего, понадобится установленный Delphi 7 версии (не проверялось). "Интерпретатор+ГА" можно запускать на любой Windows - системе.
Все написано на Delphi 7, ОС Windows. При реализации ГА использовался модуль для Delphi от . (Если вы хотите откомпилировать приведённые выше примеры, этот модуль нужно установить как написано в инструкции.) Там же вы найдёте, что такое генетические алгоритмы, а также много интересного на тему искусственного интеллекта.