Генетический алгоритм. Ограничения

@PinkPink · Регистрация: 10.05.2012

Студворк — интернет-сервис помощи студентам

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

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

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

@S_el · 03.04.2015, 11:31

Сообщение от PinkPink

Теоретически, каждая хромосома решает поставленную задачу, только какая-то лучше, какая-то - хуже.

Нет,хромосома это компонент особи.Как координата у точки.

Сообщение от PinkPink

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

Лучше расскажите подробнее какую задачу хотите решить ГА?

@IrineK · 03.04.2015, 11:38

Ненужное - выбрасываю.
Разнообразие обеспечиваю за счет мутаций.

@PinkPink · 03.04.2015, 15:40 **[ТС]**

Решаю транспортную проблему. т.е. хромосома у меня представляет собой решение в какой последовательности нужно посетить города. Например, 45182367. Здесь каждый ген - индекс города

Добавлено через 3 минуты

Сообщение от IrineK

Ненужное - выбрасываю.
Разнообразие обеспечиваю за счет мутаций.

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

@S_el · 03.04.2015, 16:38

Сообщение от PinkPink

Решаю транспортную проблему. т.е. хромосома у меня представляет собой решение в какой последовательности нужно посетить города. Например, 45182367.

Нужны подробности.

Сообщение от PinkPink

И даже если решать проблему мутациями, сколько их нужно сделать?

Есть специальные критерии останова работы генетического алгоритма.И на использовании только оператора мутации далеко не уехать.

@PinkPink · 03.04.2015, 20:33 **[ТС]**

Сообщение от S_el

Нужны подробности.

Не очень понимаю какие ещё подробности здесь нужны? Что конкретно не понятно?

Сообщение от S_el

Есть специальные критерии останова работы генетического алгоритма.И на использовании только оператора мутации далеко не уехать.

Это всё и так понятно, поэтому я спросил автора, что конкретно он предлагает.

@S_el · 03.04.2015, 21:09

Сообщение от PinkPink

Не очень понимаю какие ещё подробности здесь нужны? Что конкретно не понятно?

Какую задачу вы решаете.
Что пока известно:
Нужно определить оптимальный способ прокладывания маршрута.
Что я хочу выяснить:
1)Вы решаете классическую задачу(транспортная,коммивояжера,о ранце и.т.д) или нет.
2)Что выступает в роли фитнес-функции
3)Что такое индексы городов?
4)В каком виде представлена первоначальная информация?

Добавлено через 3 минуты

Сообщение от PinkPink

Это всё и так понятно, поэтому я спросил автора, что конкретно он предлагает.

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

@wingblack · 04.04.2015, 14:50

Кроме мутации и кросинговера рекомедуется вводить ситуацию катаклизма если скатываемся в локальный минимум (находим оптимальное решение, которое на деле не является самым оптимальным).
Суть - если наилучшее решение не меняется несколько шагов, то особи популяции подвергаются усиленной мутации, а в функцию оценки добавляется штраф за приблежение к такому решению. Рекомендуется ограничить штраф верхней границей чтобы не отсекать решения близкие к найденному. Естественно, нужно запомнить такое решение как оптимальное пока не найдем лучшее.

@PinkPink · 06.04.2015, 12:24 **[ТС]**

Сообщение от wingblack

Кроме мутации и кросинговера рекомедуется вводить ситуацию катаклизма если скатываемся в локальный минимум (находим оптимальное решение, которое на деле не является самым оптимальным).
Суть - если наилучшее решение не меняется несколько шагов, то особи популяции подвергаются усиленной мутации, а в функцию оценки добавляется штраф за приблежение к такому решению. Рекомендуется ограничить штраф верхней границей чтобы не отсекать решения близкие к найденному. Естественно, нужно запомнить такое решение как оптимальное пока не найдем лучшее.

А где-то можно почитать поподробнее об этом? Какие-то статьи, исследования?

@wingblack · 06.04.2015, 18:34

Вот например одна из последних статей на Хабрахабре
Генетический алгоритм — наглядная реализация

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292

	Генетический алгоритм. Ограничения 03.04.2015, 11:28. Показов 848. Ответов 9 Метки нет (Все метки) Добрый день. Генетический алгоритм предполагает выведение хромосом с лучшей фитнес-функций, насколько это возможно. Теоретически, каждая хромосома решает поставленную задачу, только какая-то лучше, какая-то - хуже. Вопрос в том, что делать с хромосомами, которые вообще не решают поставленную задачу? С таким в генетических алгоритмах я не сталкивался. Просто выбрасывать эти хромосомы из популяции? Но не придём ли мы сильном сокращению популяции? Генерировать новые в замен выброшеных? А возможно ли? Сколько останется подходящих хромосом для этого? А действительно ли нужно их выбрасывать? Многообразие хромосом (даже не подходящих) теоретически может привести к возникновению мутаций и лучших видов хромосом. А рационально ли вообще получать потомство от таких забракованных хромосом? Если есть какие-то соображения по этому поводу или вы можете подсказать литературу, отзовитесь пожалуйста. 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	03.04.2015, 11:38
	Ненужное - выбрасываю. Разнообразие обеспечиваю за счет мутаций. 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	04.04.2015, 14:50
	Кроме мутации и кросинговера рекомедуется вводить ситуацию катаклизма если скатываемся в локальный минимум (находим оптимальное решение, которое на деле не является самым оптимальным). Суть - если наилучшее решение не меняется несколько шагов, то особи популяции подвергаются усиленной мутации, а в функцию оценки добавляется штраф за приблежение к такому решению. Рекомендуется ограничить штраф верхней границей чтобы не отсекать решения близкие к найденному. Естественно, нужно запомнить такое решение как оптимальное пока не найдем лучшее. 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	06.04.2015, 18:34
	Вот например одна из последних статей на Хабрахабре Генетический алгоритм — наглядная реализация 0