Что такое генетический алгоритм?

[rosnovsky]

Рахим, дико интересно, я ничерта не понял (что никак не твоя вина), но ты ужасно умный (не спорь!), и я тобой горжусь :))

[barvas]

Умный человек может легко объяснить сложные вещи, если он их действительно хорошо понимает, простыми словами. Вспомните Фейнмана.
Я посмотрел первое видео и остановился, потомучто ничего не понял. Затем открыл википедию, посмотрел пару графиков и разобрался.
Автору — постарайся объяснять для начала, для чего это надо и где можно это применять, тогда будит интересней.

[Dmitry_G]

Мой Мозг довольно урчит :)

[noita_kronk]

Только начал смотреть, но уже порадовало, что-то кто-то, наконец, додумался сделать ролик-лекцию «от первого лица». За этим жанром будущее. ;-)

[Frodo]

Честно говоря надоели уже! Каждый второкурсник, которому рассказали про ГА стремится сразу же написать на Хабр! Поищите в поиске — там штук 20 таких постов найдете за последний год!

[Frodo]

извините, не сдержался

[Homakov]

Кстати бывает так впопыхах напишешь какую нибудь фигню… А потом жалко стирать и с закрытымы глазами жмешь «написать». Сейчас например )

[gopline]

> 20 штук постов
Когда человек рассказывает все сам, записав это на видео, информация от него воспринимается куда лучше статей, которые нужно читать.

[SmartBye]

Ну почему же. Довольно понятно, только не очень понятен практический смысл.

[gopline]

Лично я все понял, хотя от генетических алгоритмов до этого знал только название.

[gopline]

Я понял объяснения автора. Относительно полноты и достоверности ничего сказать не могу, тут вы возхможно правы, судя по количеству претензий к автору. «ничего не понятно!» — это другое, касающееся формы изложения. Это 20 статей мелким шрифтом. Я тут вроде бы видел пару-тройку на эту же тему, но их читать даже курсор не поднимался. Так что спасибо автору по крайней мере за форму изложения своих мыслей (там тоже есть недостатки, однако в сравнении с обычным текстом, видеоряд рулит невозбранно).

[Dipp]

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

freetonik — один из них :)

[freetonik]

Мне сложновато рассказывать об этом по-русски, но я стараюсь.

[netAn]

простая сортировка и выбор top50% — превращает весь алгоритм в банальное решение методом восхождения с хорошим рандомайзом на входе.
Замените сортировку на выживание с вероятностью, пропорциональной фитнесс-функции, и получите ГА.

[vimmer]

супер, посмотрел не все, но очень интересно.

[borius]

Статья абсолютно бесполезна.

1) Тем которые, когда либо писали ген. прожки это детский лепет

2) Тем кто не занимался нифига не понятно.

Имхо надо ввести определения, что такое хромосома что такое популяция и тд,
дальше ввести понятия отбор и мутация и тд, а также как их можно делать.
И показать простенький примерчик, без большого счета.

[Gwindor]

Как по мне достаточно для того что бы знать что это такое и для чего оно (я не про вирусы, а про искусственный интеллект), а когда появиться задача для которой алгоритм подойдет уже и углубиться.

[Masterkey]

ниче непонятно, зато есть видеооооо )))

ЗЫ занимался ГА, данную тематику лучше осваивать самому, после того как наткнешься на НП-полную задачу. потом будешь изучать имтационный отжиг, ну вобщем пойдешь по наклонной )))

[borius]

Да вроде понятно…

проходил же через это ГА…

[abulkhairov]

Я вот никогда не занимался ГА и вообще не занимаюсь программированием.
Но все, что автор сказал — понял. Он ведь сам сказал «те, кто хоть немного ходили на биологию в школе, поймут» =)
Может быть в гугле найдутся десятки статей, но узнаю я (да и многие) о таких вещах именно тут на Хабре.
Автор, ждем примеров.

[borius]

Десятки статей найдутся в хабре, в гугле тысячи=)

По поводу того, что вы все поняли (а именно поняли как этим пользоваться) я сомневаюсь.

А если вы этого не поняли, то статья для вас бесполезна=) Уж извините за суровую реальность.

[Longedok]

