Я пишу генетический алгоритм для решения определенной трехмерной задачи упаковки объектов кубоидов.
Идея состоит в том, чтобы получить список предметов кубоидов с указанием их размеров и значений, а также размера контейнера / контейнера, и цель состоит в том, чтобы найти наиболее выгодную упаковку, в которой ценность контейнера будет самой высокой.
чем-то похоже на проблему 3D-рюкзака.
, так как поиск лучшего подмножества предметов и их положений внутри контейнера - трудная задача для NP, я пишу генетический алгоритм, который попытается ее решить.
Я спроектировал хромозому существ в моем генетическом алгоритме, чтобы он представлял собой последовательность из N генов (N = количество предметов), которые представляют каждый предмет и его состояние (взято или нет) и местоположение внутри корзины.
При настройке фитнес-функции равной общему значению предметов, взятых представленными генами, алгоритм будет улучшаться в течение нескольких поколений, но достигнет только половины моего известного максимального решения.
Я полагаю, что отчасти это объясняется тем, что алгоритм не сжимает элементы, которые он принимает очень хорошо.
Например, вот изображение типа упаковки, которую достигает мой алгоритм: https://i.ibb.co/TmBL88Q/Capture.png
, которые занимают только около 36% пространства внутри корзины.
Итог:
Есть ли способ побудить генетический алгоритм также упаковать предметы в более сжатой форме с помощью функции пригодности? сейчас он определен только для того, чтобы заботиться о значениях, но я считаю, что попытка упаковать предметы в более сжатой форме поможет ему поместить больше предметов.