Как я могу использовать генетический алгоритм для решения этой проблемы оптимизации размещения?

Question

Я хотел бы использовать GA для решения следующей проблемы:

• У меня есть белое изображение с разрешением 100 * 100, которое всегда имеет 50 черных пикселей.
• Я могу выбрать, какими могут быть эти 50 пикселей.
• У меня уже есть функция f (изображение), которая в соответствии с положением этих 50 черных пикселей возвращает оценку (я не знаю, какой может быть максимальная оценка).

Как определить, какой набор из 50 пикселей является приблизительно лучшим (без необходимости пробовать все возможные комбинации)? Я новичок в GA, и я хотел бы спросить, как мне подойти / реализовать такую ​​оптимизацию?

Answer 1

Добавление к ответу Альваро:

Чтобы составить совокупность из N, каждый из этих N объектов будет действительным изображением, т. Е. Белым изображением с разрешением 100 * 100, которое всегда имеет 50 черных пикселей.

50 черных пикселей можно разместить случайным образом (если N большое) или любым другим способом.Это установит начальную популяцию размера N, где каждая хромосома будет иметь структуру данных размером 100x100 (в основном, ваше изображение).

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

Теперь, чтобы увеличить население, вам понадобятся «Функция кроссовера» и / или «Мутация».функция».

Мутация может быть сделана путем изменения некоторого (скажем, k, где k <50) положения черных пикселей с белым пикселем, что-то так, чтобы хромосома не теряла своего основного свойства, а лишь немного мутировала от оригиналаimage. </p>

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

Повторите шаги для генерации лучшей популяции, кроссовера, мутации, генерации лучшей популяции, кроссовера, мутации ... до схождения или для набора нет.итераций.

Answer 2

Ваш вопрос слишком широк для SO. Но вот краткое изложение того, как работает GA. Ключевым моментом является то, что у вас уже есть фитнес-функция.

1. Определить численность населения N.
2. Определите кодировку вашей хромосомы. Это может быть сложно.
3. Произведите случайным образом N-хромосомы.
4. Рассчитать пригодность для каждой хромосомы, используя f(image).
5. Создание следующего поколения, выполняющего выбор (с использованием предварительно рассчитанного показателя пригодности) и мутацию.
6. Повторите с 4 определенное количество раз или если удовлетворены конечные критерии.

Надеюсь, это поможет в качестве отправной точки. Возможно, вам следует проверить некоторые примеры GA, начать писать код и задать несколько более конкретных вопросов, если вам нужно.