Задача о ранце. Генетический алгоритм.

[User008]

Как генетическим алгоритмом решать задачу о ранце?

[EtCetera]

Веселенький вопросик. Мне казалось (впрочем, может быть, я ошибаюсь), что генетическими алгоритмами в лучше случае можно решать задачи оптимизации (тогда они предстают в виде некоторой убыстряющей надстройки над методом Монте-Карло), а комбинаторные задачи (типа задач о ранце) как-то выбиваются из этой области... Может быть у Вас задача о ранце просто какая-то специфическая?

[Alhimik]

Что такое генетический алгоритм? Мне просто интересно. И вообще, о чем речь. Я не пониамю, но, дейстивтельно, пытаюсь.

[EtCetera]

User008
Я немного подумал, и понял, что все-таки можно (только осторожно!). Для небольшого количества предметов в рюкзаке генетические алгоритмы в данном случае, мягко говоря, неуместны... Вот при большом могут даже сказаться некоторые их преимущества... Хотя точно я, увы, не знаю...
Alhimik
Wikipedia еще никто не отменял... Но если вкратце - генетические алгоритмы используют принципы эволюционной теории, в частности, механизмы мутации, кроссинговера, отбора и пр. С математической точки зрения - это (при всей их красивости) лишь усовершенствование методов типа Монте-Карло.

[jetyb]

Попробуйте через рекуррентные соотношения между функциями $S_m$ максимальной цены предметов при весе не более $m$.

[Мастак]

ИМХО вполне нормально генетический алгоритм сработает.
Особь - битовая строка, где позиция соответствует предмету, и 0 - нет предмета в рюкзаке, 1 - есть в рюкзаке. Стоимости и веса - в функции приспособленности. Вот функцию приспособленности по-хитрее бы.
Начать издалека - с популяции из особей, где по одному предмету в рюкзаке.

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

[Утундрий]

А чем не устраивает метод ветвей и границ?

[User008]

Утундрий в сообщении #225818 писал(а):

А чем не устраивает метод ветвей и границ?

Надо разобраться, как решать генетическим алгоритмом. В том числе многокритериальные задачи о ранце.

[Skrejet]

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

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

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

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

4. Мутацию можно определить например как замену одной или нескольких вещей в рюкзаке, но тут имеет смысл подумать над фильтром обновляемых вещей (какие пропускать на замену, какие из имеющихся обновлять). Можно сделать подвид мутации - добавление вещи в рюкзак. Естественно тоже не забываем про обработку переполнений.

[Unsleep]

Кто-нибудь может решить задачу о ранце с помощью генетического алгоритма с оплатой с моей стороны?

[Ales]

А разве нельзя сделать генетический алгоритм на основе:
http://informatics.mccme.ru/moodle/mod/ ... apterid=60

Или просто переписать алгоритм и назвать его "генетическим".

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