А вы хотите, чтобы за одну 14-ти минутную лекцию стало всё понятно? Так не бывает. Зато это очень хорошая база для дальнейшего изучения темы. Главное, что автор рассказал о ГА интересно — тема отвращения не вызвала, сложностью не отпугнула.

[borius]

Еклмн, тема намного более интересная (и та база которую автор показал) намного проще.

Вот и все что я хотел сказать…

[Longedok]

Ну, попробуйте изложить лучше — мы сравним :)

[borius]

1) Есть статьи уже достаточно хорошего качества

2) У меня карма -2

3) У меня есть куда более интересные темы и готовые статьи (про мой сайт) которые пылятся ввиду пункта 2

[Longedok]

А, ну так даже лучше. Давайте ссылки на более хорошие статьи.

[borius]

algolist.manual.ru/ai/ga/ga1.php

вот очень красивая и понятная статья, мне нравится.

[Danov]

Вот статья, написанная чуть больше года назад
aabogdanov.ru/post/NanoGApost.aspx
Есть краткое описание ГА и «нано» пример на шарпе

[EugeniyPetrov]

Ну вот, карма уже положительная. Ждем статей.

[borius]

Спасибо всем участвующим, скоро будет!

[Longedok]

Никогда не занимался реализацией генетических алгоритмов, но тем не менее всё более чем понятно. К тому же очень интересно. Вводить определения и т.п. — это всё очень скучно, врядли бы я (и думаю много кто ещё) досмотрел бы до конца Вашу версию лекции. А эту досмотрел и с удовольствием посмотрел бы ещё.

[Sartor]

Честно говоря, если бы я не знал что такое ГА, я бы из этого видео и не узнал. Ваша «фитнес-функция» называется целевая функция. Так принято в русской терминалогии. Но всё равно, спасибо.

[Gwindor]

Исправьте последнюю ссылку.

[doubled]

В целом понравилось, напомнило Слепого часовщика.
^{В последней ссылке «:» мутировала в «t».}

[EugeniyPetrov]

Рассказываете красиво, понятно. Но если бы ещё реальный практический пример с реализацией (хотя бы теоретической) вообще бы цены Вам не было )

[borius]

Могу скинуть свой практикум=)

Там была задачка про удаление минимального набора ребер из графа, чтобы не было ни одного ориентированного цикла =)

реализация на schema

[EugeniyPetrov]

Если так же красиво и понятно — давайте)

[mechmind]

Автоматический тележкострой.

[borius]

Явно не на столько красиво=)

[EugeniyPetrov]

Интересно, он к утру проедет?

[oxilor]

Оставил на ночь. Второй обрыв так и не может проехать. Да и не сильно по конструкции изменился.

[Antigluk]

Немного непонятно. Тележка уже вроде как проехала некоторую дистанцию и не перевернулась, а оно останавливает и продолжает подбирать параметры.

[EugeniyPetrov]

Я так понимаю, цель — проехать всю дистанцию. У меня пока дальше этого обрыва практически не продвигался:

[Antigluk]

Проехать и дистанцию и не коснуться красными кругами дороги. Если я правильно понимаю.
Но иногда он прерывает попытку, даже не коснувшись кругами дороги.

[Longedok]

Blue balls are wheels, red balls are vulnerabilities. The structure restarts when either:

A. A vulnerability hits the ground or a wheel
B. The structure is stretched beyond a certain tolerence

Из комментов. Перевод не привожу, ибо не очень уверен в его точности :)

[EugeniyPetrov]

Ну что то вроде:
Синие шары — это колеса, красные — это некий уязвимый груз. Цель не достигнута если:
1. Груз касается земли или колес
2. Тележка деформируется больше заданного допуска.

[Longedok]

Ну вот вам ещё тогда. Я не знаю, какой из вариантов официальный и официальный ли хоть один из них, но в комментах написано так:
It dies after 10 seconds so that evolving would be faster. As the vehicle gets better over time, it can go further in that 10s time. Given enough time it will reach a point where you cannot possibly travel farther in 10 second with the physical simulation of the program.

The statistics in the top right corner give statistics about the average and best time of the sets of 20 individuals, you can clearly see that the trend is upwards.

[mechmind]

