75.5. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

 
  THIS SECTION IS UNDER CONSTRUCTION  
 


  


Задачи:

Сводятся к поиску экстремумов в пространстве состояний.
  


  


  

А случаи могут быть гораздо более сложные.


  


  


  


Основые принципы
	Кодирование
		прямое бинарное
		Грея
		F.P
		специальные алфавиты
	Оценка
	Скрещивание

Кодирование:
  



Размер популяции
	< 10 мало
	20-500 нормально
	1000 много

Отбор
	Турнир
		между N случайно выбранными членами популяции
	Элитаризм
		выбираем N лучших особей
	Рулетка
		вероятность отбора особи пропорцианальна ее полезности

  


Агрессивные варианты отбора
	отбор с усечением
	турнирный отбор с размером турнира 4 или больше
	уничтожение дубликатов

	

Задача представляется в виде вектора (хромосома)
Делается начальная популяция
для каждого поколения
	Тест приспособленности (оценка)
	Селекция (отбор особей к скрещиванию)
		например с оценкой выше средней выживают
		ниже средней нет
	Приминение к этим особям операций
		Кроссовер
			Одноточечный кроссовер
			Многоточечный кроссовер
			Uniform кроссовер (каждый бит случайно)
		Мутация
	Если решение найдено то конец.
затем повторяется для следующего поколения



  
  Скрещивание 
 

  



Одноточечный кроссовер:
  


Многоточечный кроссовер:
  


Uniform кроссовер:
(для каждого бита)
  


Арифметический кроссовер:
  


Пример кроссовера для графов:
  




  
  Мутации 
 

Простая одноточечная мутация
  


Мутация вставка
  


Мутация инверсия
  


Мутация перемешевание
  


Мутация обмен
  





  
  Эволюция