Расстановка элементов на плате. Как реализовать с помощью генетических алгоритмов?

Question

[chincharovpc]

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

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



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

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


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

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

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

Comments

[roswell]

https://ru.wikipedia.org/wiki/Генетический_алгоритм (не благодари).

[chincharovpc]

roswell, Я хотел узнать как именно применить генетический алгоритм в этой задаче

[Александр Скуснов]

По-моему, это не актуально: лучше использовать 4 слоя (продольные, поперечные, плюс, минус) и располагать как хочется.

[Сергей П]

Александр Скуснов, да человеку, наверно, лабу сделать надо, а-то пятёрку не поставят, а вы: "неактуально... четыре слоя..."

Answer 1

[xmoonlight]

Начинать надо с соотношения сторон.
Это цель алгоритма.
Затем, нужно раскидать в 2 кучки произвольные элементы (начиная с самых крупных по размеру!), максимально приближаясь к цели (пропорции сторон платы).
Затем, начинаете менять местами (swap) те элементы разных кучек, которые дадут ещё большее приближение к цели, и так до тех пор, пока оптимизация станет невозможна.
Останавливаете алгоритм и получаете размещение с помощью ГА.

Comments

[imageman]

"начинаете менять местами (swap)" - это можно сказать мутация. А скрещивание где?

"раскидать в 2 кучки" - и на плату кидать просто кучку?!

Немного не понятно "максимально приближаясь к цели (пропорции сторон платы)" - это как?

Answer 2

[imageman]

Генетическим алгоритмом примерно так:
Сначала Разрабатываем способ кодировки. Например [Номер элемента, координаты, расположение].

Запускаем алгоритм, и он выдает кучку чисел "генетического кода", который мы превращаем в фетотип: на пустую плату последовательно помещяем все [Номер элемента, координаты, расположение].

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

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

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