Российские распределенные вычисления на платформе BOINC
Форум участников распределённых вычислений.

Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error

2 Страницы12>
Опции
К последнему сообщению К первому непрочитанному
Offline hoarfrost  
#1 Оставлено : 10 февраля 2011 г. 1:15:58(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,418
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1254 раз
Поблагодарили: 1698 раз в 1079 постах
Здравствуйте!

Написал "по Докинзу" небольшую консольную программку, моделирующую нарастающий отбор и оказалось, что наблюдать за её работой весьма и весьма интересно.
Что она делает:
1. При запуске запрашивает эталонную фразу, которую лучше составлять из "Словаря" - больших букв латинского алфавита и знаков пробела, точки, запятой и "@";

2. Затем формирует "популяцию" из 64 "особей", геномом каждой и которых является строка такой же длинны, что и введённая нами, только состоящая из произвольно выбранных символов "Словаря" (он есть в самой программке);

3. Затем, каждая "особь" оценивается - качеством особи считается сумма отклонений её букв от букв эталонной фразы. То есть если вы ввели фразу "AAA", то качество особи "AAB" - 1, "AAC" - 2, а особи "FGK" - 21 (если я не ошибся);

4. Из 64 особей оставляются верхние 16 (т.е. с наименьшим значением оценки качества), после чего на их основе создаётся новое поколение - из 16 особей составляется 8 пар, каждая из которых порождает 8 потомков. Причём, каждый ген из генома новой особи случайным образом берётся либо из соответствющей позиции генома первой особи, либо из соответствующей позиции генома второй особи. Также с вероятностью в 0.25 каждой новой особи в геном заносится мутация - когда в произвольное место генома записывается произвольная буква из "Словаря";

5. Новое поколение также подвергается отбору. И так далее.

В качестве примера покажу как работает эта програмка работает при задании эталонной фразы "MILKYWAY@HOME IS AN ATI GPU PROJECT", что будет продемонстрировано в последующих сообщениях в этой ветке.
Вложение(я):
Evolution.rar (15kb) загружен 71 раз(а).
UserPostedImage
thanks 2 пользователей поблагодарили hoarfrost за этот пост.
evatutin оставлено 11.10.2012(UTC), MikeVentris оставлено 11.10.2012(UTC)
Offline hoarfrost  
#2 Оставлено : 10 февраля 2011 г. 1:16:14(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,418
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1254 раз
Поблагодарили: 1698 раз в 1079 постах
Исходное поколение. По сути - мусор.



Второе поколение. В общем-то мало что изменилось



Десятое поколение. Популяция стала гораздо более ровной, намечаются некоторые тенденции.

UserPostedImage
Offline hoarfrost  
#3 Оставлено : 10 февраля 2011 г. 1:23:08(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,418
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1254 раз
Поблагодарили: 1698 раз в 1079 постах
Поколение № 50. Ещё ровнее. Качество приблизилось к тому, что в среднем каждый символ "промахивается" на одну-две позиции в "Словаре".



Поколение № 74. Общая структура фраз похожа на эталон, некоторые буквы уже совпадают.



Поколение № 100. То же самое, только ещё ближе.

UserPostedImage
Offline hoarfrost  
#4 Оставлено : 10 февраля 2011 г. 1:27:28(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,418
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1254 раз
Поблагодарили: 1698 раз в 1079 постах
Поколение № 150. Ничего не напоминает?



Поколение № 200. В среднем 1 ошибка на 9 символов!



Поколение № 400. Чем выше качество, тем сложнее получить мутацию, повышающее качество особи. Поэтому чтобы добраться до качества равного 1, потребовалось почти 200 поколений.



Поколение № 515. Цель достигнута!

UserPostedImage
Offline hoarfrost  
#5 Оставлено : 10 февраля 2011 г. 1:39:27(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,418
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1254 раз
Поблагодарили: 1698 раз в 1079 постах
На что хотелось бы обратить внимание в первую очередь:
1. В эталонной фразе - 35 букв. В "Словаре" - 32 символа. При помощи такого словаря можно составить 35^32 фраз, длинной в 35 символов. Для любого из обычных компьютеров с обычной архитектурой - это очень много. Чтобы перебрать все эти комбинации, моему компьютеру не хватило бы и ныншнего возраста Вселенной.

