Форум: Проблемы искусственного интеллекта

Регистрация | Вход

Все темы | Новая тема  Стр.1 (1)     Поиск:
Автор	Тема: Алгоритм компьютерной модели искусственной эволюции
Koks Сообщений: 3	Алгоритм компьютерной модели искусственной эволюции Добавлено: 19 авг 06 11:51 Хочу предложить на рассмотрение алгоритм компьютерной модели искусственной эволюции, подобную той, которая произошла при образовании жизни на земле. Во первых необходимо написать операционную систему моделирования виртуального мира. Её задачи должны заключаться в том чтобы выделять участки памяти для программ на асемблере, осуществлять функции контроля над этими програмами, и поддерживать интерфейс ввода вывода информации. Затем на асемблере пишется программа клиент, ее алгоритм заключается в том, чтобы вывести в порт вывода свою копию, несколько видоизменив её. Видоизменение может иметь один из трех вариантов: 1 Замена одного байта своего кода на произвольный. 2 отрезание от кода последнего байта. 3 Добавление в конец кода произвольного байта. Операционная система создает пространство для вновь образованной программы, и пытается запустить её. Если код завершения программы “ret” не присходит достаточно долгое время, операционная система считает эту программу мертвой, завершает её принудительно, и стирает из памяти. Если в процессе работы программы всетаки пришел код возврата, но в порт вывода ничего отправленно не было, система считает программу не способной к размножению и стирает её из памяти. Если в порт вывода был слит какой либо код, и он больше на один байт создавшей его программы, либо меньше на один байт, либо равен ей по размеру, но имеет другую контрольную сумму, и при этом создавшая его и программа завершилась удачно, происходит сохранение создавшей этот код программы, и происходит попытка запустить получившийся код с теми же условиями. Если получившийся код оказался нежизнеспособным, запускается снова породившая его программа. Если эта программа из к примеру 10 попыток не смогла сгенерировать жизнеспособный код, стираем её и возвращаемся к её родителю, и так далее. Единственная программа на которую не действует ограничение в 10 попыток, это самая первая, созданная человеком. Кроме интерфейса вывода своих копий у программ для общения с миром должен быть и порт из внешнего мира, пока нету четкого представления по какому протоколу он будет работать, ясно только что на начальной стадии развития он не будет востребован программами, и его можно будет реализовать позже, при успешной эволюции. Могу предположить что первым, прошедшим все проверки работоспособным детищем исходной программы будет лишь та, у которой регистр длинны сливаемой копии случайно увеличиться на 1. Таким образом сначала будут выживать только программы увеличивающие свои копии. Но это совершенно естественный процесс эволюции. Рано или поздно в бессмысленных наборах байт образуются вполне работоспособные цепочки, некоторые из них возможно будут обращаться к внешнему миру. Естественно это не произойдет в первом миллиарде запусков, вспомним как долго на земле идет развитие живых организмов. Ясно только одно, если запустить этот механизм, он будет постоянно генерировать все новые и новые програмные коды, и рано или поздно можно будет констатировать что он действительно эволюционирует. Я описал только общие принципы работы этой системы, не углубляясь в реализацию мелочей. Если кто нибудь считает эту теорию ошибочной, готов выслушать, и подискутировать. [Ответ][Цитата]
mserg Сообщений: 258	На: Алгоритм компьютерной модели искусственной эволюции Добавлено: 20 авг 06 1:58 На мой взгляд, с высокой вероятностью будет следующее: эволюция остановится на мелких программах. Насколько мне известно, все, кто пытался проделать подобный трюк -приходили к этому результату. Печален тот факт, что результат работы исследователей был бесполезен - не было ни теоритического, ни практического применения (если исключить PR). Мне трудно (потому что очень долго) обосновать свою позицию, но, если коротко, то случайные системы, в силу законов вероятности, стремятся к точке устойчивого равновения. Ваша система изобретет устойчивое семейство коротких программ, которые соответствуют Вашему способу получения программ, и эволюция встанет колом. Пока, с подобных подходом, дальше никто не продвинулся, насколько мне известно... Есть пара задач, увлекательных и сложных (и практически полезных), тоже связанных с эволюцией. Если интересно, могу дать ссылки - можно будет попытаться сделать перекрестное обсуждение. Я просто не могу писать обоснования по несколько страниц... [Ответ][Цитата]
Koks Сообщений: 3	На: Алгоритм компьютерной модели искусственной эволюции Добавлено: 20 авг 06 23:49 Думаю что эволюция этой программы не остановится пока не будет выключен компьютер. Естественно практического применения такому эксперименту трудно найти, а вот теоретическое запросто, ведь если будет доказано эволюционирование программы, это будет достойно Нобелевской премии. Дело в том что по моему предположению с момента образования жизни, до появления каких-то значимых изменений прошло очень много времени. Возможно миллион лет. И не было ничего замысловатого в этих элементах жизни, они могли лишь делиться. И тогда действительно существовал очень скудный набор простейших алгоритмов. Если не верить в то что Бог сотворил все живое на земле, то все мы родственники той самой первой клетки. Сколько прошло делений с того момента трудно сказать. Возможно чтобы смоделировать такое количество делений самому современному компьютеру потребуется миллион лет, может больше. А может уже через пол года будут первые результаты. Узнать это можно только запустив алгоритм. Если это действительно такой ресурсоёмкий процесс, не удивительно что никто не добился в этом значительных результатов. Но с каждым годом скорости процессоров и ёмкость оперативной памяти растет, и очень быстро. Думаю что рано или поздно по этой теории будет достигнут положительный результат в следствии эксперимента. По поводу пары задач, интересно, дайте пожалуйста ссылки. С удовольствием ознакомлюсь. [Ответ][Цитата]
mserg Сообщений: 258	На: Алгоритм компьютерной модели искусственной эволюции Добавлено: 22 авг 06 1:15 Чтобы устроить эволюцию, нужно: 1. Указать множество объектов эволюции и их характеристики 2. Указать правила эволюции, т.е. получение перечня и состояния объектов эволюции в момент времени (t+1) через состояние в момент времени t. 3. Указать начальное расположение объектов 4. Запустить моделирование, т.е. ход времени. Примером может служить моделирование молекул газа в замкнутом объеме: объектами являются молекулы газа, они характеризуются положением и скоростью. Правилами эволюции будут перемещение молекул газа с течением времени. Известен факт, что каким бы ни было начальное положение молекул и их скорость, моделирование приведет к тому, что молекулы примерно одинаково будут распределены по объему, а скорости молекул по определенному закону. Это есть точка устойчивости. Иногда могут наблюдаться некоторые небольшие флуктуации. После завершения процесса перехода из начального состояние в устойчивое, процесс эволюции заканчивается. Интересно, что это правило соблюдается для замкнутых систем: переходный процесс заканчивается устойчивым состоянием, т.е. тупиком равновесия (разумеется, тупик равновесия, может быть и динамическим; например, могут существовать циклические процессы – вроде жизни животных). Доказательств этому предостаточно: от естественных экологических систем до программ имитации искусственной жизни. Можно целую вечность моделировать – но будет одно и то же, так как система все равно скатится к своему устойчивому состоянию. Таковы законы природы – законы поведения большого числа случайных объектов. Чтобы что-то изменилось – требуется изменять условия эволюции. В этом случае есть вероятность, что имеющееся состояние объектов будет неустойчивым и произойдет прорыв на новый уровень. В новых условиях система должна прийти в новое устойчивое состояние. Но! Объекты, имеющиеся в предыдущем устойчивом состояния могут выжить и в новых, и, более того – новые устойчивые объекты будут созданы из предыдущих. И так далее, для продолжения эволюции опять нужно поменять условия, чтобы вывести систему из тупика равновесия, опять она придет к равновесию... Новые объекты иерархически будут созданы из устойчивых элементов предыдущих ступеней развития. Об этом есть целая теория (автор Хазен А.М.). Возникновение сложных объектов и даже жизни при таком подходе – высоковероятностный процесс, что меня в ней и привлекает. Он в своей работе непротиворечиво описывает весь процесс эволюции жизни на земле, пользуясь такой модель. Вот поэтому я утверждаю, что та модель, которая была Вами описана, попадет в тупик равновесия, где будут жить мелкие программы. Даже обладание вычислительными супер- ресурсами не в состоянии сдвинуть эволюцию с места. ********************************** Здесь пример, как заставить эволюцию работать для решения таких задач, которые нам интересны: http://np-soft.ru/npproject/research/ga/evo2.htm Эволюция должна создать программу, которая эффективно решает произвольные дискретные задачи. Известно, что дискретные задачи гипотетически можно решить перебором. Трудность заключается в том, что это практически невозможно даже для небольших задач. Сократить затраты на решение дискретных задач можно, применяя в той или иной форме, задачи полиномиальной сложности снижения числа вариантов. По моей задумке, эволюция должна находить эти полиномиальные алгоритмы. Система должна прийти к равновесному состоянию, найдя эффективные алгоритмы для множества тестовых задач. По мере эксплуатации, предлагая системе все новые и новые задачи, ее можно вывести из равновесия и она перейдет на новый уровень работы (наверное :-) . Конечно, эта система довольно ограничена, но это сделано намеренно – если фокус удастся реализовать, то можно будет существенно увеличить возможности для эволюции и для практического применения. [Ответ][Цитата]
гость 192.117.235.*	На: Алгоритм компьютерной модели искусственной эволюции Добавлено: 18 сен 06 17:35 Эволюцию любой системы можно представить как алгоритм поиска оптимума какой-нибудь функции, определенной на некоем множестве. Эта функция изменяется извне, а алгоритм с каждым изменением ищет новый оптимум. Очевидно, если множетсво, на котором определена функция велико, алгоритм не будет успевать перебрать достаточное количество членов множества для нахождения оптимума функции. Поэтому любая эволюция начинается с маленького подмножества, на котором ищется оптимум. Постепенно подмножество это увеличивается, то есть происходит усложнение эволюционирующей системы. Система не будет сама по себе усложняться, если оптимизируемая функция не будет меняться извне - эволюционирующая система всегда открыта, иначе она неизбежно остановится в локальном оптимуме. По мере того, как эволюционный алгоритм "изучит" возможные изменения оптимизируемой им функции, он уже не будет осуществлять случайный поиск, а при каждом изменении функции извне будет все быстрее "реагировать на это изменение", то есть все быстрее находить оптимум. Именно вследствие "изучения" изменений оптимизируемой функции и ускорения оптимизации эвоолюционный алгоритм сможет расширить пространство своего поиска - то есть увеличить сложность. Такой процесс происходил и в эволюции жизни на земле, такой процесс происходит и в эволюции компьютерных программ в последние 50 лет. Геном любого живого существа - это цепочка 4-ех аминокислот. Геном длиной в 1000 аминокислот может иметь 4 в степени 1000 состояний. Очевидно, что искать геном, дающий оптимум функции "выживаемости" среди всех возможных геномов - абсурд. Именно поэтому чем длиннее геном у животного (растения), тем более сложны мутации и рекомбинации генов. Не один ген мутирует случайным образом - мутация меняет целый большой кластер генов. То же самое с рекомбинацией - при оплодотворении не бывает так, что один ген берется от отца, а другой от матери случайным образом. Огромные кластеры генов берутся целиком от отцовской или целиком от материнской ДНК. Как возник такой механизм и почему берутся именно определенные кластеры? Механизм возник втечение длительного "изучения" алгоритмом эволюции колебаний и изменений функции "выживаемости". Похожий процесс происходит в эволюции софтвера. 30 лет назад, когда компьютерные программы были коротки, они писались на асемблере. Потом стали писаться на более сложных языках, в которых "мутации" затрагивали сразу несколько команд ассемблера. Чем дальше, тем более крупными и сложными блоками (или модулями, объектами) пользуются программисты. И это понятно. Программ длинной в 100 байт существует на много порядков меньше, чем программ длинной в 100 КБ. Поэтому и пространство поиска программ 100 КБ должно быть уже. [Ответ][Цитата]
Стр.1 (1)