Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задача об укладке рюкзака

Эта задача имеет следующую неформальную простую постановку. Имеется рюкзак объемом и различных предметов. Каждый предмет имеет известный объем W_i и стоимость P_i (). В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем С – емкость рюкзака. Форма предметов здесь не учитывается.

Формальная постановка задачи: для данного множества весов W_i, стоимостей P_i и объема надо найти двоичный вектор X= (x₁,…, x_n), где x_i=1, если предмет укладывается в рюкзак;x_i=0, если предмет не укладывается;

при этом должно выполняться: , и .

Так как решение задачи можно представить двоичным вектором X= (x₁,…, x_n), то очевидно при его поиске можно применить простой ГА со стандартными операторами скрещивания и мутации. Но при этом, что на каждом шаге надо следить за тем, чтобы новые решения, полученные в результате скрещивания или мутации, удовлетворяли требуемому ограничению V . В случае невыполнения ограничения «неправильное» потенциальное решение должно быть уничтожено, что ведет к сокращению популяции.

В качестве фитнесс-функции в простейшем случае можно взять , но в этом случае, как указано выше, есть проблемы с неправильными решениями.