В свое время я разобрал эту флешку и увеличивал таймаут до 20, 30 секунд, но тележка уезжала не намного дальше — часто в генетической памяти остаются конструкции, идеально проходящие первые холмики и обрыв. Ну и дальше дорога больше в горку, мощности двигателя начинает не хватать )

[Antigluk]

о! у меня только что преодолела этот обрыв!

[abulkhairov]

5 минут втыкал как тележка улучшалась. Ничего подобного вживую не видел. Вы открыли мне Америку! =)

[EugeniyPetrov]

Я до сих пор втыкаю)

[Antigluk]

я тоже)

[impwx]

у меня уже почти час оптимизируется — Обрыв Смерти уже не страшен. оставлю на ночь, посмотрю что с утра получится :)

[EugeniyPetrov]

Смотрите чтобы не мутировал за ночь и не сбежал )

[Ctacus]

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

[Antigluk]

у меня где-то полтора часа мутировал — так и не прошел её. сейчас запустил в отдельном окне еще одно — буквально в 15м поколении прошло.

[Antigluk]

«Мой рандом лучше чем ваш!» (с)

[Antigluk]

у меня где-то полтора часа мутировал — так и не прошел её. сейчас запустил в отдельном окне еще одно — буквально в 15м поколении прошло.

[RiderSx]

Тупиковая ветвь эволюции, убейте их…

[Antigluk]

Не думаю, что вы увидите что-то сверхъестественное =) там ограничение 10 секунд.

[impwx]

Да, увы, черный график стал практически ровным — взбирается на горку после Обрыва Смерти и на этом всё заканчивается.

Разве что «мутанты» стали более живучими — раньше сразу погибали, а теперь хотя бы несколько метров проезжают.

[impwx]

[impwx]

Пардон за даблпост — картинка отправилась раньше чем надо.

Тележки стали серьезно быстрее (этот параметр тоже меняется, но его не так заметно сразу). На картинке на левом краю Обрыв Смерти. Максимум доезжало до впадины на правом краю картинки. Так что эти четырехколесные существа, пожалуй, не такие ограниченные, как мы думаем :)

[DRUN]

у меня за двое суток эволюции это велосипед проезжает каньон смерти и даже переезжает следующую горку… вот скрин :) img130.imageshack.us/img130/5332/evol.png

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

[Whasango]

если поуправлять стрелочками, можно сильно вмешаться в процесс эволюции тележек)

[k_s]

ru.wikipedia.org/wiki/Генетический_алгоритм

=)

[medvedi]

одна большая проблема.
нужно самому понимать и объяснять главный пункт — зачем? какая мотивация каждого действия? в идеале каждый момент нужно объяснять с этой точки зрения. особенно когда материал в первую очередь для тех кто с ним в принципе не знаком.

«теперь нам нужно сделать скрещивание»
«теперь нам нужно выбрать несколько индивидуумов»
«нужно выбрать правильный алгоритм селекции»
зачем и почему?

[Tolsi]

???
profit

[Igor_Sib]

Пасиба тебе, freetonik. С удовольствием послушал, всё понятно. Ждём продолжения!

Будет очень здорово, если информация из канадского института в Оттаве будет доступна ребятам из российской провинции. ;)

[mrmager]

Такой кайф! На старшем курсе университета я уже совсем забыл, что это — вникать в математические тонкости. Тут все довольно просто, никаких изысков и трудностей, но мне реально стало интересно.
Ничуть не жалею потраченного времени

[sayn]

на будущее — чуть больше света, а то видно не очень хорошо.

[Frosty]

Вопрос: За сколько поколений должен получиться ответ в примере с ноликами и единицами? Скачал с сайта пример, уже почти пол миллиона поколений отжило, а результаты колеблются в пределах 0.7-0.86. Или я что-то не так делаю?

[mrmager]

я думаю, ответа на этот вопрос дать никто не может ибо в описании алгоритма шла речь о рандоме.

[archonoff]

Вашему рандому просто не повезло=)
У меня единица выскочила с первого же запуска уже в 75 поколении.

[Frosty]

Сделал 3 контрольных запуска по 200, 200 и 500 тысяч поколений, так и не получил ответа.

[archonoff]

Я тоже несколько раз перезапускал. У меня выше 200 (не тысяч, просто двухсот) поколения не поднимались. В основном в пределах 70-130.
Исходник этот брали: dl.dropbox.com/u/72746/css/comp%204107/A1/100750928_as1_q1.zip?

