Исследование эффективности генетических алгоритмов для задачи размещения радиоэлементов в корпусе устройства

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

1. Хромосома представляет собой связанный список пар координат центров тяжестей элементов размещения. Каждая координата описывается вещественным числом.

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

3. Условие завершения эволюции задается в виде определения числа поколений либо в виде условия достижения нулевого перекрытия элементов.

Результаты анализа поведения генетического алгоритма в зависимости от значений вероятности мутации приведены на рис. 1. Эксперимент проводился для значений вероятностей мутации в диапазоне от 0,1 до 0,6 с шагом 0,1. Значение вероятности более 0,6 нарушает сходимость функции оптимальности ГА.

Кроме стандартного ГА, для решения задачи размещения можно использовать эволюционные стратегии: стратегию «только мутация» с пропорциональным оператором селекции; стратегию с рекомбинацией (т, k). Такой оператор рекомбинации предполагает тродителей и k потомков. Параметры m и k устанавливает пользователь. Теоретически ограничения на параметры имеют следующий вид: т= 1, ..., l-1; k= 1, ..., т. Параметр l - длина хромосомы (или в нашем случае количество элементов размещения). Экспериментально исследовались следующие сочетания родителей и потомков: (2, 2), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (4, 4). Следует отметить, что при сочетании (2, 1) мы получаем в качестве оператора рекомбинации обычный одноточечный кроссинговер, в котором участвуют два родителя и один потомок, выбираемый случайным образом. На рис. 2 (а, б)показаны в сравнении виды графиков оптимальности генетического алгоритма.

Ряд экспериментов с алгоритмом, применяющим стратегию с альтернативным оператором рекомбинации, выявил особую результативность оператора рекомбинации (3, 3), хотя в целом результаты данного вида алгоритма хуже, чем в случае со стандартным генетическим алгоритмом с одноточечным кроссинговером. В первую очередь это связано с тем, что значительное увеличение точек разреза хромосом ведет к разрушению хороших подобластей потенциальных решений. На рис. 2, б это заметно по многочисленным «всплескам» на графике.

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

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

На этапе инициализации генерируется λстрок случайным образом. Параметр λ— размер популяции задается пользователем. Функция оптимальности для каждой хромосомы вычисляется, как площадь перекрытия элементов.

Эффективность мобильного ГА для задач структурного синтеза можно проверить на следующих четырех тестовых наборах: «большое монтажное поле и мало элементов размещения»; «много элементов размещения» (высокая плотность упаковки); «низкая плотность упаковки, но разные элементы размещения»; «высокая плотность упаковки и велико разнообразие». Результаты экспериментов представлены в табл. 5.4.

В табл. 5.4 под четными номерами приведены результаты работы стандартного ГА, а под нечетными — мобильного ГА. На основании проведенных экспериментов можно сделать вывод о результативности мобильного генетического алгоритма.

4. Индивидуальные задания

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

5. Содержание отчета

1. Тема лабораторной работы.

2. Цель лабораторной работы.

3. Индивидуальное задание.

4. Результаты выполнения пунктов индивидуального задания.

5. Выводы по работе.