350 руб
Журнал «Нейрокомпьютеры: разработка, применение» №9 за 2011 г.
Статья в номере:
Эвристический алгоритм приближенного решения задачи об упаковке
Ключевые слова: труднорешаемые задачи NP-полные задачи ортогональные задачи об упаковке и раскрое материала эвристические алгоритмы мультиэвристики генетические алгоритмы и нейронные сети
Авторы:
В. В. Псиола - аспирант, кафедра «Математическая теория интеллектуальных систем», мехмат МГУ E-mail: v@psiola.ru
Аннотация:
Рассмотрен один из подходов к построению эвристических алгоритмов для нахождения приближенного решения NP-полных задач за полиномиальное время, как попытка моделирования естественных рассуждений человека при решении таких задач на практике. На примере задач ортогональной упаковки в контейнер и раскроя материалов в 2- и 3-мерных случаях дан алгоритм их приближенного решения, основанный на использовании эвристических функционалов качества (мультиэвристик). Приведены примеры возможных методов оптимизации коэффициентов этого алгоритма с помощью генетических алгоритмов и нейронных сетей, а также некоторые особенности его программной реализации и внедрения на производстве.
Страницы: 13-27
Список источников
  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.