Генетски алгоритми; Лабораторија 3

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

содржина

Генетски алгоритми

Методот е инспириран од еволутивната теорија на Дарвин. Работа со А. население за кандидатско решение, што еволуира и се прилагодува на околината (во овој случај, околината е функцијата што треба да се оптимизира). Генотипот се менува:

• следната мутација (модификација на ген во кодирање на индивидуа)
• следејќи ја рекомбинацијата на генетскиот код на две лица)

Според еволутивниот принцип преживување на најсилните, од една генерација до друга ќе се фаворизира опстанокот на најдобрите (добро прилагодени) поединци.

Терминологија

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

псевдо

компоненти

Поединци се избрани во новата популација со веројатност пропорционална на подготвеноста.

Некои поединци може да имаат повеќе деца во новата популација, други може да имаат 0. турнеја

Поединци „се тепаат“ во групи од м, избрани по случаен избор. Избрани се најдобрите n во секоја група.

Врз основа на хиерархијата

Слична е на изборот на среќен тип на тркало, со таа разлика што веројатноста за избор не е пропорционална на фитнесот, туку зависи од позицијата на поединецот во подредената листа на лица во населението. Ова ја намалува можноста слабите лица да бидат „задушени“ од оние со многу висока кондиција.

Промена на поединци Тоа се прави преку генетски оператори, вкрстување и мутација.

крст

Ги комбинира одликите на два родителни хромозоми, што резултира во потомство што делумно ги наследува овие карактеристики. Влијае на хромозомите со веројатност Компјутер. Бројот на индивидуи кои учествуваат во вкрстување во една генерација се проценува според големината на компјутер *.

Избор на лица кои ќе страдаат од вкрстување:

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

  Тој менува еден или повеќе произволно избрани гени на хромозомот. Веројатноста за мутација е дадена со параметарот п.м.. Бројот на мутирани гени се проценува според големината на пом * хромозомот_поп *. Примена на мутацијата:

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

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

  Имплементирајте генетски алгоритам за да ги пронајдете крајните точки на функциите предложени во лабораторијата 1.

  Графикон како се развиваат решенијата. Графиконот мора да ги изрази максималната, минималната и просечната подготвеност на секоја генерација.

  Направете краток извештај (формат на текст) во кој се наведува:

  • минимално, просечно и максимално време на извршување
  • најдобро и најлошо решение, како и просекот на решенијата добиени по голем број на работи.

  ---