|
Вобще говоря, генетические алгоритмы, как и любые другие алгоритмы глобального поиска, имеет смысл использовать только для трудноформализуемых многоэкстремальных задач, для которых нет четкого аналитического решения. Если множество исходных вещей конечно и заданно, используя стандартный итерационный алгоритм получим глобальный оптимум за минимальное время (имеем как раз тот случай, когда задача имеет четкий алгоритм решения), применять генетические алгоритмы тут вобщем смысла нет. Если множество вещей велико, а получение глобального экстремума не требуется (просто нужно какое-нибудь приличное квазиоптимальное решение) попробовать ГА тут конечно можно, но честно говоря сомневаюсь что он может работать быстрее/алгоритмически эффективнее чем стандартный итерант. Если все-таки очень хочеться попробовать, думаю надо как-то так:
1. Делаем генератор особей, который случайным образом пихает вещи в рюкзак до тех пор, пока тот не переполнится, последнию вещь отбрасываем.
2. Создаем начальную популяцию особей (наполненных рюкзаков) при помощи генератора особей (1).
3. Кроссинговер отбираемых особей имеет смысл определить как обмен вещами между рюкзаками, при этом нужно прослеживать не переполнился ли рюкзак-потомок и если переполнился, либо выбрасываем из него одну вещи, либо пробуем скрещивать опять, либо выкидываем из популяция.
4. Мутацию можно определить например как замену одной или нескольких вещей в рюкзаке, но тут имеет смысл подумать над фильтром обновляемых вещей (какие пропускать на замену, какие из имеющихся обновлять). Можно сделать подвид мутации - добавление вещи в рюкзак. Естественно тоже не забываем про обработку переполнений.
|
29.06.2009, 18:42 
максимальной цены предметов при весе не более 
.
