Случайное программирование

lera98

Кто-нить касался такого вопроса? Будет интересно послушать мнения.
Дело в общем вот в чём: область данных забивают рандомными инструкциями и отправляют на исполнение.
ЗЫ: и долгое время любуются на акссесс виолэйшны...

Dasar

Для начала надо сделать интерпретатор максимально устойчивый к ошибкам.
т.е. чтобы переходы на неправильный адрес, обращение к несуществующей ячейке - превращалось при исполнении во что-то хорошее, а не в ошибку.
например, можно сделать круговую адресацию

lera98

Хороший способ избавиться от аксесс виолэйшнов, учту.
Для его воплощения, однако, придётся исполнять рандом-код не непосредственно на проце. Это вроде как минус.

Fragaria

а можно такой вопрос: нахуа?
какой смысл в исполнении случайных комманд? или эт из серии про миллион мартышек и собрание сочинений толстого?

durka82

Поищи инфу про генетическое программирование.
По крайней мере подходы к разработке, имхо, там должны быть похожие.

lera98

Фактически ты угадал. Не для набора собраний сочинений Толстого, конечно, а для мутационно-эволюционного развития программ без вмешательства человека.

lera98

Алгоритм генетического программирования:
Генерация случайного начального состояния.
Первое поколение создается из произвольно выбранных решений (хромосом). Это отличается от стандартных методов, когда начальное состояние всегда одно и то же.
Вычисление коэффициента выживаемости (fitness).
Каждому решению (хромосоме) сопоставляется некое численное значение, зависящее от его близости к ответу.
Воспроизводство.
Хромосомы, имеющие большую выживамость (fitness попадают к потомкам (которые затем могут мутировать) с большей вероятностью. Потомок, результат слияния 'отца' и 'матери', является комбинацей их ген. Этот процесс называется 'кроссиннговер' (crossing over).
Cледующее поколение.
Если новое поколение содержит решение, достаточно близкое к ответу, то задача решена. В противоположном случае оно проходит через тот же процесс. Это продолжается до достижения решения.
________________________________
Нет, это не то. Здесь ищется решение задачи, есть некая цель.
Я же не предполагаю изначально никакой цели. Просто хаос. Из которого вдруг может вылезти что-то интересное. Через N времени.

durka82

А кто тебе мешает поставить неопределенную цель?
Просто у тебя не будет критерия выживаемости.

Ivan8209

Создавать случайные колонии, запускать жизнь и втыкать.
---
"Бросая в воду камешки, смотри на круги, ими образуемые;
иначе такое бросание будет пустою забавою."

durka82

Вот и я про то же
Классический пример - игра Жизнь

lera98

Хе : )
Я не предполагаю _ничего_ насчёт процессов, происходящих во вселенной-ЗакольцованномУчасткеПамяти. Возможно, там не будет размножения, или будет так, как есть в нашем мире, или как-то совершенно по-другому. Возможно, там не будет понятия хромосом в том виде, в котором мне бы хотелось их видеть.
Одно точно знаю. Я введу насильственную мутацию. Т.е. иногда извне системы я буду менять случайный бит.

rosali

Около года назад я (посильно) участвовал в проекте, где на идеях генетического программирования генерировались деревья комбинаторов, которые потом интерпретировались. Если интересно, могу поискать в письмах ссылки на статьи. Вообще генетическое программирование довольно распространено (я имею ввиду по сравнению со "случайным" )

lera98

> деревья комбинаторов, которые потом интерпретировались
Фраза для меня неясная - кто, как и зачем будет интерпретировать лесопосадки Остапов Бендеров?
Ссылки на такие ресурсы - вещь полезная, давай.

bleyman

