Генетични алгоритми; Лаборатория 3

Лаборатория 3

съдържание

Генетични алгоритми

Методът е вдъхновен от еволюционната теория на Дарвин. Работа с a популация на кандидат-решение, който се развива и адаптира към среда (в този случай средата е функцията, която трябва да се оптимизира). Генотипът се променя:

• следваща мутация (модификация на ген в кодирането на индивида)
• след рекомбинацията на генетичния код на две индивиди)

Според еволюционния принцип естествен подбор, от едно поколение на друго ще бъде облагодетелствано оцеляването на най-добрите (добре адаптирани) индивиди.

Терминология

• индивидуален (хромозома) = кандидат-решение, кодирано като в лаборатория 2
• хромозомите са съставени от гени (черти)
• всеки ген е в хромозомата на една позиция (локус/локуси)
• се наричат ​​различните стойности, които един ген може да приеме алел

псевдо

компоненти

Лицата се избират в новата популация с вероятност, пропорционална на фитнес.

Някои хора могат да имат повече деца в новата популация, други могат да имат 0. обиколка

Индивидите се "бият" в групи от m, избрани на случаен принцип. Избират се най-добрите n във всяка група.

Въз основа на йерархия

Подобно е на избора на щастливо колело, с тази разлика, че вероятността за избор не е пропорционална на годността, а зависи от позицията на индивида в подредения списък на индивидите от популацията. Това намалява шанса слабите индивиди да бъдат „задушени“ от тези с много висока физическа форма.

Промяна на индивидите Това се извършва чрез генетични оператори, кръстосване и мутация.

пресичане

Той съчетава характеристиките на две родителски хромозоми, което води до потомство, което частично наследява тези характеристики. Засяга хромозомите с вероятност настолен компютър. Броят на лицата, участващи в кръстосване в поколение, се изчислява от pc * pop_size.

Избор на лица, които ще страдат от кръстосване:

• Пресичане с точка на изрязване, избрана на случаен принцип. Пример:
• Пресичане с n произволно генерирани точки на отрязване. Пример (n = 3):
• Равномерно кръстосване: за всеки локус е вероятностно избран генът на един родител.
• мутация

  Той променя един или повече произволно избрани гени на хромозома. Вероятността за мутация се определя от параметъра следобед. Броят на мутиралите гени се изчислява по pm * хромозома_дължина * pop_size. Прилагане на мутацията:

  Ако представянето се използва като низ от битове, мутацията се състои в промяна на стойността на съответния бит от 0 на 1 или обратно.

  "Стандартни" параметри pop_size = 50 индивида вероятност за мутация pm = 0,01 вероятност за кросоувър pc = 0,25 Критерии за спиране постигане на TMAX брой итерации без подобрение на решението в последните итерации TW (или TW (t)) .

  Прилагане на генетичен алгоритъм за намиране на крайните точки на функциите, предложени в лаборатория 1.

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

  Направете кратък доклад (текстов формат), в който се посочва:

  • минимално, средно и максимално време за изпълнение
  • най-доброто и най-лошото решение, както и средната стойност на решенията, получени след няколко пробега.

  ---