[Из песочницы] Генетические алгоритмы и Машина Тьюренга
Есть некая информация получаемая из внешней среды, представленная в бинарном коде, и есть Машина Тьюринга. А что если, взять и применить генетический алгоритм для составления программы Машина Тьюринга.
Которая, в свою очередь, будет конвертировать определенные данные, и сравнивать результаты выполнения модифицированной программы с эталоном решения.
Возьмем для примера самый простой алгоритм для МТ. Увеличивающий бинарное число на единицу. Выглядит он так:
1q1→1q1R
0q1→0q1R
Bq1→Bq2L
1q2→0q2L
0q2→1q3L
Bq2→1STOP
0q3→0q3L
1q3→1q3L
Bq3→BSTOPR
Но нам его надо получить с помощью генетического алгоритма.
1. Генная инженерия
Для генетического алгоритма, построения программы Машина Тьюринга, нам потребуется. Придумать геном, из конечного множества вариаций хромосом. Которые будут состоять из определенного алфавита команд для машины Тьюринга.
- если символ «нуль»
- если символ «один»
- перейти к части кода №
- если символ отсутствует
- переместить каретку влево
- переместить каретку вправо
- затереть символ
- написать символ 0
- написать символ 1
- стоп программа
Разделим геном на отсеки, Хромосомы, каждой из них будет представлять позицию программы машины Тьюринга, и разделим хромосому на 3 отдельные части (так сказать на дополнительные хромосомы) соразмерно алфавиту машины и в каждой части закодируем действие необходимое выполнить машиной.
Три действия будут закодированы в двоичной системе:
- 1-й и 2-й знак кодируют символ, который нужно поставить в читаемый код.
В данном примере.
Символ отсутствует 00***
Нуль 01***
Единица 10*** - 3-й и 4-й знак кодирует номер хромосомы, к которой нужно перейти. Остановка программы
q1 **00*
q2 **01*
q3 **10*
STOP **11* - 5-й знак кодирует в какую сторону передвинуть считывающий головку, над читаемым кодом.
R ****0
L ****1
И из этого мы имеем команду, в двоичном коде, размером в 5 бит.
Из выше перечисленного, геном будет состоять из трех хромосом, а те из 5×3=15 знаков.
Особь будет состоять из 15×3=45 знаков.
2. Подготовка «Чашки Петри»
Для реализации генерации алгоритма нам понадобится.
Генетический материал.
С генерированный программой генерации случайных строк бинарного кода.
Программа селекции.
Которая будет скрещивать, прошедший отбор генотипы.
Так сказать «Машина Тьюринга на оборот».
В которых будет хранится начальная «Бесконечная» лента и требуемый, после прохождения с генерированного генетическим алгоритмом генома, ее вариант.
Примеры лент:
Начальная лента — Конечный результат.
0001 0010
0100 0101
1011 1100
Требование к «машине Тьюренга на оборот».
- Уметь читать и обрабатывать генетический материал.
- Сравнивать полученный результат на ленте, со своим эталоном результата, в процентах совпадения.
- Уметь выявлять геном не имеющий конечного результата.
- Уничтожать геном не прошедший проверку.
3. Генерация начальной популяции
Начальную популяцию генерировать из слов двоичного кода. в пять знаков, длиной в 9 слов для каждой особи.
4. Отбор популяции
Особи у которых процент совпадения ленты результата с эталонной лентой больше, проходят на селекцию видов.
Также при одинаковых результата. Выигрывает та особь, длина гена которой, короче другой.
5. скрещивание
селекция видов происходит обменом слов генома двух подвидов подошедшие к наибольшему проценту совпадения результата и эталона.
6. мутация
Неотъемлемая часть эволюции. В данном случае, происходит мутация отдельных слов представителя вида. Также мутация подразумевает добавление дополнительной хромосом, что не мало важно для решения более сложных задач. Добавление дополнительных слов в хромосомы с расширением алфавита МТ.
В случая увлечения алфавита, или хромосом, требуется указание в начале генома инструкции для МТ, правил чтения. Так как изменение количества хромосом и количество букв в алфавите, скажется на количество бит\ген в геноме.
7. итог
Теоретически, алгоритмы полученные таким видом будут самые компактные и эффективными.
А самое главное, понятные человеку.
Спасибо за внимание.
Это моя первая статья на Хабрахабе. Планирую перейти от теории к практике, с дальнейшим написанием статьи.
Комментарии (5)
Shtucer
22 февраля 2017 в 10:52
+5↑
↓
Ой, что-то в заголовке пошло не так.
devpony
22 февраля 2017 в 11:15
+3↑
↓
Не только в заголовке…
-
Shtucer
22 февраля 2017 в 11:34
0↑
↓
О, да!
impwx
22 февраля 2017 в 11:44
0↑
↓
Мне больше всего понравился пассаж «машине Тьюренга на оборот».-
Shtucer
22 февраля 2017 в 11:47
0↑
↓
А я вот не могу выбрать, всё прекрасное. Но мне обидно, что я никак не могу заставить себя вникать в суть статьи, она же там должна быть. Не зря же её из песочницы вынули.
