Задача о 8 ферзях генетическим алгоритмом (бинарная кодировка)

@dadapilot · Регистрация: 12.12.2017

Студворк — интернет-сервис помощи студентам

Добрый день!
Нужно решить задачу о 8 ферзях генетическим алгоритмом. Алгоритм, в сущности, ясен, но сразу возникли трудности с бинарной кодировкой шахматной доски так, чтобы ферзи не били друг друга по строкам и столбцам.
То есть, можно кодировать, например, так: (03276145), где индекс массива отвечает за положение в строке, а значение за положение в столбце, если значения в массиве не повторяются -- ферзи не бьют друг друга и по строкам и по столбцам.
Но требуется решить задачу именно Классическим Генетическим Алгоритмом! То есть кодировка должна быть бинарная..
То есть надо закодировать положение ферзей в одну строку из нулей и единиц, не могу понять, как можно это сделать, пожалуйста, помогите.

@dondublon · 12.12.2019, 12:52

dadapilot, странно. Вы уже решили сложную проблему ("генетический алгоритм ясен"), не разобравшись с простой.

Генетический алгоритм на вход должен получить именно строку нулей и единиц?

Представить положение ферзей - проще простого. Каждый ферзь = две координаты = два числа от 0 до 8 (0-7) = три двоичных числа.

@dadapilot · 12.12.2019, 17:12 **[ТС]**

dondublon, ну мне изначально в голову только такой вариант пришел: если изначально положение ферзей описывалось (03276145), то бинарный код -- просто перевод в двоичную сс этих значений, а при вычислении целевой функции ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum(X_i-X_j)-(Y_i-Y_j)$ -- количество попаданий под бой) брать каждый третий индекс деленный на три и тоже переводить в 2-ю сс.. Мне почему-то показалось это глупой затеей.
Или я вообще что-то не то ни в ту сторону думаю.

"Генетический алгоритм на вход должен получить именно строку нулей и единиц?"
Вообще нет вроде как, есть реализации этой задачи, где на вход идет просто список чисел от 0 до n.
Но, вот например в таком случае.. Если какой-то хромосоме из популяции выпала участь мутировать, то, получается, мутация в данном случае -- это просто случайная перестановка генов, то есть получается совершенно другая хромосома, тогда как в бинарном варианте мы инвертировали бы один ген, у каждого гена вероятность подвергнуться инверсии была бы 1/n.

@dadapilot · 13.12.2019, 15:57 **[ТС]**

Ну в общем решила, все нормально, немного пришлось затупить вначале, конечно..

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@dadapilot 0 / 0 / 0 Регистрация: 12.12.2017 Сообщений: 6

	Задача о 8 ферзях генетическим алгоритмом (бинарная кодировка) 12.12.2019, 08:55. Показов 2126. Ответов 3 Метки нет (Все метки) Добрый день! Нужно решить задачу о 8 ферзях генетическим алгоритмом. Алгоритм, в сущности, ясен, но сразу возникли трудности с бинарной кодировкой шахматной доски так, чтобы ферзи не били друг друга по строкам и столбцам. То есть, можно кодировать, например, так: (03276145), где индекс массива отвечает за положение в строке, а значение за положение в столбце, если значения в массиве не повторяются -- ферзи не бьют друг друга и по строкам и по столбцам. Но требуется решить задачу именно Классическим Генетическим Алгоритмом! То есть кодировка должна быть бинарная.. То есть надо закодировать положение ферзей в одну строку из нулей и единиц, не могу понять, как можно это сделать, пожалуйста, помогите. 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	12.12.2019, 12:52
	dadapilot, странно. Вы уже решили сложную проблему ("генетический алгоритм ясен"), не разобравшись с простой. Генетический алгоритм на вход должен получить именно строку нулей и единиц? Представить положение ферзей - проще простого. Каждый ферзь = две координаты = два числа от 0 до 8 (0-7) = три двоичных числа. 0

@dadapilot 0 / 0 / 0 Регистрация: 12.12.2017 Сообщений: 6
	12.12.2019, 17:12 [ТС]
	dondublon, ну мне изначально в голову только такой вариант пришел: если изначально положение ферзей описывалось (03276145), то бинарный код -- просто перевод в двоичную сс этих значений, а при вычислении целевой функции ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum(X_i-X_j)-(Y_i-Y_j)$ -- количество попаданий под бой) брать каждый третий индекс деленный на три и тоже переводить в 2-ю сс.. Мне почему-то показалось это глупой затеей. Или я вообще что-то не то ни в ту сторону думаю. "Генетический алгоритм на вход должен получить именно строку нулей и единиц?" Вообще нет вроде как, есть реализации этой задачи, где на вход идет просто список чисел от 0 до n. Но, вот например в таком случае.. Если какой-то хромосоме из популяции выпала участь мутировать, то, получается, мутация в данном случае -- это просто случайная перестановка генов, то есть получается совершенно другая хромосома, тогда как в бинарном варианте мы инвертировали бы один ген, у каждого гена вероятность подвергнуться инверсии была бы 1/n. 0

@dadapilot 0 / 0 / 0 Регистрация: 12.12.2017 Сообщений: 6
	13.12.2019, 15:57 [ТС]
	Ну в общем решила, все нормально, немного пришлось затупить вначале, конечно.. 0