Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 23
Ой, что-то в заголовке пошло не так.
Не только в заголовке..
Ваша проблема — отсутствие фундаментальных знаний. Вы верно плохо учились в школе.
Проблема остановки
Проблема остановки
Я правильно понял, что «хромосома» — это состояние машины, а выбор одной из трёх её частей — определяется символом под кареткой?
Т.е. состояния всего три? Довольно слабая машина получается, но принцип понятен.
А как быть, если каретку не нужно смещать?
3-й и 4-й знак кодирует номер хромосомы, к которой нужно перейти. Остановка программы
q1 **00*
q2 **01*
q3 **10*
STOP **11*
Т.е. состояния всего три? Довольно слабая машина получается, но принцип понятен.
5-й знак кодирует в какую сторону передвинуть считывающий головку, над читаемым кодом.
R ****0
L ****1
А как быть, если каретку не нужно смещать?
Я правильно понял, что «хромосома» — это состояние машины, а выбор одной из трёх её частей — определяется символом под кареткой?
Да так и есть. Машина автоматически переходит к той части хромосомы, в соответствие с символом под кареткой.
допустим есть хромосома- 10011 10110 10011 под кареткой находится символ «1» или в понимание машины «10» в двоичном коде или 2 в десятичном и это говорит что машина должна выполнить третью часть (если считать и ноль за число) хромосомы.
Т.е. состояния всего три? Довольно слабая машина получается, но принцип понятен.
количество хромосом можно увеличить но также нужно будет увеличить резерв под эти нужды и заранее дать инструкции для МТ какая связка ген за что отвечает.
немножко другой вариант для примера.
STOP **000*
q1 **001*
q2 **010*
q3 **011*
q4 **100*
q5 **101*
А как быть, если каретку не нужно смещать?
все тоже самое как и предыдущем примере. просто добавив 1 ген
******00 стоять на месте
******01 на право
******10 на лево
спасибо за критику. наводит на мысли.
Короче, по существу. Генерация алгоритмов при помощи генетических алгоритмов на 1й взгляд выглядит привлекательно, но на деле не работает. На этапе отбора мы неизбежно натыкаемся на две фундаментальные неразрешимые (доказано что неразрешимые) проблемы: проблема доказательства корректности алгоритма, проблема остановки, которая является частным случаем проблемы доказательства корректности алгоритма.
Чтобы решить является ли алгоритм корректным, мы должны скормить ему все возможные последовательности входных данных. Ну нету другого способа. Что, естественно, невозможно. В случае с классическим определением алгоритмов через машину Тьюринга или алгорифмы Маркова входные данные представляют собой счетную бесконечность. Ладно мы можем взять какой-то промежуток входных данных. Но это нам совершенно никак не гарантирует того, что за пределами этого промежутка алгоритм будет работать корректно. Ну и зачем нам такой алгоритм, если для каждой возможной последовательности данных мы уже рассчитали выходное значение?
А проблема остановки просто усложняет нам жизнь вопросом: сколько нам ждать пока сгенерированный алгоритм закончит работать? Ну и в ходе генерации мы получим массу промежуточных алгоритмов которые будут зацикливаться и съедать всё наше время.
Но даже в случае успеха на выходе вы получите кашу, разобраться в которой будет невозможно. Эволюция редко дает оптимальное решение.
И напоследок, рекомендую упражняться с алгорифмами Маркова.
Чтобы решить является ли алгоритм корректным, мы должны скормить ему все возможные последовательности входных данных. Ну нету другого способа. Что, естественно, невозможно. В случае с классическим определением алгоритмов через машину Тьюринга или алгорифмы Маркова входные данные представляют собой счетную бесконечность. Ладно мы можем взять какой-то промежуток входных данных. Но это нам совершенно никак не гарантирует того, что за пределами этого промежутка алгоритм будет работать корректно. Ну и зачем нам такой алгоритм, если для каждой возможной последовательности данных мы уже рассчитали выходное значение?
А проблема остановки просто усложняет нам жизнь вопросом: сколько нам ждать пока сгенерированный алгоритм закончит работать? Ну и в ходе генерации мы получим массу промежуточных алгоритмов которые будут зацикливаться и съедать всё наше время.
Но даже в случае успеха на выходе вы получите кашу, разобраться в которой будет невозможно. Эволюция редко дает оптимальное решение.
И напоследок, рекомендую упражняться с алгорифмами Маркова.
Никоим образом не отрицаю ваши аргументы, но! В общем случае генетические алгоритмы не обязаны выдавать стопроцентно правильный результат, они предназначены выдавать какой-то удовлетворительный результат. Конечно, в описанной задаче, когда у нас вообще-то имеется эталон решения, это не имеет никакого смысла, но если немножко перестроить задачу, например, в сторону «найти самый короткий/быстрый конечный автомат для эталона», то может быть оно и сканает. Конечно, проблема остановки остается открытой, и вероятно на достаточно больших эталонах и входных данных все наши автоматы будут вылетать по заданному таймауту, но отсутствие результата тоже результат, в конце концов.
PS: Под «коротким» я имел в виду только количество состояний.
PS: Под «коротким» я имел в виду только количество состояний.
В общем случае генетические алгоритмы не обязаны выдавать стопроцентно правильный результат, они предназначены выдавать какой-то удовлетворительный результат.
Уверяю вас, в случае генерации алгоритма генетическим алгоритмом мы скорее всего получим алгоритм, который будет корректен ТОЛЬКО на тестовой выборке. Можно ли назвать такой результат удовлетворительным? Вряд ли.
Получить самый короткий алгоритм или конечный автомат тоже задача не очень хорошая для генетических алгоритмов. Эволюция плохо за собой убирается.
Уверяю вас, в случае генерации алгоритма генетическим алгоритмом мы скорее всего получим алгоритм, который будет корректен ТОЛЬКО на тестовой выборке. Можно ли назвать такой результат удовлетворительным? Вряд ли.
Получить самый короткий алгоритм или конечный автомат тоже задача не очень хорошая для генетических алгоритмов. Эволюция плохо за собой убирается.
в случае генерации алгоритма генетическим алгоритмом мы скорее всего получим алгоритм, который будет корректен ТОЛЬКО на тестовой выборке
Я собственно сказал то же самое: имея тестовую выборку мы уже имеем решение задачи в самом точном виде. Если для ввода 00 вывод 0, а для 11 вывод 1, то ни один генетический алгоритм не скажет нам, это конъюнкция или дизъюнкция, я понимаю.
Но если для оценки успешности мы будем смотреть именно на то, как эволюция за собой убралась, разве она не начнет убираться?
Наверное, всё же, Тьюринга в заголовке.
И хотелось бы увидеть прототип. Хоть и настроен несколько пессимистично, жду продолжения.
И хотелось бы увидеть прототип. Хоть и настроен несколько пессимистично, жду продолжения.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Генетические алгоритмы и Машина Тьюринга