2. Однако, несмотря на п.1. особи с фразой, в точности совпадающей с эталонной были выведены мною за несколько минут, во время которых я, в основном смотрел на очередное поколение, копировал каждое 50-е, или 100-е поколение в Notepad и только потом нажимал Enter чтобы создалось следующее. Реальной работы CPU там не было, наверное, и на секунду (особенно если ещё и отключить вывод поколений на экран).

3. Миллиарды лет, которых не хватит и доли секунды, которых хватило. И всё это следствие того, что в рамках популяции действовал нарастающий отбор, применяемый к каждому новому поколению "особей".
UserPostedImage
thanks 2 пользователей поблагодарили hoarfrost за этот пост.
AlexA оставлено 10.02.2011(UTC), CTAPbIi оставлено 10.02.2011(UTC)
Offline TechnoID  
#6 Оставлено : 10 февраля 2011 г. 2:02:08(UTC)
TechnoID


Статус: Давно уж тут

Группы: Member, Crystal Dream Group
Зарегистрирован: 13.01.2011(UTC)
Сообщений: 491
Мужчина
Откуда: Хабаровский край

Сказал «Спасибо»: 44 раз
Поблагодарили: 127 раз в 76 постах
Аще пипеац! Ты крут smile
По-моему, самое эффектное и эффективное доказательство (и наглядное), которое я когда-либо видел.
UserPostedImage
Offline Salmonella  
#7 Оставлено : 10 февраля 2011 г. 6:28:27(UTC)
Salmonella


Статус: Давно уж тут

Группы: Member
Зарегистрирован: 30.03.2010(UTC)
Сообщений: 226
Откуда: Россия

Сказал(а) «Спасибо»: 2 раз
Поблагодарили: 80 раз в 47 постах
Это что-то типа генетического алгоритма, да?smile
Offline CTAPbIi  
#8 Оставлено : 10 февраля 2011 г. 6:49:51(UTC)
CTAPbIi


Статус: Старожил

Группы: Member, Russia Team Group
Зарегистрирован: 30.09.2009(UTC)
Сообщений: 2,313

Сказал(а) «Спасибо»: 69 раз
Поблагодарили: 121 раз в 94 постах
интересно smile

Offline Step  
#9 Оставлено : 10 февраля 2011 г. 7:39:43(UTC)
Step


Статус: Старожил

Медали: Донор: За финансовую помощь сайту

Группы: Member
Зарегистрирован: 03.08.2010(UTC)
Сообщений: 916
Мужчина
Российская Федерация
Откуда: г. Кирово-Чепецк

Сказал «Спасибо»: 288 раз
Поблагодарили: 236 раз в 165 постах
Надо ещё внести в алгоритм случайные мутации при определении генома рождающейся особи. Иногда это может замедлить или наоборот ускорить получение эталонной особи. Правда в данной задаче эфект вряд ли будет значительным.
UserPostedImage UserPostedImage
Наука — лучший способ удовлетворения личного любопытства за государственный счёт.
Offline hoarfrost  
#10 Оставлено : 10 февраля 2011 г. 7:48:08(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,418
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1254 раз
Поблагодарили: 1698 раз в 1079 постах
Автор: Salmonella Перейти к цитате
Это что-то типа генетического алгоритма, да?smile

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

Автор: Step Перейти к цитате
Надо ещё внести в алгоритм случайные мутации при определении генома рождающейся особи. Иногда это может замедлить или наоборот ускорить получение эталонной особи. Правда в данной задаче эфект вряд ли будет значительным.

Так это и делается с вероятностью в 1/4. Или имелось ввиду что-то другое?
UserPostedImage
Offline Step  
#11 Оставлено : 10 февраля 2011 г. 9:17:44(UTC)
Step


Статус: Старожил

Медали: Донор: За финансовую помощь сайту

Группы: Member
Зарегистрирован: 03.08.2010(UTC)
Сообщений: 916
Мужчина
Российская Федерация
Откуда: г. Кирово-Чепецк

