Обсуждение:Генетический алгоритм

Untitled

Обращаю внимание редакторов на такие предложения в статье, которые меня "покоробили" (и я предполагаю, что это не только моё субъективное, а и общее восприятие - в противном случае объясните мне, пожалуйста, что я понял не так):

(1) "Положенное начало позволило компьютерной симуляции эволюционных процессов и методам, описанным в книгах Фразера и Барнелла(1970)[4] и Кросби (1973)[5], с 1960-х годов стать более распространенным видом деятельности среди биологов." Подскажите, как книги 70х годов издания повлияли на 1960тые года?

(2) "С ростом исследовательского интереса существенно выросла и вычислительная мощь настольных компьютеров, это позволило использовать новую вычислительную технику на практике." С ростом исследовательского интереса к чему? К генетическому алгоритму? Именно благодаря ему выросла мощь настольных компьютеров?

Предлагаю оформить как "Попутно, с ростом исследовательского интереса..." и т.д. по тексту. Тогда так выглядит как параллельный рост обоих аспектов.

(3) "При выборе «функции приспособленности» (или fitness function в англоязычной литературе) важно следить, чтобы её «рельеф» был «гладким»." Выглядит как "машинный" перевод. Возможно, есть человек, который разбирается в материале - довести до ума сие предложение.

Спасибо за внимание

77.52.101.194 11:05, 30 апреля 2016 (UTC) аноним

Комментарий

Генети́ческий алгори́тм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым проблемам

Браво! А аналитически разрешимые проблемы им нельзя решить :)))) — Эта реплика добавлена с IP 212.68.165.133 (о) 13:04, 7 мая 2007 (UTC)

Угу, кто-то ляпнул, а кто-то увидел, похихикал и не поправил ;) (сейчас этот недостаток устранен)

Вообще статью надо серьезно править, там огрехов выше крыши, чего только стоят фразы "Задача кодируется...", "Размножение в генетических алгоритмах обычно половое..." и вообще стиль изложения скорее повседневно-будничный, чем энциклопедический. Надо будет выбрать время и навести порядок. Если кто присоединится с этой нелегкому процессу, биг мерси :) Qai — Эта реплика добавлена участником Qai~ruwiki (о • в) 08:41, 9 октября 2007 (UTC)

И еще мне не нравится пример. Он не слишком хорошо иллюстрирует, что есть генетические алгоритмы. --Gliv 09:37, 16 марта 2009 (UTC)

Мне кажется, или предложенная еще Лемом в "Сумме технологии" методика "выращивания информации" как раз описывает генетические алгоритмы? 92.100.177.169 10:56, 5 июля 2009 (UTC)

Амебы

Почему ссылка http://amebas.ru/ не относятся к теме? Мне так не кажется. ЗЫ: сорри, ежели туплю. пёс-призраг 20:42, 19 сентября 2009 (UTC)

Потому что ссылок и так слишком много. Если мы помещаем в статью ссылку на одну программу для ГА, то должны поместить и на все остальные. Правильным выходом было бы поставить одну ссылку на какой-нить сторонний список программ для ГА. --A.I. 20:59, 19 сентября 2009 (UTC)

Схема работы алгоритма

Схема работы не соответствует тексту. Вначале должна идти селекция, потом - скрещивание и/или мутация. — Эта реплика добавлена участником Lesoslav (о • в) 12:52, 16 декабря 2009 (UTC)

Это текст не соттветствует схеме. В начале идёт как раз получение новых решений, а уже потом - отбор (селекция) решений в следующее поколение. --Sigwald 14:10, 12 февраля 2010 (UTC)

Поддерживаю первого оратора. Селекция нужна для того, чтобы отобрать хромосомы в родительский пул. Только потом их нужно сгруппировать в пары. И только затем идут скрещивание и мутация. Хотя если хорошо закодировать то, что описано на схеме, то и это заработает. -- [User:amyasnikov] — Эта реплика добавлена с IP 95.128.244.10 (о) 03:59, 25 марта 2010 (UTC)

Возможно в разной литературе под селекцией понимаются разные вещи? В моём понимании хромосомы в родительский пул (и для мутации) отбираются случайным образом (при этом вероятность выбора для более приспособленной особи выше), а селекция по определённому принципу отбирает особи в лучшее поколение (например, если будем просто брать лучшие особи, алгоритм может быстро скатиться к локальному оптимуму). --Sigwald 08:41, 25 марта 2010 (UTC) P.S. У французов в статье аналогичная схема, но там она еще более кривая, хотя статья и избранная... — Эта реплика добавлена участником Sigwald (о • в) 08:48, 25 марта 2010 (UTC)

