350 rub
Journal Neurocomputers №9 for 2011 г.
Article in number:
Heuristic algorithm for the approximate solution of the packing problem
Keywords: intractable problems orthogonal problem of packaging material and its cutting NP-complete problems heuristic algorithms multi-heuristic genetic algorithms and neural networks
Authors:
V. V. Psyola
Abstract:
Proposed for consideration is a method for the construction of heuristic algorithms for finding an approximate solution to NP-complete problems in a polynomial timeframe, which attempts to model natural human reasoning when solving such problems in practice. In the example problem of the orthogonal packing of a container and cutting of materials in 2- and 3-dimensional cases, an algorithm for their approximate solutions, based on the use of heuristic functional quality (multi-heuristic) is considered. In addition, the work gives examples of possible methods of optimizing the coefficients in this algorithm using genetic algorithms and neural networks, as well as some features of its software implementation and deployment production.
Pages: 13-27
References
  1. ВалееваА. Ф. Конструктивные методы для решения задач ортогональной упаковки и раскроя. ГОУ ВПО Уфимский государственный авиационный технический университет. Диссертационная работа на соискание ученой степени доктора технических наук. 2006.
  2. Гэри М., ДжонсонД. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.
  3. Ахо А., Хопкрофт Дж., УльманДж. Построение и анализ вычислительных алгоритмов. М.: Мир. 1979.
  4. Канторович Л. В, ЗалгаллерВ. А. Рациональный раскрой промышленных материалов. Новосибирск: Наука. 1971.
  5. Сигал И. Х., ИвановаА. П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. Изд. 2-е, испр. М.: Физматлит. 2003.
  6. Кочетов Ю., Младенович Н., ХансенП. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Январь - июнь 2003. Т. 10. Сер. 2. № 1. С. 11-43.
  7. Кочетов Ю. А., Усманова А. Р. Вероятностный поиск с запретами для задач упаковки в контейнеры // Труды Байкальской международной конференции. Иркутск. 2001. Т. 6. С. 22-26.
  8. Darrell, W., A genetic algorithm tutorial. Statistics and computing. 1994. № 4. С. 65-85.
  9. Chazelle, B., The bottom-left bin packing heuristic: An efficient implementation // IEEE Trans, on Comput. 1983. № 2. P. 697-707.
  10. Baker, B. S., Goffman, Jr. E. G., Riverst, R. L., Orthogonal packing in two dimensions. SIAM J. Comput. 1980. № 9. P. 846-855.
  11. Daniel, D. K., Sleator,D. B., A 2.5 times optimal algorithm for packing in two dimensions. Computer Science Department, Stanford University, Stanford, CA 94305, U. S A. Received 6 January 1979; revised version received 13 November 1979.
  12. Pisinger, D., Heuristics for the container loading problem. European Journal of Operational Research. 2002. № 141. P. 382-392.
  13. Норенков И. П., Косачевский О. Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Информационные технологии. 1999. № 2. С. 2-8.
  14. Норенков И. П. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. 1999. № 2, 1. С. 2-7.
  15. Khonen,T., Self-organized formation of topologically correct feature maps // Biological Cybernetics. 1982. V. 43. P. 59-69.
  16. Khonen,T., Self-organized map // Proc. IEEE. 1990. V. 78. № 9.P. 1464-1480.
  17. УоссерменФ. Нейрокомпьютернаятехника. Теорияипрактика. М.: Мир. 1992.
  18. Block,H. D., The Perseptron: a model for brain function // Review of Modern Physics. 1962. V. 34. P. 123-135.
  19. Псиола В. В. О приближенном решении трехмерной задачи об упаковке на основе эвристик // Интеллектуальные системы. 2007. Т. 11. Вып. 1-4.
  20. Псиола В. В. Оценки качества работы алгоритма Packer3d (теория и практика). М.: МГУ им. М.В. Ломоносова. 2009. Деп. в ВИНИТИ 01.04.09, № 182-В2009.
  21. Псиола В. В. Об одной особенности двумерной задачи о рюкзаке // Материалы X Междунар. семинара «Дискретная математика и ее приложения». Москва, МГУ, 1-6 февраля 2010 г. / под ред. О. М. Касим-Заде. М.: Изд-во мехмата МГУ. 2010.
  22. Псиола В. В. Особенности программной реализации алгоритма Packer3d. М.: МГУ им. М. В. Ломоносова. 2009. Деп. в ВИНИТИ 01.04.09, № 181-В2009.
  23. Псиола В. В. Обзор основных нейросетевых моделей // Интеллектуальные системы. 1999. Т. 4. Вып. 3-4.
  24. Хаменя В. А., Артельных И. В., Псиола В. В., ХаменяИ. Д. Решение задачи классификации в рамках модели смеси гауссовских распределений // Сборник «Теоретические и прикладные проблемы информационных технологий». М. 2001.