Здравствуй, ночной. В /pr мне никто не отвечает, поэтому спрошу здесьмало ли есть толковый анон.Есть один генетический алгоритм - алгоритм укладывания рюкзака предметами максимальной ценности. Как лучше скрещивать детишек? Размер гипотетических рюкзаков случайный.
Вверх
Вверх1
Вверх2
Вверх3
>>130188143 (OP)НАверное никто тебе не ответил, потому что так и не понял че ты хочешь то?
>>130188143 (OP)Там комбинаторная сложность, быстрее невозможно
>>130188896Есть одна задача. Нам дан рюкзак определенной вместимости и куча рандомных предметов, у которых есть свой вес и ценность. Нужно заполнить рюкзак максимально ценными вещами, учитывая ограничение по весу. Сама задача несложная, но мне нужно сделать не просто алгоритм, а генетический алгоритм.
слишком сложно даже для ночного, тебе к-ху-ям, ОП
>>130189355Но ведь мне не нужен сам алгоритм, я его по сути уже сделалтам какой-то ебаный ужас, но хочется увеличить скорость, изменив скрещивание особей
>>130189550>увеличить скоростьСложность алгоритмов не происходил?
>>130188143 (OP)Ну хуй знает, берешь и скрещиваешь. Выбираешь случайный набор предметов из первого рюкзака, в него досыпаешь случайный набор из второго пока не превысишь общий объем.А вообще пробовать надо.
>>130189605Нет, я происходил сложность алгоритмов, и понятно, что увеличение там будет совсем незначительное, но по-моему создание всех детей со всевозможными генами можно как-то обойти. А может и нельзя, меня уже пиздец как плавитА если честно,
>>130188143 (OP)Анон, я понял, что ты хочешь, но как это сделать - хуй знает. Мы случайно не знакомы?Первая мысль - отсортить рюкзаки по весу, идти двумя указателями в разные стороны в двух рюкзаках, пытаясь заменить тяжёлые вещи на наборы лёгкие так, чтобы вес не вырос, а стоимость не уменьшилась.А вообще у меня в генетике и не такая дичь заходила, пробуй чо попало, всегда есть шанс, что заработает.
>>130188143 (OP)давай учись там, пидрила, тебе еще страну поднимать
>>130189605Шёл бы ты отсюда. Сложность генетического алгоритма он собрался оценивать... ну что за мудаки, а?
>>130189940По-сути, это и сейчас работает, хотя я просто создаю всех возможных потомков, но с генами обоих родителей, а такой подход совсем не нравится.Может и знакомы
>>130189940>чтобы вес не выросА это необязательно. Оператор скрещивания не должен следить за качеством детей, за него это делает фитнес-функция и оператор выбора.
Попробовал от каждого родителя брать гены в зависимости от их размера - если отец больше, а мать поменьше, то мы берем половину матери, а все остальное пространство заполняем генами отца(с конца). Если наоборот, то та же самая операция, только батя заменяет мать. Если же они одинаковые, то берем ровно по половине от каждого. Работает вроде получше, но опять же теряются данные
>>130191611> но опять же теряются данныеЧто значит теряются?
>>130191989Гены некоторых предков не передаются, ведь теперь создаются не всевозможные детишки, а лишь часть
Жадный алгоритм?
>>130192281Нет, ГЕНЕТИЧЕСКИЙ
>>130192194Ну так это норма. Ты видимо не до конца понимаешь сути генетического алгоритма. Он не должен все возможные варианты перебирать
>>130192525Может и неправильно, но примерно так. Мол, у нас есть полудохлые пердящие старики и нам надо с помощью скрещивания и мутаций сделать ебаных амбалов.Мол, каждое поколоние становится немного лучше предыдущего
>>130192793В целом да, но становится лучше оно не за счет скрещивания. Скрещивание слепо - оно лишь берет часть генов одного родителя, часть у другого и соединяет. Получился ли при этом даун или гений его не заботит.Потом еще мутации хуярятся. Они опять же случайны.Затем в дело вступает естественный отбор. Есть много разных его видов, в простейшем случае потомство дадут N самых приспособленных членов популяции. Есть более сложные варианты (например турнирный, в котором особи разибиваются на пары и у каждой особи шанс выиграть и пройти дальше пропорционален значению фитнес-функции).В целом алгоритм вероятностный. Он не гарантирует результата, не гарантирует что твоя популяция не застрянет в окрестности локального максимума и т.п. Популяция в результате неудачных мутаций может на какое-то время даже деградировать.
Ладно, спасибо всем, кто ответил. В итоге, сделал два скрещивания(от одной пары родителей по два дитя). Одно скрещивание зависит от количества вещей у каждого родителя, а второе от суммарной стоимости всех предметов у каждого родителя. Надеюсь, что мне не дадут сильной пизды за это. Всем добра