Генетический алгоритм для размещения разногабаритных элементов на печатной плате?

Question

[chincharovpc]

Есть элементы, у которых известны (Высота, Ширина).
Есть матрица связей(Какие элементы между собой связаны и количество связей)

Ниже приведен пример:



Нужно эти элементы разместить на плате с помощью Генетического алгоритма.

Ниже приведен пример:


Пока я делаю так:
1)Берем элемент, у которого больше всех связей и Размещаем на плате
2)Берем элемент у которого больше всех связей с размещенными
3) И так до конца

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

А теперь нужно с помощью Генетического алгоритма.

Comments

[Владимир Солнцев]

Ниче не понятно, но я тоже хочу! Подскажете, с чего начать?

[mayton2019]

Можно поискать "задачу оптимального раскроя". Она похожа на топик.

Генетический тут неудобен. Сложно протянуть аналогии между координатами элементов и геном. И любое скрещивание будет порождать на 99 процентов непригодные расклады.

Вобщем - поиск в глубину лучше.

[xmoonlight]

mayton2019, крайне легко.

[mayton2019]

xmoonlight, you welcome. Автор ждет помощи.

[chincharovpc]

mayton2019, мне нужен именно генетический алгоритм

[mayton2019]

Ты надеешся что кто-то напишет здесь готовое решение под "ключ"?

Давай поговорим о функции приспособленности для твоей задачи. Обычно - это метрика. Которая характеризует как некая вещественная величина харатеризуюая пригодность варианта решения. Ее у тебя вообще нет. Или она - булевая. Элементы уложились? Или нет. Если элементы легли с нахлёстом? Как это считать? Метрика? Какая?

Как будет работать ГА в твоём случае - я не знаю.

[xmoonlight]

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

Или максимизировать общее количество свободных клеток сетки размещения.

Теперь, куда уж проще...

[mayton2019]

Не намного проще. По прежнему неизвестно как скрещивать и мутировать раскладки.

Answer 1

[Antonio Solo]

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

ну а дальше поле для экспериментов

Comments

[chincharovpc]

Алгоритм зависит от последовательности размещения и от точки размещения очередного элемента. Для последовательности можно поступить так как вы сказали. Но на плате элемент можно разместить где угодно, пока я ищу локальный минимум и размещаю туда. А нельзя применить ГА к размещению тоже?

[Antonio Solo]

pakhrudin, ну на ум приходят следующее первый элемент ставится как бы посередине всегда да а все последующие достраивается с какой-то стороны но я например ваш алгоритм выглядит так взять элемент n и поставить его стороны м

То есть ваша последовательность будет выглядеть как пары номер элемента страна с которой он пристраивается.

[Antonio Solo]

pakhrudin, вы всегда на каждом шаге имеете какуюто расстановка как результат вашей последовательности

[chincharovpc]

Antonio Solo, Еще один вопрос. Я применяю мутацию, инверсию, сегрегацию и т.д. А проверять целевую функцию нужно после каждого метода или после выполнения всех методов?