валеева. Решение на лучшее в специально определенной окрестности

• Название: Решение на лучшее в специально определенной окрестности
• Дата: 25.02.2020
• Размер: 3.15 Mb.
• Имя файла: валеева.docx
• Тип: Решение; #109780
• страница: 6 из 19

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

Идея заимствована у живой природы и состоит в организации эволюции, целью которой является получение оптимального решения в сложной комбинаторной задаче:



Начальная популяция: P = {S1, S2, … , Sk} — набор допустимых решений исходной задачи.

Шаг эволюции: выбираем из популяции два решения, скрещиваем их, применяем мутацию, локальную перестройку и добавляем в популяцию, затем наихудшее решение удаляем из популяции.

Общая схема алгоритма

1. 
   Выбрать начальную популяцию P и запомнить рекорд .
   

2. 
   Пока не выполнен критерий остановки делать следующее:
   

1. 
   Выбрать “родителей” из популяции.
   

2. 
   Применить к оператор скрещивания и получить новое решение S’.
   

3. 
   Применить к S’ оператор мутации и получить новое решение S’’.
   

4. 
   Применить к S’’ оператор локального улучшения и получить новое решение S’’’.
   
5. 
   Если f (S’’’) < F*, то сменить рекорд F* := f (S’’’).
   

6. 
   Добавить S’’’ к популяции и удалить из нее наихудшее решение.