2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача о ранце. Генетический алгоритм.
Сообщение29.06.2009, 18:42 


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

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение29.06.2009, 20:38 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение29.06.2009, 21:56 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение30.06.2009, 08:21 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение30.06.2009, 08:54 
Заблокирован


19/06/09

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

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение30.06.2009, 11:49 
Аватара пользователя


27/02/09

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

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

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение30.06.2009, 18:46 
Заслуженный участник
Аватара пользователя


15/10/08
11536
А чем не устраивает метод ветвей и границ?

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение01.07.2009, 12:24 


10/12/08
10
Утундрий в сообщении #225818 писал(а):
А чем не устраивает метод ветвей и границ?

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

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение24.10.2009, 20:24 


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

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

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

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

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

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение31.03.2012, 18:38 


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

 Профиль  
                  
 
 Re: Задача о ранце. Генетический алгоритм.
Сообщение01.04.2012, 21:43 


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group