Все там верно на схеме .. S.J. 10:21, 25 марта 2010 (UTC)

Если вы про французов, то не совсем всё там верно. Если посмотреть историю, то видно что схема менялась. Evaluation (вычисление критерия/функции приспособленности) добавили в цикл, но криво. Получается что как только получили потомков/мутантов сразу каким-то эмпирическим путём можем выяснить, достигли ли критерия завершения или нет, если ответ "нет", то только после этого вычисляется для полученных особей функция приспособленности. Должно быть тогда уж так для логики:

Начальное поколение -> вычисление функции приспособленности для особей из него -> селекция1 (выбор особей для кроссовера/мутации) -> кроссовер/мутация -> вычисление функции приспособленности для полученных особей -> селекция2 (отбор особей в следующее поколение) -> условие остановки процесса выполненно? (да -> остановка, нет -> переход на селекцию).

Вариаций генетического алгоритма множество. В одном новое поколение формируется только из потомков, в другом проводится "турнир" между родителями и потомками и лучшие попадают в новое поколение. Какой алгоритм считать классическим, или "простым" - вопрос. Я встречал разные определения. Поэтому что в итоге рисовать на схеме тоже вопрос... --Sigwald 12:12, 25 марта 2010 (UTC)

Это не так. Для мутаций особи не отбираются. Для размножения (кроссовер) особи отобраны на прошлом этапе, именно поэтому размножение начинается с самого начала. Новое поколение размножается - мутирует - смотрим на сколько оно удовлетворяет целевой функции - отбираем на основе этого новое поколение. И ни каких других вариаций ! Вариации могут быть только в деталях, а не в общей схеме. S.J. 14:38, 25 марта 2010 (UTC)

Откуда же по вашему особи для мутаций берутся? С небес? Не в каждом ГА мутациям подвергаются результаты кроссовера. Для кроссовера вы в любом случае должны выбрать пары особей. На входе в итерацию мы имеем просто ранжированное поколение, без какого бы ни было деления на пары для кроссовера. --Sigwald 16:25, 25 марта 2010 (UTC)

Классически размножение и мутации для всех особей. Ничего отбирать для этого не нужно, если же вы знаете какой спец. алгоритм - то опишите, в частности меня интересует тогда критерий на основе чего решается - что вот эти нужно размножаться, а вот этим мутировать. S.J. 17:19, 25 марта 2010 (UTC)

Разных критериев достаточно много, но в любом из них для размножения (и возможной мутации) отбираются особи с наибольший приспособленностью, и именно их потомство составляет следующее поколение. Если же размножать и мутировать всех, то мы получаем не генетический алгоритм, а случайный поиск Mikhael 666 mikhailovich 16:59, 26 марта 2010 (UTC)

Вот тут и ошибка. Если мы говорим о отборе наиболее приспособленных - то она производится ПОСЛЕ размножения и мутаций, а на следующей итерации мы уже размножаем следующие ОТОБРАННОЕ поколение. ДВА раза никогда не отбираются. Просто процесс идет в цикле - в КОНЦЕ цикла происходит отбор, а вначале размножение. S.J. 21:30, 26 марта 2010 (UTC)

Кажется мы таки докопались до основного разночтения: селекция может производиться как среди родителей, так и среди потомков. Причем в обоих случаях алгоритм будет работать (возможно с разной эффективностью (могут быть какие-то тонкости) ). И естественно проводить ее два раза на одной итерации неэффективно. Mikhael 666 mikhailovich 11:13, 27 марта 2010 (UTC)

Вот. Все правильно. Правда я сомневаюсь о разной эффективности, т.к. разница всего в одно поколение (потомки это родители через одну итерацию). Но дать такое пояснение в статье думаю можно, чтобы не было больше неясностей. Поправьте, если что я подкорректирую. S.J. 22:15, 27 марта 2010 (UTC)

Но если у нас первая популяция из «нулевых» элементов или одно элемента (как обычно и бывает), то зачем секцию ставить раньше размножения. А вообще процесс циклический, приходим к банальному вопросу курицы и яйца ;). --A.I. 17:51, 25 марта 2010 (UTC)

Тем более алгоритм схеме соответствует, в начальной популяции у нас однотипные элементы (серые), так что бессмысленно выбирать из них лучший. --A.I. 17:52, 25 марта 2010 (UTC)

Почему же из нулевых? Начальная популяция должна состоять как раз таки из случайных, разных элементов Mikhael 666 mikhailovich 20:41, 25 марта 2010 (UTC)

