автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и исследование бионических методов упаковки

На правах рукописи

ПОТАРУСОВ РОМАН ВАЛЕРЬЕВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ БИОНИЧЕСКИХ МЕТОДОВ УПАКОВКИ

Специальность 05.13.01 - Системный анализ, управление и обработка

информации (вычислительная техника и информатика)

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Научный руководитель: заслуженный деятель науки РФ, доктор технических наук, профессор В.М. Курейчик

Таганрог - 2008 г.

Работа выполнена на кафедре Систем автоматизированного проектирования Технологического института ФГОУ ВПО «Южный федеральный университет» в г. Таганроге Научный руководитель: заслуженный деятель науки РФ,

доктор технических наук, профессор В.М. Курейчик

доктор технических наук, профессор Ковалев С.М.

доктор технических наук, профессор Карелин В.П.

Официальные оппоненты:

Ведущая организация:

Федеральное государственное унитарное предприятие Таганрогский НИИ связи

Защита состоится "18" декабря 2008 г. в 10:20 на заседании диссертационного совета Д 212.208.22 по защите диссертаций при ФГОУ ВПО «Южный федеральный университет» по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан "27" октября 2008 г.

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

/

А4

Учёный секретарь диссертационного совета •

доктор технических наук, профессор

А. Н. Целых

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Области применения задачи упаковки одномерных элементов в блоки (далее, задача упаковки блоков) охватывают большое количество сфер деятельности человека. Упаковка блоков является распространенной производственной задачей. Она решается при производстве стали, стекла, бумаги, дизайне СБИС, составлении бюджета, форматировании таблиц, постраничном разбиении и т.д. Задача упаковки блоков является ^-сложной и NР-полной.

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

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

Цель и основные задачи диссертационной работы.

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

1. Разработана архитектура гибридного генетического поиска, основанная на стратегии «эволюция - локальный поиск»;

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

квазиоптимальные и оптимальные решения рассматриваемой задачи;

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

4. Построены проблемно-ориентированные модифицированные генетические операторы, позволяющие получать допустимые решения задачи упаковки блоков;

5. Создан программный комплекс для решения задачи упаковки блоков «ВРР Ьу йА».

Методы исследования

Методы исследования основываются на элементах теории множеств, алгоритмов, эволюционного моделирования, статистике.

Достоверность результатов исследования

Объем численных экспериментов, проведенных при решении различных контрольных (тестовых) задач и вариациях параметров параллельного гибридного генетического алгоритма, составил не менее 104 опытов. Программный комплекс «Одномерная упаковка элементов в блоки методами генетического поиска» («ВРРЬуСА») на котором осуществлялось автоматизированное проведение экспериментов, прошел официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство №2007613933 (роспатент) от 14.09.2007).

Научная новизна диссертационной работы заключается в следующем:

1 .Разработана архитектура гибридного генетического поиска, основанная на стратегии «эволюция - локальный поиск»;

2.Построен гибридный параллельный генетический алгоритм упаковки блоков, позволяющий получать квазиоптимальные и оптимальные решения рассматриваемой задачи;

3.Разработаны методы гибридного генетического поиска, основанные на моделях эволюции Ж. Ламарка и Г. де Фриза, позволяющие создавать различные по качеству решения рассматриваемой задачи, частично решая проблему преждевременной сходимости поиска к локально оптимальному решению;

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

5.Предложены проблемно-ориентированные модифицированные генетические операторы для параллельного гибридного генетического алгоритма упаковки блоков, позволяющие получать допустимые решения рассматриваемой задачи.

К числу наиболее важных научных результатов диссертации относятся:

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

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

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

Практическая ценность

Разработан программный комплекс, позволяющий находить квазиоптимальные и оптимальные решения задачи упаковки блоков. Одним из возможных применений комплекса является решение задачи форматирования таблиц, а также постраничное разбиение и дизайн СБИС. Программный комплекс разработан для операционной системы Windows, написан на языке С++. Компиляция выполнена в среде объектно-ориентированного программирования Microsoft Visual Studio. NET.

Реализация результатов работы.

Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при чтении лекций по курсам: «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторског о и технологического проектирования». Разработанный программный комплекс был успешно протестирован и принят к использованию на кафедре САПР ТТИ ЮФУ при проведении лабораторных и практических занятий по курсам «Методы оптимизации», «Эволюционное

моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

Апробация работы и публикации.

Основные теоретические и практические результаты работы представлены на международных научно-технических конференциях АГБ'Об, САО'Об (пос. Дивноморск, 2006 г.), международных научно-технических конференциях А18'07, САБ107 (пос. Дивноморск, 2007 г.), международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2007).

Результаты диссертации отражены в 7 печатных работах.

Структура и объём диссертационной работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 145 стр., включая 55 рис., 23 таб., список литературы из 133 наименований, 3 стр. приложений и актов об использовании.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационной работы, сформулированы цели, приведены сведения о полученных научных и практических результатах, реализации и внедрении результатов работы, апробации, дано краткое описание выполненной работы.

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

wJ = вес элемента у, с = вместимость каждого блока. Упакуем каждый элемент в один блок так, что общий вес элементов в каждом блоке не превышал с, а число использованных блоков было минимально. Математическая формулировка задачи:

п

минимизировать г = "У, У> (1.1)

(=1

п

при условии, что ^и^Ху <су) {1, ..., п}, (1.2)

м

л

IX =l,jsN,

(1.3)

(1.4)

(1.5)

у, = 0 или 1, I е N,

x,j = 0 или 1, / eN.j eN,

где

д:

У,=

Г 1, если блок / использован ' [ 0, в противном случае \,если элемент ] упакован в блок / О, в противном случае

Будем полагать, что wh с- положительные целые, м>, < с для j eN.