Сказал «Спасибо»: 288 раз
Поблагодарили: 236 раз в 165 постах
Автор: hoarfrost Перейти к цитате
Так это и делается с вероятностью в 1/4. Или имелось ввиду что-то другое?

А не, сорри, увидел - пункт 4. Да, это и имел в виду. 199
UserPostedImage UserPostedImage
Наука — лучший способ удовлетворения личного любопытства за государственный счёт.
Offline slepojpju  
#12 Оставлено : 10 февраля 2011 г. 11:32:15(UTC)
slepojpju


Статус: Старожил

Медали: Донор: За финансовую помощь сайту

Группы: Moderator "St.Petersburg", Member
Зарегистрирован: 23.10.2010(UTC)
Сообщений: 766
Мужчина
Откуда: Ленинград. Город герой.

Сказал «Спасибо»: 48 раз
Поблагодарили: 80 раз в 53 постах
Открытие? Еврика? Нобелевка?
Кто людям помогает, тот тратит время зря.
ХА-ХА.
Хорошими делами, прославиться нельзя.
UserPostedImage
Offline hoarfrost  
#13 Оставлено : 10 февраля 2011 г. 12:22:05(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,418
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1254 раз
Поблагодарили: 1698 раз в 1079 постах
Автор: slepojpju Перейти к цитате
Открытие? Еврика? Нобелевка?

Нет, это просто демонстрация того, что довольно неплохо известно, но совсем по другому осознаётся, если это хорошо показать.
laugh1
UserPostedImage
Offline pazzl  
#14 Оставлено : 10 февраля 2011 г. 12:23:38(UTC)
pazzl


Статус: Старожил

Группы: Member, Crystal Dream Group
Зарегистрирован: 29.05.2010(UTC)
Сообщений: 4,198
Откуда: новая москва

Сказал(а) «Спасибо»: 783 раз
Поблагодарили: 453 раз в 340 постах
а как ее запустить?
= работаю укладчиком парашютов, на мою работу еще никто не жаловался =
Offline hoarfrost  
#15 Оставлено : 10 февраля 2011 г. 13:26:22(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,418
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1254 раз
Поблагодарили: 1698 раз в 1079 постах
Автор: pazzl Перейти к цитате
а как ее запустить?

В первом сообщении приложен проект (решение) для Visual Studio 2010, в котором програмку можно скомпилировать и запустить. Впрочем её можно скомпилиировать и тем же Visual Studio 2010 Express. Да и 2008 (только надо program.cs брать и всё).

Приаттачил к этому сообщению вариант, скомпилированный под Windows 7 x64. Но поскольку .NET, то быть может и под другими платформами Windows запустится.
Вложение(я):
EvolutionExecutable.rar (11kb) загружен 43 раз(а).
UserPostedImage
Offline pazzl  
#16 Оставлено : 10 февраля 2011 г. 14:07:26(UTC)
pazzl


Статус: Старожил

Группы: Member, Crystal Dream Group
Зарегистрирован: 29.05.2010(UTC)
Сообщений: 4,198
Откуда: новая москва

Сказал(а) «Спасибо»: 783 раз
Поблагодарили: 453 раз в 340 постах
спасибо))
= работаю укладчиком парашютов, на мою работу еще никто не жаловался =
Offline ЧАТланин Баг  
#17 Оставлено : 12 февраля 2011 г. 21:56:57(UTC)
ЧАТланин Баг


Статус: Старожил

Группы: Member, Russia Team Group
Зарегистрирован: 02.07.2008(UTC)
Сообщений: 1,403
Мужчина
Российская Федерация
Откуда: Мос. область

Сказал «Спасибо»: 189 раз
Поблагодарили: 155 раз в 122 постах
Не запускается...
Ку! UserPostedImage
Таблица видюх -- http://b23.ru/c8xx
Offline A_Burnashev  
#18 Оставлено : 13 февраля 2011 г. 0:31:02(UTC)
A_Burnashev


Статус: Старожил

Медали: Донор: За финансовую помощь сайту

Группы: Member, Russia Team Group
Зарегистрирован: 20.05.2008(UTC)
Сообщений: 622
Мужчина
Откуда: Харьков

