Генетичните алгоритми (GA) се опитват да подходят към решаването на проблеми по начина, по който го правят природата и еволюцията. Най-здравите индивиди се избират за размножаване, за да се създаде потомство от следващото поколение. В тази статия ще се опитаме да решим пъзел с 8 дами, използвайки една за образователни цели. 8 дами е класически пъзел за поставяне на осем дами на шахматна дъска 8x8, така че две дами да не се заплашват една друга. Следователно две дами не трябва да споделят един и същи ред, колона или диагонал.

Подходът, който ще използваме, когато се справяме с проблема с 8-те дами Първо, ще потърсим комбинация от списък, която дава нулеви разходи за функцията на разходите, което означава, че нито една дама не атакува другата дама.

Предполагаме, че всяка царица принадлежи на отделен ред, в противен случай те вече биха се атакували една друга. Например шахматната дъска вдясно ще бъде декодирана като [3,1,6,2,5,7,4,0] . Нашата цел е да намерим една такава пермутация.

Аналитично процесът включва следните стъпки:

  • Инициализация: Създава се популация с подходящ размер и подходяща дължина. Размерът на популацията не трябва да се поддържа много голям, тъй като може да доведе до забавяне на GA, докато по-малка популация може да не е достатъчна за добро брачен басейн. Следователно оптималният размер на популацията трябва да бъде определен чрез проба и грешка.
  • Избор: включва подбор на подмножество от най-добрите резултати от текущата популация, т.е. резултатите от 8-те дами, които имат функцията на минималните разходи. В нашия случай ще запазим 20% от населението.
  • Кръстосано: Избирайки това подмножество, ще избираме произволно 2 от тези думи всеки път и ще ги кръстосваме. Избирайки произволна дължина от 0,8, която е дължината на състоянията на Куинс, ще вземем първия бит от първата дума и ще го свържем с втората дума от втория бит

Визуално изображение по-долу показва какво се случва:

  • Мутация: Мутацията се проявява с малка случайна промяна в комбинацията от индивиди. Тази мутация се случва веднъж с малка вероятност. В нашия случай това е 30% от времето.

По-долу не прави нищо повече, освен описаното по-горе в една рутина:

И накрая, е необходимо представяне на клас EightQueensState, за да работи всичко:

Двойният for цикъл за всяка шахматна позиция като по-долу ще визуализира нашето решение:

Така че сега нашият алгоритъм работи. Но нека го увеличим, като направим няколко допълнителни стъпки и разширим нашето приложение:

  • Първо нека накараме дамите да приемат произволен брой дами.
  • Тъй като имаме пермутация, има смисъл да се възползваме от това и да не го третираме като цяло число. Промяната към пермутация вместо цяло число трябва да доведе до по-добър резултат по-бързо.
  • Накрая внедрите функцията за кръстосване на реда на Дейвис и промяна на мутацията.

Опитахме се да използваме OX1, за да постигнем по-бързи резултати. Това, което направихме в нашата нова кросоувър функция, включва следните стъпки.

  1. Създайте две произволни точки на кръстосване в първия родител, копирайте сегмента между тях от първия родител към потомството.
  2. Започвайки от втората точка на пресичане във втория родител, копирайте останалите неизползвани числа от втория родител към първото дъщерно, обвивайки списъка.
  3. Направете същото за второто дете, като първият родител сега е вторият и обратното.
  4. Тъй като запазването им на една и съща функция на мутация или изтриването й нарушава приложението, защото ще имаме повече от едно появяване на един и същи номер и това би нарушило внедряването на OX1 или ще конвергира наистина бързо получаване на стека в опит да се намери комбинация, където тя не съществува. Внедрихме функция за мутация, която на всеки 30% от времето просто въвежда произволна пермутация на нов индивид.

Пример за кросоувър на Дейвид [2]

Сега нека направим последователен начин за преценка дали нашите подобрения наистина повишават ефективността на нашия алгоритъм във времето. И така, създаваме цикъл за първите 100 семена и изчисляваме времето, необходимо на алгоритъма да намери оптимално решение.

Добавянето на графика и статистика за средна стойност, средна стойност, дисперсия, макс., мин. ще ни даде усещане колко добре сме се справили.

Тези графики показват нашите начални времена:

Подобрената версия ясно показва значително увеличение на ефективността на алгоритъма.

Пълният проект е на GitHub https://github.com/nikkaramessinis/Genetic-Algorithm

Ако сте харесали съдържанието, моля, обмислете да следвате Ник Карамесинис или https://www.buymeacoffee.com/nikaramesinis. За всякакви корекции или допълнения сте повече от добре дошли да коментирате за повече дискусия.

Препратки

[1] Изкуственият интелект - модерен подход, трето издание. (n.d.).

[2]Генетичен алгоритъм: Проблем с 8 кралици | от Cheng Xi Tsou | Nerd For Tech | Среден. (n.d.). Изтеглено на 18 януари 2022 г. от

https://medium.com/nerd-for-tech/genetic-algorithm-8-queens-problem-b01730e673fd

[3] Генетични алгоритми — Бързо ръководство. (n.d.). Изтеглено на 18 януари 2022 г. от https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_quick_guide.htm