[Frosty]

Этот самый, сейчас сделал еще 3 миллиона итераций… что-то тут не так :/

[ilder]

Спасибо. В дополнение www.youtube.com/watch?v=6O9YBnaUYGw

[demoded]

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

[oparinov]

Мы в своем подкасте обсуждали и нейронные сети, и генетические алгоритмы, и где их можно применить. Послушайте, там немного и кратко, empatikafm.rpod.ru/142820.html (4-я тема)

[demoded]

на словах я все понимаю, я даже понимаю исходники как работают. меня вгоняет в ступор, когда все это понятное мне, аццкими формулами записано… каюсь по вышке было слааабенькое 3

[Likvidator]

Круто, хочу еще такого видео!

[Klajnor]

Всё круто и интересно,!!! НО!!! не сказано ни слова о том, как понять, что работу алгоритма можно закончить

[amlet]

Просто прекрасно, очень интересно и вдохновляюще. Рахим молодец кстати: в самом конце видеокаста прямо заинтриговал: программы которые эволюционируют и решают поставленную задачу — сверхинтересная тема. Можно конечно немного поумничать и абстрагироваться и сказать, что программа — это тот же набор переходов и всякой другой шняги по типу значений для иксов, а решение — это значение функции, но количество и «значений», а главное как их описать и описать сам факт решения — вот в этом и сложность. А ещё нужно сделать какой-то механизм, который бы разделял программу написанную с применением некоторого синтаксиса на эти элементарные составляющие и вносил коррективы и в самом конце из наилучшего набора предоставил программу, понятную человеку… Короче очень интересно и интригующе :)

[noita_kronk]

К сожалению, всё-таки путанно рассказано, надо было получше подготовиться.

[Keroll]

Мне понравилось применение некого числа — «К… чёрт запутался»- ага!)

[AndreyYu]

Посмотрев ролики стало понятно, что
1. Ничего толком не понятно. Слишком много лишних слов, мне кажется.
2. В любом процессе очень важен секс
3. Ручка классная!

[Veminz]

Извините, но я не понял… что не поняли все те, кто жалуется в комментариях? По-моему все, хоть и не подробно, но довольно доходчиво рассказано и показано.

Возможно многих просто раздражает личность самого Фритоника и его плодовитость в плане создаваемого контента. Это я конечно же могу понять, на самом деле это просто самая банальная зависть. Зависть, что некий молодой человек является более успешным и популярным чем я, что он создает массу популярных статей по алгоритмам, записывает подкасты, делает переводы и т.п., а моих 2 поста даже на главную не попали. Конечно возникает естественная реакция защитить свое эго и оправдаться тем, что на самом деле это не я неудачник, это просто у Фритоника контент говно, поэтому он его с такой легкостью создает в массе…

Нет, товарищи, проблема вашей бездарности не в других, она в вас.

[Veminz]

Рахим, поправь, пожалуйста, вторую ссылку в своем посте, сейчас она выглядит так:

http://htttp//css.freetonik.com

[ultx]

По мне все понятно, хоть я и не разбираюсь. Единственное, что мне пришло в голову — эти популяции собрать в одну «гиперпопуляцию», и сделать много «гиперпопуляций» а потом сравнивать более успешные, так точность может возрасти. Хотя для такой задачи может быть это и не критично.
зы: Фритоник продолжай. Есть предложения по поводу видео, может быть следующую серию сделать более привлекательной, и нарисовать все схемы не рукой, а на компьютере, что бы было более «инфографично». Или скооперироваться с тем кто лучше это сделает.

[slam007]

вспомнил видео-ролик про сломанные часы и эволюцию.

[AirLight]

вы все конечно же молодцы, и все-таки, для чего используются на практике ГА?

[Igor_Sib]

Насколько я знаю в системах автоматического раскроя используются ГА. То есть если надо расположить заготовки деталей на листе металла, или буквы для плоттера на самоклеящейся плёнке, с минимальным расходом материала. Такие задачи решаются с помощью ГА.

[Throwable]

Математик — это отдельный склад ума. Объяснить простые вещи настолько сложно, насколько это возможно, при абсолютной бесполезности результата.

[roller]

фитнес -> целевая функция