Размышления , о применении генетического алгоритма для машины Тьюринга.
Есть некоторая информация, полученная из внешней среды, представленная в двоичном коде, и есть Машина Тьюринга.
Что, если мы возьмем и применим генетический алгоритм для создания программы? Машина Тьюринга .
Который, в свою очередь, преобразует определенные данные и сравнивает результаты выполнения модифицированной программы со стандартным решением.
Возьмем в качестве примера простейший алгоритм для МТ.
Увеличение двоичного числа на единицу.
Это выглядит так:
1q1-> 1q1R 0q1-> 0q1R Bq1-> Bq2L 1q2-> 0q2L 0q2-> 1q3L Бк2-> 1СТОП 0q3-> 0q3L 1q3-> 1q3L Bq3-> BSTOPRНо нам нужно получить его с помощью генетического алгоритма.
1. Генная инженерия
Для генетического алгоритма, строящего программу «Машина Тьюринга», нам понадобится.Изобрести геном из конечного набора вариаций хромосом.
Который будет состоять из определенного алфавита команд для машины Тьюринга.
если символ «нулевой» если персонаж "один" перейдите к номеру детали кода.
если символ отсутствует переместить карету влево переместить каретку вправо стереть символ написать символ 0 напиши символ 1 остановить программу Разделим геном на участки, Хромосомы, каждая из них будет представлять позицию программы машины Тьюринга, а хромосому разделим на 3 отдельные части (так сказать, на дополнительные хромосомы) соизмеримые с алфавитом машины и в каждой части мы кодируем действие, необходимое для выполнения машиной.
Три действия будут закодированы в двоичном формате: 1-й и 2-й символы кодируют символ, который необходимо поместить в читаемый код. В этом примере.
Нет символа 00*** Ноль 01*** Блок 10*** 3-й и 4-й символы кодируют номер хромосомы, к которой нужно перейти.
Остановка программы квартал 1 **00* квартал 2 **01* кв3 **10* СТОП **11* Пятый символ кодирует направление перемещения считывающей головки над читаемым кодом.
Р****0 Л****1 И отсюда у нас есть команда, в двоичном коде размером 5 бит. Судя по вышесказанному, геном будет состоять из трёх хромосом, а их 5х3=15 символов.
Индивид будет состоять из 15х3=45 символов.
2. Приготовление «чашки Петри»
Для реализации генерации алгоритма нам понадобится.Генетический материал.
С помощью программы, генерируемой случайными строками двоичного кода.
Программа разведения.
Который будет скрещивать выбранные генотипы.
Так сказать, «Обратная машина Тьюринга».
В котором будет храниться исходная лента «Бесконечная» и необходимая версия после прохождения генома, сгенерированного генетическим алгоритмом.
Примеры лент:
Стартовая лента – Окончательный результат.
0001- 0010
0100- 0101
1011- 1100 
Требование к «обратной машине Тьюринга».
Уметь читать и обрабатывать генетический материал.
Сравните результат, полученный на ленте, со своим стандартным результатом, в процентах согласия.
Уметь идентифицировать геном, не имеющий окончательного результата.
Уничтожить геном, не прошедший проверку.
3. Генерация начальной популяции
Сгенерируйте начальную популяцию из слов двоичного кода.в пяти символах по 9 слов для каждого человека.
4. Отбор населения
Для отбора видов отбираются особи с более высоким процентом совпадения между результирующей лентой и эталонной лентой.Тоже с теми же результатами.
Победителем становится особь, длина гена которой короче другой.
5. пересечение
отбор видов происходит путем обмена словами из генома двух подвидов, имеющих наибольший процент совпадения результата с эталоном.
6. мутация
Неотъемлемая часть эволюции.При этом мутация происходит в отдельных словах представителя вида.
Также мутация подразумевает добавление дополнительных хромосом, что важно для решения более сложных задач.
Добавление дополнительных слов в хромосомы при расширении алфавита МТ.
В случае увлечения алфавитом или хромосомами в начале генома требуются инструкции по МТ и правилам чтения.
Так как изменение количества хромосом и количества букв в алфавите повлияет на количество битов/генов в геноме.
7. резюме
Теоретически полученные таким образом алгоритмы будут наиболее компактными и эффективными.
И самое главное, понятное человеку.
Спасибо за внимание.
Это моя первая статья на Хабрахабе.
Планирую перейти от теории к практике, с дальнейшим написанием статьи.
Теги: #генетический алгоритм #алгоритм #машина Тьюринга #ИИ #искусственный интеллект #Машинное обучение
-
Крепостное Право В Ит
19 Oct, 24 -
Изменение Голосов За Тексты/Темы/Комментарии
19 Oct, 24 -
Несколько Слов О Дневнике Проекта
19 Oct, 24 -
Подскажите, Во Что Инвестировать
19 Oct, 24 -
Настройка Панелей Инструментов Smplayer
19 Oct, 24