> Я же не предполагаю изначально никакой цели. Просто хаос. Из которого вдруг может вылезти что-то интересное. Через N времени.
Гы гы гы. 1) критерий "интересного" пожалуйста. Хоть один. 2) А теперь оцени отношения следующих величин: "интересные" программы, все программы, производительность твоего компа, возраст вселенной.
Я писал одну такую прогу давно. Там был как-бы рисковый асм на 9 инструкций (насколько я помню фиксированное количество байтовых переменных, а программа представляла собой просто фиксированное количество инструкций. Были джампы. Вроде как оно довольно быстро научалось делить (в отсутствие инструкции деления). Понятий "гена" и "скрещивания" там не было, просто мутации и оценка.
Один из полезных результатов - выяснил, что без специальных средств прогу на 30 инструкций понять невозможно. Вообще.
Прога проимелась вместе с винтом.
Я писал ещё одну такую прогу недавно. Она была несколько сложнее - там было понятие гена (цепочка инструкций + селектор и два адреса следующих генов; то же самое с селектором в центре, так что оно выглядело как буква Y (энтрипоинт снизу); или селектор в начале). Соответственно работает скрещивание и мутации на генном уровне (типа поменять их местами).
ВМ там была стековая.
Выяснилось, что что-то тут не то - бо умножать (в отсутствие соответствующей инструкции в языке) оно так и не научилось. Код получался несколько более читаемым, поэтому я даже выяснил в чем проблема.
Типа генерился ген, который брал некоторое достаточно большое количество ответов в одиночку (то есть завершал прогу) (что-то достаточно тупое было, вроде сложения аргументов он делал после чего дуплицировался на всю программу. Такая программа оказывалась устойчива к ошибкам и скрещиванию.
А потом у меня времени не стало, поэтому я забил её изучать.
Прога у меня валяется где-то.
ЗЫ: Мало кто задумывался над фразой про обезьян, время и Шекспира. Те, кто задумывался, точно знают, что это неправда. Эти обезьяны даже мой пост не напишут на самом деле.
Поэтому получить что-нибудь мало-мальски сложное без направленных эволюционных факторов невозможно.

rosali

Комбинаторы - это лямбда выражения без свободных переменных. Ладно, вобщем я пока положил, скоро сотру...

lera98

Ок, закачал.

gopnik1994

А теперь оцени отношения следующих величин: "интересные" программы, все программы, производительность твоего компа, возраст вселенной
Все зависит от начальных данных. Можно вообще задать один бит и ждать, пока он сам начнет размнодаться, а можно задать основные принципы эволюции и создать некое достаточно продвинутое "существо", обладающее уже некоторомы навыками. Например, научив его сразу размножаться, сэкономишь много времени.
А эволюция меряется не в годах, а в поколениях. Поэтому "существо" _обязано_ умирать. Когда природа "придумала" смерть и заложила это в генах, эволюция резко ускорилась благодаря осбождающимся ресурсам.
Задав время жизни своих "существ" равной сотне-другой инструкций, ты тоже можешь значительно ускорить эволюцию.

bleyman

Он их случайно собирался генерить, ага. Без эволюции.
Почитай другие мои посты лучше, а?
Да, естественно после пары сотен итераций прога считается зависшей и должна скинуться с ВМ.

gopnik1994

не итераций, а инструкций!

lera98

Кроме утрирования про один бит, ты во всём прав.
Непосредственно хочется увидеть, как тамошняя "природа" "научит" проги умирать. Увидеть рождение эволюционного процесса.

bleyman

ну типа да, инструкций. А какие ещё "итерации" могли иметься в виду?

mysha

Мало кто задумывался над фразой про обезьян, время и Шекспира. Те, кто задумывался, точно знают, что это неправда. Эти обезьяны даже мой пост не напишут на самом деле.
Поэтому получить что-нибудь мало-мальски сложное без направленных эволюционных факторов невозможно.
Мало ты похоже задумывался. Получить - легко, а вот выделить и осознать
все полезное полученное и в будущем использовать - практически нереально
без создния вышеупомянутых законов.
ЗЫ для любого эксперимента обязана быть цель - интерпретация результатов, иначе смысл эксперимента теряется, часто,
в процессе описания этой цели исчезает и нужда в эксперименте.
Случайное программирование, по здравому разумению, к полезным программам приведет с очень маленькой вероятностью
или мы не сможем понять полезность полученных программ, поэтому случайное программирование и не распространено -
мало кто к нему обращается дважды. (термин "случайное программирование" используется в определении автора треда)

bleyman

Зачем ты это мне говоришь?
Я это прекрасно понимаю всё.
Когда я писал свои проги, у меня была вполне конкретная цель: проверить возможность и эффективность воздейсвия определённых эволюционных факторов на "популяцию" случайно сгенерённых и случайно изменяемых факторов.
Результата я достиг, бтв.
FJ>Мало кто задумывался над фразой про обезьян, время и Шекспира. Те, кто задумывался, точно знают,
FJ>что это неправда. Эти обезьяны даже мой пост не напишут на самом деле.
BM>Мало ты похоже задумывался.
Поясни.

mysha

Поясни.
вот это я для тебя писал
Получить - легко, а вот выделить и осознать
все полезное полученное и в будущем использовать - практически нереально
без создния вышеупомянутых законов.
Все остальное было не тебе лично, извини - лень было на 2 поста разбивать.
Я имел ввиду, что получить, в частности шекспира - несложно, вот только
понять ценность, и смысл практически невозможно.
Например, твой пост - содержится в конкретном контексте, без которого он будет
довольно бессмысленен, поэтому выделить его из миллиардов случайных буквосочетаний
сложно, да и надо ли? Контекст обычно задается постановкой задачи, мартышки
же к сожалению набивают бесконтекстно.
Постановка же задачи у аффтора треда, похоже, состоит в самосовершенствовании через наблюдение
исполнения случайных последовательностей кодов, что сродни самосозерцанию .

bleyman

Получить более ста наперёд заданных символов невозможно.
Невозможно в принципе. Не хватит возраста вселенной.
Я об этом говорил.

lera98

Вариантов комбинаций 100 байт К: 256^100 < 10^250
Размер винта Р: 10^11 байт, возможный общекластерный 10^15 байт
Производительность обработки данных процом П: 10^7 б/с, прикидка для кластера 10^12 б/с
Возраст вселенной В: 4.2*10^11 < 10^12 секунд
Допустимое время ожидания Д: 10^3 с
К / (Р * П) > Д, даже К / (Р * П) > В
Вывод: таким методом результат технологически недостижим.
___________
Пусть идея ждёт новых технологий.

karkar

Был такой проект - TIERRA, если не ошибаюсь в названии. Там очень похожие были условия - простой код, циклическая память, в ней программы-существа, который должны мутировать, размножаться и развиваться, сражаясь друг с другом или вроде того. Результаты там получались весьма интересные, но очень нескоро - после многих недель работы..

lera98

Это ты говоришь о примере генетического программирования, которое может самовозникнуть из случайного.
Ясное дело, начиная сразу с генетического результат типа "жизнь" достигается во много порядков быстрее.
Оставить комментарий
Имя или ник:
Комментарий: