3. Решение задачи размещения разногабаритных элементов в пространстве на основе га

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

-заданы ограничения на объем размещения (например - габариты конкретного корпуса);

-заданы габариты (размеры) элементов размещения;

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

Исходными данными задачи являются: а, b - габариты монтажного поля; {(а₁, Ь₁), ...,(а_i, 6_i),…, (а_n, 6_n)} - множество габаритов элементов размещения; С - матрица связей элементов, представляющая собой матрицу связности. Необходимо найти такой вариант размещения элементов на монтажном поле: Z= {(x₁, y₁), …,(x_i,y_i), …,(x_n,y_n)},где (x_i,y_i) - координаты центра тяжести установочной площади i-го элемента размещения, при котором площадь перекрытия размещения элементов была бы равна нулю.

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

4. Порядок выполнения работы

1.Ввести исходные данные габаритов элементов согласно табл. 1. Выбрать в качестве критерия останова ГА достижение числа поколений заданной величины, число поколений принять равным 300.

Таблица 1

Исходные данные задачи

Исходные данные	Вариант 1	Вариант 2	Вариант 3	Вариант 4
Габариты монтажного пространства	100x100	100x100	100x100	100x100
Элемент 1	24x10	12x28	10x10	25x45
Элемент 2	32x40	31x40	20x18	22x14
Элемент 3	32x15	15x25	11x24	11x10
Элемент 4	20x22	12x50	30x45	31x16
Элемент 5	10x48	21x19	31x18	20x24
Элемент 6	17x20	20x22	45x19	Г 16x22
Элемент 7	41x33	39x33	35x32	40x35
Элемент 8	25x47	49x17	28x20	24x50
Элемент 9	20x20	15x29	20x19	25x27
Элемент 10	9x10	10x10	10x50	13x13
Вероятность кроссовера	0,6	0,6	0,6	0,6
Вероятность мутации	0,05	0,05	0,05	0,05
Размер популяции (М)	200	200	200	200

Ввод числа и габаритов элементов осуществляется в диалоговом окне «Входные параметры» (меню «Алгоритм —> Входные параметры») см.рис.3). Параметры матрицы связности в данной работе не используются.

Настройка параметров генетического алгоритма осуществляется в диалоговом окне «Параметры эволюции» (меню «Алгоритм→Параметры эволюции») (см. рис. 4).

2.Сгенерировать начальное размещение элементов на монтажном пространстве, используя пункт меню «Алгорим→Генерация исходной популяции».

3.Запустить алгоритм на выполнение с помощью кнопки «Запуск» на панели инструментов, либо пункта меню «Алгоритм → Эволюция».

Рис. 3. Диалоговое окно ввода входных параметров

4.Занести в отчет график зависимости значения целевой функции от времени эволюции (числа поколений) (пункт меню «Просмотр —> Статистика»), количество мутаций и площадь пересечения элементов.

5.Уменьшить значение размера популяции с 200 на 100. Повторить работу, начиная с пункта 2.

6.Увеличить значение размера популяции со 100 на 200, значение вероятности кроссовера на 0,99. Повторить работу, начиная с пункта 2.

7.Изменить значение вероятности кроссовера на 0,6, значение вероятности мутации на 0,1. Повторить работу, начиная с пункта 2.

8.Изменить значение вероятности мутации на 0,05. В основном окне программы выбрать алгоритм «стратегия с рекомбинацией (т. к)». В окне параметров эволюции (см. рис. 4) задать соотношение числа родителей к потомкам (4, 1). Повторить работу, начиная с пункта 2.

9.Повторить пункт 8, последовательно изменяя соотношение числа родителей к потомкам (т, к). Сопоставить результаты работы алгоритма.

Рис. 4. Параметры генетического алгоритма.