Произведен сравнительный анализ существующих методов и алгоритмов упаковки блоков. Обоснован выбор гибридных генетических алгоритмов для решения задачи упаковки блоков. Рассмотрены возможные методы кодирования решения и оценки значения его целевой функции.

Во второй главе описана архитектура гибридного генетического поиска, предложенная в данной работе (рис. 1). Методы и алгоритмы, разработанные на базе предложенной архитектуры, позволили достигнуть качественных квазиоптимальных и оптимальных решений для всех тестовых задач, доступных в Интернет.

Разработаны методы гибридного генетического поиска на основе моделей эволюции Г. де Фриза (рис. 3) и Ж. Ламарка (рис. 4). При моделировании эволюции по Г. де Фризу на следующую итерацию гибридного генетического алгоритма переходят альтернативные решения со значением ЦФ больше 0.5. Каждые N (устанавливается экспертом) итераций половина подпопуляции альтернативных решений замещается решениями, сгенерированными случайным образом. При моделировании эволюции по Ж. Ламарку на следующую итерацию алгоритма переходят только те решения, которые содержат блоки, заполненные целиком (на 100%).

В третьей главе построен гибридный параллельный генетический алгоритм упаковки блоков, структурная схема которого изображена на рис. 2.

Приведено обоснование выбора целевой функции, используемой генетическим алгоритмом для решения задачи упаковки одномерных элементов в блоки. В данной работе используется следующая целевая функция: максимизировать

I /с) + у (5\ /с) f .>=1 •___

]т'.....N

где Ы- общее количество блоков, используемых в решении, <2

- количество блоков, заполненных менее чем на 100%, б1, - сумма

весов элементов в блоке /, с - вместимость блока, Р - количество

блоков, заполненных на 100%, Sj - сумма весов элементов в блоке у,

к - константа, к = 2. Приведенная целевая функция позволяет

производить оценку не только альтернативного решения задачи

упаковки блоков в целом, но и получать необходимую информацию

о количестве блоков, заполненных целиком, т.е. о функциональной

части хромосомы.

Описано кодирование альтернативного решения задачи

упаковки блоков. Альтернативное решение кодируется одной

хромосомой, где каждому гену соответствует один блок,

содержащий упакованные в него элементы. Пример

альтернативного решения, закодированного хромосомой, изображен

на рис. 5. Элементная часть хромосомы записывается следующим

образом

ААВВВСОЕГ,

означая, что элементы с весами 68 и 32 упакованы в блок А, элементы с весами 1, 35, 25 - в блок В, элемент веса 42 - в блок С, элемент веса 70 - в блок Д элемент с весом 59 - в блок Е, элемент с весом 79 — в блок К

Рис 1. Архитектура гибридного поиска

с

I

Критерий останова

чостигнут?^" нет

/Выдать 7 лучшие / решения /

Конец

3

Рис. 2. Структурная схема гибридного параллельного генетического

алгоритма

Рис. 3. Гибридный генетический поиск, основанный на модели эволюции Ж. Ламарка

Рис. 4. Гибридный генетический поиск, основанный на модели эволюции Г. де Фриза 10

68

35

79

А В С D Е F

Рис. 5. Пример упаковки 9 элементов в блоки вместимости 100

Групповая часть хромосомы представляет только блоки и выглядит следующим образом:

ABCDEF.

Введено понятие функциональной части альтернативного решения, состоящей из тех блоков групповой части, которые заполнены на 100%. Функциональная часть альтернативного решения, изображенного на рис. 5, состоит из блока Л.

Проведено исследование и сделаны выводы относительно эффективности распараллеливания эволюционных вычислений в алгоритмах упаковки блоков. Разработанный комплекс алгоритмов затрачивает на получение оптимальных и квазиоптимальных решений, как минимум, в 1,5 раза меньше времени, чем лучшие существующие алгоритмы решения рассматриваемой задачи.

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

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

Четвертая глава посвящена реализации программного комплекса упаковки блоков и тестированию предложенного комплекса гибридных алгоритмов одномерной упаковки. Программный комплекс реализован на языке С++ в среде Microsoft Visual Studio. NET. Разработанный комплекс не требователен к ресурсам, может быть запущен на любом ПК с установленной ОС

11

! ________________________

Windows 2000 и выше. Пользователю предлагается удобная система с возможностью модификации параметров алгоритмов и просмотром результатов упаковки. Общее представление об интерфейсе программного комплекса «BPPbyGA» можно получить на рис. 6, где представлена главная форма приложения с диалоговым окном ввода параметров.

Сделаны выводы об оптимальном размере популяции решений для параллельного гибридного генетического алгоритма упаковки блоков. Наибольшая эффективность разработанного комплекса гибридных алгоритмов достигнута при размере популяции в диапазоне от 70 до 100 альтернативных решений.

tlC*1 thlmtOSOtnt Сфмйу-.»«'««