Сказал «Спасибо»: 42 раз
Поблагодарили: 32 раз в 32 постах
Когда-то очень давно у меня был ZX Spectrum 48K. Кто не знает 48К - это объем его памяти 48 килобайт.
И написал я к нему программку, которая моделировала эволюцию организмов в неком "супе".
Придумал и закодировал 461 реакцию с участием около сотни веществ (большинство реакций имели реальные аналоги, например реакции цикла Кребса), генетический код из 37 символов (10 цифр + 26 букв + стрелка как специальный код начала/остановки) и начал моделировать.
В "супе" жили 25 организмов, каждый имел ДНК из 240 символов, которые делились на 60 четверок. Четверка кодировала некий фермент, его активность в конкретной реакции определялась по несложной формуле. В среднем только 0,01% из 36^4=1679616 четверок обладали активностью в конкретной реакции.
Каждому организму при рождении давалось некоторое количество энергии, осуществление им соответствующих реакций увеличивало или уменьшало это количество и немного меняло состав "супа".
5 самых неудачных в энергетическом отношении организмов отбраковывались после каждого цикла, их место занимали измененные (мутировавшие) версии пяти самых удачных. Остальные 15 просто выживали и переходили на следующий этап.
Состав "супа" со временем менялся, что тоже вносило свою лепту.
Для начала я запустил в "суп" из глюкозы и добавок искусственно созданных "бактерий", превращающих глюкозу в молочную кислоту (прямой такой реакции не было, что важно, но были две реакции: глюкоза -> глицеральдегид с затратой небольшого количества энергии и глицеральдегид -> молочная кислота с получением большого количества энергии). Через всего 10 поколений в супе появились мутанты-паразиты, которые могли делать только вторую реакцию, т.е. они жили за счет организмов, делающих обе. Их число поддерживалось на уровне 10-15 из 25.
Потом глюкоза кончилось и началось самое веселое. Организмы постоянно мутировали, пока какой-то не научился (неожиданно для меня) синтезировать ацетон (что почему-то было выгодно). Его потомки сразу вытеснили остальных.
На этом этапе я программку забросил, так как работала она весьма медленно (поколение около 10 минут), что неудивительно, учитывая ее реализацию на интерпретируемом Бейсике Спектрума.

Сейчас вот думаю - а может вернуться к этой моей игрушке.
UserPostedImage

Подробная статистика:
Offline arenda13  
#19 Оставлено : 13 февраля 2011 г. 0:42:52(UTC)
arenda13


Статус: Старожил

Медали: Переводчику: За помощь в создании сайта

Группы: Member, Russia Team Group, Moderators
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 771
Мужчина
Откуда: Москва

Сказал «Спасибо»: 69 раз
Поблагодарили: 50 раз в 43 постах
Хочу такую программку. Можно даже ради этого повторить биохимию, и внести еще какие-нибудь реакции и вещества.
UserPostedImage
Offline Dragon2010  
#20 Оставлено : 13 февраля 2011 г. 1:28:13(UTC)
Dragon2010


Статус: Интересующийся

Медали: Донор: За финансовую помощь сайту

Группы: Member, Russia Team Group
Зарегистрирован: 24.10.2010(UTC)
Сообщений: 68
Откуда: Балашиха

Сказал(а) «Спасибо»: 5 раз
Поблагодарили: 7 раз в 4 постах
В тему
Проект связанный с моделированием процессов эволюции на примере цифровых примитивов. http://devolab.msu.edu/
Прогу Avida-ED можно скачать. Перед запуском рекомендуется приковать системник к батареи дабы на многомиллионной итерации не пострадать от агрессивного потомка элементарных функцийsmile

И по этому же проекту статья из Компьютерры http://www.computerra.ru/vision/553033/

P.S. Жаль перестали бумажную Компьютерру печатать.
si vis pacem, para bellum
Пользователи, просматривающие эту тему
Guest
2 Страницы12>
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

Boinc.ru theme. Boinc.ru
Форум YAF 2.1.1 | YAF © 2003-2018, Yet Another Forum.NET
Страница сгенерирована за 0.957 секунды.