- PVSM.RU - https://www.pvsm.ru -
Размышления , о применение генетического алгоритма для Машина Тьюринга.
Есть некая информация получаемая из внешней среды, представленная в бинарном коде, и есть Машина Тьюринга. А что если, взять и применить генетический алгоритм для составления программы Машина Тьюринга [1].
Которая, в свою очередь, будет конвертировать определенные данные, и сравнивать результаты выполнения модифицированной программы с эталоном решения.
Возьмем для примера самый простой алгоритм для МТ. Увеличивающий бинарное число на единицу. Выглядит он так:
1q1->1q1R
0q1->0q1R
Bq1->Bq2L
1q2->0q2L
0q2->1q3L
Bq2->1STOP
0q3->0q3L
1q3->1q3L
Bq3->BSTOPR
Но нам его надо получить с помощью генетического алгоритма.
Для генетического алгоритма, построения программы Машина Тьюринга, нам потребуется. Придумать геном, из конечного множества вариаций хромосом. Которые будут состоять из определенного алфавита команд для машины Тьюринга.
Разделим геном на отсеки, Хромосомы, каждой из них будет представлять позицию программы машины Тьюринга, и разделим хромосому на 3 отдельные части (так сказать на дополнительные хромосомы) соразмерно алфавиту машины и в каждой части закодируем действие необходимое выполнить машиной.
Три действия будут закодированы в двоичной системе:
И из этого мы имеем команду, в двоичном коде, размером в 5 бит.
Из выше перечисленного, геном будет состоять из трех хромосом, а те из 5х3=15 знаков.
Особь будет состоять из 15х3=45 знаков.
Для реализации генерации алгоритма нам понадобится.
Генетический материал.
С генерированный программой генерации случайных строк бинарного кода.
Программа селекции.
Которая будет скрещивать, прошедший отбор генотипы.
Так сказать «Машина Тьюринга на оборот».
В которых будет хранится начальная «Бесконечная» лента и требуемый, после прохождения с генерированного генетическим алгоритмом генома, ее вариант.
Примеры лент:
Начальная лента — Конечный результат.
0001- 0010
0100- 0101
1011- 1100
Требование к «машине Тьюринга на оборот».
Начальную популяцию генерировать из слов двоичного кода. в пять знаков, длиной в 9 слов для каждой особи.
Особи у которых процент совпадения ленты результата с эталонной лентой больше, проходят на селекцию видов.
Также при одинаковых результата. Выигрывает та особь, длина гена которой, короче другой.
селекция видов происходит обменом слов генома двух подвидов подошедшие к наибольшему проценту совпадения результата и эталона.
Неотъемлемая часть эволюции. В данном случае, происходит мутация отдельных слов представителя вида. Также мутация подразумевает добавление дополнительной хромосом, что не мало важно для решения более сложных задач. Добавление дополнительных слов в хромосомы с расширением алфавита МТ.
В случая увлечения алфавита, или хромосом, требуется указание в начале генома инструкции для МТ, правил чтения. Так как изменение количества хромосом и количество букв в алфавите, скажется на количество битген в геноме.
Теоретически, алгоритмы полученные таким видом будут самые компактные и эффективными.
А самое главное, понятные человеку.
Спасибо за внимание.
Это моя первая статья на Хабрахабе. Планирую перейти от теории к практике, с дальнейшим написанием статьи.
Автор: belkov_k_v
Источник [2]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/ii/245599
Ссылки в тексте:
[1] Машина Тьюринга: https://ru.wikipedia.org/wiki/Машина_Тьюринга
[2] Источник: https://habrahabr.ru/post/322370/?utm_source=habrahabr&utm_medium=rss&utm_campaign=sandbox
Нажмите здесь для печати.