Это равносильно, начальной популяции из «нулевых» элементов и мутации на первом шаге :), тогда тогда на диаграмме не будет отражено как формировалось начальная случайная популяция. --A.I. 08:35, 26 марта 2010 (UTC)

Нулевых конечно странно. но см. мой ответ выше, размножать нужно всех, и никакого критерия отбора для размножающихся нету ! S.J. 22:42, 25 марта 2010 (UTC)

Есть специалисты ?

вообще-то я удивился, что столько людей отметились в обсуждении, я то думал специалистов в области ИИ тут мало. Так может доведем статью до хорошей ? S.J. 22:43, 25 марта 2010 (UTC)

Не могу назвать себя крупным специалистом, однако мой диплом был посвящен именно решению прикладной задачи с использованием ГА, и в данный момент я продолжаю над ней работать =) Можно и до хорошей, почему бы нет? --Sigwald 09:03, 26 марта 2010 (UTC)

Давайте тогда подумаем, чего не хватает в статье ? S.J. 12:29, 26 марта 2010 (UTC)

Чего не хватает для статуса хорошей ?

Ставьте # и дополняйте. И желательно затем участвуйте в пополнении статьи.

1. Нету истории появления, и соответственно ссылок на АИ S.J. 12:30, 26 марта 2010 (UTC)
2. Приведена куча ссылок на источники, но сноска в статье всего одна. Да и сами ссылки надо проверить. --Sigwald 14:14, 26 марта 2010 (UTC)
3. Пример кода в статье иллюстрирует скорее случайный поиск чем генетический алгоритм... Надо бы его поправить... Mikhael 666 mikhailovich 11:19, 27 марта 2010 (UTC)

   Конечно, пример обрезанный, не раскрыты функции sort/copy. Но почему случайный поиск ? Я так понимаю целевая функция предполагается в sort, хотя это не очевидно - думаю поправив (показав) это пример станет нормальным. S.J. 22:22, 27 марта 2010 (UTC)

   sort|copy - это как раз мелочи. В статье есть такая фраза:

   Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания»

   здесь его нет, а значит удачная мутация не сможет распростроняться по популяции. И каждой особи нужно будет в одиночк пройти всю лестницу эволюции. — Эта реплика добавлена участником Mikhael 666 mikhailovich (о • в) 13:06, 28 марта 2010 (UTC)

‎

Модель естественного отбора или эволюции?

Никто и никогда еще не мог смоделировать эволюцию (не путать с машинным обучением, естественным отбором). Ссылки на эволюцию по Дарвину не нужны. Такое сопоставление создает ложное впечатление наличия алгоритмических аналогов того процесса, который мы можем считать лишь гипотезой, а не теорией (я имею ввиду гипотезу Эволюции). Базовые термины, которыми оперируют алгоритмы, относящиеся к эволюционному программированию, взяты из естественного отбора (популяция, особь, гены, сходимость, выживаемость, скрещивание, мутация и т.д.). Первые генетические алгоритмы создавались с целью имитировать изменение популяции по поколениям. Изменения внутри популяции не есть эволюция, которая предполагает преобразование видов, появлению новых видов. В дальнейшем генетические алгоритмы адаптировались для решения всевозможных алгоритмических задач, для которых их можно было приспособить, но их природным аналогом остался естественный отбор, а не эволюция. Эволюция предполагает глобальные изменения (преобразование экосистем и биосферы в целом), что, конечно, не имитируется никакими эволюционными (в том числе генетическими) алгоритмами. Таким образом, правильным считаю проводить аналогию с естественным отбором. 109.184.219.12 16:41, 18 августа 2013 (UTC)к.т.н., специалист по ГА

Эту статью писал человек либо далекий от ГА, либо почему-то очень невзлюбивший ГА

1) Описание алгоритма сомнительное

2) примеров использования нет

3) код неудачный

4) ссылок на оригинальные и важные работы - нет

5) критика просто убила! все пункты надуманные. Повторное вычисление целевой функции? не вычисляйте - храните в памяти. Не понравилось члену IEEE, я тоже член и мне нравится — Эта реплика добавлена с IP 212.41.20.10 (о) 07:49, 17 апреля 2014 (UTC)

По пятому пункту: Всё, кроме цитаты, — перевод из английской Википедии, и при этом вполне допустимая критика. Не понравилось не члену, а лауреату премии IEEE. Членом IEEE может стать любой за деньги. По остальному: смело добавляйте ссылки на важные работы, примеры использования, правьте неудачный на Ваш взгляд код... Это Википедия. Sergey539 05:45, 24 апреля 2014 (UTC)