п*гЛ*Л for pa, 'Hieo: 'j 4.И i(08flii fitness". ti.3!S4iJl(

Cowitefioft: IW 01**: W

jkri/kSiMiuitliiiM

СИЗ ...ж. j

Рис. 6. Интерфейс программного комплекса «ВРРЬувА»

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

При отборе решений для применения генетических операторов наиболее эффективными оказались метод селекции на основе рулетки и турнирная селекция. Количество решений, участвовавших в турнире, варьировалось в диапазоне от 3 до 7. Оптимальным является турнир размера 7.

Алгоритмы протестированы на контрольных (тестовых) задачах упаковки одномерных элементов в блоки, доступных в Интернет. Проведены тесты для 1370 контрольных задач, на каждой из них параллельный алгоритм запускался 10 раз. Для 1365 контрольных задач получены оптимальные решения задачи, для 5 -квазиоптимальные с отклонением от оптимального решения в 1 блок (табл. 1). Количество проведенных экспериментов и их результаты доказывают эффективность и устойчивость разработанного комплекса гибридных алгоритмов.

Таблица 1.

Результаты экспериментов

Набор Кол-во Отклонение от

тестовых задач в оптимального

задач наборе решения, количество блоков

ср. макс.

U120 20 0.00 0

U250 20 0.00 0

U500 20 0.00 0

U1000 20 0.00 0

Т60 20 0.00 0

Т120 20 0.00 0

Т249 20 0.00 0

Т501 20 0.00 0

HI 720 0.59 1

Н2 480 0.36 1

НЗ 10 0.11 1

ALL 1370 0.096 1

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

В заключении изложены основные выводы и результаты диссертационной работы.

В приложении представлены копии актов о внедрении и актов об использовании в учебном процессе результатов представленной работы.

ЗАКЛЮЧЕНИЕ

1. Представлены области применения и дана постановка задачи упаковки одномерных элементов в блоки. Проведен анализ существующих подходов к решению задачи упаковки блоков. На основе проведенного анализа в качестве перспективного выбран гибридный генетический метод.

2.Разработана архитектура гибридного генетического поиска, основанная на стратегии «эволюция - локальный поиск»;

3. Построен и исследован гибридный параллельный генетический алгоритм упаковки блоков, позволяющий получать квазиоптимальные и оптимальные решения рассматриваемой задачи;

4. Разработаны методы гибридного генетического поиска, основанные на моделях эволюции Ж. Ламарка и Г. де Фриза, позволяющие создавать различные по качеству решения рассматриваемой задачи, тем самым частично решая проблему преждевременной сходимости поиска к локально оптимальному решению;

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

6. Построены проблемно-ориентированные модифицированные генетические операторы для гибридного параллельного генетического алгоритма упаковки, позволяющие получать допустимые решения рассматриваемой задачи.

7. Создан программный комплекс «BPPbyGA» для ЭВМ типа IBM PC на языке программирования С++ в среде программирования Microsoft Visual Studio. NET.

8. Проведены серии экспериментов, выполнена статистическая обработка экспериментальных данных. Результаты экспериментов показали, что применение гибридного параллельного группирующего генетического алгоритма упаковки блоков позволяет получать квазиоптимальные и оптимальные

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1.Потарусов Р.В., Курейчик В.М. Проблема одномерной упаковки элементов. - Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТРТУ, 2006. №8 (63),-с. 88-93.

2.Потарусов Р. В. Гибридный параллельный группирующий генетический алгоритм для решения задачи упаковки блоков. -Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТТИ ЮФУ, 2008, №4 (81)-с. 42-45.

Публикации в других изданиях

3.Потарусов Р.В., Курейчик В.М. Задача одномерной упаковки. Анализ и обзор эвристических алгоритмов. Перспективные информационные технологии и интеллектуальные системы, Таганрог, ТРТУ, 2006, № 4(28), с.37-47

4.Потарусов Р.В., Курейчик В.М. Задача одномерной упаковки и ее использование при решении задачи маршрутизации автотранспорта. Труды Международных научно-технических конференций «Интеллектуальные системы» (А18'06) и «Интеллектуальные САПР» (САО-2006). Научное издание в 3-х томах. - М.: Физматлит, 2006, Т.2. - с. 56-61.

5.Потарусов Р.В., Курейчик В.М. Модифицированные генетические операторы. Сборник трудов международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». - М: Изд-во Физматлит, 2007, с. 406-412.

6.Потарусов Р.В. Гибридный генетический поиск для задачи упаковки блоков. Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТТИ ЮФУ, 2007, № 2 (77), с. 30-35.

7.R. Potarusov, V. Kureychik, G. Goncalves, H. Allaoui. Solving the Bin Packing Problem with Algorithm of Genetic Search with Migration. Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'07) и «Интеллектуальные САПР» (CAD-2007). Научное издание в 3-х томах. - М.: Физматлит, 2007, Т.З. - с. 34-45.

Личный вклад автора в работах, опубликованных в соавторстве: [1, 3, 4] -обзор и анализ существующих алгоритмов решения рассматриваемой задачи, [5-7] - разработка архитектуры гибридного генетического поиска, модифицированных генетических операторов, программная реализация и проведение экспериментальных исследований.

Соискатель Потарусов Р.В..

Тип.ТТИ ЮФУ Заказ №Л2Я.тир. /:0экз.

ВВЕДЕНИЕ.

1. ОБЗОР И АНАЛИЗ АЛГОРИТМОВ И МЕТОДОВ ОПТИМИЗАЦИИ УПАКОВКИ ОДНОМЕРНЫХ ЭЛЕМЕНТОВ В БЛОКИ.

1.1. Математическая формулировка задачи упаковки блоков.

1.2. Приближенные алгоритмы.

1.3. Редукционная процедура С. Мартелло и П. Тота.

1.4. Точные алгоритмы.

1.5. Мета-эвристические методы решения задачи упаковки блоков.

1.6. Эвристики,' о'снованные на минимальной остаточной вместимости блока.

1.7. Процедура повышения качества решения А.Алвима и Ф. Гловера.

1.8. Алгоритм моделирования отжига.

1.9. Алгоритм поиска при переменном соседстве.

1.10. Выводы.

2. РАЗРАБОТКА АРХИТЕКТУРЫ ГИБРИДНОГО ГЕНЕТИЧЕСКОГО ПОИСКА.

2.1. Разработка архитектуры гибридного генетического поиска для задачи упаковки блоков.

2.2. Разработка методов гибридного генетического поиска, основанных на моделях эволюции.

2.3. Выводы.

3. РАЗРАБОТКА КОМПЛЕКСА ГИБРИДНЫХ АЛГОРИТМОВ.

3.1. Распараллеливание эволюционных вычислений в алгоритмах упаковки

3.2. Целевая функция.

3.3. Кодирование решений.

3.4. Создание начальной популяции.

3.5. Гибридный параллельный генетический алгоритм решения задачи упаковки блоков.

3.6. Общая процедура гибридного параллельного генетического алгоритма

3.7. Разработка и анализ модифицированных генетических операторов, ориентированных на решение задачи упаковки блоков.

3.8. Разработка алгоритмов локального поиска, ориентированных на решение задачи упаковки блоков.

3.9. Теоретические оценки временной и пространственной сложности разработанных алгоритмов.

3.10. Выводы.

4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО

КОМПЛЕКСА ГИБРИДНЫХ АЛГОРИТМОВ.

4.1. Требования к программным продуктам, реализующим генетические алгоритмы.

4.2. Основные характеристики программного комплекса «ВРРЬувА».

4.3. Структура программного комплекса «ВРРЬуСА».

4.4. Цель экспериментального исследования.

4.5. Планирование эксперимента.

4.6. Результаты экспериментальных исследований.

4.7. Область применения разработанных алгоритмов.

4.8. Выводы.

Задача упаковки одномерных элементов в блоки (далее, задача упаковки блоков) - ЫР-сложная комбинаторная оптимизационная задача [1]. В задаче упаковки блоков целью является скомбинировать элементы в блоки заданной вместимости так, чтобы минимизировать общее количество блоков [2-5].

Задача упаковки блоков является распространенной производственной задачей. Она решается при производстве стали, стекла, бумаги, дизайне СБИС, составлении бюджета и т.д [2]. Рассматриваемая задача упаковки одномерных элементов в блоки является ИР-полной.

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

Ввиду вышеизложенного, задача упаковки блоков является АКТУАЛЬНОЙ ПРОБЛЕМОЙ комбинаторной оптимизации, стоящей перед специалистами в различных областях производства.

Результатом непрекращающегося поиска наиболее эффективных методов упаковки стало использование бионических методов и алгоритмов, в том числе эволюционных и генетических алгоритмов (ГА). Впервые предложенные американским ученым-исследователем Дж. Холландом в 1975 году, ГА основаны на аналогии в принципах адаптации биологических и технических систем [б]. Они представляют собой мощный оптимизационный метод, моделирующий естественный процесс эволюции в качестве средства достижения оптимума, и основаны на селекции лучших альтернативных решений из полученного набора (популяции) решений. Сравнительно недавно он начал широко применяться для решения задач в самых различных областях, в том числе для решения задачи упаковки блоков [7-43].

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

Недостатки ГА, применяемых для решения задачи упаковки блоков [7-43], заключаются в низкой степени учета особенностей задачи, что приводит к излишним требованиям по объему памяти, времени работы ГА и к ухудшению качества получаемых решений.

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

ЦЕЛЫО диссертационной работы является разработка и исследование комплекса гибридных генетических алгоритмов упаковки одномерных элементов в блоки, способных получать квазиоптимальные и оптимальные решения рассматриваемой задачи.

Для достижения поставленной цели были решены следующие задачи:

1. Разработка архитектуры гибридного генетического поиска, основанной на стратегии «эволюция — локальный поиск»;

2. Построение и исследование гибридного параллельного генетического алгоритма упаковки блоков, позволяющего получать квазиоптимальные и оптимальные решения рассматриваемой задачи;

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

4. Построение проблемпо-ориентированных модифицированных генетических операторов, позволяющих получать допустимые решения задачи упаковки одномерных элементов в блоки;

5. Создание программного комплекса «ВРР Ьу ОА», позволяющего автоматизировать процесс решения задачи упаковки блоков.

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании теории принятия решений, элементов теории множеств, элементов теории алгоритмов, элементов теории статистических вычислений.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем:

1. Разработана архитектура гибридного генетического поиска, основанная на стратегии «эволюция - локальный поиск»;

2. Построен гибридиый параллельный генетический алгоритм упаковки, позволяющий получать квазиоптимальные и оптимальные решения рассматриваемой задачи;

3. Разработаны методы гибридного генетического поиска, основанные на моделях эволюции Ж. Ламарка и Г. де Фриза, позволяющие создавать различные по качеству решения рассматриваемой задачи, частично решая проблему преждевременной сходимости поиска к локально оптимальному решению;

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

5. Построены проблемно-ориентированные модифицированные генетические операторы для параллельного гибридного генетического алгоритма упаковки, позволяющие получать допустимые решения рассматриваемой задачи.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

• гибридный параллельный генетический алгоритм упаковки блоков;

• программный комплекс упаковки блоков.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе № 12354 «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска». Кроме того, материалы диссертации использованы в учебном процессе кафедры САПР ТТИ ЮФУ при чтении лекций и проведении лабораторных работ по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась па международных научно-технических конференциях AIS'06, CAD-2006 (нос. Дивноморское, 2006), 4-ой международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2007), международных научно-технических конференциях AIS'07, CAD-2007 (пос. Дивноморское, 2007).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 7 печатных работах.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложения. Работа содержит 145 страниц, включая 55 рисунков, 23 таблицы, список использованной литературы из 133 наименований, 3 страницы приложений и актов об использовании.

4.8. Выводы

1. Выделены объекты исследования: гибридный параллельный генетический алгоритм для задачи упаковки блоков, алгоритмы локального поиска;

2. Для выделенных объектов исследования выполнены следующие действия: поставлена цель исследования; построен план проведения экспериментов;

3. Описаны основные недостатки и определены требования к программным продуктам, реализующим ГА;

4. Разработан программный комплекс «BPPbyGA», позволяющий исследовать построенный комплекс гибридных алгоритмов упаковки. Программное обеспечение реализовано в среде Microsoft Visual Studio. NET версии 2005 в рамках объектно-ориентировапиого подхода, что

5. Описана структура программного комплекса «ВРРЬуОА», состав и принцип действия основных блоков программного комплекса;

6. Проведены серии экспериментов; выполнена статистическая обработка экспериментальных данных. Результаты исследования позволили уточнить теоретические оценки временной и пространственной сложности алгоритмов, по которым можно адекватно оценить разработанные алгоритмы. Эмпирические оценки сложности совпадают с теоретическими;

7. Проведено сравнение экспериментальных данных разработанных алгоритмов и их аналогов. Результаты экспериментов показали, что применение гибридного параллельного генетического алгоритма для решения задачи упаковки позволяет получать квазиоптимальные и оптимальные решения задачи для всех тестовых задач, доступных в литературе;

8. Отмечены особенности и определены области применения разработанных алгоритмов.

ЗАКЛЮЧЕНИЕ

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

2. Разработана архитектура гибридного генетического поиска, основанная на стратегии «эволюция — локальный поиск»;

3. Построен и исследован гибридный параллельный генетический алгоритм упаковки, позволяющий получать квазиоптимальные и оптимальные решения рассматриваемой задачи;

4. Разработаны методы гибридного генетического поиска, основанные на моделях эволюции Ж. Ламарка и Г. де Фриза, позволяющие создавать различные по качеству решения рассматриваемой задачи, тем самым частично решая проблему преждевременной сходимости поиска к локально оптимальному решению;

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

6. Построены проблемно-ориентированные модифицированные генетические операторы для гибридного параллельного генетического алгоритма упаковки, позволяющие получать допустимые решения рассматриваемой задачи.

7. Создан программный комплекс «BPPbyGA» для ЭВМ типа IBM PC на языке программирования С++ в среде программирования Microsoft Visual Studio. NET.

8. Проведены серии экспериментов, выполнена статистическая обработка экспериментальных данных. Результаты экспериментов показали, что применение гибридного параллельного генетического алгоритма для

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

1. Garey, М. R. and Johnson, D. S. Computers and 1.tractability: A Guide to the Theory of NP-Completeness, W.H. Freeman. 1979.

2. Bischoff E. E. and Wäscher. G. Cutting and packing. European Journal of Operational Research, 84, 1995, 503-505.

3. Martello, S. and Toth, P. An Upper Bound for the Zero-one Knapsack Problem and a Branch and Bound Algorithm, European Journal of Operational Research. 1, 1975, 169-175.

4. Martello, S. and Toth, P. Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990a, ISBN: 0-471-92420-2.

5. Martello, S. and Toth, P. Lower Bounds and Reduction Procedures for the Bin Packing Problem, Discrete Applied Mathematics. 28, 1990b, 59-70.

6. Holland, J. H. Adaptation in Natural and Artificial Systems, University- of Michigan Press, 1975.

7. Beasley, D., Bull, D. R. and Martin, R. R. An Overview of Genetic Algorithms: Part 1, Fundamentals, University Computing. 15, 1993, 58-69.

8. Coley, D. A. An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific Publishing Co. Pte. Ltd., 1999.

9. Davis, L. D. Genetic Algorithms and Simulated Annealing, Pitman, London, 1987.

10. Davis, L. D. Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.

11. Forrest, S. Genetic Algorithms: Principles of Natural Selection Applied to Computation. Science. 261, 1993, 872-878.

12. Fraser, A. S. Simulation of Genetic Systems by Automatic Digital Computers, Aust. J. Biol. Sei. 10, 1957, 484-499.

13. Gladkov L., Kureychik V. M., Kureychik V. V. Genetic algorithms. Edited by. Kureychik V. M. Rostizdat, Rostov-on-Don, 2004.

14. Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

15. Han, L., Kendall, G. and Cowling, P. An Adaptive Length Chromosome Iiyperheuristic Genetic Algorithm for a Trainer Scheduling Problem, 4th Asia-Pacific Conference on Simulated Evolution and Learning SEAL'02., 2002, 267271.

16. Kitano, H. Designing Neural Networks Using Genetic Algorithms with Graph Generation System, Complex Systems. 4, 1990, 461-476.

17. Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Programs, 3rd. Ed., Springer, 1996.

18. Mitchell, M. An Introduction to Genetic Algorithms, Massachusetts Institute of Technology, 1996.

19. Moscato, P. On Evolution, Search, Optimisation, Genetic Algorithms and Martial Arts: Towards Mcmetic Algorithms, Technical Report Caltech Concurrent Computation Program, Report 826, California Institute of Technology, Pasadena, California, USA, 1989.

20. Back, T. Evolutionary Algorithms in Theory and Practice, Oxford University Press, 1996.

21. Back, T., Fogel, D. and Michalewicz, Z. Handbook of Evolutionary Computation, Institute of Physics Publishing and Oxford University Press, 1997.

22. Bremermann, H. J. Optimisation Through Evolution and Re-Combination. In: Yovits,M., Sawbi,G., and Goldstein,G. (Eds.), Self-Organising Systems, Washington, Spartan, 1962.

23. Emelianov V., Kureychik Y. M. and Kureychik V. V. Theory and practice of evolutionary modelling. "Fizmatlit", Moscow, 2003.

24. Fogel, D. B. Evolutionary Computation: The Fossil Record, IEEE Press, 1998.

25. Fogel, D. B. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, IEEE Press, 2000.

26. Hart, E., Ross, P. and Nelson, J. A. Solving a Real-World Problem Using An Evolving Heuristically Driven Schedule Builder, Evolutionary Computing. 6, 1998,61-80.

27. Hart, W. E., Krasnogor, N., and Smith, J. E. Recent Advances in Memetic Algorithms and Related Search Technologies, Springer, 2003.

28. Yao, X. Evolutionary Computation: Theory and Applications, World Scientific, 1999.

29. Birrattari, M., Paquete, L., Stutzle, T. and Varrentrapp, K. Classification of Metaheuristics and Design of Experiments for the Analysis of Components, Technical Report AIDA-01-05, FG Intellektik, FB Informatik, TU Darmstadt, Germany, 2001.

30. Blum, C. and Roli, A. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison, ACM Computing Surveys. 35, 2003, 268-303.

31. Burke, E. and Kendall, G. Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Kluwer Academic Publishers, Boston, Dordrecht, London, 2005.

32. Dorigo, Marco, Optimization, Learning, and Natural Algorithms, PhD Thesis, Politécnico di Milano, Italy, 1992.

33. Feo, T. A. and Resende, M. G. C. A Probabilistic Heuristic for a Computational Difficult Set Covering Problem, Operations Research Letters. 8, 1989, 67-71.

34. Feo, T. A. and Resende, M. G. C. Greedy Randomized Adaptive Search Procedures, Journal of Global Optimization. 6, 1995, 109-133.

35. Glover, F. and Kochenberger, G. A. Handbook of Mela-Heuristics, Kluwer, 2003, ISBN: 1-4020-7263-5.

36. Michalewicz, Z. and Fogcl, D. B. How To Solve It: Model Heuristics, SpringerVerlag, 2000.

37. Nemhauser, G. L. and Wolsey, L. A. Linear and Combinatorial Optimization, Wiley, 1988.

38. Osman, I. II. and Kelly, J. P. Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, 1996.

39. Osman, I. H. and Laporte, G. Metaheursitics: A Bibliography, Annals of Operations Research. 63, 1996, 513-623.

40. Reeves, C. Modern Heuristic Techniques For Combinatorial Problems, McGraw-Hill, 1995, ISBN: 0-07-709239-2.

41. Coffman, E. G., Garcy, M. R., and Johnson, D. S. Approximation Algorithms for Bin Packing. In: Hochbaum,D.S. (Ed.), Approximation Algorithms for NPhard Problems, PWS Publishing, 1997, pp. 46-93.

42. Johnson D.S., Demers A., Ullman J.D., Garey M.R. and Graham R.L. A worst ease performance bounds for simple one-dimensional packing algorithms. SIAM Journal of Computing 3, 1974, 299- 325.

43. Beasley, J. E. OR-library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1990, 1069-107.

44. Ibarra, О. H. and Kim, С. E. Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of ACM. 22, 1975, 463-468.

45. Hillier, F. S. and Lieberman, G. J. Introduction to Operations Research, McGraw-Hill, 8th ed. 2005, ISBN: 0-07-252744-7.

46. Sahni, S. Approximate Algorithms for the 0-1 Knapsack Problem, Journal of ACM. 22, 1976, 115-124.

47. Scholl, A., Klein, R. and Jürgens, С. BISON: A Fast Hybrid Procedure for Exactly Solving the One-dimensional Bin Packing Problem, Computers & Operations Research. 24, 1997, 627-645.

48. Потарусон P.B., Курейчик B.M. Проблема одномерной упаковки элементов. Известия ТРТУ, №8, 2006, - с. 88 - 93.

49. Потарусов Р.В., Курейчик В.М. Задача одномерной упаковки. Анализ и обзор эвристических алгоритмов. ПИТИС, Таганрог, ТРТУ 2006, с.37-47.

50. Потарусов Р.В., Курейчик В.М. Задача одномерной упаковки и ее использование при решении задачи маршрутизации автотранспорта. Сборник трудов международных научно-технических конференций AIS'06, CAD'06, 2006,-с. 56-61.

51. Valerio de Carvalho, J. M. Exact Solution of Bin-packing Problems Using Column Generation and Branch-and-bound, Annals of Operations Research. 86, 1999, 629-659.

52. Falkenauer, E. A Hybrid Grouping Genetic Algorithm for Bin Pacing, Journal of Heuristics. 2, 1996, 5-30.

53. Falkenauer, E. Genetic Algorithms and Grouping Problems, John Wiley & Sons Ltd, 1998.

54. Lim, A., Rodrigues, В. and Zhang, X. Metaheuristics With Local Search Techniques for Retail Shelf-Space Optimization, Management Science. 50, 2004, 117-131.i

55. Lourenco, H. R., Martin, О. C., and Stutzle, T. Iterated Local Search. In: Glover,F. and Kochenberger,G.A. (Eds.), Handbook of Metaheuristics, Kluwer, 2003, pp. 321-354.

56. Потарусов P.B. Гибридный параллельный группирующий генетический алгоритм для решения задачи упаковки блоков. Известия ЮФУ, № 4, 2008, - с. 42-45.

57. Потарусов Р.В., Курейчик В.М. Модифицированные генетические операторы'. Сборник трудов международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте», 28-30 мая, Коломна, 2007.

58. Потарусов Р.В. Гибридный генетический поиск для задачи упаковки блоков. Известия ЮФУ. Технические науки, № 2, 2007, с. 30-35.

59. Potarusov, R., Kureychilc, V., Goncalves, G. and Allaoui Ii. Solving the Bin Packing Problem with Algorithm of Genetic Search with Migration.

60. Potarusov, R., Kureychik, V., Goncalves, G. and Allaoui 11. Solving the Bin Packing Problem with Hybrid Parallel Genetic Algorithm. The paper has been submitted to the INCOM'09 International Conference, Moscow, June 3-5, 2009.

61. Resende, M. G. C. and Ribeiro, C. C. Greedy Randomized Adaptive Search Procedures. In: Glover F. and Kochenberger,G.A. (Eds.), Handbook of Metaheuristies, Kluwer, 2003, pp. 219-249.

62. Taillard, E. D., Gambardella, L. M., Gendreau, M. and Potvin, J. Adaptive Memory Programming: A Unified View of Metaheuristies, European Journal of Operational Research. 135,2001, 1-16.

63. Voss, S., Martello, S., and Osman, I. H. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, 1999.

64. Voudouris, C. and Tsang, E.P.K. Guided Local Search. Technical Report CSM-247, Department of Computer Science, University of Essex, 1997.

65. Voudouris, C. and Tsang, E. P. K. Guided Local Search. In: Glover F. and Kochenbergcr,G. (Eds.), Handbook of Metaheuristies, Kluwer, 2003, pp. 185218.

66. Levine J. and F. Ducatelle. Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems. Centre for Intelligent Systems and their Applications, School of Informatics, University of Edinburgh, 2003.

67. Dorigo, M., Vittorio, M. and Alberto, C. Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man and Cybernetics Part B : Cybernetics. 26, 1996, 29-41.

68. Dorigo, M. and Stutzle, T. The Ant Colony Optimisation Metaheuristic: Algorithms, Applications and Advances. In: Glover F. and Kochenberger,G. (Eds.), Handbook of Metaheuristies, Kluwer, 2003, pp. 457-474.

69. Gambardclla, L. M. and Dorigo, M. Ant Colony System Hybridised with a New Local Search for the Sequential Ordering Problems, INFORMS Journal on Computing. 12, 2000, 237-255.

70. Gupta, J. N. D. and Ho, J. C. A New Hcuristic Algorithm for the One-dimensional Bin-packing Problem, Production Planning & Control. 10, 1999, 598-603.

71. Fleszar, K. and Hindi, K. S. New Heuristics for One-dimensional Bin-packing, Computers & Operations Research. 29, 2002, 821-839.

72. Bai, R. An investigation of novel approaches for optimizing retail shelf space allocation. Ph. D thesis. School of Computer Science & Information Technology. The University of Nottingham, Nottingham, UK, 2005.

73. Alvim Adriana C. F., Glover Fred S., Ribeiro Celso C., and Aloise Dario J. Local search for the bin packing problem. Journal of Heuristics, 10, 2004, 205-229.

74. Glover F. and Laguna, M. Tabu Search. In: Reeves,C.R. (Ed.), Modem Heuristic Techniques for Combinatorial Problems, McGraw-Hill, 1995, pp. 21-69.

75. Glover, F., Laguna, M., and Marti, R. Scatter Search and Path Relinking. In: Glover,F. and Kochenberger,G.A. (Eds.), Handbook of Metaheuristics, Kluwer, 2003, pp. 1-37.

76. Glover, F. Heuristics for Integer Programming using Surrogate Constraints, Decisions Science, 8, 1977, 155-166.

77. Glover, F. Tabu Search Part I, ORSA Journal on Computing, 1, 1989, 190-206.

78. Glover, F. Tabu Search Part II, ORSA Journal on Computing, 2, 1990, 4-32.

79. Glover, F. and Laguna, M. Tabu Search, Kluwer Academic Publishers, 1997.

80. Aarts, E. H. L. and van Laarhoven, P. J. M. Statistical Cooling: A General Approach to Combinatorial Optimization Problems, Phillips Journal of Research. 40, 1985, 193-226.

81. Dowsland, IC. A. Some Experiments with Simulated Annealing Techniques for Packing Problems, European Journal of Operational Research. 68, 1993, 389399.

82. Fisher, Ii. and Thompson, G. L. Probabilistic Learning Combinations of Local Job-shop Scheduling Rules, Factory Scheduling Conference, Carnegie Institute of Technology. May, 1961, 10-12.

83. Gabriele, G. A. and Ilagsdell, K. M. The Generalized Reduced Gradient Method: A Reliable Tool for Optimal Design, AMSE Journal of Engineering for Industry. 99, 1977, 384-400.

84. Fujiwara, O. and Perera, U. L. J. S. R. EOQ Models for Continuously Deteriorating Products Using Linear and Exponential Penalty Costs, European Journal of Operational Research. 70, 1993, 104-114.

85. Gendreau, M. Recent Advances in Tabu Search. In: Ribeiro,C.C. and Hansen,P. (Eds.), Essays and Surveys in Metaheuristics, Kluwer Academic Publishers, 2002, pp. 369-377.

86. Gendreau, M., Hertz, A. and Laporte, G. A Tabu Search Heuristic for the Vehicle Routing Problem, Management Science. 40, 1994, 1276-1290.

87. Giri, B. C., Pal, S., Goswami, A. and Chaudhuri, K. S. An Inventory Model for Deteriorating Items with Stock-dependent Demand Rate, European Journal of Operational Research. 95, 1996, 604-610.

88. Goyal, S. K. and Giri, B. C. Recent Trends in Modeling of Deteriorating Inventory, European Journal of Operational Research. 134, 2001, 1-16.

89. Gruen, T. and Shah, R. Determinants and Outcomes of Plan Objectivity and Implementation in Category Management Relationships, Journal of Retailing. 76, 2000,483-510.

90. Hart, C. and Davies, M. The Location and Merchandising of Non-food in Supermarkets, International Journal of Retail & Distribution Management. 24, 1996, 17-25.

91. Hollier, R. Ii. and Mak, K. L. Inventory Replenishing Policies for Deteriorating Items in a Declining Market, International Journal of Production Research. 21, 1983, 813-826.

92. Hwang, H., Choi, B. and Lee, M.-J. A Model for Shelf Space Allocation and Inventory Control Considering Location and Inventory Level Effects on Demand, International Journal of Production Economics. In Press, 2005.

93. Ibbotson, J. Personal Correspondence, Retail Vision, 2002.

94. Jain, K. and Silver, E. A. Lot Sizing for a Product Subject to Obsolescence or Perishability, European Journal of Operational Research. 75, 1994, 287-295.

95. Kaelbling, L. P., Littman, M. L. and Moore, A. W. Reinforcement Learning: A Survey, Journal of Artificial Intelligence Research. 4, 1996, 237-285.

96. Kar, S., Bhunia, A. K. and Maiti, M. Inventory of Multi-deteriorating Items Sold From Two Shops Under Single Management with Constraints on Space and Investment, Computers & Operations Research. 28, 2001, 1203-1221.

97. Kendall, G. and Mohamad, M. Channel Assignment Optimisation Using a Hyper-heuristic, In the Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems (CIS), Singapore, 1-3 December 2004, 2004a, 790-795.

98. Kendall, G. and Mohamad, M. Channel Assignment In Cellular Communication Using A Great Deluge Ilyper-heuristic, In the Proceedings of the 2004 IEEE International Conference on Network (ICON2004), Singapore, 16-19 November 2004, 2004b, 769-773.

99. Kendall, G. and Mohd Ilussin, N. An Investigation of a Tabu Search Based Hyper-heuristic for Examination Timetabling. In: Kendal 1,G., Burke,E., and Petrovic,S. (Eds.), Selected Papers from MISTA 2003, ICluwer Academic Publisher, 2005, 309-328.

100. Kendall, G. and Mohd I-Iussin, N. An Investigation of a Tabu Search Based Hyper-heuristic for Examination Timetabling. In: Kendall,G., Burke,E., and Petrovic,S. (Eds.), Selected Papers from MISTA 2003, Kluwer Academic Publisher, 2004a.

101. Kotzan, J. and Evanson, R. Responsiveness of Drug Store Sales to Shelf Space Allocations, Journal of Marketing Research. 6, 1969, 465-469.

102. Lasdon, L. S., Waren, A. D., Jain, A. and Ratner, M. Design and Testing of a Generalized Reduced Gradient Code for Nonlinear Programming, ACM Transactions on Mathematical Software. 4, 1978, 34-50.

103. Levy, M. and Weitz, B. Retailing Management, Homewood, IL., 1992, ISBN: 0256-05989-6.

104. Lundy, M. and Mees, A. Convergence of an Annealing Algorithm, Mathematical Programming. 34, 1986, 111-124.

105. Mazzola, J. B. and Schantz, R. Ii. Single-facility Resource Allocation Under Capacity-based Economics and Diseconomies of Scope, Management Science. 41, 1995, 669-689.

106. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. Ii. and Teller, E. Equation of State Calculation by Fast Computing Machines, Journal of Chemical Physics. 21, 1953, 1087-1091.

107. Mockus, J. A Set of Examples of Global and Discrete Optimization: Application of Baycsian Heuristic Approach, Kluwer Academic Publishers, Dordrecht-London-Boston, 2000.

108. Moscato, P. and Cotta, C. A Gentle Introduction to Memetic Algorithms. In: Glover,F. and ICochenberger,G.A. (Eds.), Handbook of Metaheuristics, Kluwer, 2003, pp. 105-144.

109. Petch, R. J. and Salhi, S. A multi-phase constructive heuristic for the vehicle routing problem with multiple trips. Discrete Applied Mathematics, 133, 2004, 69-92.

110. Rao, R. L. and Iyengar, S. S. Bin-packing by Simulated Annealing, Computers & Mathematics with Applications. 27, 1994, 71-82.

111. Ross, P., Schulenburg, S., Marin-Blazquez, J.G., and Hart, E. Hyper Heuristics: Learning to Combine Simple Heuristics in Bin-packing Problems, Proceeding of the Genetic and Evolutionary Computation Conference, GECC02002, New York, US, 2002, 942-948.

112. Smith, J. Co-evolving Memetie Algorithms: Initial Investigations. In: Parallel Problem Solving from Nature VII, PPSN 2002, Lecture Notes in Computer Science, Springer-Verlag, 2002, pp. 537-546.

113. Toth, P. Dynamic Programming Algorithms for the Zero-one Knapsack Problem, Computing. 25, 1980, 29-45.

114. Urban, T. An Inventory-Theoretic Approach to Product Assortment and Shelf-Space Allocation, Journal of Retailing. 74, 1998, 15-35.

115. Wang, C.J. and Tsang, E.P.K. Solving Constraint Satisfaction Problems Using Neural-networks, Proceedings of the IEE Second International Conference on Artificial Neural Networks, 1991, 295-299.

116. Wang, C. J. and Tsang, E. P. K. A Cascadable VLSI Design for GENET. In: Delgado-Frias, J.G. and Moore, W.R. (Eds.), VLSI for Neural Networks and Artificial Intelligence, New York, Plenum Press, 1994, pp. 187-196.

117. Yang, M.-H. An Efficient Algorithm to Allocate Shelf Space, European Journal of Operational Research. 131,2001, 107-118.

118. Yang, M.-H. and Chen, W.-C. A Study on Shelf Space Allocation and Management, International Journal of Production Economics. 60, 1999, 309-317.

119. Zufryden, F. A Dynamic Programming Approach for Product Selection and Supermarket Shelf-Space Allocation, Journal of Operations Research Society. 37, 1986,413-422.

120. Ross, P. Hyper-Heuristics. In: Burke, E. and Kendall, G. (Eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Springer, 2005, pp. 529-556.

121. Gutin, G. Exponential Neighbourhood Local Search for the Traveling Salesman Problem, Computer & Operations Research. 26, 1999, 313-320.

122. Ahuja, R. K., Orlin, J. B. and Sharma, D. Very Large Scale Neighbourhood Search, International Transaction in Operational Research. 7, 2000, 301-317.

123. Bellman, R. Dynamic Programming, Princeton University Press, 1957.

124. Dantzig, G. B. Linear Programming and Extensions, Princeton University Press, Princeton, 1963.

125. Hansen, P. and Maldenovic, N. Variable Neighbourhood Search: Principles and Applications, European Journal of Operational Research. 130, 2001, 449-467.

126. Hansen, P. and Maldenovic, N. Variable Neighbourhood Search. In: Glover F. and Kochenberger,G. (Eds.), Handbook of Mcta-Heuristies, Kluwer, 2003, pp. 145-184.

127. Mladenovic, N. and Hansen, P. Variable Neighbourhood Search, Computers & Operations Research. 11, 1997, 1097-1100.

128. Cantu-Paz, E. A Summary of research on Parallel Genetic Algorithms. 1995, IlliGAL Report No. 95007.